use alloc::vec;
use alloc::vec::Vec;
use super::bitstream::BitWriter;
pub(super) fn normalize(counts: &[u32], log: u32) -> Vec<i16> {
let total: u64 = counts.iter().map(|&c| u64::from(c)).sum();
let target = 1i32 << log;
let mut normalized = vec![0i16; counts.len()];
let mut used = 0i32;
for (symbol, &count) in counts.iter().enumerate() {
if count == 0 {
continue;
}
let scaled = (u64::from(count) * target as u64 * 2 / total).div_ceil(2);
let points = (scaled as i32).max(1);
normalized[symbol] = points as i16;
used += points;
}
while used != target {
let floor = i16::from(used > target);
let Some(symbol) = (0..counts.len())
.filter(|&s| normalized[s] > floor)
.max_by_key(|&s| normalized[s])
else {
break;
};
if used > target {
normalized[symbol] -= 1;
used -= 1;
} else {
normalized[symbol] += 1;
used += 1;
}
}
normalized
}
pub(super) fn write_description(bw: &mut BitWriter, distribution: &[i16], log: u32) {
bw.push(log - 5, 4);
let last = distribution
.iter()
.rposition(|&points| points != 0)
.unwrap_or(0);
let mut remaining = 1i32 << log;
let mut symbol = 0usize;
while symbol <= last {
let ceiling = (remaining + 1) as u32;
let bits = u32::BITS - ceiling.leading_zeros();
let threshold = (1u32 << bits) - 1 - ceiling;
let value = (distribution[symbol] + 1) as u32;
if value < threshold {
bw.push(value, bits - 1);
} else if value < 1 << (bits - 1) {
bw.push(value, bits);
} else {
bw.push(value + threshold, bits);
}
remaining -= i32::from(distribution[symbol]);
if distribution[symbol] == 0 {
let mut run = 0usize;
while symbol + 1 + run <= last && distribution[symbol + 1 + run] == 0 {
run += 1;
}
symbol += run;
loop {
if run >= 3 {
bw.push(3, 2);
run -= 3;
} else {
bw.push(run as u32, 2);
break;
}
}
}
symbol += 1;
}
}
pub(super) fn describe(distribution: &[i16], log: u32) -> Vec<u8> {
let mut bw = BitWriter::new();
write_description(&mut bw, distribution, log);
bw.finish_forward()
}
pub(super) fn log2_fixed(value: u32) -> u32 {
debug_assert!(value > 0);
let msb = u32::BITS - 1 - value.leading_zeros();
let fraction = if msb >= 8 {
value >> (msb - 8)
} else {
value << (8 - msb)
};
msb * 256 + (fraction & 0xff)
}