Bug: bs_read_ue compiler-dependent behavior when i==32

[aizvorski]

This line has compiler-dependent behavior

https://github.com/aizvorski/h264bitstream/blob/d8e53fdaa866aff3c987a331d522044c92f37935/bs.h#L203

Found by @LostInKadath https://github.com/aizvorski/h264bitstream/pull/51#issuecomment-1798000840

(Probably gcc does what is intended here and clang on 64bit platforms is bugged)

[LostInKadath]

The minimal fix could be like:

    r = bs_read_u(b, i);
    if (i < 32)
        return r + (1 << i) - 1;
    else
        return r - 1;

But it looks quite ugly. And things go deeper, if we look closer on other implementations.

There's a bit different implementation in VLC project. They increment i up to 31. But this solution doesn't help us -- autotests do fail on x264.

VLC also have different realization of bs_read_u1() -- it's bs_read1(). They have some preventive checks, and only after checks they move the b->p pointer and increment b->bits_left.

Our implementation is quite strange -- for instance, we decrement the b->bits_left, despite the fact it could already be 0. It seems that code is unsafe, and we suffer from a lack of extrachecks.

[LostInKadath]

I was wrong about the minimal fix.

This function implements the Exponential-Golomb decoding algorithm:

static inline uint32_t bs_read_ue(bs_t* b)
{
    int32_t r = 0;
    int i = 0;

    while( (bs_read_u1(b) == 0) && (i < 32) && (!bs_eof(b)) )
    {
        i++;
    }
    r = bs_read_u(b, i);
    r += (1 << i) - 1;
    return r;
}

The Exp-Golomb coded integer number looks like: [N zero bits] 1 [N informational bits]. It can be decoded in two steps -- counting head zero bits, followed by representing 1[N informational bits] as an integer and subtracting 1 from it.

First the function reads N zero bits. It stops either reading non-zero bit or reaching some limits. That's the while-loop code.

Then it reads next N bits and represents them as an unsigned value (according to the ue-suffix). Thus we have [N informational bits]. That's bs_read_u() call.

Finally we add (1<<i), getting 1[N informational bits], and subtract 1, getting the decoded number.

So the (1<<i) step is crucial -- it restores the 1-bit, that separates leading zero bits from the "payload". If, in any case, it equals to 0, this breaks the Exp-Golomb algorithm. So it can't be omitted.

As for the failing tests -- there's a byte sequence:

00 00 00 00
00 00 59 40
00 00 ...

which in binary is:

00000000 00000000 00000000 00000000
00000000 00000000 01011001 01000000
00000000 00000000 ...

Moreover, the bs_t structure has b->bits_left==6 at the beginning of the algorithm. So two zero bits have already been read, and we have:

__000000 00000000 00000000 00000000
00000000 00000000 01011001 01000000
00000000 00000000 ...

There are 47 leading zero bits before the first 1-bit. So our coded number should contain 47 informational bits. That's neither int32_t, nor uint32_t. Houston, we've had a problem!

However, if it's true and we really need 47 bits, we don't have them. After bytes given above the bs_t structure (and the NALU) ends. =) It seems that we have another bug somewhere earlier.