[Matroska-devel] Element order in EBML/libebml

Cyrius suiryc at yahoo.com
Fri Oct 17 16:28:41 CEST 2003


Mosu:
> Regarding the VobSub issue, here's the draft for
some new elements.
>
> KaxTracks (old)
> \+ KaxTrackEntry (old)
>  \+ KaxContentEncoding (master, optional, multiple)
>   \+ KaxContentEncodingType (UInt, mandatory,
single, default 0)
>    + KaxContentEncodingMethod (UInt, mandatory,
single, default 0)
>    + KaxContentEncodingScope (UInt, mandatory,
single, default 0)
>    + KaxContentEncodingSettings (binary, optional,
single)
>
> * KaxContentEncoding: A master containing the
aforementioned
> children. Can be used multiple times. Order is
important!
> The order in which the multiple KaxContentEncoding
elements are
> stored in the file is the same order that the data
manipulation
> has been done during encoding/muxing, so a
decoder/demuxer would
> have to reverse this order.

Pamel:
> Bad!  Order sensetive data is a nono in EBML.

robUx4:
> It all sounds good to me, except for the order thing
(even though
> the Checksum already assume you keep elements in
order).
> Why not just adding KaxContentEncodingOrder under
> KaxContentEncoding ?

Mosu:
> Here's my second attempt.
>
> Preface: The last one had two drawbacks: relying on
the order
> (minor) and being totally insufficient for
encryption (I usually
> know a lot about encryption and was clearly too
preoccupied when I
> wrote my last mail).
>
> So here I go again.
>
> KaxTracks (old)
> \+ KaxTrackEntry (old)
>  \+ KaxContentEncoding (master, optional, multiple)
>   \+ KaxContentEncodingOrder (UInt, mandatory,
unique, single
>                                                   ,
default 0)
>    + KaxContentEncodingScope (UInt, mandatory,
single, default 0)
>    + KaxContentEncodingType (UInt, mandatory,
single, default 0)
>    + KaxContentCompression (master, optional,
single)
>    \+ KaxContentCompressionAlgo (UInt, mandatory,
single, default 0)
>     + KaxContentCompressionSettings (binary,
optional, single)
>    \+ KaxContentEncryption (master, optional,
single)
>     + KaxContentEncryptionAlgo (UInt, optional,
single)
>     + KaxContentEncryptionKeyID (binary, optional,
single)
>     + KaxContentSignatureAlgo (UInt, optional,
single)
>     + KaxContentSignatureHashAlgo (UInt, optional,
single)
>     + KaxContentSignatureKeyID (binary, optional,
single)
>     + KaxContentSignature (binary, optional, single)
>
> * KaxContentEncoding: A master containing the
aforementioned
>   children. Can be used multiple times. Order is NOT
important :)



Now someone will have to cut the crap !!
Either there is some incredible nonsense somewhere,
either I'm completly stupid! (that can be possible
too)

Here are a few things about how libebml and
libmatroska works (as far as I could understand) :
For master elements there are children (subelements)
that have to be present (mandatory elements) and some
that don't have to. Some elements can also be present
multiple times (that's the case of
KaxContentEncoding).
Now to enforce mandatory elements the current
implementation of libebml automatically create the
mandatory children when you create an element (e.g.
when you create a KaxTrackEncoding, libebml would
automatically create a KaxContentEncodingOrder, a
KaxContentEncodingScope, ... and add them of the newly
created KaxTrackEncoding element). Then when you need
to set the data of those mandatory subelements the
library would give you the children that has been
created in advance.
If you need to create a new children that isn't
mandatory (or for an element that can be found
multiple times) the library will create it for you
(there are some functions to do this, but one could
also create it and add it to the master) and add it in
the list of the children (IIRC libebml uses STL
containers where elements have an order here).

In this manner the order of the mandatory children
KaxContentEncodingOrder, KaxContentEncodingScope, ...
isn't respected by libebml. This means that depending
on the order in which those elements have been
declared in the Context of KaxContentEncoding, libebml
will always store them in a certain order (that may
then be different from the order in which we filled
their data).
But, provided what I wrote earlier is true, as far as
same elements are concerned (e.g. the
KaxContentEncoding elements as children of the
KaxTrackEntry element) their order is (and have to be
- see later) respected. Indeed if I add a
KaxContentEncoding to a KaxTrackEntry, then another
one, ..., their order should remain intact (provided I
was right saying that ordered STL containers are used
in libebml). The same would apply if the
KaxContentEncoding was a mandatory element that could
be present multiple times: the first occurence
(mandatory) of the element would have been created
beforehand and the other ones would have been added
after (thus still respecting the order).


If all I said here is crap then we (people relying on
libebml and libmatroska) have a serious problem. If I
said bullshit till now, this would mean that order
really can't be guaranted by libebml. What does this
imply ? Simple :
First, it's true that a KaxContentEncodingOrder
element would be necessary in KaxContentEncoding, in
order to know in which order we need to treat the
elements.
_But_ that would mean that we need such an ordering
elements for _ALL_ elements that are multiple in a
given context. So where would this be needed ? e.g. in
the KaxCluster (yes, even if most of us create them
and write them one by one, nothing tell that other or
future apps don't create a KaxSegment and multiple
KaxCluster in memory ... even so would you add in the
specs that people shouldn't hold a KaxSegment with
KaxCluster children in memory ? that would be
nonsense), but also in each KaxBlock (I let you
imagine the amount of overhead that would represent).
Why in each KaxBlock ? If the order can't be guaranted
then we need to sort the KaxBlock elements when we
read a whole KaxCluster in memory.
Some of you will say "Simple, just order them thanks
to the timecodes". Yes .. but no, what do you do with
native MPEG4 streams where frames are stored
out-of-order ? Someone knowing the MPEG4 specs would
say "Just take into account the type of the frame -
IBP - and their timecode and you can sort them too".
True, but then what do you do with (future) codecs
that would store the frame in yet another order or use
other kind of frames ? You would say "Oh sorry, I
don't know in which order the frames are stored, I
can't reorder them, you will have to wait for an
upgrade of the program to take into account this new
codec" ? If so you can already remove the lines in all
the docs about Matroska mentioning that this container
is great because applications can edit Matroska files
without having to know what is inside.

This would also mean that up to now we (devels using
libebml and libmatroska) have been writing
unpredictible data. Indeed most of us create a
KaxCluster in memory and add KaxBlock elements when
needed, and finally write the KaxCluster in the file
when we consider the Cluster full. Generally we add
the KaxBlock elements in a certain order (trying to
achieve a good stream - audio/video/text -
interleaving so that data stay in sync even at the
container level). So the order in which we added the
data is important.
Not to mention, when we read back the data from a
Matroska file we assume we get the KaxBlock elements
in the correct order.

Same goes for MPEG4. KaxBlock elements have been added
in a specific order (the coding order). If this order
can't be guaranted, then you can also remove the lines
telling that Matroska can safely store native MPEG4
streams.


Last but not least. Let's consider why a new ordering
element (KaxContentEncoding) has been asked :
> Bad!  Order sensitive data is a nono in EBML.
I don't think that's really true. Ebml by itself
introduce order (when you read an EBML stream,
elements have been written in a certain order).
The actual reason would be
"Bad! Order sensitive data is a nono in libebml."
Yeah that's true. As I said earlier in the current
libebml order of _certain_ elements (the mandatory
ones) isn't guaranted to be the one in which you wrote
them.
So that would mean that Matroska specs would have to
be changed because of a _possible_ implementation of
those specs ? (keep in mind that alexnoe wrote hiw own
library, and it seems that he doesn't have this
element order problem - Gabest too wrote his own
implementation, but I don't recall if he replaced
libmatroska only or both libs). IMHO that would be a
nonsense.
Up to now I only saw implementations being changed to
follow the specs, not the contrary.


That's my point of view. Now I may also be completly
stupid and missed something else in EBML/libebml
(that's possible). If so I guess I will just shut up
and won't write anything else before a long time :P
(as if I had written often till now ;))


Best regards
Cyrius

__________________________________
Do you Yahoo!?
The New Yahoo! Shopping - with improved product search
http://shopping.yahoo.com



More information about the Matroska-devel mailing list