sylz format

sylz format

Format v2, frozen at tag v0.2.2 (commit 24638678e90691faad11ce1cdbcac7fa1ea2f427); v0.2.0–0.2.1 wrote v1. The token table is SYLZ_TOKENS in src/sylz.pas at v0.2.2.

Frozen means: zpaq-std decodes this format with its own ZPAQL decoder, so any later change to the block format is a new format (v3) under a new codec name, and v2 stays as it is here. One block per call: the caller stores the decoded size (the CLI's container does). Little-endian throughout.

block    := ctrlLen:u32  control[ctrlLen]  literals[...]
control  := sequence*
sequence := token  offset:u16  [literal-length-ext]  [match-length-ext]
token    := index into SYLZ_TOKENS (src/sylz.pas):
              0..209    exact (literals, match) pair: literals <= 15, match <= 32
              210..225  literals = token - 210, match = 4 + ext
              226..254  literals = ext,         match = 4 + (token - 226)
              255       literals = ext,         match = 4 + ext
offset   := distance - 1   (distances 1..65536)
ext      := 255-run bytes: each byte adds itself, 255 means another
            byte follows; the literal extension comes first

Each sequence takes its literals from the front of the literal stream, then copies its match. Whatever is left in the literal stream after the last sequence is the end of the block. A block with no matches is a header with ctrlLen = 0 followed by the data.

Format v3 (frozen at v0.2.14)

v2 plus entropy-coded literals. A v2 block is a valid v3 block; a v3 block sets bit 31 of the first u32, which a v2-only decoder (zpaq-std's ZPAQSYLZ included) rejects as an impossible control length instead of misreading it. syc writes it with -ec. All integers little-endian.

block       := hdr:u32  control[ctrlLen]  litsection
hdr         := ctrlLen (bits 0-30) | bit 31: literals entropy-coded
litsection  := literals[...]                    bit 31 clear: as in v2
             | litCount:u32  chunk*             bit 31 set
chunk       := 0x00  raw[c]
             | 0x02  lengths[128]  size1:u16 size2:u16 size3:u16 size4:u16  stream1 stream2 stream3 stream4
             | 0x01  lengths[128]  size1:u16 size2:u16 size3:u16  stream1 stream2 stream3 stream4
                     (mode 1: written by syc 0.2.4-0.2.13; read, never written)

The control stream is v2's, unchanged: the same tokens, offsets and extensions. Only where the literals come from differs.

The literal section (bit 31 set): litCount (1 .. the block's decoded size) literals, in chunks of 65536 each, the last one c = litCount - 65536k (1 .. 65536). The chunks must use the rest of the block exactly. Decoding: the chunks into a literal buffer of litCount bytes, then v2's sequence decoder over the control stream and that buffer (its tail literals included), so it must consume exactly litCount literals.

A raw chunk (0x00) is its c bytes.

A Huffman chunk (0x02, or 0x01) needs c >= 256 (decoders reject smaller ones: the four-run split degenerates, c = 5 gives runs of 2, 2, 2 and -1):

• lengths: symbol 2k's code length in the low nibble of byte k, 2k+1's in the high nibble; 0 = the symbol does not occur, else 1 .. 11. The lengths must form a complete prefix code (Σ 2^(11 - len) = 2^11) over at least two symbols; anything else is rejected.
• Canonical codes, as deflate's: next[1] = 0, next[b + 1] = (next[b] + count[b]) << 1 for b = 1 .. 11; then symbols in increasing order each take code = next[len]++. A code is written LSB first: its bits reversed (code bit len-1 first), so that the first bit of a code is the lowest unused bit of the stream.
• Four streams: the chunk's c symbols split into runs of q = (c + 3) div 4 (stream 1: symbols 0 .. q-1, stream 2: q .. 2q-1, stream 3: 2q .. 3q-1, stream 4 the remaining c - 3q, possibly fewer than q). Each run is coded into its own stream: bits fill each byte from bit 0 up, the last byte padded with zero bits; the next stream starts at the next byte.
• Sizes (mode 2): size1 .. size4 are the streams' byte lengths; the chunk is exactly 1 + 128 + 8 + size1 + .. + size4 bytes, and each stream must end inside its own bytes (a decoder may read zeros past a stream's end, but if its codes end past the stream's size the chunk is rejected). Mode 1 has no size4: stream 4 ends where its last code does (rounded up to a byte), which is where the next chunk starts.
• The encoder Huffman-codes a chunk only when that saves at least 4% of it (else raw).

A decoder (what HufDecodeChunk in src/sylzhuf.pas does): build a 2^11-entry table, entry i = (symbol, length) of the code whose reversed bits are the low len bits of i; then for each stream keep a little-endian bit buffer, and per symbol take t[buf & 2047], output its symbol, drop its length from the buffer.

Limits, for a decoder:

• code lengths 1 .. 11 (MAXBITS = 11); a 4-bit length of 12 .. 15 is malformed;
• size1 .. size4: u16 little-endian, so a stream is at most 65535 bytes (a chunk of 65536 literals at 11 bits needs 22528 per stream);
• litCount u32, at most the block's decoded size; chunks of 65536 literals, the last 1 .. 65536;
• the encoder writes mode 2 (never mode 1) and raw chunks; a v3 block whose chunks would not be smaller than the v2 literal stream is written as v2 instead, so a sylzec block may be a plain v2 block: a decoder for it must read both.

Damaged data: a decoder must reject, never loop and never read or write outside the block and the decoded size. Every loop above is bounded by a count known before it starts (sequences by the control stream's length, extensions by the bytes left in it, symbols by the run length, chunks by litCount), so a decoder written this way always ends. Reject: an unknown chunk mode; a Huffman chunk under 256 symbols; lengths over 11, or not a complete code over two or more symbols; a stream whose codes end past its size; sizes past the block; chunks that do not end exactly at the block's end; then everything v2 rejects (sequences past the control stream, literal runs past the literals, matches before the output's start or past its end, tail literals that do not fill the block exactly).

Reference: tools/sylz_ref.py in the repository decodes v2 and v3 blocks straight from this description (an oracle for other decoders; it raises on anything above), and tests/sylzvectors.pas writes test vectors (each case's original and what compress() returns at levels 0 .. 10, in both formats); the release carries them as sylz-vectors.zip.

Stability: frozen at tag v0.2.14. From then on any change is a new format (a new codec name in zpaq-std). Mode 1 stays readable.

Why two streams

In a single interleaved stream (LZ4's layout) the next token sits after the current sequence's literals, so the decoder can't load it before it knows the literal length. With a separate control stream the next token is always 3 bytes on (plus the occasional extension), so consecutive sequences overlap in the CPU. This is the idea misa77's light format is built on.

Why a token table

v1 split the token into 3 bits of literal length (0..6) and 5 of match length (4..34), with an extension when a field was saturated. Profiled with perf, 65% of the decoder's branch misses were on "is this field extended" — 15.5% of level-1 sequences on silesia.tar needed one, and which ones can't be predicted. A branch-free extension was slower: the next token's address then waits on this sequence's loads, while a predicted branch lets the CPU run ahead on ctrl + 3.

So v2 makes extensions rare. The joint distribution of (literals, match) is concentrated, and the 210 most frequent pairs inside the fixed-copy region (literals <= 15, match <= 32, so the decoder copies 16 + 32 bytes with no loop) cover far more sequences than the bit split:

sequences needing no extension	v1 (3/5 bits)	v2 (table)
silesia.tar, level 1	84.5%	90.9%
silesia.tar, level 9	87.7%	91.8%
mixed corpus, level 1	79.0%	87.9%
mixed corpus, level 9	83.0%	89.2%

The mixed corpus is 141 MB of samples of text, documents, executables, fonts, images, audio and more, so the table isn't tuned to Silesia alone; each input weighs the same. bench/sylztable.pas derives the table from sample blocks. Wider regions (literals up to 31, match up to 64) stay within a point and need wider copies.

Result: ratio 44.62 -> 44.18% (silesia -1), decode +5% (silesia -1) to +8.6% (mixed -1), compression speed unchanged.

Other measurements behind the format

From the v1 analysis (bench/sylzstats, silesia.tar):

• Offsets under 16 are 1.6–2.3% of matches: they stay allowed, behind a rarely taken branch.
• Repeat offsets are 2.6–4.6%: with a fixed 3-byte control entry they would save nothing. Left for a later format with entropy coding.
• 11–21% of offsets are in the top 32 KiB of the window, so the high levels would gain from a larger window: a later "heavy" format.

Decoding safely

The decoder never reads or writes out of bounds on corrupt input and returns -1. It runs a fast loop with unchecked wide copies while every stream is at least a margin away from its end (control 3, literals 16, output 64 bytes), and an exact, fully checked loop for the tail and for any sequence that doesn't fit the margins.

History

• v2: token table (this page).
• v1: same layout, token split 3/5 bits.
• v0 was byte-compatible with the LZ4 block format: a calibration step, so the Pascal decoder could be timed against the C one on identical streams (it ran at 72–76% of C). It is in git history before v1.