use super::dc_tokens::{
DC_PREDICTOR_GRADIENT, DC_PREDICTOR_WEIGHTED, DcTreeChoice, choose_dc_predictors,
collect_dc_channel_tokens, collect_dc_tokens_with_gradient, write_context_tree,
write_tree_tokens,
};
use super::metadata::collect_ac_metadata_tokens;
use crate::bit_writer::BitWriter;
use crate::coder_scratch::CoderScratch;
use crate::dc_group_data::DcGroupData;
use crate::encoding_context::EncodingContext;
use crate::entropy::{EntropyCode, OwnedEntropyCode, Token, f_log2, write_entropy_code};
use crate::static_entropy_codes::K_NUM_DC_CONTEXTS;
use crate::weighted_predictor::WpParams;
pub(crate) struct DcEntropy {
pub(crate) tree: DcTreeChoice,
pub(crate) dc: Vec<Vec<Token>>,
pub(crate) meta: Vec<Vec<Token>>,
pub(crate) code: OwnedEntropyCode,
pub(crate) refinement: Option<crate::entropy::AnsRefinement>,
pub(crate) wp_params: WpParams,
pub(crate) ma_tree: Option<MaDcTrees>,
pub(crate) ma_leaf_ctx: Vec<u32>,
pub(crate) ma_offsets: Vec<i32>,
}
impl DcEntropy {
pub(crate) fn bits(&self, num_dc_groups: usize, scratch: &mut CoderScratch) -> u64 {
self.bits_with(num_dc_groups, scratch, &self.dc, self.wp_params)
}
pub(crate) fn bits_with(
&self,
num_dc_groups: usize,
scratch: &mut CoderScratch,
dc: &[Vec<Token>],
wp_params: WpParams,
) -> u64 {
let mut w = BitWriter::new();
crate::weighted_predictor::write_wp_header(wp_params, &mut w);
match &self.tree {
DcTreeChoice::Static(grad) => {
write_context_tree(num_dc_groups, grad, &mut scratch.huffman_pool, &mut w);
}
DcTreeChoice::Learned(tokens) => {
write_tree_tokens(tokens, &mut scratch.huffman_pool, &mut w);
}
}
write_entropy_code(&self.code.as_ref(), &mut scratch.huffman_pool, &mut w);
w.bits_written() as u64
+ crate::entropy::estimate_ac_plain_bits(
dc.iter()
.map(Vec::as_slice)
.chain(self.meta.iter().map(Vec::as_slice)),
&self.code,
)
}
pub(crate) fn dc_tokens_under(
&self,
ctx: &EncodingContext,
scratch: &mut CoderScratch,
dc_datas: &[DcGroupData],
wp_params: WpParams,
) -> Option<Vec<Vec<Token>>> {
let trees = self.ma_tree.as_ref()?;
if self.ma_leaf_ctx.is_empty() {
return None;
}
let groups = dc_planes(dc_datas);
let pool = &ctx.thread_pool;
if self.ma_offsets.iter().all(|&o| o == 0) {
return Some(tokenize_streams(
pool,
scratch,
&groups,
&trees.dc,
&self.ma_leaf_ctx,
wp_params,
));
}
let identity: Vec<u32> = (0..trees.dc.nodes.len() as u32).collect();
let mut tokens = tokenize_streams(pool, scratch, &groups, &trees.dc, &identity, wp_params);
crate::dc_tree::apply_leaf_offsets(&mut tokens, &self.ma_offsets);
let leaf_ctx = &self.ma_leaf_ctx;
Some(pool.map(tokens.len(), |g| {
tokens[g]
.iter()
.map(|t| Token::new(leaf_ctx[t.context as usize], t.value))
.collect()
}))
}
pub(crate) fn warmed(
&self,
ctx: &EncodingContext,
scratch: &mut CoderScratch,
dc: Vec<Vec<Token>>,
wp_params: WpParams,
) -> Option<DcEntropy> {
let streams = || {
dc.iter()
.map(Vec::as_slice)
.chain(self.meta.iter().map(Vec::as_slice))
};
let mut code =
crate::entropy::recount_entropy_code(&self.code, streams(), &ctx.thread_pool, scratch)?;
crate::entropy::refine_entropy_bundle(
&mut code,
streams(),
crate::entropy::AnsRefinement::Slow,
&ctx.thread_pool,
scratch,
);
Some(DcEntropy {
tree: self.tree.clone(),
dc,
meta: self.meta.clone(),
code,
refinement: self.refinement,
wp_params,
ma_tree: self.ma_tree.clone(),
ma_leaf_ctx: self.ma_leaf_ctx.clone(),
ma_offsets: self.ma_offsets.clone(),
})
}
}
pub(crate) fn dc_wp_proxy_bits(
pool: &crate::thread_pool::ThreadPool,
scratch: &mut CoderScratch,
dc_datas: &[DcGroupData],
params: WpParams,
) -> f64 {
let groups: Vec<(Vec<Token>, Vec<Token>)> =
pool.steal_map(scratch, dc_datas.len(), |i, _scratch| {
collect_dc_tokens_with_gradient(
&dc_datas[i],
&DC_PREDICTOR_WEIGHTED,
&mut Vec::new(),
false,
true,
params,
)
});
let (wp, grad): (Vec<_>, Vec<_>) = groups.into_iter().unzip();
let flips = choose_dc_predictors(&wp, &grad, &mut scratch.dc_predictor);
const SYMBOLS: usize = 64;
let mut counts = vec![0u64; K_NUM_DC_CONTEXTS * SYMBOLS];
let mut raw_bits = 0u64;
for (wp, grad) in wp.iter().zip(&grad) {
for (w, g) in wp.iter().zip(grad) {
let t = if flips[w.context as usize] { g } else { w };
let (sym, nbits, _) = crate::entropy::uint_encode(t.value);
counts[t.context as usize * SYMBOLS + (sym as usize).min(SYMBOLS - 1)] += 1;
raw_bits += u64::from(nbits);
}
}
let mut bits = raw_bits as f64;
for hist in counts.chunks(SYMBOLS) {
let total: u64 = hist.iter().sum();
if total == 0 {
continue;
}
let total = total as f64;
bits += hist
.iter()
.filter(|&&c| c != 0)
.map(|&c| c as f64 * f_log2(total / c as f64))
.sum::<f64>();
}
bits
}
pub(crate) fn fit_dc_wp_params(
ctx: &EncodingContext,
scratch: &mut CoderScratch,
dc_datas: &[DcGroupData],
start: WpParams,
) -> WpParams {
const ROUNDS: usize = 3;
const P_MAX: i64 = 31;
const W_MAX: u32 = 15;
let mut best = start;
let mut best_bits = dc_wp_proxy_bits(&ctx.thread_pool, scratch, dc_datas, best);
for _ in 0..ROUNDS {
let mut improved = false;
for coord in 0..11 {
for delta in [-1i64, 1] {
let mut candidate = best;
if coord < 7 {
let v = candidate.p[coord] + delta;
if !(0..=P_MAX).contains(&v) {
continue;
}
candidate.p[coord] = v;
} else {
let v = candidate.w[coord - 7] as i64 + delta;
if !(0..=i64::from(W_MAX)).contains(&v) {
continue;
}
candidate.w[coord - 7] = v as u32;
}
let bits = dc_wp_proxy_bits(&ctx.thread_pool, scratch, dc_datas, candidate);
if bits < best_bits {
best = candidate;
best_bits = bits;
improved = true;
}
}
}
if !improved {
break;
}
}
best
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn prepare_dc_entropy(
ctx: &EncodingContext,
scratch: &mut CoderScratch,
dc_datas: &[DcGroupData],
num_dc_groups: usize,
epf_sharpness: i32,
use_dc_frame: bool,
distance: f32,
wp_params: WpParams,
ma_tree: Option<&MaDcTrees>,
) -> DcEntropy {
let effort = ctx.speed.effort();
let dc_predictor_search = effort.dc_predictor_search || effort.dc_learned_tree;
const PARTS: usize = 4;
let parts = ctx
.thread_pool
.steal_map(scratch, dc_datas.len() * PARTS, |i, _scratch| {
let (group, part) = (i / PARTS, i % PARTS);
let predictor = if dc_predictor_search {
&DC_PREDICTOR_WEIGHTED
} else {
&DC_PREDICTOR_GRADIENT
};
let mut props = Vec::new();
if part < 3 {
let (wp, grad) = if use_dc_frame {
(Vec::new(), Vec::new())
} else {
collect_dc_channel_tokens(
&dc_datas[group],
part,
[1usize, 0, 2][part],
predictor,
&mut props,
effort.dc_learned_tree,
dc_predictor_search,
wp_params,
)
};
(wp, props, grad)
} else {
let meta = collect_ac_metadata_tokens(
&dc_datas[group],
&mut props,
epf_sharpness,
effort.dc_learned_tree,
);
(meta, props, Vec::new())
}
});
let mut wp_tokens_per_group = Vec::with_capacity(dc_datas.len());
let mut props_per_group = Vec::with_capacity(dc_datas.len());
let mut grad_tokens_per_group = Vec::with_capacity(dc_datas.len());
let mut meta_tokens_per_group = Vec::with_capacity(dc_datas.len());
let mut meta_props_per_group = Vec::with_capacity(dc_datas.len());
let mut parts = parts.into_iter();
for _ in 0..dc_datas.len() {
let (mut wp, mut props, mut grad) = (Vec::new(), Vec::new(), Vec::new());
for _ in 0..3 {
let (channel_wp, channel_props, channel_grad) = parts.next().expect("channel part");
wp.extend(channel_wp);
props.extend(channel_props);
grad.extend(channel_grad);
}
let (meta, meta_props, _) = parts.next().expect("metadata part");
wp_tokens_per_group.push(wp);
props_per_group.push(props);
grad_tokens_per_group.push(grad);
meta_tokens_per_group.push(meta);
meta_props_per_group.push(meta_props);
}
let payload =
|dc: &[Vec<Token>], meta: &[Vec<Token>], code: &crate::entropy::OwnedEntropyCode| {
crate::entropy::estimate_ac_plain_bits(
dc.iter()
.map(Vec::as_slice)
.chain(meta.iter().map(Vec::as_slice)),
code,
)
};
let header = |tree: &DcTreeChoice, code: &EntropyCode, scratch: &mut CoderScratch| {
let mut w = BitWriter::new();
match tree {
DcTreeChoice::Static(grad) => {
write_context_tree(num_dc_groups, grad, &mut scratch.huffman_pool, &mut w);
}
DcTreeChoice::Learned(tokens) => {
write_tree_tokens(tokens, &mut scratch.huffman_pool, &mut w);
}
}
write_entropy_code(code, &mut scratch.huffman_pool, &mut w);
w.bits_written() as u64
};
const LEARNED_TREE_MARGIN_BITS: u64 = 64;
let ans_refinement = if effort.ans_refine {
Some(crate::entropy::AnsRefinement::slow_for_speed(ctx.speed))
} else if effort.ans_fast_refine && !effort.ans_prefix_race {
Some(crate::entropy::AnsRefinement::FastNoRace)
} else if effort.ans_fast_refine {
Some(crate::entropy::AnsRefinement::Fast {
recluster: (distance >= 3.0 && effort.ans_recluster_coarse) || effort.ans_recluster,
})
} else {
None
};
let mut learned_ma_tree: Option<MaDcTrees> = None;
let mut ma_leaf_map: (Vec<u32>, Vec<i32>) = (Vec::new(), Vec::new());
let dc_samples: usize = dc_datas
.iter()
.map(|d| {
(0..3)
.map(|c| d.quant_dc.plane(c).xsize() * d.quant_dc.plane(c).ysize())
.sum::<usize>()
})
.sum();
let ma_budget = ma_dc_budget(effort).filter(|budget| dc_samples >= budget.min_samples);
let ma_arm = if use_dc_frame {
None
} else {
ma_budget
.and_then(|budget| {
learn_ma_dc_arm(
&ctx.thread_pool,
scratch,
dc_datas,
&meta_tokens_per_group,
&meta_props_per_group,
epf_sharpness,
wp_params,
ma_tree,
budget,
)
})
.and_then(|(arms, trees)| {
let price = |arm: MaDcArm, scratch: &mut CoderScratch| {
let MaDcArm {
dc: dc_tokens,
meta: meta_tokens,
tree: tree_tokens,
num_contexts,
dc_leaf_ctx,
offsets,
meta_learned,
} = arm;
let streams = || {
dc_tokens
.iter()
.map(Vec::as_slice)
.chain(meta_tokens.iter().map(Vec::as_slice))
};
let mut code = crate::entropy::optimize_entropy_code_ac_streams(
streams(),
num_contexts,
&mut scratch.huffman_pool,
true,
ctx.speed,
Some(&ctx.thread_pool),
);
crate::entropy::refine_entropy_bundle(
&mut code,
streams(),
crate::entropy::AnsRefinement::Slow,
&ctx.thread_pool,
scratch,
);
let tree = DcTreeChoice::Learned(tree_tokens);
let cost = header(&tree, &code.as_ref(), scratch)
+ payload(&dc_tokens, &meta_tokens, &code);
(
cost,
dc_tokens,
meta_tokens,
code,
tree,
dc_leaf_ctx,
offsets,
meta_learned,
)
};
let price_arms = |arms: Vec<MaDcArm>, scratch: &mut CoderScratch| {
let mut slots: Vec<_> = arms.into_iter().map(|arm| (Some(arm), None)).collect();
ctx.thread_pool
.steal_for_each_mut(scratch, &mut slots, |_, slot, scratch| {
slot.1 = slot.0.take().map(|arm| price(arm, scratch));
});
slots
.into_iter()
.filter_map(|slot| slot.1)
.collect::<Vec<_>>()
};
let mut best = price_arms(arms, scratch).into_iter().min_by_key(|v| v.0)?;
let mut trees = trees;
if effort.ma_dc_repick()
&& let Some(repicked) = repick_leaf_predictors(
dc_datas, &trees, &best.5, &best.6, &best.3, wp_params,
)
{
let with_offsets = best.6.iter().any(|&o| o != 0);
let arms = assemble_ma_arms(
&ctx.thread_pool,
scratch,
dc_datas,
&meta_tokens_per_group,
&meta_props_per_group,
epf_sharpness,
wp_params,
&repicked,
with_offsets,
);
let arms = arms
.into_iter()
.filter(|arm| {
arm.meta_learned == best.7
&& arm.offsets.iter().any(|&o| o != 0) == with_offsets
})
.collect();
if let Some(better) = price_arms(arms, scratch).into_iter().min_by_key(|v| v.0)
&& better.0 < best.0
{
best = better;
trees = repicked;
}
}
learned_ma_tree = Some(trees);
ma_leaf_map = (best.5, best.6);
Some((best.0, best.1, best.2, best.3, best.4))
})
};
let (dc_tokens_per_group, meta_tokens_per_group, mut dc_code_owned, dc_tree, dc_code_refined) =
match ma_arm {
Some((_, dc_tokens, meta_tokens, code, tree)) if dc_samples >= MA_ARM_ALONE_SAMPLES => {
(dc_tokens, meta_tokens, code, tree, true)
}
ma_arm => {
if ma_arm.is_none() {
ma_leaf_map = (Vec::new(), Vec::new());
}
let dc_gradient = if !dc_predictor_search {
DC_PREDICTOR_GRADIENT
} else {
choose_dc_predictors(
&wp_tokens_per_group,
&grad_tokens_per_group,
&mut scratch.dc_predictor,
)
};
let dc_tokens_static: Vec<Vec<Token>> = if !dc_predictor_search {
std::mem::take(&mut wp_tokens_per_group)
} else {
wp_tokens_per_group
.iter()
.zip(&grad_tokens_per_group)
.map(|(wp, grad)| {
wp.iter()
.zip(grad)
.map(|(w, g)| {
if dc_gradient[w.context as usize] {
*g
} else {
*w
}
})
.collect()
})
.collect()
};
let code_static = crate::entropy::optimize_entropy_code_ac_streams(
dc_tokens_static
.iter()
.map(Vec::as_slice)
.chain(meta_tokens_per_group.iter().map(Vec::as_slice)),
K_NUM_DC_CONTEXTS,
&mut scratch.huffman_pool,
effort.huc_select,
ctx.speed,
Some(&ctx.thread_pool),
);
let tree_static = DcTreeChoice::Static(dc_gradient);
let best = if !effort.dc_learned_tree || use_dc_frame {
(
dc_tokens_static,
meta_tokens_per_group,
code_static,
tree_static,
)
} else {
let learned = crate::dc_tree::learn_dc_tree(
num_dc_groups,
&wp_tokens_per_group,
&grad_tokens_per_group,
&props_per_group,
&meta_tokens_per_group,
&meta_props_per_group,
);
let dc_tokens_learned: Vec<Vec<Token>> = wp_tokens_per_group
.iter()
.zip(&grad_tokens_per_group)
.zip(&props_per_group)
.map(|((wp, grad), props)| {
wp.iter()
.zip(grad)
.zip(props)
.map(|((w, g), &p)| {
let ctx = learned.dc_context[p as usize];
let value = if learned.leaf_gradient[ctx as usize] {
g.value
} else {
w.value
};
Token::new(u32::from(ctx), value)
})
.collect()
})
.collect();
let meta_tokens_learned: Vec<Vec<Token>> = meta_tokens_per_group
.iter()
.zip(&meta_props_per_group)
.map(|(group, props)| {
group
.iter()
.zip(props)
.map(|(t, &p)| {
let slot = ((t.context as usize) << 10) | (p & 1023) as usize;
Token::new(u32::from(learned.meta_context[slot]), t.value)
})
.collect()
})
.collect();
let code_learned = crate::entropy::optimize_entropy_code_ac_streams(
dc_tokens_learned
.iter()
.map(Vec::as_slice)
.chain(meta_tokens_learned.iter().map(Vec::as_slice)),
learned.num_contexts,
&mut scratch.huffman_pool,
effort.huc_select,
ctx.speed,
Some(&ctx.thread_pool),
);
let tree_learned = DcTreeChoice::Learned(learned.tokens);
let cost_static = header(&tree_static, &code_static.as_ref(), scratch)
+ payload(&dc_tokens_static, &meta_tokens_per_group, &code_static);
let cost_learned = header(&tree_learned, &code_learned.as_ref(), scratch)
+ payload(&dc_tokens_learned, &meta_tokens_learned, &code_learned);
if cost_learned + LEARNED_TREE_MARGIN_BITS < cost_static {
(
dc_tokens_learned,
meta_tokens_learned,
code_learned,
tree_learned,
)
} else {
(
dc_tokens_static,
meta_tokens_per_group,
code_static,
tree_static,
)
}
};
match ma_arm {
Some((cost, dc_tokens, meta_tokens, code, tree)) => {
let (best_dc, best_meta, mut best_code, best_tree) = best;
crate::entropy::refine_entropy_bundle(
&mut best_code,
best_dc
.iter()
.map(Vec::as_slice)
.chain(best_meta.iter().map(Vec::as_slice)),
crate::entropy::AnsRefinement::Slow,
&ctx.thread_pool,
scratch,
);
let best_cost = header(&best_tree, &best_code.as_ref(), scratch)
+ payload(&best_dc, &best_meta, &best_code);
if cost + LEARNED_TREE_MARGIN_BITS < best_cost {
(dc_tokens, meta_tokens, code, tree, true)
} else {
ma_leaf_map = (Vec::new(), Vec::new());
(best_dc, best_meta, best_code, best_tree, true)
}
}
None => (best.0, best.1, best.2, best.3, false),
}
}
};
drop(wp_tokens_per_group);
drop(grad_tokens_per_group);
drop(props_per_group);
drop(meta_props_per_group);
if let Some(refinement) = ans_refinement.filter(|_| !dc_code_refined) {
crate::entropy::refine_entropy_bundle(
&mut dc_code_owned,
dc_tokens_per_group
.iter()
.map(Vec::as_slice)
.chain(meta_tokens_per_group.iter().map(Vec::as_slice)),
refinement,
&ctx.thread_pool,
scratch,
);
} else if dc_code_refined && ctx.speed.effort().ans_exhaustive() {
crate::entropy::refine_ans_entropy_exhaustive(
&mut dc_code_owned,
dc_tokens_per_group
.iter()
.map(Vec::as_slice)
.chain(meta_tokens_per_group.iter().map(Vec::as_slice)),
&ctx.thread_pool,
scratch,
);
}
DcEntropy {
tree: dc_tree,
dc: dc_tokens_per_group,
meta: meta_tokens_per_group,
code: dc_code_owned,
refinement: ans_refinement,
wp_params,
ma_tree: learned_ma_tree,
ma_leaf_ctx: ma_leaf_map.0,
ma_offsets: ma_leaf_map.1,
}
}
pub(crate) fn write_dc_tree_and_code<'a>(
tree: &DcTreeChoice,
code: &mut OwnedEntropyCode,
streams: impl Iterator<Item = &'a mut Vec<Token>>,
num_dc_groups: usize,
scratch: &mut CoderScratch,
writer: &mut BitWriter,
) {
let tokens = tree.tokens(num_dc_groups);
let candidate = if code.orig_context_map.is_none() {
super::dc_tokens::compact_tree(&tokens, &code.context_map)
} else {
None
};
let mut write_header = |tokens: &[Token], code: &EntropyCode, w: &mut BitWriter| {
write_tree_tokens(tokens, &mut scratch.huffman_pool, w);
w.write(1, 0); write_entropy_code(code, &mut scratch.huffman_pool, w);
};
let Some(candidate) = candidate else {
write_header(&tokens, &code.as_ref(), writer);
return;
};
let mut original_header = BitWriter::new();
let mut compacted_header = BitWriter::new();
let original_code = code.as_ref();
write_header(&tokens, &original_code, &mut original_header);
let mut compacted_code = original_code;
compacted_code.context_map = &candidate.context_map;
compacted_code.num_contexts = candidate.context_map.len();
write_header(&candidate.tokens, &compacted_code, &mut compacted_header);
if compacted_header.bits_written() >= original_header.bits_written() {
writer.append_bits(&original_header);
return;
}
for token in streams.flatten() {
token.context = candidate.leaf_remap[token.context as usize];
}
code.orig_num_contexts = candidate.context_map.len();
code.context_map = candidate.context_map;
writer.append_bits(&compacted_header);
}
const MA_DC_TARGET_SAMPLES: usize = 1 << 19;
const MA_DC_MAX_LEAVES: usize = 400;
const MA_DC_SPLIT_COST_BITS: f32 = 50.0;
const MA_DC_MIN_NODE_SAMPLES: usize = 64;
fn dc_planes(dc_datas: &[DcGroupData]) -> Vec<crate::lossless::DcPlanes> {
dc_datas
.iter()
.enumerate()
.map(|(group, dc)| {
let q = &dc.quant_dc;
let plane = |c: usize| {
q.plane(c)
.as_slice()
.iter()
.map(|&v| i32::from(v))
.collect()
};
let dims = |c: usize| (q.plane(c).xsize(), q.plane(c).ysize());
crate::lossless::DcPlanes {
planes: vec![plane(1), plane(0), plane(2)],
dims: vec![dims(1), dims(0), dims(2)],
stream: 1 + group as i32,
}
})
.collect()
}
fn meta_planes(dc_datas: &[DcGroupData], epf_sharpness: i32) -> Vec<crate::lossless::DcPlanes> {
let num_dc_groups = dc_datas.len();
dc_datas
.iter()
.enumerate()
.map(|(group, dc)| {
let tile = |m: &crate::image::ImageSB| -> Vec<i32> {
m.as_slice().iter().map(|&v| i32::from(v)).collect()
};
let (xt, yt) = (dc.ytox_map.xsize(), dc.ytox_map.ysize());
let (xb, yb) = (dc.ac_strategy.xsize(), dc.ac_strategy.ysize());
let first = dc.ac_strategy.count_first_blocks();
let mut info = Vec::with_capacity(2 * first);
let mut qfs = Vec::with_capacity(first);
for y in 0..yb {
let row = dc.raw_quant_field.row(y);
for x in 0..xb {
if dc.ac_strategy.is_first_block(x, y) {
info.push(dc.ac_strategy.strategy_code(x, y) as i32);
qfs.push(i32::from(row[x]) - 1);
}
}
}
info.extend(qfs);
crate::lossless::DcPlanes {
planes: vec![
tile(&dc.ytox_map),
tile(&dc.ytob_map),
info,
vec![epf_sharpness; xb * yb],
],
dims: vec![(xt, yt), (xt, yt), (first, 2), (xb, yb)],
stream: (1 + 2 * num_dc_groups + group) as i32,
}
})
.collect()
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct MaDcBudget {
pub(crate) target_samples: usize,
pub(crate) max_leaves: usize,
pub(crate) max_candidates: usize,
pub(crate) side_preds: usize,
pub(crate) offsets_variant: bool,
pub(crate) learn_meta: bool,
pub(crate) min_samples: usize,
}
impl MaDcBudget {
pub(crate) const FULL: Self = Self {
target_samples: MA_DC_TARGET_SAMPLES,
max_leaves: MA_DC_MAX_LEAVES,
max_candidates: 32,
side_preds: 14,
offsets_variant: true,
learn_meta: true,
min_samples: 0,
};
pub(crate) const LITE: Self = Self {
target_samples: 1 << 17,
max_leaves: 128,
max_candidates: 8,
side_preds: 4,
offsets_variant: false,
learn_meta: true,
min_samples: 0,
};
pub(crate) const DEEP_LITE: Self = Self {
target_samples: MA_DC_TARGET_SAMPLES,
max_leaves: MA_DC_MAX_LEAVES,
..Self::LITE
};
pub(crate) const XLITE: Self = Self {
target_samples: 1 << 16,
max_leaves: 32,
max_candidates: 4,
side_preds: 1,
offsets_variant: false,
learn_meta: false,
min_samples: 1 << 16,
};
}
#[derive(Clone)]
pub(crate) struct MaDcTrees {
pub(crate) dc: crate::ma_tree::LearnedTree,
pub(crate) meta: Option<crate::ma_tree::LearnedTree>,
}
pub(crate) struct MaDcArm {
pub(crate) dc: Vec<Vec<Token>>,
pub(crate) meta: Vec<Vec<Token>>,
pub(crate) tree: Vec<Token>,
pub(crate) num_contexts: usize,
pub(crate) dc_leaf_ctx: Vec<u32>,
pub(crate) offsets: Vec<i32>,
pub(crate) meta_learned: bool,
}
const MA_META_MAX_LEAVES: usize = 64;
const MA_ARM_ALONE_SAMPLES: usize = 32_768;
const MA_MAX_TREE_CONTEXTS: usize = 512;
fn learn_planes(
pool: &crate::thread_pool::ThreadPool,
scratch: &mut CoderScratch,
planes: &[crate::lossless::DcPlanes],
budget: MaDcBudget,
max_leaves: usize,
wp_params: WpParams,
) -> Option<crate::ma_tree::LearnedTree> {
let total: usize = planes.iter().map(|g| g.len()).sum();
let mut stride = total.div_ceil(budget.target_samples).max(1);
if stride > 1 && stride.is_multiple_of(2) {
stride += 1;
}
let mut samples = crate::lossless::sample_dc_planes(pool, planes, stride, wp_params);
if samples.len() < 4 * MA_DC_MIN_NODE_SAMPLES {
return None;
}
let params = ma_dc_params(&samples, budget, max_leaves, stride);
Some(crate::ma_tree::learn_ma_tree_in_place(
&mut samples,
params,
pool,
scratch,
))
}
fn ma_dc_params(
samples: &crate::ma_tree::MaSamples,
budget: MaDcBudget,
max_leaves: usize,
stride: usize,
) -> crate::ma_tree::MaLearnParams {
let alphabet = samples
.tok
.iter()
.flat_map(|t| t.iter())
.copied()
.max()
.unwrap_or(0) as usize
+ 1;
crate::ma_tree::MaLearnParams {
alphabet,
max_leaves,
split_cost_bits: MA_DC_SPLIT_COST_BITS / stride as f32,
min_node: MA_DC_MIN_NODE_SAMPLES,
allow_wp: true,
allowed_preds: u16::MAX,
side_preds: budget.side_preds,
max_candidates: budget.max_candidates,
modal_offsets: false,
prune_leaf_bits: 0.0,
channel_first: false,
no_wp_channels: 0,
}
}
fn learn_meta_parts(
pool: &crate::thread_pool::ThreadPool,
scratch: &mut CoderScratch,
planes: &[crate::lossless::DcPlanes],
budget: MaDcBudget,
cap: usize,
) -> Option<crate::ma_tree::LearnedTree> {
use crate::ma_tree::{LearnedTree, MaNode};
let total: usize = planes.iter().map(|g| g.len()).sum();
let mut stride = total.div_ceil(budget.target_samples).max(1);
if stride > 1 && stride.is_multiple_of(2) {
stride += 1;
}
let samples = crate::lossless::sample_dc_planes(pool, planes, stride, WpParams::DEFAULT);
let mut idx: [Vec<u32>; 4] = Default::default();
for (i, row) in samples.props.iter().enumerate() {
let part = match (row[0], row[2]) {
(0 | 1, _) => 0,
(2, 0) => 1,
(2, _) => 2,
_ => 3,
};
idx[part].push(i as u32);
}
let caps = [
(cap / 8).max(2),
(cap * 2 / 5).max(4),
(cap * 2 / 5).max(4),
2,
];
let learned: Vec<Option<LearnedTree>> = {
let (samples, idx) = (&samples, &idx);
pool.steal_map(scratch, idx.len(), |part, worker_scratch| {
let part_idx = &idx[part];
if part_idx.len() < MA_DC_MIN_NODE_SAMPLES {
return None;
}
let params = ma_dc_params(samples, budget, caps[part], stride);
Some(crate::ma_tree::learn_ma_tree_indexed(
samples,
part_idx.clone(),
params,
pool,
worker_scratch,
))
})
};
let mut parts: Vec<Vec<MaNode>> = Vec::with_capacity(4);
let mut est_bits = 0.0;
let mut flat_bits = 0.0;
for tree in learned {
match tree {
None => parts.push(vec![MaNode::Leaf { pred: 0, offset: 0 }]),
Some(tree) => {
est_bits += tree.est_bits;
flat_bits += tree.flat_bits;
parts.push(tree.nodes);
}
}
}
let mut nodes = vec![
MaNode::Split {
prop: 0,
val: 2,
gt: 0,
le: 1,
},
MaNode::Split {
prop: 0,
val: 1,
gt: 2,
le: 0,
},
MaNode::Split {
prop: 2,
val: 0,
gt: 0,
le: 0,
},
];
let mut roots = [0u32; 4];
for (part, part_nodes) in parts.into_iter().enumerate() {
let base = nodes.len() as u32;
roots[part] = base;
nodes.extend(part_nodes.into_iter().map(|n| match n {
MaNode::Split { prop, val, gt, le } => MaNode::Split {
prop,
val,
gt: gt + base,
le: le + base,
},
leaf => leaf,
}));
}
nodes[0] = MaNode::Split {
prop: 0,
val: 2,
gt: roots[3],
le: 1,
};
nodes[1] = MaNode::Split {
prop: 0,
val: 1,
gt: 2,
le: roots[0],
};
nodes[2] = MaNode::Split {
prop: 2,
val: 0,
gt: roots[2],
le: roots[1],
};
Some(LearnedTree {
nodes,
est_bits,
flat_bits,
})
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn learn_ma_dc_arm(
pool: &crate::thread_pool::ThreadPool,
scratch: &mut CoderScratch,
dc_datas: &[DcGroupData],
meta_tokens: &[Vec<Token>],
meta_props: &[Vec<crate::dc_tree::DcProp>],
epf_sharpness: i32,
wp_params: WpParams,
reuse: Option<&MaDcTrees>,
budget: MaDcBudget,
) -> Option<(Vec<MaDcArm>, MaDcTrees)> {
let groups = dc_planes(dc_datas);
let trees = match reuse {
Some(trees) => trees.clone(),
None => {
let meta_cap_from_budget = (budget.learn_meta
&& MA_MAX_TREE_CONTEXTS.saturating_sub(budget.max_leaves) >= MA_META_MAX_LEAVES)
.then_some(MA_META_MAX_LEAVES);
let (dc, meta) = match meta_cap_from_budget {
Some(cap) => {
let planes = meta_planes(dc_datas, epf_sharpness);
let mut meta_scratch = CoderScratch::lossless();
pool.join(
|| {
learn_planes(
pool,
scratch,
&groups,
budget,
budget.max_leaves,
wp_params,
)
},
|| learn_meta_parts(pool, &mut meta_scratch, &planes, budget, cap),
)
}
None => {
let dc =
learn_planes(pool, scratch, &groups, budget, budget.max_leaves, wp_params);
let meta = match (&dc, budget.learn_meta) {
(Some(dc), true) => {
let dc_leaves = dc
.nodes
.iter()
.filter(|n| matches!(n, crate::ma_tree::MaNode::Leaf { .. }))
.count();
let cap = MA_META_MAX_LEAVES
.min(MA_MAX_TREE_CONTEXTS.saturating_sub(dc_leaves));
if cap >= 8 {
let planes = meta_planes(dc_datas, epf_sharpness);
learn_meta_parts(pool, scratch, &planes, budget, cap)
} else {
None
}
}
_ => None,
};
(dc, meta)
}
};
let dc = dc?;
MaDcTrees { dc, meta }
}
};
let arms = assemble_ma_arms(
pool,
scratch,
dc_datas,
meta_tokens,
meta_props,
epf_sharpness,
wp_params,
&trees,
budget.offsets_variant,
);
Some((arms, trees))
}
fn tokenize_streams(
pool: &crate::thread_pool::ThreadPool,
scratch: &mut CoderScratch,
streams: &[crate::lossless::DcPlanes],
tree: &crate::ma_tree::LearnedTree,
leaf_ctx: &[u32],
wp_params: WpParams,
) -> Vec<Vec<Token>> {
let channels = crate::lossless::dc_channels(streams);
let parts = pool.steal_map(scratch, channels.len(), |i, _scratch| {
let (g, c) = channels[i];
let (w, h) = streams[g].dims[c];
let mut out = Vec::with_capacity(w * h);
crate::lossless::tokenize_dc_channel(&streams[g], c, tree, leaf_ctx, wp_params, &mut out);
out
});
let mut tokens: Vec<Vec<Token>> = streams
.iter()
.map(|g| Vec::with_capacity(g.len()))
.collect();
for (&(g, _), part) in channels.iter().zip(parts) {
tokens[g].extend(part);
}
tokens
}
#[allow(clippy::too_many_arguments)]
fn assemble_ma_arms(
pool: &crate::thread_pool::ThreadPool,
scratch: &mut CoderScratch,
dc_datas: &[DcGroupData],
meta_tokens: &[Vec<Token>],
meta_props: &[Vec<crate::dc_tree::DcProp>],
epf_sharpness: i32,
wp_params: WpParams,
trees: &MaDcTrees,
offsets_variant: bool,
) -> Vec<MaDcArm> {
let groups = dc_planes(dc_datas);
let num_dc_groups = dc_datas.len();
let dc_identity: Vec<u32> = (0..trees.dc.nodes.len() as u32).collect();
let dc_nodes = tokenize_streams(pool, scratch, &groups, &trees.dc, &dc_identity, wp_params);
let meta_nodes: Option<Vec<Vec<Token>>> = trees.meta.as_ref().map(|meta_tree| {
let planes = meta_planes(dc_datas, epf_sharpness);
let identity: Vec<u32> = (0..meta_tree.nodes.len() as u32).collect();
tokenize_streams(
pool,
scratch,
&planes,
meta_tree,
&identity,
WpParams::DEFAULT,
)
});
let map_ctx = |tokens: &[Vec<Token>], leaf_ctx: &[u32]| -> Vec<Vec<Token>> {
pool.map(tokens.len(), |g| {
tokens[g]
.iter()
.map(|t| Token::new(leaf_ctx[t.context as usize], t.value))
.collect()
})
};
let static_meta = |meta_context: &[u16]| -> Vec<Vec<Token>> {
pool.map(meta_tokens.len(), |g| {
meta_tokens[g]
.iter()
.zip(&meta_props[g])
.map(|(t, &p)| {
let slot = ((t.context as usize) << 10) | (p & 1023) as usize;
Token::new(u32::from(meta_context[slot]), t.value)
})
.collect()
})
};
let node_offsets = crate::dc_tree::median_leaf_offsets(&dc_nodes, trees.dc.nodes.len());
let with_offsets = offsets_variant && node_offsets.iter().any(|&o| o != 0);
let zero_offsets = vec![0i32; trees.dc.nodes.len()];
let mut arms = Vec::new();
for offsets in [false, true] {
if offsets && !with_offsets {
continue;
}
let offs = if offsets {
&node_offsets
} else {
&zero_offsets
};
let mut dc_tokens = dc_nodes.clone();
if offsets {
crate::dc_tree::apply_leaf_offsets(&mut dc_tokens, offs);
}
let grafted = crate::dc_tree::graft_ma_dc_tree(
num_dc_groups,
&trees.dc,
offs,
meta_tokens,
meta_props,
);
arms.push(MaDcArm {
dc: map_ctx(&dc_tokens, &grafted.leaf_ctx),
meta: static_meta(&grafted.meta_context),
tree: grafted.tokens,
num_contexts: grafted.num_contexts,
dc_leaf_ctx: grafted.leaf_ctx,
offsets: offs.clone(),
meta_learned: false,
});
if let (Some(meta_tree), Some(meta_nodes)) = (&trees.meta, &meta_nodes) {
let joint =
crate::dc_tree::graft_ma_dc_meta_tree(num_dc_groups, &trees.dc, offs, meta_tree);
arms.push(MaDcArm {
dc: map_ctx(&dc_tokens, &joint.dc_leaf_ctx),
meta: map_ctx(meta_nodes, &joint.meta_leaf_ctx),
tree: joint.tokens,
num_contexts: joint.num_contexts,
dc_leaf_ctx: joint.dc_leaf_ctx,
offsets: offs.clone(),
meta_learned: true,
});
}
}
arms
}
fn repick_leaf_predictors(
dc_datas: &[DcGroupData],
trees: &MaDcTrees,
arm_leaf_ctx: &[u32],
arm_offsets: &[i32],
code: &OwnedEntropyCode,
wp_params: WpParams,
) -> Option<MaDcTrees> {
use crate::ma_tree::{MaNode, NUM_MA_PREDS};
if code.use_prefix_code {
return None;
}
let cost_tables: Vec<Vec<f32>> = code
.ans_histograms
.iter()
.map(|h| {
h.freqs
.iter()
.map(|&f| {
if f == 0 {
crate::entropy::ANS_LOG_TAB_SIZE as f32
} else {
(f64::from(crate::entropy::ANS_LOG_TAB_SIZE) - f_log2(f64::from(f))) as f32
}
})
.collect()
})
.collect();
let nodes = trees.dc.nodes.len();
let mut cost = vec![0f32; nodes * NUM_MA_PREDS];
for g in dc_planes(dc_datas) {
crate::lossless::walk_dc_planes_predictors(&g, &trees.dc, wp_params, |node, residuals| {
let ctx = arm_leaf_ctx[node as usize] as usize;
let cl = code.context_map[ctx] as usize;
let config = code.hybrid_uint_configs[cl];
let table = &cost_tables[cl];
let row = &mut cost[node as usize * NUM_MA_PREDS..(node as usize + 1) * NUM_MA_PREDS];
for (c, &r) in row.iter_mut().zip(residuals) {
let (sym, nbits, _) = crate::entropy::uint_encode_with_config(
crate::entropy::pack_signed((r - i64::from(arm_offsets[node as usize])) as i32),
config,
);
*c += table[(sym as usize).min(table.len() - 1)] + nbits as f32;
}
});
}
let mut changed = false;
let mut dc = trees.dc.clone();
for (node, n) in dc.nodes.iter_mut().enumerate() {
if let MaNode::Leaf { pred, .. } = n {
let row = &cost[node * NUM_MA_PREDS..(node + 1) * NUM_MA_PREDS];
let (best, _) = row.iter().enumerate().fold(
(*pred as usize, row[*pred as usize]),
|acc, (p, &c)| {
if c < acc.1 { (p, c) } else { acc }
},
);
if best != *pred as usize {
*pred = best as u32;
changed = true;
}
}
}
changed.then(|| MaDcTrees {
dc,
meta: trees.meta.clone(),
})
}
pub(crate) fn ma_dc_budget(effort: &crate::effort::Effort) -> Option<MaDcBudget> {
if effort.ma_dc_tree {
Some(MaDcBudget::FULL)
} else if effort.ma_dc_tree_deep {
Some(MaDcBudget::DEEP_LITE)
} else if effort.ma_dc_tree_lite {
Some(MaDcBudget::LITE)
} else if effort.ma_dc_tree_xlite {
Some(MaDcBudget::XLITE)
} else {
None
}
}