Arquivos - LZ77 v3

LZSS v3.16 β€” Levels -0..-9 (v22)

πŸ“‚ Source Code Availability: The C source file for each version is available in Files on SourceForge β€” lzss_v1.1.c, lzss_v1.4.c, lzss_v1.5.c, lzss_v1.6.c, lzss_v1.7.c, lzss_v1.8a.c, lzss_v1.8b.c, lzss_v1.8c.c, lzss_v1.9.c, lzss_v2.0a.c, lzss_v2.0b.c (offset codes), lzss_v2.0c.c (streaming BROKEN, do not use), lzss_v2.0d.c (single-pass fixed-memory, legacy 12B header), lzss_v2.1_ds32_BE.c (previous: REP-4 + LE + magic/version 1), lzss_v2.2_slots.c (slots + Huffman selector, version 2), lzss_v2.3_range.c (range order-0 literals, version 3), lzss_v2.4_ctx.c (range order-1 nibble-class literals, version 4), lzss_v2.5_mix.c (per-literal implicit judge order-0 x 16ctx, version 5), lzss_v2.6_flags.c (+ order-1 binary match/lit flags, version 6), lzss_v2.7_slots.c (+ order-1 slot selector, version 7), lzss_v2.8_len.c (+ order-1 len Huffman, version 8), lzss_v2.9_rep.c (+ order-1 REP-hit context, version 9), lzss_v3.0_bcj.c (+ per-block BCJ x86 filter, version 10), lzss_v3.1_fix.c (stored+BCJ corruption fix, version 11), lzss_v3.2_dp.c (optimal DP parse + fair guard, version 12), lzss_v3.3_dp2.c (DP REP-aware + 2nd iteration + hash restore, version 13), lzss_v3.4_sel.c (quota shortlist + rep_en fix, version 14), lzss_v3.6_fast.c (skip DP2 convergido, version 15), lzss_v3.7_win.c (janela 512K + pedΓ‘gio greedy, version 16), lzss_v3.8_long.c (matches atΓ© 65535, version 17), lzss_v3.9_tiny.c (tabelas singleton compactas, version 18), lzss_v3.11_rep.c (SUPERSEDED before release: repeat-bit v19, do not use), lzss_v3.12_gate.c (repeat escape len==0, version 20), lzss_v3.13_frame.c (framing compacto 2b, version 21), lzss_v3.13_frame.c (framing compacto 2b, version 21), lzss_v3.14_slots.c (Γ‘rvores esparsas kind 11, version 21), lzss_v3.15_reuse.c (reuse cross-block, version 22), lzss_v3.16_levels.c (current: levels -0..-9, mesma version 22, use this) + invtest.c (inverter/judge/context bit-level test harness, modes 0-5) + bcjtest.c (standalone BCJ filter) (e.g. https://sourceforge.net/projects/lz77-v3/files/). Browser AIs can read the raw .c directly via .../files/<name>.c/download. Old v1.8 (Huffman Full) / v1.9-RC (Range Coder) were discarded β€” only approached gzip, never beat it.

An ultra-efficient, production-grade derivation of Haruhiko Okumura's LZSS (1989), optimized for bit-level stream efficiency, blazing-fast index lookups, architectural safety, and resilient cross-platform validation.

By replacing fixed-token byte structures with a unified bit-writer stream, deploying a concurrent dual sliding window setup, and driving search lookups with a high-speed hash chain, this engine achieves high data-density compression and asymmetrical runtime performance over machine bytecode and text blocks without statistical tree overhead [πŸ“‘].

πŸš€ Architectural & Engineering Milestones

  1. High-Speed Hash Chaining (v1.3 Breakthrough): Integrated Jean-loup Gailly's legendary chained index lookup mapping strategy [πŸ“‘]. The engine bypasses brute-force linear searches by computing a fast 3-byte window hash, cutting execution time down to virtually 0.00 seconds on compiled binaries and 0.01 seconds on dense text [πŸ“‘].
  2. Dual Sliding Window Integration (v1.2): Operates a dynamic search architecture over two independent history buffers:
  3. Deterministic Bit-Cost Balancing: Implemented a specialized evaluation matrix determining selection based on true bit value. The engine only commits to the 14-bit window if the extra match sequence mathematically breaks even against the 5-bit offset penalty over the shorter 9-bit option [πŸ“‘].
  4. Fixed Memory Streaming (v2.0d): compressor uses a fixed ~1.6MB ceiling for any input size (ring 256KB + head 256KB + prev 512KB + toks 512KB). No malloc(file_size), no ftell, single-pass with incremental Adler-32 and 20B header backpatch (12B before magic, v2.1+). Decompressor uses ~260KB (ring 256KB). Old "under 16KB" claim was true only up to v1.9 β€” v2.x 128K window needs the hash tables (see Memory Limits below).
  5. Adler-32 Integrity Anchor: Employs a rigid 12-byte layout fixed to the absolute header sequence containing an Adler-32 checksum (honoring Mark Adler's contribution to compression science) [πŸ“‘]. The decompressor executes validation over the output block to guarantee byte-perfect restoration.
  6. REP Offsets, zstd-inspired (v1.8a): Per-block switch tracking the last 3 offsets; repeat matches encode a 2-bit index instead of the full 9/15-bit offset. Costs 1 bit/block where useless, saves 7–13 bits per repeat where it hits (texto_rep -32%, zeros -31%, misto -1067B).
  7. 15-Bit Long Window (v1.8b): Long window grows 14-bit (16,383B) β†’ 15-bit (32,767B, same as gzip). Costs +1 bit per large match, pays off on every file larger than 16KB (make.txt -4.6%, ja_comprimido -43%).
  8. 10-Bit Short Window (v1.8c): Short window grows 9-bit (511B) β†’ 10-bit (1,023B). Offset histogram showed 500-700 matches/block in 512-1023 paying 20b large, now 15b short (make.txt -1%, make.bin -117B).
  9. Flag-Remap (v1.9): Per-block 1-bit switch; large-dominated blocks use large=0 / lit=10 / short=11 instead of lit=0. Auto-disabled where literals dominate (make.bin Β±0) or REP is on (make.txt -1.67%).
  10. Single-Pass Streaming (v2.0d, fixes v2.0c): same format/tokens as v2.0b (bit-identical output), but ring-buffered. Fixed v2.0c ring_end -= drop corruption (lost 1 byte per 128K slide, first fail at byte 131074 of make.txt).
  11. REP-4 + LE + Magic (v2.1, first format break): REP history 3 β†’ 4 ({1,8,32} + 128), same 2-bit code β€” small win on binaries (make.bin -38B payload, binario_ls -94B), neutral on text. Header/total_len/raw_len forced LE (BE-safe memcmp matcher, __builtin_clz bitlen). 20B header with magic "LZSS" + version 1 (was 12B, no magic). Incompatible with v2.0d and older by design: old decoders guard-trip on v2.1 files, new decoder rejects magic-less files with a clear message.
  12. Slot Distances (v2.2, window flag dead): all distances 1–131071 through lzip-style slots 0–33 (magnitude = msb+nextbit) with per-block Huffman-coded selector (existing canonical machinery) + raw footers. No window flag, no remap (needed the flag; ~2KB txt headwind accepted, still net βˆ’1.55%). Per-block has_slots bit skips the slot tree where unused (zeros identical). REP-4 untouched. Header version 2.
  13. Range order-0 + order-1 nibble-class literals (v2.3/v2.4): LZMA-style byte range core (canonical ShiftLow, no tables) with per-block literal mode in the same 2 bits (00 fixed / 01 huff / 10 range order-0 / 11 range order-1 by prev>>4, 16 ctx, adaptive, continuous across blocks via snapshot). Header version 4 (decodes v2/v3/v4). 256-ctx lost by 1–3% (warmup); 16 classes won on binaries.
  14. Per-literal implicit judge (v2.5): MIX mode switches order-0 x 16ctx per literal with 0 side bits (both models advance always, discounted scores, post-update costs, identical order both sides). Header version 5. Neutral-to-tiny (Β±bytes): block selection already captures ~99%.
  15. Order-1 binary match/lit flags (v2.6, current): per-block flagctx bit; flags via binary RC order-1 (ctx = prev flag) in own payload, bodies in second payload (u32 len + backpatch). Independent of literal mode. Header version 6 (decodes v2..v6). Biggest jump since slots: misto βˆ’10.4%, ja_comprimido βˆ’10%, beats gzip-9 on make.bin.
  16. Order-1 slot selector (v2.7, current): per-block slotctx bit (only if has_slots); selector via adaptive RC order-1 by magnitude class (4 ctx Γ— 34 syms, fresh/block) in own payload, footers stay in bodies. Replaces Huffman tree+codes where exact min-selection wins. Header version 7 (decodes v2..v7). bin βˆ’354, txt βˆ’340, binario_ls βˆ’368; rest identical.
  17. Order-1 len Huffman (v2.8, current): per-block lenctx bit; len_code via Huffman order-1 by prev-len class (3 ctx Γ— 8 syms, exact 2-pass), codes precomputed per token, extra byte raw. Header version 8 (decodes v2..v8). Biggest single jump yet: bin βˆ’716, txt βˆ’353, texto_rep βˆ’12.5%, zeros βˆ’944.
  18. Order-1 REP-hit context (v2.9, current): per-block repctx bit (only if rep_en); yes/no bit via binary RC order-1 (ctx = prev outcome), index stays in bodies. Header version 9 (decodes v2..v9). binario_ls βˆ’454, texto_rep βˆ’665, zeros βˆ’352; low-rep files identical.
  19. BCJ x86 filter per block (v3.0, current): per-block bcj bit; E8/E9 rel32β†’abs with global base before parsing, exact proxy decision (cover margin 256B), hash history via snapshot, Adler always original. Header version 10 (decodes v2..v10). bin βˆ’3.800 (βˆ’4.5%), binario_ls βˆ’1.755; rest identical.
  20. Stored+BCJ fix (v3.1, current): stored blocks restore raw ring (no marker exists); lazy-2-by-sum reverted (overlap double-count β†’ literal flood). Sizes identical to v3.0. Header version 11 (decodes v2..v11).
  21. Optimal DP parse + fair guard (v3.2): pass-1 greedy β†’ tables A; DP over DAG (literal + top-16-by-len + pinned best/short/long, table costs, prev-len-class state); each stream estimated with its own optimal tables (+REP walk + flag order-1 entropy), switch on clear win. Header version 12 (decodes v2..v12). bin βˆ’784, codigo βˆ’123, misto βˆ’688; txt βˆ’83.
  22. DP REP-aware + 2nd iteration + hash restore (v3.3): each of the 3 passes (greedy, DP1, DP2) restarts hash tables from the block-entry snapshot β€” without this, greedy's future inserts truncate DP's chain (break on mp>=pos) and DP loses all cross-block matches. DP costs model REP hits via fixed per-position history from the reference path (hit = flag+repbit+2b index+len, miss = +1 repbit; model follows greedy's rep decision, refined by DP1's for DP2); DP2 re-parses with tables B + history from DP1; best-of-3 (greedy/DP1/DP2, each with own optimal tables + best rep 0/1 + flag order-1 entropy), guard 256b. 32 candidates/pos (16β†’32 keeps mid matches when cross-block longs flood the top list). Header version 13 (decodes v2..v13). bin βˆ’1.353, txt βˆ’5.453, binario_ls βˆ’953 (fixes v3.2 +34 noise); misto +688 (guard falls back to greedy everywhere β€” open); price: ~2-3x compress time (txt 7.6s, texto_rep 2.2MB 140s in WSL2).
  23. Quota shortlist + rep_en fix (v3.4, current): DP candidates as quotas β€” top-12 by len + top-12 by save + top-8 by save among recent (dist≀4096) + 3 pins (32 total) β€” plus rep_en decision fixed to (boβˆ’3)/hit instead of (boβˆ’2) (a hit costs repbit+2b index = 3b; the extra +1/hit switched REP on in marginal blocks). Rejected: top-by-true-saving (compared 1 literal vs whole match β€” garbage ranking), len-bucket diversity (cost more than gained). Header version 14 (decodes v2..v14). bin βˆ’33, txt βˆ’53, binario_ls βˆ’34, zeros βˆ’752; misto βˆ’28 (still +660 vs v3.2, OPEN).
  24. Skip DP2 convergido (v3.6, current): pula o DP2 quando est1>=estA (DP2, que parte das tabelas/hist do DP1~=greedy, repetiria o DP1); guard e custos intactos, bytes idΓͺnticos Γ  v3.4 em todo o corpus. DP2 pulado em 45/48 blocos no misto (tempo 100sβ†’29s), 0/7 no bin (DP1 vence sempre β€” sem atalho). Header version 15 (decodes v2..v15; v15 queimada pela v3.5 descartada, reutilizada aqui).
  25. Janela 512K + pedΓ‘gio greedy (v3.7, current): janela longa 128Kβ†’512K (slots lzip 34β†’38 sozinhos, resto genΓ©rico; ring 1MB, prev 2MB) + FAR_PEN=16 sΓ³ no greedy (matches far redundantes diluΓ­am tabelas). DP segue livre com fars e o guard decide. Tunado 8/16/24/32/64. DiagnΓ³stico: no txt o ganho (βˆ’1178) vem do DP2 achando estrutura fewer/longer com fars; no misto o estrago (+2806 sem pedΓ‘gio) vinha do greedy. Header version 16 (decodes v2..v16). txt βˆ’1.178, resto Β±ruΓ­do (bin +38 downstream); lΓ­quido βˆ’1.087 no corpus.
  26. Matches longos atΓ© 65535 (v3.8, current): escape E==255 reservado (shorts atΓ© 257, longs 258+ via u16; custo extra 24b) + clamp 258β†’257+literal + greedy medindo atΓ© 258 (rΓ‘pido) com collect estendendo full-len sΓ³ nas 8 entradas mais recentes. Bugs pegos: (1) E==255 ambΓ­guo p/ len 258 (dessincronizava o decoder β€” truncation no bloco 4 do txt); (2) truesave comparando 1 literal vs match inteiro (ranking loteria, revertido p/ buckets e depois p/ cotas+extensΓ£o). Header version 17 (decodes v2..v17). texto_rep βˆ’12.656, zeros βˆ’5.149 (264B, abaixo do xz 284!), ja βˆ’347 (25.062, abaixo do xz 25.268!); preΓ§o estrutural da reserva do 255 no misto +1.283 (+0,19%).
  27. Tabelas singleton compactas (v3.9, current): framing kind nas Γ‘rvores Huffman (00 vazia, 01 singleton+sΓ­mbolo, 10 bitmap legado) β€” bloco degenerado pagava ~105b de bitmaps vazios. Valores idΓͺnticos (singleton = len 1, convenção do build); decoder dual por fver. Header version 18 (decodes v2..v18). zeros βˆ’68 (196B), resto Β±2b/tabela em blocos densos; lΓ­quido βˆ’51B.

πŸ“Š Empirical Benchmarks (Sep 26, 2026)

Tested directly on active binary machine code from the original MinGW toolchain (make.exe) and unformatted source assets (make.txt), the custom dynamic 3-bit engine outpaces classical platforms [πŸ“‘]:

🎯 1. make.exe (Real MinGW Executable Bytecode)

πŸ“ 2. make.txt (Text Footprint)

🧠 Memory Limits (v3.16, WSL2 verified β€” /usr/bin/time -v: enc 11264 kB, dec 2304 kB)

Compressor (fixed, independent of input size β€” β‰ˆ 10.8MB heap):

🏁 Compression Levels (v3.16, same v22 format at every level)

lzss -c [-0..-9] <input> <output> (default -6; -c <in> <out> = -6). Decoder and bitstream format are identical at all levels β€” levels only change encoder effort:

Decompressor (fixed):

πŸ› οΈ Automated Compilation & Verification

The environment is mapped directly under a linear Makefile layout to preserve proper processing synchronizations across shell routines:

# 1. Compile the source engine under absolute -O3 vectorizations
make

# 2. Run the dynamic target evaluations over real data payloads
make test

# 3. Purge operational artifacts
make clean

Stream Token Layout (lzss_v1.3)

######################################

LZSS v1.2 β€” Custom 3-Bit Dual Sliding Window Compressor

An ultra-efficient, production-grade derivation of Haruhiko Okumura's LZSS (1989), optimized for bit-level stream efficiency, architectural safety, and resilient cross-platform validation.

By replacing fixed-token byte structures with a unified bit-writer stream and deploying a synchronized hybrid search engine, this implementation achieves high data-density compression over both binary structures and text blocks without statistical encoding overhead.

πŸš€ Today's Engineering Achievements

  1. Dual Sliding Window Integration (v1.2): Transitioned from a baseline single window to a dynamic, concurrent search architecture utilizing two distinct history radii:
  2. Deterministic Bit-Cost Balancing: Implemented a specialized evaluation matrix determining selection based on true bit value. The engine only commits to the 14-bit window if the extra match sequence mathematically breaks even against the 5-bit overhead compared to the short window.
  3. 64-Bit Memory Expansion: Rewrote the stream parsers and internal mapping structs to support uint64_t original lengths. The engine natively compresses multi-gigabyte structures while keeping runtime memory footprints bounded under 16KB.
  4. Adler-32 Integrity Anchor: Dedicated a fixed 12-byte layout to the absolute header sequence containing an Adler-32 checksum (honoring Mark Adler's contribution to compression science). The decompressor executes validation over the output block to guarantee byte-perfect restoration.

πŸ“Š Empirical Benchmarks (Sep 25, 2026)

Tested directly on active binary compilation sequences (make.bin) and unformatted source assets (make.txt), the custom dynamic 3-bit engine outpaces classical platforms:

🎯 1. make.bin (Binary Structure)

πŸ“ 2. make.txt (Text Footprint)

πŸ› οΈ Automated Compilation & Verification

The environment is mapped directly under a linear Makefile layout to preserve proper processing synchronizations across shell routines:

# 1. Compile the source engine under absolute -O3 vectorizations
make

# 2. Run the dynamic target evaluations over data payloads
make test

# 3. Purge operational artifacts
make clean

Stream Token Layout (lzss_v1.2)