SQUISH
| SQUISH | |
|---|---|
| Filename extension | .sqsh |
| Magic number | SQSH followed by 0x0D 0x0A 0x1A 0x0A |
| Developed by | Paige Julianne Sullivan |
| Latest release | 1 (on-disk format) |
| Type of format | Lossless data compression |
| Container for | Files and directory trees |
| Standard | docs/FORMAT.md (self-published) |
| Free format? | Yes |
SQUISH is a lossless data compression format and its reference implementation, a context mixing file compressor written in C. It is distributed as a linkable library (libsquish.so / squish.dll) together with a command-line tool. SQUISH trades speed for compression ratio: on a 315 MB combined standard-corpus benchmark it produces smaller output than zip -9, bzip2 -9, and rar -m5 on 23 of 24 files, and beats xz -9e on 19 of 24, at a cost of roughly 0.6 MB/s throughput and about 150 MB of model memory per active block.[1]
The design rests on a single premise: compression is prediction. If the probability of the next bit can be estimated accurately, an arithmetic coder converts those probabilities into a near-optimal code, a consequence of Shannon's source coding theorem. Accordingly, essentially all of SQUISH's engineering is concentrated in an online-learning predictor that adapts to whatever kind of data it reads.[2]
Overview
[edit]Conventional general-purpose compressors each commit to one structural model of data: zip uses DEFLATE (LZ77 plus Huffman coding), bzip2 uses the Burrows–Wheeler transform, and RAR combines LZ with prediction-by-partial-matching filters. SQUISH instead runs ten specialist statistical models simultaneously and learns, bit by bit, which of them to trust for the data currently being read. As a result it behaves like an LZ compressor on repetitive data, like a high-order PPM compressor on text, and like a table or raster codec on record-structured data, without being told in advance which kind of file it is handling.[2]
Because the decompressor runs the identical predictor in lockstep — making the same predictions and applying the same updates as the encoder — the format needs no stored dictionaries, no code tables, and no block structure describing the model. In the project's phrasing, "the model is the format": the constants and update rules in the source file squish.c are the bitstream specification, and any change to them constitutes a format break.[2][3]
Compression is symmetric in cost: decompression runs the same models as compression and therefore takes approximately the same time, distinguishing SQUISH from asymmetric codecs such as xz, where decompression is far cheaper than compression.[1]
Compression algorithm
[edit]SQUISH codes one bit at a time. For each bit, every model emits a probability that the bit is 1; an online-trained mixer fuses those opinions into a single probability, two refinement stages recalibrate it, and an arithmetic coder emits the corresponding fraction of a bit. The pipeline runs in the order predict, code, update for both encoder and decoder.[3]
Adaptive counters
[edit]Most contexts are represented by a 32-bit adaptive counter holding a 16-bit probability and a 16-bit confidence count, initialized to probability 0.5 with zero confidence. After each bit the probability moves toward the observed outcome by a step of 1/(n + 2), where n is the confidence count, which is then incremented (capped at 255). The counter is therefore highly plastic when a context is fresh and stabilizes as evidence accumulates, giving fast convergence on new contexts and stability on well-established ones.[3]
The ten models
[edit]Eight of the models are hashed context models sharing a table of 222 counters, each indexed by a 64-bit hash function of its context combined with the partial current byte:[3]
- Order-1 through order-6 byte contexts (orders 1, 2, 3, 4, and 6) — predict the next bit from the preceding one to six bytes, the classic finite-context models of PPM.
- Word model — hashes the current run of alphanumeric characters, so text is predicted from the word being spelled rather than raw byte history.
- Record model — two contexts that activate when a dominant repeating row length R is detected: the byte one record above the current position, and a combination of column index with the two bytes above. These capture the two-dimensional regularity of spreadsheets, raster scan lines, and fixed-size database records.
The remaining two models are an order-0 model (256 counters indexed directly by the partial byte) and a match model.[3]
Match model
[edit]The match model hashes the last six bytes into a table of 222 positions to find the most recent identical context, then predicts that history simply repeats from that point, with confidence learned per match-length bucket. This gives SQUISH the long-range repeat power of LZ77 but with an unbounded window covering the whole file, and probabilistically rather than as explicit tokens: a broken match costs a fraction of a bit rather than producing a malformed match token. A bit that contradicts the predicted byte silences the model until the next byte boundary.[2][3]
Record-length detection
[edit]The record model's row length R is detected automatically. A table records the last position of each byte value; recurring distances between equal bytes are tallied as votes, and every 2048 bytes the winning distance is examined. A vote total above 600 sets R to that distance, while a total below 300 clears it, with a hysteresis band between to avoid thrashing. This automatic detection is credited with SQUISH outperforming even RAR's specialized filters on the spreadsheet file kennedy.xls.[2][3]
Logistic mixing
[edit]The models' probabilities are combined by a logistic mixer — a single-layer neural network with 11 inputs — operating in the log-odds ("stretch") domain. It computes a weighted sum of the stretched model outputs and squashes the result back into a probability. One of 1024 weight vectors is selected per bit by context (the previous byte together with the match and record state), and the active vector is trained online by gradient descent on the actual coding loss. Models that are useless for the current data have their weights driven toward zero within a few kilobytes; on text the word model earns a large weight, while on binary records the record model does.[2][3]
APM/SSE refinement
[edit]Two chained adaptive probability map stages (also known as secondary symbol estimation, SSE) refine the mixed probability. Each maps a (context, probability) pair to a corrected probability via interpolation over a small table that is itself updated toward observed outcomes, correcting systematic miscalibration in the mixer's output. The first stage is keyed on the partial byte, the second on the previous byte and partial byte.[3]
Arithmetic coder
[edit]The refined 12-bit probability feeds a carryless binary arithmetic coder over 32-bit registers, coding bits most-significant-first within each byte. The coder never allows the coding interval to collapse. The decoder mirrors the encoder exactly, preloading four bytes and pulling one byte per renormalization step.[3]
File format
[edit]SQUISH has a single on-disk format, the SQUISH archive, identified by the magic bytes SQSH followed by 0x0D 0x0A 0x1A 0x0A. A lone file or memory buffer is stored as a one-member archive (marked with a SINGLE flag); a directory is stored as a many-member archive.[3]
An archive consists of a fixed 64-byte header, a member-data region, and a compressed index. The header records the format version, flags, member and byte counts, the block (chunk) size, and the location of the index. The index is a single compressed block listing every member in pre-order — directories before their contents, siblings sorted by name — so the archive contents depend only on the directory tree and not on filesystem iteration order. Each index entry stores the member type, Unix permission bits, uncompressed size, the offset of its first block, its path, and the compressed length of each of its blocks.[3]
The atom of the format is the coded block, which holds up to one chunk of original data as a one-byte mode field, a payload, and a 32-bit FNV-1a checksum of the block's original bytes. Two modes exist: a context-mixed arithmetic stream, or a stored block containing the original bytes verbatim. Encoders emit a stored block whenever the arithmetic stream would be no smaller, which bounds the output of any block at its input size plus five bytes and guarantees the compressor never expands incompressible data beyond a fixed bound.[3]
Because the index records each member's block layout, a reader can seek straight to any member — or any block within a member — without inflating the rest of the archive, enabling listing and single-file extraction. Extraction rejects absolute paths and paths containing .. components, so an archive can never write outside its target directory (a defense against the Zip Slip class of directory traversal attacks). Each member is limited to just under 4 gibibytes.[3][1]
Parallelism
[edit]The model pipeline is strictly sequential within a block, since each bit's prediction depends on the update from the previous bit. Multi-core operation therefore comes from cutting a member into fixed-size blocks whose models start independently: separate blocks compress and decompress in parallel. This yields near-linear speedup at a cost of roughly 1–2% of compression ratio, because each block's model begins "cold" with no accumulated history. The default single-threaded mode packs each member as one whole-file block, which is ratio-optimal.[2][1]
Results
[edit]SQUISH's published benchmark combines the Silesia corpus, the Canterbury corpus, and enwik8 — 24 files totaling about 315 MB — with every file verified to round-trip exactly. Each rival compressor is run at its strongest documented setting. The totals below are for the ratio-optimal single-block mode of SQUISH.[4]
| Compressor | Total compressed | Ratio |
|---|---|---|
| zip -9 | 104,800,190 | 0.333 |
| bzip2 -9 | 84,058,237 | 0.267 |
| rar -m5 | 80,560,956 | 0.256 |
| xz -9e | 73,780,732 | 0.234 |
| SQUISH | 67,432,463 | 0.214 |
Overall SQUISH compresses the corpus about 8.6% smaller than the best rival on the total, beats zip, bzip2, and rar on 23 of 24 individual files, and beats all four (including xz -9e) on 19 of 24.[4]
Its largest per-file margins over the best rival occur on record-structured and text data — about 28.5% smaller than the next best on the kennedy.xls spreadsheet, 21.3% on the webster dictionary, and 17.8% on dickens. The files where a rival wins are dominated by xz: nci (−13.4%), ptt5 (−16.0%), and the small sum archive (−20.5%), among a handful of others.[4]
Speed and memory trade-off
[edit]The ratio comes at a cost. Throughput is roughly 0.5–0.7 MB/s, and because the decoder runs the same models the process is symmetric — the full single-block corpus takes on the order of 400 seconds to compress and a similar time to decompress on the reference machine. Each active block requires about 150 MB of model state. The project describes this plainly as spending CPU that zip, bzip2, and rar do not, and buying compression ratio with it. Running SQUISH in its multi-threaded, multi-block mode recovers most of the speed — about 1.86× faster overall on the benchmark, and up to roughly 4× on the large enwik8 file — while giving up about 1.4% of ratio to the cold-start penalty of independent blocks.[1][4]
Implementation
[edit]SQUISH is implemented in portable C with no dependencies beyond the C standard library and math library. It builds a shared and static library, a command-line tool, and — via a MinGW cross-compiler or MSVC — a Windows DLL and executable. The library exposes buffer- and file-level compression functions and a squish_archive_* API for packing, listing, and selectively extracting directory trees; the shared object can be called from Python via ctypes without a dedicated wrapper.[1]
The command-line tool uses subcommands to compress (c), decompress or restore (d), list an archive (l), and extract a single member or subtree (x), with options for thread count and block size and a live progress display.[1]
The implementation guarantees round-trip fidelity through per-block checksums that make decompression fail loudly on corruption, bounded expansion through the stored-block fallback, and thread safety through the absence of global mutable state, so independent (de)compressions on separate buffers may run concurrently.[1]
History
[edit]Version 1.0.0 was the initial release, comprising the context-mixing library, the CLI, the ten models, the integrity checksum and stored-mode fallback, a test suite, the benchmark suite, and project documentation. It was licensed under the GPLv3.[5]
Subsequent development consolidated four never-released pre-release formats — two single-stream formats (SQ01, SQ02) and two directory-archive formats (SQAR01, SQAR02) — into the single seekable SQUISH archive format, and folded parallelism into the core library functions via thread-count and chunk-size parameters rather than separate entry points. A self-extracting archive format and its squish s command were removed in favor of distributing the archive and the CLI separately. Because none of the pre-release formats had shipped, no on-disk data required migration.[5]
Per the project's contribution policy, any change to the model constants in squish.c is treated as a compressed-format break requiring a new magic number, since those constants define the bitstream.[5][3]
Lineage
[edit]SQUISH composes well-known compression primitives. Context mixing is the architecture behind the PAQ family of compressors developed by Matt Mahoney and others, which holds many compression-ratio records. According to its authors, SQUISH's specific set of models, its automatically detected record contexts, its counter and mixer parameterization, and its implementation are original to the project.[2]