use super::TokenSlice;
use super::histogram::Histogram;
#[cfg(test)]
use super::token::Token;
use crate::bit_writer::BitWriter;
use crate::entropy::dlog2::{f_fmla, f_log2};
use crate::entropy::fast_div_u16::FastDivU16;
#[cfg(not(target_arch = "aarch64"))]
use crate::fast_divide::DividerU64;
use std::sync::OnceLock;
pub(crate) const ANS_LOG_TAB_SIZE: u32 = 12;
pub(crate) const ANS_TAB_SIZE: u32 = 1 << ANS_LOG_TAB_SIZE; pub(crate) const ANS_SIGNATURE: u32 = 0x13;
#[derive(Clone)]
pub(crate) struct AnsHistogram {
pub(crate) freqs: Vec<u16>,
method: u8,
omit_pos: u8,
cost: f64,
}
const LOG_ALPHA_SIZE: usize = 7;
const TABLE_ENTRIES: usize = 1 << LOG_ALPHA_SIZE; const LOG_ENTRY_SIZE: usize = ANS_LOG_TAB_SIZE as usize - LOG_ALPHA_SIZE; const ENTRY_SIZE: u32 = 1 << LOG_ENTRY_SIZE; const ENTRY_SIZE_M1: u32 = ENTRY_SIZE - 1;
pub(crate) fn normalize_counts(counts: &[u32], freqs: &mut Vec<u16>) {
let n = counts.len();
if freqs.len() != n {
freqs.resize(n, 0);
}
normalize_counts_into(counts, freqs);
}
#[inline]
fn first_maximum(freqs: &[u16]) -> (usize, u16) {
let maximum = freqs.iter().copied().max().unwrap_or(0);
let position = freqs.iter().position(|&freq| freq == maximum).unwrap_or(0);
(position, maximum)
}
pub(crate) fn normalize_counts_into(counts: &[u32], freqs: &mut [u16]) {
normalize_counts_first_maximum(counts, freqs);
}
pub(crate) fn normalize_counts_first_maximum(counts: &[u32], freqs: &mut [u16]) -> usize {
debug_assert_eq!(counts.len(), freqs.len());
freqs.fill(0);
let total: u64 = counts.iter().map(|&c| c as u64).sum();
if total == 0 {
return 0;
}
#[cfg(target_arch = "aarch64")]
let divider = total;
#[cfg(not(target_arch = "aarch64"))]
let divider = DividerU64::new(total);
let table = ANS_TAB_SIZE as i64;
let mut sum: i64 = 0;
for (freq, &count) in freqs.iter_mut().zip(counts.iter()) {
if count == 0 {
continue;
}
let mut f = (count as u64 * ANS_TAB_SIZE as u64 / divider) as i64;
if f < 1 {
f = 1;
}
*freq = f as u16;
sum += f;
}
while sum != table {
let (mi, mf) = first_maximum(freqs);
if sum < table {
freqs[mi] += (table - sum) as u16;
return mi;
} else if mf > 1 {
freqs[mi] -= 1;
sum -= 1;
} else {
break;
}
}
first_maximum(freqs).0
}
pub(crate) fn populated_alphabet_size(counts: &[u32]) -> usize {
let (chunks, tail) = counts.as_chunks::<8>();
if let Some(i) = tail.iter().rposition(|&c| c != 0) {
return chunks.len() * 8 + i + 1;
}
for (k, chunk) in chunks.iter().enumerate().rev() {
if chunk.iter().fold(0u32, |acc, &c| acc | c) != 0 {
let i = chunk.iter().rposition(|&c| c != 0).unwrap_or(0);
return k * 8 + i + 1;
}
}
0
}
#[derive(Clone, Copy)]
struct AllowedCount {
count: u16,
step_log: u8,
delta_log: f64,
}
struct AllowedCounts {
descending: Vec<AllowedCount>,
index: Box<[u16; ANS_TAB_SIZE as usize]>,
}
static ALLOWED_COUNTS: OnceLock<[AllowedCounts; ANS_LOG_TAB_SIZE as usize]> = OnceLock::new();
static COUNT_LOG2: OnceLock<Box<[f64]>> = OnceLock::new();
fn count_log2() -> &'static [f64] {
COUNT_LOG2.get_or_init(|| {
(0..=ANS_TAB_SIZE)
.map(|v| if v == 0 { 0.0 } else { f_log2(v as f64) })
.collect::<Vec<_>>()
.into_boxed_slice()
})
}
fn allowed_counts() -> &'static [AllowedCounts; ANS_LOG_TAB_SIZE as usize] {
ALLOWED_COUNTS.get_or_init(|| {
let logs = count_log2();
core::array::from_fn(|shift| {
let mut descending = Vec::with_capacity(ANS_TAB_SIZE as usize);
let mut index = Box::new([0u16; ANS_TAB_SIZE as usize]);
let mut last = u16::MAX;
for i in (0..ANS_TAB_SIZE as u16).rev() {
let step_log = if i == 0 {
0
} else {
let log = floor_log2(i as u32) as i32;
(log - get_pop_count_precision(log, shift as i32)) as u8
};
let current = i & !((1u16 << step_log) - 1);
if current == last {
continue;
}
last = current;
let slot = descending.len();
index[current as usize] = slot as u16;
if current == 0 {
descending.push(AllowedCount {
count: 0,
step_log: 0,
delta_log: f64::INFINITY,
});
} else {
let previous = descending.last().map_or(current, |v| v.count);
descending.push(AllowedCount {
count: current,
step_log: if slot == 0 {
0
} else {
floor_log2((previous - current) as u32) as u8
},
delta_log: if slot == 0 {
0.0
} else {
logs[previous as usize] - logs[current as usize]
},
});
}
}
AllowedCounts { descending, index }
})
})
}
#[derive(Clone, Copy)]
struct AdjustableBin {
source_count: u32,
count_index: usize,
bin_index: usize,
}
fn rebalance_counts(counts: &[u32], alphabet_size: usize, shift: usize) -> Option<AnsHistogram> {
let total: u64 = counts[..alphabet_size].iter().map(|&v| v as u64).sum();
if total == 0 {
return Some(AnsHistogram {
freqs: vec![0; counts.len()],
method: (shift + 1) as u8,
omit_pos: 0,
cost: 0.0,
});
}
let allowed = &allowed_counts()[shift];
let logs = count_log2();
let mut freqs = vec![0u16; counts.len()];
let norm = ANS_TAB_SIZE as f64 / total as f64;
let mut omit_pos = 0usize;
let mut max_source = 0u32;
let mut rest = ANS_TAB_SIZE as i32;
let mut bins = Vec::with_capacity(alphabet_size);
for i in 0..alphabet_size {
let source = counts[i];
if source > max_source {
max_source = source;
omit_pos = i;
}
let target = source as f64 * norm;
let mut count = target.round().clamp((source != 0) as u8 as f64, 4095.0) as u16;
let log = if count == 0 {
0
} else {
floor_log2(count as u32) as i32
};
let step_log = if count == 0 {
0
} else {
log - get_pop_count_precision(log, shift as i32)
};
count &= !((1u16 << step_log) - 1);
freqs[i] = count;
rest -= count as i32;
if target > 1.0 {
bins.push(AdjustableBin {
source_count: source,
count_index: allowed.index[count as usize] as usize,
bin_index: i,
});
}
}
bins.retain(|b| b.bin_index != omit_pos);
rest += freqs[omit_pos] as i32;
if !bins.is_empty() {
let max_step_log = allowed.descending[1].step_log as usize;
loop {
let mut balance_inc = [0.0f64; ANS_LOG_TAB_SIZE as usize - 1];
let mut balance_dec = [0.0f64; ANS_LOG_TAB_SIZE as usize - 1];
for log in 0..=max_step_log {
let delta = 1i32 << log;
if rest >= ANS_TAB_SIZE as i32 {
balance_inc[log] = 0.0;
balance_dec[log] = 0.0;
} else if rest > 1 {
balance_inc[log] = if rest > delta {
max_source as f64 * (logs[rest as usize] - logs[(rest - delta) as usize])
} else {
f64::INFINITY
};
balance_dec[log] = if rest + delta < ANS_TAB_SIZE as i32 {
max_source as f64 * (logs[(rest + delta) as usize] - logs[rest as usize])
} else {
f64::INFINITY
};
} else {
balance_inc[log] = f64::INFINITY;
balance_dec[log] = f64::INFINITY;
}
}
let inc_delta = |b: &AdjustableBin| {
let a = allowed.descending[b.count_index];
(b.source_count as f64 * a.delta_log - balance_inc[a.step_log as usize])
/ (1u32 << a.step_log) as f64
};
let dec_delta = |b: &AdjustableBin| {
let a = allowed.descending[b.count_index + 1];
(b.source_count as f64 * a.delta_log - balance_dec[a.step_log as usize])
/ (1u32 << a.step_log) as f64
};
let best_inc = bins
.iter()
.enumerate()
.max_by(|(_, a), (_, b)| inc_delta(a).total_cmp(&inc_delta(b)))
.map(|(i, _)| i)
.unwrap();
if inc_delta(&bins[best_inc]) > 0.0 {
let step = allowed.descending[bins[best_inc].count_index].step_log;
bins[best_inc].count_index -= 1;
rest -= 1i32 << step;
continue;
}
let best_dec = bins
.iter()
.enumerate()
.min_by(|(_, a), (_, b)| dec_delta(a).total_cmp(&dec_delta(b)))
.map(|(i, _)| i)
.unwrap();
if dec_delta(&bins[best_dec]) >= 0.0 {
break;
}
bins[best_dec].count_index += 1;
let step = allowed.descending[bins[best_dec].count_index].step_log;
rest += 1i32 << step;
}
for bin in bins {
freqs[bin.bin_index] = allowed.descending[bin.count_index].count;
}
for i in 0..omit_pos {
if freqs[i] >= 2048 {
freqs[omit_pos] = freqs[i];
omit_pos = i;
break;
}
}
}
if !(1..ANS_TAB_SIZE as i32).contains(&rest) {
return None;
}
freqs[omit_pos] = rest as u16;
Some(AnsHistogram {
freqs,
method: (shift + 1) as u8,
omit_pos: omit_pos as u8,
cost: 0.0,
})
}
#[derive(Clone, Copy, Default)]
struct AliasEntry {
cutoff: u32,
right_value: u32,
freq0: u32,
offsets1: u32,
freq1_xor_freq0: u32,
}
fn init_alias_table(distribution_in: &[u16]) -> [AliasEntry; TABLE_ENTRIES] {
let range = ANS_TAB_SIZE;
let entry_size = ENTRY_SIZE;
let mut dist: Vec<u32> = distribution_in.iter().map(|&x| x as u32).collect();
while dist.last() == Some(&0) {
dist.pop();
}
if dist.is_empty() {
dist.push(range);
}
let mut a = [AliasEntry::default(); TABLE_ENTRIES];
if let Some(sym) = dist.iter().position(|&v| v == ANS_TAB_SIZE) {
for i in 0..TABLE_ENTRIES {
a[i].right_value = sym as u32;
a[i].cutoff = 0;
a[i].offsets1 = entry_size * i as u32;
a[i].freq0 = 0;
a[i].freq1_xor_freq0 = ANS_TAB_SIZE;
}
return a;
}
let mut underfull: Vec<u32> = Vec::with_capacity(TABLE_ENTRIES);
let mut overfull: Vec<u32> = Vec::with_capacity(TABLE_ENTRIES);
let mut cutoffs = [0u32; TABLE_ENTRIES];
for (i, (&dist, cutoff)) in dist.iter().zip(cutoffs.iter_mut()).enumerate() {
*cutoff = dist;
if *cutoff > entry_size {
overfull.push(i as u32);
} else if *cutoff < entry_size {
underfull.push(i as u32);
}
}
for (i, cutoff) in
(dist.len()..TABLE_ENTRIES).zip(cutoffs[dist.len()..TABLE_ENTRIES].iter_mut())
{
*cutoff = 0;
underfull.push(i as u32);
}
while let Some(over) = overfull.pop() {
let under = underfull.pop().expect("alias: underfull stack empty");
let under_by = entry_size - cutoffs[under as usize];
cutoffs[over as usize] -= under_by;
a[under as usize].right_value = over;
a[under as usize].offsets1 = cutoffs[over as usize];
if cutoffs[over as usize] < entry_size {
underfull.push(over);
} else if cutoffs[over as usize] > entry_size {
overfull.push(over);
}
}
for (i, (&cutoff, a)) in cutoffs[..TABLE_ENTRIES]
.iter()
.zip(a[..TABLE_ENTRIES].iter_mut())
.enumerate()
{
if cutoff == entry_size {
a.right_value = i as u32;
a.offsets1 = 0;
a.cutoff = 0;
} else {
a.offsets1 -= cutoff;
a.cutoff = cutoff;
}
let freq0 = if i < dist.len() { dist[i] } else { 0 };
let i1 = a.right_value as usize;
let freq1 = if i1 < dist.len() { dist[i1] } else { 0 };
a.freq0 = freq0;
a.freq1_xor_freq0 = freq1 ^ freq0;
}
a
}
struct AliasSymbol {
value: usize,
offset: usize,
}
#[inline]
fn alias_lookup(a: &[AliasEntry; TABLE_ENTRIES], value: u32) -> AliasSymbol {
let i = (value >> LOG_ENTRY_SIZE) as usize;
let pos = value & ENTRY_SIZE_M1;
let greater = pos >= a[i].cutoff;
let offsets1_or_0 = if greater { a[i].offsets1 } else { 0 };
AliasSymbol {
value: if greater {
a[i].right_value as usize
} else {
i
},
offset: (offsets1_or_0 + pos) as usize,
}
}
#[derive(Clone, Copy)]
pub(crate) struct AnsEncSymbolInfo {
pub(crate) freq: u16,
divider: FastDivU16,
reverse_offset: u16,
}
pub(crate) fn build_symbol_info(freqs: &[u16], reverse_map: &mut [u16]) -> Vec<AnsEncSymbolInfo> {
assert_eq!(reverse_map.len(), ANS_TAB_SIZE as usize);
reverse_map.fill(0);
let alias = init_alias_table(freqs);
let mut reverse_offset = 0u16;
let symbols: Vec<AnsEncSymbolInfo> = freqs
.iter()
.map(|&freq| {
let info = AnsEncSymbolInfo {
freq,
divider: FastDivU16::new_or_one(freq),
reverse_offset,
};
reverse_offset += freq;
info
})
.collect();
debug_assert!(
u32::from(reverse_offset) == ANS_TAB_SIZE || freqs.iter().all(|&f| f == 0),
"frequencies sum to {reverse_offset}, expected {ANS_TAB_SIZE}"
);
for slot in 0..ANS_TAB_SIZE {
let s = alias_lookup(&alias, slot);
if s.value < symbols.len() && s.offset < symbols[s.value].freq as usize {
let offset = symbols[s.value].reverse_offset as usize + s.offset;
reverse_map[offset] = slot as u16;
}
}
symbols
}
pub(crate) struct AnsCoder {
state: u32,
}
impl AnsCoder {
pub(crate) fn new() -> Self {
Self {
state: ANS_SIGNATURE << 16,
}
}
#[inline]
pub(crate) fn put_symbol(
&mut self,
info: &AnsEncSymbolInfo,
reverse_map: &[u16],
) -> Option<u16> {
let freq = info.freq as u32;
debug_assert!(freq > 0, "ANS symbol with zero frequency");
if freq == ANS_TAB_SIZE {
return None;
}
let reverse_offset = info.reverse_offset as usize;
debug_assert!(reverse_offset + freq as usize <= reverse_map.len());
let mut state = self.state;
let mut emitted = None;
if (state >> (32 - ANS_LOG_TAB_SIZE)) >= freq {
emitted = Some((state & 0xffff) as u16);
state >>= 16;
}
let (q, rem) = info.divider.div_rem_fast(state, freq);
let mapped = reverse_map[reverse_offset + rem as usize] as u32;
self.state = (q << ANS_LOG_TAB_SIZE) + mapped;
emitted
}
#[inline]
pub(crate) fn state(&self) -> u32 {
self.state
}
}
const ANS_NO_EMIT: u32 = u32::MAX;
pub(crate) fn write_ans_tokens<'a>(
tokens: impl Into<TokenSlice<'a>>,
context_map: &[u8],
symbol_info: &[Vec<AnsEncSymbolInfo>],
reverse_maps: &[u16],
hybrid_uint_configs: &[super::token::HybridUintConfig],
w: &mut BitWriter,
) {
let tokens = tokens.into();
let mut emitted: Vec<u64> = Vec::with_capacity(tokens.len());
let mut extra_bits: Vec<u8> = Vec::with_capacity(tokens.len());
let mut coder = AnsCoder::new();
tokens.iter().rev().for_each(|t| {
let hist = context_map[t.context as usize] as usize;
let (sym, nbits, bits) =
super::token::uint_encode_with_config(t.value, hybrid_uint_configs[hist]);
let start = hist * ANS_TAB_SIZE as usize;
let word = coder.put_symbol(
&symbol_info[hist][sym as usize],
&reverse_maps[start..start + ANS_TAB_SIZE as usize],
);
emitted.push((u64::from(word.map_or(ANS_NO_EMIT, u32::from)) << 32) | u64::from(bits));
extra_bits.push(nbits as u8);
});
w.write(32, coder.state() as u64);
for (&packed, &nbits) in emitted.iter().rev().zip(extra_bits.iter().rev()) {
let word = (packed >> 32) as u32;
if word != ANS_NO_EMIT {
w.write(16, u64::from(word));
}
if nbits != 0 {
w.write(nbits as usize, packed & 0xffff_ffff);
}
}
}
#[cfg(test)]
pub(crate) fn ans_tokens_bits<'a>(
tokens: impl Into<TokenSlice<'a>>,
context_map: &[u8],
symbol_info: &[Vec<AnsEncSymbolInfo>],
reverse_maps: &[u16],
hybrid_uint_configs: &[super::token::HybridUintConfig],
) -> usize {
let tokens = tokens.into();
let mut coder = AnsCoder::new();
let mut bits = 32usize;
tokens.iter().rev().for_each(|t| {
let hist = context_map[t.context as usize] as usize;
let (sym, nbits, _) =
super::token::uint_encode_with_config(t.value, hybrid_uint_configs[hist]);
let reverse_start = hist * ANS_TAB_SIZE as usize;
let reverse_map = &reverse_maps[reverse_start..reverse_start + ANS_TAB_SIZE as usize];
if coder
.put_symbol(&symbol_info[hist][sym as usize], reverse_map)
.is_some()
{
bits += 16;
}
bits += nbits as usize;
});
bits
}
#[derive(Clone, Copy)]
pub(crate) struct AnsTokenCodeRef<'a> {
pub(crate) context_map: &'a [u8],
pub(crate) symbol_info: &'a [Vec<AnsEncSymbolInfo>],
pub(crate) reverse_maps: &'a [u16],
pub(crate) hybrid_uint_configs: &'a [super::token::HybridUintConfig],
}
pub(crate) fn ans_tokens_bits_pair<'a>(
tokens: impl Into<TokenSlice<'a>>,
first: &AnsTokenCodeRef<'_>,
second: &AnsTokenCodeRef<'_>,
) -> (usize, usize) {
let tokens = tokens.into();
let mut first_coder = AnsCoder::new();
let mut second_coder = AnsCoder::new();
let mut first_bits = 32usize;
let mut second_bits = 32usize;
tokens.iter().rev().for_each(|token| {
let context = token.context as usize;
let first_hist = first.context_map[context] as usize;
let second_hist = second.context_map[context] as usize;
let first_config = first.hybrid_uint_configs[first_hist];
let (symbol, nbits, _) = super::token::uint_encode_with_config(token.value, first_config);
let second_config = second.hybrid_uint_configs[second_hist];
let (second_symbol, second_nbits, _) = if first_config == second_config {
(symbol, nbits, 0)
} else {
super::token::uint_encode_with_config(token.value, second_config)
};
let first_reverse_start = first_hist * ANS_TAB_SIZE as usize;
if first_coder
.put_symbol(
&first.symbol_info[first_hist][symbol as usize],
&first.reverse_maps
[first_reverse_start..first_reverse_start + ANS_TAB_SIZE as usize],
)
.is_some()
{
first_bits += 16;
}
let second_reverse_start = second_hist * ANS_TAB_SIZE as usize;
if second_coder
.put_symbol(
&second.symbol_info[second_hist][second_symbol as usize],
&second.reverse_maps
[second_reverse_start..second_reverse_start + ANS_TAB_SIZE as usize],
)
.is_some()
{
second_bits += 16;
}
first_bits += nbits as usize;
second_bits += second_nbits as usize;
});
(first_bits, second_bits)
}
#[inline]
fn floor_log2(x: u32) -> u32 {
31 - x.leading_zeros()
}
#[inline]
fn get_pop_count_precision(logcount: i32, shift: i32) -> i32 {
let r = logcount.min(shift - ((ANS_LOG_TAB_SIZE as i32 - logcount) >> 1));
if r < 0 { 0 } else { r }
}
pub(crate) trait HistogramWriter {
fn write(&mut self, n_bits: usize, bits: u64);
}
impl HistogramWriter for BitWriter {
#[inline]
fn write(&mut self, n_bits: usize, bits: u64) {
BitWriter::write(self, n_bits, bits);
}
}
#[derive(Default)]
struct HistogramBitCounter(usize);
impl HistogramWriter for HistogramBitCounter {
#[inline]
fn write(&mut self, n_bits: usize, _bits: u64) {
self.0 += n_bits;
}
}
fn store_varlen_u8<W: HistogramWriter>(n: u32, w: &mut W) {
if n == 0 {
w.write(1, 0);
} else {
w.write(1, 1);
let nbits = floor_log2(n);
w.write(3, nbits as u64);
w.write(nbits as usize, (n - (1 << nbits)) as u64);
}
}
static K_BIT_WIDTH_LENGTHS: [u8; 14] = [5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 6, 7, 7];
static K_BIT_WIDTH_SYMBOLS: [u8; 14] = [17, 11, 15, 3, 9, 7, 4, 2, 5, 6, 0, 33, 1, 65];
pub(crate) fn encode_histogram<W: HistogramWriter>(
histogram: &AnsHistogram,
_log_alpha_size: u32,
w: &mut W,
) {
let freqs = &histogram.freqs;
let mut alphabet_size = freqs.len();
while alphabet_size > 0 && freqs[alphabet_size - 1] == 0 {
alphabet_size -= 1;
}
debug_assert!(alphabet_size <= TABLE_ENTRIES);
if histogram.method == 0 {
w.write(1, 0); w.write(1, 1); debug_assert!(alphabet_size > 0);
store_varlen_u8((alphabet_size - 1) as u32, w);
return;
}
let mut symbols = [0usize; 2];
let mut num_symbols = 0usize;
for (i, &freq) in freqs[..alphabet_size].iter().enumerate() {
if freq != 0 {
if num_symbols < symbols.len() {
symbols[num_symbols] = i;
}
num_symbols += 1;
}
}
if num_symbols <= 2 {
w.write(1, 1); if num_symbols == 0 {
w.write(1, 0);
store_varlen_u8(0, w);
} else {
w.write(1, (num_symbols - 1) as u64);
for &s in &symbols[..num_symbols] {
store_varlen_u8(s as u32, w);
}
}
if num_symbols == 2 {
w.write(ANS_LOG_TAB_SIZE as usize, freqs[symbols[0]] as u64);
}
return;
}
w.write(1, 0); w.write(1, 0); let method = histogram.method as u32;
let upper_bound_log = floor_log2(ANS_LOG_TAB_SIZE + 1); let log = floor_log2(method); w.write(log as usize, ((1u32 << log) - 1) as u64);
if log != upper_bound_log {
w.write(1, 0);
}
w.write(log as usize, (((1u32 << log) - 1) & method) as u64);
store_varlen_u8((alphabet_size - 3) as u32, w);
let omit_pos = histogram.omit_pos as usize;
debug_assert!(omit_pos < alphabet_size);
let mut bit_width = [0u8; TABLE_ENTRIES];
let mut omit_width: i32 = 10;
for (i, (bit_width, &count)) in bit_width
.iter_mut()
.zip(freqs[..alphabet_size].iter())
.enumerate()
{
if i != omit_pos && count > 0 {
*bit_width = (floor_log2(count as u32) + 1) as u8;
let cand = *bit_width as i32 + if i < omit_pos { 1 } else { 0 };
if cand > omit_width {
omit_width = cand;
}
}
}
bit_width[omit_pos] = omit_width as u8;
const MIN_REPS: usize = 5;
const RLE_SYMBOL: usize = ANS_LOG_TAB_SIZE as usize + 1;
let mut same = [0u8; TABLE_ENTRIES];
let mut last = 0usize;
for i in 1..=alphabet_size {
if i == alphabet_size || i == omit_pos || i == omit_pos + 1 || freqs[i] != freqs[last] {
same[last] = (i - last) as u8;
last = i;
}
}
let mut i = 0usize;
while i < alphabet_size {
let bw = bit_width[i] as usize;
w.write(
K_BIT_WIDTH_LENGTHS[bw] as usize,
K_BIT_WIDTH_SYMBOLS[bw] as u64,
);
let run = same[i] as usize;
if run >= MIN_REPS {
w.write(
K_BIT_WIDTH_LENGTHS[RLE_SYMBOL] as usize,
K_BIT_WIDTH_SYMBOLS[RLE_SYMBOL] as u64,
);
store_varlen_u8((run - MIN_REPS) as u32, w);
i += run;
} else {
i += 1;
}
}
let shift: i32 = (method - 1) as i32;
if shift != 0 {
let mut i = 0usize;
while i < alphabet_size {
let bit_width = bit_width[i];
let count = freqs[i] as i32;
if bit_width > 1 && i != omit_pos {
let code = bit_width as i32 - 1;
let bitcount = get_pop_count_precision(code, shift);
let drop_bits = code - bitcount;
debug_assert_eq!(count & ((1 << drop_bits) - 1), 0);
w.write(
bitcount as usize,
((count >> drop_bits) - (1 << bitcount)) as u64,
);
}
let run = same[i] as usize;
i += if run >= MIN_REPS { run } else { 1 };
}
}
}
fn flat_histogram(len: usize, storage_len: usize) -> AnsHistogram {
let base = ANS_TAB_SIZE as usize / len;
let remainder = ANS_TAB_SIZE as usize % len;
let mut freqs = vec![0u16; storage_len];
for (i, freq) in freqs[..len].iter_mut().enumerate() {
*freq = (base + usize::from(i < remainder)) as u16;
}
AnsHistogram {
freqs,
method: 0,
omit_pos: 0,
cost: 0.0,
}
}
fn histogram_cost(counts: &[u32], histogram: &AnsHistogram) -> f64 {
ans_data_bits(counts, &histogram.freqs) + ans_table_bits(histogram)
}
pub(crate) struct AnsCostScratch {
precise: AnsHistogram,
}
impl AnsCostScratch {
pub(crate) fn new() -> Self {
let blank = || AnsHistogram {
freqs: vec![0u16; TABLE_ENTRIES],
method: 12,
omit_pos: 0,
cost: 0.0,
};
Self { precise: blank() }
}
}
struct FlatPopulationCost {
symbol_bits: Box<[f64]>,
table_bits: f64,
}
fn flat_population_costs() -> &'static [FlatPopulationCost] {
static COSTS: OnceLock<Box<[FlatPopulationCost]>> = OnceLock::new();
COSTS.get_or_init(|| {
let logs = count_log2();
(1..=TABLE_ENTRIES)
.map(|len| {
let flat = flat_histogram(len, len);
FlatPopulationCost {
symbol_bits: flat
.freqs
.iter()
.map(|&freq| ANS_LOG_TAB_SIZE as f64 - logs[freq as usize])
.collect(),
table_bits: ans_table_bits(&flat),
}
})
.collect()
})
}
pub(crate) fn fast_ans_population_cost_scratch(
counts: &[u32],
data_scale: usize,
scratch: &mut AnsCostScratch,
) -> f64 {
debug_assert_eq!(counts.len(), TABLE_ENTRIES);
let alphabet_size = populated_alphabet_size(counts);
let precise = &mut scratch.precise;
let counts = &counts[..alphabet_size];
precise.freqs.resize(alphabet_size, 0);
let omit_pos = normalize_counts_first_maximum(counts, &mut precise.freqs);
precise.method = 12;
precise.omit_pos = omit_pos as u8;
if alphabet_size == 0 {
return ans_table_bits(precise);
}
let flat = &flat_population_costs()[alphabet_size - 1];
let logs = count_log2();
let mut precise_bits = 0.0;
let mut flat_bits = 0.0;
for ((&count, &freq), &flat_price) in counts.iter().zip(&precise.freqs).zip(&flat.symbol_bits) {
if count != 0 {
precise_bits = f_fmla(
count as f64,
ANS_LOG_TAB_SIZE as f64 - logs[freq.max(1) as usize],
precise_bits,
);
flat_bits = f_fmla(count as f64, flat_price, flat_bits);
}
}
(precise_bits * data_scale as f64 + ans_table_bits(precise))
.min(flat_bits * data_scale as f64 + flat.table_bits)
}
pub(crate) fn fast_ans_population_cost(counts: &[u32], data_scale: usize) -> f64 {
let mut alphabet_size = counts.len();
while alphabet_size > 0 && counts[alphabet_size - 1] == 0 {
alphabet_size -= 1;
}
let mut freqs = Vec::new();
normalize_counts(counts, &mut freqs);
let (omit_pos, _) = first_maximum(&freqs[..alphabet_size]);
let precise = AnsHistogram {
freqs,
method: 12,
omit_pos: omit_pos as u8,
cost: 0.0,
};
let scaled_cost = |histogram: &AnsHistogram| {
ans_data_bits(counts, &histogram.freqs) * data_scale as f64 + ans_table_bits(histogram)
};
let mut best = scaled_cost(&precise);
if alphabet_size != 0 {
best = best.min(scaled_cost(&flat_histogram(alphabet_size, counts.len())));
}
best
}
pub(crate) fn optimize_ans_histogram(counts: &[u32]) -> AnsHistogram {
let mut alphabet_size = counts.len();
while alphabet_size > 0 && counts[alphabet_size - 1] == 0 {
alphabet_size -= 1;
}
if alphabet_size == 0 {
return AnsHistogram {
freqs: vec![0; counts.len()],
method: 1,
omit_pos: 0,
cost: 3.0,
};
}
let mut best = flat_histogram(alphabet_size, counts.len());
let mut best_cost = histogram_cost(counts, &best);
best.cost = best_cost;
let num_symbols = counts[..alphabet_size].iter().filter(|&&v| v != 0).count();
if num_symbols == 1 {
let symbol = counts[..alphabet_size]
.iter()
.position(|&v| v != 0)
.unwrap();
let mut freqs = vec![0; counts.len()];
freqs[symbol] = ANS_TAB_SIZE as u16;
let mut histogram = AnsHistogram {
freqs,
method: 1,
omit_pos: symbol as u8,
cost: 0.0,
};
histogram.cost = histogram_cost(counts, &histogram);
return histogram;
}
if num_symbols == 2 {
let mut freqs = Vec::new();
normalize_counts(counts, &mut freqs);
let omit_pos = freqs
.iter()
.enumerate()
.max_by_key(|&(_, f)| f)
.map_or(0, |(i, _)| i);
let precise = AnsHistogram {
freqs,
method: 12,
omit_pos: omit_pos as u8,
cost: 0.0,
};
let precise_cost = histogram_cost(counts, &precise);
if precise_cost < best_cost {
let mut precise = precise;
precise.cost = precise_cost;
return precise;
}
return best;
}
let mut precise_freqs = Vec::new();
normalize_counts(counts, &mut precise_freqs);
let (precise_omit, _) = first_maximum(&precise_freqs[..alphabet_size]);
let precise = AnsHistogram {
freqs: precise_freqs,
method: 12,
omit_pos: precise_omit as u8,
cost: 0.0,
};
let precise_cost = histogram_cost(counts, &precise);
if precise_cost < best_cost {
best = precise;
best_cost = precise_cost;
best.cost = best_cost;
}
for shift in [0usize, ANS_LOG_TAB_SIZE as usize / 2] {
if let Some(candidate) = rebalance_counts(counts, alphabet_size, shift) {
let cost = histogram_cost(counts, &candidate);
if cost < best_cost {
best = candidate;
best_cost = cost;
best.cost = best_cost;
}
}
}
best
}
pub(crate) fn refine_ans_histogram_precision(
counts: &[u32],
incumbent: &AnsHistogram,
) -> Option<AnsHistogram> {
let alphabet_size = counts.iter().rposition(|&c| c != 0).map_or(0, |i| i + 1);
if counts[..alphabet_size].iter().filter(|&&c| c != 0).count() < 3 {
return None;
}
let mut best = None;
let mut best_cost = histogram_cost(counts, incumbent);
for shift in [1, 2, 3, 4, 5, 7, 8, 9, 10, 11] {
if let Some(mut candidate) = rebalance_counts(counts, alphabet_size, shift) {
let cost = histogram_cost(counts, &candidate);
if cost < best_cost {
candidate.cost = cost;
best = Some(candidate);
best_cost = cost;
}
}
}
best
}
pub(crate) fn ans_data_bits(counts: &[u32], freqs: &[u16]) -> f64 {
let mut bits = 0.0f64;
let logs = count_log2();
for (&freqs, &count) in freqs.iter().zip(counts.iter()) {
if count == 0 {
continue;
}
let f = freqs.max(1) as usize;
bits = f_fmla(count as f64, ANS_LOG_TAB_SIZE as f64 - logs[f], bits);
}
bits
}
pub(crate) fn huffman_data_bits(counts: &[u32], depths: &[u8]) -> f64 {
let mut bits = 0.0f64;
for (&count, &depth) in counts.iter().zip(depths[..counts.len()].iter()) {
bits = f_fmla(count as f64, depth as f64, bits);
}
bits
}
fn precise_ans_table_bits(histogram: &AnsHistogram) -> usize {
fn varlen_bits(n: usize) -> usize {
if n == 0 {
1
} else {
4 + floor_log2(n as u32) as usize
}
}
fn width(freq: u16) -> usize {
(u16::BITS - freq.leading_zeros()) as usize
}
fn flush_run(bits: &mut usize, freq: u16, run: usize) {
if run == 0 {
return;
}
let width = width(freq);
let entry_bits = K_BIT_WIDTH_LENGTHS[width] as usize + width.saturating_sub(1);
if run >= 5 {
*bits += entry_bits
+ K_BIT_WIDTH_LENGTHS[ANS_LOG_TAB_SIZE as usize + 1] as usize
+ varlen_bits(run - 5);
} else {
*bits += run * entry_bits;
}
}
let alphabet_size = histogram
.freqs
.iter()
.rposition(|&f| f != 0)
.map_or(0, |i| i + 1);
let freqs = &histogram.freqs[..alphabet_size];
let omit_pos = histogram.omit_pos as usize;
let mut populated = 0usize;
let mut first = 0usize;
let mut second = 0usize;
let mut before = 0u16;
let mut after = 0u16;
let mut run_bits = 0usize;
let mut run_freq = 0u16;
let mut run = 0usize;
for (i, &freq) in freqs.iter().enumerate() {
if freq != 0 {
match populated {
0 => first = i,
1 => second = i,
_ => {}
}
populated += 1;
}
if i == omit_pos {
flush_run(&mut run_bits, run_freq, run);
run = 0;
continue;
}
if i < omit_pos {
before = before.max(freq);
} else {
after = after.max(freq);
}
if run != 0 && freq == run_freq {
run += 1;
} else {
flush_run(&mut run_bits, run_freq, run);
run_freq = freq;
run = 1;
}
}
flush_run(&mut run_bits, run_freq, run);
match populated {
0 => return 3,
1 => return 2 + varlen_bits(first),
2 => return 2 + varlen_bits(first) + varlen_bits(second) + ANS_LOG_TAB_SIZE as usize,
_ => {}
}
let omit_width = 10.max(width(before) + 1).max(width(after));
8 + varlen_bits(alphabet_size - 3) + K_BIT_WIDTH_LENGTHS[omit_width] as usize + run_bits
}
pub(crate) fn ans_table_bits(histogram: &AnsHistogram) -> f64 {
if histogram.method == 12 {
return precise_ans_table_bits(histogram) as f64;
}
let mut w = HistogramBitCounter::default();
encode_histogram(histogram, LOG_ALPHA_SIZE as u32, &mut w);
w.0 as f64
}
pub(crate) fn huffman_tree_bits_estimate(depths: &[u8]) -> f64 {
let used = depths.iter().filter(|&&d| d != 0).count();
f_fmla(used as f64, 4.0, 8.0)
}
pub(crate) fn choose_use_prefix_code(
histograms: &[Histogram],
ans_histograms: &[AnsHistogram],
huffman_depths: &[[u8; super::prefix_code::ALPHABET_SIZE]],
) -> bool {
let mut ans_total = 0.0f64;
let mut huff_total = 0.0f64;
for ((h, histogram), depths) in histograms
.iter()
.zip(ans_histograms)
.zip(huffman_depths.iter())
{
ans_total += histogram.cost;
huff_total += huffman_data_bits(&h.counts, depths) + huffman_tree_bits_estimate(depths);
}
huff_total <= ans_total
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn precise_table_cost_matches_serialized_bits() {
let mut state = 0xc39e_729bu32;
let check = |freqs: Vec<u16>, omit_pos: usize| {
let histogram = AnsHistogram {
freqs,
method: 12,
omit_pos: omit_pos as u8,
cost: 0.0,
};
let mut writer = BitWriter::new();
encode_histogram(&histogram, LOG_ALPHA_SIZE as u32, &mut writer);
assert_eq!(
ans_table_bits(&histogram) as usize,
writer.bits_written(),
"freqs={:?}, omit_pos={omit_pos}",
histogram.freqs
);
};
for case in 0..2_000 {
let len = (case * 73) % (TABLE_ENTRIES + 1);
let mut counts = [0; TABLE_ENTRIES];
for (i, count) in counts[..len].iter_mut().enumerate() {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
*count = match case % 4 {
0 => 1,
1 => u32::from(i % 7 == 0) * (state % 10_000),
2 => u32::from(i == 0 || i + 1 == len),
_ => state % 10_000,
};
}
let mut freqs = Vec::new();
normalize_counts(&counts, &mut freqs);
let (omit, _) = first_maximum(&freqs);
check(freqs.clone(), omit);
freqs.truncate(len);
check(freqs, omit);
}
for run in [4, 5, 6, 63, 126] {
for repeated in [0, 1, 16] {
let mut freqs = vec![repeated; run];
freqs.extend([2, ANS_TAB_SIZE as u16 - repeated * run as u16 - 2]);
for omit in [0, run / 2, freqs.len() - 1] {
check(freqs.clone(), omit);
}
}
}
}
#[test]
fn scratch_population_cost_matches_full_alphabet_after_reuse() {
let mut scratch = AnsCostScratch::new();
let mut state = 0x392dda71u32;
for case in 0..1024 {
let len = (case * 73) % (TABLE_ENTRIES + 1);
let mut counts = [0; TABLE_ENTRIES];
for (i, count) in counts[..len].iter_mut().enumerate() {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
*count = match case % 4 {
0 => 1,
1 => {
if i % 3 == 0 {
state % 10_000
} else {
0
}
}
2 => {
if i + 1 == len {
u32::MAX
} else {
0
}
}
_ => state % 10_000,
};
}
for scale in [0, 1, 3, 17] {
assert_eq!(
fast_ans_population_cost_scratch(&counts, scale, &mut scratch).to_bits(),
fast_ans_population_cost(&counts, scale).to_bits(),
"case={case}, scale={scale}",
);
}
}
}
#[test]
fn normalization_matches_one_count_at_a_time() {
fn reference(counts: &[u32]) -> Vec<u16> {
let total: u64 = counts.iter().map(|&c| u64::from(c)).sum();
if total == 0 {
return vec![0; counts.len()];
}
let mut freqs: Vec<u16> = counts
.iter()
.map(|&c| {
if c == 0 {
0
} else {
(u64::from(c) * u64::from(ANS_TAB_SIZE) / total).max(1) as u16
}
})
.collect();
let mut sum: u32 = freqs.iter().map(|&f| u32::from(f)).sum();
while sum != ANS_TAB_SIZE {
let maximum = *freqs.iter().max().unwrap();
let first = freqs.iter().position(|&f| f == maximum).unwrap();
if sum < ANS_TAB_SIZE {
freqs[first] += 1;
sum += 1;
} else if maximum > 1 {
freqs[first] -= 1;
sum -= 1;
} else {
break;
}
}
freqs
}
let mut state = 0x235da23eu32;
for case in 0..2048 {
let len = case % (TABLE_ENTRIES + 1);
let counts: Vec<u32> = (0..len)
.map(|i| {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
match case % 6 {
0 => 0,
1 => 1, 2 => {
if i == len / 2 {
u32::MAX
} else {
1
}
} 3 => state % 11,
4 => {
if i % 3 == 0 {
0
} else {
state
}
}
_ => state,
}
})
.collect();
let mut freqs = vec![u16::MAX; len];
normalize_counts_into(&counts, &mut freqs);
assert_eq!(freqs, reference(&counts), "case={case}");
}
}
fn assert_flat_reverse_map(freqs: &[u16]) {
let alias = init_alias_table(freqs);
let mut reverse_map = vec![0u16; ANS_TAB_SIZE as usize];
let info = build_symbol_info(freqs, &mut reverse_map);
let mut legacy: Vec<Vec<u16>> = freqs
.iter()
.map(|&freq| vec![0u16; freq as usize])
.collect();
for slot in 0..ANS_TAB_SIZE {
let decoded = alias_lookup(&alias, slot);
legacy[decoded.value][decoded.offset] = slot as u16;
}
assert_eq!(reverse_map.len(), ANS_TAB_SIZE as usize);
assert_eq!(info.len(), freqs.len());
let mut expected_offset = 0usize;
for (symbol, (&freq, symbol_info)) in freqs.iter().zip(&info).enumerate() {
assert_eq!(symbol_info.freq, freq);
assert_eq!(symbol_info.reverse_offset as usize, expected_offset);
assert_eq!(
&reverse_map[expected_offset..expected_offset + freq as usize],
legacy[symbol]
);
for remainder in 0..freq as usize {
let slot = reverse_map[expected_offset + remainder] as u32;
let decoded = alias_lookup(&alias, slot);
assert_eq!(decoded.value, symbol);
assert_eq!(decoded.offset, remainder);
}
expected_offset += freq as usize;
}
assert_eq!(expected_offset, ANS_TAB_SIZE as usize);
}
#[test]
fn flat_reverse_map_inverts_alias_lookup() {
assert!(core::mem::size_of::<AnsEncSymbolInfo>() <= 16);
let mut single = [0u16; TABLE_ENTRIES];
single[37] = ANS_TAB_SIZE as u16;
assert_flat_reverse_map(&single);
let counts: [u32; TABLE_ENTRIES] =
core::array::from_fn(|symbol| ((symbol * 29 + symbol * symbol * 7 + 11) % 251) as u32);
let mut normalized = Vec::new();
normalize_counts(&counts, &mut normalized);
assert_flat_reverse_map(&normalized);
}
#[test]
fn single_symbol_leaves_every_state_unchanged() {
for symbol in [0, 37, TABLE_ENTRIES - 1] {
let mut freqs = [0u16; TABLE_ENTRIES];
freqs[symbol] = ANS_TAB_SIZE as u16;
let mut reverse_map = vec![0u16; ANS_TAB_SIZE as usize];
let info = build_symbol_info(&freqs, &mut reverse_map);
assert!(
reverse_map
.iter()
.enumerate()
.all(|(i, &v)| i == v as usize)
);
for state in [0, 1, 65_535, 65_536, 0x13ab_0000, u32::MAX] {
let mut coder = AnsCoder { state };
assert_eq!(coder.put_symbol(&info[symbol], &reverse_map), None);
assert_eq!(coder.state(), state);
}
}
}
#[test]
fn symbol_info_builds_on_a_small_stack() {
crate::thread_pool::ThreadPool::on_small_stack(|| {
let counts: [u32; TABLE_ENTRIES] =
core::array::from_fn(|symbol| (symbol * 37 % 257 + 1) as u32);
let mut freqs = Vec::new();
normalize_counts(&counts, &mut freqs);
let mut reverse_map = vec![0u16; ANS_TAB_SIZE as usize];
let symbols = build_symbol_info(&freqs, &mut reverse_map);
assert_eq!(symbols.len(), TABLE_ENTRIES);
});
}
#[test]
fn optimized_histograms_are_valid_and_representable() {
let mut state = 0x1234_5678_9abc_def0u64;
for case in 0..500 {
let len = case % TABLE_ENTRIES + 1;
let mut counts = vec![0u32; TABLE_ENTRIES];
for count in &mut counts[..len] {
state = state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
*count = ((state >> 33) as u32) % 10_000;
}
counts[case % len] = counts[case % len].max(1);
let histogram = optimize_ans_histogram(&counts);
let refined = refine_ans_histogram_precision(&counts, &histogram);
if let Some(refined) = &refined {
assert!(histogram_cost(&counts, refined) < histogram_cost(&counts, &histogram));
}
for histogram in std::iter::once(histogram).chain(refined) {
assert_eq!(
histogram.freqs.iter().map(|&v| v as u32).sum::<u32>(),
ANS_TAB_SIZE
);
assert!(histogram.method <= 12);
if histogram.method == 0 {
let expected = flat_histogram(len, counts.len());
assert_eq!(histogram.freqs, expected.freqs);
continue;
}
for (i, (&source, &freq)) in counts.iter().zip(&histogram.freqs).enumerate() {
assert_eq!(source == 0, freq == 0);
if freq != 0 && i != histogram.omit_pos as usize {
let log = floor_log2(freq as u32) as i32;
let precision = get_pop_count_precision(log, histogram.method as i32 - 1);
let dropped = log - precision;
assert_eq!(freq & ((1u16 << dropped) - 1), 0);
}
}
let mut writer = BitWriter::new();
encode_histogram(&histogram, LOG_ALPHA_SIZE as u32, &mut writer);
assert!(writer.bits_written() != 0);
}
}
}
#[test]
fn precision_refinement_skips_empty_and_small_histograms() {
for counts in [vec![0; 128], vec![0, 23, 0], vec![7, 0, 11]] {
let incumbent = optimize_ans_histogram(&counts);
assert!(refine_ans_histogram_precision(&counts, &incumbent).is_none());
}
}
#[test]
fn flat_and_rle_forms_reduce_header_bits() {
let flat = flat_histogram(128, 128);
assert_eq!(ans_table_bits(&flat), 12.0);
let mut freqs = vec![16u16; 128];
freqs[0] += 2048;
let histogram = AnsHistogram {
freqs,
method: 12,
omit_pos: 0,
cost: 0.0,
};
assert!(ans_table_bits(&histogram) < 100.0);
}
#[test]
fn token_bit_counter_matches_writer_exactly() {
use crate::entropy::token::{HybridUintConfig, uint_encode_with_config};
let tokens: Vec<Token> = (0..5000)
.map(|i| Token::new((i % 3 == 0) as u32, (i * 37 % 911) as u32))
.collect();
let context_map = [0u8, 1u8];
let configs = [HybridUintConfig::DEFAULT; 2];
let mut counts = [[0u32; TABLE_ENTRIES]; 2];
for token in &tokens {
let histogram = context_map[token.context as usize] as usize;
let (symbol, _, _) = uint_encode_with_config(token.value, configs[histogram]);
counts[histogram][symbol as usize] += 1;
}
let histograms: Vec<AnsHistogram> = counts
.iter()
.map(|counts| optimize_ans_histogram(counts))
.collect();
let mut reverse_maps = vec![0u16; histograms.len() * ANS_TAB_SIZE as usize];
let symbols: Vec<Vec<AnsEncSymbolInfo>> = histograms
.iter()
.enumerate()
.map(|(index, histogram)| {
let start = index * ANS_TAB_SIZE as usize;
build_symbol_info(
&histogram.freqs,
&mut reverse_maps[start..start + ANS_TAB_SIZE as usize],
)
})
.collect();
let mut writer = BitWriter::new();
write_ans_tokens(
&tokens,
&context_map,
&symbols,
&reverse_maps,
&configs,
&mut writer,
);
assert_eq!(
ans_tokens_bits(&tokens, &context_map, &symbols, &reverse_maps, &configs),
writer.bits_written()
);
let code = AnsTokenCodeRef {
context_map: &context_map,
symbol_info: &symbols,
reverse_maps: &reverse_maps,
hybrid_uint_configs: &configs,
};
assert_eq!(
ans_tokens_bits_pair(&tokens, &code, &code),
(writer.bits_written(), writer.bits_written())
);
let merged_counts: [u32; TABLE_ENTRIES] =
core::array::from_fn(|symbol| counts[0][symbol] + counts[1][symbol]);
let merged_histogram = optimize_ans_histogram(&merged_counts);
let mut merged_reverse_map = vec![0u16; ANS_TAB_SIZE as usize];
let merged_symbols = vec![build_symbol_info(
&merged_histogram.freqs,
&mut merged_reverse_map,
)];
let merged_context_map = [0u8, 0u8];
let merged_configs = [HybridUintConfig::DEFAULT];
let merged_code = AnsTokenCodeRef {
context_map: &merged_context_map,
symbol_info: &merged_symbols,
reverse_maps: &merged_reverse_map,
hybrid_uint_configs: &merged_configs,
};
let mut merged_writer = BitWriter::new();
write_ans_tokens(
&tokens,
&merged_context_map,
&merged_symbols,
&merged_reverse_map,
&merged_configs,
&mut merged_writer,
);
assert_eq!(
ans_tokens_bits_pair(&tokens, &code, &merged_code),
(writer.bits_written(), merged_writer.bits_written())
);
}
}