feat: long distance matching (LDM) for compression

[polaz]

Summary

Long Distance Matching enables finding matches beyond the normal window size, critical for highly repetitive data with distant patterns (log files, database dumps, backup archives).

C reference implementation (zstd_ldm.c)

Gear hash rolling

• Rolling hash: hash = (hash << 1) + ZSTD_ldm_gearTab[byte]
• Gear table: 256-entry lookup table for byte-to-hash-value mapping
• Stop mask determines split points (average every 2^hashRateLog bytes)

LDM hash table

• Bucket-based: ldmEntry_t with position + checksum
• LDM_BUCKET_SIZE_LOG = 4 (16 entries per bucket)
• Memory-efficient: only stores position + small checksum, not full content

Parameters

• ZSTD_c_enableLongDistanceMatching: on/off
• ldmHashLog: Hash table size
• ldmMinMatch: Minimum match length (default 64 bytes)
• ldmBucketSizeLog: Collision bucket size
• ldmHashRateLog: Insertion frequency

Integration

• LDM matches are merged with regular matches in sequence generation
• Auto-enables large window (128MB) for effective long-range matching

What needs to be implemented

1. Gear hash implementation — rolling hash with lookup table
2. LDM hash table — bucket-based with position + checksum
3. LDM match finding — search LDM table, verify matches, extend
4. Sequence merging — combine LDM matches with regular matches
5. Parameter API — enable/configure LDM via compression parameters
6. Window extension — auto-increase window when LDM enabled

Acceptance criteria

• LDM can be enabled via parameter
• Finds matches beyond normal window distance
• Decompressible by C zstd
• Compression ratio improves on highly repetitive large data
• Configurable parameters

Time estimate

3d