Poprawa funkcji dekodującej LEB128

Potrzebuję zaimplementować funkcję dekodującą LEB128 ze znakiem.

Implementacje opracowałem dosłownie na podstawie opisu "Decode signed integer" z https://en.wikipedia.org/wiki/LEB128

typedef unsigned char uchar;
typedef signed long long sllong;

// raw - tabloca bajtowa
// ptr - pierwszy bajt dekodowanej liczby
// size - wielkość liczby - zazwyczaj 32 lub 64
// leb128Size - liczba bajtów liczby w tablicy, obliczona po zdekodowaniu
sllong fileStructure::leb128s(uchar * raw, int ptr, int size, int &leb128Size)
{
    sllong result = 0;
    int shift = 0;
    leb128Size = 0;
    do
    {
        // 8080808010370210 64 - runtime error: left shift of 16 by 28 places cannot be represented in type 'int'
        // 8080808080808080807F 64 - runtime error: shift exponent 35 is too large for 32-bit type 'int'
        // FFFFFFFFFFFFFFEF3F84 64 - runtime error: left shift of 127 by 28 places cannot be represented in type 'int'
        result |= (((int)raw[ptr] & 0b01111111) << shift);
        shift += 7;
        ptr++;
        leb128Size++;
    }
    while ((raw[ptr - 1] & 0b10000000));

    if ((shift < size) && (raw[ptr - 1] & 0b01000000))
    {
        // 7C712105 32 - runtime error: left shift of negative value -1
        // 7C712108 32
        // 7C712202 32
        // 7C712204 32
        // 7C712205 32
        // 7C712207 32
        // 7C71220A 32
        // 7F10E616 32
        // 7F10EE16 32
        // 7F10EF16 32
        // 70712202 32
        // 70716B22 32
        // 406A2202 32
        // 406B2400 32
        // 7E712107 32
        result |= (~0 << shift);
    }

    return result;
}

Po zaimplementowaniu według opisu z Wikipedii i sprawdzeniu kilku przypadków funkcja wydawała się działać, ale po właczeniu sanitizerów i próbie odczytu większego pliku, gdzie jest bardzo dużo liczb, dostawałem komunikaty błędów.

Informacje wklepiłem jako komentarze wraz z przypadkami testowymi. Każdy przypadek testowy, to ciąg bajtów w hex (na przykład 7C71220A znaczy ciąg 0x7c, 0x71, 0x22, 0x0A) w tablicy poczynając od ptr i wielkośc podstawiona za size. Ciąg bajtów będący przypadkiem testowym może być dłuższy niż faktycznie zawierający liczbę LEB128.

1. Co potrzeba w tej funkcji poprawić, żeby nie zmienił działania dla poprawnych przypadków (czyli 99% przypadków użytku tej funkcji, które nie są wyżej wymienione), niezależnie od podanej wielkości size?
2. Czy jest w internecie działający kalkulator LEB128 ze znakiem, gdzie mogę sprawdzić trudniejsze przypadki, czy mój kod daje poprawny wynik?

Przesuwasz bity w wartości, którą rzutowałeś na int, a następnie przypisujesz do zmiennej sllong. Podczas przesuwania bitów są one obcinane do rozmiaru wartości int. Podobnie jest w drugim.
Natomiast drugie ostrzeżenie dotyczy przypuszczalnie tylko tego, jeśli chciałbyś przesuwać bity z zachowaniem bitu znaku liczby. By przesuwać razem ze znakiem liczby potrzeba rzutować wartość na bez znaku.

ChatGPT sugerował taką korektę jednego błędu:

        result |= (~0u << shift);

To skutecznie likwidowało błąd runtime error: left shift of negative value -1, ale nie byłem w stanie zweryfikować poprawności obliczeń. Czy ta zmiana jest dobra dla poprawności obliczeń?

CzatGPT. Gemini, Claude nie potrafił rzetelnie podać wyniku dekodowania LEB128 ze znakiem dla podanego przypadku testowego, co próba, to był inny wynik, a bywało zastrzeżenie w stylu "nie jestem pewny poprawności obliczeń, ale wiem, ze tak to mniej więcej wygląda obliczanie". Nie byłem w stanie znaleźć w internecie działającego kalkulatora umiejącego obliczyć LEB128 ze znakiem dla ciągu bajtowego. Również i o to zapytałem Gemini, ale podał kilka adresów, z których żaden nie działał.

O inne błędy, to póki co nie pytałem czatów, bo nie mogę być pewien, czy odpowiedź jest rzetelna. Dlatego napisałem na forum.

overcq napisał(a):

Przesuwasz bity w wartości, którą rzutowałeś na int, a następnie przypisujesz do zmiennej sllong. Podczas przesuwania bitów są one obcinane do rozmiaru wartości int. Podobnie jest w drugim.

Tak było pierwotnie

        result |= ((raw[ptr] & 0b01111111) << shift);

To też czat Claude sugerował owe rzutowanie, o którym zapomniałem potem.

Rozumiem, ze powinno być tak jak niżej? A shift może być int?

        result |= (((sslong)raw[ptr] & 0b01111111) << shift);

andrzejlisek napisał(a):

ChatGPT sugerował taką korektę jednego błędu:

Kopiuj

        result |= (~0u << shift);

To skutecznie likwidowało błąd runtime error: left shift of negative value -1, ale nie byłem w stanie zweryfikować poprawności obliczeń. Czy ta zmiana jest dobra dla poprawności obliczeń?

Jeśli przypisujesz do zmiennej long long to powinno być raczej ~0ULL.
Co do drugiego: może tak być albo poza nawiasem a przed przesuwaniem ((sllong)( raw[ptr] & 0b01111111 ) << shift).
Zwykle używam wartości bez znaku, ale wydaje się, że w tym przypadku nie ma znaczenia, bo shift jest zawsze dodatnie.

Mam taki kształt funkcji.

Nie ma błędów, które miałem na początku, ale znalazł się następujące przypadki testowe:

80 80 80 80 80 80 80 80 80 7F - size=64
80 80 80 80 A0 F2 F1 A9 85 7F - size=64

Komunikat błędu w komentarzu.

sllong fileStructure::leb128s(uchar * raw, int ptr, int size, int &leb128Size)
{
    sllong result = 0;
    int shift = 0;
    leb128Size = 0;
    do
    {
        result |= ((sllong)(raw[ptr] & 0b01111111) << shift); // runtime error: left shift of 127 by 63 places cannot be represented in type 'long long int'

        shift += 7;
        ptr++;
        leb128Size++;
    }
    while ((raw[ptr - 1] & 0b10000000));

    if ((shift < size) && (raw[ptr - 1] & 0b01000000))
    {
        result |= (~0ull << shift);
    }

    return result;
}

W danych przykładowych dla raw jest 10 bajtów. Jeśli z każdego bajtu bierzemy 7 bitów, to tworzy się liczba 70‐bitowa, co przekracza 64 bity dostępne przypuszczalnie w long long. Albo potrzebujesz poprawić dane wejściowe, by nie przekraczały rozmiaru, albo je ‘walidować’.

@overcq: W przypadku, gdzie potrzebuję, wszystkie liczby LEB128 ze znakiem w danych wejściowych mieszczą się w zakresie 64-bitowej liczby ze znakiem. Takie założenie można przyjąć w ciemno na potrzeby rozważanego algorytmu dekodowania LEB128.

Wygląda na to, że się udało, najważniejsze, że nie sypie błędami. Liczba końcowa to owszem, jest 64-bit, ale w zapisie dopuszcza się dłuższa liczbę. Dodatkowo, nawet niewielka liczba (mieszcząca się w 63 bitach) może mieć zapis ponad 8 bajtów. Udało mi się napisać funkcję, która nie sypie błędami i zawsze konwertuje. A nawet, w przypadku liczby poza zakresem 64-bit, funkcja zwraca skrajną liczbę.

Okazuje się, że funkcja musi przewidywać dwie wersje. Standardowa wersja dla krótszych liczb (maksymalnie 8 bajtów w zapisie LEB128) i dłuższa wersja, która wykorzystuje dwie zmienne tymczasowe i przesunięcia bitowe w celu obsłużenia liczb potencjalnie do 16 bajtów, przy czym w praktyce, zapis ponad 16 bajtów zdarzy się z szansą poniżej 0,0001%. Zapis co najmniej 8 bajtów, jak widać, zdarza się pomimo liczby mieszczącej się w 64-bit.

A zasada działania z dwiema zmiennymi jest bardzo prosta:

1. Pierwsze 8 siódemek (56 bitów) umieścić w części niskiej.
2. Kolejne siódemki bitów umieścić w części wysokiej.
3. Obie części przyciąć do tylu bitów, żeby razem były 63 bity. Jeżeli obcięcie części wysokiej zmieni jej wartość, to znaczy, że przekroczono zakres i należy zwrócić wartość graniczną.
4. Przesunąć binarnie część wysoką w lewo i dodać binarnie obie części, tworząc jedną liczbę.

Ponieważ wartość ujemna jest uzupełnieniem do dwóch, to w przypadku liczby ujemnej, należy odwrócić bity części przy ich przycinaniu, a potem znowu odwrócić binarnie wartość końcową.

sllong fileStructure::leb128s(uchar * raw, int ptr, int size, int &leb128Size)
{
    // Measure number length
    leb128Size = 0;
    while (raw[ptr + leb128Size] & 0b10000000)
    {
        leb128Size++;
    }
    leb128Size++;


    // Longer number - uses two 64-bit numbers as teporary
    if (leb128Size >= 8)
    {
        sllong result_h = 0;
        sllong result_l = 0;
        int shift = 0;

        int bits_l = 56;
        int bits_h = 63 - bits_l;
        do
        {
            if (shift < bits_l)
            {
                result_l |= ((sllong)(raw[ptr] & 0b01111111) << shift);
            }
            else
            {
                result_h |= ((sllong)(raw[ptr] & 0b01111111) << (shift - bits_l));
            }
            shift += 7;
            ptr++;
        }
        while ((raw[ptr - 1] & 0b10000000));

        if ((shift < size) && (raw[ptr - 1] & 0b01000000))
        {
            if (shift < bits_l)
            {
                result_l |= (~0ull << shift);
                result_h |= (~0ull);
            }
            else
            {
                result_h |= (~0ull << (shift - bits_l));
            }

            if ((~result_h) >> bits_h)
            {
                return INT64_MIN;
            }

            result_h = (~result_h) & ((1ll << bits_h) - 1ll);
            result_l = (~result_l) & ((1ll << bits_l) - 1ll);
            return ~((result_h << bits_l) | result_l);
        }
        else
        {
            if (result_h >> bits_h)
            {
                return INT64_MAX;
            }

            result_h = result_h & ((1ll << bits_h) - 1ll);
            result_l = result_l & ((1ll << bits_l) - 1ll);
            return (result_h << bits_l) | result_l;
        }
    }
    else
    {
        sllong result = 0;
        int shift = 0;

        do
        {
            result |= ((sllong)(raw[ptr] & 0b01111111) << shift);
            shift += 7;
            ptr++;
        }
        while ((raw[ptr - 1] & 0b10000000));

        if ((shift < size) && (raw[ptr - 1] & 0b01000000))
        {
            result |= (~0ull << shift);
        }

        return result;
    }
}