Consistent Overhead Byte Stuffing¶

A reversible byte code that removes a reserved delimiter from packet bodies while bounding worst-case expansion to roughly one byte per 254 input bytes.

Version: v3 · 2026-09-19 · History
Domain-specific #: 1545
Domain group: Interdisciplinary & Synthetic
Origin domain: Data Science & Analytics
Subdomains: Data Communications, Packet Framing → Data Science & Analytics
Aliases: COBS

Core Idea¶

Consistent Overhead Byte Stuffing (COBS) is a reversible encoding for delimiter-framed byte packets. One byte value—usually zero—is reserved to mark packet boundaries on a serial stream. Because an arbitrary payload may itself contain zero, the encoder transforms the payload into a zero-free sequence; the decoder reconstructs every original zero from compact distance codes. An actual zero can then delimit the encoded packet unambiguously.

The distinctive commitment is not merely escaping a forbidden symbol. COBS tightly bounds the worst-case expansion. Cheshire and Baker designed it for packet media where an unexpectedly doubled frame could violate a fixed transmission-time or buffer limit; their original paper guarantees no more than about one added byte per 254 payload bytes, while keeping average overhead competitive with conventional stuffing.

How would you explain it like I'm…

No-Zero Message Trick

Imagine sending a long line of numbered beads, with a special zero bead meaning "this message is over." But what if your message has zero beads inside it? Consistent Overhead Byte Stuffing rewrites the message so it has no zeros, using little notes that say how far away each missing zero was. The other person can put the zeros back exactly, and the rewritten message is only a tiny bit longer, never a lot longer.

Hide the Zeros, Mark the End

Computers sending data over a wire need a way to show where one message ends and the next begins. A common trick is to use a zero byte as the "end" marker. But the message itself might contain zeros, which would confuse things. Consistent Overhead Byte Stuffing, or COBS, changes the message so it has no zeros inside, replacing them with small counts that say how far it is to the next zero. The receiver uses those counts to rebuild the original message exactly. The special part is that COBS always adds only a tiny, predictable amount of extra data, no matter what the message contains.

Bounded-Overhead Delimiter Framing

Consistent Overhead Byte Stuffing (COBS) is a reversible way to encode packets sent on a serial byte stream where one byte value, usually zero, marks packet boundaries. Since a payload can contain zeros, the encoder converts it into a sequence with no zeros, replacing them with compact codes that give the distance to the next original zero. Then a real zero can safely mark the end of the encoded packet, and the decoder restores every original zero exactly. What makes COBS special is not just avoiding a forbidden byte, but tightly bounding the worst-case size increase: Cheshire and Baker's design adds at most about one byte for every 254 bytes of payload, while average overhead stays competitive. Older stuffing schemes could, in the worst case, nearly double a packet, which could break fixed buffer sizes or transmission-time limits.

Consistent Overhead Byte Stuffing (COBS) is a reversible encoding for delimiter-framed byte packets. One byte value, usually zero, is reserved to mark packet boundaries on a serial stream; since the payload may itself contain that value, the encoder transforms it into a zero-free sequence in which each original zero is represented implicitly by compact distance codes, and the decoder reconstructs the zeros exactly. An actual zero then delimits the encoded packet unambiguously. The distinguishing commitment is not simply escaping a forbidden symbol but tightly bounding worst-case expansion. Cheshire and Baker designed COBS for packet media where an unexpectedly doubled frame could violate a fixed transmission-time or buffer limit, and their original paper guarantees no more than about one added byte per 254 payload bytes while keeping average overhead competitive with conventional stuffing. The concept thus combines four roles: delimiter exclusion, exact reversibility, bounded block length, and content-independent worst-case overhead. Together these support deterministic buffer sizing and recovery after malformed frames; a generic encoder, escape convention, or checksum does not by itself provide them.

Scope of Application¶

COBS applies to byte-oriented serial or datagram links that use an in-band delimiter and require a predictable encoded maximum. Embedded controllers, packet radios, telemetry links, bootloaders, and host-device protocols are natural settings because memory and airtime are often statically budgeted.

Its literal scope does not require a physical serial cable. Any ordered byte channel carrying concatenated delimiter-separated records can use it. What matters is that packet boundaries must be rediscovered from the stream, payloads are arbitrary byte strings, and one symbol can be reserved.

Clarity¶

The code byte denotes a block length including itself, not simply the number of literal bytes. Thus a code of three is followed by two literal bytes; if the block is not the maximal-run case and another block follows, the decoder reconstructs a zero after those bytes. The maximum value 255 covers a code byte plus 254 literal bytes and suppresses implicit-zero insertion.

Manages Complexity¶

COBS converts content-dependent framing risk into a fixed buffer and airtime budget. An engineer can allocate for the maximum encoded length without scanning for a worst-case density of escaped bytes. This is especially useful when hardware limits packet duration or direct-memory-access buffers have fixed capacity.

The algorithm also localizes resynchronization. If zero never appears inside a valid encoded body, every observed zero is a candidate packet boundary.

Abstract Reasoning¶

The zero-free invariant follows by construction. Input zero bytes are not copied; they close blocks. Nonzero bytes are copied as literals, while all generated code values lie from one through 255. Therefore an encoded body contains no zero.

For reversibility, each nonmaximal code identifies how many literal bytes precede the next omitted zero. The decoder copies exactly those bytes and restores one zero when another block follows.

Knowledge Transfer¶

Literal transfer occurs wherever a forbidden delimiter must be removed from arbitrary byte payloads with bounded expansion. The same block and decoder invariants apply across radio, UART, USB virtual serial, and stored delimiter-separated records.

The broader idea—replace repeated local escapes with amortized distance metadata—can inspire other encodings, but it is not COBS unless the byte-level code and maximal-run semantics are preserved. Similarly, “bounded overhead” transfers as a design criterion, whereas the numerical one-per-254 result depends on an eight-bit code alphabet.

Relationships to Other Abstractions¶

Current abstraction Consistent Overhead Byte Stuffing Domain-specific

Parents (1) — outgoing typed relations

Consistent Overhead Byte Stuffing is a kind of Encoding And Decoding Prime

prime:encoding_and_decoding is the broader abstraction this entry instantiates because COBS specifies coordinated inverse byte transformations under a shared wire scheme.

Hierarchy path (1) — routes to 1 parentless root

Consistent Overhead Byte Stuffing → is a kind of Encoding And Decoding → includes Transformation → is a kind of, typical Function (Mapping)

Neighborhood in Abstraction Space¶

Consistent Overhead Byte Stuffing sits in a sparse region of the domain-specific corpus (93^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25