Squinch implementation

This document describes the current C encoder and decoder implementation. The byte-format contract is in Format.md.

Encoder

The one-shot encoder allocates a history ring with the configured window size and a matcher. The streaming compressor additionally allocates a configurable look-ahead ring. Caller input fills the look-ahead ring, and encoding reads only from that ring. If fewer than three bytes are available or a detected copy or RLE operation reaches the available end, the compressor refills the ring before committing the operation. It resumes when more input is available, the ring is full, or the caller signals the end of data.

The matcher hashes each three-byte sequence with a fixed 65536-entry hash table. Each hash-table entry points to the newest matching position, and a circular previous-position array forms a bounded hash chain. The encoder starts from the newest candidate and examines no more than matchLimit candidates. Candidates older than the history ring are ignored.

For every input position, the encoder first detects a repeated-byte run from the most recently output byte. Otherwise it searches matching candidates and retains the longest eligible copy for every instruction-size class. It compares each candidate's encoded size with the cost of its literal representation, selects the greatest immediate saving, and uses instruction size and then copy length as tie-breakers. RLE is preferred when applicable.

The encoder appends every literal and copied byte to the history ring and matcher immediately. Each copied byte can therefore become the source of a later byte in the same copy operation, allowing a copy to exceed the current history length or window size. RLE changes only the last-output-byte state because RLE output is not history.

A copy is emitted only when it saves bytes over its literal representation. A copy form may be longer than the bytes it represents, but can still save space when those literal bytes require escaping. The byte values and copy semantics are specified in Format.md.

Decoder

The one-shot decoder parses the complete header, allocates a history ring, and interprets the remaining bytes until input ends. The streaming decoder collects the 16-byte header incrementally, verifies it before allocating deferred history storage, then alternates between instruction parsing and pending output.

Streaming decode keeps at most five instruction parameter bytes. Copies, RLE operations, and a literal blocked by a full caller output buffer become pending output. Later calls may therefore produce output without consuming more input. The decoder retains the source offset while draining a copy and immediately appends each copied byte to the history ring.

The decoder tracks the last output byte separately for RLE. It validates reserved instruction forms, copy lengths, offsets, history availability, the configured maximum window, and incomplete input signaled by a zero-input finish call.

History storage

The decoder implements the format's history window as a ring buffer. Its logical order has the newest byte at the front and the oldest at the back. The ring records the oldest byte as its first element, so a copy offset selects the element at length - offset - 1 from that element. Every encoded copy-offset field stores the copy offset minus 1.

  Back [ | | | | | | | | | | | | | | | | | | | | ] Front
Offset  W . . . . . . . . . . . . . . . . 3 2 1 0

Offset W is windowSize - 1. During a copy, each output byte advances the ring before the next offset read. This is how a copy can continue beyond the initially available history.

Streaming state

The decoder first collects exactly 16 header bytes. It validates the magic, version, window encoding, and zero leading byte of the uncompressed-size field before accepting encoded bytes. Header metadata is unavailable until this state completes.

It then reads an instruction byte, collects its parameters, validates the operation, and produces its output. A zero-input call finishes only when no header bytes, instruction bytes, parameters, or pending output remain. Later zero-input calls drain the terminal state; nonempty input is invalid. The public streaming-call contract is specified in API.md.