Re: [Cellar] clarity for the EBML CRC Element (and some bit of FFV1 CRC)

[Jerome Martinez <[e-mail]>]

Le 06/01/2016 05:35, Dave Rice a écrit :
> [...]
>
> Here is a proposed rewrite of the CRC-32 Element definition. It is 
> based upon the matroska.org’s definition with additional edits for 
> clarity. The CRC-32 Element contains a 32 bit Cyclic Redundancy Check 
> value of all the Element Data of the Parent Element as stored except 
> for the CRC-32 Element itself. The CRC element SHOULD be the first in 
> its Parent Element for easier reading. All Elements at Level 1 of an 
> EBML Document SHOULD include a CRC-32 Element as a Child Element. The 
> CRC in use is the IEEE-CRC-32 algorithm as used in the ISO 3309 
> standard and in section 8.1.1.6.2 of ITU-T recommendation V.42. The 
> CRC value MUST use little endian storage.

CRC definition is a pain, with often implementation details different 
and missing from the spec, despite the fact developers need such details.
For example with IEEE-CRC-32, we can see on Wikipedia:
https://en.wikipedia.org/wiki/Polynomial_representations_of_cyclic_redundancy_checks
that both Gzip (similar to the one used by Matroska) and MPEG-2 are 
listed as CRC-32 (as well as "ITU-T V.42")
We also see in original FFV1 spec "The CRC generator polynom used is the 
standard IEEE CRC polynom"

But:
- MPEG-2 uses an initial content of the register of 0xFFFFFFFF and runs 
on a Big Endian bitstream (final value not stored, must be 0 if not 
reversed, 0xFFFFFFFF if reversed). Note: MPEG-2 don't claim to be IEEE 
compliant)
- Matroska uses an initial content of the register of 0xFFFFFFFF and 
runs on a Little Endian bitstream, final value is reversed and stored in 
Little Endian
- FFV1 uses an initial content of the register of 0x00000000 and runs on 
a Big Endian bitstream, final value is not reversed and stored in Big Endian
All different despite the fact they are in the "CRC-32" group.

I read section 8.1.1.6.2 of ITU-T recommendation V.42, it says:
"As a typical implementation at the transmitter, the initial content of 
the register of the device computing the remainder of the division is 
preset to all 1s"

"typical" is not "MUST."

And I don't see in section 8.1.1.6.2 that the result should be reversed.

I don't have access to ISO 3309.

So I propose to be more explicit:
"The CRC in use is the IEEE-CRC-32 algorithm as used in the ISO 3309 
standard and in section 8.1.1.6.2 of ITU-T recommendation V.42, with 
initial value of 0xFFFFFFFF. The CRC value MUST be computed on a little 
endian bitstream and MUST use little endian storage."

I already added some details on the FFV1 spec some time ago (when I 
tried to reuse MPEG-2 CRC code for FFV1):
https://github.com/FFmpeg/FFV1/commit/0e67a72a75485b95261be2e1f39258004666c4a1
(the initial value is 0x00000000)
Maybe I need to add that it must be computed on a big endian bitstream 
and that the result is stored not reversed (big endian storage is forced 
for the whole spec, so no need to add such info here) in order to be 
explicit on all implementation details.

I am not a CRC expert, just a developer facing issues when I need to 
check CRCs, so don't hesitate to correct me if I am wrong on the 
analysis of the issues I have when I implement, and maybe there are 
already a "standard" way to define a CRC at the IETF (I need to dig 
further, but I see e.g. the Polynomial in some IETF documents).

Note: checking (not a reference)
http://reveng.sourceforge.net/crc-catalogue/17plus.htm
V.42 is defined as:
width=32 poly=0x04c11db7 init=0xffffffff refin=true refout=true 
xorout=0xffffffff check=0xcbf43926 name="CRC-32"
CRC-32/MPEG-2 is defined:
width=32 poly=0x04c11db7 init=0xffffffff refin=false refout=false 
xorout=0x00000000 check=0x0376e6e7 name="CRC-32/MPEG-2"

If it is obvious that "IEEE-CRC-32" is the way it is implemented in 
Matroska and only this way, no need of details and I guess we need to 
update FFV1 spec with the same kind of details ("CRC-32/FFV1"?)


Jérôme