Byte Stuffing: The Complete Algorithm

In the previous two pages, we explored flag bytes for frame delimitation and escape sequences for representing reserved bytes within payload data. Now we bring these concepts together into the complete byte stuffing algorithm—the unified mechanism that enables reliable, transparent byte-oriented framing.

Byte stuffing (also called character stuffing or octet stuffing) is the process by which a transmitter inserts additional bytes into frame data to avoid confusion with protocol control bytes, and the corresponding process by which a receiver removes these inserted bytes to recover the original data.

The term "stuffing" comes from the visual metaphor of inserting (stuffing) extra bytes into the data stream, similar to stuffing padding into a cushion. Just as the padding can be removed to reveal the original cushion shape, the stuffed bytes can be removed to reveal the original data.

The byte stuffing algorithm consists of two complementary procedures: stuffing at the transmitter and unstuffing at the receiver.

Transmitter Algorithm (Stuffing):

TRANSMIT_FRAME(data):
  1. Output FLAG byte (0x7E)
  2. For each byte B in data:
     a. If B is FLAG (0x7E):
        Output ESCAPE (0x7D), then output 0x5E
     b. Else if B is ESCAPE (0x7D):
        Output ESCAPE (0x7D), then output 0x5D
     c. Else if B is in ACCM escape set:
        Output ESCAPE (0x7D), then output B XOR 0x20
     d. Else:
        Output B unchanged
  3. Output FLAG byte (0x7E)

Receiver Algorithm (Unstuffing):

RECEIVE_FRAME():
  1. Wait for FLAG byte (0x7E)
  2. Initialize empty buffer
  3. Loop:
     a. Receive next byte B
     b. If B is FLAG (0x7E):
        Return buffer as complete frame
     c. Else if B is ESCAPE (0x7D):
        Receive next byte B'
        Append (B' XOR 0x20) to buffer
     d. Else:
        Append B to buffer

Algorithm Properties:

1. Correctness: The unstuffing procedure perfectly inverts the stuffing procedure. For any input data D, UNSTUFF(STUFF(D)) = D.

2. Completeness: The algorithm handles all possible byte values (0x00-0xFF) correctly, ensuring full data transparency.

3. Determinism: Both procedures are deterministic; given the same input, they always produce the same output.

4. Single-Pass: Both stuffing and unstuffing are single-pass algorithms with O(n) time complexity, where n is the input length.

5. Streaming: The algorithms can process data byte-by-byte, making them suitable for resource-constrained environments.

The Key Insight:

The elegance of byte stuffing lies in the invariant it maintains:

After stuffing, the only occurrence of the flag byte (0x7E) in the byte stream is at actual frame boundaries.

This invariant ensures the receiver can unambiguously identify frame boundaries by scanning for flag bytes, regardless of what data the frame contains.

Let's trace through the complete byte stuffing process with a detailed example. This example will solidify your understanding of both the stuffing and unstuffing algorithms.

Original Payload Data:

Payload: [0x41, 0x7E, 0x42, 0x7D, 0x43, 0x7E, 0x7D, 0x44]
         'A'   FLAG  'B'   ESC   'C'   FLAG  ESC   'D'

This 8-byte payload contains two flag bytes (0x7E) and two escape bytes (0x7D)—requiring stuffing.

Step 1: Transmitter Stuffing

Processing each byte:

Complete Transmitted Frame:

[0x7E] [0x41] [0x7D 0x5E] [0x42] [0x7D 0x5D] [0x43] [0x7D 0x5E] [0x7D 0x5D] [0x44] [0x7E]
  ↑      ↑       ↑          ↑       ↑          ↑       ↑          ↑          ↑      ↑
START   'A'   escaped     'B'   escaped      'C'   escaped    escaped     'D'    END
              FLAG              ESC                FLAG        ESC

Size Analysis:

• Original payload: 8 bytes
• Stuffed payload: 12 bytes (4 bytes of escape sequences)
• Total frame: 14 bytes (with start/end flags)
• Overhead: 50% increase due to stuffing, plus 2 flag bytes

Step 2: Receiver Unstuffing

The receiver processes the frame between flags:

Input stream: [0x41] [0x7D 0x5E] [0x42] [0x7D 0x5D] [0x43] [0x7D 0x5E] [0x7D 0x5D] [0x44]

Processing with state machine:

Recovered Payload:

[0x41, 0x7E, 0x42, 0x7D, 0x43, 0x7E, 0x7D, 0x44]

This exactly matches the original payload!

Let's develop a complete, production-quality implementation of byte stuffing that combines frame construction, CRC calculation, and escape processing. This implementation reflects real-world requirements including buffer management, error handling, and efficiency optimization.

A critical aspect of any framing mechanism is its efficiency—how much overhead does it add to the original data? Let's analyze byte stuffing mathematically and empirically.

Theoretical Analysis:

For a payload of N bytes, the stuffed length L depends on how many bytes require escaping:

L = N + E

where:
  N = original payload length
  E = number of bytes requiring escaping

Each escaped byte becomes two bytes (escape byte + XOR'd byte), adding exactly one byte of overhead per escaped byte.

Probability Model:

Assuming uniformly random data (each byte value equally likely):

• Probability of FLAG (0x7E): P(FLAG) = 1/256 ≈ 0.39%
• Probability of ESCAPE (0x7D): P(ESCAPE) = 1/256 ≈ 0.39%
• With minimal ACCM: P(escape) = 2/256 ≈ 0.78%
• With full ACCM: P(escape) = 34/256 ≈ 13.28%

Expected Overhead:

E[overhead] = N × P(escape)

Minimal ACCM: E[L] = N × (1 + 2/256) ≈ 1.008N
Full ACCM:    E[L] = N × (1 + 34/256) ≈ 1.133N

Worst-Case Analysis:

The absolute worst case occurs when every byte in the payload requires escaping:

Payload: [0x7E, 0x7E, 0x7E, ...] (N bytes)
Stuffed: [0x7D, 0x5E, 0x7D, 0x5E, ...] (2N bytes)

This represents 100% overhead. However, this case is extremely rare in practice:

• For random data, probability of all N bytes needing escape: (2/256)^N
• For N=100: essentially zero

Best-Case Analysis:

The best case occurs when no bytes require escaping:

Payload: [0x41, 0x42, 0x43, ...] (N bytes, no 0x7E/0x7D)
Stuffed: [0x41, 0x42, 0x43, ...] (N bytes, unchanged)

This is common for ASCII text and carefully constructed data.

Comparison with Fixed Overhead:

Byte stuffing has variable overhead that depends on data content. This contrasts with fixed overhead approaches like character count framing, which always add the same number of header bytes regardless of content.

While this module focuses on byte stuffing, it's essential to understand its relationship to bit stuffing, the alternative approach used in bit-oriented protocols like HDLC.

Bit Stuffing Overview:

In bit stuffing (used by HDLC and its derivatives), the flag pattern is 01111110 (same as 0x7E, but processed at the bit level). The transparency rule is:

After any sequence of five consecutive 1-bits in the data, insert a 0-bit.

The receiver performs the reverse: after seeing five consecutive 1-bits followed by a 0, it removes that 0.

Example:

Original:  01111110 11111 01111110
           FLAG     data  FLAG
                          
Bit-stuffed data: 011111010 → 0111110 10
                         ↑ inserted bit

Mathematical Comparison:

For bit stuffing:

• Worst case: Every 5 bits followed by a 0 → 6/5 = 1.2x = 20% overhead
• Average (random data): ~1 stuffed bit per 32 data bits → ~1.8% overhead

For byte stuffing (minimal ACCM):

• Worst case: Every byte escaped → 2x = 100% overhead
• Average (random data): ~2/256 bytes escaped → ~0.8% overhead

Why Use Byte Stuffing?

Despite bit stuffing's lower average overhead, byte stuffing remains prevalent because:

1. Hardware Simplicity: Standard UART chips output bytes, not bits. Bit stuffing requires additional hardware or software bit manipulation.

2. Debugging: Byte-oriented frames are easier to inspect in hex dumps and protocol analyzers.

3. Asynchronous Compatibility: Byte stuffing works naturally with asynchronous serial communication.

4. Legacy Systems: Enormous installed base of byte-oriented equipment.

When to Use Each:

• Byte stuffing: Serial lines, modems, tunneling protocols, software implementations
• Bit stuffing: High-speed synchronous links, dedicated hardware, WAN protocols

Production implementations of byte stuffing must be highly optimized, especially for high-speed links or resource-constrained embedded systems. Let's explore key optimization strategies.

1. Lookup Table for Escape Decisions:

Rather than computing "should this byte be escaped?" with bit operations, pre-compute a 256-entry lookup table:

# Initialization (once)
escape_table = [False] * 256
escape_table[0x7E] = True
escape_table[0x7D] = True
for i in range(32):  # ACCM bits
    if accm & (1 << i):
        escape_table[i] = True

# Usage (per byte) - single array lookup
if escape_table[byte]:
    # Escape needed

This trades 256 bytes of memory for O(1) escape decisions.

2. SIMD Processing:

Modern CPUs can check multiple bytes simultaneously using SIMD instructions:

// Process 16 bytes at once with SSE
__m128i data = _mm_loadu_si128(input);
__m128i flag_match = _mm_cmpeq_epi8(data, _mm_set1_epi8(0x7E));
__m128i esc_match = _mm_cmpeq_epi8(data, _mm_set1_epi8(0x7D));
__m128i needs_escape = _mm_or_si128(flag_match, esc_match);
int mask = _mm_movemask_epi8(needs_escape);

if (mask == 0) {
    // Fast path: no escaping needed, copy all 16 bytes
}

3. In-Place Unstuffing:

Since unstuffing always shrinks (or maintains) data length, it can be done in-place:

def unstuff_in_place(buffer):
    read_idx = 0
    write_idx = 0
    
    while read_idx < len(buffer):
        if buffer[read_idx] == ESCAPE:
            read_idx += 1
            buffer[write_idx] = buffer[read_idx] ^ 0x20
        else:
            buffer[write_idx] = buffer[read_idx]
        read_idx += 1
        write_idx += 1
    
    return write_idx  # New length

4. Scatter-Gather I/O:

Instead of copying data to insert escape bytes, use scatter-gather to describe the output as segments:

# Instead of copying everything:
output = flag + stuffed_header + stuffed_payload + stuffed_fcs + flag

# Use scatter-gather:
iov = [
    (flag_buffer, 1),
    (stuffed_header, len_header),
    (stuffed_payload, len_payload),
    (stuffed_fcs, len_fcs),
    (flag_buffer, 1),
]
writev(socket, iov)  # Single system call

5. Branch Prediction Hints:

Most bytes don't need escaping. Hint this to the compiler:

if (__builtin_expect(escape_table[byte], 0)) {
    // Unlikely: escape needed
    *output++ = ESCAPE;
    *output++ = byte ^ 0x20;
} else {
    // Likely: pass through
    *output++ = byte;
}

6. Pre-calculated Frame Length:

When buffer allocation needs to be exact, scan once for escape count:

def calculate_stuffed_length(data):
    return len(data) + sum(1 for b in data if escape_table[b])

# Allocate exact buffer size
output = bytearray(2 + calculate_stuffed_length(payload))

This avoids reallocation during stuffing at the cost of an extra scan.

Robust byte stuffing implementations must handle numerous error conditions and edge cases. Let's examine the most important ones.

1. Incomplete Escape Sequence:

A frame ends with an escape byte (0x7D) followed immediately by the end flag:

[0x7E] ... [0x7D] [0x7E]  ← Where is the escaped byte?

This is a protocol error. The receiver should:

• Discard the incomplete frame
• Log the error for diagnostics
• Continue processing (the closing flag may be the start of a valid frame)

2. Invalid Escaped Byte:

In strict PPP, only certain escape sequences are valid. What if we receive:

[0x7D] [0x20]  ← XOR 0x20 = 0x00 (valid)
[0x7D] [0x40]  ← XOR 0x20 = 0x60 (unexpected original)

The second case produces 0x60, which is not normally escaped. Options:

• Accept it (lenient): Decode as 0x60
• Reject it (strict): Discard frame as malformed

Most implementations are lenient for interoperability.

3. Maximum Frame Size Exceeded:

If no flag arrives within MAX_FRAME_SIZE bytes:

[0x7E] [data...data...data...]  ← Buffer full, still no flag!

The receiver must:

• Discard accumulated data
• Return to HUNT state
• Wait for next flag to resynchronize

4. CRC Errors After Unstuffing:

The CRC is calculated on unstuffed data. If CRC fails:

Unstuffed frame: [addr] [ctrl] [proto] [payload] [FCS]
CRC check: FAIL

This could mean:

• Bit errors during transmission
• Stuffing/unstuffing bug
• Missed synchronization (interpreting garbage as frame)

The receiver should discard the frame, log the error, and increment an error counter.

5. Abort Sequence:

Some protocols define an "abort sequence" to forcibly terminate a frame without completing it. In HDLC/PPP:

[0x7E] [partial frame...] [0x7E 0x7E 0x7E...] [0x7E] [new frame]

Multiple consecutive flags are treated as inter-frame fill, effectively aborting any partial frame.

Defensive Implementation:

class RobustUnstuffer:
    def __init__(self):
        self.error_counts = {
            'incomplete_escape': 0,
            'buffer_overflow': 0,
            'crc_error': 0,
            'frame_too_short': 0,
        }
    
    def log_error(self, error_type, details):
        self.error_counts[error_type] += 1
        if self.error_counts[error_type] <= 10:  # Limit log spam
            logger.warning(f"Frame error: {error_type} - {details}")