use crate::bit_writer::BitWriter;
use crate::coder_scratch::DcPredictorScratch;
use crate::dc_group_data::DcGroupData;
use crate::entropy::{Token, f_log2, pack_signed};
use crate::static_entropy_codes::{
K_CONTEXT_TREE_TOKENS, K_GRADIENT_CONTEXT_LUT, K_NUM_DC_CONTEXTS,
};
use crate::weighted_predictor::WpParams;
const K_NUM_TREE_CONTEXTS: usize = 6;
pub(super) const K_GRAD_RANGE_MID: i64 = 512;
pub(super) const K_GRAD_RANGE_MIN: i64 = 0;
pub(super) const K_GRAD_RANGE_MAX: i64 = 1023;
#[inline]
pub(super) fn clamped_gradient(n: i32, w: i32, l: i32) -> i32 {
let mn = n.min(w);
let mx = n.max(w);
let g = (n as i64 + w as i64 - l as i64) as i32;
g.clamp(mn, mx)
}
#[inline(always)]
fn push_dc_wp_token(
tokens: &mut Vec<Token>,
gradient_tokens: &mut Vec<Token>,
collect_gradient: bool,
wp: &mut crate::weighted_predictor::WpState,
x: usize,
y: usize,
value: i64,
n: i64,
w: i64,
ne: i64,
nw: i64,
nn: i64,
dc_gradient: &DcPredictorChoice,
mchan: usize,
props: &mut Vec<crate::dc_tree::DcProp>,
collect_props: bool,
) {
let wp_prediction = wp.predict(x, y, n, w, ne, nw, nn);
let prop = (K_GRAD_RANGE_MID + wp.wp_prop).clamp(K_GRAD_RANGE_MIN, K_GRAD_RANGE_MAX) as usize;
if collect_props {
props.push(crate::dc_tree::dc_prop(mchan, prop));
}
wp.update(value, x, y);
let context = K_GRADIENT_CONTEXT_LUT[prop] as usize;
let prediction = if dc_gradient[context] {
(n + w - nw).clamp(n.min(w), n.max(w))
} else {
wp_prediction
};
tokens.push(Token::new(
context as u32,
pack_signed((value - prediction) as i32),
));
if collect_gradient {
let gradient = (n + w - nw).clamp(n.min(w), n.max(w));
gradient_tokens.push(Token::new(
context as u32,
pack_signed((value - gradient) as i32),
));
}
}
pub(super) type DcPredictorChoice = [bool; K_NUM_DC_CONTEXTS];
pub(crate) const DC_PREDICTOR_WEIGHTED: DcPredictorChoice = [false; K_NUM_DC_CONTEXTS];
pub(super) const DC_PREDICTOR_GRADIENT: DcPredictorChoice = [true; K_NUM_DC_CONTEXTS];
pub(super) fn choose_dc_predictors(
wp: &[Vec<Token>],
grad: &[Vec<Token>],
scratch: &mut DcPredictorScratch,
) -> DcPredictorChoice {
let counts = &mut scratch.counts;
let extra = &mut scratch.extra;
counts.as_flattened_mut().fill(0);
extra.fill(0);
for (cand, groups) in [wp, grad].into_iter().enumerate() {
for token in groups.iter().flatten() {
let (sym, nbits, _) = crate::entropy::uint_encode(token.value);
let slot = cand * K_NUM_DC_CONTEXTS + token.context as usize;
counts[slot][sym as usize] += 1;
extra[slot] += nbits as u64;
}
}
choose_dc_predictors_from_counts(scratch)
}
pub(super) fn choose_dc_predictors_from_counts(scratch: &DcPredictorScratch) -> DcPredictorChoice {
let counts = &scratch.counts;
let extra = &scratch.extra;
let cost = |slot: usize| -> f64 {
let total: u32 = counts[slot].iter().sum();
if total == 0 {
return 0.0;
}
let total = f64::from(total);
let entropy: f64 = counts[slot]
.iter()
.filter(|&&n| n != 0)
.map(|&n| f64::from(n) * f_log2(total / f64::from(n)))
.sum();
entropy + extra[slot] as f64
};
let mut choice = DC_PREDICTOR_WEIGHTED;
for (ctx, out) in choice.iter_mut().enumerate() {
let (wp_cost, grad_cost) = (cost(ctx), cost(K_NUM_DC_CONTEXTS + ctx));
let populated = counts[ctx].iter().sum::<u32>() >= MIN_TOKENS_PER_DC_LEAF;
*out = populated && grad_cost < wp_cost * DC_PREDICTOR_MARGIN;
}
choice
}
const MIN_TOKENS_PER_DC_LEAF: u32 = 256;
const DC_PREDICTOR_MARGIN: f64 = 0.995;
#[cfg(test)]
fn collect_dc_tokens(
dc_data: &DcGroupData,
dc_gradient: &DcPredictorChoice,
props: &mut Vec<crate::dc_tree::DcProp>,
collect_props: bool,
) -> Vec<Token> {
collect_dc_tokens_with_gradient(
dc_data,
dc_gradient,
props,
collect_props,
false,
WpParams::DEFAULT,
)
.0
}
pub(crate) fn collect_dc_tokens_with_gradient(
dc_data: &DcGroupData,
dc_gradient: &DcPredictorChoice,
props: &mut Vec<crate::dc_tree::DcProp>,
collect_props: bool,
collect_gradient: bool,
wp_params: WpParams,
) -> (Vec<Token>, Vec<Token>) {
let token_count = [1usize, 0, 2]
.into_iter()
.map(|c| dc_data.quant_dc.plane(c).as_slice().len())
.sum();
let mut tokens = Vec::with_capacity(token_count);
let mut gradient_tokens = Vec::with_capacity(if collect_gradient { token_count } else { 0 });
for (mchan, c) in [1usize, 0, 2].into_iter().enumerate() {
let (channel_tokens, channel_gradient) = collect_dc_channel_tokens(
dc_data,
mchan,
c,
dc_gradient,
props,
collect_props,
collect_gradient,
wp_params,
);
tokens.extend(channel_tokens);
gradient_tokens.extend(channel_gradient);
}
(tokens, gradient_tokens)
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn collect_dc_channel_tokens(
dc_data: &DcGroupData,
mchan: usize,
c: usize,
dc_gradient: &DcPredictorChoice,
props: &mut Vec<crate::dc_tree::DcProp>,
collect_props: bool,
collect_gradient: bool,
wp_params: WpParams,
) -> (Vec<Token>, Vec<Token>) {
let plane = dc_data.quant_dc.plane(c);
let token_count = plane.as_slice().len();
let mut tokens = Vec::with_capacity(token_count);
let mut gradient_tokens = Vec::with_capacity(if collect_gradient { token_count } else { 0 });
walk_dc_channel(
plane.as_slice(),
plane.xsize(),
plane.ysize(),
plane.xsize(),
mchan,
dc_gradient,
props,
collect_props,
collect_gradient,
wp_params,
&mut tokens,
&mut gradient_tokens,
);
(tokens, gradient_tokens)
}
#[allow(clippy::too_many_arguments)]
pub(super) fn walk_dc_channel<T: Copy + Into<i64>>(
data: &[T],
xsize: usize,
ysize: usize,
stride: usize,
mchan: usize,
dc_gradient: &DcPredictorChoice,
props: &mut Vec<crate::dc_tree::DcProp>,
collect_props: bool,
collect_gradient: bool,
wp_params: WpParams,
tokens: &mut Vec<Token>,
gradient_tokens: &mut Vec<Token>,
) {
if xsize == 0 || ysize == 0 {
return;
}
let row = |y: usize| &data[y * stride..y * stride + xsize];
let mut wp = crate::weighted_predictor::WpState::with_params(xsize, wp_params);
let first_row = row(0);
let mut left = 0i64;
for (x, &value) in first_row.iter().enumerate() {
let value: i64 = value.into();
push_dc_wp_token(
tokens,
gradient_tokens,
collect_gradient,
&mut wp,
x,
0,
value,
left,
left,
left,
left,
left,
dc_gradient,
mchan,
props,
collect_props,
);
left = value;
}
let mut row_above = first_row;
let mut row_above2 = first_row;
for y in 1..ysize {
let current_row = row(y);
let n: i64 = row_above[0].into();
let ne: i64 = row_above.get(1).copied().unwrap_or(row_above[0]).into();
push_dc_wp_token(
tokens,
gradient_tokens,
collect_gradient,
&mut wp,
0,
y,
current_row[0].into(),
n,
n,
ne,
n,
row_above2[0].into(),
dc_gradient,
mchan,
props,
collect_props,
);
let current_pairs = current_row.array_windows::<2>();
let north_triplets = row_above.array_windows::<3>();
for (offset, ((current, north), &nn)) in current_pairs
.zip(north_triplets)
.zip(row_above2.iter().skip(1))
.enumerate()
{
push_dc_wp_token(
tokens,
gradient_tokens,
collect_gradient,
&mut wp,
offset + 1,
y,
current[1].into(),
north[1].into(),
current[0].into(),
north[2].into(),
north[0].into(),
nn.into(),
dc_gradient,
mchan,
props,
collect_props,
);
}
if xsize > 1 {
let x = xsize - 1;
let n: i64 = row_above[x].into();
push_dc_wp_token(
tokens,
gradient_tokens,
collect_gradient,
&mut wp,
x,
y,
current_row[x].into(),
n,
current_row[x - 1].into(),
n,
row_above[x - 1].into(),
row_above2[x].into(),
dc_gradient,
mchan,
props,
collect_props,
);
}
row_above2 = row_above;
row_above = current_row;
}
}
pub(crate) fn price_dc_plane(levels: &[i32], width: usize, height: usize, stride: usize) -> f64 {
let mut price = DcPlanePrice::default();
price.add(levels, width, height, stride);
price.bits()
}
pub(crate) struct DcPlanePrice {
pub(super) tokens: Vec<Token>,
pub(super) counts: Vec<[u32; crate::entropy::ALPHABET_SIZE]>,
pub(super) raw_bits: u64,
}
impl Default for DcPlanePrice {
fn default() -> Self {
Self {
tokens: Vec::new(),
counts: vec![[0; crate::entropy::ALPHABET_SIZE]; K_NUM_DC_CONTEXTS],
raw_bits: 0,
}
}
}
impl DcPlanePrice {
pub(crate) fn clear(&mut self) {
self.counts.as_flattened_mut().fill(0);
self.raw_bits = 0;
}
pub(crate) fn add<T: Copy + Into<i64>>(
&mut self,
levels: &[T],
width: usize,
height: usize,
stride: usize,
) {
self.tokens.clear();
walk_dc_channel(
levels,
width,
height,
stride,
0,
&DC_PREDICTOR_WEIGHTED,
&mut Vec::new(),
false,
false,
WpParams::DEFAULT,
&mut self.tokens,
&mut Vec::new(),
);
for token in &self.tokens {
let (sym, nbits, _) = crate::entropy::uint_encode(token.value);
self.counts[token.context as usize][sym as usize] += 1;
self.raw_bits += u64::from(nbits);
}
}
pub(super) fn add_token(&mut self, token: Token) {
let (sym, nbits, _) = crate::entropy::uint_encode(token.value);
self.counts[token.context as usize][sym as usize] += 1;
self.raw_bits += u64::from(nbits);
}
pub(super) fn merge(&mut self, other: &Self) {
for (mine, theirs) in self.counts.iter_mut().zip(&other.counts) {
for (count, &extra) in mine.iter_mut().zip(theirs) {
*count += extra;
}
}
self.raw_bits += other.raw_bits;
}
pub(crate) fn bits(&self) -> f64 {
let mut bits = self.raw_bits as f64;
for ctx in &self.counts {
let total: u32 = ctx.iter().sum();
if total == 0 {
continue;
}
let total = f64::from(total);
bits += ctx
.iter()
.filter(|&&n| n != 0)
.map(|&n| f64::from(n) * f_log2(total / f64::from(n)))
.sum::<f64>();
}
bits
}
}
pub(crate) fn write_context_tree(
num_dc_groups: usize,
dc_gradient: &DcPredictorChoice,
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
writer: &mut BitWriter,
) {
let tokens = context_tree_tokens(num_dc_groups, dc_gradient);
write_tree_tokens(&tokens, huffman_pool, writer);
}
fn context_tree_tokens(num_dc_groups: usize, dc_gradient: &DcPredictorChoice) -> Vec<Token> {
let mut tokens: Vec<Token> = K_CONTEXT_TREE_TOKENS
.iter()
.map(|&(ctx, val)| Token::new(ctx, val))
.collect();
tokens[1].value = pack_signed(1 + num_dc_groups as i32);
{
let mut i = 0usize;
let mut leaf_idx = 0usize;
while i < tokens.len() {
debug_assert_eq!(tokens[i].context, 1);
if tokens[i].value == 0 {
if leaf_idx >= 11 && tokens[i + 1].value == 5 && !dc_gradient[leaf_idx] {
tokens[i + 1] = Token::new(2, 6); }
leaf_idx += 1;
i += 5;
} else {
if tokens[i].value == 9 + 1 {
tokens[i] = Token::new(1, 15 + 1); }
i += 2; }
}
}
tokens
}
pub(crate) fn write_tree_tokens(
tokens: &[Token],
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
writer: &mut BitWriter,
) {
writer.write(1, 1); crate::entropy::write_raced_token_stream(tokens, K_NUM_TREE_CONTEXTS, huffman_pool, writer);
}
#[derive(Clone)]
pub(super) enum DcTreeChoice {
Static(DcPredictorChoice),
Learned(Vec<Token>),
}
impl DcTreeChoice {
pub(super) fn tokens(&self, num_dc_groups: usize) -> Vec<Token> {
match self {
Self::Static(grad) => context_tree_tokens(num_dc_groups, grad),
Self::Learned(tokens) => tokens.clone(),
}
}
}
#[derive(Clone, Copy)]
pub(super) enum ModularTreeNode {
Split {
prop: u32,
val: u32,
gt: usize,
le: usize,
},
Leaf([u32; 4]),
}
pub(super) fn parse_tree(tokens: &[Token]) -> Vec<ModularTreeNode> {
let mut nodes = Vec::new();
let mut declared = 1usize;
let mut i = 0usize;
while nodes.len() < declared {
let prop = tokens[i].value;
if prop == 0 {
let leaf = std::array::from_fn(|k| tokens[i + 1 + k].value);
nodes.push(ModularTreeNode::Leaf(leaf));
i += 5;
} else {
nodes.push(ModularTreeNode::Split {
prop,
val: tokens[i + 1].value,
gt: declared,
le: declared + 1,
});
declared += 2;
i += 2;
}
}
debug_assert_eq!(i, tokens.len());
nodes
}
pub(crate) struct CompactedTree {
pub(crate) tokens: Vec<Token>,
pub(crate) context_map: Vec<u8>,
pub(crate) leaf_remap: Vec<u32>,
}
pub(super) fn compact_tree(tokens: &[Token], context_map: &[u8]) -> Option<CompactedTree> {
use ModularTreeNode::{Leaf, Split};
let nodes = parse_tree(tokens);
let mut leaves: Vec<Option<([u32; 4], u8)>> = vec![None; nodes.len()];
let mut context = 0;
for (i, node) in nodes.iter().enumerate() {
if let Leaf(value) = *node {
leaves[i] = Some((value, context_map[context]));
context += 1;
}
}
debug_assert_eq!(context, context_map.len());
let mut collapsed = false;
for i in (0..nodes.len()).rev() {
if let Split { gt, le, .. } = nodes[i]
&& leaves[gt].is_some()
&& leaves[le] == leaves[gt]
{
leaves[i] = leaves[gt];
collapsed = true;
}
}
if !collapsed || leaves[0].is_some() {
return None;
}
let mut queue = std::collections::VecDeque::from([0]);
let mut remapped_nodes = vec![0u32; nodes.len()];
let mut new_tokens = Vec::with_capacity(tokens.len());
let mut new_map = Vec::with_capacity(context_map.len());
while let Some(i) = queue.pop_front() {
if let Some((value, cluster)) = leaves[i] {
remapped_nodes[i] = new_map.len() as u32;
new_map.push(cluster);
new_tokens.push(Token::new(1, 0));
new_tokens.extend(
value
.into_iter()
.enumerate()
.map(|(k, v)| Token::new(2 + k as u32, v)),
);
} else if let Split { prop, val, gt, le } = nodes[i] {
new_tokens.push(Token::new(1, prop));
new_tokens.push(Token::new(0, val));
queue.extend([gt, le]);
}
}
for i in 0..nodes.len() {
if let Split { gt, le, .. } = nodes[i]
&& leaves[i].is_some()
{
remapped_nodes[gt] = remapped_nodes[i];
remapped_nodes[le] = remapped_nodes[i];
}
}
let leaf_remap = nodes
.into_iter()
.zip(remapped_nodes)
.filter_map(|(node, id)| matches!(node, Leaf(_)).then_some(id))
.collect();
Some(CompactedTree {
tokens: new_tokens,
context_map: new_map,
leaf_remap,
})
}
#[cfg(test)]
mod tests {
use super::*;
fn leaf_tokens(context: u32, value: u32, n: usize) -> Vec<Vec<Token>> {
vec![(0..n).map(|_| Token::new(context, value)).collect()]
}
#[test]
fn dc_plane_price_pools_histograms_and_restarts_prediction() {
let mut price = super::DcPlanePrice::default();
price.add(&[0i16], 1, 1, 1);
price.add(&[1i16], 1, 1, 1);
assert_eq!(price.bits(), 2.0);
price.clear();
assert_eq!(price.bits(), 0.0);
price.add(&[100i16], 1, 1, 1);
price.add(&[100i16], 1, 1, 1);
assert_eq!(price.bits(), 2.0 * super::price_dc_plane(&[100], 1, 1, 1));
assert!(super::price_dc_plane(&[100, 100], 2, 1, 2) < price.bits());
}
#[test]
fn dc_predictor_flips_only_on_a_decisive_populated_win() {
let n = MIN_TOKENS_PER_DC_LEAF as usize;
let ctx = 11;
let mut scratch = DcPredictorScratch::default();
let decisive = choose_dc_predictors(
&leaf_tokens(ctx, 4000, n),
&leaf_tokens(ctx, 0, n),
&mut scratch,
);
assert!(decisive[ctx as usize], "a decisive gradient win must flip");
let tied = choose_dc_predictors(
&leaf_tokens(ctx, 7, n),
&leaf_tokens(ctx, 7, n),
&mut scratch,
);
assert!(!tied[ctx as usize], "a tie must not flip");
let sparse = choose_dc_predictors(
&leaf_tokens(ctx, 4000, n - 1),
&leaf_tokens(ctx, 0, n - 1),
&mut scratch,
);
assert!(
!sparse[ctx as usize],
"an underpopulated leaf must not flip"
);
}
}
#[cfg(test)]
mod fused_dc_tests {
use super::*;
#[test]
fn fused_dc_candidates_match_separate_predictor_traversals() {
for w in [1, 2, 3, 9, 32] {
for h in [1, 2, 3, 17] {
let mut dc = DcGroupData::new(w, h).unwrap();
for c in 0..3 {
for y in 0..h {
for x in 0..w {
let i = (y * w + x + 1) * (c + 7);
dc.quant_dc.plane_row_mut(c, y)[x] =
(((i * 7919) ^ (i / 7 * 1237)) % 65536) as i16;
}
}
}
for collect_props in [false, true] {
for choice in [
DC_PREDICTOR_WEIGHTED,
DC_PREDICTOR_GRADIENT,
std::array::from_fn(|i| i % 2 == 0),
] {
let mut expected_props = Vec::new();
let expected =
collect_dc_tokens(&dc, &choice, &mut expected_props, collect_props);
let grad =
collect_dc_tokens(&dc, &DC_PREDICTOR_GRADIENT, &mut Vec::new(), false);
let mut props = Vec::new();
let (fused, fused_grad) = collect_dc_tokens_with_gradient(
&dc,
&choice,
&mut props,
collect_props,
true,
WpParams::DEFAULT,
);
let values = |ts: Vec<Token>| {
ts.into_iter()
.map(|t| (t.context, t.value))
.collect::<Vec<_>>()
};
assert_eq!(values(fused), values(expected));
assert_eq!(values(fused_grad), values(grad));
assert_eq!(props, expected_props);
}
}
}
}
}
}