use super::DequantBias;
use crate::Arbiter;
use crate::ac_context::{
fine_block_context, fine_non_zero_context, fine_zero_density_contexts_offset,
zero_density_context, zero_density_context_8x8,
};
use crate::entropy::{FrozenTokenPrices, Token, pack_signed};
use crate::image::Image3F;
use crate::util::FastRound;
#[cfg(test)]
use crate::util::heap_array;
const RDOQ_MAX_STRIDE: usize = 2 * (256 + 1);
#[inline]
pub(crate) fn rdoq_channel_weights(coding: crate::CodingTransform) -> [f32; 3] {
match coding {
crate::CodingTransform::YCbCr => coding.channel_weights(),
crate::CodingTransform::Xyb | crate::CodingTransform::Rgb => {
crate::inflated_cost::CHANNEL_WEIGHT
}
}
}
const RDOQ_MAX_CHOICES: usize = 64 * RDOQ_MAX_STRIDE;
const RDOQ_MAX_NZERO_DELTA: usize = 6;
const RDOQ_BAND_STRIDE: usize = 2 * (2 * RDOQ_MAX_NZERO_DELTA + 2);
#[inline]
fn rdoq_candidates(ideal: f32, current: i32, restore: bool) -> ([i32; 5], usize) {
if !restore {
let toward_zero = current - current.signum();
return match (current, toward_zero) {
(0, _) => ([0; 5], 1),
(_, 0) => ([current, 0, 0, 0, 0], 2),
_ => ([current, toward_zero, 0, 0, 0], 3),
};
}
let rounded = ideal.fast_round() as i32;
if ideal.abs() > 2.5 && (ideal - rounded as f32).abs() < 0.25 {
return ([current; 5], 1);
}
let proposed = [
current,
0,
rounded,
rounded.saturating_sub(1),
rounded.saturating_add(1),
];
let mut candidates = [current; 5];
let mut len = 0;
for level in proposed {
if !candidates[..len].contains(&level) {
candidates[len] = level;
len += 1;
}
}
(candidates, len)
}
#[inline]
fn rdoq_distortion_weight(window_index: usize, window_len: usize, distance: f32) -> f32 {
let scan_position = window_index as f32 / window_len.max(1) as f32;
let strength = (distance - 2.0).clamp(0.0, 1.0);
1.0 + strength * (1.0 - scan_position).powi(2)
}
#[inline]
pub(crate) fn rdoq_lambda(arbiter: Arbiter, qf_ratio: f32) -> f32 {
crate::ac_strategy::RD_LAMBDA * 0.25 * arbiter.tuning().rdoq_lambda * qf_ratio.clamp(0.5, 2.0)
}
#[inline(always)]
fn update_rdoq_state_pair(
distortion: f32,
token_cost: [f32; 2],
tail: f32,
candidate: u8,
current: &mut [f32; 2],
choices: &mut [u8; 2],
) {
#[cfg(all(target_arch = "aarch64", feature = "neon", target_feature = "neon"))]
{
use std::arch::aarch64::*;
unsafe {
let cost = vadd_f32(
vadd_f32(vdup_n_f32(distortion), vld1_f32(token_cost.as_ptr())),
vdup_n_f32(tail),
);
let old = vld1_f32(current.as_ptr());
let better = vclt_f32(cost, old);
vst1_f32(current.as_mut_ptr(), vbsl_f32(better, cost, old));
let mask16 = vmovn_u32(vcombine_u32(better, better));
let mask8 = vmovn_u16(vcombine_u16(mask16, mask16));
let mask = vget_lane_u16::<0>(vreinterpret_u16_u8(mask8));
let old_choice = u16::from_ne_bytes(*choices);
let new_choice = u16::from_ne_bytes([candidate; 2]);
*choices = ((new_choice & mask) | (old_choice & !mask)).to_ne_bytes();
}
}
#[cfg(not(all(target_arch = "aarch64", feature = "neon", target_feature = "neon")))]
for prev in 0..2 {
let cost = distortion + token_cost[prev] + tail;
if cost < current[prev] {
current[prev] = cost;
choices[prev] = candidate;
}
}
}
fn rdoq_window_len(covered_blocks: usize) -> (usize, usize) {
if covered_blocks == 1 {
(63, 20)
} else {
(
(64 * covered_blocks).min(1024),
(24 * covered_blocks).min(256),
)
}
}
pub(super) const RESTORE_FEW_COLORS_PER_BLOCK: usize = 24;
pub(super) const RESTORE_FEW_COLORS_PENALTY: f32 = 2.0;
pub(super) fn few_colors(
opsin: &Image3F,
x0: usize,
y0: usize,
x1: usize,
y1: usize,
limit: usize,
seen: &mut Vec<u64>,
) -> bool {
let key_at = |rows: &[&[f32]; 3], x: usize| {
rows.iter().fold(0u64, |k, r| {
(k << 21) | (((r[x] * 1024.0) + 0.5) as i64 as u64 & 0x1f_ffff)
})
};
const EMPTY: u64 = u64::MAX;
let capacity = (2 * (limit + 1)).next_power_of_two().max(16);
let shift = 64 - capacity.trailing_zeros();
let mask = capacity - 1;
seen.clear();
seen.resize(capacity, EMPTY);
let mut distinct = 0usize;
let few = 'scan: {
for y in y0..y1 {
let rows = [
opsin.plane_row(0, y),
opsin.plane_row(1, y),
opsin.plane_row(2, y),
];
for x in x0..x1 {
let key = key_at(&rows, x);
let mut slot = (key.wrapping_mul(0x9E37_79B9_7F4A_7C15) >> shift) as usize;
loop {
let held = seen[slot];
if held == key {
break;
}
if held == EMPTY {
if distinct == limit {
break 'scan false;
}
seen[slot] = key;
distinct += 1;
break;
}
slot = (slot + 1) & mask;
}
}
}
true
};
seen.clear();
few
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum RdoqSearch {
Greedy,
Beam,
Trellis,
}
impl RdoqSearch {
pub(crate) fn of(effort: &crate::effort::Effort) -> Self {
if effort.rdoq_trellis {
Self::Trellis
} else if effort.rdoq_beam {
Self::Beam
} else {
Self::Greedy
}
}
}
const RDOQ_BEAM_WIDTH: usize = 3;
#[allow(clippy::too_many_arguments)]
pub(super) fn rdoq_block(
channel_weight: f32,
prices: &FrozenTokenPrices,
scan: &[u32],
source: &[f32],
inv_qm: &[f32],
q_scaled: f32,
block: &mut [i32],
raw_strategy: u8,
strategy_code: u8,
c: usize,
bias: DequantBias,
predicted: u8,
cx: usize,
cy: usize,
distance: f32,
qf_hi: bool,
lambda: f32,
restore_penalty: f32,
search: RdoqSearch,
scratch: &mut RdoqScratch,
) {
let covered_blocks = cx * cy;
let (window_cap, restore_len) = rdoq_window_len(covered_blocks);
if search == RdoqSearch::Beam {
let choices = scratch.choices(window_cap * (2 * RDOQ_BEAM_WIDTH));
rdoq_block_beam::<RDOQ_BEAM_WIDTH>(
channel_weight,
window_cap,
restore_len,
prices,
scan,
source,
inv_qm,
q_scaled,
block,
strategy_code,
c,
bias,
predicted,
cx,
cy,
distance,
qf_hi,
lambda,
restore_penalty,
choices,
);
return;
}
if search == RdoqSearch::Greedy {
rdoq_block_greedy(
channel_weight,
window_cap,
restore_len,
prices,
scan,
source,
inv_qm,
q_scaled,
block,
strategy_code,
c,
bias,
predicted,
cx,
cy,
distance,
qf_hi,
lambda,
restore_penalty,
);
return;
}
let legacy_limit = window_cap <= 64 && !crate::dc_group_data::is_128_strategy(raw_strategy);
let (choices, costs) = scratch.trellis(window_cap);
macro_rules! refine {
($factored:literal, $single_block:literal) => {
rdoq_block_banded::<$factored, $single_block>(
channel_weight,
window_cap,
restore_len,
legacy_limit,
prices,
scan,
source,
inv_qm,
q_scaled,
block,
strategy_code,
c,
bias,
predicted,
cx,
cy,
distance,
qf_hi,
lambda,
restore_penalty,
choices,
costs,
)
};
}
if covered_blocks == 1 {
refine!(true, true);
} else {
refine!(true, false);
}
}
#[allow(clippy::too_many_arguments)]
fn rdoq_block_greedy(
channel_weight: f32,
window_cap: usize,
restore_len: usize,
prices: &FrozenTokenPrices,
scan: &[u32],
source: &[f32],
inv_qm: &[f32],
q_scaled: f32,
block: &mut [i32],
strategy_code: u8,
c: usize,
bias: DequantBias,
predicted: u8,
cx: usize,
cy: usize,
distance: f32,
qf_hi: bool,
lambda: f32,
restore_penalty: f32,
) {
let covered_blocks = cx * cy;
let size = block.len();
let available = size
.checked_sub(covered_blocks)
.expect("LLF positions fit in the block");
let window_len = window_cap.min(available);
let search_end = covered_blocks + window_len;
let base_window_len = (24 * covered_blocks).min(64).min(available);
let block_ctx = fine_block_context(c, strategy_code, qf_hi);
let histo_offset = fine_zero_density_contexts_offset(block_ctx);
let log2_covered_blocks = covered_blocks.trailing_zeros() as usize;
let context = |remaining: usize, k: usize, prev: usize| -> u32 {
histo_offset
+ if covered_blocks == 1 {
zero_density_context_8x8(remaining, k, prev) as u32
} else {
zero_density_context(remaining, k, covered_blocks, log2_covered_blocks, prev) as u32
}
};
let nzero_ctx = fine_non_zero_context(predicted as u32, block_ctx);
let nonzero_at = |block: &[i32], k: usize| block[scan[k] as usize] != 0;
let initial_prev = |count: usize| usize::from(count <= size / 16);
let channel_scale = if c == 1 {
1.0
} else {
chroma_rdoq_weight(distance)
};
let mut remaining_after = (search_end..size).filter(|&k| nonzero_at(block, k)).count();
let mut total = remaining_after
+ (covered_blocks..search_end)
.filter(|&k| nonzero_at(block, k))
.count();
for window_index in (0..window_len).rev() {
let k = covered_blocks + window_index;
let idx = scan[k] as usize;
let current = block[idx];
let ideal = source[idx] * inv_qm[idx] * q_scaled;
let (candidates, candidate_count) =
rdoq_candidates(ideal, current, window_index < restore_len);
let original_nz = usize::from(current != 0);
if candidate_count == 1 || (current == 0 && remaining_after == 0) {
remaining_after += original_nz;
continue;
}
let distortion_weight = channel_weight
* channel_scale
* rdoq_distortion_weight(window_index.min(base_window_len), base_window_len, distance);
let others = total - original_nz;
let previous_nonzero = if k == covered_blocks {
0 } else {
usize::from(nonzero_at(block, k - 1))
};
let run_bits = if remaining_after == 0 {
let mut start = k;
while start > covered_blocks && !nonzero_at(block, start - 1) {
start -= 1;
}
(start..k)
.map(|j| {
let prev = if j > start {
0
} else if j > covered_blocks {
1
} else {
initial_prev(others + 1)
};
prices.token_bits(Token::new(context(1, j, prev), 0))
})
.sum::<f32>()
} else {
0.0
};
let mut best = (f32::INFINITY, current);
for &level in &candidates[..candidate_count] {
let nonzero = usize::from(level != 0);
let remaining = remaining_after + nonzero;
let prev = if k == covered_blocks {
initial_prev(others + nonzero)
} else {
previous_nonzero
};
let rate = if current == 0 && level != 0 {
lambda * restore_penalty
} else {
lambda
};
let token_bits = if remaining == 0 {
0.0
} else {
prices.token_bits(Token::new(context(remaining, k, prev), pack_signed(level)))
+ if nonzero == 1 { run_bits } else { 0.0 }
};
let count_bits = prices.token_bits(Token::new(nzero_ctx, (others + nonzero) as u32));
let cost = distortion_weight * (ideal - bias.level(level)).powi(2)
+ rate * token_bits
+ lambda * count_bits;
if cost < best.0 {
best = (cost, level);
}
}
block[idx] = best.1;
let nonzero = usize::from(best.1 != 0);
total = others + nonzero;
remaining_after += nonzero;
}
}
#[allow(clippy::too_many_arguments)]
fn rdoq_block_beam<const K: usize>(
channel_weight: f32,
window_cap: usize,
restore_len: usize,
prices: &FrozenTokenPrices,
scan: &[u32],
source: &[f32],
inv_qm: &[f32],
q_scaled: f32,
block: &mut [i32],
strategy_code: u8,
c: usize,
bias: DequantBias,
predicted: u8,
cx: usize,
cy: usize,
distance: f32,
qf_hi: bool,
lambda: f32,
restore_penalty: f32,
back: &mut [u8],
) {
const { assert!(K <= 8) };
let covered_blocks = cx * cy;
let size = block.len();
let available = size
.checked_sub(covered_blocks)
.expect("LLF positions fit in the block");
let window_len = window_cap.min(available);
assert!(
window_len <= back.len() / (2 * K),
"RDOQ window exceeds choice storage"
);
let search_end = covered_blocks + window_len;
let base_window_len = (24 * covered_blocks).min(64).min(available);
let block_ctx = fine_block_context(c, strategy_code, qf_hi);
let histo_offset = fine_zero_density_contexts_offset(block_ctx);
let log2_covered_blocks = covered_blocks.trailing_zeros() as usize;
let context = |remaining: usize, k: usize, prev: usize| -> u32 {
histo_offset
+ if covered_blocks == 1 {
zero_density_context_8x8(remaining, k, prev) as u32
} else {
zero_density_context(remaining, k, covered_blocks, log2_covered_blocks, prev) as u32
}
};
let channel_scale = if c == 1 {
1.0
} else {
chroma_rdoq_weight(distance)
};
let suffix_nzeros = (search_end..size)
.filter(|&k| block[scan[k] as usize] != 0)
.count();
let mut suffix_cost = [0.0f32; 2];
for (initial_prev, target) in suffix_cost.iter_mut().enumerate() {
let mut remaining = suffix_nzeros;
let mut prev = initial_prev;
let mut k = search_end;
while k < size && remaining != 0 {
let coef = block[scan[k] as usize];
*target += lambda
* prices.token_bits(Token::new(context(remaining, k, prev), pack_signed(coef)));
prev = usize::from(coef != 0);
remaining -= usize::from(coef != 0);
k += 1;
}
}
let mut path_remaining = [0usize; K];
let mut path_cost = [[f32::INFINITY; 2]; K];
path_remaining[0] = suffix_nzeros;
path_cost[0] = suffix_cost;
let mut paths = 1;
for window_index in (0..window_len).rev() {
let k = covered_blocks + window_index;
let idx = scan[k] as usize;
let current = block[idx];
let ideal = source[idx] * inv_qm[idx] * q_scaled;
let (candidates, candidate_count) =
rdoq_candidates(ideal, current, window_index < restore_len);
let distortion_weight = channel_weight
* channel_scale
* rdoq_distortion_weight(window_index.min(base_window_len), base_window_len, distance);
if candidate_count == 1 {
let level = candidates[0];
let nonzero = usize::from(level != 0);
let rate = if current == 0 && level != 0 {
lambda * restore_penalty
} else {
lambda
};
let distortion = distortion_weight * (ideal - bias.level(level)).powi(2);
for (path, (remaining, cost)) in path_remaining[..paths]
.iter_mut()
.zip(&mut path_cost)
.enumerate()
{
let tail = cost[nonzero];
*remaining += nonzero;
let token_cost = if *remaining == 0 {
[0.0; 2]
} else {
prices
.token_bits_pair(context(*remaining, k, 0), pack_signed(level))
.map(|bits| rate * bits)
};
*cost = token_cost.map(|token| distortion + token + tail);
let row = (window_index * K + path) * 2;
back[row..row + 2].fill((path as u8) << 4);
}
continue;
}
let mut distortions = [0.0f32; 5];
let mut rates = [lambda; 5];
for ((distortion, rate), &level) in distortions
.iter_mut()
.zip(&mut rates)
.zip(&candidates[..candidate_count])
{
*distortion = distortion_weight * (ideal - bias.level(level)).powi(2);
if current == 0 && level != 0 {
*rate = lambda * restore_penalty;
}
}
let mut count_of = [0usize; 16];
let mut cost_of = [[f32::INFINITY; 2]; 16];
let mut choice_of = [[0u8; 2]; 16];
let mut counts = 0;
let mut slot_of =
|remaining: usize| match count_of[..counts].iter().position(|&r| r == remaining) {
Some(slot) => slot,
None => {
count_of[counts] = remaining;
counts += 1;
counts - 1
}
};
for (path, (&remaining_after, tail_pair)) in
path_remaining[..paths].iter().zip(&path_cost).enumerate()
{
let slots = [slot_of(remaining_after), slot_of(remaining_after + 1)];
for (candidate, &level) in candidates[..candidate_count].iter().enumerate() {
let nonzero = usize::from(level != 0);
let tail = tail_pair[nonzero];
if !tail.is_finite() {
continue;
}
let remaining = remaining_after + nonzero;
let token_cost = if remaining == 0 {
[0.0; 2]
} else {
prices
.token_bits_pair(context(remaining, k, 0), pack_signed(level))
.map(|bits| rates[candidate] * bits)
};
let slot = slots[nonzero];
for prev in 0..2 {
let cost = distortions[candidate] + token_cost[prev] + tail;
if cost < cost_of[slot][prev] {
cost_of[slot][prev] = cost;
choice_of[slot][prev] = ((path as u8) << 4) | candidate as u8;
}
}
}
}
let mut order = [0usize; 16];
for (i, slot) in order[..counts].iter_mut().enumerate() {
*slot = i;
}
if counts > K {
let key = |slot: usize| cost_of[slot][0].min(cost_of[slot][1]);
for p in 0..K {
let mut best = p;
for q in p + 1..counts {
if key(order[q]).total_cmp(&key(order[best])) == std::cmp::Ordering::Less {
best = q;
}
}
order[p..=best].rotate_right(1);
}
}
paths = counts.min(K);
for (path, &slot) in order[..paths].iter().enumerate() {
path_remaining[path] = count_of[slot];
path_cost[path] = cost_of[slot];
let row = (window_index * K + path) * 2;
back[row..row + 2].copy_from_slice(&choice_of[slot]);
}
}
let initial_prev = |remaining: usize| usize::from(remaining <= size / 16);
let nzero_ctx = fine_non_zero_context(predicted as u32, block_ctx);
let mut best = (f32::INFINITY, usize::MAX);
for (path, (&remaining, cost)) in path_remaining[..paths].iter().zip(&path_cost).enumerate() {
let tail = cost[initial_prev(remaining)];
if !tail.is_finite() {
continue;
}
let cost = tail + lambda * prices.token_bits(Token::new(nzero_ctx, remaining as u32));
if cost < best.0 {
best = (cost, path);
}
}
if best.1 == usize::MAX {
return;
}
let mut path = best.1;
let mut prev = initial_prev(path_remaining[path]);
for window_index in 0..window_len {
let k = covered_blocks + window_index;
let idx = scan[k] as usize;
let ideal = source[idx] * inv_qm[idx] * q_scaled;
let (candidates, candidate_count) =
rdoq_candidates(ideal, block[idx], window_index < restore_len);
let choice = back[(window_index * K + path) * 2 + prev];
let candidate = usize::from(choice & 15);
debug_assert!(candidate < candidate_count);
let level = candidates[candidate];
block[idx] = level;
prev = usize::from(level != 0);
path = usize::from(choice >> 4);
}
}
#[allow(clippy::too_many_arguments)]
fn rdoq_block_banded<const FACTORED: bool, const SINGLE_BLOCK: bool>(
channel_weight: f32,
window_cap: usize,
restore_len: usize,
legacy_limit: bool,
prices: &FrozenTokenPrices,
scan: &[u32],
source: &[f32],
inv_qm: &[f32],
q_scaled: f32,
block: &mut [i32],
strategy_code: u8,
c: usize,
bias: DequantBias,
predicted: u8,
cx: usize,
cy: usize,
distance: f32,
qf_hi: bool,
lambda: f32,
restore_penalty: f32,
choices: &mut [u8],
costs: &mut [[f32; RDOQ_BAND_STRIDE]; 2],
) {
const MAX_NZERO_DELTA: usize = RDOQ_MAX_NZERO_DELTA;
const BAND_STRIDE: usize = RDOQ_BAND_STRIDE;
debug_assert!(!SINGLE_BLOCK || cx * cy == 1);
let covered_blocks = if SINGLE_BLOCK { 1 } else { cx * cy };
let available = block
.len()
.checked_sub(covered_blocks)
.expect("LLF positions fit in the block");
let window_len = window_cap.min(available);
assert!(
window_len <= choices.len() / BAND_STRIDE,
"RDOQ window exceeds choice storage"
);
let search_end = covered_blocks + window_len;
let base_window_len = (24 * covered_blocks).min(64).min(available);
let block_ctx = fine_block_context(c, strategy_code, qf_hi);
let histo_offset = fine_zero_density_contexts_offset(block_ctx);
let log2_covered_blocks = covered_blocks.trailing_zeros() as usize;
let context = |remaining: usize, k: usize, prev: usize| -> u32 {
histo_offset
+ if covered_blocks == 1 {
zero_density_context_8x8(remaining, k, prev) as u32
} else {
zero_density_context(remaining, k, covered_blocks, log2_covered_blocks, prev) as u32
}
};
let suffix_nzeros = (search_end..block.len())
.filter(|&k| block[scan[k] as usize] != 0)
.count();
let mut suffix_cost = [0.0f32; 2];
for (initial_prev, target) in suffix_cost.iter_mut().enumerate() {
let mut remaining = suffix_nzeros;
let mut prev = initial_prev;
let mut k = search_end;
while k < block.len() && remaining != 0 {
let coef = block[scan[k] as usize];
*target += lambda
* prices.token_bits(Token::new(context(remaining, k, prev), pack_signed(coef)));
prev = usize::from(coef != 0);
remaining -= usize::from(coef != 0);
k += 1;
}
}
let max_nzeros = suffix_nzeros + window_len;
let legacy_stride = (max_nzeros + 1) * 2;
if legacy_limit
&& (legacy_stride > RDOQ_MAX_STRIDE || window_len * legacy_stride > RDOQ_MAX_CHOICES)
{
return;
}
let stride = BAND_STRIDE;
let [next_buf, current_buf] = costs;
let mut next = &mut next_buf[..stride];
let mut current_cost = &mut current_buf[..stride];
next[0] = suffix_cost[0];
next[1] = suffix_cost[1];
let mut next_min = suffix_nzeros;
let mut next_max = suffix_nzeros;
let mut original_after_nzeros = 0usize;
for window_index in (0..window_len).rev() {
let k = covered_blocks + window_index;
let idx = scan[k] as usize;
let ideal = source[idx] * inv_qm[idx] * q_scaled;
let distortion_weight = channel_weight
* if c == 1 {
1.0
} else {
chroma_rdoq_weight(distance)
}
* rdoq_distortion_weight(window_index.min(base_window_len), base_window_len, distance);
let (candidates, candidate_count) =
rdoq_candidates(ideal, block[idx], window_index < restore_len);
let mut candidate_distortion = [0.0f32; 5];
for (d, &level) in candidate_distortion[..candidate_count]
.iter_mut()
.zip(candidates.iter())
{
*d = distortion_weight * (ideal - bias.level(level)).powi(2);
}
let processed_after = window_len - 1 - window_index;
debug_assert!(original_after_nzeros <= processed_after);
let min_remaining = suffix_nzeros + original_after_nzeros.saturating_sub(MAX_NZERO_DELTA);
let max_remaining =
suffix_nzeros + (original_after_nzeros + MAX_NZERO_DELTA).min(processed_after);
let current_min = min_remaining;
let current_max = (max_remaining + 1).min(max_nzeros);
debug_assert!(current_min <= current_max);
debug_assert!(current_max - current_min < BAND_STRIDE / 2);
debug_assert!(next_max - next_min < BAND_STRIDE / 2);
if !FACTORED {
current_cost[..(current_max - current_min + 1) * 2].fill(f32::INFINITY);
for next_remaining in min_remaining.max(next_min)..=max_remaining.min(next_max) {
for (candidate_index, &level) in candidates[..candidate_count].iter().enumerate() {
let nonzero = usize::from(level != 0);
let remaining = next_remaining + nonzero;
if remaining > max_nzeros {
continue;
}
let tail = next[(next_remaining - next_min) * 2 + nonzero];
if !tail.is_finite() {
continue;
}
let distortion = candidate_distortion[candidate_index];
let token_cost = if remaining == 0 {
[0.0; 2]
} else {
let bits =
prices.token_bits_pair(context(remaining, k, 0), pack_signed(level));
let rate = if block[idx] == 0 && level != 0 {
lambda * restore_penalty
} else {
lambda
};
[rate * bits[0], rate * bits[1]]
};
let state = (remaining - current_min) * 2;
update_rdoq_state_pair(
distortion,
token_cost,
tail,
candidate_index as u8,
(&mut current_cost[state..state + 2]).try_into().unwrap(),
(&mut choices
[window_index * stride + state..window_index * stride + state + 2])
.try_into()
.unwrap(),
);
}
}
} else if candidate_count == 1 {
let level = candidates[0];
let nonzero = usize::from(level != 0);
let value = pack_signed(level);
let rate = if block[idx] == 0 && level != 0 {
lambda * restore_penalty
} else {
lambda
};
let mut cached_context = u32::MAX;
let mut local_cost = [0.0; 2];
unsafe { current_cost.get_unchecked_mut(..(current_max - current_min + 1) * 2) }
.fill(f32::INFINITY);
for next_remaining in min_remaining.max(next_min)..=max_remaining.min(next_max) {
let remaining = next_remaining + nonzero;
if remaining > max_nzeros {
continue;
}
let tail =
unsafe { *next.get_unchecked((next_remaining - next_min) * 2 + nonzero) };
if !tail.is_finite() {
continue;
}
let ctx = if remaining == 0 {
u32::MAX - 1
} else {
context(remaining, k, 0)
};
if ctx != cached_context {
cached_context = ctx;
let token_cost = if remaining == 0 {
[0.0; 2]
} else {
prices.token_bits_pair(ctx, value).map(|bits| rate * bits)
};
local_cost = token_cost.map(|cost| candidate_distortion[0] + cost);
}
let state = (remaining - current_min) * 2;
for prev in 0..2 {
let cost = local_cost[prev] + tail;
if cost < f32::INFINITY {
unsafe {
*current_cost.get_unchecked_mut(state + prev) = cost;
if cost.is_finite() {
*choices.get_unchecked_mut(window_index * stride + state + prev) =
0;
}
}
}
}
}
} else {
let source_min = min_remaining.max(next_min);
let source_max = max_remaining.min(next_max);
let zero_candidate = candidates[..candidate_count].iter().position(|&q| q == 0);
let mut cached_context = u32::MAX;
let mut local_cost = [[f32::INFINITY; 2]; 5];
let mut zero_local_cost = [f32::INFINITY; 2];
let mut nz_cost = [f32::INFINITY; 2];
let mut nz_before = [f32::INFINITY; 2];
let mut nz_choice = [u8::MAX; 2];
for remaining in current_min..=current_max {
let zero_tail = if zero_candidate.is_some()
&& remaining >= source_min
&& remaining <= source_max
{
unsafe { *next.get_unchecked((remaining - next_min) * 2) }
} else {
f32::INFINITY
};
let nz_tail = if remaining > source_min && remaining - 1 <= source_max {
unsafe { *next.get_unchecked((remaining - 1 - next_min) * 2 + 1) }
} else {
f32::INFINITY
};
let state = (remaining - current_min) * 2;
let current_pair: &mut [f32; 2] = unsafe {
current_cost
.get_unchecked_mut(state..state + 2)
.try_into()
.unwrap()
};
if !zero_tail.is_finite() && !nz_tail.is_finite() {
*current_pair = [f32::INFINITY; 2];
continue;
}
let ctx = if remaining == 0 {
u32::MAX - 1
} else {
context(remaining, k, 0)
};
if ctx != cached_context {
cached_context = ctx;
nz_cost = [f32::INFINITY; 2];
nz_before = [f32::INFINITY; 2];
nz_choice = [u8::MAX; 2];
for (candidate_index, ((&level, &distortion), local)) in candidates
[..candidate_count]
.iter()
.zip(&candidate_distortion)
.zip(&mut local_cost)
.enumerate()
{
let token_cost = if remaining == 0 {
[0.0; 2]
} else {
let bits = prices.token_bits_pair(ctx, pack_signed(level));
let rate = if block[idx] == 0 && level != 0 {
lambda * restore_penalty
} else {
lambda
};
[rate * bits[0], rate * bits[1]]
};
for prev in 0..2 {
let cost = distortion + token_cost[prev];
local[prev] = cost;
if level == 0 {
zero_local_cost[prev] = cost;
} else if cost < nz_cost[prev] {
nz_before[prev] = nz_cost[prev];
nz_cost[prev] = cost;
nz_choice[prev] = candidate_index as u8;
}
}
}
}
let row = window_index * stride + state;
let choice_pair: &mut [u8; 2] =
unsafe { choices.get_unchecked_mut(row..row + 2).try_into().unwrap() };
for prev in 0..2 {
let mut cost = if nz_tail.is_finite() {
nz_cost[prev] + nz_tail
} else {
f32::INFINITY
};
let mut choice = nz_choice[prev];
if cost.is_finite() && nz_before[prev] + nz_tail == cost {
for (i, (&level, local)) in candidates[..candidate_count]
.iter()
.zip(&local_cost)
.enumerate()
.take(choice as usize)
{
if level != 0 && local[prev] + nz_tail == cost {
choice = i as u8;
break;
}
}
}
if zero_tail.is_finite() {
let zero = zero_candidate.unwrap();
let zero_cost = zero_local_cost[prev] + zero_tail;
if zero_cost < cost {
cost = zero_cost;
choice = zero as u8;
}
}
current_pair[prev] = cost;
if cost.is_finite() {
choice_pair[prev] = choice;
}
}
}
}
std::mem::swap(&mut current_cost, &mut next);
next_min = current_min;
next_max = current_max;
original_after_nzeros += usize::from(block[idx] != 0);
}
let nzero_ctx = fine_non_zero_context(predicted as u32, block_ctx);
let mut best_remaining = 0;
let mut best_cost = f32::INFINITY;
for remaining in next_min..=next_max {
let initial_prev = usize::from(remaining <= block.len() / 16);
let tail = next[(remaining - next_min) * 2 + initial_prev];
if !tail.is_finite() {
continue;
}
let cost = tail + lambda * prices.token_bits(Token::new(nzero_ctx, remaining as u32));
if cost < best_cost {
best_cost = cost;
best_remaining = remaining;
}
}
let mut remaining = best_remaining;
let mut prev = usize::from(remaining <= block.len() / 16);
let mut original_remaining = original_after_nzeros;
for window_index in 0..window_len {
let k = covered_blocks + window_index;
let idx = scan[k] as usize;
let ideal = source[idx] * inv_qm[idx] * q_scaled;
let (candidates, candidate_count) =
rdoq_candidates(ideal, block[idx], window_index < restore_len);
original_remaining -= usize::from(block[idx] != 0);
let row_min = suffix_nzeros + original_remaining.saturating_sub(MAX_NZERO_DELTA);
let choice = choices[window_index * stride + (remaining - row_min) * 2 + prev] as usize;
debug_assert!(choice < candidate_count);
let level = candidates[choice];
block[idx] = level;
let nonzero = usize::from(level != 0);
remaining -= nonzero;
prev = nonzero;
}
}
const CHROMA_RDOQ_WEIGHT_HQ: f32 = 2.0;
const CHROMA_RDOQ_WEIGHT_D0: f32 = 2.25;
const CHROMA_RDOQ_WEIGHT_D1: f32 = 4.0;
#[inline]
pub(crate) fn chroma_rdoq_weight(distance: f32) -> f32 {
let t = ((distance - CHROMA_RDOQ_WEIGHT_D0) / (CHROMA_RDOQ_WEIGHT_D1 - CHROMA_RDOQ_WEIGHT_D0))
.clamp(0.0, 1.0);
CHROMA_RDOQ_WEIGHT_HQ + t * (1.0 - CHROMA_RDOQ_WEIGHT_HQ)
}
#[derive(Default)]
pub(super) struct RdoqScratch {
pub(super) choices: Box<[u8]>,
pub(super) costs: Option<Box<[[f32; RDOQ_BAND_STRIDE]; 2]>>,
}
impl RdoqScratch {
fn choices(&mut self, len: usize) -> &mut [u8] {
grow_choices(&mut self.choices, len);
&mut self.choices[..len]
}
fn trellis(&mut self, window_len: usize) -> (&mut [u8], &mut [[f32; RDOQ_BAND_STRIDE]; 2]) {
let len = window_len * RDOQ_BAND_STRIDE;
grow_choices(&mut self.choices, len);
let costs = self
.costs
.get_or_insert_with(|| Box::new([[f32::INFINITY; RDOQ_BAND_STRIDE]; 2]));
(&mut self.choices[..len], costs)
}
}
fn grow_choices(choices: &mut Box<[u8]>, len: usize) {
if choices.len() < len {
*choices = vec![u8::MAX; len].into_boxed_slice();
}
}
#[cfg(test)]
mod tests {
#[test]
fn greedy_first_coefficient_prices_its_candidate_count_predecessor() {
use crate::ac_context::{
K_NUM_FINE_AC_CONTEXTS, fine_block_context, fine_zero_density_contexts_offset,
zero_density_context, zero_density_context_8x8,
};
use crate::dc_group_data::{STRATEGY_CODE_LUT, STRATEGY_DCT, STRATEGY_DCT16X8};
use crate::entropy::{FrozenTokenPrices, Token, build_entropy_code_no_cluster};
let orders = crate::coeff_order::CoeffOrders::natural();
for (raw, cx) in [(STRATEGY_DCT, 1), (STRATEGY_DCT16X8, 2)] {
let size = cx * 64;
let threshold = size / 16;
let strategy = STRATEGY_CODE_LUT[raw as usize];
let scan = orders.scan_for(strategy, 1);
let block_ctx = fine_block_context(1, strategy, false);
let offset = fine_zero_density_contexts_offset(block_ctx);
let context = |remaining, prev| {
offset
+ if cx == 1 {
zero_density_context_8x8(remaining, cx, prev) as u32
} else {
zero_density_context(remaining, cx, cx, cx.trailing_zeros() as usize, prev)
as u32
}
};
let tokens = [Token::new(0, 0), Token::new(1, 0)];
let mut code = build_entropy_code_no_cluster(&tokens, 2, &mut Vec::new());
for prefix in &mut code.prefix_codes {
prefix.depths.fill(15);
prefix.single_symbol = false;
}
code.prefix_codes[1].depths[0] = 1;
code.context_map = vec![0; K_NUM_FINE_AC_CONTEXTS];
code.context_map[context(threshold, 1) as usize] = 1;
let prices = FrozenTokenPrices::new(&code);
assert_eq!(prices.token_bits(Token::new(context(threshold, 0), 0)), 15.);
assert_eq!(prices.token_bits(Token::new(context(threshold, 1), 0)), 1.);
for sign in [-1, 1] {
let mut source = vec![0.; size];
let mut block = vec![0; size];
let first = scan[cx] as usize;
source[first] = sign as f32 * 0.6;
block[first] = sign;
for &raw in &scan[cx + 1..cx + 1 + threshold] {
source[raw as usize] = 3.;
block[raw as usize] = 3;
}
let mut expected = block.clone();
expected[first] = 0;
super::rdoq_block_greedy(
1.,
1,
1,
&prices,
scan,
&source,
&vec![1.; size],
1.,
&mut block,
strategy,
1,
super::DequantBias::DEFAULT[1],
32,
cx,
1,
2.,
false,
0.03,
1.,
);
assert_eq!(block, expected, "shape {cx}x1, sign {sign}");
}
}
}
#[test]
fn rdoq_scratch_index_model_is_bounded() {
let delta = super::RDOQ_MAX_NZERO_DELTA;
let stride = super::RDOQ_BAND_STRIDE;
let window = super::RDOQ_MAX_CHOICES / stride;
for suffix in [0, isize::MAX as usize / size_of::<i32>() - window] {
for processed in 0..window {
for original in 0..=processed {
let min = suffix + original.saturating_sub(delta);
let max = suffix + (original + delta).min(processed);
let current_max = (max + 1).min(suffix + window);
assert!(current_max >= min);
assert!(current_max - min < stride / 2);
for last in 0..=1 {
let (next_min, next_max) = if processed == 0 {
if last != 0 {
continue;
}
(suffix, suffix)
} else {
let Some(previous) = original.checked_sub(last) else {
continue;
};
if previous >= processed {
continue;
}
(
suffix + previous.saturating_sub(delta),
suffix + (previous + delta).min(processed - 1) + 1,
)
};
assert!(next_max - next_min < stride / 2);
let source_min = min.max(next_min);
let source_max = max.min(next_max);
for remaining in min..=current_max {
if remaining >= source_min && remaining <= source_max {
assert!((remaining - next_min) * 2 < stride);
}
if remaining > source_min && remaining - 1 <= source_max {
assert!((remaining - 1 - next_min) * 2 + 1 < stride);
}
let state = (remaining - min) * 2;
assert!(state + 2 <= stride);
let row = (window - 1 - processed) * stride + state;
assert!(row + 2 <= super::RDOQ_MAX_CHOICES);
}
}
}
}
}
}
#[test]
fn rdoq_scratch_memory_safety() {
use crate::dc_group_data::{STRATEGY_CODE_LUT, STRATEGY_DCT, STRATEGY_DCT16X8};
use crate::entropy::{FrozenTokenPrices, Token, build_entropy_code_no_cluster};
use std::panic::{AssertUnwindSafe, catch_unwind};
let tokens = [Token::new(0, 0), Token::new(0, 1), Token::new(0, 2)];
let mut code = build_entropy_code_no_cluster(&tokens, 1, &mut Vec::new());
code.context_map = vec![0; crate::ac_context::K_NUM_FINE_AC_CONTEXTS];
let prices = FrozenTokenPrices::new(&code);
let orders = crate::coeff_order::CoeffOrders::natural();
let run = |cap: usize, cx: usize, source: &[f32], scan: &[u32], block: &mut [i32]| {
let mut choices = super::heap_array::<_, { super::RDOQ_MAX_CHOICES }>(0xA5);
let mut costs = Box::new([[f32::NAN; super::RDOQ_BAND_STRIDE]; 2]);
let inv_qm = vec![1.; block.len()];
let refine = if cx == 1 {
super::rdoq_block_banded::<true, true>
} else {
super::rdoq_block_banded::<true, false>
};
let raw = if cx == 1 {
STRATEGY_DCT
} else {
STRATEGY_DCT16X8
};
refine(
1.,
cap,
20,
false,
&prices,
scan,
source,
&inv_qm,
1.,
block,
STRATEGY_CODE_LUT[raw as usize],
1,
super::DequantBias::DEFAULT[1],
32,
cx,
1,
2.,
false,
0.1,
2.,
choices.as_mut_slice(),
&mut costs,
);
};
for (raw, cx) in [(STRATEGY_DCT, 1), (STRATEGY_DCT16X8, 2)] {
let scan = orders.scan_for(STRATEGY_CODE_LUT[raw as usize], 1);
for dense in [false, true] {
let source: Vec<f32> = (0..cx * 64)
.map(|i| if dense && i % 3 != 0 { 1.25 } else { 0. })
.collect();
let initial: Vec<i32> = source.iter().map(|v| v.round() as i32).collect();
for cap in [0, 1, 20, usize::MAX] {
run(cap, cx, &source, scan, &mut initial.clone());
}
}
}
assert!(
catch_unwind(AssertUnwindSafe(|| {
run(usize::MAX, 2, &[], &[], &mut [0]);
}))
.is_err()
);
let too_long = super::RDOQ_MAX_CHOICES / super::RDOQ_BAND_STRIDE + 2;
assert!(
catch_unwind(AssertUnwindSafe(|| {
run(usize::MAX, 1, &[], &[], &mut vec![0; too_long]);
}))
.is_err()
);
for value in [f32::NAN, f32::MAX] {
assert!(
catch_unwind(AssertUnwindSafe(|| {
let scan = orders.scan_for(STRATEGY_CODE_LUT[STRATEGY_DCT as usize], 1);
run(20, 1, &[value; 64], scan, &mut [0; 64]);
}))
.is_err()
);
}
}
#[test]
fn few_colors_counts_distinct_source_colors() {
use crate::image::Image3F;
let mut xyb = Image3F::new(16, 8);
for c in 0..3 {
for y in 0..8 {
let row = xyb.plane_row_mut(c, y);
for x in 0..8 {
row[x] = if x < 4 { 0.1 } else { 0.5 };
row[8 + x] = (y * 8 + x) as f32 * 0.01;
}
}
}
let mut seen = vec![u64::MAX; 256];
let storage = seen.as_ptr();
assert!(super::few_colors(&xyb, 0, 0, 8, 8, 24, &mut seen));
assert!(super::few_colors(&xyb, 0, 0, 8, 8, 2, &mut seen));
assert!(!super::few_colors(&xyb, 0, 0, 8, 8, 1, &mut seen));
assert!(!super::few_colors(&xyb, 8, 0, 16, 8, 24, &mut seen));
assert!(super::few_colors(&xyb, 8, 0, 16, 8, 64, &mut seen));
assert!(!super::few_colors(&xyb, 0, 0, 8, 8, 0, &mut seen));
assert!(super::few_colors(&xyb, 0, 0, 0, 0, 0, &mut seen));
assert!(seen.is_empty());
assert_eq!(seen.as_ptr(), storage, "color storage should be reused");
}
#[test]
fn rdoq_state_pair_preserves_scalar_cost_bits_and_choices() {
let special = [
0.0,
-0.0,
1.0,
-1.0,
f32::INFINITY,
f32::NEG_INFINITY,
f32::MAX,
f32::MIN_POSITIVE,
f32::from_bits(1),
f32::from_bits(0x7fc0_1234),
f32::from_bits(0xffc0_5678),
f32::from_bits(0x7f80_1234),
f32::from_bits(0xff80_5678),
];
let mut seed = 73u32;
let mut random = || {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
if seed.is_multiple_of(4) {
special[seed as usize % special.len()]
} else {
f32::from_bits(seed)
}
};
let mut masks = [false; 4];
for case in 0..16_384 {
let distortion = random();
let token_cost = [random(), random()];
let tail = random();
let cost = token_cost.map(|price| distortion + price + tail);
let mut initial = [random(), random()];
if case % 8 == 0 {
initial = cost;
}
let initial_choices = [case as u8, (case >> 3) as u8];
let candidate = (case % 5) as u8;
let mut expected = initial;
let mut expected_choices = initial_choices;
let mut mask = 0;
for prev in 0..2 {
if cost[prev] < expected[prev] {
expected[prev] = cost[prev];
expected_choices[prev] = candidate;
mask |= 1 << prev;
}
}
masks[mask] = true;
let mut actual = initial;
let mut actual_choices = initial_choices;
super::update_rdoq_state_pair(
distortion,
token_cost,
tail,
candidate,
&mut actual,
&mut actual_choices,
);
assert_eq!(
actual.map(f32::to_bits),
expected.map(f32::to_bits),
"costs in case {case}"
);
assert_eq!(actual_choices, expected_choices, "choices in case {case}");
}
assert_eq!(masks, [true; 4]);
}
#[test]
fn rdoq_reused_scratch_matches_fresh_scratch() {
use crate::dc_group_data::STRATEGY_CODE_LUT;
use crate::entropy::{FrozenTokenPrices, Token, build_entropy_code_no_cluster};
let tokens: Vec<_> = (0..4096)
.map(|i| Token::new(i % 2, if i % 3 == 0 { 0 } else { i % 17 }))
.collect();
let mut code = build_entropy_code_no_cluster(&tokens, 2, &mut Vec::new());
code.context_map = (0..crate::ac_context::K_NUM_FINE_AC_CONTEXTS)
.map(|i| (i % 2) as u8)
.collect();
let prices = FrozenTokenPrices::new(&code);
let orders = crate::coeff_order::CoeffOrders::natural();
let mut reused = super::RdoqScratch {
choices: vec![0xA5; super::RDOQ_MAX_CHOICES].into_boxed_slice(),
costs: Some(Box::new([[f32::NAN; super::RDOQ_BAND_STRIDE]; 2])),
};
let mut seed = 73u32;
let mut random = || {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
seed
};
let mut changed = 0;
for case in 0..384 {
let (raw, cx, cy) = [
(crate::dc_group_data::STRATEGY_DCT, 1, 1),
(crate::dc_group_data::STRATEGY_DCT16X8, 2, 1),
(crate::dc_group_data::STRATEGY_DCT16X16, 2, 2),
(crate::dc_group_data::STRATEGY_DCT32X16, 4, 2),
(crate::dc_group_data::STRATEGY_DCT32X32, 4, 4),
][case % 5];
let strategy = STRATEGY_CODE_LUT[raw as usize];
let c = case % 3;
let coding = [
crate::CodingTransform::Xyb,
crate::CodingTransform::YCbCr,
crate::CodingTransform::Rgb,
][case / 3 % 3];
let mut scan = orders.scan_for(strategy, c).to_vec();
let size = cx * cy * 64;
if case % 2 == 0 {
for i in cx * cy..size {
let j = cx * cy + random() as usize % (size - cx * cy);
scan.swap(i, j);
}
}
let inv_qm = vec![1.; size];
let source: Vec<f32> = (0..size)
.map(|_| {
if random() % 10 < (case % 10) as u32 {
0.
} else {
(random() % 1024) as f32 / 128. - 4.
}
})
.collect();
let original: Vec<i32> = source.iter().map(|v| v.round() as i32).collect();
let mut expected = original.clone();
let mut actual = original.clone();
let search = [
super::RdoqSearch::Trellis,
super::RdoqSearch::Beam,
super::RdoqSearch::Greedy,
][case % 3];
let mut fresh = super::RdoqScratch::default();
let run = |block: &mut [i32], scratch: &mut super::RdoqScratch| {
super::rdoq_block(
super::rdoq_channel_weights(coding)[c],
&prices,
&scan,
&source,
&inv_qm,
1.,
block,
raw,
strategy,
c,
super::DequantBias::DEFAULT[c],
(case % 64) as u8,
cx,
cy,
[1., 2., 3., 4.][case % 4],
case % 2 == 0,
super::rdoq_lambda(crate::Arbiter::Ssimulacra2, [0.5, 1.0, 1.2, 2.0][case % 4]),
1.0,
search,
scratch,
);
};
run(&mut expected, &mut fresh);
run(&mut actual, &mut reused);
let (window, _) = super::rdoq_window_len(cx * cy);
let stride = match search {
super::RdoqSearch::Greedy => 0,
super::RdoqSearch::Beam => 2 * super::RDOQ_BEAM_WIDTH,
super::RdoqSearch::Trellis => super::RDOQ_BAND_STRIDE,
};
assert_eq!(fresh.choices.len(), window * stride);
assert_eq!(fresh.costs.is_some(), search == super::RdoqSearch::Trellis);
assert_eq!(actual, expected, "scratch reuse in case {case}");
changed += usize::from(actual != original);
}
assert!(
changed > 100,
"exercise finite trellis paths, including changed blocks"
);
}
#[test]
fn rdoq_window_policy() {
for covered in [1, 2, 4, 8, 16, 32, 64] {
let expected = if covered == 1 {
(63, 20)
} else {
((64 * covered).min(1024), (24 * covered).min(256))
};
assert_eq!(super::rdoq_window_len(covered), expected);
}
}
#[test]
fn factored_rdoq_preserves_cost_bits_choices_and_restore_penalties() {
use crate::dc_group_data::STRATEGY_CODE_LUT;
use crate::entropy::{FrozenTokenPrices, Token, build_entropy_code_no_cluster};
let tokens: Vec<_> = (0..16_384)
.map(|i| {
let context = i % 4;
let value = if i % 7 < context + 1 {
0
} else {
(i / 4) % 601
};
Token::new(context, value)
})
.collect();
let mut code = build_entropy_code_no_cluster(&tokens, 4, &mut Vec::new());
code.context_map = (0..crate::ac_context::K_NUM_FINE_AC_CONTEXTS)
.map(|i| ((i / 2 + i % 2) % 4) as u8)
.collect();
let prices = FrozenTokenPrices::new(&code);
let orders = crate::coeff_order::CoeffOrders::natural();
let mut choices0 = super::heap_array::<_, { super::RDOQ_MAX_CHOICES }>(0xA5u8);
let mut choices1 = super::heap_array::<_, { super::RDOQ_MAX_CHOICES }>(0xA5u8);
let mut costs0 = Box::new([[f32::NAN; super::RDOQ_BAND_STRIDE]; 2]);
let mut costs1 = costs0.clone();
let mut seed = 173u32;
let mut random = || {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
seed
};
let shapes = [
(crate::dc_group_data::STRATEGY_DCT, 1, 1),
(crate::dc_group_data::STRATEGY_DCT16X8, 2, 1),
(crate::dc_group_data::STRATEGY_DCT16X16, 2, 2),
(crate::dc_group_data::STRATEGY_DCT32X16, 4, 2),
(crate::dc_group_data::STRATEGY_DCT32X32, 4, 4),
(crate::dc_group_data::STRATEGY_DCT64X32, 8, 4),
(crate::dc_group_data::STRATEGY_DCT64X64, 8, 8),
#[cfg(feature = "extraslow")]
(crate::dc_group_data::STRATEGY_DCT128X64, 16, 8),
#[cfg(feature = "extraslow")]
(crate::dc_group_data::STRATEGY_DCT128X128, 16, 16),
];
let mut changed = 0;
for case in 0..144 {
let (raw, cx, cy) = shapes[case % shapes.len()];
let strategy = STRATEGY_CODE_LUT[raw as usize];
let c = case / shapes.len() % 3;
let size = cx * cy * 64;
let mut scan = orders.scan_for(strategy, c).to_vec();
if case % 2 == 0 {
for i in cx * cy..size {
let j = cx * cy + random() as usize % (size - cx * cy);
scan.swap(i, j);
}
}
let inv_qm: Vec<_> = (0..size).map(|i| 0.75 + (i % 9) as f32 / 16.).collect();
let source: Vec<f32> = (0..size)
.map(|_| {
let r = random();
if r % 10 < (case / shapes.len() % 10) as u32 {
0.
} else if case % 7 == 0 {
(r % 4001) as f32 / 8. - 250.
} else {
(r % 1024) as f32 / 128. - 4.
}
})
.collect();
let original: Vec<i32> = source.iter().map(|v| v.round() as i32).collect();
for cap in [64, 256, 1024] {
let mut expected = original.clone();
let mut actual = original.clone();
let run = |factored, block: &mut [i32], choices: &mut _, costs: &mut _| {
let refine = if factored && cx * cy == 1 {
super::rdoq_block_banded::<true, true>
} else if factored {
super::rdoq_block_banded::<true, false>
} else {
super::rdoq_block_banded::<false, false>
};
refine(
[0.3, 1., 0.6][c],
cap,
cap,
false,
&prices,
&scan,
&source,
&inv_qm,
[0.75, 1.5][case % 2],
block,
strategy,
c,
super::DequantBias::DEFAULT[c],
(case % 256) as u8,
cx,
cy,
[0.3, 2., 4., 8.][case % 4],
case % 2 == 0,
super::rdoq_lambda(crate::Arbiter::Ssimulacra2, [0.5, 1.2][case % 2])
/ [1., 0.125][case % 2],
[1., 2.][case / shapes.len() % 2],
choices,
costs,
);
};
run(false, &mut expected, choices0.as_mut_slice(), &mut costs0);
run(true, &mut actual, choices1.as_mut_slice(), &mut costs1);
assert_eq!(actual, expected, "coefficients, case={case}, cap={cap}");
assert_eq!(
choices0.as_slice(),
choices1.as_slice(),
"choices, case={case}, cap={cap}"
);
for (&a, &b) in costs0.iter().flatten().zip(costs1.iter().flatten()) {
assert_eq!(
a.to_bits(),
b.to_bits(),
"cost bits, case={case}, cap={cap}"
);
}
changed += usize::from(actual != original);
}
}
assert!(changed > 100, "must exercise changed blocks: {changed}");
}
#[test]
fn single_candidate_rows_preserve_cost_bits_and_choices() {
use crate::dc_group_data::*;
use crate::entropy::{FrozenTokenPrices, Token, build_entropy_code_no_cluster};
let tokens: Vec<_> = (0..4096)
.map(|i| Token::new(i % 4, if i % 5 == 0 { 0 } else { i % 257 }))
.collect();
let mut code = build_entropy_code_no_cluster(&tokens, 4, &mut Vec::new());
code.context_map = (0..crate::ac_context::K_NUM_FINE_AC_CONTEXTS)
.map(|i| ((i / 2 + i % 2) % 4) as u8)
.collect();
let prices = FrozenTokenPrices::new(&code);
let orders = crate::coeff_order::CoeffOrders::natural();
let shapes = [
(STRATEGY_DCT, 1, 1),
(STRATEGY_DCT16X8, 2, 1),
(STRATEGY_DCT16X16, 2, 2),
(STRATEGY_DCT32X32, 4, 4),
(STRATEGY_DCT64X64, 8, 8),
#[cfg(feature = "extraslow")]
(STRATEGY_DCT128X128, 16, 16),
];
let mut choices0 = super::heap_array::<_, { super::RDOQ_MAX_CHOICES }>(0xA5);
let mut choices1 = super::heap_array::<_, { super::RDOQ_MAX_CHOICES }>(0xA5);
let mut costs0 = Box::new([[f32::from_bits(0x7fc0_1234); super::RDOQ_BAND_STRIDE]; 2]);
let mut costs1 = costs0.clone();
let mut single_zero = 0;
let mut single_nonzero = 0;
for case in 0..72 {
let (raw, cx, cy) = shapes[case % shapes.len()];
let strategy = STRATEGY_CODE_LUT[raw as usize];
let c = case / shapes.len() % 3;
let covered = cx * cy;
let size = covered * 64;
let mut scan = orders.scan_for(strategy, c).to_vec();
if case % 2 == 0 {
scan[covered..].reverse();
}
let source: Vec<f32> = (0..size)
.map(|i| match (i + case) % 8 {
0 => -0.0,
1 => 0.000_001,
2 => -0.000_001,
3 => 3.0,
4 => -4.125,
5 => 128.0,
6 => -257.0,
_ => 0.49,
})
.collect();
let original: Vec<_> = source
.iter()
.enumerate()
.map(|(i, v)| if i % 7 == 0 { 0 } else { v.round() as i32 })
.collect();
let inv_qm = vec![1.; size];
let (cap, restoring) = super::rdoq_window_len(covered);
for restore_len in [0, restoring, cap] {
for (wi, &idx) in scan.iter().skip(covered).take(cap).enumerate() {
let idx = idx as usize;
let (candidates, n) =
super::rdoq_candidates(source[idx], original[idx], wi < restore_len);
if n == 1 {
if candidates[0] == 0 {
single_zero += 1;
} else {
single_nonzero += 1;
}
}
}
let run = |factored, block: &mut [i32], choices: &mut _, costs: &mut _| {
let refine = if factored && covered == 1 {
super::rdoq_block_banded::<true, true>
} else if factored {
super::rdoq_block_banded::<true, false>
} else {
super::rdoq_block_banded::<false, false>
};
refine(
[0.3, 1., 0.6][c],
cap,
restore_len,
false,
&prices,
&scan,
&source,
&inv_qm,
1.,
block,
strategy,
c,
super::DequantBias::DEFAULT[c],
(case * 17) as u8,
cx,
cy,
[0.05, 2., 4., 8.][case % 4],
case % 2 == 0,
[0., 0.01, 0.1, 1_000_000.][case % 4],
[1., 2.][case % 2],
choices,
costs,
);
};
let mut expected = original.clone();
let mut actual = original.clone();
run(false, &mut expected, choices0.as_mut_slice(), &mut costs0);
run(true, &mut actual, choices1.as_mut_slice(), &mut costs1);
assert_eq!(
actual, expected,
"levels, case={case}, restore={restore_len}"
);
assert_eq!(
*choices1, *choices0,
"choices, case={case}, restore={restore_len}"
);
for (&a, &b) in costs0.iter().flatten().zip(costs1.iter().flatten()) {
assert_eq!(
a.to_bits(),
b.to_bits(),
"cost bits, case={case}, restore={restore_len}"
);
}
}
}
assert!(single_zero > 10_000 && single_nonzero > 10_000);
}
#[test]
fn factored_rdoq_preserves_tail_rounding_ties() {
use crate::dc_group_data::STRATEGY_CODE_LUT;
use crate::entropy::{
FrozenTokenPrices, Token, build_entropy_code_no_cluster, pack_signed,
};
let mut tokens = vec![Token::new(0, 0); 1000];
tokens.extend((0..100).flat_map(|_| [Token::new(0, 1), Token::new(0, 2)]));
let mut code = build_entropy_code_no_cluster(&tokens, 1, &mut Vec::new());
code.context_map = vec![0; crate::ac_context::K_NUM_FINE_AC_CONTEXTS];
let prices = FrozenTokenPrices::new(&code);
let orders = crate::coeff_order::CoeffOrders::natural();
let raw = crate::dc_group_data::STRATEGY_DCT16X8;
let strategy = STRATEGY_CODE_LUT[raw as usize];
let scan = orders.scan_for(strategy, 1);
let inv_qm = [1.; 128];
let mut collapsed = 0;
for i in 1..100 {
let ideal = i as f32 * 1e-8;
let mut source = [0.; 128];
source[scan[2] as usize] = ideal;
let mut expected = [0; 128];
for &idx in &scan[3..54] {
source[idx as usize] = 1.;
expected[idx as usize] = 1;
}
let mut actual = expected;
let mut choices0 = super::heap_array::<_, { super::RDOQ_MAX_CHOICES }>(0xA5);
let mut choices1 = super::heap_array::<_, { super::RDOQ_MAX_CHOICES }>(0xA5);
let mut costs0 = Box::new([[f32::NAN; super::RDOQ_BAND_STRIDE]; 2]);
let mut costs1 = costs0.clone();
let run = |factored, block: &mut [i32], choices: &mut _, costs: &mut _| {
let refine = if factored {
super::rdoq_block_banded::<true, false>
} else {
super::rdoq_block_banded::<false, false>
};
refine(
1.,
1,
1,
false,
&prices,
scan,
&source,
&inv_qm,
1.,
block,
strategy,
1,
super::DequantBias::DEFAULT[1],
17,
2,
1,
1.,
false,
super::rdoq_lambda(crate::Arbiter::Ssimulacra2, 1.),
2.,
choices,
costs,
);
};
run(false, &mut expected, choices0.as_mut_slice(), &mut costs0);
run(true, &mut actual, choices1.as_mut_slice(), &mut costs1);
assert_eq!(actual, expected);
assert_eq!(choices0.as_slice(), choices1.as_slice());
for (&a, &b) in costs0.iter().flatten().zip(costs1.iter().flatten()) {
assert_eq!(a.to_bits(), b.to_bits());
}
let rate = 2. * super::rdoq_lambda(crate::Arbiter::Ssimulacra2, 1.);
let minus = (ideal - super::DequantBias::DEFAULT[1].level(-1)).powi(2)
+ rate * prices.token_bits(Token::new(0, pack_signed(-1)));
let plus = (ideal - super::DequantBias::DEFAULT[1].level(1)).powi(2)
+ rate * prices.token_bits(Token::new(0, pack_signed(1)));
let tail = costs0[0][1];
if plus < minus && plus + tail == minus + tail {
collapsed += 1;
assert_eq!(choices1[2], 1);
assert_eq!(choices1[3], 1);
}
}
assert!(
collapsed > 0,
"must exercise distinct local costs with equal totals"
);
}
}