Consistent Overhead Byte Stuffing (COBS) is an algorithmic solution for framing packetized data across serial media where a reserved byte value (typically 0x00) denotes a packet boundary. Unlike legacy methods such as HDLC, which exhibit a 100% worst-case overhead, COBS provides a strictly bounded overhead of $\lceil n/254 \rceil$ bytes for an $n$-byte payload. This predictability is critical for real-time systems where jitter must be minimized. The algorithm operates by replacing zero-value data bytes with an offset pointer to the subsequent zero byte, thereby ensuring the data payload is free of the framing delimiter.
Technical Summary
Objective: To achieve unambiguous packet framing by eliminating reserved delimiter bytes from the data payload while maintaining a deterministic overhead.
Delimiter Management: COBS utilizes 0x00 as the framing marker. By replacing all internal zeros with offsets to the next zero byte, the algorithm ensures that any detected 0x00 byte is strictly an end-of-packet indicator.
Predictable Overhead:
Minimum Overhead: 1 byte per packet.
Worst-Case Overhead: $\lceil n/254 \rceil$ bytes.
Jitter Reduction: Highly efficient compared to variable-length stuffing schemes (like HDLC), making it ideal for real-time applications requiring bounded transmission latency.
Encoding Logic: The algorithm processes data in groups of up to 254 non-zero bytes. It uses a "code" byte (overhead byte) to store the offset to the next zero byte, essentially creating a linked-list structure within the encoded stream.
Key Requirements:
Lookahead: Requires the encoder to be aware of the position of the first zero byte within a 254-byte window.
Reversibility: The process is strictly deterministic, allowing the receiver to reconstruct the original data sequence by interpreting the offset pointers.
Implementation Efficiency: As shown in the provided C reference code, the algorithm is computationally inexpensive, involving simple byte-wise iteration and pointer manipulation.
Comparison to Legacy Protocols: While HDLC is common, it is susceptible to doubling the packet size in the worst case; COBS is specifically engineered to mitigate this vulnerability, offering superior performance for robust communication stacks.