use alloc::vec::Vec;
use crate::{Error, Result};
const SCALE_BITS: u32 = 12;
const SCALE: u32 = 1 << SCALE_BITS; const RANS_BYTE_L: u32 = 1 << 23;
#[derive(Clone, Debug)]
pub struct FseTable {
pub freq: [u16; 256],
pub cumul: [u16; 257],
}
impl FseTable {
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;
}
let mut raw: Vec<(usize, u64, u64)> = Vec::new(); 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;
}
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;
}
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 })
}
pub fn write_to(&self, out: &mut Vec<u8>) {
for &f in &self.freq {
out.extend_from_slice(&f.to_le_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 {
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
}
}
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}");
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());
for &b in renorm.iter().rev() {
out.push(b);
}
out
}
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)
}
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
}
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)
}
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)
}
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)
}
const COMPACT_TAG: u8 = 0x01;
const FULL_TAG: u8 = 0x02;
impl FseTable {
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());
}
}
}
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))
}
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))
}
_ => {
let t = Self::read_from(data)?;
Ok((t, 512))
}
}
}
pub fn alphabet_size(&self) -> usize {
self.freq.iter().filter(|&&f| f > 0).count()
}
pub fn compact_saves(&self) -> bool {
let n = self.alphabet_size();
2 + n * 3 < 1 + 512
}
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);
}
}
}
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)
}
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;
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)
}
pub const LL_CODE_TABLE: [(u32, u8); 43] = [
(0, 0),
(1, 0),
(2, 0),
(3, 0), (4, 0),
(5, 0),
(6, 0),
(7, 0), (8, 0),
(9, 0),
(10, 0),
(11, 0), (12, 0),
(13, 0),
(14, 0),
(15, 0), (16, 1), (18, 1), (20, 1), (22, 1), (24, 2), (28, 2), (32, 3), (40, 3), (48, 4), (64, 6), (128, 7), (256, 8), (512, 9), (1024, 10), (2048, 11), (4096, 12), (8192, 13), (16384, 14), (32768, 15), (65536, 16), (131072, 17), (262144, 18), (524288, 19), (1048576, 20), (2097152, 21), (4194304, 22), (8388608, 24), ];
pub const ML_CODE_TABLE: [(u32, u8); 54] = [
(4, 0),
(5, 0),
(6, 0),
(7, 0), (8, 0),
(9, 0),
(10, 0),
(11, 0), (12, 0),
(13, 0),
(14, 0),
(15, 0), (16, 0),
(17, 0),
(18, 0),
(19, 0), (20, 0),
(21, 0),
(22, 0),
(23, 0), (24, 0),
(25, 0),
(26, 0),
(27, 0), (28, 0),
(29, 0),
(30, 0),
(31, 0), (32, 0),
(33, 0),
(34, 0),
(35, 0), (36, 1), (38, 1), (40, 2), (44, 2), (48, 3), (56, 3), (64, 4), (80, 4), (96, 5), (128, 7), (256, 8), (512, 9), (1024, 10), (2048, 11), (4096, 12), (8192, 13), (16384, 14), (32768, 15), (65536, 16), (131072, 17), (262144, 18), (524288, 20), ];
pub fn encode_ll(ll: u32) -> (u8, u32, u8) {
if ll <= 15 {
return (ll as u8, 0, 0);
}
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);
}
}
let (base, eb) = LL_CODE_TABLE[last as usize];
(last, ll.saturating_sub(base), eb)
}
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)
}
pub fn encode_ml(ml: u32) -> (u8, u32, u8) {
if ml == 0 {
return (0, 0, 0);
}
if (4..=35).contains(&ml) {
return ((ml - 3) as u8, 0, 0);
}
if ml < 4 {
return (1, 0, 0);
}
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)
}
#[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
}
}
}
pub fn decode_ml(code: u8, extra: u32) -> Result<u32> {
if code == 0 {
return Ok(0);
}
if (1..=32).contains(&code) {
return Ok(u32::from(code) + 3);
}
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)
}
pub fn encode_off_log2(offset: u32) -> (u8, u32, u8) {
if offset == 0 {
return (0, 0, 0);
}
let bits = 32 - offset.leading_zeros(); let code = bits as u8;
let extra = offset - (1u32 << (bits - 1));
let extra_bits = (bits - 1) as u8;
(code, extra, extra_bits)
}
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() {
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();
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() {
let mut counts = [0u32; 256];
counts[0] = 1; 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() {
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() {
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() {
for ml in [
0, 4, 5, 35, 36, 37, 40, 64, 128, 256, 1024, 65536, 262144, 262145, 524287, 524288,
700000, 1_048_576, ] {
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}");
}
}
}