zexc 1.1.0

zex native lossless compressor — CLI zexc, library zexc, files *.zex
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
//! Order-0 rANS entropy coder for sequence symbols.
//!
//! Used to pack lit_len / match_len / offset_code streams after they are
//! expanded into byte tokens (0..=255 runs). Smaller and simpler than full
//! Zstd FSE tables, same role: better than raw varints on skewed distributions.

use crate::{Error, Result};

/// Total frequency scale (must be power of two).
const SCALE_BITS: u32 = 12;
const SCALE: u32 = 1 << SCALE_BITS; // 4096
const RANS_BYTE_L: u32 = 1 << 23;

/// Normalized frequencies + cumulative for 256 symbols.
#[derive(Clone, Debug)]
pub struct FseTable {
    /// freq[s] — normalized, sum = SCALE
    pub freq: [u16; 256],
    /// cumul[s] = sum of freq[0..s]
    pub cumul: [u16; 257],
}

impl FseTable {
    /// Build from raw counts (zeros allowed). At least one symbol must appear.
    pub fn from_counts(counts: &[u32; 256]) -> Option<Self> {
        let total: u64 = counts.iter().map(|&c| u64::from(c)).sum();
        if total == 0 {
            return None;
        }

        // Largest-remainder method, each present symbol ≥ 1
        let mut raw: Vec<(usize, u64, u64)> = Vec::new(); // idx, floor, remainder
        let mut present = 0u32;
        for (i, &c) in counts.iter().enumerate() {
            if c == 0 {
                continue;
            }
            present += 1;
            let scaled = c as u64 * SCALE as u64;
            let floor = (scaled / total).max(1);
            let rem = scaled % total;
            raw.push((i, floor, rem));
        }
        if present == 0 || present > SCALE {
            return None;
        }

        let mut freq = [0u16; 256];
        let mut sum: u64 = 0;
        for &(i, floor, _) in &raw {
            freq[i] = floor as u16;
            sum += floor;
        }
        // If over-allocated (many min-1), scale down largest
        while sum > SCALE as u64 {
            let mut best = 0usize;
            let mut best_f = 0u16;
            for &(i, _, _) in &raw {
                if freq[i] > best_f {
                    best_f = freq[i];
                    best = i;
                }
            }
            if freq[best] <= 1 {
                break;
            }
            freq[best] -= 1;
            sum -= 1;
        }
        // Distribute remainder to highest remainders
        if sum < SCALE as u64 {
            let mut order = raw.clone();
            order.sort_by(|a, b| b.2.cmp(&a.2));
            let mut it = 0usize;
            while sum < SCALE as u64 && !order.is_empty() {
                let i = order[it % order.len()].0;
                freq[i] = freq[i].saturating_add(1);
                sum += 1;
                it += 1;
            }
        }

        let mut cumul = [0u16; 257];
        let mut acc = 0u32;
        for i in 0..256 {
            cumul[i] = acc as u16;
            acc += u32::from(freq[i]);
        }
        cumul[256] = SCALE as u16;
        if acc != SCALE {
            return None;
        }
        Some(Self { freq, cumul })
    }

    /// Serialize: 256 × u16 LE frequencies.
    pub fn write_to(&self, out: &mut Vec<u8>) {
        for &f in &self.freq {
            out.extend_from_slice(&f.to_le_bytes());
        }
    }

    /// Deserialize 512 bytes.
    pub fn read_from(data: &[u8]) -> Result<Self> {
        if data.len() < 512 {
            return Err(Error::Decompression("fse table truncated".into()));
        }
        let mut freq = [0u16; 256];
        let mut sum = 0u32;
        for i in 0..256 {
            freq[i] = u16::from_le_bytes([data[i * 2], data[i * 2 + 1]]);
            sum += freq[i] as u32;
        }
        if sum != SCALE {
            return Err(Error::Decompression(format!(
                "fse freq sum {sum} != {SCALE}"
            )));
        }
        let mut cumul = [0u16; 257];
        let mut acc = 0u32;
        for i in 0..256 {
            cumul[i] = acc as u16;
            acc += freq[i] as u32;
        }
        cumul[256] = SCALE as u16;
        Ok(Self { freq, cumul })
    }

    fn symbol_of_cumul(&self, c: u16) -> u8 {
        // Linear search is fine for 256; binary would be faster
        let mut lo = 0usize;
        let mut hi = 256usize;
        while lo + 1 < hi {
            let mid = (lo + hi) / 2;
            if self.cumul[mid] <= c {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        lo as u8
    }
}

/// rANS encode symbols (processed in reverse).
/// Layout: `state:u32 LE` || renorm bytes (forward order for decoder).
pub fn rans_encode(symbols: &[u8], table: &FseTable) -> Vec<u8> {
    if symbols.is_empty() {
        return Vec::new();
    }
    let mut state = RANS_BYTE_L;
    let mut renorm = Vec::with_capacity(symbols.len() + 8);

    for &sym in symbols.iter().rev() {
        let freq = table.freq[sym as usize] as u32;
        let start = table.cumul[sym as usize] as u32;
        debug_assert!(freq > 0, "missing freq for symbol {sym}");
        // Renormalize so state stays bounded
        let x_max = ((RANS_BYTE_L >> SCALE_BITS) << 8) * freq;
        while state >= x_max {
            renorm.push((state & 0xFF) as u8);
            state >>= 8;
        }
        state = ((state / freq) << SCALE_BITS) + (state % freq) + start;
    }

    let mut out = Vec::with_capacity(4 + renorm.len());
    out.extend_from_slice(&state.to_le_bytes());
    // renorm was pushed last-first; reverse for forward read
    for &b in renorm.iter().rev() {
        out.push(b);
    }
    out
}

/// rANS decode `n` symbols.
pub fn rans_decode(data: &[u8], n: usize, table: &FseTable) -> Result<Vec<u8>> {
    if n == 0 {
        return Ok(Vec::new());
    }
    if data.len() < 4 {
        return Err(Error::Decompression("rans stream too short".into()));
    }
    let mut ip = 0usize;
    let mut state = u32::from_le_bytes(data[ip..ip + 4].try_into().unwrap());
    ip += 4;

    let mut out = Vec::with_capacity(n);
    let mask = SCALE - 1;

    for _ in 0..n {
        let slot = (state & mask) as u16;
        let sym = table.symbol_of_cumul(slot);
        let freq = table.freq[sym as usize] as u32;
        let start = table.cumul[sym as usize] as u32;
        if freq == 0 {
            return Err(Error::Decompression("rans bad symbol freq 0".into()));
        }
        state = freq * (state >> SCALE_BITS) + (state & mask) - start;
        out.push(sym);
        while state < RANS_BYTE_L {
            if ip >= data.len() {
                return Err(Error::Decompression("rans truncated".into()));
            }
            state = (state << 8) | u32::from(data[ip]);
            ip += 1;
        }
    }
    Ok(out)
}

/// Expand u32 values to byte tokens: runs of 255 + remainder (like LZ4 extra).
pub fn u32s_to_tokens(vals: &[u32]) -> Vec<u8> {
    let mut t = Vec::with_capacity(vals.len() * 2);
    for &v0 in vals {
        let mut v = v0;
        while v >= 255 {
            t.push(255);
            v -= 255;
        }
        t.push(v as u8);
    }
    t
}

/// Inverse of [`u32s_to_tokens`] for `count` values.
pub fn tokens_to_u32s(tokens: &[u8], count: usize) -> Result<Vec<u32>> {
    let mut out = Vec::with_capacity(count);
    let mut i = 0usize;
    for _ in 0..count {
        let mut v = 0u32;
        loop {
            if i >= tokens.len() {
                return Err(Error::Decompression("token stream short".into()));
            }
            let b = tokens[i];
            i += 1;
            if b == 255 {
                v = v.saturating_add(255);
            } else {
                v = v.saturating_add(b as u32);
                break;
            }
        }
        out.push(v);
    }
    Ok(out)
}

/// Encode a u32 array: table + rans bitstream (len prefixed).
pub fn encode_u32_array(vals: &[u32]) -> Result<Vec<u8>> {
    let tokens = u32s_to_tokens(vals);
    let mut counts = [0u32; 256];
    for &t in &tokens {
        counts[t as usize] += 1;
    }
    let table = FseTable::from_counts(&counts)
        .ok_or_else(|| Error::Compression("empty fse counts".into()))?;
    let stream = rans_encode(&tokens, &table);
    let mut out = Vec::with_capacity(512 + 4 + stream.len());
    table.write_to(&mut out);
    out.extend_from_slice(&(tokens.len() as u32).to_le_bytes());
    out.extend_from_slice(&(stream.len() as u32).to_le_bytes());
    out.extend_from_slice(&stream);
    Ok(out)
}

/// Decode a u32 array previously written by [`encode_u32_array`].
pub fn decode_u32_array(data: &[u8], ip: &mut usize, count: usize) -> Result<Vec<u32>> {
    if *ip + 512 + 8 > data.len() {
        return Err(Error::Decompression("fse array header truncated".into()));
    }
    let table = FseTable::read_from(&data[*ip..*ip + 512])?;
    *ip += 512;
    let ntok = u32::from_le_bytes(data[*ip..*ip + 4].try_into().unwrap()) as usize;
    *ip += 4;
    let nstream = u32::from_le_bytes(data[*ip..*ip + 4].try_into().unwrap()) as usize;
    *ip += 4;
    if *ip + nstream > data.len() {
        return Err(Error::Decompression("fse stream truncated".into()));
    }
    let tokens = rans_decode(&data[*ip..*ip + nstream], ntok, &table)?;
    *ip += nstream;
    tokens_to_u32s(&tokens, count)
}

// ═════════════════════════════════════════════════════════════════════════════
// Compact FSE table — adaptive alphabet serialization
// ═════════════════════════════════════════════════════════════════════════════

/// Compact serialization version tag.
const COMPACT_TAG: u8 = 0x01;

impl FseTable {
    /// Compact serialize: only emit non-zero frequencies.
    ///
    /// Wire layout:
    /// ```text
    /// [COMPACT_TAG: u8] [n_symbols: u8] [symbol: u8, freq: u16 LE] × n_symbols
    /// ```
    /// Total: 2 + n_symbols × 3 bytes (vs 512 for full table).
    pub fn write_compact(&self, out: &mut Vec<u8>) {
        let mut n = 0u8;
        for &f in &self.freq {
            if f > 0 {
                n = n.saturating_add(1);
            }
        }
        out.push(COMPACT_TAG);
        out.push(n);
        for (sym, &f) in self.freq.iter().enumerate() {
            if f > 0 {
                out.push(sym as u8);
                out.extend_from_slice(&f.to_le_bytes());
            }
        }
    }

    /// Read a compact-format table. `data` starts at the COMPACT_TAG byte.
    pub fn read_compact(data: &[u8]) -> Result<(Self, usize)> {
        if data.len() < 2 {
            return Err(Error::Decompression("compact fse table truncated".into()));
        }
        if data[0] != COMPACT_TAG {
            return Err(Error::Decompression("bad compact fse tag".into()));
        }
        let n = data[1] as usize;
        let need = 2 + n * 3;
        if data.len() < need {
            return Err(Error::Decompression("compact fse table truncated".into()));
        }
        let mut freq = [0u16; 256];
        let mut sum = 0u32;
        for i in 0..n {
            let base = 2 + i * 3;
            let sym = data[base] as usize;
            let f = u16::from_le_bytes([data[base + 1], data[base + 2]]);
            freq[sym] = f;
            sum += f as u32;
        }
        if sum != SCALE {
            return Err(Error::Decompression(format!(
                "compact fse freq sum {sum} != {SCALE}"
            )));
        }
        let mut cumul = [0u16; 257];
        let mut acc = 0u32;
        for i in 0..256 {
            cumul[i] = acc as u16;
            acc += freq[i] as u32;
        }
        cumul[256] = SCALE as u16;
        Ok((Self { freq, cumul }, need))
    }

    /// Auto-detect and read either legacy (512-byte) or compact format.
    ///
    /// Returns (table, bytes_consumed).
    pub fn read_auto(data: &[u8]) -> Result<(Self, usize)> {
        if data.is_empty() {
            return Err(Error::Decompression("fse table empty".into()));
        }
        if data[0] == COMPACT_TAG {
            Self::read_compact(data)
        } else {
            let t = Self::read_from(data)?;
            Ok((t, 512))
        }
    }

    /// Number of distinct symbols with freq > 0.
    pub fn alphabet_size(&self) -> usize {
        self.freq.iter().filter(|&&f| f > 0).count()
    }

    /// Whether compact encoding would save space vs full 512-byte table.
    pub fn compact_saves(&self) -> bool {
        let n = self.alphabet_size();
        // Compact: 2 + n*3.  Full: 512.
        2 + n * 3 < 512
    }

    /// Write in whichever format is smaller.
    pub fn write_best(&self, out: &mut Vec<u8>) {
        if self.compact_saves() {
            self.write_compact(out);
        } else {
            self.write_to(out);
        }
    }
}

/// Encode a u32 array with adaptive (compact) FSE tables when profitable.
pub fn encode_u32_array_compact(vals: &[u32]) -> Result<Vec<u8>> {
    let tokens = u32s_to_tokens(vals);
    let mut counts = [0u32; 256];
    for &t in &tokens {
        counts[t as usize] += 1;
    }
    let table = FseTable::from_counts(&counts)
        .ok_or_else(|| Error::Compression("empty fse counts".into()))?;
    let stream = rans_encode(&tokens, &table);
    let mut out = Vec::with_capacity(128 + stream.len());
    table.write_best(&mut out);
    out.extend_from_slice(&(tokens.len() as u32).to_le_bytes());
    out.extend_from_slice(&(stream.len() as u32).to_le_bytes());
    out.extend_from_slice(&stream);
    Ok(out)
}

/// Decode a u32 array with auto-detected table format.
pub fn decode_u32_array_auto(data: &[u8], ip: &mut usize, count: usize) -> Result<Vec<u32>> {
    if *ip >= data.len() {
        return Err(Error::Decompression("fse array header truncated".into()));
    }
    let (table, consumed) = FseTable::read_auto(&data[*ip..])?;
    *ip += consumed;
    if *ip + 8 > data.len() {
        return Err(Error::Decompression("fse array lengths truncated".into()));
    }
    let ntok = u32::from_le_bytes(data[*ip..*ip + 4].try_into().unwrap()) as usize;
    *ip += 4;
    let nstream = u32::from_le_bytes(data[*ip..*ip + 4].try_into().unwrap()) as usize;
    *ip += 4;
    if *ip + nstream > data.len() {
        return Err(Error::Decompression("fse stream truncated".into()));
    }
    let tokens = rans_decode(&data[*ip..*ip + nstream], ntok, &table)?;
    *ip += nstream;
    tokens_to_u32s(&tokens, count)
}

// ═════════════════════════════════════════════════════════════════════════════
// Zstd-style code tables for LL / ML / OFF
// ═════════════════════════════════════════════════════════════════════════════

/// Literal-Length code table entry: (base_value, extra_bits).
///
/// Codes 0–15: literal values 0–15, no extra bits.
/// Codes 16–35: base + extra bits, covering values up to 131072+.
pub const LL_CODE_TABLE: [(u32, u8); 36] = [
    (0, 0), (1, 0), (2, 0), (3, 0),    // 0–3
    (4, 0), (5, 0), (6, 0), (7, 0),    // 4–7
    (8, 0), (9, 0), (10, 0), (11, 0),  // 8–11
    (12, 0), (13, 0), (14, 0), (15, 0),// 12–15
    (16, 1),   // 16–17
    (18, 1),   // 18–19
    (20, 1),   // 20–21
    (22, 1),   // 22–23
    (24, 2),   // 24–27
    (28, 2),   // 28–31
    (32, 3),   // 32–39
    (40, 3),   // 40–47
    (48, 4),   // 48–63
    (64, 6),   // 64–127
    (128, 7),  // 128–255
    (256, 8),  // 256–511
    (512, 9),  // 512–1023
    (1024, 10),// 1024–2047
    (2048, 11),// 2048–4095
    (4096, 12),// 4096–8191
    (8192, 13),// 8192–16383
    (16384, 14),// 16384–32767
    (32768, 15),// 32768–65535
    (65536, 16),// 65536–131071
];

/// Match-Length code table entry: (base_value, extra_bits).
///
/// Codes 0–31: literal values MIN_MATCH..(MIN_MATCH+31), no extra bits.
/// Codes 32–52: base + extra bits, covering very long matches.
pub const ML_CODE_TABLE: [(u32, u8); 53] = [
    (4, 0), (5, 0), (6, 0), (7, 0),    // 0–3  → match 4–7
    (8, 0), (9, 0), (10, 0), (11, 0),  // 4–7
    (12, 0), (13, 0), (14, 0), (15, 0),// 8–11
    (16, 0), (17, 0), (18, 0), (19, 0),// 12–15
    (20, 0), (21, 0), (22, 0), (23, 0),// 16–19
    (24, 0), (25, 0), (26, 0), (27, 0),// 20–23
    (28, 0), (29, 0), (30, 0), (31, 0),// 24–27
    (32, 0), (33, 0), (34, 0), (35, 0),// 28–31
    (36, 1),   // 32: 36–37
    (38, 1),   // 33: 38–39
    (40, 2),   // 34: 40–43
    (44, 2),   // 35: 44–47
    (48, 3),   // 36: 48–55
    (56, 3),   // 37: 56–63
    (64, 4),   // 38: 64–79
    (80, 4),   // 39: 80–95
    (96, 5),   // 40: 96–127
    (128, 7),  // 41: 128–255
    (256, 8),  // 42: 256–511
    (512, 9),  // 43: 512–1023
    (1024, 10),// 44: 1024–2047
    (2048, 11),// 45: 2048–4095
    (4096, 12),// 46: 4096–8191
    (8192, 13),// 47: 8192–16383
    (16384, 14),// 48: 16384–32767
    (32768, 15),// 49: 32768–65535
    (65536, 16),// 50: 65536–131071
    (131072, 17),// 51: 131072–262143
    (262144, 18),// 52: 262144–524287
];

/// Encode a literal-length value → (code, extra_value, extra_bits).
pub fn encode_ll(ll: u32) -> (u8, u32, u8) {
    // Direct codes for 0–15
    if ll <= 15 {
        return (ll as u8, 0, 0);
    }
    // Binary search through table entries 16–35
    for code in (16..36u8).rev() {
        let (base, eb) = LL_CODE_TABLE[code as usize];
        if ll >= base {
            return (code, ll - base, eb);
        }
    }
    // Fallback: largest code
    let (base, eb) = LL_CODE_TABLE[35];
    (35, ll.saturating_sub(base), eb)
}

/// Decode a literal-length code + extra bits → value.
pub fn decode_ll(code: u8, extra: u32) -> Result<u32> {
    if (code as usize) >= LL_CODE_TABLE.len() {
        return Err(Error::Decompression(format!("bad LL code {code}")));
    }
    let (base, _eb) = LL_CODE_TABLE[code as usize];
    Ok(base + extra)
}

/// Encode a match-length value → (code, extra_value, extra_bits).
pub fn encode_ml(ml: u32) -> (u8, u32, u8) {
    // Codes 0–31 map directly to match lengths 4–35
    if ml >= 4 && ml <= 35 {
        return ((ml - 4) as u8, 0, 0);
    }
    if ml < 4 {
        // Shouldn't happen (MIN_MATCH=4), treat as code 0
        return (0, 0, 0);
    }
    // Binary search through codes 32–52
    for code in (32..53u8).rev() {
        let (base, eb) = ML_CODE_TABLE[code as usize];
        if ml >= base {
            return (code, ml - base, eb);
        }
    }
    let (base, eb) = ML_CODE_TABLE[52];
    (52, ml.saturating_sub(base), eb)
}

/// Decode a match-length code + extra bits → value.
pub fn decode_ml(code: u8, extra: u32) -> Result<u32> {
    if (code as usize) >= ML_CODE_TABLE.len() {
        return Err(Error::Decompression(format!("bad ML code {code}")));
    }
    let (base, _eb) = ML_CODE_TABLE[code as usize];
    Ok(base + extra)
}

/// Encode an offset → (code, extra_value, extra_bits).
///
/// Uses log2-style coding: code = floor(log2(offset)) + 1, extra = remainder.
/// Code 0 is reserved for repeat-offset handling.
pub fn encode_off_log2(offset: u32) -> (u8, u32, u8) {
    if offset == 0 {
        return (0, 0, 0);
    }
    let bits = 32 - offset.leading_zeros(); // = floor(log2(offset)) + 1
    let code = bits as u8;
    let extra = offset - (1u32 << (bits - 1));
    let extra_bits = (bits - 1) as u8;
    (code, extra, extra_bits)
}

/// Decode an offset code + extra bits → offset value.
pub fn decode_off_log2(code: u8, extra: u32) -> Result<u32> {
    if code == 0 {
        return Ok(0);
    }
    let base = 1u32 << (code - 1);
    Ok(base + extra)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn rans_roundtrip() {
        let mut syms = Vec::new();
        for _ in 0..100 {
            syms.extend_from_slice(&[1u8, 1, 1, 2, 2, 3, 0, 0, 0, 0]);
        }
        let mut counts = [0u32; 256];
        for &s in &syms {
            counts[s as usize] += 1;
        }
        let table = FseTable::from_counts(&counts).unwrap();
        let enc = rans_encode(&syms, &table);
        let dec = rans_decode(&enc, syms.len(), &table).unwrap();
        assert_eq!(dec, syms);
    }

    #[test]
    fn u32_array_roundtrip() {
        let vals: Vec<u32> = (0..50).map(|i| i * 3 + 1).collect();
        let blob = encode_u32_array(&vals).unwrap();
        let mut ip = 0;
        let out = decode_u32_array(&blob, &mut ip, vals.len()).unwrap();
        assert_eq!(out, vals);
        assert_eq!(ip, blob.len());
    }

    #[test]
    fn compact_table_roundtrip() {
        // Small alphabet (8 symbols) — compact should save a lot
        let mut counts = [0u32; 256];
        counts[0] = 100;
        counts[1] = 200;
        counts[2] = 150;
        counts[3] = 80;
        counts[10] = 60;
        counts[20] = 40;
        counts[50] = 30;
        counts[100] = 20;
        let table = FseTable::from_counts(&counts).unwrap();
        assert!(table.compact_saves(), "8 symbols should save space");

        let mut buf = Vec::new();
        table.write_compact(&mut buf);
        assert_eq!(buf[0], COMPACT_TAG);
        assert!(buf.len() < 100, "compact must be < 100 bytes, got {}", buf.len());

        let (decoded, consumed) = FseTable::read_compact(&buf).unwrap();
        assert_eq!(consumed, buf.len());
        assert_eq!(decoded.freq, table.freq);
        assert_eq!(decoded.cumul, table.cumul);
    }

    #[test]
    fn compact_array_roundtrip() {
        let vals: Vec<u32> = (0..100).map(|i| i % 8).collect();
        let blob = encode_u32_array_compact(&vals).unwrap();
        let legacy = encode_u32_array(&vals).unwrap();
        // Compact should be smaller (8-symbol alphabet)
        assert!(
            blob.len() < legacy.len(),
            "compact {} should be < legacy {}",
            blob.len(),
            legacy.len()
        );
        let mut ip = 0;
        let out = decode_u32_array_auto(&blob, &mut ip, vals.len()).unwrap();
        assert_eq!(out, vals);
        assert_eq!(ip, blob.len());
    }

    #[test]
    fn auto_detect_reads_legacy() {
        // Legacy 512-byte format should still be readable by auto
        let vals: Vec<u32> = (0..50).map(|i| i * 3 + 1).collect();
        let blob = encode_u32_array(&vals).unwrap();
        let mut ip = 0;
        let out = decode_u32_array_auto(&blob, &mut ip, vals.len()).unwrap();
        assert_eq!(out, vals);
    }

    #[test]
    fn ll_code_roundtrip() {
        for ll in [0, 1, 15, 16, 17, 24, 32, 64, 128, 256, 1024, 65536, 131071] {
            let (code, extra, eb) = encode_ll(ll);
            let decoded = decode_ll(code, extra).unwrap();
            assert_eq!(decoded, ll, "LL roundtrip failed for {ll}: code={code} extra={extra} eb={eb}");
        }
    }

    #[test]
    fn ml_code_roundtrip() {
        for ml in [4, 5, 35, 36, 37, 40, 64, 128, 256, 1024, 65536, 262144] {
            let (code, extra, eb) = encode_ml(ml);
            let decoded = decode_ml(code, extra).unwrap();
            assert_eq!(decoded, ml, "ML roundtrip failed for {ml}: code={code} extra={extra} eb={eb}");
        }
    }

    #[test]
    fn off_log2_roundtrip() {
        for off in [1, 2, 3, 4, 7, 8, 15, 16, 255, 256, 1024, 65536, 1 << 20] {
            let (code, extra, _eb) = encode_off_log2(off);
            let decoded = decode_off_log2(code, extra).unwrap();
            assert_eq!(decoded, off, "OFF roundtrip failed for {off}");
        }
    }
}