lz77-v3 - DUAS JANELAS + BIT IMPLICITO - v1.0.3 Fixed

[License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg) (opensource.org) [Version](https://img.shields.io/badge/version-1.0.3-blue.svg) (lz77-v3.sourceforge.io) [RFC Draft](https://img.shields.io/badge/RFC-DRAFT-green.svg)

Fast, secure LZ77 variant with dual sliding windows and implicit window-bit optimization.

Project page: https://lz77-v3.sourceforge.io
Reference implementation: lz77_v3.c v1.0.3 - Fixed search + security hardening

Benchmark - Real Test from 21/09/2026 (make.txt 327528 bytes)

From your WSL test /mnt :

--- LZ77 ORIGINAL - 1 JANELA 14b ---
Literais: 10582 | Matches: 55900
Original: 327528 bytes
Final: 172618 bytes (1380938 bits)
Taxa: 52.70% | Compressao: 47.30% menor

--- LZ77 V2 - 2 JANELAS COM FLAG 9/14b ---
Literais: 10582 | Small 9b: 2776 | Large 14b: 53124
Original: 327528 bytes
Final: 177870 bytes (1422958 bits)
Taxa: 54.31% | Compressao: 45.69% menor

--- LZ77 V3 - 2 JANELAS SEM FLAG (BIT IMPLICITO) ---
Literais: 10582 | Small 9b: 2776 | Large 14b: 53124
Original: 327528 bytes
Final: 170883 bytes (1367058 bits)
Taxa: 52.17% | Compressao: 47.83% menor
Economia bit implicito: 55900 bits vs V2

Conclusion: V3 wins!

• V1: 172618 bytes
• V2: 177870 bytes (+3252 bytes worse than V1 due to flag cost)
• V3: 170883 bytes (BEST) - 1735 bytes better than V1, 6987 bytes better than V2
• Implicit bit saves 55900 bits = 6987 bytes vs V2

What is this?

LZ77-v3 improves classic LZ77 by using two sliding windows instead of one, and saving 1 byte per match with an implicit bit.

• WINDOW_SHORT = 512 bytes - for recent, local repetitions
• WINDOW_LONG = 16384 bytes - for distant repetitions
• Implicit Bit Rule: offset <= 512 ? short window : long window - no extra flag stored!

Lineage - Past Authors

This project builds on foundational work:

• 1977 - Abraham Lempel & Jacob Ziv (Technion, Israel) - Original LZ77 algorithm. Paper: "A Universal Algorithm for Sequential Data Compression". Introduced sliding window + lookahead buffer. Basis for all LZ variants (LZSS, LZW, LZMA, DEFLATE). Without them, no ZIP, PNG, gzip.
• 1982 - James A. Storer & Thomas G. Szymanski - LZSS improvement: introduced flag bit to distinguish literal vs (offset, length) token. Our token format [flag][literal or offset+length] comes from them.
• 1984 - Terry Welch - LZW dictionary variant.
• 1993-2016 - Various - CRUSH, liblzg, LZ77JavaCoder on SourceForge kept LZ77 alive for study.
• 2026 - Seth Bin Ghazi & Meta AI - LZ77-v3 family:
• v1.0.0: Single window 16K baseline
• v1.0.1: Dual window (512 / 16384) + explicit flag (proved worse due to overhead)
• v1.0.2: Implicit bit - removed flag, infer from offset
• v1.0.3: FIXED search + security hardening (CURRENT) - early skip on first/second byte, correct heuristic needed_for_long = best+1, early exit on max match, and full decompressor validation (MAX_FILE 100MB, MAX_OUT 300MB)

We honor Lempel & Ziv as original inventors.

Wire Format (Frozen for v1.0.3 - RFC)

Token stream, no header, little-endian:
[1 byte flag]
  0x00 = literal: [1 byte value]
  0x01 = match: [2 bytes uint16 offset LE][2 bytes uint16 length LE]

Constraints: 1 <= offset <= 16384, 3 <= length <= 258, offset <= current outpos
Implicit: offset <= 512 => short window, else long window

See Docs/draft-ghazi-lz77-v3-implicit-00.txt for full RFC draft draft-ghazi-lz77-v3-implicit-00.

Build & Use

gcc lz77_v3.c -O2 -o lz77-v3 -Wall

# compress
./lz77-v3 c input.txt output.lz77

# decompress
./lz77-v3 d output.lz77 restored.txt

# check
diff input.txt restored.txt

Security

v1.0.3 is hardened for untrusted input:

• MAX_FILE_SIZE = 100MB (compressor OOM protection)
• MAX_OUT_SIZE = 300MB (decompression bomb protection)
• Validation: offset !=0, offset <= WINDOW_LONG, offset <= outpos, length in [3,258]
• Fixed heap overflow from old versions

Older versions (<1.0.3) are deprecated, do NOT use with untrusted files. See SECURITY.md.

Files for SourceForge

Upload to https://lz77-v3.sourceforge.io Files:

• lz77_v3.c - Reference implementation v1.0.3
• LICENSE / LICENSE_v1.0.3.txt - MIT License (Copyright (c) 2026 Seth Bin Ghazi & Meta AI)
• README.md - This file
• SECURITY.md - Security policy
• Docs/draft-ghazi-lz77-v3-implicit-00.txt - RFC Draft

License

MIT License - see LICENSE file. Copyright (c) 2026 Seth Bin Ghazi & Meta AI Free for commercial use, just keep copyright notice.

Changelog

• 1.0.3 Fixed - Fixed search (early skip, correct heuristic, early exit) + secure decompressor
• 1.0.2 - Implicit bit (no window flag)
• 1.0.1 - Dual window
• 1.0.0 - Initial single window

Roadmap

• v4: Hash chain (3-byte hash -> linked list) for O(1) average search, same wire format.

Maintained by Seth Bin Ghazi, Matinhos, Paraná, Brazil.