LZ4 Compression, in depth: tokens and length bytes, a verified block decoder and encoder, overlapping copies, hostile input and the frame format

Sequences: token, literals, offset, match

A block is a series of sequences. Each sequence is a run of literal bytes followed by a back-reference that copies earlier output. The layout:

The minimum match, minmatch, is 4, so a low nibble of 0 means 4 bytes. A literal length of 15 is written as nibble 15 plus a zero byte. A length of 270 is 15 + 255 + 0, so it costs two extension bytes. The format has no length limit, which is why the specification asks decoders to reject lengths that would overflow their registers. It also notes that the best achievable ratio is about 250 to 1.

Two consequences explain LZ4's speed. Everything is byte-aligned, so the decoder never shifts bits. And a sequence needs only one branch for the common short case: lengths under 15 fit in the token, so most sequences are a token, a few literals and an offset.

End-of-block rules

The specification adds three end-of-block rules. Hand-written encoders that ignore them produce blocks that some decoders reject:

1. The last sequence contains only literals: the block ends right after them, with no offset.
2. The last 5 bytes of input are always literals.
3. The last match must start at least 12 bytes before the end of the block. So blocks under 12 bytes cannot be compressed, and independent blocks under 13 bytes cannot either, because they must start with at least one literal.

These rules exist for the sake of fast decoders. A decoder that knows a match can never touch the last bytes of the buffer can copy in 8- or 16-byte chunks that overrun the logical end without leaving the buffer. Even empty input has a valid encoding: the single byte 00, a final token with no literals.

A safe decoder

Here is a complete safe block decoder. It is written for clarity, not speed, and checks every bound the specification's safe-decoding notes call for:

def decode_block(src, max_out):
    out = bytearray(); i = 0; n = len(src)
    while True:
        if i >= n: raise ValueError("truncated: missing token")
        token = src[i]; i += 1
        lit = token >> 4
        if lit == 15:
            while True:
                if i >= n: raise ValueError("truncated literal length")
                b = src[i]; i += 1; lit += b
                if b != 255: break
        if i + lit > n or len(out) + lit > max_out:
            raise ValueError("literal run overflows input or output")
        out += src[i:i + lit]; i += lit
        if i == n:
            return bytes(out)                 # last sequence: literals only
        if i + 2 > n: raise ValueError("truncated offset")
        off = src[i] | (src[i + 1] << 8); i += 2
        if off == 0 or off > len(out):
            raise ValueError(f"bad offset {off} at output {len(out)}")
        mlen = token & 15
        if mlen == 15:
            while True:
                if i >= n: raise ValueError("truncated match length")
                b = src[i]; i += 1; mlen += b
                if b != 255: break
        mlen += 4                             # minmatch
        if len(out) + mlen > max_out: raise ValueError("match overflows output")
        start = len(out) - off
        for k in range(mlen):                 # byte-wise: source may overlap destination
            out.append(out[start + k])

The byte-wise loop at the end matters. When the offset is smaller than the match length, the match reads bytes it is writing in the same copy. Offset 1 with length 100 repeats one byte 100 times, which is run-length encoding for free. A memmove or a slice copy of out[start:start + mlen] reads the source before it is fully written and produces wrong output. Production decoders copy in wide chunks when the offset is at least 8 and fall back to pattern-replication tricks for short offsets.

Worked example: 29 bytes into 13

Take the 29-byte input abcabcabcabcabcabcabcabc-end!. The encoder below produces 13 bytes, identical to python-lz4's lz4.block.compress(data, store_size=False):

3f 61 62 63 03 00 02 50 2d 65 6e 64 21

1. 3f: token. High nibble 3 means 3 literals. Low nibble 15 means the match length continues in extension bytes after the offset.
2. 61 62 63: the literals abc.
3. 03 00: offset 3, little-endian.
4. 02: match extension. Length = 15 + 2 + 4 = 21. Copying 21 bytes from 3 back overlaps itself and produces abc seven more times. Output is now 24 bytes.
5. 50: final token, 5 literals, no match.
6. 2d 65 6e 64 21: -end!. Input is exhausted, so the block ends at 29 bytes.

Here the match stops at - anyway. To see the end-of-block rule bite, encode abc repeated 10 times: the output is 3f 61 62 63 03 00 03 50 62 63 61 62 63, a 22-byte match and then 5 literals, although the pattern runs to the end. The 300-input round trip behind these figures mixed random bytes, two-symbol text and repeated HTTP lines. Our encoder's output decoded with the reference library, the reference's output decoded with ours, and everything round-tripped.

The compressor and LZ4 HC

The reference fast compressor is a greedy single-pass matcher with one hash table of earlier positions, sized by LZ4_MEMORY_USAGE (default 14, meaning 16 KB). The hash multiplies the next bytes (four, or five on 64-bit builds for larger inputs) by a large odd constant and keeps the top bits. Each position looks up one candidate and overwrites it, with no chains and no second chance:

def encode_block(data, hash_log=12):
    n = len(data); out = bytearray(); table = [-1] * (1 << hash_log)
    h = lambda p: ((int.from_bytes(data[p:p+4], "little") * 2654435761) & 0xFFFFFFFF) >> (32 - hash_log)
    anchor = p = 0
    while p < n - 12:                         # last match starts >= 12 bytes before end
        hv = h(p); cand = table[hv]; table[hv] = p
        if cand >= 0 and p - cand <= 65535 and data[cand:cand+4] == data[p:p+4]:
            m = 4
            while p + m < n - 5 and data[cand + m] == data[p + m]:
                m += 1                        # last 5 bytes stay literal
            emit_sequence(out, data[anchor:p], offset=p - cand, match_len=m)
            p += m; anchor = p
        else:
            p += 1
    emit_last_literals(out, data[anchor:])  # helpers write token + length bytes per the table
    return bytes(out)

The real implementation adds an acceleration step: after repeated misses it skips ahead faster, so incompressible regions are crossed quickly. LZ4_compress_fast exposes this as an acceleration argument, trading ratio for speed. LZ4 HC keeps the same output format but searches hash chains. Its levels run from 2 to 12 (default 9), and levels 10 and above use an optimal parser. HC compresses far more slowly, but the decoder is unchanged and decodes HC output at full speed, which suits write-once, read-many data.

Hostile input

A decoder is an attack surface: it takes lengths and offsets from the input and turns them into memory copies. The checks above rejected these hand-crafted blocks:

Offset 0 deserves its own note. The specification warns that a naive decoder leaves the destination unchanged, which can disclose whatever was in an uninitialized buffer, and that the reference decoder zero-fills the match instead. In C, use LZ4_decompress_safe(src, dst, compressedSize, dstCapacity). The older LZ4_decompress_fast is obsolete since v1.9.0 because it never learns the input size and is not protected against malformed input. Always pass a max_out derived from your own limits, never from a size field in the untrusted data, or a 4-byte header can request a 4 GB allocation. Fuzz any decoder you own with a sanitizer build.

The frame format

The block format carries no sizes or checksums. The specification calls those out-of-band. The frame format adds them. Here is python-lz4's frame for hello hello hello hello with a content checksum:

04 22 4d 18                 magic 0x184D2204, little-endian
6c                          FLG: version 01, blocks independent, content size, content checksum
40                          BD: block max size code 4 = 64 KB
17 00 00 00 00 00 00 00     content size 23
07                          HC: (xxh32(descriptor) >> 8) & 0xFF
0f 00 00 00                 block size 15, high bit clear = compressed
68 68 65 6c 6c 6f 20 06 00 50 68 65 6c 6c 6f
00 00 00 00                 EndMark
f2 6b 94 0b                 xxHash32 of the original content

The block inside decodes just like the worked example: 6 literals hello , offset 6, match 8 + 4 = 12, then 5 final literals. The block-size word's high bit marks a block stored raw, which is how incompressible data avoids expansion inside a frame. The BD codes 4 to 7 select 64 KB, 256 KB, 1 MB or 4 MB blocks. The FLG byte can also enable per-block checksums, a dictionary ID, and dependent blocks that may reference the previous 64 KB. There is a legacy frame with magic 0x184C2102, and skippable frames use magics 0x184D2A50 to 0x184D2A5F.

Operational guidance

• Agree on the container. Raw blocks, the frame format, the legacy frame and framework-specific framings such as Hadoop's codec are mutually unreadable. Most "LZ4 is corrupt" incidents are a framing mismatch. Check the first four bytes.
• Budget for expansion. Incompressible input grows. A random 64 KB buffer came out at 65,794 bytes as a raw block. Size output buffers with LZ4_compressBound (n + n/255 + 16).
• Small payloads compress poorly. A 200-byte message has little to match against. Batch records, or prime the window with a dictionary through the dictionary API.
• Pick the block size for random access. Storage engines compress fixed chunks so a point read decodes one chunk. Larger chunks give a better ratio and slower point reads. See the HFile format article for one engine's version of this trade.
• Turn on content checksums for data at rest. The decoder's bounds checks catch malformed structure, not flipped literal bits.
• Measure on your data. Throughput depends on the CPU and on the data. Benchmark with lz4 -b on a sample before you quote a figure.

Failure modes

• Overlapping copy implemented with memmove: run-length data decodes wrongly while ordinary text still round-trips, so tests pass.
• Encoder ignoring end-of-block rules: its own decoder accepts the output and a strict third-party decoder rejects it.
• Trusting embedded sizes: python-lz4's lz4.block.compress prepends a 4-byte size by default (1d 00 00 00 for 29 bytes). Feeding that to a raw decoder fails, and allocating from it unchecked invites memory exhaustion.
• Dependent blocks decoded out of order: linked-block frames need the previous 64 KB of output, so parallel or seek-based readers must use independent blocks.
• Header checksum computed over the wrong bytes: early Kafka clients computed the frame header checksum incorrectly, and fixing that interop took a dedicated proposal (KIP-57).

Trade-offs

LZ4 gives up ratio for speed. Next to Zstandard, which adds Huffman and FSE entropy stages and a much larger window, LZ4 compresses less. It wins where decode CPU per byte is the bottleneck: page caches, compressed swap, hot storage blocks and inter-service hops on fast networks. On log data the gap narrows, because repetition, not symbol statistics, carries most of the redundancy. In our run, 71,000 bytes of identical log lines shrank to 360 bytes with the fast and HC-12 modes alike. For why entropy coding pays off elsewhere, see the entropy coding overview. For a column-format view of codec choice, see the Hive compression article.

What to do next

1. Hex-dump one LZ4 payload from your system and identify the container from the first four bytes.
2. Run the decoder above against your library on a sample of production data, including empty and short inputs, and keep it as an interop test.
3. Audit every decode call site: safe API, output cap from your own limits, checksum verified.
4. Benchmark fast, HC 9 and zstd level 1 to 3 on a representative sample with the CLI tools, and record ratio and decode cost.
5. If payloads are small, test dictionary compression before you change codecs.