Parsing variable-sized data in 32-bit datastream

Question

I have a 32-bit datastream coming from a sensor. The data is encoded as a Type-Length-Value encoding. This means the first byte indicates what kind of data there is and the second byte contains the length. The body is variable sized from 1 byte to 32 bytes.

Now the problems lies in that a message can have arbitrary alignment and worse can be smaller then 32-bit which means it's possible to parse multiple packets in a single 32-bit word.

I'm honestly at a loss on how to efficiently implement this. There is just an explosion of cases. Message type is at pos 0, 1, 2, 3. Which leads to either being able to grab the length or not. Which means you MIGHT need to parse the next message type.

I unfortunately don't have the option to do back-pressure which would at least make it a bit more doable.

How to decode something like this efficiently on an FPGA?

Answer 1

I have almost always done using state machines that read from a FIFO. The FIFO is there to absorb backpressure. The decoder has to have average performance good enough for the FIFO not to fill up over time, but short-term it relies on the FIFO to ride through data that takes longer to process.

This applies to most any variable-format protocol.

Another approach is to left- (or right-align) the message on a suitable boundary, then decode process various cases in parallel. Once a case decoder sees a valid input, it'll be the only one to issue decoded output to shift the input again and activate next set of decoders.

Such alignment is done by having a decode register as wide as the longest message - say 34 bytes in the case of your sensor if I understand correctly.

The "decode register" is nothing more than a view of the output side of the FIFO. After the message is decoded and acted upon, the FIFO discards as many bytes as the decoder figured out.

The decode register may be a view into the FIFO if the FIFO is short, or it may be an actual register that absorbs data from the FIFO. Each time a message is processed, the register shifts N+2 bytes to the right, and the FIFO dispenses (34-N-2) bytes to fill the FIFO.

Of interest in this approach would be the Instruction Decoder in the Mill Architecture CPU - Video, and white paper on the same.

Answer 2

A state machine would be a straight-forward solution for assembling a full 34-byte message. Three bits in the state machine would track which of the incoming bytes is the type, if any. These 3 bits track the alignment for the rest of the message, and tell each flop of stored message which of the 4 bits of input, if any, it should take its input from. You'd also need a 3 bit word counter, to tell which of the 8 DWORDS is present at the input, and drive the output_enable/message_complete output.

It would simplify the problem if you could specify the format of the datastream to avoid the possibility of an (unpadded) message be less than 32-bits.

I would first think about, and solve the issue of what happens when the message rate is higher than the input rate (eg, if all messages are 3 bytes, thus you receive more messages than word clocks). Your SM should be either:

1. capable of emitting two messages per clock
2. specify input formatting to avoid messages shorter than 32-bits.

How you handle the multiple message case will lead you to a plan to parse the input. Eg, if you need to process two messages per clock, in some way, you'd have two instances of the message assembly FSM daisy-chained, so that you can begin assembling a second message while finishing the first, and you would be assembling two messages at the same time. Recognizing that you can receive at most 24-bits from the "other message" in any one clock, you'd need 34-bytes + 24 bits of flop storage to store two 34-byte messages.