The Simple Effectiveness of COBS: Framing Serial Data Without Ambiguity

The first time I stumbled upon COBS was for a simple project during my PhD. Since then, whenever I need to establish a reliable serial communication with an embedded device, this is my holy grail. Paired with CRC and a line protocol — e.g., a header carrying a message ID — COBS ensures dependable communication with almost no overhead.

Introduction: The Framing Dilemma

A reliable system architecture is built on top of stable blocks. The success of interconnected embedded systems lies in dependability, predictability, and efficiency of the communication layers. COBS is not strictly a layer, but it offers a mechanism to improve serial communication elegantly and extremely efficiently. It is suitable for applications where the integrity of a message is crucial and detecting a corrupted message is safety critical.

The recurring situation where a host talks to an embedded device over UART brings up one question: how to clearly distinguish the end of a serial frame at arbitrarily high baud rates.

As long as the payload is text, framing is not an issue: the termination character ('\n') never appears in the payload, hence it can clearly identify the end of the message. When we need to send raw data — i.e., an array of values in the range [0, 255] — this trick falls short. No value remains reserved as a termination byte for delimiting a frame. Failing to mark the boundary between subsequent communications leads to silent misalignment, where the receiver keeps decoding garbage with no means to detect the failure.

COBS solves this problem elegantly, with limited computational effort and deterministic communication overhead.

Existing solutions

We can recognize four existing ways of delimiting serial data:

1. Time gaps (e.g. ModBus RTU): infer the boundaries from silence on the line. Precise timing and synchronization at both ends are crucial for guaranteeing high speed. In an MCU-to-MCU context, where dedicated hardware timers work at microsecond-level precision, this is a viable solution. It becomes a problem specifically in host-to-MCU communication, where the host OS introduces driver latency and scheduling jitter that drastically reduce the attainable throughput by requiring long periods of silence.

2. Synchronization signals (e.g. SPI or I2C): the sender shares its TX state with the receiver through dedicated hardware (lines), making framing implicit. Clean solution that requires additional connections and protocol awareness — not suitable for generic UART applications. It's worth noting that hardware flow-control lines like RTS/CTS solve a related but distinct problem — pacing data to avoid overflowing a receiver's buffer — rather than marking frame boundaries. A UART link can have RTS/CTS flow control and still have no way to tell where one message ends and the next begins.

3. Length-prefixed frames (Netstrings, Type-Length-Value/TLV, fixed-length): the receiver knows the number of bytes to expect. Effective on paper, fragile in practice: whether the length is fixed or stored in the message header, a byte sent out of sequence, a missing byte, or a corrupted header breaks the frame being transmitted and potentially the subsequent ones.

4. End-of-frame marker (SLIP, PPP, HDLC, Base64, ASCII, COBS): the sender transforms the original payload to remove any occurrence of the reserved End-of-Frame (EoF) value; the receiver applies the reverse transform to decode the original message. ASCII needs no transformation, as it restricts the payload to printable characters excluding the EoF value. Base64 converts groups of three consecutive bytes into a 6-bit representation — de facto freeing a set of values among which falls the EoF. It introduces significant communication and computational overhead. SLIP, PPP, and HDLC rely on escape values to replace the reserved EoF value. The length of the transformed message is non-deterministic. In the worst-case scenario, the length of a transmitted frame doubles. COBS provides an elegant and deterministic solution for excluding the EoF value from the original payload. It also offers computationally efficient encoding and decoding algorithms.

How COBS works

COBS eliminates all reserved values from the payload by replacing them with pointers to the next reserved value. The standard COBS defines zero as the reserved EoF value. We can extend this concept considering any arbitrary reserved value (e.g., '\n', that is 0x0A), provided we apply the corresponding offset to the pointers.

The COBS encoder starts prepending a 1-byte pointer $P_0$ to the decoded frame. The pointer indicates the relative distance $d_0$ to the next reserved value in the original frame. When the chosen reserved value S is not zero, we need to add its value to the distance $P_0 = d_0 + S$. Being this an 8-bit operation (modulo 256), it ensures $P_0$ never matches $S$ -- unless the distance is null or 256, which is not possible, as analyzed below. In a similar manner, all the reserved values in the original message are replaced by pointers to the next reserved value. Only the last pointer points to the actual EoF that matches the reserved value.

This alone gives an indication of the integrity of the message.

This mechanism works smoothly as long as the distance between consecutive reserved bytes is below 255. When this is not satisfied, COBS introduces a rule:

insert an artificial pointer $P_n$ after a 254-byte sequence not containing the reserved value.

Consequently, the previous pointer $P_{n-1}$ takes on the value $255 + S$. This allows the receiver to distinguish between real pointers - replacing a reserved value - and artificially inserted ones: the artificial ones are pointed by pointers containing exactly $255 + S$.

Should the distance between consecutive reserved bytes be exactly 255, the artificial pointer rule applies: an artificial pointer $P_{n-1} = 255 + S$ is inserted, immediately followed by the real pointer $P_n = 1 + S$.

It follows that the minimum overhead of an arbitrarily long frame is 2 bytes: the initial pointer and the EoF. For an n-byte frame, the worst-case overhead is $1+\frac{n}{254}$.

This predictability is a massive advantage for embedded developers who must pre-allocate static memory buffers.

Light computational effort

In embedded systems, COBS decoding and encoding can happen in-place without duplicating memory buffers, saving precious resources.

COBS decoding will eventually replace every pointed byte with the reserved value. Exceptions are the first pointer and any artificially inserted pointers that are removed by shifting all the following bytes to the left.

The COBS encoder is slightly trickier, yet it can happen in the same input buffer. Assuming the first pointer can be inserted at the head without shifts involved, a secondary circular buffer is needed to contain the overhead when an artificial pointer is inserted. In the worst-case scenario, the allocated circular buffer is $\frac{n}{254}$ bytes, with $n$ the maximum frame length. Bytes in the payload are shifted rightwards for inserting every artificial pointer.

Merging COBS with DMA

An convenient improvement uses the Direct Memory Access (DMA). By combining COBS with an MCU's DMA engine, the hardware handles the raw transport stream silently in the background. Here is the workflow: the DMA collects incoming data until the unique reserved value delimiter triggers a frame-complete event. This typically happens in a dedicated memory area – for performance and configuration reasons. Only then does the MCU wake up to execute the COBS decoding. Instead of an in-place shift, the DMA plainly transfers the chunks of data interleaving consecutive pointers to the target memory buffer, while the MCU computes the original values from the pointers. This completely isolates timing-critical hardware interrupts from variable-time software execution.

The Line-Clearing Preamble

The COBS decoding algorithm embeds a "flush" or reset mechanism to synchronize the receiver's and sender's state machines. Sending a sequence of end-of-frame delimiters before transmitting the next frame ensures that any previously corrupted or interrupted communication or byte injection due to line noise is eliminated. Prefixing the stream with the delimiter forces the receiver to discard the corrupted garbage data and cleanly initialize its buffer for the incoming valid frame.

Integrity

COBS alone does not guarantee message integrity. One way to overcome this is to append a CRC to the input message before encoding it. On the receiver side, after decoding, the CRC can indicate whether message integrity is fulfilled or a resend is to be requested.

Failure detection

The combination of COBS, CRC, and line clearing preamble allows us to detect and contain several failure modes. The assumption is that during communication something goes wrong. The goal is to invalidate corrupted messages.

1. First COBS pointer gets corrupted:
   1. it matches the reserved value: the decoding resets and starts with the second transmitted byte
   2. it is not the reserved value: the decoding will generate inconsistent jumps across pointers:
      1. should the last pointer accidentally point to the EoF, the CRC will highlight the corruption
      2. should the last pointer point past the EoF, COBS logic detects the failure as soon as the next line clearing preamble is received
2. Any other COBS pointer gets corrupted: equivalent to (1.)
3. Any byte that is not a pointer gets corrupted:
   1. it matches the reserved value: the decoding of the first frame ends and the CRC detects a mismatch. The same applies to the remainder of the frame
   2. it is not the reserved value: the decoding will generate consistent output, but eventually the CRC detects a mismatch
4. The CRC bytes get corrupted: equivalent to (3.)
5. The frame is partially sent: the next line clearing preamble will invalidate the partially received message