Subject: Re: [Cellar] clarity for the EBML CRC Element

From: Steve Lhomme <[email-masked]>
Date: Sat, 2 Jan 2016 09:41:16 +0100

I'd say the reference here is libebml. It may be the only
implementation that handles CRC32.

2015-12-30 1:10 GMT+01:00 Dave Rice <[email-masked]>:
> The EBML CRC Element has many contradictory definitions.
>
> Version 1: The Matroska draft states:
>
> "The CRC is computed on all the data of the Master element it's in. The CRC element should be the first in it's parent master for easier reading. All level 1 elements should include a CRC-32. The CRC in use is the IEEE CRC32 Little Endian"
>
> Version 2: An older Matroska draft at http://matroska.org/technical/specs/rfc/index.html states:
>
> "The CRC32 container can be placed around any EBML element or elements. The value stored in CRC32Value is the result of the CRC-32 [CRC32] checksum performed on the other child elements.
>      CRC32 := c3 container [ level:1..; card:*; ] {
>        %children;
>        CRC32Value := 42fe binary [ size:4; ]
>      }”
>
> Version 3: The EBML draft states:
>
> "The CRC is computed on all the data from the last CRC element (or start of the upper level element), up to the CRC element, including other previous CRC elements. All level 1 elements SHOULD include a CRC-32."
>
> Issue with Version 1:
> Usually the Matroska version is considered authoritative since that documentation was the most maintained; however, in this case the Matroska definition doesn’t make sense as it implies that the CRC Element is documenting a CRC value of data that includes the CRC Element itself.
>
> Issue with Version 2:
> This definition refers the CRC Element as a Master-element (aka “container”) with a sub-element (called “CRC32Value" 0x42FE) that contains the hash. AFAIK there has never been such an implementation. Additionally this draft does not have an open license.
>
> Issues with Version 3:
>
> I think there is a typo and that: "All level 1 elements SHOULD include a CRC-32” should be "All level 1 Master-elements SHOULD include a child CRC Element.”
> The procedure for using multiple CRC Elements within a single Master-element seems very inefficient with each subsequent CRC representing the data of all prior CRC Elements within the same Parent Element. This is like a rolling checksum although I’m not sure that is what was intended.
> Also the definition implies that the CRC element can occur multiple times within the parent element while the definition in both EBML and Matroska clarifies that CRC is not a ‘multiple' element.
>
> So, can we clarify the following:
>
> - The CRC Element may only occur 0 or 1 times as a child element of a Master-Element.

Agreed.

> - That the CRC Element is a binary element and not a Master-element

Correct

> - There is no definition for a CRC32Value element

The code in libebml assumes the element can be anywhere and the value
is processed in memory on all the data of the Master element minus the
Checksum itself.
https://github.com/Matroska-Org/libebml/blob/master/src/EbmlMaster.cpp#L537

That seems not practical, especially because of the in-memory step.
There are also a TODO that raises some issues with Checksum:
  /// \todo find another way when not all default values are saved or
(unknown from the reader !!!)

> - Is there a placement requirement or suggestion for the use of the CRC element within a parent (i.e. "should be the first in it's parent master”)

IMO it should be first. It doesn't make sense to signal it at the end.
Either it's present and first or it's not there. Hopefully that will
be the only element that needs to come first.

> - What data exactly does the CRC value represent?
>         All Element Data of the parent element (unfeasible)?

It's feasible, although that implies knowing you need to process the
checksum while doing the children, if you don't want to do a fake
render in memory afterwards.

>         The entire Parent Element (including the parent’s Element ID, Element Data Size, and Element Data) (also unfeasible)?

IMO only the data inside the Master element it's contained.

>         All Element Data of the parent element excepting the child CRC element?
>         The entire Parent Element (including the parent’s Element ID, Element Data Size, and Element Data) excepting the child CRC element?
>         All data from the beginning of the Master-element up to the beginning of the CRC Element?
>         All data from the beginning of the Master-element’s Element Data up to the beginning of the CRC Element?

It should also be the data as they are rendered, meaning elements not
written (default) or with a 0 size (default value) should be processed
as they are written in the file, and not as they might be represented
in memory. That should make some CRC tools work even without knowing
the semantic.

> I understand these clarifications have an impact on the validity of existing EBML implementations, but I’ve rarely seen any implementation of the EBML CRC element (better documentation may encourage such implementations ;)
>
> Dave Rice
> _______________________________________________
> Cellar mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cellar

-- 
Steve Lhomme
Matroska association Chairman

---

From: Dave Rice <[email-masked]>
Date: Sun, 3 Jan 2016 22:31:00 -0500

Hi,

> On Jan 2, 2016, at 3:41 AM, Steve Lhomme <[email-masked]> wrote:
> 

That seems unexpected to me. If the CRC represents data that is not present but given default values from the EBML Schema, then the CRC validation requires full semantic knowledge. My preference would be to checksum the data as stored rather than as the data is understood (especially since that understanding may change).

> be the only element that needs to come first.

Technically at Level 0 the EBML Master-element also has a requirement to appear first. :)

> render in memory afterwards.

I mean that it isn’t feasible for a CRC32 element to represents the whole Element Data of the Master-element since then the checksum would have to be a checksum of data that includes itself.

> IMO only the data inside the Master element it's contained.

Agreed, but that data minus the CRC32 element itself (as you note above).

> in memory. That should make some CRC tools work even without knowing

I haven’t yet found a file in the wild with CRC Elements within Master-elements that contain non-present mandated child elements that have defaults.

>> I understand these clarifications have an impact on the validity of existing EBML implementations, but I’ve rarely seen any implementation of the EBML CRC element (better documentation may encoura…

Here is a survey of Matroska files in the wild which contain CRC32 elements.

Sample 1 ===============================================================
File: http://archive.org/download/159753000/blackpool_1-0_manutd-regmo.blogspot.com.mkv
Muxing App: Haali DirectShow Matroska Muxer 1.10.262.12
Writing App: gdsmux
Note: This file has 5 CRC32 Elements. All Level 1 Master-elements include a CRC32 Element as the first child Element. The CRC32 value represents the remaining data of the Master-element that it is contained within. This file is done exactly as suggested by the Matroska spec (Version 1 noted above). But it is invalid according to the EBML draft Specification and older Matroska RFC Draft (Version #2 and #3).

Sample 2 ===============================================================
http://archive.org/download/3asq.comBNXFANTASTECMidoHeRo/3asq.com-BNX-EP 01-[F A N T A S T E C-MidoHeRo].mkv
Muxing App: libebml-0.7.5 & libmatroska-0.7.7
Writing App: VirtualDubMod 1.5.10.2 (build 2540/release)
Note: Similar to sample #1 but includes 1,413 Cluster elements so LOTS MOAR CRC values!

Other samples:
File: http://archive.org/download/Al3asqAlfilsofOnePiece3/[Al3asq - Alfilsof] One Piece 0357.mkv
Muxing App: libebml-0.7.7 & libmatroska-0.8.1
Writing App: VirtualDubMod 1.5.10.3 | www.virtualdub-fr.org || (build 2550/release)
Note: Similar as sample #2

File: http://archive.org/download/BAR2010-2011/LaLiga/05tur_Atletic_Bilbao-Barcelona_(0-1)_Keita_HD.mkv
Muxing App: Haali DirectShow Matroska Muxer 1.9.42.1
Writing App: gdsmux
Note: similar to #1

File: http://archive.org/download/L0rdGwynSuperGhoulnGhostChouMakaiMura/L0rd_Gwyn - Super Ghoul'n'Ghost - Chou Makai Mura.mkv
Muxing App: libebml v0.7.8 + libmatroska v0.8.1
Writing App: Cyberlink Matroska Muxer v1.0.0

File: http://archive.org/download/OP08-Shashah.tv/OP357_Shashah-tv.mkv
Muxing App: libebml-0.7.7 &amp; libmatroska-0.8.1
Writing App: VirtualDubMod 1.5.10.3 | www.virtualdub-fr.org || (build 2550/release)

I looked over about 20 more samples but all of them either used Haali or libebml as muxers and gdsmux, VirtualDubMod, Cyberlink, or mkvclean as writers. All reviewed samples included CRC32 (if at all) as the first child element of all level 1 Master-elements. I could not find any samples with a CRC32 Element at any other level besides level 2 or a CRC32 Element that wasn’t the first child element of its parent. From this I think that the EBML and earlier Matroska RFC Draft definitions of CRC (version #2 and #3) are either wrong or never apparently used.

I propose to refine the Matroska.org definition of the CRC element as move that to the EBML specification.

Dave Rice

---

From: Steve Lhomme <[email-masked]>
Date: Mon, 4 Jan 2016 09:03:03 +0100

Agreed.

---

From: "Sebastian G. <bastik>" <[email-masked]>
Date: Mon, 4 Jan 2016 19:35:39 +0100

04.01.2016, 04:31 Dave Rice:

[trimmed to maker it more readable and just have the relevant part]

> If the CRC represents data that is not present but given default
> values from the EBML Schema, then the CRC validation requires full
> semantic knowledge. My preference would be to checksum the data as
> stored rather than as the data is understood (especially since that
> understanding may change).

I fully agree with the statement that a checksum should be of whatever
is actually present within a segment the checksum covers. Particularly
if the default values are omitted.

It makes it easier to check the checksum with trivial validators. This
would not be the case when, as Dave points out, default values change.
Something easy as a checksum should not have to take version
considerations into account or worse actually having to be able to
'understand' what the checksum is for.

If I create a hash of a file with several tools implementing the same
hash-function and get different results I would be confused. The same
would be true if different tools that handle matroksa files tell me
different answers on the validity of checksums within them.

--
Sebastian

---

From: Dave Rice <[email-masked]>
Date: Tue, 5 Jan 2016 23:35:24 -0500

> On Jan 4, 2016, at 3:03 AM, Steve Lhomme <[email-masked]> wrote:
> 

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.

The revision is with a pull request at https://github.com/Matroska-Org/ebml-specification/pull/46.

Dave Rice

---

From: Jerome Martinez <[email-masked]>
Date: Wed, 6 Jan 2016 19:16:29 +0100

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

---

From: Dave Rice <[email-masked]>
Date: Sat, 9 Jan 2016 16:06:49 -0500

Hi,

> On Jan 6, 2016, at 1:16 PM, Jerome Martinez <[email-masked]> wrote:
> 
>> 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.
> 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
> "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."
> 
> "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):
> 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).
> 
> width=32 poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xcbf43926 name="CRC-32"
> 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"?)

Based on Jerome’s comments here is an update to the CRC Element for the EBML specification:

===========
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, with initial value of 0xFFFFFFFF. The CRC value MUST be computed on a little endian bitstream and MUST use little endian storage.
===========

I agree with Jerome that to refer simply to “CRC” presumes a lot and that it’s better to be explicate with initial values and endianness of computation of data and storage of the hash. I updated the pull request at https://github.com/Matroska-Org/ebml-specification/pull/46 to include the new definition, https://github.com/Matroska-Org/ebml-specification/pull/46.
Dave Rice

---

From: Steve Lhomme <[email-masked]>
Date: Mon, 11 Jan 2016 09:50:08 +0100

2016-01-06 5:35 GMT+01:00 Dave Rice <[email-masked]>:
> 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

I think it should be "MUST 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.

---

From: Steve Lhomme <[email-masked]>
Date: Mon, 11 Jan 2016 10:15:46 +0100

> Based on Jerome’s comments here is an update to the CRC Element for the EBML specification:

Looking good apart from the SHOULD be first vs MUST be first. But
maybe the wording might be altered to say it MUST be the first, when
it is present.

---

From: Dave Rice <[email-masked]>
Date: Mon, 11 Jan 2016 20:50:51 -0500

> On Jan 11, 2016, at 4:15 AM, Steve Lhomme <[email-masked]> wrote:
> 

The text is updated to add a mandate for the CRC-32 Element to be the first Element within its Parent, when used. All 119 Matroska files that use CRC-32 Elements found within archive.org as well as all of the Matroska test files adhere to mandate, so I think a backwards compatibility issue is unlikely. I also updated the pull request: https://github.com/Matroska-Org/ebml-specification/pull/46.

==============
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. When the CRC-32 Element is present, the CRC-32 Element MUST be the first ordered Element within 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, with initial value of 0xFFFFFFFF. The CRC value MUST be computed on a little endian bitstream and MUST use little endian storage.
==============

The remaining issue in the CRC-32 definition regards the use of the word “SHOULD”. Obviously the existing implementations do not appear to respond to the RFC2119 meaning of the word “SHOULD” but the term “MAY” seems more realistic to the actual usage.

Some suggestions (for reference RFC 2119 on Requirement Indicators https://www.ietf.org/rfc/rfc2119.txt):

- Change SHOULD to MAY, and let the Document Types (matroska, webm, etc) opt to add a stricter requirement.

- Change SHOULD to MAY for EBML version 1 and define EBML version 2 with MUST.

- Think of a valid and acceptable explanation for when the SHOULD should and should not be adhered to.

Other suggestions welcome.

[…]

Dave Rice