zexc 1.2.1

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
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
//! 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 alloc::vec::Vec;

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_key(|b| ::core::cmp::Reverse(b.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;

/// Tag byte written before a full 512-byte table in the `write_best` path.
///
/// `write_best` used to fall back to a bare, untagged 512-byte table
/// (`data[0]` = low byte of `freq[0]`, i.e. arbitrary input-controlled data)
/// whenever the alphabet was too large for compact encoding to pay off. When
/// that byte happened to equal `COMPACT_TAG`, `read_auto` misparsed a
/// legitimate full table as a (near-empty) compact one and corrupted decode
/// — reproducible on ordinary English text at balanced level 3. New writes
/// now always prefix the full table with this distinct tag so `read_auto`
/// never has to guess. `read_auto` still falls back to the untagged legacy
/// sniff (`FseTable::read_from`) for any other leading byte, preserving
/// decode of pre-compact archives (see `auto_detect_reads_legacy`); that
/// fallback is best-effort by construction — it was never fully unambiguous
/// — but nothing shipped by this crate writes that shape anymore.
const FULL_TAG: u8 = 0x02;

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 compact, tagged-full, or legacy untagged-full 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()));
        }
        match data[0] {
            COMPACT_TAG => Self::read_compact(data),
            FULL_TAG => {
                if data.len() < 1 + 512 {
                    return Err(Error::Decompression("fse table truncated".into()));
                }
                let t = Self::read_from(&data[1..1 + 512])?;
                Ok((t, 1 + 512))
            }
            // Legacy: bare 512-byte table with no tag (pre-compact archives).
            _ => {
                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 tagged full table.
    pub fn compact_saves(&self) -> bool {
        let n = self.alphabet_size();
        // Compact: 2 + n*3.  Tagged full: 1 + 512.
        2 + n * 3 < 1 + 512
    }

    /// Write in whichever format is smaller (always tagged — see [`read_auto`]).
    ///
    /// [`read_auto`]: FseTable::read_auto
    pub fn write_best(&self, out: &mut Vec<u8>) {
        if self.compact_saves() {
            self.write_compact(out);
        } else {
            out.push(FULL_TAG);
            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;
    // `ntok` is attacker-controlled and drives `rans_decode`'s upfront
    // `Vec::with_capacity(ntok)` — a forged huge value OOM'd the allocator
    // even though `count` (the actual expected value count) was tiny (found
    // via fuzzing). A legitimate encoder never emits more than one token per
    // value plus one continuation token per full 255-run of value weight, and
    // total value weight can never exceed the crate's absolute largest block
    // size, so this bound accepts every real encode while rejecting forgeries.
    let max_ntok = count.saturating_add(crate::utils::security::MAX_BLOCK_UNCOMPRESSED / 255 + 1);
    if ntok > max_ntok {
        return Err(Error::Decompression(format!(
            "fse token count {ntok} exceeds sane bound {max_ntok}"
        )));
    }
    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–42: base + extra bits, covering values up to 16,777,215 —
/// the maximum a single literal run can reach, since a block's total
/// literal length can never exceed the block size itself, and block_size
/// is clamped to 16 MiB (`core::encoder::CompressOptions::block_size`).
///
/// Previously stopped at code 35 = (65536, 16), covering only up to
/// 131,071. `encode_ll` still clamped anything larger into that last
/// bucket without checking the (ll - base) extra value actually fit in
/// 16 bits — for e.g. ll=155636 the extra value 90100 silently lost its
/// 17th bit when written, decoding back to a literal length 65536 bytes
/// short and desyncing every sequence after it (surfaces downstream as
/// "unused literals" or "offset > history" decompression errors on any
/// block containing a single literal run ≥ 131072 bytes — common in
/// large incompressible-ish stretches of source data). Extending the
/// table (mirroring how ML_CODE_TABLE already goes past 131072) is the
/// actual fix; matching bounds-widening belongs in the caller too, see
/// `encode_ll`.
pub const LL_CODE_TABLE: [(u32, u8); 43] = [
    (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
    (131072, 17),   // 131072–262143
    (262144, 18),   // 262144–524287
    (524288, 19),   // 524288–1048575
    (1048576, 20),  // 1048576–2097151
    (2097152, 21),  // 2097152–4194303
    (4194304, 22),  // 4194304–8388607
    (8388608, 24),  // 8388608–25165823 — 24 bits of headroom past the
                     // 16 MiB max block_size (25,165,823 > 16,777,216)
                     // so the exact-block-size boundary case can't repeat
                     // this same truncate-on-clamp bug at the new edge.
];

/// Match-Length code table entry: (base_value, extra_bits).
///
/// **Wire codes** (see [`encode_ml`] / [`decode_ml`]):
/// - Code **0** → match_len **0** (no match / trailing-literals sequence)
/// - Codes **1..=32** → match_len **4..=35** (direct, no extra bits)
/// - Codes **33..=54** → long matches; bases live in this table at index
///   `code - 1` (i.e. table rows 32..=53)
///
/// Table layout (index = old-style code before the ml=0 reservation):
/// indices 0–31 unused by the long-match path; 32–53 are long bases.
///
/// Row 53 = (524288, 20), added alongside the same fix in
/// [`LL_CODE_TABLE`] — the table previously stopped at (262144, 18),
/// covering only match lengths up to 524,287. `MAX_MATCH_LEN` is
/// 1,048,576, so any match in [524288, 1048576] hit the identical
/// truncate-on-clamp bug in `encode_ml`: the extra value silently lost
/// bits it needed, decoding to a shorter match than actually encoded.
pub const ML_CODE_TABLE: [(u32, u8); 54] = [
    (4, 0),
    (5, 0),
    (6, 0),
    (7, 0), // 0–3  → match 4–7 (legacy table rows)
    (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
    (524288, 20), // 53: 524288–1572863 (headroom past MAX_MATCH_LEN=1048576)
];

/// 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..LL_CODE_TABLE.len()
    let last = (LL_CODE_TABLE.len() - 1) as u8;
    for code in (16..=last).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[last as usize];
    (last, 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).
///
/// **Critical:** `ml == 0` is a first-class value (trailing-literals sequences).
/// Older code mapped `ml < 4` → code 0 → decoded as 4, which inflated output
/// and caused `output overflow (match)` on any block that ended with literals.
pub fn encode_ml(ml: u32) -> (u8, u32, u8) {
    // Code 0 reserved for "no match"
    if ml == 0 {
        return (0, 0, 0);
    }
    // Codes 1..=32 → match lengths 4..=35
    if (4..=35).contains(&ml) {
        return ((ml - 3) as u8, 0, 0);
    }
    if ml < 4 {
        // Invalid short match — clamp to MIN_MATCH=4 → code 1
        return (1, 0, 0);
    }
    // Long matches: table rows 32..=last, wire codes 33..=last+1
    let last_idx = (ML_CODE_TABLE.len() - 1) as u8;
    for idx in (32..=last_idx).rev() {
        let (base, eb) = ML_CODE_TABLE[idx as usize];
        if ml >= base {
            return (idx + 1, ml - base, eb);
        }
    }
    let (base, eb) = ML_CODE_TABLE[last_idx as usize];
    (last_idx + 1, ml.saturating_sub(base), eb)
}

/// Extra bits for a match-length **wire** code (must match [`encode_ml`]).
#[inline]
pub fn ml_extra_bits(code: u8) -> u8 {
    if code <= 32 {
        0
    } else {
        let idx = (code as usize).saturating_sub(1);
        if idx < ML_CODE_TABLE.len() {
            ML_CODE_TABLE[idx].1
        } else {
            0
        }
    }
}

/// Decode a match-length code + extra bits → value.
pub fn decode_ml(code: u8, extra: u32) -> Result<u32> {
    if code == 0 {
        return Ok(0);
    }
    // Direct short matches: codes 1..=32 → 4..=35
    if (1..=32).contains(&code) {
        return Ok(u32::from(code) + 3);
    }
    // Long matches: wire code 33..=53 → table index 32..=52
    let idx = (code as usize).saturating_sub(1);
    if idx >= ML_CODE_TABLE.len() {
        return Err(Error::Decompression(format!("bad ML code {code}")));
    }
    let (base, _eb) = ML_CODE_TABLE[idx];
    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 full_table_tag_no_collision_with_compact_tag() {
        // Regression for a real corruption bug: when write_best fell back to
        // an untagged 512-byte table, data[0] was the low byte of freq[0] —
        // arbitrary input-controlled data. If that byte happened to equal
        // COMPACT_TAG, read_auto misparsed a full table as a near-empty
        // compact one ("compact fse freq sum 0 != 4096"). Reproduced by
        // compressing real English text (Canterbury corpus alice29.txt) at
        // balanced level 3, where a wide code alphabet forces the full-table
        // path. Force freq[0] == 1 directly and confirm write_best/read_auto
        // round-trip it correctly now that the full path is always tagged.
        let mut counts = [0u32; 256];
        counts[0] = 1; // symbol 0 gets minimum normalized freq 1 → LSB == COMPACT_TAG
        for (i, c) in counts.iter_mut().enumerate().skip(1).take(200) {
            *c = (i as u32) + 1;
        }
        let table = FseTable::from_counts(&counts).unwrap();
        assert!(!table.compact_saves(), "test needs the full-table path");
        assert_eq!(
            table.freq[0], 1,
            "test needs freq[0] == 1 to hit the collision"
        );

        let mut buf = Vec::new();
        table.write_best(&mut buf);
        assert_eq!(buf[0], FULL_TAG, "full path must be explicitly tagged");

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

    #[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() {
        // 131072+ regression: encode_ll used to clamp any ll >= 65536 into
        // LL_CODE_TABLE's last (fixed 16-extra-bit) bucket without checking
        // (ll - base) actually fit — e.g. ll=155636 silently lost its 17th
        // bit, decoding back to 90100. Covers up through block_size's max
        // (16 MiB) since a block's total literal length is bounded by it.
        for ll in [
            0, 1, 15, 16, 17, 24, 32, 64, 128, 256, 1024, 65536, 131071, 131072, 155636, 262143,
            262144, 524287, 524288, 1048576, 8388607, 8388608, 16777215, 16777216,
        ] {
            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() {
        // 0 must round-trip — trailing-literal sequences use match_len 0.
        // 524288+ regression: same clamp-without-bounds-check bug as LL,
        // in ML_CODE_TABLE's old last bucket (262144, 18) — any match
        // length in [524288, MAX_MATCH_LEN] silently decoded shorter.
        for ml in [
            0, 4, 5, 35, 36, 37, 40, 64, 128, 256, 1024, 65536, 262144, 262145, 524287, 524288,
            700000, 1_048_576, // 1_048_576 = MAX_MATCH_LEN (utils::security)
        ] {
            let (code, extra, eb) = encode_ml(ml);
            assert_eq!(eb, ml_extra_bits(code), "extra_bits mismatch for 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}");
        }
    }
}