Snappy Compression, in depth: the varint preamble and four tag types, the reference compressor's skip heuristic, the framing format with masked CRC-32C, and a hardened decoder

The raw format: preamble, literals and copies

A raw Snappy block starts with a preamble: the uncompressed length as a little-endian base-128 varint, at most 2^32 - 1 and so at most five bytes. Each byte carries 7 data bits and sets the high bit if another byte follows, so 64 is 40 and 2,097,150 is FE FF 7F.

After the preamble come elements, each starting with a tag byte whose low two bits give the type. Literals copy bytes from the input. Copies reference bytes already produced: an offset back from the current output position and a length. As in every LZ77 format, the length may exceed the offset, which turns a copy into run-length encoding: "xababab" is the literal "xab" followed by a copy with offset 2 and length 4.

Three details from the format description matter. First, a literal of up to 60 bytes stores len-1 in the tag. Longer literals put 60, 61, 62 or 63 in the tag's upper six bits to say that 1, 2, 3 or 4 little-endian bytes of len-1 follow. Second, the 1-byte-offset copy packs an 11-bit offset (0-2047) and a 4-11 length into two bytes total, which is the common case for short, nearby repeats. Third, an offset of zero can be encoded but is illegal, and so is an offset reaching back before the start of the output. A decoder must reject both. There is no end marker: the stream ends when the input ends, and the produced length must equal the preamble.

How the reference compressor finds matches

The format says nothing about how to find matches, so compressors are free to differ. The reference C++ compressor in snappy.cc makes these choices:

• Fragments of 64 KiB. Input is cut into fragments of at most kBlockSize = 65,536 bytes, compressed independently, so no copy crosses a fragment boundary and 2-byte offsets always suffice. The 2011 format text still says 32 kB. Decoders must not rely on either figure, and must accept 4-byte offsets.
• A small hash table. Four input bytes are hashed by multiplication to index a table of 16-bit positions, at most 2^15 entries, sized to the fragment. Each slot holds only the most recent position, so there are no hash chains and no search: one probe, one 4-byte compare.
• Greedy matching. On a hit, the match is extended as far as it goes and emitted immediately. There is no lazy evaluation and no optimal parsing.
• Skip heuristic. A skip counter starts at 32, and each probe advances by skip >> 5 bytes. After 32 misses the compressor checks every second byte, then every third, and so on, resetting on the next match. The source comment calls this a small loss on compressible data and a huge win on incompressible data such as JPEG, because the compressor quickly stops looking.
• Copy splitting. A copy element holds at most 64 bytes, so long matches become several elements: chunks of 64, with a 60 inserted when needed so that the remainder never drops below the minimum of 4 that a 1-byte-offset copy can encode.

Every one of these choices gives up ratio for speed, and together they are the reason Snappy sits where it does on the ratio-versus-speed curve.

A hardened decoder

The decoder is the half that faces untrusted input, so it has to be strict. Every read is bounds-checked, every copy offset is validated, and output can never exceed the declared length. The declared length itself is capped by the caller, so a 5-byte preamble cannot make you allocate 4 GiB.

class SnappyError(ValueError):
    pass

def read_varint(buf, pos):
    result = shift = 0
    for _ in range(5):
        if pos >= len(buf):
            raise SnappyError("truncated preamble")
        b = buf[pos]; pos += 1
        result |= (b & 0x7F) << shift
        if b < 0x80:
            if result > 0xFFFFFFFF:
                raise SnappyError("length exceeds 2^32-1")
            return result, pos
        shift += 7
    raise SnappyError("varint longer than 5 bytes")

def decompress(buf, max_out=1 << 30):
    n, pos = read_varint(buf, 0)
    if n > max_out:
        raise SnappyError("declared length over limit")
    out = bytearray()
    while pos < len(buf):
        tag = buf[pos]; pos += 1
        kind = tag & 3
        if kind == 0:                                   # literal
            ln = tag >> 2
            if ln >= 60:
                nb = ln - 59
                if pos + nb > len(buf):
                    raise SnappyError("truncated literal length")
                ln = int.from_bytes(buf[pos:pos + nb], "little"); pos += nb
            ln += 1
            if pos + ln > len(buf) or len(out) + ln > n:
                raise SnappyError("literal overruns input or output")
            out += buf[pos:pos + ln]; pos += ln
            continue
        if kind == 1:                                   # copy, 1-byte offset
            if pos + 1 > len(buf):
                raise SnappyError("truncated copy")
            ln = 4 + ((tag >> 2) & 7)
            off = ((tag >> 5) << 8) | buf[pos]; pos += 1
        else:                                           # copy, 2- or 4-byte offset
            nb = 2 if kind == 2 else 4
            if pos + nb > len(buf):
                raise SnappyError("truncated copy")
            ln = (tag >> 2) + 1
            off = int.from_bytes(buf[pos:pos + nb], "little"); pos += nb
        if off == 0 or off > len(out):
            raise SnappyError("copy offset out of range")
        if len(out) + ln > n:
            raise SnappyError("copy overruns declared length")
        start = len(out) - off
        for i in range(ln):                             # byte-wise: overlap is legal
            out.append(out[start + i])
    if len(out) != n:
        raise SnappyError("output shorter than declared length")
    return bytes(out)

The byte-at-a-time copy loop is the correct semantics for overlapping copies. Fast C decoders replace it with 8- or 16-byte unaligned copies, which is why they reserve slack at the end of the output buffer. A Python out[start:start+ln] slice would be wrong whenever offset is less than length. We fed this decoder 20,000 random byte strings and it never raised anything but SnappyError. Hand-built streams for all three copy types decode "xab" plus a copy of offset 2, length 4 to "xababab".

Worked example

Worked example. Compress the 15 bytes "abcabcabcabcabc" with a greedy encoder. The preamble is 0F (15). The first three bytes have no earlier match, so they become a literal: tag 08 (len-1 = 2 in the upper six bits, type 00) followed by 61 62 63. At position 3, "abca" matches position 0. Extending the match runs to the end of the input, giving length 12 and offset 3. Twelve is too long for a 1-byte-offset copy (maximum 11), so it becomes a 2-byte-offset copy: tag = 2 | (11 << 2) = 2E, then offset 03 00.

The whole block is 0F 08 61 62 63 2E 03 00, 8 bytes for 15. Decoding replays it: emit "abc", then copy 12 bytes starting 3 back. Each copied byte becomes available as a source three bytes later, which regenerates the run. On a more realistic input, three repeats of a 47-byte HTTP request line and Host header, our encoder produced 56 bytes from 141: a 47-byte literal plus two 2-byte-offset copies, since a 94-byte match must be split into 64- and 30-byte elements.

def emit_copy(out, off, ln):
    while ln > 0:
        if 4 <= ln < 12 and off < 2048:                 # 2-byte element
            out.append(1 | ((ln - 4) << 2) | ((off >> 8) << 5))
            out.append(off & 0xFF)
            return
        step = 64 if ln >= 68 else (60 if ln > 64 else ln)
        out.append(2 | ((step - 1) << 2))               # 3-byte element
        out += off.to_bytes(2, "little")
        ln -= step

The framing format and masked CRC-32C

Raw Snappy has no checksum and must be held whole in memory, so a separate, optional framing format handles streams and files (extension .sz). A framed stream is a sequence of chunks. Each chunk has a 1-byte type, a 3-byte little-endian length and then data. It must begin with the stream identifier chunk, type 0xff, whose six bytes spell sNaPpY. Compressed chunks (0x00) and uncompressed chunks (0x01) each start with a 4-byte masked CRC-32C of the uncompressed data, and each may hold at most 65,536 uncompressed bytes. That cap lets readers use fixed buffers.

The mask is rotate right by 15 and add 0xa282ead8, the same as Hadoop's. It exists because checksumming data that already contains its own CRC behaves poorly. Unknown types 0x02-0x7f are fatal, 0x80-0xfd are skipped, and 0xfe is padding. The specification warns that there is no metadata checksum, so it cannot detect every form of truncation.

CRC_TABLE = []
for b in range(256):
    c = b
    for _ in range(8):
        c = (c >> 1) ^ 0x82F63B78 if c & 1 else c >> 1   # Castagnoli, reflected
    CRC_TABLE.append(c)

def crc32c(data):
    c = 0xFFFFFFFF
    for b in data:
        c = CRC_TABLE[(c ^ b) & 0xFF] ^ (c >> 8)
    return c ^ 0xFFFFFFFF                                 # crc32c(b"123456789") == 0xE3069283

def masked_crc(data):
    c = crc32c(data)
    return (((c >> 15) | (c << 17)) + 0xA282EAD8) & 0xFFFFFFFF

Operational guidance

• Know which container you have. Raw blocks, the official framing format and the older Hadoop block format are mutually unreadable. The usual symptom of a mismatch is a "corrupt input" error on a perfectly good file.
• Use it where CPU is the bottleneck. Snappy fits hot paths such as RPC payloads, in-memory caches and LSM-tree blocks that are read constantly. Cold storage and network-bound transfers usually do better with zstd.
• Do not compress twice. JPEG, video, encrypted bytes and already-compressed columns gain nothing. The skip heuristic makes the attempt cheap, but storing such data raw is cheaper still.
• Bound everything on decode. Cap the preamble length against your buffer limit before allocating, and fuzz your binding with truncated and random inputs.
• Check before you trust. Raw blocks carry no checksum, so if storage or the network can corrupt them, wrap them in the framing format or in your own CRC.

Failure modes

• Memory blow-up from the preamble. A decoder that allocates the declared length up front can be pushed to allocate gigabytes by a few bytes of input.
• Silent corruption. A flipped bit in a literal decodes to wrong data with no error, and a flipped bit in an offset may only show as a length mismatch. Without CRCs you find out downstream.
• Overlapping-copy bugs. Using memcpy or a slice for copies where offset is less than length produces garbage on runs, and only on runs, so the bug hides until real data contains long repeats.
• Expansion on random data. Incompressible input grows slightly, by the preamble plus literal headers. The library's MaxCompressedLength bound (32 + n + n/6) is what you size output buffers by.
• Framing assumptions. Concatenated framed files are valid, since repeated stream identifiers are ignored. Tools that stop at the second identifier truncate data silently.

Trade-offs

Snappy, LZ4 and zstd are the usual shortlist. LZ4 makes similar trade-offs and generally matches or beats Snappy on speed in public benchmarks, with a high-compression mode for write-once data. zstd adds entropy coding with Huffman and FSE, giving much better ratios at tunable speed and dictionaries for small messages. Snappy's remaining advantages are a very simple, stable format, mature bindings and its established place in existing file formats. Pick it for compatibility with Parquet, ORC, Kafka or LevelDB-style stores, or where its simplicity matters. For new systems you control, benchmark LZ4 and zstd at a low level on your own data before deciding.

What to do next

1. Run the decoder above against hand-built streams for every tag type, then against your library's output for real files, to confirm you understand the format.
2. Fuzz your production Snappy binding with truncated, random and oversized-preamble inputs under a memory limit.
3. Audit where you store raw blocks without a checksum, and add the framing format or a CRC.
4. Benchmark Snappy, LZ4 and zstd level 1 to 3 on a sample of your real data. Record ratio, compress MB/s and decompress MB/s per core.
5. Read the LZ78 article for the dictionary-based branch of the family that Snappy does not use.