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.^[1] Their extended journal treatment analyzes the construction and comparison in greater detail.^[2]

The abstraction therefore joins four roles: delimiter exclusion, exact reversibility, bounded block length, and content-independent worst-case overhead. That package supports deterministic buffer sizing and recovery after malformed frames. A generic encoder, escape convention, or checksum does not entail it.

Structural Signature¶

Mandatory roles:

Reserved delimiter: a byte value excluded from every valid encoded packet body.
Payload partition: input is divided at delimiter-valued bytes and when a run reaches the maximum representable block length.
Code byte: each block begins with a nonzero count locating the next reconstructed delimiter or block boundary.
Literal-data run: the following nonzero bytes are copied without per-byte escape markers.
Maximum-run convention: the maximal code value terminates a full-length run without inserting a payload zero.
Inverse decoder: code values govern copying and implicit-zero reconstruction.
External frame delimiter: a reserved byte separates complete encoded packets on the stream.

Invariants: the encoded body contains no reserved delimiter; decoding a valid encoding reproduces the exact payload; a code byte never points outside its permitted block; and overhead has a small content-independent worst-case bound.^[1]

Recognition test. Show both the code-distance rule and the maximal-run exception. A protocol that merely prefixes a length, doubles every zero, or reserves a sentinel without a reversible stuffing rule is not COBS.

What It Is Not¶

COBS is not compression. It normally expands data and optimizes predictability of overhead rather than reduction in average size. It is not encryption: byte values are transformed openly and provide no secrecy or authenticity. It is not error correction or integrity checking; a checksum may accompany a COBS frame, but COBS alone cannot prove that a syntactically decodable payload is uncorrupted.

It is not packet framing by itself. The encoded body excludes the delimiter, while the transport or caller appends the delimiter between packets. It is not length-prefix framing, which communicates a packet boundary through an explicit size and has different desynchronization behavior.

It is not SLIP or PPP octet escaping. Those schemes replace each reserved occurrence locally and can have content-dependent expansion approaching one extra byte for every input byte. COBS amortizes control information across bounded runs.^[2] COBS/R and other reduced-overhead variants change terminal-block rules and should be named separately.

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.

The method is less compelling where frames already have reliable out-of-band lengths, where a transport preserves message boundaries, or where bit-level transparency is required instead of byte transparency. It also does not replace validation above the framing layer. A receiver should reject zero code bytes, truncated blocks, and codes that exceed the available input rather than treating every byte string as valid.

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.

The physical frame delimiter is not part of the encoded payload returned by the COBS encoder in many APIs. Buffer calculations must say whether they include that trailing delimiter. Likewise, “overhead” can mean code expansion alone or expansion plus framing delimiter; mixing these accounting conventions creates off-by-one claims.

Finally, zero is conventional. A bijective remapping can reserve another byte, but an implementation's wire format must agree on the reserved value. The semantic invariant is delimiter exclusion, not a metaphysical privilege for zero.

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.^[1]

The algorithm also localizes resynchronization. If zero never appears inside a valid encoded body, every observed zero is a candidate packet boundary. A malformed packet can be discarded up to the next delimiter rather than allowing one erroneous length to shift all following frames indefinitely. This property does not correct the damaged packet, but it bounds framing loss when delimiter bytes remain observable.

Implementation remains linear in payload length and can operate incrementally. The encoder maintains the current block's code location and run length; the decoder alternates between reading a code and copying its literal run. The roles are small enough for constrained devices yet precise enough for interoperability tests.

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. A maximal code identifies 254 literals without an omitted zero, preventing an artificial zero inside long nonzero runs. Induction over blocks reconstructs the original sequence.

For capacity reasoning, each full run of 254 nonzero input bytes needs one code byte, and shorter or zero-terminated runs share the same block-control mechanism. Hence worst-case expansion grows approximately by one byte per 254 bytes rather than with the number of unlucky reserved symbols.^[2]

These proofs assume syntactically valid code blocks. A corrupted code may cause a receiver to reject the current frame or misdecode bytes within it; COBS guarantees transparency and a bound, not semantic integrity.

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.

The parent Encoding and Decoding supplies the paired reversible transformation. COBS adds a specific reserved-symbol constraint, run partition, and worst-case bound that the parent does not predict.

Examples¶

Embedded zero. The payload bytes 11 22 00 33 form two runs. They encode as 03 11 22 02 33; a following 00 delimits the frame. The first code says to copy two bytes then restore zero, and the second says to copy one byte to the packet end. Decoding yields the original four bytes.

Empty payload. A common COBS encoding of an empty payload is the single code byte 01, followed on the wire by the external zero delimiter. The code represents a run with zero literal bytes; the API's exact empty-frame convention must be documented.

Long nonzero run. A run of 254 nonzero bytes begins with FF. The decoder copies 254 bytes and inserts no zero before the next block. Treating FF like an ordinary shorter code would corrupt the payload by inventing a delimiter-valued byte.

Structural Tensions¶

Predictable worst case versus occasional overhead: COBS pays block-control bytes even for benign payloads to avoid catastrophic content-dependent expansion. Diagnostic: compare the required maximum buffer, not only mean encoded size.
Framing recovery versus data integrity: delimiter exclusion helps locate the next packet but cannot authenticate the recovered one. Diagnostic: corrupt a nonzero code or literal; if decoding succeeds incorrectly, an independent integrity check is still required.
Compact codes versus malformed-input safety: count bytes make decoding simple but can request unavailable literals. Diagnostic: verify each block endpoint lies within the received frame before copying.
Wire invariant versus API convention: encoded body, trailing delimiter, and empty-packet handling may be counted differently. Diagnostic: state whether the API consumes or emits the frame delimiter and test the zero-length payload.
Autonomy versus generic encoding: Encoding and Decoding explains the round trip but not the reserved-byte, maximal-run, and bound package. Diagnostic: subtract generic reversible coding; if zero exclusion and one-per-254-style block control remain, COBS is autonomous.

Structural–Framed Character¶

COBS is highly structural: its identity is a mapping between byte strings with proofs of exclusion, inversion, and bounded expansion. It is nevertheless domain-framed because bytes, packet delimiters, serial ordering, and buffer overhead are indispensable communication-system concepts.

The algorithm carries no evaluative or institutional frame. “Consistent” refers to a worst-case resource bound, not uniform encoded length or normative quality.

Structural Core vs. Domain Accent¶

The portable core is reversible removal of a reserved symbol through bounded run-distance metadata. The domain accent fixes an eight-bit alphabet, a delimiter-framed byte stream, code value 255, and packet recovery behavior.

Changing the alphabet changes the numerical bound; replacing bytes with bits produces a related stuffing family; replacing delimiter framing with length prefixes removes the defining need. The catalog should therefore keep the named byte algorithm domain-specific while recognizing its generic encoding parent.

prime:encoding_and_decoding is the minimal parent because COBS specifies coordinated inverse byte transformations under a shared wire scheme. Serialization is related when structured records are converted to bytes, but COBS treats an already formed byte payload and does not serialize fields. Framing is related as the operational purpose, not exact coverage.

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

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

Not to Be Confused With¶

Byte stuffing generally: a family including escape-doubling and table-based schemes.
SLIP/PPP escaping: local replacement rules with different worst-case overhead.
Bit stuffing: inserts bits after patterns and works below the byte level.
Length-prefix framing: transmits size rather than excluding a delimiter.
COBS/R: a related terminal-block optimization with a different encoding rule.
Checksum or CRC: detects corruption; it does not guarantee delimiter transparency.

References¶

[1] Stuart Cheshire and Mary Baker, “Consistent Overhead Byte Stuffing,” Proceedings of ACM SIGCOMM 1997, 209–220. Author-hosted HTML and paper: https://www.stuartcheshire.org/papers/COBSforSIGCOMM/ registry ↩a ↩b ↩c

[2] Stuart Cheshire and Mary Baker, “Consistent Overhead Byte Stuffing,” IEEE/ACM Transactions on Networking 7, no. 2 (1999): 159–172. https://doi.org/10.1109/90.769765 registry ↩a ↩b ↩c