9

Background: I'm writing micro controller C code to write an EBML file. EBML is like a binary XML with nested elements, but instead of start and end tags, there is a start ID, length, and then the data. I am writing this into external Flash in a low power application, so I'd like to keep the flash accesses to a minimum. Memory is also limited, because nothing is ever easy.

When I can keep the whole EBML element in memory, then generating it is easy because I can go back and fill in the length of each element after I know what that length is. The problem is what to do when I can't hold the whole element in memory. The options I see are:

  • Write what I know, then go back and add in the lengths (easiest, but adds more flash access than I want)
  • Calculate each element's length before I start writing it (relatively easy, but a lot of processor time)
  • Switch modes once my memory fills up, so that I then continue through the data, but only to calculate the lengths for elements already reserved in memory. Then write what I have in memory, and go back and continue processing the data from where I left off. (My favorite option so far)
  • Give elements a maximum or worst case length when they need to be written and their final length is not yet known. (Easier than above, but could backfire and waste space)

Question: It seems like this should be a relatively common issue that people have thought about. I know it can also happen when forming some data packets. Is there a better / more common / more accepted technique I'm missing here? Or just some terms for the issue that I can search for?

1
  • 1
    /sccs works this way: it writes checksum of all bytes in the beginning of the file after it's done writing. Works great on Unixes that can do needed file operations atomically (eg Solaris) and causes weird sporadic issues on Unixes that can't do that, eg Linux
    – gnat
    Aug 9, 2017 at 16:29

3 Answers 3

2

If you do not know how long your payload will be, that is rarely cause for worry even if you cannot remember the position and backfill the length later:

Just note down "unknown size".

That feature depends on the payload consisting of EBML-elements and the following element not being a valid child-element though.

If you want, you can later canonicalize the resulting EBML offline at your convenience any way you want, for example to "no unknown sizes, minimal size" or to "minimal size, avoid unknown sizes".


Refer to the EBML RFC Draft on matroska.org for the details.

3
  • This is great! It is something I was not aware of and it avoids the core problem, but I'd still like guidance on a good way to solve the core problem. Using an unknown size element seems like it could limit future compatibility, since old software would prematurely exit on new elements.
    – pscheidler
    Aug 9, 2017 at 19:44
  • You need the right DTD or you cannot really decode EBML. Well, if all unknown elements are sized you can skip them, but is that enough? Just post-process any EBML you want to store offline if it is. Aug 9, 2017 at 20:08
  • We're using our own schema, which will expand. It has been designed with the knowledge that older software may eventually have to skip out on some data. But this is a great feature of EBML that I was unaware of, so I accept the answer.
    – pscheidler
    Aug 10, 2017 at 14:53
0

If a single element with fixed number of subelements is too large, then perhaps you should try to divide it in schema. I don't know this format, but most probably you can define a maximum lenght in it.

For sequences you could try to define max count of subelements and "stream" remaining in next file

For elements potentially exceeding max memory size prepare a stack containing pairs: reserved element length location and length counter. On pop save current counter in current marker and add it's value to the next counter.

In general try to minimalize number of the too big elements

3
  • Well, he could probably do it for his own EBML elements, but that still doesn't help him with the parent element. Aug 9, 2017 at 22:03
  • Your idea would work, but I would rather create a system that can handle large elements, instead of constraining the schema so that it avoids large elements.
    – pscheidler
    Aug 10, 2017 at 14:50
  • This solution will work for large elements as well, just be carefull with stack size. And if it comes to schema... think of it as a language your applications are using, if one cannot handle a complex one, then the other one should adjust or a translator is required. Many developers (at least C/C++ ones I know) tend to avoid schema/design changes like it was a fire, which later result in a poor system. If other component is unable to adjust, then perhaps it is poorly decomposed/designed. If there are other reasons not to change, then you should probably consider usage of a different hardware
    – Whoot
    Aug 10, 2017 at 22:02
0

KISS and YAGNI.
Choose option #1 and if it becomes a real problem - only then reiterate on it.

At least for similar use-cases with similar binary formats, when only a couple of values had to be filled in such a manner, this is the simplest/easiest/best solution. If you have to do this on each and every chunk of data - then it might be a flaw in architecture.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.