use crate::entropy::{HybridUintConfig, Token, uint_encode_with_config};
use std::borrow::Cow;
pub(crate) const PERMUTATION_CONTEXTS: usize = 8;
#[inline]
pub(crate) fn coeff_order_context(val: u32) -> u32 {
const CFG: HybridUintConfig = HybridUintConfig {
split_exponent: 0,
msb_in_token: 0,
lsb_in_token: 0,
};
let (token, _, _) = uint_encode_with_config(val, CFG);
token.min(PERMUTATION_CONTEXTS as u32 - 1)
}
pub(crate) fn compute_lehmer_code(permutation: &[u32], code: &mut [u32]) {
let n = permutation.len();
debug_assert_eq!(code.len(), n);
let mut temp = vec![0u32; n + 1];
for (idx, &s) in permutation.iter().enumerate() {
let mut penalty = 0u32;
let mut i = s + 1;
while i != 0 {
penalty += temp[i as usize];
i &= i - 1; }
debug_assert!(s >= penalty, "not a permutation at {idx}");
code[idx] = s - penalty;
let mut i = s + 1;
while (i as usize) < n + 1 {
temp[i as usize] += 1;
i += i & i.wrapping_neg(); }
}
}
#[cfg(test)]
pub(crate) fn decode_lehmer_code(code: &[u32], permutation: &mut [u32]) {
let n = code.len();
let mut available: Vec<u32> = (0..n as u32).collect();
for (&c, perm) in code.iter().zip(permutation.iter_mut()) {
*perm = available.remove(c as usize);
}
}
pub(crate) fn tokenize_permutation(zigzag: &[u32], skip: usize, tokens: &mut Vec<Token>) {
let size = zigzag.len();
let mut lehmer = vec![0u32; size];
compute_lehmer_code(zigzag, &mut lehmer);
let mut end = size;
while end > skip && lehmer[end - 1] == 0 {
end -= 1;
}
tokens.push(Token::new(
coeff_order_context(size as u32),
(end - skip) as u32,
));
let mut last = 0u32;
for &l in &lehmer[skip..end] {
tokens.push(Token::new(coeff_order_context(last), l));
last = l;
}
}
pub(crate) static ORDER_SPECS: [(usize, usize, usize); 6] = [
(0, 1, 64),
(1, 1, 64),
(2, 4, 256),
(3, 16, 1024),
(4, 2, 128),
(6, 8, 512),
];
fn natural_scan_64() -> &'static [u32] {
static SCAN: std::sync::OnceLock<Vec<u32>> = std::sync::OnceLock::new();
SCAN.get_or_init(|| {
const SIDE: usize = 64;
const LLF: usize = 8;
let mut out = Vec::with_capacity(SIDE * SIDE);
for y in 0..LLF {
for x in 0..LLF {
out.push((y * SIDE + x) as u32);
}
}
for sum in 0..=(2 * (SIDE - 1)) {
let lo = sum.saturating_sub(SIDE - 1);
let hi = sum.min(SIDE - 1);
if sum % 2 == 0 {
for x in lo..=hi {
let y = sum - x;
if x >= LLF || y >= LLF {
out.push((y * SIDE + x) as u32);
}
}
} else {
for x in (lo..=hi).rev() {
let y = sum - x;
if x >= LLF || y >= LLF {
out.push((y * SIDE + x) as u32);
}
}
}
}
debug_assert_eq!(out.len(), SIDE * SIDE);
out
})
}
fn natural_scan_64x32() -> &'static [u32] {
static SCAN: std::sync::OnceLock<Vec<u32>> = std::sync::OnceLock::new();
SCAN.get_or_init(|| {
let mut out = vec![0u32; 2048];
let mut cur = 32usize;
for diagonal in 0..64usize {
for j in 0..=diagonal {
let (mut x, mut y) = (j, diagonal - j);
if diagonal & 1 != 0 {
std::mem::swap(&mut x, &mut y);
}
if y & 1 == 0 {
y >>= 1;
let position = if x < 8 && y < 4 {
y * 8 + x
} else {
let position = cur;
cur += 1;
position
};
out[position] = (y * 64 + x) as u32;
}
}
}
for ip in (1..64usize).rev() {
let diagonal = ip - 1;
for j in 0..=diagonal {
let (mut x, mut y) = (63 - (diagonal - j), 63 - j);
if diagonal & 1 != 0 {
std::mem::swap(&mut x, &mut y);
}
if y & 1 == 0 {
y >>= 1;
out[cur] = (y * 64 + x) as u32;
cur += 1;
}
}
}
debug_assert_eq!(cur, 2048);
out
})
}
fn natural_scan_generic(cx: usize, cy: usize) -> Vec<u32> {
let size = cx * cy * 64;
let side = cx * 8;
let xs = cx / cy;
let xsm = xs - 1;
let xss = xs.trailing_zeros() as usize;
let mut out = vec![0u32; size];
let mut cur = cx * cy;
for i in 0..side {
for j in 0..=i {
let (mut x, mut y) = (j, i - j);
if i % 2 != 0 {
std::mem::swap(&mut x, &mut y);
}
if y & xsm != 0 {
continue;
}
y >>= xss;
let val = if x < cx && y < cy {
y * cx + x
} else {
cur += 1;
cur - 1
};
out[val] = (y * side + x) as u32;
}
}
for ip in (1..side).rev() {
let i = ip - 1;
for j in 0..=i {
let (mut x, mut y) = (side - 1 - (i - j), side - 1 - j);
if i % 2 != 0 {
std::mem::swap(&mut x, &mut y);
}
if y & xsm != 0 {
continue;
}
y >>= xss;
out[cur] = (y * side + x) as u32;
cur += 1;
}
}
debug_assert_eq!(cur, size);
out
}
fn natural_scan_128() -> &'static [u32] {
static SCAN: std::sync::OnceLock<Vec<u32>> = std::sync::OnceLock::new();
SCAN.get_or_init(|| natural_scan_generic(16, 16))
}
fn natural_scan_128x64() -> &'static [u32] {
static SCAN: std::sync::OnceLock<Vec<u32>> = std::sync::OnceLock::new();
SCAN.get_or_init(|| natural_scan_generic(16, 8))
}
pub(crate) fn natural_position_lut(size: usize) -> Vec<u32> {
use crate::ac_context::{
K_COEFF_ORDER_8X8, K_COEFF_ORDER_16X8, K_COEFF_ORDER_16X16, K_COEFF_ORDER_32X16,
K_COEFF_ORDER_32X32,
};
let mut lut = vec![0u32; size];
let mut set = |scan_pos: usize, raw: usize| lut[raw] = scan_pos as u32;
match size {
64 => K_COEFF_ORDER_8X8
.iter()
.enumerate()
.for_each(|(k, &r)| set(k, r as usize)),
128 => K_COEFF_ORDER_16X8
.iter()
.enumerate()
.for_each(|(k, &r)| set(k, r as usize)),
256 => K_COEFF_ORDER_16X16
.iter()
.enumerate()
.for_each(|(k, &r)| set(k, r as usize)),
512 => K_COEFF_ORDER_32X16
.iter()
.enumerate()
.for_each(|(k, &r)| set(k, r as usize)),
1024 => K_COEFF_ORDER_32X32
.iter()
.enumerate()
.for_each(|(k, &r)| set(k, r as usize)),
2048 => natural_scan_64x32()
.iter()
.enumerate()
.for_each(|(k, &r)| set(k, r as usize)),
4096 => natural_scan_64()
.iter()
.enumerate()
.for_each(|(k, &r)| set(k, r as usize)),
8192 => natural_scan_128x64()
.iter()
.enumerate()
.for_each(|(k, &r)| set(k, r as usize)),
16384 => natural_scan_128()
.iter()
.enumerate()
.for_each(|(k, &r)| set(k, r as usize)),
_ => unreachable!("no natural order table for size {size}"),
}
lut
}
pub(crate) fn scan_pos_lut(width: usize, height: usize) -> &'static [u32] {
type ShapeLuts = Vec<((usize, usize), Vec<u32>)>;
static LUTS: std::sync::OnceLock<ShapeLuts> = std::sync::OnceLock::new();
let luts = LUTS.get_or_init(|| {
let shapes = [
(8, 8),
(16, 8),
(8, 16),
(16, 16),
(32, 16),
(16, 32),
(32, 32),
(64, 32),
(32, 64),
(64, 64),
(128, 64),
(64, 128),
(128, 128),
];
shapes
.iter()
.map(|&(w, h)| {
let size = w * h;
let lut = if w >= h {
natural_position_lut(size)
} else {
let c = natural_position_lut(size);
let mut t = vec![0u32; size];
for y in 0..h {
for x in 0..w {
t[y * w + x] = c[x * h + y];
}
}
t
};
((w, h), lut)
})
.collect()
});
&luts
.iter()
.find(|(shape, _)| *shape == (width, height))
.expect("scan lut shape")
.1
}
pub(crate) struct CoeffOrders {
pub(crate) used_mask: u16,
pub(crate) orders: [[Cow<'static, [u32]>; 3]; ORDER_SPECS.len()],
}
impl CoeffOrders {
pub(crate) fn natural() -> Self {
static NATURAL: std::sync::OnceLock<[Vec<u32>; 5]> = std::sync::OnceLock::new();
let natural = NATURAL.get_or_init(|| {
std::array::from_fn(|i| match [64, 128, 256, 512, 1024][i] {
64 => crate::ac_context::K_COEFF_ORDER_8X8
.iter()
.map(|&r| r as u32)
.collect(),
128 => crate::ac_context::K_COEFF_ORDER_16X8
.iter()
.map(|&r| r as u32)
.collect(),
256 => crate::ac_context::K_COEFF_ORDER_16X16
.iter()
.map(|&r| r as u32)
.collect(),
512 => crate::ac_context::K_COEFF_ORDER_32X16
.iter()
.map(|&r| r as u32)
.collect(),
1024 => crate::ac_context::K_COEFF_ORDER_32X32
.iter()
.map(|&r| r as u32)
.collect(),
_ => unreachable!(),
})
});
Self {
used_mask: 0,
orders: std::array::from_fn(|i| {
let slot = match ORDER_SPECS[i].2 {
64 => 0,
128 => 1,
256 => 2,
512 => 3,
1024 => 4,
_ => unreachable!(),
};
std::array::from_fn(|_| Cow::Borrowed(natural[slot].as_slice()))
}),
}
}
}
pub(crate) fn write_coeff_orders(
orders: &CoeffOrders,
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
w: &mut crate::bit_writer::BitWriter,
) {
w.write(2, 3);
w.write(13, u64::from(orders.used_mask));
if orders.used_mask == 0 {
return;
}
let mut tokens: Vec<Token> = Vec::new();
for (i, &(order_index, llf, size)) in ORDER_SPECS.iter().enumerate() {
if orders.used_mask & (1 << order_index) == 0 {
continue;
}
let natural_pos = natural_position_lut(size);
for channel_order in &orders.orders[i] {
debug_assert_eq!(channel_order.len(), size);
let zigzag: Vec<u32> = channel_order
.iter()
.map(|&raw| natural_pos[raw as usize])
.collect();
tokenize_permutation(&zigzag, llf, &mut tokens);
}
}
let code = crate::entropy::optimize_entropy_code(&tokens, PERMUTATION_CONTEXTS, huffman_pool);
let code_ref = code.as_ref();
w.write(1, 0); crate::entropy::write_entropy_code(&code_ref, huffman_pool, w);
for t in &tokens {
crate::entropy::write_token(*t, &code_ref, w);
}
}
#[inline]
pub(crate) fn order_slot_of(strategy_code: u8) -> Option<usize> {
let group = crate::ac_context::K_STRATEGY_ORDER[strategy_code as usize] as usize;
ORDER_SPECS.iter().position(|&(g, _, _)| g == group)
}
pub(crate) struct OrderStats {
counts: [[Vec<u32>; 3]; ORDER_SPECS.len()],
blocks: [u32; ORDER_SPECS.len()],
}
impl OrderStats {
pub(crate) fn new() -> Self {
Self {
counts: std::array::from_fn(|_| std::array::from_fn(|_| Vec::new())),
blocks: [0u32; ORDER_SPECS.len()],
}
}
#[inline]
pub(crate) fn tally(&mut self, slot: usize, channel: usize, raw_index: usize) {
self.counts[slot][channel][raw_index] += 1;
}
#[inline]
pub(crate) fn tally_block(&mut self, slot: usize) {
if self.counts[slot][0].is_empty() {
self.counts[slot] = std::array::from_fn(|_| vec![0u32; ORDER_SPECS[slot].2]);
}
self.blocks[slot] += 1;
}
pub(crate) fn merge(&mut self, other: &Self) {
for (dst, src) in self.counts.iter_mut().zip(other.counts.iter()) {
if src[0].is_empty() {
continue;
}
if dst[0].is_empty() {
dst.clone_from(src);
continue;
}
for (d, s) in dst.iter_mut().zip(src.iter()) {
for (a, &b) in d.iter_mut().zip(s.iter()) {
*a += b;
}
}
}
for (d, &s) in self.blocks.iter_mut().zip(other.blocks.iter()) {
*d += s;
}
}
pub(crate) fn blocks_in(&self, slot: usize) -> u32 {
self.blocks[slot]
}
fn expected_walk(&self, slot: usize, channel: usize, order: &[u32], llf: usize) -> f64 {
let blocks = 1.0 / self.blocks[slot].max(1) as f64;
let counts = &self.counts[slot][channel];
let mut none_at_or_after = 1.0f64;
let mut expected = 0.0f64;
for &raw in order[llf..].iter().rev() {
expected += 1.0 - none_at_or_after;
let p = (counts[raw as usize] as f64 * blocks).clamp(0.0, 1.0);
none_at_or_after *= 1.0 - p;
}
expected
}
fn derive(&self, slot: usize, channel: usize, natural: &[u32], llf: usize) -> Vec<u32> {
let counts = &self.counts[slot][channel];
let mut ranked: Vec<u64> = natural
.iter()
.enumerate()
.skip(llf)
.map(|(rank, &raw)| (u64::from(u32::MAX - counts[raw as usize]) << 32) | rank as u64)
.collect();
ranked.sort_unstable();
let mut out = Vec::with_capacity(natural.len());
out.extend_from_slice(&natural[..llf]);
out.extend(ranked.into_iter().map(|key| natural[(key as u32) as usize]));
out
}
}
const MIN_BLOCKS_FOR_ORDER: u32 = 64;
const BITS_PER_SAVED_TOKEN: f64 = 0.2;
const GATE_MARGIN: f64 = 1.5;
const BITS_PER_PERMUTATION_TOKEN: f64 = 5.0;
pub(crate) fn derive_orders(stats: &OrderStats, out: &mut CoeffOrders) -> f64 {
debug_assert_eq!(out.used_mask, 0);
let (mut natural_walk, mut saved_walk) = (0.0f64, 0.0f64);
for (slot, &(order_index, llf, _size)) in ORDER_SPECS.iter().enumerate() {
let blocks = stats.blocks_in(slot);
if blocks < MIN_BLOCKS_FOR_ORDER {
continue;
}
let mut derived: [Cow<'static, [u32]>; 3] = std::array::from_fn(|_| Cow::Borrowed(&[][..]));
let mut saved_bits = 0.0f64;
let mut cost_bits = 0.0f64;
let mut slot_saved_walk = 0.0f64;
let mut any = false;
for channel in 0..3 {
let natural = out.orders[slot][channel].clone();
let candidate = stats.derive(slot, channel, &natural, llf);
let walk = stats.expected_walk(slot, channel, &natural, llf);
let gain = walk - stats.expected_walk(slot, channel, &candidate, llf);
natural_walk += walk * f64::from(blocks);
let mut tokens = Vec::new();
let natural_pos = natural_position_lut(natural.len());
let zigzag: Vec<u32> = candidate
.iter()
.map(|&raw| natural_pos[raw as usize])
.collect();
tokenize_permutation(&zigzag, llf, &mut tokens);
let channel_saved = gain * f64::from(blocks) * BITS_PER_SAVED_TOKEN;
let channel_cost = tokens.len() as f64 * BITS_PER_PERMUTATION_TOKEN;
if gain > 0.0 && channel_saved > channel_cost * GATE_MARGIN {
any = true;
slot_saved_walk += gain * f64::from(blocks);
saved_bits += channel_saved;
cost_bits += channel_cost;
derived[channel] = Cow::Owned(candidate);
} else {
derived[channel] = natural;
}
}
if any && saved_bits > cost_bits * GATE_MARGIN {
out.used_mask |= 1 << order_index;
out.orders[slot] = derived;
saved_walk += slot_saved_walk;
}
}
if natural_walk > 0.0 {
saved_walk / natural_walk
} else {
0.0
}
}
pub(crate) fn propose_orders(stats: &OrderStats, out: &mut CoeffOrders) {
debug_assert_eq!(out.used_mask, 0);
for (slot, &(order_index, llf, _)) in ORDER_SPECS.iter().enumerate() {
if stats.blocks_in(slot) < MIN_BLOCKS_FOR_ORDER {
continue;
}
for channel in 0..3 {
let natural = &out.orders[slot][channel];
let candidate = stats.derive(slot, channel, natural, llf);
if candidate.as_slice() != natural.as_ref() {
out.orders[slot][channel] = Cow::Owned(candidate);
out.used_mask |= 1 << order_index;
}
}
}
}
impl CoeffOrders {
#[inline]
pub(crate) fn scan_for(&self, strategy_code: u8, channel: usize) -> &[u32] {
match order_slot_of(strategy_code) {
Some(slot) => &self.orders[slot][channel],
None => match crate::ac_context::K_STRATEGY_ORDER[strategy_code as usize] {
7 => natural_scan_64(),
8 => natural_scan_64x32(),
9 => natural_scan_128(),
10 => natural_scan_128x64(),
order => unreachable!("unsupported natural-only order {order}"),
},
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn entropy_candidates_do_not_use_the_walk_or_permutation_gate() {
let mut stats = OrderStats::new();
for _ in 0..MIN_BLOCKS_FOR_ORDER {
stats.tally_block(0);
}
stats.counts[0][0].fill(32);
let natural = CoeffOrders::natural();
let last = *natural.orders[0][0].last().unwrap() as usize;
stats.counts[0][0][last] = 33;
let mut gated = CoeffOrders::natural();
derive_orders(&stats, &mut gated);
assert_eq!(gated.used_mask, 0);
let mut proposed = CoeffOrders::natural();
propose_orders(&stats, &mut proposed);
assert_eq!(proposed.used_mask, 1);
assert_eq!(proposed.orders[0][0][0], natural.orders[0][0][0]);
assert_eq!(proposed.orders[0][0][1], last as u32);
assert_eq!(proposed.orders[0][1..], natural.orders[0][1..]);
assert_eq!(proposed.orders[1..], natural.orders[1..]);
stats.blocks[0] -= 1;
let mut sparse = CoeffOrders::natural();
propose_orders(&stats, &mut sparse);
assert_eq!(sparse.used_mask, 0);
}
#[test]
fn sparse_order_statistics_preserve_dense_counts_and_derived_scans() {
let mut rng = 73u32;
for case in 0..32 {
let mut expected = OrderStats {
counts: std::array::from_fn(|slot| {
std::array::from_fn(|_| vec![0u32; ORDER_SPECS[slot].2])
}),
blocks: [0; ORDER_SPECS.len()],
};
let mut actual = OrderStats::new();
assert!(actual.counts.iter().flatten().all(Vec::is_empty));
for group in 0..16 {
let mut part = OrderStats::new();
for (slot, &(_, _, size)) in ORDER_SPECS.iter().enumerate() {
if (slot + case + group).is_multiple_of(3) {
continue;
}
let blocks = (case * 17 + group * 13 + slot * 7) % 129;
for _ in 0..blocks {
part.tally_block(slot);
expected.blocks[slot] += 1;
for channel in 0..3 {
for _ in 0..4 {
rng = rng.wrapping_mul(1664525).wrapping_add(1013904223);
let raw = rng as usize % size;
part.tally(slot, channel, raw);
expected.counts[slot][channel][raw] += 1;
}
}
}
}
actual.merge(&part);
}
assert_eq!(actual.blocks, expected.blocks);
for slot in 0..ORDER_SPECS.len() {
for channel in 0..3 {
if actual.counts[slot][channel].is_empty() {
assert!(expected.counts[slot][channel].iter().all(|&v| v == 0));
} else {
assert_eq!(actual.counts[slot][channel], expected.counts[slot][channel]);
}
}
}
let mut expected_orders = CoeffOrders::natural();
let mut actual_orders = CoeffOrders::natural();
assert_eq!(
derive_orders(&actual, &mut actual_orders).to_bits(),
derive_orders(&expected, &mut expected_orders).to_bits()
);
assert_eq!(actual_orders.used_mask, expected_orders.used_mask);
assert_eq!(actual_orders.orders, expected_orders.orders);
}
let mut empty = OrderStats::new();
empty.merge(&OrderStats::new());
assert!(empty.counts.iter().flatten().all(Vec::is_empty));
let mut only_dct8 = OrderStats::new();
only_dct8.tally_block(0);
only_dct8.tally(0, 1, 63);
empty.merge(&only_dct8);
assert!(empty.counts[1..].iter().flatten().all(Vec::is_empty));
assert_eq!(empty.counts[0][1][63], 1);
}
#[test]
fn natural_scans_are_shared_and_learned_scans_stay_local() {
let natural = CoeffOrders::natural();
let mut learned = CoeffOrders::natural();
let mut stats = OrderStats::new();
for slot in 0..ORDER_SPECS.len() {
for c in 0..3 {
assert!(matches!(learned.orders[slot][c], Cow::Borrowed(_)));
assert!(std::ptr::eq(
natural.orders[slot][0].as_ptr(),
learned.orders[slot][c].as_ptr()
));
}
stats.tally_block(slot);
stats.blocks[slot] = 10_000;
let raw = *natural.orders[slot][0].last().unwrap() as usize;
stats.counts[slot][0][raw] = 10_000;
}
let moved = derive_orders(&stats, &mut learned);
assert!((0.0..=1.0).contains(&moved) && moved > 0.0, "{moved}");
assert_ne!(learned.used_mask, 0);
assert_eq!(natural.used_mask, 0);
for (slot, &(order, _, _)) in ORDER_SPECS.iter().enumerate() {
assert_ne!(learned.used_mask & (1 << order), 0);
assert!(matches!(learned.orders[slot][0], Cow::Owned(_)));
assert_ne!(learned.orders[slot][0], natural.orders[slot][0]);
for c in 1..3 {
assert!(matches!(learned.orders[slot][c], Cow::Borrowed(_)));
assert_eq!(learned.orders[slot][c], natural.orders[slot][c]);
}
}
}
#[test]
fn dct64x32_natural_scan_is_a_permutation_with_llf_first() {
let scan = natural_scan_64x32();
assert_eq!(scan.len(), 2048);
let mut sorted = scan.to_vec();
sorted.sort_unstable();
assert!(sorted.iter().enumerate().all(|(i, &v)| i as u32 == v));
for y in 0..4 {
for x in 0..8 {
assert_eq!(scan[y * 8 + x], (y * 64 + x) as u32);
}
}
}
#[test]
fn identity_permutation_lehmer_is_all_zeros() {
for n in [8usize, 64, 256] {
let perm: Vec<u32> = (0..n as u32).collect();
let mut code = vec![0u32; n];
compute_lehmer_code(&perm, &mut code);
assert!(code.iter().all(|&c| c == 0), "n={n}: {code:?}");
}
}
#[test]
fn lehmer_code_round_trips() {
let mut state = 12345u32;
for n in [4usize, 16, 64, 128] {
let mut perm: Vec<u32> = (0..n as u32).collect();
for i in (1..n).rev() {
state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
perm.swap(i, (state >> 8) as usize % (i + 1));
}
let mut code = vec![0u32; n];
compute_lehmer_code(&perm, &mut code);
let mut back = vec![0u32; n];
decode_lehmer_code(&code, &mut back);
assert_eq!(perm, back, "n={n}");
}
}
#[test]
fn natural_order_tokenizes_to_one_token() {
let perm: Vec<u32> = (0..64).collect();
let mut tokens = Vec::new();
tokenize_permutation(&perm, 1, &mut tokens);
assert_eq!(tokens.len(), 1, "{tokens:?}");
assert_eq!(tokens[0].value, 0, "trimmed length must be 0");
}
#[test]
fn coeff_order_context_matches_libjxl() {
assert_eq!(coeff_order_context(0), 0);
assert_eq!(coeff_order_context(1), 1);
assert_eq!(coeff_order_context(2), 2);
assert_eq!(coeff_order_context(3), 2);
assert_eq!(coeff_order_context(4), 3);
assert_eq!(coeff_order_context(7), 3);
assert_eq!(coeff_order_context(8), 4);
assert_eq!(coeff_order_context(1 << 6), 7);
assert_eq!(coeff_order_context(1 << 20), 7, "must clamp");
}
#[test]
fn single_swap_has_one_nonzero_lehmer_entry() {
let mut perm: Vec<u32> = (0..16).collect();
perm.swap(3, 4);
let mut code = vec![0u32; 16];
compute_lehmer_code(&perm, &mut code);
assert_eq!(code[3], 1);
assert!(
code.iter().enumerate().all(|(i, &c)| i == 3 || c == 0),
"{code:?}"
);
}
#[test]
fn packed_coefficient_order_matches_stable_frequency_order() {
let mut rng = 0x93ab2017u32;
for n in [1, 2, 7, 64, 128, 4096] {
let mut natural: Vec<u32> = (0..n as u32).collect();
for i in (1..n).rev() {
rng = rng.wrapping_mul(1664525).wrapping_add(1013904223);
natural.swap(i, rng as usize % (i + 1));
}
for pattern in 0..4 {
let counts: Vec<u32> = (0..n)
.map(|i| match pattern {
0 => 0,
1 => u32::MAX,
2 => (i % 7) as u32,
_ => {
rng = rng.wrapping_mul(1664525).wrapping_add(1013904223);
rng
}
})
.collect();
let stats = OrderStats {
counts: std::array::from_fn(|slot| {
std::array::from_fn(|_| {
if slot == 0 {
counts.clone()
} else {
Vec::new()
}
})
}),
blocks: [1; ORDER_SPECS.len()],
};
for llf in [0, 1, n / 3, n] {
let mut expected = natural.clone();
expected[llf..].sort_by_key(|&raw| std::cmp::Reverse(counts[raw as usize]));
assert_eq!(
stats.derive(0, 0, &natural, llf),
expected,
"n={n} llf={llf} pattern={pattern}"
);
}
}
}
}
}