What is a fast way to decode a data protocol like FAST in which data is encoded in bytes with bits as existence flags?

Question

A protocol like FAST for encoding data is very clever in minimizing the amount of data needed to be sent. Essentially one gets a char*, reading the first couple bytes as an integer gives you an id number which points you to instructions on how to decode the rest (i.e. it tells you the rest of the bytes are, for example, respectivley an int, a string, an unsigned int, another unsigned int, a nested message etc..) and the next couple bytes tell you (in each bit) whether the subsequent fields are there or not. 8th bit in every byte is reserved to denote boundaries between the data.

Decoding such a protocol seems impossible to do without a linear traversal of bit ops (ands, ors, shifts, bit checks)...is there any way to do this faster?

Answer 1

I think you won't find a technique or approach faster than just described. Such protocols are meant to parse them sequentially. The only reason to continue searching is to find a more convenient way to work with a data.

As far as I see, there are three ways:

• Just do it as you described below
• Use low-level framework such as Boost::Spirit which has a binary parsers.
• Try to use ready-to-go library: for example QuickFAST -- An implementation of the FAST protocol for native C++ and .NET.

Answer 2

Decoding such a protocol seems impossible to do without a linear traversal of bit ops (ands, ors, shifts, bit checks)...is there any way to do this faster?

The FAST protocol encodes values using a stop-bit approach, in other words, it parses byte by byte sequentially until it hits a byte with the 8th bit set to 1. You lose a bit in every byte doing that, but overall it is a fast way to encode many different fields without requiring a separator byte between them.

Take a look on this article about the FAST support from CoralFIX. It has a Java code example of a FAST decoder generated from an exchange XML template file.

Disclaimer: I am one of the developers of CoralFIX.