LZ0 - Asymmetrischer LZ-Kompressor mit minimalem Decoder
Show HN: LZ0 -An asymmetric LZ compressor with ultra minimal, 0-alloc decoder
LZ0 ist ein experimentelles, verlustfreies Kompressionsformat und eine C-Implementierung, die Komplexität bewusst vom Decoder auf den Encoder verlagert. Der Decoder kommt ohne dynamische Speicherzuweisung (malloc) aus, benötigt nur wenige Stack-Register und verarbeitet komprimierte Daten mit Hunderten von Megabyte pro Sekunde. LZ0 eignet sich für kleine bis mittlere Binärdateien und strukturierte Datensätze und bietet Kompressionsraten vergleichbar mit ZX0 – bei deutlich schnellerer Kodierung. Die Referenzimplementierung umfasst mehrere Decoder-Varianten, darunter eine ultra-kompakte C-Version (~40 Zeilen) sowie handgeschriebene Assembly-Decoder für x86-64, ARM64 und RISC-V. Ideal für Bootloader, Mikrocontroller, Retro-Computing und Kernel-Umgebungen.
Verlagere die Komplexität vom Decoder zum Encoder – für eine Dekompression, die so einfach und speicherfrei wie möglich ist.
- nellacross
Ich würde gerne einen tiefergehenden Vergleich mit LZ4 sehen. Ein Decoder im LZ4-Stil lässt sich minimal gestalten, und man kann LZ4HC verwenden, um eine bessere Dichte zu erzielen, ohne die Dekompressionsgeschwindigkeit zu opfern.
- aidenn0
Es wäre schön, Benchmarks gegen lz4hc -9 zu sehen, da dies der engste Konkurrent in Bezug auf sowohl Kompressions- als auch Dekompressionsgeschwindigkeit ist.
- seb3773
Ich habe LZ0 entwickelt, einen asymmetrischen LZ-Kompressor, der auf Umgebungen abzielt, in denen die Dekompressionsressourcen stark eingeschränkt sind (Bootloader, Mikrocontroller, Laden eingebetteter Assets) oder in denen die Einfachheit des Decoders am wichtigsten ist.
Ich habe schon immer Mikro-Decoder wie Einar Saukas' ZX0 bewundert – keine dynamische Speicherzuweisung, kein Scratch-RAM und klein genug, um in eine Handvoll Instruktionen zu passen. Der Haken bei traditionellen optimalen Parsern ist, dass sie oft mit O(N^2) skalieren und bei Dateien über ein paar hundert Kilobyte Dutzende Sekunden oder Minuten brauchen. Ich habe LZ0 geschrieben, um denselben Decoder-Footprint beizubehalten und dabei Multi-Megabyte-Dateien in Millisekunden zu komprimieren.
Wo es einzuordnen ist (Verhältnis vs. Geschwindigkeit): - Kompressionsdichte: schlägt LZ4/Snappy und bleibt innerhalb von 1–3 % von zlib/Deflate und erschöpfendem ZX0. - Dekompressionsgeschwindigkeit: 200–350 MB/s für portables C, 250–700 MB/s für kompaktes ASM und 520–1.330 MB/s für Vektor-ASM. Das ist bis zu 10x schneller als Deflate und benötigt null Heap-Speicher oder Zustandstabellen. - Kompressionsdurchsatz: ~1,3–1,6 s bei typischen 1-MB-Eingaben.
Wie der Encoder die O(N^2)-Wand vermeidet (H2C8-Pipeline): - Mehrstufige Match-Suche: zweistufige Hash-Ketten für lokale Übereinstimmungen, gepaart mit einem O(N)-SA-IS-Suffix-Array für tiefe, weitreichende Übereinstimmungen. - Sparse-DP-Parsing: Anstatt jede Kante im Graphen zu bewerten, gruppiert es Elias-Gamma-Bitkosten in mathematische Plateaus, um redundante Suchen zu überspringen.
Das Repo wird mit drei 0-Alloc-Decoder-Implementierungen ausgeliefert: 1. Portables C (`lz0dec_min.c`): ~75 Zeilen freestanding C mit z […]