leb128() contradicting constraints

[podborski]

I see two contradicting statements in the definition of leb128().

It is a requirement of bitstream conformance that the value returned from the leb128 parsing process is less than or equal to (1 << 32) - 1.

constricts with

It is a requirement of bitstream conformance that the most significant bit of leb128_byte is equal to 0 if i is equal to 7. (This ensures that this syntax descriptor never uses more than 8 bytes.)

First statement limits the number of bytes to 5. Second says that the limit is 8. I guess the first one wins :)

[agrange]

Yes, looks like i should range from 0..4, and the test should be:

It is a requirement of bitstream conformance that the most significant bit of leb128_byte is equal to 0 if i is equal to 4. (This ensures that this syntax descriptor never uses more than 5 bytes.)

(assuming the max value is correct, (1 << 32) - 1).

Can/did you file an issue against the AV1 spec please.

Thanks, Adrian

On Tue, Aug 27, 2024 at 12:19 PM Dimitri Podborski @.***> wrote:

I see two contradicting statements in the definition of leb128() https://aomediacodec.github.io/av1-spec/#leb128.

It is a requirement of bitstream conformance that the value returned from the leb128 parsing process is less than or equal to (1 << 32) - 1.

constricts with

It is a requirement of bitstream conformance that the most significant bit of leb128_byte is equal to 0 if i is equal to 7. (This ensures that this syntax descriptor never uses more than 8 bytes.)

First statement limits the number of bytes to 5. Second says that the limit is 8. I guess the first one wins :)

— Reply to this email directly, view it on GitHub https://github.com/AOMediaCodec/av1-spec/issues/356, or unsubscribe https://github.com/notifications/unsubscribe-auth/AACCQPVQNWYR5GQG2TCDANLZTTGLLAVCNFSM6AAAAABNGY2TQ2VHI2DSMVQWIX3LMV43ASLTON2WKOZSGQ4TAMJVGM2DKNY . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[agrange]

Theoretically, we could also extend the constraint to state that the most significant 4 bits of byte 4 should be 0. Not suggesting we do that though.

On Tue, Aug 27, 2024 at 12:43 PM Adrian Grange @.***> wrote:

Yes, looks like i should range from 0..4, and the test should be:

It is a requirement of bitstream conformance that the most significant bit of leb128_byte is equal to 0 if i is equal to 4. (This ensures that this syntax descriptor never uses more than 5 bytes.)

(assuming the max value is correct, (1 << 32) - 1).

Can/did you file an issue against the AV1 spec please.

Thanks, Adrian

On Tue, Aug 27, 2024 at 12:19 PM Dimitri Podborski < @.***> wrote:

I see two contradicting statements in the definition of leb128() https://aomediacodec.github.io/av1-spec/#leb128.

It is a requirement of bitstream conformance that the value returned from the leb128 parsing process is less than or equal to (1 << 32) - 1.

constricts with

It is a requirement of bitstream conformance that the most significant bit of leb128_byte is equal to 0 if i is equal to 7. (This ensures that this syntax descriptor never uses more than 8 bytes.)

First statement limits the number of bytes to 5. Second says that the limit is 8. I guess the first one wins :)

— Reply to this email directly, view it on GitHub https://github.com/AOMediaCodec/av1-spec/issues/356, or unsubscribe https://github.com/notifications/unsubscribe-auth/AACCQPVQNWYR5GQG2TCDANLZTTGLLAVCNFSM6AAAAABNGY2TQ2VHI2DSMVQWIX3LMV43ASLTON2WKOZSGQ4TAMJVGM2DKNY . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[wantehchang]

The first requirement was added later. It was added to make it possible to store a leb128 value in size_t, whether size_t is 32 or 64 bits.

The Note in that section explains why the two requirements do not contradict each other:

Note: There are multiple ways of encoding the same value depending on how many leading zero bits are encoded. There is no requirement that this syntax descriptor uses the most compressed representation. This can be useful for encoder implementations by allowing a fixed amount of space to be filled in later when the value becomes known.

So, the first requirement does NOT limit the number of bytes to 5.

[agrange]

So, the spec is self-consistent, but there doesn't seem any point in using 8 bytes to encode a value that at most can use 5? Other than, maybe, 4 byte-alignment?

We can fix this in AV2, but there doesn't seem any point to fix AV1?

On Tue, Aug 27, 2024 at 1:08 PM Wan-Teh Chang @.***> wrote:

The first requirement was added later. It was added to make it possible to store a leb128 value in size_t, whether size_t is 32 or 64 bits.

The Note in that section explains why the two requirements do not contradict each other:

Note: There are multiple ways of encoding the same value depending on how many leading zero bits are encoded. There is no requirement that this syntax descriptor uses the most compressed representation. This can be useful for encoder implementations by allowing a fixed amount of space to be filled in later when the value becomes known.

So, the first requirement does NOT limit the number of bytes to 5.

— Reply to this email directly, view it on GitHub https://github.com/AOMediaCodec/av1-spec/issues/356#issuecomment-2313413770, or unsubscribe https://github.com/notifications/unsubscribe-auth/AACCQPSG5KAQJ2GCDNDQGODZTTMD7AVCNFSM6AAAAABNGY2TQ2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGMJTGQYTGNZXGA . You are receiving this because you commented.Message ID: @.***>

[podborski]

But leb128() is always byte-aligned. I'm not so sure I understand the use-case where you would need more than 5 bytes in leb128(). Are there any examples of where non-compact representation is used?

[agrange]

To be clear, I'm not sure whether it makes sense to code more than 5 bytes, I was just suggesting one possible case that I could think of. Either way, the spec seems to over-specify what is actually required, but there is not a bug, per se.

On Tue, Aug 27, 2024 at 2:02 PM Dimitri Podborski @.***> wrote:

But leb128() is always byte-aligned. I'm not so sure I understand the use-case where you would need more than 5 bytes in leb128(). Are there any examples of where non-compact representation is used?

— Reply to this email directly, view it on GitHub https://github.com/AOMediaCodec/av1-spec/issues/356#issuecomment-2313535873, or unsubscribe https://github.com/notifications/unsubscribe-auth/AACCQPVMJRA5Y2AHLNHP4P3ZTTSOXAVCNFSM6AAAAABNGY2TQ2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGMJTGUZTKOBXGM . You are receiving this because you commented.Message ID: @.***>