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

v2 · 2026-09-06 · History

Domain-specific #

1545

Origin domain

data communications

Subdomain

packet framing

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.

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) — more general patterns this builds on

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

  prime:encoding_and_decoding is the minimal parent because COBS specifies coordinated inverse byte transformations under a shared wire scheme.

Hierarchy path (1) — routes to 1 parentless root

• Consistent Overhead Byte Stuffing → Encoding And Decoding → Transformation → 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 (1565 abstractions)

Nearest neighbors

• Lempel–Ziv–Welch — 0.79
• Interpreter — 0.77
• Insecure Deserialization — 0.77
• Fallacy of Zero Transport Cost — 0.77
• Plaintext — 0.77

Computed from structural-signature embeddings · 2026-09-08