Skip to main content

tufazip_arith/
coder.rs

1use std::io::{Read, Write};
2
3use serde::{Deserialize, Serialize};
4
5use crate::bitstream::{BitInputStream, BitOutputStream};
6use crate::error::ArithError;
7
8/// Default state bit width used by `tufazip`.
9pub const DEFAULT_STATE_BITS: u32 = 32;
10
11/// Frequency-table resolution used when quantizing softmax probabilities.
12pub const FREQ_TOTAL: u32 = 10_000_000;
13
14/// Exact serializable state of an [`ArithmeticEncoder`].
15#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
16pub struct EncoderState {
17    /// Bit width of the coder state registers.
18    pub num_state_bits: u32,
19    /// Lower bound of the active coding interval.
20    pub low: u64,
21    /// Upper bound (inclusive) of the active coding interval.
22    pub high: u64,
23    /// Number of pending underflow bits.
24    pub num_underflow: u64,
25}
26
27/// Exact serializable state of an [`ArithmeticDecoder`].
28#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
29pub struct DecoderState {
30    /// Bit width of the coder state registers.
31    pub num_state_bits: u32,
32    /// Lower bound of the active coding interval.
33    pub low: u64,
34    /// Upper bound (inclusive) of the active coding interval.
35    pub high: u64,
36    /// Current buffered code word.
37    pub code: u64,
38}
39
40#[derive(Debug, Clone, Copy)]
41struct CoderCore {
42    num_state_bits: u32,
43    half_range: u64,
44    quarter_range: u64,
45    maximum_total: u64,
46    state_mask: u64,
47    low: u64,
48    high: u64,
49}
50
51impl CoderCore {
52    fn new(num_state_bits: u32) -> Result<Self, ArithError> {
53        if !(1..=62).contains(&num_state_bits) {
54            return Err(ArithError::InvalidStateBits(num_state_bits));
55        }
56        let full_range = 1u64 << num_state_bits;
57        let half_range = full_range >> 1;
58        let quarter_range = half_range >> 1;
59        let minimum_range = quarter_range + 2;
60        let state_mask = full_range - 1;
61        Ok(Self {
62            num_state_bits,
63            half_range,
64            quarter_range,
65            maximum_total: minimum_range,
66            state_mask,
67            low: 0,
68            high: state_mask,
69        })
70    }
71
72    #[inline]
73    fn validate_table(&self, freqs: &[u32]) -> Result<u64, ArithError> {
74        let total = *freqs.last().ok_or(ArithError::EmptyFreqTable)?;
75        let total_u64 = u64::from(total);
76        if total_u64 == 0 || total_u64 > self.maximum_total {
77            return Err(ArithError::TotalTooLarge {
78                total: total_u64,
79                max: self.maximum_total,
80            });
81        }
82        Ok(total_u64)
83    }
84
85    #[inline]
86    fn update<F>(&mut self, freqs: &[u32], symbol: usize, mut on_event: F) -> Result<(), ArithError>
87    where
88        F: FnMut(UpdateEvent) -> Result<(), ArithError>,
89    {
90        if symbol >= freqs.len() {
91            return Err(ArithError::InvalidSymbol {
92                symbol,
93                len: freqs.len(),
94            });
95        }
96        let total = self.validate_table(freqs)?;
97        let sym_low = if symbol > 0 { freqs[symbol - 1] } else { 0 };
98        let sym_high = freqs[symbol];
99        if sym_low >= sym_high {
100            return Err(ArithError::ZeroFrequencySymbol(symbol));
101        }
102
103        let (new_low, new_high) = if self.num_state_bits <= 32 {
104            let range = self.high - self.low + 1;
105            let new_low = self.low + (u64::from(sym_low) * range) / total;
106            let new_high = self.low + (u64::from(sym_high) * range) / total - 1;
107            (new_low, new_high)
108        } else {
109            let low_u128 = u128::from(self.low);
110            let range_u128 = u128::from(self.high - self.low + 1);
111            let total_u128 = u128::from(total);
112            let new_low = (low_u128 + (u128::from(sym_low) * range_u128) / total_u128) as u64;
113            let new_high = (low_u128 + (u128::from(sym_high) * range_u128) / total_u128 - 1) as u64;
114            (new_low, new_high)
115        };
116        self.low = new_low;
117        self.high = new_high;
118
119        while ((self.low ^ self.high) & self.half_range) == 0 {
120            on_event(UpdateEvent::Shift(self.low))?;
121            self.low = (self.low << 1) & self.state_mask;
122            self.high = ((self.high << 1) & self.state_mask) | 1;
123        }
124
125        while (self.low & !self.high & self.quarter_range) != 0 {
126            on_event(UpdateEvent::Underflow)?;
127            self.low = ((self.low << 1) ^ self.half_range) & self.state_mask;
128            self.high =
129                (((self.high ^ self.half_range) << 1) | self.half_range | 1) & self.state_mask;
130        }
131
132        Ok(())
133    }
134}
135
136#[derive(Debug, Clone, Copy)]
137enum UpdateEvent {
138    Shift(u64),
139    Underflow,
140}
141
142/// Range arithmetic encoder writing big-endian bits to a [`BitOutputStream`].
143#[derive(Debug)]
144pub struct ArithmeticEncoder<W> {
145    core: CoderCore,
146    output: BitOutputStream<W>,
147    num_underflow: u64,
148}
149
150impl<W: Write> ArithmeticEncoder<W> {
151    /// Constructs an encoder using `num_state_bits` (typically [`DEFAULT_STATE_BITS`]).
152    ///
153    /// # Errors
154    ///
155    /// Returns [`ArithError::InvalidStateBits`] if `num_state_bits` is not in `1..=62`.
156    pub fn new(num_state_bits: u32, output: BitOutputStream<W>) -> Result<Self, ArithError> {
157        Ok(Self {
158            core: CoderCore::new(num_state_bits)?,
159            output,
160            num_underflow: 0,
161        })
162    }
163
164    /// Encodes `symbol` using the cumulative frequency table `freqs`.
165    ///
166    /// `freqs[i]` must hold the inclusive cumulative frequency of symbols `0..=i`,
167    /// with `freqs.last()` equal to the total frequency mass (`<= minimum_range`).
168    ///
169    /// # Errors
170    ///
171    /// Returns [`ArithError`] if `freqs` or `symbol` is invalid or writing fails.
172    #[inline]
173    pub fn write(&mut self, freqs: &[u32], symbol: usize) -> Result<(), ArithError> {
174        let num_state_bits = self.core.num_state_bits;
175        let output = &mut self.output;
176        let num_underflow = &mut self.num_underflow;
177        self.core.update(freqs, symbol, |event| match event {
178            UpdateEvent::Shift(low) => {
179                let bit = ((low >> (num_state_bits - 1)) & 1) as u8;
180                output.write_bit(bit)?;
181                for _ in 0..*num_underflow {
182                    output.write_bit(bit ^ 1)?;
183                }
184                *num_underflow = 0;
185                Ok(())
186            }
187            UpdateEvent::Underflow => {
188                *num_underflow += 1;
189                Ok(())
190            }
191        })
192    }
193
194    /// Terminates the arithmetic stream by emitting the final disambiguating bit.
195    ///
196    /// Call [`BitOutputStream::finish_padding`] on [`Self::bit_stream_mut`] afterwards to pad
197    /// the final partial byte, or call [`Self::into_inner`] directly instead of calling `finish`.
198    ///
199    /// # Errors
200    ///
201    /// Returns [`ArithError::Io`] if writing to the underlying bit stream fails.
202    pub fn finish(&mut self) -> Result<(), ArithError> {
203        self.output.write_bit(1)
204    }
205
206    /// Captures the minimal exact encoder state for checkpointing.
207    pub fn state(&self) -> EncoderState {
208        EncoderState {
209            num_state_bits: self.core.num_state_bits,
210            low: self.core.low,
211            high: self.core.high,
212            num_underflow: self.num_underflow,
213        }
214    }
215
216    /// Restores a previously captured [`EncoderState`].
217    ///
218    /// Note that the underlying [`BitOutputStream`] must also be restored separately.
219    ///
220    /// # Errors
221    ///
222    /// Returns [`ArithError::StateWidthMismatch`] if `num_state_bits` differs.
223    pub fn restore_state(&mut self, state: EncoderState) -> Result<(), ArithError> {
224        if state.num_state_bits != self.core.num_state_bits {
225            return Err(ArithError::StateWidthMismatch {
226                expected: self.core.num_state_bits,
227                found: state.num_state_bits,
228            });
229        }
230        self.core.low = state.low;
231        self.core.high = state.high;
232        self.num_underflow = state.num_underflow;
233        Ok(())
234    }
235
236    /// Returns a shared reference to the underlying [`BitOutputStream`].
237    pub fn bit_stream(&self) -> &BitOutputStream<W> {
238        &self.output
239    }
240
241    /// Returns a mutable reference to the underlying [`BitOutputStream`].
242    pub fn bit_stream_mut(&mut self) -> &mut BitOutputStream<W> {
243        &mut self.output
244    }
245
246    /// Finishes arithmetic coding, pads the bit stream, and returns the underlying writer.
247    ///
248    /// # Errors
249    ///
250    /// Returns [`ArithError`] if finishing or flushing fails.
251    pub fn into_inner(mut self) -> Result<W, ArithError> {
252        self.finish()?;
253        self.output.into_inner()
254    }
255}
256
257/// Range arithmetic decoder reading big-endian bits from a [`BitInputStream`].
258#[derive(Debug)]
259pub struct ArithmeticDecoder<R> {
260    core: CoderCore,
261    input: BitInputStream<R>,
262    code: u64,
263}
264
265impl<R: Read> ArithmeticDecoder<R> {
266    /// Constructs a decoder using `num_state_bits` and reads the initial code word.
267    ///
268    /// # Errors
269    ///
270    /// Returns [`ArithError::InvalidStateBits`] or [`ArithError::Io`] on initial reads.
271    pub fn new(num_state_bits: u32, mut input: BitInputStream<R>) -> Result<Self, ArithError> {
272        let core = CoderCore::new(num_state_bits)?;
273        let mut code = 0u64;
274        for _ in 0..num_state_bits {
275            let bit = u64::from(input.read_bit()?.unwrap_or(0));
276            code = (code << 1) | bit;
277        }
278        Ok(Self { core, input, code })
279    }
280
281    /// Decodes the next symbol using the cumulative frequency table `freqs`.
282    ///
283    /// # Errors
284    ///
285    /// Returns [`ArithError`] if `freqs` is invalid or reading from the bit stream fails.
286    #[inline]
287    pub fn read(&mut self, freqs: &[u32]) -> Result<usize, ArithError> {
288        let total = self.core.validate_table(freqs)?;
289        let value = if self.core.num_state_bits <= 32 {
290            let range = self.core.high - self.core.low + 1;
291            let offset = self.code - self.core.low;
292            ((offset + 1) * total - 1) / range
293        } else {
294            let range = u128::from(self.core.high - self.core.low + 1);
295            let offset = u128::from(self.code - self.core.low);
296            (((offset + 1) * u128::from(total) - 1) / range) as u64
297        };
298
299        let value_u32 = value as u32;
300        let symbol = freqs.partition_point(|&cum| cum <= value_u32);
301
302        let half_range = self.core.half_range;
303        let state_mask = self.core.state_mask;
304        let input = &mut self.input;
305        let code = &mut self.code;
306        self.core.update(freqs, symbol, |event| {
307            let bit = u64::from(input.read_bit()?.unwrap_or(0));
308            match event {
309                UpdateEvent::Shift(_) => {
310                    *code = ((*code << 1) & state_mask) | bit;
311                }
312                UpdateEvent::Underflow => {
313                    *code = (*code & half_range) | ((*code << 1) & (state_mask >> 1)) | bit;
314                }
315            }
316            Ok(())
317        })?;
318
319        Ok(symbol)
320    }
321
322    /// Captures the minimal exact decoder state for checkpointing.
323    pub fn state(&self) -> DecoderState {
324        DecoderState {
325            num_state_bits: self.core.num_state_bits,
326            low: self.core.low,
327            high: self.core.high,
328            code: self.code,
329        }
330    }
331
332    /// Restores a previously captured [`DecoderState`].
333    ///
334    /// Note that the underlying [`BitInputStream`] must also be restored separately.
335    ///
336    /// # Errors
337    ///
338    /// Returns [`ArithError::StateWidthMismatch`] if `num_state_bits` differs.
339    pub fn restore_state(&mut self, state: DecoderState) -> Result<(), ArithError> {
340        if state.num_state_bits != self.core.num_state_bits {
341            return Err(ArithError::StateWidthMismatch {
342                expected: self.core.num_state_bits,
343                found: state.num_state_bits,
344            });
345        }
346        self.core.low = state.low;
347        self.core.high = state.high;
348        self.code = state.code;
349        Ok(())
350    }
351
352    /// Returns a shared reference to the underlying [`BitInputStream`].
353    pub fn bit_stream(&self) -> &BitInputStream<R> {
354        &self.input
355    }
356
357    /// Returns a mutable reference to the underlying [`BitInputStream`].
358    pub fn bit_stream_mut(&mut self) -> &mut BitInputStream<R> {
359        &mut self.input
360    }
361
362    /// Consumes this decoder and returns the underlying [`BitInputStream`].
363    pub fn into_bit_stream(self) -> BitInputStream<R> {
364        self.input
365    }
366}
367
368/// Converts raw logits into a cumulative integer frequency table matching `nn.py`.
369///
370/// Computes `softmax(logits)`, scales by [`FREQ_TOTAL`], rounds ties to even,
371/// clamps each symbol frequency to at least `1`, and returns the cumulative sum.
372#[must_use]
373pub fn make_freq_table(logits: &[f32]) -> Vec<u32> {
374    let mut out = Vec::with_capacity(logits.len());
375    make_freq_table_into(logits, &mut out);
376    out
377}
378
379/// Converts raw logits into a cumulative integer frequency table, reusing `out`.
380pub fn make_freq_table_into(logits: &[f32], out: &mut Vec<u32>) {
381    out.clear();
382    if logits.is_empty() {
383        return;
384    }
385    let max_logit = logits.iter().copied().fold(f32::NEG_INFINITY, f32::max);
386    let mut sum_exp = 0.0f32;
387    out.reserve(logits.len());
388    // Pass 1: store positive exp(x - max_logit) bit patterns directly in `out`
389    // so we avoid computing `f32::exp` twice with zero extra allocations.
390    for &x in logits {
391        let e = (x - max_logit).exp();
392        sum_exp += e;
393        out.push(e.to_bits());
394    }
395    let inv_sum = 1.0f32 / sum_exp;
396    let scale = FREQ_TOTAL as f32;
397    let mut cum = 0u32;
398    for slot in out.iter_mut() {
399        let prob = f32::from_bits(*slot) * inv_sum;
400        let rounded = (prob * scale).round_ties_even();
401        let freq = (rounded as i64).max(1) as u32;
402        cum = cum.saturating_add(freq);
403        *slot = cum;
404    }
405}
406
407#[cfg(test)]
408mod tests {
409    use std::io::Cursor;
410
411    use super::*;
412
413    #[test]
414    fn roundtrip_uniform_and_skewed_tables() {
415        let tables: &[&[u32]] = &[
416            &[1, 2, 3, 4],
417            &[999_997, 999_998, 999_999, 1_000_000],
418            &[1, 500_000, 500_001, 1_000_000],
419            &[10_000_000],
420        ];
421        let symbols = [0usize, 3, 0, 2, 1, 0, 0, 1, 2, 3, 0, 0];
422
423        let mut encoded = Vec::new();
424        {
425            let bit_out = BitOutputStream::new(&mut encoded);
426            let mut enc = ArithmeticEncoder::new(DEFAULT_STATE_BITS, bit_out).unwrap();
427            for (i, &sym) in symbols.iter().enumerate() {
428                let table = tables[i % (tables.len() - 1)];
429                enc.write(table, sym).unwrap();
430            }
431            enc.write(tables[3], 0).unwrap();
432            enc.finish().unwrap();
433            enc.bit_stream_mut().finish_padding().unwrap();
434        }
435
436        let bit_in = BitInputStream::new(Cursor::new(&encoded));
437        let mut dec = ArithmeticDecoder::new(DEFAULT_STATE_BITS, bit_in).unwrap();
438        for (i, &want) in symbols.iter().enumerate() {
439            let table = tables[i % (tables.len() - 1)];
440            let got = dec.read(table).unwrap();
441            assert_eq!(got, want, "mismatch at symbol index {i}");
442        }
443        assert_eq!(dec.read(tables[3]).unwrap(), 0);
444    }
445
446    #[test]
447    fn roundtrip_make_freq_table_4097_vocab() {
448        let mut logits = vec![-12.0f32; 4097];
449        logits[0] = 4.5;
450        logits[42] = 6.25;
451        logits[4096] = 2.0;
452        let freqs = make_freq_table(&logits);
453        assert_eq!(freqs.len(), 4097);
454        assert!(*freqs.last().unwrap() >= FREQ_TOTAL);
455
456        let symbols = [42usize, 0, 4096, 1234, 42, 42, 999, 1, 4095];
457        let mut buf = Vec::new();
458        {
459            let mut enc =
460                ArithmeticEncoder::new(DEFAULT_STATE_BITS, BitOutputStream::new(&mut buf)).unwrap();
461            for &sym in &symbols {
462                enc.write(&freqs, sym).unwrap();
463            }
464            enc.into_inner().unwrap();
465        }
466
467        let mut dec =
468            ArithmeticDecoder::new(DEFAULT_STATE_BITS, BitInputStream::new(Cursor::new(&buf)))
469                .unwrap();
470        let decoded: Vec<usize> = (0..symbols.len())
471            .map(|_| dec.read(&freqs).unwrap())
472            .collect();
473        assert_eq!(decoded, symbols);
474    }
475
476    #[test]
477    fn checkpoint_resume_encoder_and_decoder_bit_exact() {
478        let mut logits_a = vec![-3.0f32; 64];
479        logits_a[5] = 3.0;
480        logits_a[17] = 1.5;
481        let mut logits_b = vec![-4.0f32; 64];
482        logits_b[63] = 2.5;
483        logits_b[0] = 2.2;
484        let table_a = make_freq_table(&logits_a);
485        let table_b = make_freq_table(&logits_b);
486
487        let stream_syms: Vec<usize> = (0..120).map(|i| (i * 19 + 5) % 64).collect();
488        let split = 57;
489
490        // Uninterrupted encode
491        let mut full_bytes = Vec::new();
492        {
493            let mut enc =
494                ArithmeticEncoder::new(DEFAULT_STATE_BITS, BitOutputStream::new(&mut full_bytes))
495                    .unwrap();
496            for (i, &sym) in stream_syms.iter().enumerate() {
497                let tbl = if i % 2 == 0 { &table_a } else { &table_b };
498                enc.write(tbl, sym).unwrap();
499            }
500            enc.into_inner().unwrap();
501        }
502
503        // Split encode with state snapshot + resume on temporary file
504        let tmp = tempfile::NamedTempFile::new().unwrap();
505        let (enc_state, bit_out_state) = {
506            let file = tmp.reopen().unwrap();
507            let mut enc =
508                ArithmeticEncoder::new(DEFAULT_STATE_BITS, BitOutputStream::new(file)).unwrap();
509            for (i, &sym) in stream_syms[..split].iter().enumerate() {
510                let tbl = if i % 2 == 0 { &table_a } else { &table_b };
511                enc.write(tbl, sym).unwrap();
512            }
513            let es = enc.state();
514            let bs = enc.bit_stream_mut().state().unwrap();
515            // Simulate extra trailing bytes written before crash
516            enc.write(&table_a, 11).unwrap();
517            enc.write(&table_b, 22).unwrap();
518            enc.bit_stream_mut().flush().unwrap();
519            (es, bs)
520        };
521
522        {
523            let file = std::fs::OpenOptions::new()
524                .read(true)
525                .write(true)
526                .open(tmp.path())
527                .unwrap();
528            let mut bit_out = BitOutputStream::new(file);
529            bit_out.restore_file_state(bit_out_state).unwrap();
530            let mut enc = ArithmeticEncoder::new(DEFAULT_STATE_BITS, bit_out).unwrap();
531            enc.restore_state(enc_state).unwrap();
532            for (offset, &sym) in stream_syms[split..].iter().enumerate() {
533                let i = split + offset;
534                let tbl = if i % 2 == 0 { &table_a } else { &table_b };
535                enc.write(tbl, sym).unwrap();
536            }
537            enc.into_inner().unwrap();
538        }
539
540        let resumed_bytes = std::fs::read(tmp.path()).unwrap();
541        assert_eq!(resumed_bytes, full_bytes);
542
543        // Split decode with state snapshot + resume
544        let mut dec = ArithmeticDecoder::new(
545            DEFAULT_STATE_BITS,
546            BitInputStream::new(Cursor::new(&full_bytes)),
547        )
548        .unwrap();
549        let mut decoded = Vec::new();
550        for i in 0..split {
551            let tbl = if i % 2 == 0 { &table_a } else { &table_b };
552            decoded.push(dec.read(tbl).unwrap());
553        }
554        let dec_state = dec.state();
555        let bit_in_state = dec.bit_stream_mut().state().unwrap();
556
557        let mut dec2 = ArithmeticDecoder::new(
558            DEFAULT_STATE_BITS,
559            BitInputStream::new(Cursor::new(&full_bytes)),
560        )
561        .unwrap();
562        dec2.bit_stream_mut().restore_state(bit_in_state).unwrap();
563        dec2.restore_state(dec_state).unwrap();
564        for i in split..stream_syms.len() {
565            let tbl = if i % 2 == 0 { &table_a } else { &table_b };
566            decoded.push(dec2.read(tbl).unwrap());
567        }
568        assert_eq!(decoded, stream_syms);
569    }
570
571    #[test]
572    fn error_handling_edges() {
573        assert!(matches!(
574            CoderCore::new(0),
575            Err(ArithError::InvalidStateBits(0))
576        ));
577        assert!(matches!(
578            CoderCore::new(63),
579            Err(ArithError::InvalidStateBits(63))
580        ));
581
582        let mut buf = Vec::new();
583        let mut enc =
584            ArithmeticEncoder::new(DEFAULT_STATE_BITS, BitOutputStream::new(&mut buf)).unwrap();
585        assert!(matches!(
586            enc.write(&[], 0),
587            Err(ArithError::InvalidSymbol { .. })
588        ));
589        assert!(matches!(
590            enc.write(&[10, 10], 1),
591            Err(ArithError::ZeroFrequencySymbol(1))
592        ));
593        assert!(matches!(
594            enc.bit_stream_mut().write_bit(2),
595            Err(ArithError::InvalidBit(2))
596        ));
597    }
598
599    #[test]
600    fn single_pass_freq_table_matches_two_pass_reference_bit_for_bit() {
601        fn ref_two_pass(logits: &[f32]) -> Vec<u32> {
602            if logits.is_empty() {
603                return Vec::new();
604            }
605            let max_logit = logits.iter().copied().fold(f32::NEG_INFINITY, f32::max);
606            let mut sum_exp = 0.0f32;
607            for &x in logits {
608                sum_exp += (x - max_logit).exp();
609            }
610            let inv_sum = 1.0f32 / sum_exp;
611            let scale = FREQ_TOTAL as f32;
612            let mut cum = 0u32;
613            let mut out = Vec::with_capacity(logits.len());
614            for &x in logits {
615                let prob = (x - max_logit).exp() * inv_sum;
616                let rounded = (prob * scale).round_ties_even();
617                let freq = (rounded as i64).max(1) as u32;
618                cum = cum.saturating_add(freq);
619                out.push(cum);
620            }
621            out
622        }
623
624        let cases: &[&[f32]] = &[&[], &[0.0], &[-100.0, 0.0, 100.0, -50.0, 99.5], &[1.0; 128]];
625        for case in cases {
626            assert_eq!(make_freq_table(case), ref_two_pass(case));
627        }
628
629        let mut large = vec![-12.0f32; 4097];
630        for (i, slot) in large.iter_mut().enumerate() {
631            *slot = -6.0 + ((i * 37) % 101) as f32 * 0.11;
632        }
633        large[42] = 9.75;
634        let mut reused = Vec::with_capacity(4097);
635        make_freq_table_into(&large, &mut reused);
636        assert_eq!(reused, ref_two_pass(&large));
637    }
638
639    #[test]
640    fn u64_fast_path_matches_32bit_and_wide_state_roundtrip() {
641        // Test 32-bit u64 fast path with FREQ_TOTAL ~10M logits and sparse zero-frequency CDFs,
642        // plus 40-bit u128 fallback path.
643        let mut logits = vec![-12.0f32; 512];
644        logits[0] = 6.0;
645        logits[255] = 4.5;
646        logits[511] = 3.0;
647        let dense_cdf = make_freq_table(&logits);
648        // Construct a sparse CDF containing zero-frequency intervals between active symbols.
649        let sparse_cdf = vec![10, 10, 10, 1_000_000, 1_000_000, FREQ_TOTAL, FREQ_TOTAL];
650
651        let dense_syms = [0usize, 1, 255, 511, 0, 510, 511, 42, 255, 0];
652        let sparse_syms = [0usize, 3, 5, 0, 5, 3];
653
654        for bits in [DEFAULT_STATE_BITS, 40u32] {
655            let mut bytes = Vec::new();
656            let mut enc = ArithmeticEncoder::new(bits, BitOutputStream::new(&mut bytes)).unwrap();
657            for &s in &dense_syms {
658                enc.write(&dense_cdf, s).unwrap();
659            }
660            for &s in &sparse_syms {
661                enc.write(&sparse_cdf, s).unwrap();
662            }
663            let bytes = enc.into_inner().unwrap();
664
665            let mut dec =
666                ArithmeticDecoder::new(bits, BitInputStream::new(Cursor::new(&bytes))).unwrap();
667            let mut got_dense = Vec::with_capacity(dense_syms.len());
668            for _ in 0..dense_syms.len() {
669                got_dense.push(dec.read(&dense_cdf).unwrap());
670            }
671            let mut got_sparse = Vec::with_capacity(sparse_syms.len());
672            for _ in 0..sparse_syms.len() {
673                got_sparse.push(dec.read(&sparse_cdf).unwrap());
674            }
675            assert_eq!(got_dense, dense_syms, "bits={bits}");
676            assert_eq!(got_sparse, sparse_syms, "bits={bits}");
677        }
678    }
679}