1use std::io::{Read, Write};
2
3use serde::{Deserialize, Serialize};
4
5use crate::bitstream::{BitInputStream, BitOutputStream};
6use crate::error::ArithError;
7
8pub const DEFAULT_STATE_BITS: u32 = 32;
10
11pub const FREQ_TOTAL: u32 = 10_000_000;
13
14#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
16pub struct EncoderState {
17 pub num_state_bits: u32,
19 pub low: u64,
21 pub high: u64,
23 pub num_underflow: u64,
25}
26
27#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
29pub struct DecoderState {
30 pub num_state_bits: u32,
32 pub low: u64,
34 pub high: u64,
36 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#[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 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 #[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 pub fn finish(&mut self) -> Result<(), ArithError> {
203 self.output.write_bit(1)
204 }
205
206 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 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 pub fn bit_stream(&self) -> &BitOutputStream<W> {
238 &self.output
239 }
240
241 pub fn bit_stream_mut(&mut self) -> &mut BitOutputStream<W> {
243 &mut self.output
244 }
245
246 pub fn into_inner(mut self) -> Result<W, ArithError> {
252 self.finish()?;
253 self.output.into_inner()
254 }
255}
256
257#[derive(Debug)]
259pub struct ArithmeticDecoder<R> {
260 core: CoderCore,
261 input: BitInputStream<R>,
262 code: u64,
263}
264
265impl<R: Read> ArithmeticDecoder<R> {
266 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 #[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 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 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 pub fn bit_stream(&self) -> &BitInputStream<R> {
354 &self.input
355 }
356
357 pub fn bit_stream_mut(&mut self) -> &mut BitInputStream<R> {
359 &mut self.input
360 }
361
362 pub fn into_bit_stream(self) -> BitInputStream<R> {
364 self.input
365 }
366}
367
368#[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
379pub 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 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 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 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 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 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 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 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}