Compression is prediction
If you can estimate the probability of the next bit accurately, an arithmetic coder converts those probabilities into a near-optimal code for free. All the effort goes into one fast, online-learning predictor.
▦ Ten specialist models
Order-0…6 byte contexts, a word model, an auto-detected record model, and an unbounded-window match model each vote on P(bit=1) — so SQUISH behaves like LZ on repetitive data, like PPM on text, and like a record codec on tables, without being told which is which.
∑ Logistic mixing
A tiny one-layer network fuses the ten opinions as a weighted sum of log-odds, with the weight set chosen by context and trained online by gradient descent on real coding loss. Useless models are learned away in a few KB.
⇄ Match & record models
A rolling hash finds the most recent identical context and predicts the history simply repeats — LZ77’s long-range power with an unbounded window, but probabilistically. A vote table detects fixed row lengths, lighting up “cell above” contexts that beat RAR’s filters on spreadsheets.
◈ The model is the format
The decompressor runs the identical predictor in lockstep, so the format needs no dictionaries, tables, or block structure. Every coded block carries a 32-bit checksum; incompressible data falls back to stored blocks, so expansion is bounded.
The pipeline, per bit
order-0..6 byte contexts (7) ┐
word model ├─▶ each emits P(bit=1) from an adaptive counter
record model (row length R) │
match model (6-byte hash) ┘
│
▼ logistic mixer — 11 inputs, 1024 context-selected weight sets
▼ 2 chained APM/SSE stages — recalibrate against what happened
▼ carryless 32-bit binary arithmetic coder
output bitsFull algorithm write-up: SQUISH.md · byte-level spec: docs/FORMAT.md
Results
Silesia + Canterbury + enwik8 — 315 MB across 24 files, every file round-trip verified. Ratio-optimal single-block SQUISH against each rival’s strongest setting.
| file | original | zip -9 | bzip2 -9 | rar -m5 | xz -9e | SQUISH | vs best |
|---|---|---|---|---|---|---|---|
| enwik8 | 100,000,000 | 36,493,328 | 29,008,758 | 26,922,421 | 24,831,648 | 22,461,575 | +9.5% |
| silesia/mozilla | 51,220,480 | 19,032,067 | 17,914,392 | 15,147,513 | 13,376,240 | 14,305,318 | −6.9% |
| silesia/webster | 41,458,703 | 12,114,412 | 8,644,714 | 9,030,482 | 8,368,672 | 6,584,906 | +21.3% |
| silesia/nci | 33,553,445 | 2,998,618 | 1,812,734 | 1,858,838 | 1,449,272 | 1,643,448 | −13.4% |
| silesia/samba | 21,606,400 | 5,406,446 | 4,549,759 | 4,107,454 | 3,739,524 | 3,529,273 | +5.6% |
| silesia/dickens | 10,192,446 | 3,859,202 | 2,799,520 | 3,032,424 | 2,831,212 | 2,300,272 | +17.8% |
| silesia/osdb | 10,085,684 | 3,667,602 | 2,802,792 | 3,237,063 | 2,844,556 | 2,401,772 | +14.3% |
| silesia/mr | 9,970,564 | 3,656,264 | 2,441,280 | 2,775,664 | 2,751,892 | 2,200,359 | +9.9% |
| silesia/x-ray | 8,474,240 | 5,957,301 | 4,051,112 | 4,162,449 | 4,491,264 | 3,732,271 | +7.9% |
| silesia/sao | 7,251,944 | 5,318,180 | 4,940,524 | 5,542,741 | 4,425,664 | 3,968,327 | +10.3% |
| silesia/reymont | 6,627,202 | 1,826,497 | 1,246,230 | 1,444,933 | 1,315,592 | 1,112,376 | +10.7% |
| silesia/ooffice | 6,152,192 | 3,078,367 | 2,862,526 | 2,302,529 | 2,427,224 | 2,412,103 | −4.8% |
| silesia/xml | 5,345,280 | 661,981 | 441,186 | 484,735 | 434,892 | 385,143 | +11.4% |
| canterbury/kennedy.xls | 1,029,744 | 207,125 | 130,280 | 35,651 | 51,868 | 25,479 | +28.5% |
| canterbury/ptt5 | 513,216 | 52,783 | 49,759 | 49,348 | 39,860 | 46,231 | −16.0% |
| canterbury/plrabn12.txt | 481,861 | 194,869 | 145,577 | 175,669 | 165,456 | 130,534 | +10.3% |
| canterbury/lcet10.txt | 426,754 | 144,475 | 107,706 | 126,510 | 119,488 | 94,649 | +12.1% |
| canterbury/alice29.txt | 152,089 | 54,320 | 43,202 | 51,262 | 48,528 | 38,687 | +10.5% |
| canterbury/asyoulik.txt | 125,179 | 48,950 | 39,569 | 47,009 | 44,592 | 35,725 | +9.7% |
| canterbury/sum | 38,240 | 12,976 | 12,909 | 11,684 | 9,500 | 11,447 | −20.5% |
| canterbury/cp.html | 24,603 | 8,069 | 7,624 | 8,156 | 7,652 | 6,787 | +11.0% |
| canterbury/fields.c | 11,150 | 3,212 | 3,039 | 3,202 | 3,032 | 2,819 | +7.0% |
| canterbury/xargs.1 | 4,227 | 1,830 | 1,762 | 1,860 | 1,812 | 1,710 | +3.0% |
| canterbury/grammar.lsp | 3,721 | 1,316 | 1,283 | 1,359 | 1,292 | 1,252 | +2.4% |
| TOTAL | 314,749,364 | 104,800,190 | 84,058,237 | 80,560,956 | 73,780,732 | 67,432,463 | +8.6% |
SQUISH beats zip + bzip2 + rar on 23/24 files, and beats all four (including xz -9e) on 19/24. “vs best” compares SQUISH to the smallest rival output for that file. The trade: ~0.6 MB/s, symmetric, ~150 MB of model memory per active block — SQUISH spends CPU that zip/bzip2/rar don’t and buys ratio with it. Full table: bench/RESULTS.md.
Command-line tool
Everything SQUISH writes is one format: a SQUISH archive. The input may be a file or a whole directory tree — either way the output is an archive, each file its own member.
./squish c bigfile bigfile.sqsh # compress a file
./squish d bigfile.sqsh restored # restore it (checksum-verified)
./squish c project project.sqsh # pack a whole directory tree
./squish l project.sqsh # list the archive's contents
./squish x project.sqsh src/main.c # extract one file (or a subtree)
./squish d project.sqsh restored-dir # recreate the whole tree
./squish -t 0 c bigfile bigfile.sqsh # compress on all cores
./squish -t 0 -b 4 c big big.sqsh # ... with 4 MiB blocks (more parallel)- Members are stored sorted, so output depends only on the tree; extraction refuses absolute paths and
.., so an archive never writes outside its target. -t Nsplits each member into independently modeled blocks for near-linear speedup, at ~1–2% ratio cost. The default-t 1keeps the ratio-optimal single-block layout.- A live status line (percent, bytes, throughput) shows while working;
-qsuppresses it.
Library
SQUISH is a linkable C library — squish.h + libsquish.so (or squish.dll on Windows). Python needs no wrapper; libsquish.so loads directly with ctypes.
Compress a buffer and back
#include <squish.h>
/* trailing args: threads (0 = all cores, 1 = serial),
* chunk size (0 = 16 MiB), progress callback + user pointer */
void *c, *d; size_t cn, dn;
squish_compress_alloc(data, n, &c, &cn, 1, 0, NULL, NULL);
squish_decompress_alloc(c, cn, &d, &dn, 0, NULL, NULL); /* integrity-checked */
squish_free(c); squish_free(d);Pack a tree, reach one member without inflating the rest
squish_archive_create("project", "project.sqsh", 0, 0, NULL, NULL);
squish_archive *a;
squish_archive_open("project.sqsh", &a);
squish_archive_extract_path(a, "src/main.c", &d, &dn); /* just this file */
squish_free(d); squish_archive_close(a);Link with -lsquish -lm -pthread (or pkg-config --cflags --libs squish after install). Full reference: docs/API.md · examples: example.c, example.py.
Build & install
No dependencies beyond libc / libm.
make # libsquish.so + squish CLI
make test # build and run the test suite
make install # headers, libs, CLI, pkg-config to /usr/local
make dll # squish.dll + squish.exe via mingw-w64
make windows-dll # ... via MSVC (cl.exe on PATH)On Windows without make, run build-windows.bat — it locates Visual Studio automatically and builds squish.dll + squish.exe.
Guarantees & limits
- One on-disk format — every output is a SQUISH archive (magic
SQSH). - Round-trip fidelity — every coded block carries a 32-bit checksum; decompression fails loudly on corruption.
- Bounded expansion — incompressible data falls back to stored blocks.
- No global mutable state — concurrent (de)compressions on different buffers are safe. Up to 4 GiB per member.