Serialization library optimized for space? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking us to recommend or find a tool, library or favorite off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it.

Closed 8 years ago.

Improve this question

Is anyone aware of a serialization library (along the lines of Protocol Buffers) that is efficient at the bit level? I need to transport bytes over a very expensive link (leased satellite) and we need to pack those bytes as much as possible to reduce costs.

For example we ignore alignment: where the range of a value is known (e.g. 0-128) we pack that into 7 bits and use the remaining bit for the next value that needs to be packed. We pack DateTime values using only the information we need and nothing else (removing year and seconds for example and packing the result into 20 bits). Shaving two bytes off a message counts.

Currently all our messages are hand-crafted and this is error-prone. Is there something similar to protocol buffers that can pack bitfields and produce code in C and C#? I'm aware of boost's dynamic_bitset, but this is not consumable from C# (easily). Before I go ahead and write a library along the lines of the answer to this question, is there an alternative approach we could consider?

Answer 1

In this situation I would advise you to invest time into figuring out your data set and make a custom solution. My reasoning is as follows.

Should you choose something that is off-the-shelf you will be running good, stable code that is maintained by someone else and you will feel good about code reuse and will make the deadline. But if this code is not suited to your particular needs (unless you are really lucky) you will not be saving yourself as much as you could with a custom solution. Especially because it seems that you already can see a way to save yourself from sending redundant information (i.e. the year in a date time stamp).

Once you have an idea of what you want to send and remove all the information that the receiver can guess or infer from your messages then you can apply compression. And I would recommend a compression method that I have been looking at for a couple months now, Arithmetic Coding. You can find an implementation by Michael Dipperstein here but it may need a little work to plug it into your solution. A really good description of the algorithm can be found here in this pdf.

The reason I'm giving you that link instead of some C# code is that I suspect that since you mentioned a satellite link that you are dealing with an embedded system and that you are probably coding in C or C++.

Do note that my recommendation of Arithmetic Coding means that I'm recommending that you do a lot of work here.

However, my assumption is that you really need to make this efficient. With compression the efficiency comes from understanding your data-set and customizing your algorithm for it. If you're ok with a slightly less efficient approach then there are more genric algorithms out there...