CHANGELOG -- lz77-v3 Evolution All notable architectural upgrades, bitstream adjustments, and optimization breakthroughs for the lz77-v3 project are documented in this file. ------------------------------------------------------------------------ [v3.17] -- 2026-10-09 (Zero-find DP skip -- DISCARDED, file removed) Proposta: pular DP1+DP2 quando o greedy acha zero finds>=3 (mesmas chains do DP => DP so repetiria literais; prova completa + BCJ-cover intacto, pois toks finais identicos). Implementado, 9/9 byte-identical + RT tudo OK. Medido: ganho ~zero -- random tem ~3% de matches de acaso (3B em 512KB de historia) e nfind nunca zera; todo o resto tem matches reais. Afrouxar p/ "zero tokens" quebra a exatidao (toll rejeita far que o DP sem toll pegaria; custos Huffman vs fixos diferem). Removido pela regra do degenerado (codigo que nao dispara nao embarca). Velocidade continua nos levels (-1 = 0.5s no random) e nos skips exatos v3.6/v3.12. ------------------------------------------------------------------------ [v3.16] -- 2026-10-09 (Levels -0..-9, MESMA v22, so encoder) CLI `-c [nivel] in out` (default 6; `-c in out` = 6). Knobs: DP 0-3 / depth 32-256 / BCJ / RC-ctx / RANGE. -0 stored puro; -1 greedy rapido; -5 +DP1; -6 +DP2 d128 (default); -7/-8 depth 192/256 (-8 == v3.15 byte-identical 9/9, provado por cmp); -9 soma DP3 (3a iteracao, best-of-4 com mesmo guard 256: nunca pior que -8, provado -9 <= -8 em 9/9). Decoder/formato intactos. Bug pego: tie-break do best-of reescrito como `est2 672937, -78K: flagctx e O feature do misto) * -5: +DP1 (texto_rep 434, zeros 33, bin 78824) * -6 default: bin 78777@1.9s, txt 109659@4.5s, misto 672115@17s * -9 max: bin 78620 (-4 vs -8), txt 108649 (-25), binario 59238 (-31), codigo 4416 (-1); resto == -8. Memoria ~11.0MB RSS (11264 kB, +toksDP2). ------------------------------------------------------------------------ [v3.15] -- 2026-10-08 (Reuse cross-block de tabelas -- v22) 1 bit reuse_lit/reuse_slot/reuse_len apos o repctx, SO quando a arvore existiria (mode==1 / has_slots&&!slotctx / lenctx) E algum bloco passado a emitiu (have persistente -- encoder/decoder derivam igual, sem bit extra). Corpos usam os codigos prev (sobrescreve codes+lens pos-estimativa); gate por min-EXATO em inteiros (prev_body vs new_body + tree_cost, margem 0; ok_* exige todo simbolo coberto pela prev). fver<=21 legado (v19 rejeitada). Ideias B/C do Meta rejeitadas com dados (codigo.c tem 2927 toks; random 15B). Bug pego: build_canonical le 256 entradas -- pv_len[_c] ([8] estreito) lia lixo da pilha e dessincronizava (make.bin/txt FAIL); fix com pv8[256] zerado (espelho do decoder). v22 exigido por bits novos em posicao existente. Measured (WSL2 gcc -O2, cmp+Adler PASS, 9/9; deltas vs v3.14, tudo <=0) * texto_rep 541 -> 434 (-107; xz -e 504 RETOMADO por 70; slot reuse em 33 blocos) * misto 672189 -> 672124 (-65); make.txt 108688 -> 108674 (-14) * make.bin 78631 -> 78624 (-7); ja 25054 (-3); resto identical (codigo 1 bloco nao reusa, como previsto). Total ~-196B. V21BACK_OK, V22REJECT_OK. * Placar: vs gzip-9 7/9, vs xz -e 4/9, vs zstd-19 2/9 (texto_rep ainda +138). ------------------------------------------------------------------------ [v3.14] -- 2026-10-08 (Arvores esparsas kind 11 -- MESMA v21, sem bump) Diagnostico V25DBG: texto_rep blocos 2+ tem ntoks=2, ctx off, sem payloads; o porco e o bitmap de slots (38b+lens p/ 2 simbolos). Kind 11: count + (indices crescentes + lens 4b). min-EXATO dentro do bw_tree (nunca pior): bitmap = 2+N+4n vs esparsa = 2+cb+n*(sb+4) -- slot38 vence com n<=5, lit256 com n<=30, len8 nunca. Decoder valida ordem crescente (dup=erro). Nenhuma v21 publicada, sem bump (precedente v3.1/v11); binario v3.13 aborta kind 11 com erro claro (provado V313REJECT_OK). Degenerado frame-11 avaliado e REJEITADO com dados: slot flat 6b perde 5b p/ Huffman 1b nos poucos simbolos (0 takes no corpus; near-dup sintetico 5x64KB+1B: 77B vs 77B, 0 takes). Piso ~120b/bloco p/ longs far e informacao (footer+extra) -- zstd so passa com reuse cross-block (fora de escopo). Measured (WSL2 gcc -O2, cmp+Adler PASS, 9/9; deltas vs v3.13) * texto_rep 625 -> 541 (-84; xz -e 504, gap 37; 34 takes esparsos) * ja 25058 -> 25057 (-1); resto 7/9 BYTE-IDENTICAL (min-exato provado) * V20BACK_OK (le v20/v18); binario v3.13 rejeita kind 11 com erro claro. ------------------------------------------------------------------------ [v3.13] -- 2026-10-08 (Framing compacto 2b -- v21) u32 len por bloco sempre desperdicava ~15b (bloco <= 65536): agora prefixo 2b apos o bit de tipo -- comprimido: 00 = full 64K, 01 = u16 parcial, 10 = repeat (len = prev len); 11 reservado (erro claro). Stored: mesmo prefixo apos flush (00 full, 01 u16; 10/11 invalidos) + flush antes do raw (simetria de alinhamento). Parcial so existe no ultimo bloco (encoder nunca emite parcial no meio) -- decoder exige parcial alcancando total_len. fver<=20 le u32 legado (v19 segue rejeitada). Zero constants de conteudo: economia vem do formato. Bug pego: fwrite do stored sem flush apos os bits do frame (raw mid-byte) -- flush + br_align espelhados. Measured (WSL2 gcc -O2, cmp+Adler PASS, 9/9; deltas vs v3.12, tudo <=0) * zeros 93 -> 33 (-60; xz -e 284 beaten by 251; zstd-19 53 BEATEN by 20) * texto_rep 751 -> 625 (-126); misto 672241 -> 672189 (-52) * random 1048676 -> 1048628 (-48; zstd-19 1048613, gap 15) * make.txt 108706 -> 108688 (-18); make.bin 78639 -> 78631 (-8) * binario_ls -9; ja 25063 -> 25058 (-5; xz -e 25268 beaten by 210) * codigo 4419 -> 4417 (-2; gzip-9 4292, gap 125 -- tabelas dominam aqui) * Total corpus: ~-328B. V20BACK_OK, V18BACK_OK, V20REJECTS21_OK. * vs zstd-19 agora 2/9 (bin + zeros); vs xz -e 4/9; vs gzip-9 7/9. ------------------------------------------------------------------------ [v3.12] -- 2026-10-08 (Repeat vira escape len==0 -- taxa zero) v3.11 (v19, repeat-bit 1+32+1b) SUPERSEDED antes de qualquer release (nunca publicada; v19 rejeitada com mensagem clara). Motivo: o bit custava +1b/bloco em arquivo sem repeat (misto +9B, texto_rep +4B, bin +2B, ja +1B) -- e o "gate depois do primeiro hit" e impossivel em single-pass (o primeiro hit precisaria de um bit que o decoder ainda nao espera; header-backpatch nao resolve porque os blocos sao escritos antes do futuro ser conhecido). Solucao: escape no proprio u32 len. len==0 era invalido em TODAS as versoes (decoder antigo aborta com erro claro, sem corrupcao silenciosa). Bloco normal volta a ser bit-identical a v18 (1+len+bcj+...): taxa zero PROVADA (payload pos-header byte-identical a v3.9 nos 8 arquivos sem repeat). Repeat = 1+32b (len implicito = prev len, sempre igual -- encoder so repete com mesmo len; prev BCJ inibe). Sem constants magicas, sem cegueira a repeats tardios, -1b/repeat vs v3.11. v20 (le v2..v20 exceto v19). Measured (WSL2 gcc -O2, cmp+Adler PASS, 9/9 corpus) * zeros 1M: 196 -> 93 (-103; v311 era 95: -2B dos repeat=0 eliminados; xz -e 284 beaten by 191; zstd-19 53) * zeros time ~96s -> ~7s (DP pulado em 15/16 blocos repeat) * resto 8/9 TAMANHOS == v3.9 (bin 78639, txt 108706, misto 672241, texto_rep 751, binario_ls 59278, codigo 4419, random 1048676, ja 25063) * V18BACK_OK (le v18); V19REJECT_OK; memoria inalterada (~10.8MB enc). * Survey 08/10 (sha256 por bloco 64KB, distancias 1-8, todo o corpus): ZERO pares identicos em 8/9 arquivos (texto_rep 34 blocos, misto 16, resto 1-5 -- nenhum). So zeros repete (15 hits d1, trivial -- ja pego pelo escape distancia-1). Conclusao: repeat de distancia variavel (Ideia 1 Meta, historico XXH3 8 entradas) daria +0B no corpus. NAO IMPLEMENTADO -- morto com dados, como a v3.10. Proximo: regime de bloco pequeno (codigo.c perde pros 3: gzip +127 / xz +279 / zstd +287). ------------------------------------------------------------------------ [v3.11] -- 2026-10-07 (Whole-block repeat, 1+32+1b -- SUPERSEDED, never released) Compressed block gains 1 repeat bit after u32 len (v19): if raw bytes of the block == previous raw block (same len, memcmp), emit 1+32+1b and skip parse/BCJ/DP/hash-restore (hash_insert only for future history). Decoder copies prev block from ring (+Adler+output). Safe: compares raw bytes, never tokens; prev BCJ-filtered inhibits (ring holds filtered bytes). First block never repeats. v19 (v18 files still decode: V18BACK_OK; v18 binaries reject v19 with clear message). Cost: +1b per compressed block where it misses (~+0-9B). Win: whole-block runs collapse. Measured (WSL2 gcc -O2, cmp+Adler PASS, 9/9 corpus) * zeros 1M: 196 -> 95 (-101, -52%; xz -e 284 beaten by 189) * zeros time ~96s -> ~6s (DP skipped on 15/16 repeat blocks) * texto_rep 751 -> 755 (+4: no whole-block alignment, longs already won) * misto +9; binario_ls +1; ja +1; bin +2; codigo/txt/random identical * Net: biggest single-file win since v3.8 longs; only repeat-heavy wins. * Memory (WSL2 /usr/bin/time -v, NEW measurement -- README was stale at v2.2 1.6MB): compressor fixed ~10.8MB heap (11008 kB RSS: ring 1MB + head 256KB + prev 2MB + toks/save/DP1 3x512KB + dpCost 768KB + dpPar 1.5MB + repHist 1MB + h0 snapshot 2.25MB + tables/scratch ~450KB; repeat adds 0 RAM), decompressor ~2.3MB RSS (ring 1MB + model 16KB). Still fixed for any input size (streaming, no malloc(file_size)). ------------------------------------------------------------------------ [v3.10] -- 2026-10-07 (2M window + walk 512 -- DISCARDED, file removed) 512K->2M (slots 38->42, ring 4MB, prev 8MB): uniformly +10~30B everywhere (texto_rep 751->768, no gain). Far history beyond 512K is unreachable: 256-walk takes the 256 most recent same-hash entries, extra tail never surfaces; depth-512 probe also flat (768/672251: bigger pool, same top-N lottery). Lesson: reachable far mass was fully captured at 512K (v3.7); further reach needs adaptive budgets, not raw window. v19 not shipped. ------------------------------------------------------------------------ [v3.9] -- 2026-10-07 (Tabelas singleton compactas) Huffman tree framing with kind (00 empty, len-ctx only; 01 singleton + direct symbol, always len 1 per build convention; 10 legacy bitmap + 4b lens): degenerate blocks (1 lit + 1 long match, est 27b) paid ~105b of empty bitmaps (slot 42b + len 36b). Identical values, decoder dual by fver (legacy bitmap for fver<18). v18 (v2..v18); V17BACK_OK. Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * zeros 1M: 264 -> 196 (-68, -26%; xz -e 284 beaten by 88) * texto_rep -> 751 (+9: dense alphabets pay the +2b/table kind bits) * misto -> 672241 (-3); binario_ls +2; ja +1; codigo/bin/txt +1/+1/+6 * random identical. Net -51B. Sparse-list (count+indices) evaluated and skipped: lit bitmap 256b is already compact, slot saves <=4b. ------------------------------------------------------------------------ [v3.8] -- 2026-10-07 (Matches longos ate 65535) Escape E==255 reserved: shorts up to 257 (E=len-3), longs 258+ via u16 (len = 258+u16, extra cost 24b); clamp 258->257+literal (257+lit beats 255+u16 by ~7b); greedy measures to 258 (fast, unchanged); collect extends full-len only the 8 most recent entries (bounded cost, rest cap 258 for ranking); DP/est/emit/decode carry true lens + 24b extra. v17 (v2..v17); V16BACK_OK. Bugs caught: (1) E==255 ambiguous for len 258 (decoder ate 16 ghost bits -> desync/truncation from txt block 4; reserved 255, shorts to 257); (2) true-save ranking compared ONE literal vs the whole match (garbage, bin +1413 -- reverted); len-bucket diversity also lost to quotas. Bisection proved misto +1283 is the 255-reservation price (noext build is +1640 worse), not DP-longs (extension helps misto by -357). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin 166400: 78640 -> 78638 (-2; zstd-19 80401 beaten by 1763) * make.txt 327528: 108725 -> 108700 (-25; gzip-9 119980) * texto_rep 2211500: 13398 -> 742 (-12656; gzip-9 6099; xz -e 504) * zeros 1M: 5413 -> 264 (-5149; xz -e 284 BEATEN by 20; zstd 53) * ja_comprimido: 25409 -> 25062 (-347; xz -e 25268 BEATEN by 206) * binario_ls -> 59276 (-39); codigo identical; random identical * misto -> 672244 (+1283, +0.19%: structural 255 price on repetitive content -- OPEN alongside v3.2 +660) * Cost: repetitive files slower (zeros 96s, texto_rep ~160s: full-len measures; bounded at 8/pos). ------------------------------------------------------------------------ [v3.7] -- 2026-10-07 (512K window + greedy far toll) Long window 128K->512K (whole-file history up to ~512KB; lzip slots extend themselves 34->38, Huffman/RC/guard already generic; ring 256KB->1MB, prev 512KB->2MB) + FAR_PEN=16 toll ONLY in greedy: redundant far matches dilute tables (misto +2806 with no toll); DP stays toll-free with exact costs and the guard decides. Tuned 8/16/24/32/64 (8 leaks marginals on misto/binario, 32+ eats txt). Post-match literals NOT built: txt uses Huffman (mode 1) on all 5 blocks and post-match lits are rare there; R1/JD sweep also flat. Diagnosis: txt -1178 comes from DP2 finding fewer/longer structure with fars (estA 196302 -> DP2 185529 on block 1); misto damage came from greedy. v16 (v2..v16); V15BACK_OK. Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin 166400: 78602 -> 78640 (+38 downstream noise, est-level ~2B) * make.txt 327528: 109903 -> 108725 (-1178; gzip-9 119980; xz -e 100464) * misto -> 670961 (+6); binario_ls -> 59315 (+13); codigo 4418 (+1) * texto_rep 13398 (+16); zeros 5429 (+16); random/ja identical * Net across corpus: -1087. Bin xz gap: 1984. Txt xz gap: 8261. ------------------------------------------------------------------------ [v3.6] -- 2026-10-07 (Skip DP2 convergido -- same bytes, faster) Skips DP2 when est1>=estA: DP2 starts from DP1's tables/history, so when DP1 ~= greedy it would just repeat DP1. Guard and costs untouched, so output bytes are identical to v3.4 on the whole corpus (verified); only work is skipped (provably <= work of v3.4). DP2 skipped on 45/48 blocks of misto (time ~100s -> 29s in WSL2), 0/7 on make.bin (DP1 genuinely wins there -- no shortcut taken). v15 (v2..v15); v14 files verified readable (V14BACK_OK). v15 was burned by discarded v3.5 and is reused here. Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus -- all sizes = v3.4) * make.bin 78602, make.txt 109903, binario_ls 59302, codigo 4417 * texto_rep 13382, misto 670955, zeros 5413, random 1048676, ja 25408 ------------------------------------------------------------------------ [v3.5] -- 2026-10-07 (Slot order-1 -- DISCARDED, do not use) Two variants tried, both rejected on measurement (WSL2 gcc -O2): (a) DP-12-state (len-cls x slot-cls) with order-1 slot tables: bin -67 but binario_ls +456 (overfit: optimizes for order-1 while real emit sometimes keeps order-0 Huffman; static order-1 tables from small samples don't match adaptive RC). (b) est-only slot order-1 (min Huffman / order-1 entropy): all identical except binario_ls +568 (H1 entropy ignores RC cold-start ~190b/block, flips guard wrongly). File removed; v15 not shipped. Lesson: any order-1 model in est/DP needs cold-start accounting to be guard-safe. ------------------------------------------------------------------------ [v3.4] -- 2026-10-07 (Quota shortlist + rep_en fix) (a) DP shortlist by quotas — top-12 by len + top-12 by save + top-8 by save among recent (dist<=4096) + 3 pins (32 total): with restored history, cross-block longs flood any single top-by-len list and evict mid matches. (b) rep_en decision fixed to (bo-3)/hit instead of (bo-2): a REP hit costs repbit+2b index = 3b vs full offset, so saving is bo-3; the extra +1/hit switched REP on in marginal blocks (real emit worse than est). v14 (v2..v14); v14 decoder verified reading v13 files (V13BACK_OK). Rejected on measurement: top-by-true-saving (compared ONE literal vs the whole match -- garbage ranking, bin +1413), len-bucket diversity 4x8 (bin +105 vs quotas). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin 166400: 78635 -> 78602 (-33; gzip-9 85792; xz -e 76656) * make.txt 327528: 109956 -> 109903 (-53; gzip-9 119980; xz -e 100464) * binario_ls -> 59302 (-34); codigo.c -> 4417 (-3); zeros -> 5413 (-752) * texto_rep/random/ja identical; misto -> 670955 (-28, still +660 vs v3.2's 670295 -- OPEN: DP converges to greedy path under tables-A built from that same greedy path; v3.2's fewer/longer wins need pool entries that any fixed-budget ranking evicts; needs adaptive budget or different table seed, under study) ------------------------------------------------------------------------ [v3.3] -- 2026-10-07 (DP REP-aware + 2nd iteration + hash restore) Each of the 3 passes (greedy, DP1, DP2) restarts hash tables from the block-entry snapshot h0: without this, greedy's future inserts truncate DP's chain (break on mp>=pos) and DP loses ALL cross-block matches (latent in v3.2; most of txt's -5.4KB comes from this fix). DP costs model REP hits via fixed per-position history from the reference path (hit = flag+repbit+2b index+len, miss = +1 repbit; model = greedy's repA, refined by DP1's rep 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. NCAND 16->32 (cross-block longs flood the top-by-len list and evict mid matches). v13 (v2..v13); v13 decoder verified reading v12 files (V12BACK_OK bin+txt). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin 166400: 79988 -> 78635 (-1353; gzip-9 85792; xz -e 76656) * make.txt 327528: 115409 -> 109956 (-5453; gzip-9 119980; xz -e 100464) * binario_ls -> 59336 (-953, fixes v3.2 +34 noise); codigo.c -> 4420 (-10) * texto_rep/zeros/random/ja identical; misto -> 670983 (+688, guard falls back to greedy on every block -- OPEN: DP1 converges to greedy path, NCAND=32 did not recover v3.2's fewer/longer wins; candidate shaping vs table-feedback under study) * Cost: ~2-3x compress time (bin 2.9s, txt 7.6s; texto_rep 2.2MB 140s, misto 1M 100s, zeros 1M 48s -- 3 passes x 35 edges/pos) * Bugs caught: (1) DP double-insert without restore hid pre-block history (see above); (2) est reused greedy's repA for DP streams -- now best rep 0/1 per stream via est_best. ------------------------------------------------------------------------ [v3.2] -- 2026-10-07 (Optimal parse via exact DP + fair guard) Pass 1 greedy -> tables A; DP over DAG (literal + top-16-by-len + pinned best/short/long matches, costs from tables A, state = prev-len class); est A vs B with EACH stream's own optimal tables (+REP walk + flag order-1 entropy), switch on clear win (margin 256b) else greedy. Hash inserts identical coverage both passes. v12 (v2..v12). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin 166400: 80772 -> 79988 (-784; gzip-9 85792; xz -e 76628) * make.txt 327528: 115492 -> 115409 (-83; gzip-9 119980) * binario_ls -> 60289 (+34, margin noise); codigo.c -> 4430 (-123) * misto -> 670295 (-688); texto_rep/zeros/random/ja identical * Bugs caught: (1) lazy-2-by-sum double-counts overlaps (reverted in v3.1); (2) DP candidate set missed greedy's longs (top-by-len + 3 pins); (3) est without REP/flag-ctx favored DP falsely (added both). ------------------------------------------------------------------------ [v3.1] -- 2026-10-07 (Stored+BCJ corruption fix; lazy-2 reverted) Bloco STORED com anel transformado (bcj=1) escrevia bytes filtrados sem marcador -> corrupção silenciosa (Adler pegava). Agora restaura o raw antes do stored. Tamanhos idênticos à v3.0 em tudo (só correção). Também revertido o lazy-2 por soma: matches em +1 e +2 se sobrepõem, a soma conta 2x e o parser vira literal-flood (+52% no txt). Parsing ótimo de verdade exige DP de bloco inteiro (futuro). v11 (v2..v11). ------------------------------------------------------------------------ [v3.0] -- 2026-10-07 (BCJ x86 filter per block) Per-compressed-block bcj bit: 1 = ring filtered with BCJ x86 (E8/E9 rel32->abs, base = global offset, complete opcodes only) before parsing. Decision by exact proxy (match cover raw vs filtered, margin 256B); hash history preserved via snapshot (never zeroed mid-stream). Streaming-safe (block-local positions); Adler always over original (decoder recomputes over inverse range). Header version 10 (v2..v10). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin 166400: 84572 -> 80772 (-3800, -4.5%; gzip-9 85792; xz -e 76628) * binario_ls -> 60255 (-1755); resto idêntico (rejeitado corretamente) * Bugs caught: (1) zeroing hash tables between parses killed cross-block history (+KBs); fixed with H0 snapshot; (2) cover margin 2048 never fired (1 cover-byte ~= 8 bits) -> 256. ------------------------------------------------------------------------ [v2.9] -- 2026-10-07 (REP-hit yes/no with order-1 binary context) Per-block repctx bit (only if rep_en): 1 = REP yes/no bit (0=hit,1=miss) via binary RC order-1 (ctx = prev outcome, 2 fresh models/block) in own payload; 2-bit index stays in bodies. Header version 9 (decodes v2..v9). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin/texto: identical (low rep rate, correctly rejected) * binario_ls -> 62010 (-454); texto_rep -> 13364 (-665) * zeros -> 6165 (-352); ja_comprimido -> 25407 (-14) * rest identical (correctly rejected) ------------------------------------------------------------------------ [v2.8] -- 2026-10-07 (Len codes with order-1 Huffman) Per-block lenctx bit: 1 = len_code (0-6, 7=escape) via Huffman order-1 by prev-len class (short<6/med<10/long, 3 ctx x 8 syms, exact 2-pass); extra byte stays raw. Codes precomputed per token (lcc/lcl/lcb arrays) so all payload loops stay branch-free. Header version 8 (decodes v2..v8). Fixed 3-bit codes were pure waste (short lens dominate). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin 166400: 85288 -> 84572 (-716; gzip-9 85792 beaten by 1220) * make.txt 327528: 115845 -> 115492 (-353; gzip-9 119980) * binario_ls -> 62464 (-722); codigo.c -> 4553 (-58) * texto_rep -> 14029 (-2006, -12.5%); misto -> 670982 (-1005) * zeros -> 6517 (-944); ja_comprimido -> 25421 (-52); random identical ------------------------------------------------------------------------ [v2.7] -- 2026-10-07 (Slot selector with order-1 context) Per-block slotctx bit (only if has_slots): 1 = slot selector via adaptive RC order-1 by magnitude class (s<4?0:s<8?1:s<16?2:3, 4 ctx x 34 syms, fresh/block) in own payload; footers stay in bodies. Replaces Huffman tree+codes where it wins (exact min-selection, no table overhead). Header version 7 (decodes v2..v7). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin 166400: 85642 -> 85288 (-354; gzip-9 85792 beaten by 504) * make.txt 327528: 116185 -> 115845 (-340; gzip-9 119980) * binario_ls -> 63186 (-368); resto idêntico (rejeitado corretamente) * Bug caught in testing: slot cost accounting included footers (kept in both layouts) -> false wins; selector-only comparison fixed it. ------------------------------------------------------------------------ [v2.6] -- 2026-10-07 (Flags match/lit with order-1 binary context) Per-block flagctx bit: 1 = match/lit flags via binary RC order-1 (ctx = prev flag, 2 fresh models/block) in own payload; bodies (matches+literal values) in second payload (u32 len + backpatch). Independent of literal mode (works with fixed/huff/range0/range1/MIX). Header version 6 (decodes v2..v6). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus) * make.bin 166400: 85866 -> 85642 (-224; BEATS gzip-9 85792 by 150!) * make.txt 327528: 116964 -> 116185 (-779; gzip-9 119980) * binario_ls -> 63554 (-361); codigo.c -> 4611 (-16) * texto_rep -> 16035 (-562); misto_1M -> 671987 (-78059, -10.4%) * zeros -> 7461 (-271); ja_comprimido -> 25473 (-2851, -10%) * random identical (correctly rejected) ------------------------------------------------------------------------ [v2.4] -- 2026-10-07 (Range order-1 by nibble class on literals, 4-way select) Adds literal mode 11 (2-bit litmode now full: 00 fixed / 01 huff / 10 range order-0 / 11 range order-1) with zero format overhead vs v2.3. Order-1 model: ctx = prev_literal >> 4 (16 classes x 256 syms, ~16KB), adaptive, no table, CONTINUOUS across blocks with snapshot simulation (live advances only if mode 3 wins the block). Decoder tracks prev per block the same way. Header version 4 (decodes v2/v3/v4). The 256-ctx variant was measured first and lost by 1-3% everywhere (warmup over 256 ctx with only 2-15K lits/block); 16 classes fixed it. invtest harness (invtest.c modes 0-5) proved the implicit-judge machinery with 0 side bits on the side (alternating 20KB -> 106B). Measured (WSL2 gcc -O2, cmp+Adler PASS, all corpus + empty) * make.bin 166400: 85931 -> 85868 (-63; gzip-9 85792, gap 76B; xz -e 76628) * make.txt 327528: 116963 -> 116963 (mode 3 correctly rejected everywhere) * binario_ls 142312 -> 63869 (-145, -0.23%) * codigo.c/texto_rep/misto/zeros/random/ja_comprimido: identical to v2.3 * Bugs caught in testing: (1) ShiftLow missed the 32-bit wrap (Low>>32 carried data, not just carry) -> mask like canonical LZMA; (2) range size estimate dropped the 1 flag bit per literal. ------------------------------------------------------------------------ [v2.2] -- 2026-10-04 (Slot Distances: lzip-style slots + Huffman selector) Kills the window flag. All distances (1..131071) go through lzip-style slots 0-33 (magnitude class = msb+nextbit) with a per-block Huffman-coded selector (reuses the canonical machinery) + raw footers. No window flag, no remap (needed the flag; disabled, ~2KB txt headwind documented below), REP-4 untouched. Per-block has_slots bit skips the slot tree when no match needs slot coding (pure rep-hit blocks). Memory unchanged (~1.6MB enc / ~260KB dec). Format break -> header version 2 (v2.1 files rejected with "Older version", v2.0d with "Bad magic"). Measured (WSL2 gcc -O2 -Wall, cmp+Adler PASS, all corpus + empty) * make.txt 327528: 118809 -> 116963 (-1846, -1.55%; net of remap loss) * make.bin 166400: 87866 -> 86207 (-1659, -1.89%) * binario_ls -> 64216 (-1090, -1.67%); codigo.c -> 4627 (-125, -2.6%) * misto_1M -> 750042 (-1302); ja_comprimido -> 28455 (-18) * random_1M identical (stored); zeros_1M 7728 identical (tree skipped) * texto_rep -> 16589 (+149, +0.9%: slot-table price on rep-heavy blocks that still need the tree; has_slots covers only pure rep-hit blocks) * Bugs caught in testing: fixed-block mode never counted the slot-tree overhead in its estimates (wrong mode on borderline blocks) -> added to fixed_block_bits before release. ------------------------------------------------------------------------ [v2.1] -- 2026-10-03 (REP-4 + LE Header + Magic/Version -- FIRST FORMAT BREAK) Modest gain, kept anyway. Same streaming engine as v2.0d, plus: (1) REP history 3 -> 4 ({1,8,32} + 128), same 2-bit code, per-block enable unchanged; (2) header/total_len/raw_len forced LE (fixes v2.0d native-fwrite bug on BE); (3) match compare via memcmp 8B (portable, no unaligned u64 loads) + __builtin_clz bitlen; (4) 20B header with magic "LZSS" (0x53535A4C) + version u32 = 1 (was 12B len+adler, no magic). Memory unchanged (~1.6MB enc / ~260KB dec). Measured (WSL2 gcc -O2 -Wall, cmp+Adler PASS; disk sizes incl. +8B header) * make.bin 166400 -> 87866 (-30 vs v2.0d 87896; -38 payload, +8 header) * make.txt 327528 -> 118809 (+8 vs 118801; payload bit-identical) * corpus: binario_ls 65392 -> 65306 (-86 disk, -94 payload), misto 751358 -> 751344 (-14 disk, -22 payload), texto_rep/codigo/ ja_comprimido/random/zeros payload-identical (+8 header each). * Incompatible with v2.0d and older by design (REP history differs): old decoder guard-trips on v2.1 files (verified); new decoder rejects magic-less files with a clear message instead of a cryptic guard. ------------------------------------------------------------------------ [v2.0d] -- 2026-10-02 (Single-Pass Streaming, Fixed Memory -- FIXES v2.0c) Same format/tokens as v2.0b (bit-identical output), but no full-file load. Compressor: ring 256KB + head 256KB + prev 512KB + toks 512KB = ~1.6MB fixed for any input size. No malloc(total_len), no ftell (supports >2GB / >4GB and pipes), no double-read: incremental Adler-32 + 12B header backpatch at end. Decompressor: ring 256KB only (~260KB total), already streaming, unchanged logic. Measured (WSL2 gcc -O2 -Wall clean, cmp+Adler PASS 11/11) * make.bin 166400 -> 87896 (identical to v2.0b) * make.txt 327528 -> 118801 (identical to v2.0b, beats gzip-9 119980) * corpus 7/7 PASS: binario, codigo, ja_comprimido, misto, random, texto_rep, zeros; empty + 1B PASS. * Bugs caught in testing: (1) v2.0c ring slide did ring_end -= drop, but ring_end is a file-offset one-past (must not decrement) -> lost 1 byte per 128K slide, first corruption at byte 131074 of make.txt (block 3). Fixed: only ring_base moves. (2) hash_insert limited to block_end skipped 2 hash entries/block (+1B on bin) -> limit to ring_end (resident incl. +2 lookahead), back to bit-identical. ------------------------------------------------------------------------ [v2.0c] -- 2026-10-02 (Streaming Ring -- BROKEN, SUPERSEDED BY v2.0d) First streaming attempt: ring + int32 tables, pre-pass Adler (double read). BROKEN: ring_end bug above corrupts any file >131072 bytes (make.txt FAIL at 131074). Decoder streaming was OK (v2.0b stream decodes PASS). Do not use -- use v2.0d. ------------------------------------------------------------------------ [v2.0b] -- 2026-10-02 (Static Offset Codes on 128K -- INSPIRED, NOT CLONE) v2.0a + magnitude-based offset codes for d >= 1024 (short <=1023 stays raw 10b). No FSE, no zstd frame: own static table. First table (unary 2-5b) punished far offsets (c15+ cost 19-22b > raw 17b) and lost txt by 717B; measured distribution is ~uniform over c10-c16, so flat 3-bit prefix won: totals c10:13 ... c17:20 vs raw 17b. Measured (flat table, Wall-clean, cmp+Adler PASS) * make.bin 89696 -> 87896 (-800) (+2.45% over gzip-9 85792; -977 vs v1.9 88873) * make.txt 119702 -> 118801 (-901, beats gzip-9 119980 by 1179B / ~1%) * binario -1385, codigo -183; misto +401 (far-heavy offsets pay 18-20b), rest neutral. * Bugs caught in testing: (1) large-flagged match with off <= 1023 broke the code domain -> normalize small to short; (2) writer emitted c16 prefix as c17 (desync + guard trip) -> fixed, re-measured. ------------------------------------------------------------------------ [v2.0a] -- 2026-10-01 (128K Window, Raw 17-Bit Offsets -- EXPERIMENTAL) Long window 15-bit (32767) -> 128KB (131071) with raw 17-bit offsets on the v1.9 engine (REP + remap + lit-Huffman kept). Tok.off widened uint16_t -> uint32_t; short stays 10-bit; bit-cost threshold 5 -> 7. Purpose: measure how much hides beyond 32K. Measured * Offset histogram (per 64KB block): txt has ~7K matches in 32-64K and ~6.6K in 64-128K; bin only ~3K total beyond 32K. * make.bin 88873 -> 89696 (+823 worse -- few far matches don't pay +2b on every large). * make.txt 124603 -> 119702 (-4901, -3.9%) -- first time beating gzip-9 (119980), by 278B. * Roundtrip PASS (cmp + Adler-32), Wall-clean. Hash memory ~1.5MB (breaks the old 16KB-RAM claim). * Lesson: the gold beyond 32K is real (txt) but raw fixed offsets tax it (bin). Next: magnitude-based offset codes (zstd method) as v2.0b, no FSE yet. ------------------------------------------------------------------------ [v1.9] -- 2026-10-01 (Flag-Remap on v1.8c; old Range-Coder discarded) Per-block flag switch on top of v1.8c (REP + 15b + short 10b), active only when REP is off. Large-dominated blocks encode large=0 (1b), lit=10, short=11. (Old v1.9 Range-Coder order-0: approached gzip, discarded -- complexity not worth it.) Added * Flag-remap 1b/block: lit-dominated blocks keep lit=0; large-dominated flip to large=0. Costs 1b/block, saves ~1b per large match net of dearer literals. * Verified Gains over v1.8c: make.bin 88873 -> 88873 (0, remap correctly stays off), make.txt 126715 -> 124603 (-2112, -1.67%); rest +/-4B mode-bit noise; 9/9 PASS (cmp + Adler-32), Wall clean. * Bug caught in testing: first cut emitted a stray leading 1 before remapped matches (encoder/decoder desync, +3KB + guard trip); fixed, re-measured. ------------------------------------------------------------------------ [v1.8c] -- 2026-10-01 (Short Window 10-Bit, 1023B) Short window 9-bit (511) -> 10-bit (1023); large stays 15-bit. Offset histogram showed 500-700 matches/block in 512-1023 paying 20b large, now 15b short. Added * 10-Bit Short Window: WS_SMALL 511 -> 1023, short token 14b -> 15b, large token stays 20b. Net win everywhere it matters. * Verified Gains over v1.8b: make.bin 88990 -> 88873 (-117), make.txt 127983 -> 126715 (-1268, -1%); binario -13, codigo -41; misto +10B, texto_rep +7B (noise); 9/9 PASS, Wall clean, Adler-32 OK. ------------------------------------------------------------------------ [v1.8b] -- 2026-10-01 (Long Window 15-Bit, 32767B) Long window 14-bit (16383) -> 15-bit (32767, same as gzip). Costs +1b per large match, pays off on every file >16KB. Added * 15-Bit Long Window: WS_LARGE 16383 -> 32767; large token 19b -> 20b (long escape 27b -> 28b). 13b variant tested and rejected (make.txt +7568 worse -- window matters more than 1 bit). * Verified Gains over v1.8a: make.bin 89483 -> 88990 (-493), make.txt 132894 -> 127983 (-4911, -3.7%); ja_comprimido 57162 -> 32373 (-43%); 9/9 PASS, Wall clean. ------------------------------------------------------------------------ [v1.8a] -- 2026-10-01 (REP Offsets Per-Block, zstd-inspired) Tracks last 3 offsets; repeat matches encode a 2-bit index instead of the full offset. Per-block enable bit -- zero cost where rep-rate is low. Added * REP-3 with per-block switch: rep token 7b (+8 extra if long) vs 14/20b normal; non-rep pays +1b flag only in REP-enabled blocks. Rep-rate measured: make.bin 7%, make.txt 0.5%, texto_rep 93%, zeros 99%. * Verified Gains over v1.7: make.bin 89654 -> 89483 (-171), misto -1067, texto_rep -32%, zeros -31%; 9/9 PASS, Wall clean. ------------------------------------------------------------------------ [v1.9] -- 2026-09-26 (Range Coder Order-0 Adaptive) -- DISCARDED Entropy backend replaces Huffman; carry-safe LZMA-style RC, zero table overhead. Added * Adaptive Range Coder: models bit/256/16/256 per block, uniform init, rescale at 16383; offsets raw bits, extra-length via own model; self-framed byte-aligned blocks (type + u32 decomp + u32 paylen + payload). * Verified Gains over v1.8: make.bin -1.6%, make.txt -0.7%, texto_rep -37%, zeros -39%, misto -10.7% (a 0.4% do gzip!), binario -2.6%; random stored igual; 9/9 PASS, Wall clean. ------------------------------------------------------------------------ [v1.8] -- 2026-09-26 (Huffman Full + Re-parse by Real Cost) -- DISCARDED Match_types (16) join literals in Huffman; 2-pass parsing with true costs. Added * Match-Type Huffman (16 syms = use_large*8+len_code): replaces fixed 4b header with variable code; per-table fallback flags (lit_huff, mt_huff); offsets/extra stay fixed. * Two-Pass Re-parse: pass 1 fixed-cost freqs -> cost tables -> hash snapshot restore -> pass 2 lazy with 1+lens real costs + lookahead savings vs Huffman literals; final tables rebuilt from final tokens. * Verified Gains: make.bin -1186 (-1.3%), make.txt -4706 (-3.5%), texto_rep -2858 (-11.8%), zeros -1450 (-12.8%), binario -782, codigo -86; random/misto neutral; 9/9 PASS, Wall clean. ------------------------------------------------------------------------ [v1.7] -- 2026-09-26 (Dynamic Huffman on Literals, DEFLATE-lite) First entropy coding, new decoder, stored/fixed fallback keeps worst case safe. Added * Per-Block Canonical Huffman (literals only): freq from lazy tokens, max 15 bits, table as 256b mask + 4b lens; literals flag0 + Huff, matches unchanged; huff_flag per compressed block, fallback to fixed/stored if overhead wins. * Verified Gains: make.bin 91704 -> 89654 (-2.2%, beats lzari 91268), make.txt 140103 -> 132893 (-5.1%, beats lzari 143724 by ~10KB), codigo.c 5041 -> 4737 (-6%), binario -999, ja_comprimido -95; random/zeros/misto neutral (+/-5B). * 9/9 PASS Adler-32, gcc -Wall clean. ------------------------------------------------------------------------ [v1.6] -- 2026-09-26 (Lazy Optimal Parsing, Same Format) General 2-5% gain without Huffman/range, decoder v1.5 compatible. Added * Lazy Parsing by Real Bit Saving: greedy -> lazy, compares save = ml*9 - token_cost current vs next position; emits literal if next saves more. Same token format, XDECODER15_OK. * Verified Gains: make.bin 93525 -> 91704 (-1.95%), make.txt 142608 -> 140103 (-1.76%), codigo.c -70, binario_ls -1785 (-2.58%); random/zeros unchanged, no expansion. * vs Okumura LZARI (1989): make.bin 166400 lzari 91268 vs v1.6 91704 (+436B), make.txt 327528 lzari 143724 vs v1.6 140103 (-3621B, -2.5% win on text, pure LZSS). * No Overfit: no per-file constants, validated on 7-file general corpus + make pair. ------------------------------------------------------------------------ [v1.5] -- 2026-09-26 (The Failsafe Block Segmentation Fix) Fixes v1.4 multi-block regression while keeping the stored-block escape so incompressible data no longer expands. Fixed * 64KB Block Overflow: uint16_t block length wrapped to 0 -- now uint32_t decomp_len / raw_len. * Inter-Block Desync: removed fbr_init() after compressed blocks and ftell()-based bits_end_pos; bitstream is now continuous, byte-align only for stored blocks. * Portability: removed nested write_file_bit() function (MSVC + GCC + WSL2 clean); BitWriter / BitReader structs, no globals. * OOB Read: removed in[pos+best_len] prefetch that read past total_len; head / prev moved to int64_t. Added * Stored-Block Escape Kept: if compressed_bytes >= raw_len, emits 0 + flush + u32 raw_len + raw (~5 bytes overhead per 64KB). Verified: 12.7MB file.bin v1.3 -> 14.26MB (+12.1%), v1.5 -> 12.70MB (-0.15%). * v1.5 Block Format: 12B header (u64 total_len + Adler-32) + per block [1b type + 32b decomp_len + tokens | 0 + flush + 32b raw_len + raw]. * General Corpus 7/7 PASS: text 1.09%, code 30.5%, binary 48.6%, random 1MB 100.01% (+92B), zeros 1.08%, mixed 75.2%. ------------------------------------------------------------------------ [v1.3] -- 2026-09-26 (The Execution Speed Breakthrough) The "Coup of the Century" release, accelerating runtime execution via localized memory index mapping. Added * High-Speed Hash Chaining (Gailly-Based Optimization): Replaced the traditional brute-force backward linear history scans with a 3-byte inline lookup hash table (head and prev tracking chains). * Blistering Runtime Acceleration: Dropped execution times dramatically down to 0.01 seconds on text payloads (make.txt) and down to a virtual 0.00 seconds on dense binaries like the classic MinGW make.exe. * Execution Boundary Guard: Added a smart depth-cap to the hash-chain lookups (capped at 256 backward traversals) to guarantee tight performance predictability under heavy instruction cache stresses. ------------------------------------------------------------------------ [v1.2] -- 2026-09-25 (The Dual Sliding Window Integration) The architectural transition to hybrid dictionary modeling, optimizing localized entropy footprints. Added * Dual Sliding Window Strategy: Integrated a synchronized dual lookback radius designed by Seth bin Ghazi, his team, and Gemini AI, running concurrent sweep checks: - Short Window: 9 bits of offset (511 bytes back) for localized repetitions. - Large Window: 14 bits of offset (16,383 bytes back) for sweeping macroeconomic redundancies. * Deterministic Bit-Cost Decision Matrix: Injected an automated evaluation loop inside the compressor to weight token configurations. The engine only issues a 14-bit token if the extra byte coverage mathematically breaks even against the 5-bit offset penalty over the shorter 9-bit option. * Universal 64-Bit Memory Expansion: Rewrote internal stream offsets and file headers to natively utilize uint64_t data types, ensuring absolute runtime stability over multi-gigabyte payloads while keeping memory consumption under 16KB. * Mark Adler Verification Anchor: Introduced a rigid 12-byte structural header layout containing the calculated Adler-32 verification signature alongside the 64-bit original size block to ensure byte-perfect automated file restoration. ------------------------------------------------------------------------ [v1.1] -- 2026-09-25 (The Variable Length Baseline) The original foundational project specification breaking away from Okumura's standard 4-bit configurations. Added * 3-Bit Stream Customization: Implemented a raw Bit-Writer streaming model managed via continuous bitwise shifting, shifting entirely away from fixed byte-aligned token flags. * Short Match Mapping Matrix: Structured the core match-length window (ml = 3 to 9 bytes) to pack neatly into a 3-bit space by applying a static subtractive base offset (ml - 3), costing exactly 16 bits total. * Long Escape Match Mode: Engineered an ultra-compact escape gateway. When matches scale to greater than 10 bytes, the 3-bit length field hardcodes to its maximum boundary (111), instantly declaring an auxiliary 8-bit byte extension. * Extended Dynamic Capacity: Empowered the escape block to seamlessly store matching byte sequences stretching from 10 up to exactly 258 contiguous bytes safely without byte overflow (255 + 3 = 258). ------------------------------------------------------------------------ Lineage and Credits Developed and maintained by Seth bin Ghazi alongside the Aurora Boreal Initiative and the Gemini AI Engine. Built upon the fundamental structural breakthroughs established by Abraham Lempel, Jacob Ziv, Terry Welch, Haruhiko Okumura, Jean-loup Gailly, and Mark Adler.