use crate::entropy::{HybridUintConfig, Token, uint_encode_with_config};
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 (i, &c) in code.iter().enumerate() {
permutation[i] = 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
})
}
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)),
_ => 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),
];
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: [[Vec<u32>; 3]; ORDER_SPECS.len()],
}
impl CoeffOrders {
pub(crate) fn natural() -> Self {
Self {
used_mask: 0,
orders: std::array::from_fn(|i| {
let (_, _, size) = ORDER_SPECS[i];
let natural: Vec<u32> = match size {
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!(),
};
[natural.clone(), natural.clone(), natural]
}),
}
}
}
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<[Vec<u32>; 3]>,
blocks: Vec<u32>,
}
impl OrderStats {
pub(crate) fn new() -> Self {
Self {
counts: ORDER_SPECS
.iter()
.map(|&(_, _, size)| [vec![0u32; size], vec![0u32; size], vec![0u32; size]])
.collect(),
blocks: vec![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) {
self.blocks[slot] += 1;
}
pub(crate) fn merge(&mut self, other: &Self) {
for (dst, src) in self.counts.iter_mut().zip(other.counts.iter()) {
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 = 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 rest: Vec<u32> = natural[llf..].to_vec();
rest.sort_by(|&a, &b| {
counts[b as usize]
.cmp(&counts[a as usize])
.then_with(|| a.cmp(&b))
});
let mut out = Vec::with_capacity(natural.len());
out.extend_from_slice(&natural[..llf]);
out.extend_from_slice(&rest);
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) -> CoeffOrders {
let mut out = CoeffOrders::natural();
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: [Vec<u32>; 3] = std::array::from_fn(|_| Vec::new());
let mut saved_bits = 0.0f64;
let mut cost_bits = 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 gain = stats.expected_walk(slot, channel, &natural, llf)
- stats.expected_walk(slot, channel, &candidate, llf);
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;
saved_bits += channel_saved;
cost_bits += channel_cost;
derived[channel] = candidate;
} else {
derived[channel] = natural;
}
}
if any && saved_bits > cost_bits * GATE_MARGIN {
out.used_mask |= 1 << order_index;
out.orders[slot] = derived;
}
}
out
}
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(),
order => unreachable!("unsupported natural-only order {order}"),
},
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[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:?}"
);
}
}