use super::GroupLayout;
use super::context::PROP_WP;
use super::ma_sampling::{MaRefPlane, ma_channel_sample_count, sample_channel_ma};
use super::ma_source::{
CoarseLearn, LearnedCandidate, MA_COARSE_MAX_LEAVES, MA_COARSE_TARGET_SAMPLES,
MA_DEEPEN_MIN_SAVINGS, MA_FINAL_SPLIT_COST_BITS, MA_LITE_CANDIDATES, MA_LITE_MAX_LEAVES,
MA_MIN_NODE_SAMPLES, MA_PRUNE_LEAF_BITS, MA_PRUNE_MIN_NODE_SAMPLES, MA_PRUNE_SPLIT_COST_BITS,
MA_SIDE_PREDS, MA_SPLIT_COST_BITS, MA_WIDE_SIDE_PREDS, MaSource, MaTransform, ac_stream_id,
with_ma_pixels,
};
use super::tree::emit_learned_tree;
use crate::coder_scratch::CoderScratch;
use crate::ma_tree::{
LearnedTree, MaLearnParams, MaNode, MaSamples, NUM_MA_PREDS, NUM_MA_PROPS, deepen_ma_tree,
learn_ma_tree, learn_ma_tree_indexed,
};
use crate::thread_pool::ThreadPool;
use crate::weighted_predictor::WpParams;
const MA_LEAF_OFFSET_LIMIT: i32 = 8;
const MA_LEAF_EXACT_SYMBOLS: u32 = 16;
const MA_LEAF_OFFSET_MIN_SAMPLES: u32 = 16;
const MA_LEAF_OFFSET_MAX_ZERO_FRACTION: f64 = 0.9;
fn unpack_signed(token: u32) -> i32 {
if token & 1 == 1 {
-(((token + 1) >> 1) as i32)
} else {
(token >> 1) as i32
}
}
pub(super) fn leaf_offsets<'a, T: crate::ma_tree::MaProperty + 'a>(
tree: &LearnedTree,
leaf_ctx: &[u32],
num_ctx: u32,
samples: impl Iterator<Item = (&'a [T; NUM_MA_PROPS], &'a [u8; NUM_MA_PREDS])>,
) -> Vec<i32> {
const BINS: usize = 2 * MA_LEAF_OFFSET_LIMIT as usize + 1;
let mut hist = vec![[0u32; BINS]; num_ctx as usize];
let mut routed = 0u64;
for (props, tok) in samples {
let (node, pred) = tree.lookup(props);
routed += 1;
let symbol = tok[pred as usize] as u32;
if symbol < MA_LEAF_EXACT_SYMBOLS {
let r = unpack_signed(symbol);
hist[leaf_ctx[node as usize] as usize][(r + MA_LEAF_OFFSET_LIMIT) as usize] += 1;
}
}
let zeros: u64 = hist
.iter()
.map(|h| h[MA_LEAF_OFFSET_LIMIT as usize] as u64)
.sum();
if zeros as f64 > MA_LEAF_OFFSET_MAX_ZERO_FRACTION * routed as f64 {
return vec![0; num_ctx as usize];
}
hist.iter()
.map(|h| {
let total: u32 = h.iter().sum();
if total < MA_LEAF_OFFSET_MIN_SAMPLES {
return 0;
}
let half = total.div_ceil(2);
let mut acc = 0u32;
for (bin, &c) in h.iter().enumerate() {
acc += c;
if acc >= half {
return bin as i32 - MA_LEAF_OFFSET_LIMIT;
}
}
0
})
.collect()
}
fn ma_sample_stride(total_px: usize, target_samples: usize, full_sample_limit: usize) -> usize {
let mut stride = total_px.div_ceil(target_samples).max(1);
if stride == 1 && total_px > full_sample_limit {
stride = 3;
}
if stride > 1 && stride.is_multiple_of(2) {
stride += 1;
}
stride
}
pub(super) fn gate_ma_tree(
tree: LearnedTree,
sample_scale: f64,
samples: Option<&MaSamples>,
leaf_price: Option<f64>,
) -> Option<LearnedCandidate> {
let mut cand = finish_ma_candidate(tree, sample_scale, leaf_price);
if cand.est_real.partial_cmp(&cand.flat_real) != Some(std::cmp::Ordering::Less) {
return None;
}
if let Some(samples) = samples {
cand.set_leaf_offsets(samples, 4);
}
Some(cand)
}
pub(super) fn finish_ma_candidate(
tree: LearnedTree,
sample_scale: f64,
leaf_price: Option<f64>,
) -> LearnedCandidate {
let (tree_tokens, leaf_ctx, num_ctx) = emit_learned_tree(&tree);
let clusters_bits = (num_ctx.min(128) as f64) * 200.0;
let overhead_bits = match leaf_price {
Some(price) => num_ctx as f64 * price + clusters_bits,
None => tree_tokens.len() as f64 * 10.0 + clusters_bits + num_ctx as f64 * 8.0,
};
let est_real = tree.est_bits * sample_scale + overhead_bits;
let flat_real = tree.flat_bits * sample_scale;
let mut leaf_offset = vec![0; num_ctx as usize];
for (node, &ctx) in tree.nodes.iter().zip(&leaf_ctx) {
if let MaNode::Leaf { offset, .. } = *node
&& ctx != u32::MAX
{
leaf_offset[ctx as usize] = offset;
}
}
let estimated_savings = 1.0 - tree.est_bits / tree.flat_bits.max(f64::MIN_POSITIVE);
LearnedCandidate {
tree,
tree_tokens,
leaf_ctx,
leaf_offset,
num_ctx,
est_real,
flat_real,
estimated_savings,
constant_ctx: None,
}
}
fn ma_learn_params_final(
min_symbol: u32,
max_leaves: usize,
max_candidates: usize,
split_scale: f64,
use_wp: bool,
modal_offsets: bool,
) -> MaLearnParams {
let mut params = ma_learn_params(
min_symbol,
max_leaves,
max_candidates,
split_scale,
use_wp,
modal_offsets,
);
params.split_cost_bits = MA_FINAL_SPLIT_COST_BITS / split_scale as f32;
params
}
pub(super) fn ma_learn_params(
min_symbol: u32,
max_leaves: usize,
max_candidates: usize,
split_scale: f64,
use_wp: bool,
modal_offsets: bool,
) -> MaLearnParams {
MaLearnParams {
alphabet: min_symbol as usize,
max_leaves,
split_cost_bits: MA_SPLIT_COST_BITS / split_scale as f32,
min_node: MA_MIN_NODE_SAMPLES,
allow_wp: use_wp,
allowed_preds: u16::MAX,
side_preds: MA_SIDE_PREDS,
max_candidates,
modal_offsets,
prune_leaf_bits: 0.0,
}
}
pub(super) fn with_ma_prune(mut params: MaLearnParams, split_scale: f64) -> MaLearnParams {
if params.modal_offsets {
params.split_cost_bits = MA_PRUNE_SPLIT_COST_BITS / split_scale as f32;
params.min_node = MA_PRUNE_MIN_NODE_SAMPLES;
params.prune_leaf_bits = MA_PRUNE_LEAF_BITS / split_scale as f32;
}
params
}
pub(super) fn ma_leaf_price(params: &MaLearnParams, split_scale: f64) -> Option<f64> {
(params.prune_leaf_bits > 0.0).then_some(params.prune_leaf_bits as f64 * split_scale)
}
fn learn_ma_coarse(
samples: MaSamples,
stride: usize,
min_symbol: u32,
use_wp: bool,
max_leaves: usize,
max_candidates: usize,
leaf_offsets: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<CoarseLearn> {
if samples.len() < 4 * MA_MIN_NODE_SAMPLES {
return None;
}
if samples.len() <= MA_COARSE_TARGET_SAMPLES {
let best_first = || {
ma_learn_params(
min_symbol,
max_leaves,
max_candidates,
stride as f64,
use_wp,
!leaf_offsets,
)
};
let params = with_ma_prune(best_first(), stride as f64);
let pruned = params.prune_leaf_bits > 0.0;
let leaf_price = ma_leaf_price(¶ms, stride as f64);
let tree = learn_ma_tree(&samples, params, pool, scratch);
let candidate = match gate_ma_tree(
tree,
stride as f64,
leaf_offsets.then_some(&samples),
leaf_price,
) {
Some(candidate) => candidate,
None if pruned => gate_ma_tree(
learn_ma_tree(&samples, best_first(), pool, scratch),
stride as f64,
leaf_offsets.then_some(&samples),
None,
)?,
None => return None,
};
return Some(CoarseLearn {
samples,
stride,
max_candidates,
leaf_offsets,
candidate,
deepen: false,
});
}
let coarse_indices = samples.evenly_sampled_indices(MA_COARSE_TARGET_SAMPLES);
let coarse_scale = stride as f64 * samples.len() as f64 / coarse_indices.len() as f64;
let coarse_tree = learn_ma_tree_indexed(
&samples,
coarse_indices,
ma_learn_params(
min_symbol,
MA_COARSE_MAX_LEAVES,
max_candidates,
coarse_scale,
use_wp,
!leaf_offsets,
),
pool,
scratch,
);
let candidate = gate_ma_tree(coarse_tree, coarse_scale, None, None)?;
let coarse_leaves = candidate.tree.nodes.len().div_ceil(2);
let coarse_savings = 1.0 - candidate.est_real / candidate.flat_real;
let deepen = coarse_leaves == MA_COARSE_MAX_LEAVES && coarse_savings >= MA_DEEPEN_MIN_SAVINGS;
Some(CoarseLearn {
samples,
stride,
max_candidates,
leaf_offsets,
candidate,
deepen,
})
}
pub(super) fn finish_ma_learn(
speed: crate::Speed,
coarse: CoarseLearn,
min_symbol: u32,
use_wp: bool,
max_leaves: usize,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> LearnedCandidate {
if !coarse.deepen {
return coarse.candidate;
}
let mut params = with_ma_prune(
ma_learn_params_final(
min_symbol,
max_leaves,
coarse.max_candidates,
coarse.stride as f64,
use_wp,
!coarse.leaf_offsets,
),
coarse.stride as f64,
);
if !speed.effort().tree_deep_final && coarse.stride > 1 {
params.max_leaves = params.max_leaves.min(MA_LITE_MAX_LEAVES);
params.max_candidates = params.max_candidates.min(MA_LITE_CANDIDATES);
}
if coarse.leaf_offsets && speed.effort().tree_wide_side_preds() {
params.side_preds = MA_WIDE_SIDE_PREDS;
}
let leaf_price = ma_leaf_price(¶ms, coarse.stride as f64);
let (deep_tree, samples) = deepen_ma_tree(
coarse.samples,
params,
coarse.candidate.tree.clone(),
pool,
scratch,
);
gate_ma_tree(
deep_tree,
coarse.stride as f64,
coarse.leaf_offsets.then_some(&samples),
leaf_price,
)
.unwrap_or(coarse.candidate)
}
const WP_RANK_MIN_ROW_SHARE: f64 = 0.02;
const WP_RANK_MIN_SPLIT_SHARE: f64 = 0.15;
fn wp_matters(stage: &CoarseLearn) -> bool {
let tree = &stage.candidate.tree;
let (mut splits, mut wp_splits) = (0usize, 0usize);
for node in &tree.nodes {
if let crate::ma_tree::MaNode::Split { prop, .. } = node {
splits += 1;
wp_splits += usize::from(*prop as usize == PROP_WP as usize);
}
}
if wp_splits as f64 >= WP_RANK_MIN_SPLIT_SHARE * splits as f64 && wp_splits > 0 {
return true;
}
let mut rows = 0usize;
let mut wp_rows = 0usize;
for props in stage.samples.props.iter().step_by(16) {
rows += 1;
if tree.lookup(&props).1 as usize == crate::ma_tree::PRED_WEIGHTED {
wp_rows += 1;
}
}
wp_rows as f64 >= WP_RANK_MIN_ROW_SHARE * rows as f64
}
#[allow(clippy::too_many_arguments)]
pub(super) fn rank_presets(
source: &MaSource<'_>,
xsize: usize,
ysize: usize,
min_symbol: u32,
use_wp: bool,
first: Option<CoarseLearn>,
first_params: WpParams,
header_bits: &dyn Fn(WpParams) -> f64,
all_presets: bool,
layout: GroupLayout,
sampling: (usize, usize),
keep_stage: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> (f64, f64, WpParams, Option<CoarseLearn>) {
let mut best_stage = None;
let mut best_bits = f64::INFINITY;
let mut best_coarse = f64::INFINITY;
let mut best_params = first_params;
let mut order: Vec<WpParams> = vec![first_params];
if use_wp && all_presets && first.as_ref().is_none_or(wp_matters) {
for &preset in [1usize, 2, 3, 0].iter().map(|&i| &WpParams::PRESETS[i]) {
if preset != first_params {
order.push(preset);
}
}
}
let mut first = first;
for preset in order {
let stage = match first.take() {
Some(stage) => Some(stage),
None => rank_coarse(
source, xsize, ysize, min_symbol, preset, use_wp, layout, sampling, pool, scratch,
),
};
let Some(stage) = stage else {
continue;
};
let coarse = stage.candidate.est_real + header_bits(preset);
if coarse > best_coarse * RANK_COARSE_PRUNE {
continue;
}
best_coarse = best_coarse.min(coarse);
let bits = rank_bits(&stage) + header_bits(preset);
if bits < best_bits {
best_bits = bits;
best_params = preset;
best_stage = keep_stage.then_some(stage);
}
}
(best_bits, best_coarse, best_params, best_stage)
}
#[allow(clippy::too_many_arguments)]
pub(super) fn learn_ma_candidate(
source: &MaSource<'_>,
xsize: usize,
ysize: usize,
layout: GroupLayout,
min_symbol: u32,
wp_params: WpParams,
use_wp: bool,
max_leaves: usize,
(target_samples, full_sample_limit): (usize, usize),
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<CoarseLearn> {
let gdim = layout.dim();
let xsize_groups = xsize.div_ceil(gdim);
let num_groups = xsize_groups * ysize.div_ceil(gdim);
let placement = source.placement(layout, num_groups == 1);
let max_candidates = source.max_candidates();
let stride = ma_sample_stride(source.total_values(), target_samples, full_sample_limit);
struct Job<'a> {
channel: usize,
chan_id: u32,
stream: i32,
refs: Vec<MaRefPlane<'a>>,
group_override: Option<usize>,
x0: usize,
y0: usize,
w: usize,
h: usize,
}
let num_dc_groups = xsize.div_ceil(layout.lf_dim()) * ysize.div_ceil(layout.lf_dim());
let mut jobs: Vec<Job> = Vec::new();
for p in placement.iter().filter(|p| p.global) {
let ch = &source.channels[p.channel];
if ch.constant.is_some() {
continue;
}
jobs.push(Job {
channel: p.channel,
chan_id: p.chan_id,
stream: 0,
refs: source.ref_planes(&placement, p, 0, 0),
group_override: None,
x0: 0,
y0: 0,
w: ch.w,
h: ch.h,
});
}
if num_groups > 1 {
for group_index in 0..num_groups {
let x0 = (group_index % xsize_groups) * gdim;
let y0 = (group_index / xsize_groups) * gdim;
if let Some(over) = source.group_override(group_index) {
for (channel, ch) in over.channels.iter().enumerate() {
jobs.push(Job {
channel,
chan_id: channel as u32,
stream: ac_stream_id(num_dc_groups, group_index),
refs: Vec::new(),
group_override: Some(group_index),
x0: 0,
y0: 0,
w: ch.w,
h: ch.h,
});
}
continue;
}
for p in placement.iter().filter(|p| !p.global) {
let ch = &source.channels[p.channel];
if ch.constant.is_some() {
continue;
}
jobs.push(Job {
channel: p.channel,
chan_id: p.chan_id,
stream: ac_stream_id(num_dc_groups, group_index),
refs: source.ref_planes(&placement, p, x0, y0),
group_override: None,
x0,
y0,
w: gdim.min(ch.w - x0),
h: gdim.min(ch.h - y0),
});
}
}
}
let counts: Vec<usize> = jobs
.iter()
.map(|job| ma_channel_sample_count(job.w, job.h, stride))
.collect();
let total_samples = counts.iter().sum();
let mut samples = MaSamples {
props: crate::ma_tree::MaProperties::zeroed(total_samples),
tok: vec![[0; NUM_MA_PREDS]; total_samples],
val: vec![0; total_samples],
};
loop {
let overflow = crate::ma_tree::with_ma_properties!(&mut samples.props, |props| {
let mut props = props.as_mut_slice();
let mut tok = samples.tok.as_mut_slice();
let mut val = samples.val.as_mut_slice();
let mut ranges = Vec::with_capacity(jobs.len());
for &count in &counts {
let (p, rest_p) = props.split_at_mut(count);
let (t, rest_t) = tok.split_at_mut(count);
let (v, rest_v) = val.split_at_mut(count);
ranges.push((p, t, v, false));
(props, tok, val) = (rest_p, rest_t, rest_v);
}
pool.steal_for_each_mut(scratch, &mut ranges, |i, range, _scratch| {
let job = &jobs[i];
let ch = source.channel_at(job.group_override, job.channel);
let mut rows = range
.0
.iter_mut()
.zip(range.1.iter_mut())
.zip(range.2.iter_mut());
with_ma_pixels!(ch, |pixels| sample_channel_ma(
|y| &pixels[(job.y0 + y) * ch.w + job.x0..][..job.w],
job.w,
job.h,
job.chan_id,
job.stream,
&job.refs,
wp_params,
use_wp,
stride,
|p, t, v| {
let ((props, tok), val) = rows.next().expect("sample count");
range.3 |= !crate::ma_tree::write_property_row(props, p);
*tok = t;
*val = v;
},
));
debug_assert!(rows.next().is_none());
});
ranges.iter().any(|range| range.3)
});
if !overflow {
break;
}
samples.props = crate::ma_tree::MaProperties::Wide(Vec::new());
samples.props = crate::ma_tree::MaProperties::Wide(vec![[0; NUM_MA_PROPS]; total_samples]);
}
learn_ma_coarse(
samples,
stride,
min_symbol,
use_wp,
max_leaves,
max_candidates,
matches!(source.transform, MaTransform::Rct(_)),
pool,
scratch,
)
}
const MA_RANK_LEAVES: usize = MA_COARSE_MAX_LEAVES;
pub(super) const RCT_RANK_MARGIN: f32 = 1.02;
pub(super) const RANK_COARSE_PRUNE: f64 = 1.005;
#[allow(clippy::too_many_arguments)]
pub(super) fn rank_coarse(
source: &MaSource<'_>,
xsize: usize,
ysize: usize,
min_symbol: u32,
wp_params: WpParams,
use_wp: bool,
layout: GroupLayout,
sampling: (usize, usize),
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<CoarseLearn> {
learn_ma_candidate(
source,
xsize,
ysize,
layout,
min_symbol,
wp_params,
use_wp,
MA_RANK_LEAVES,
sampling,
pool,
scratch,
)
}
pub(super) fn rank_bits(stage: &CoarseLearn) -> f64 {
stage.candidate.est_real.min(stage.candidate.flat_real)
}
#[allow(clippy::too_many_arguments)]
pub(super) fn learn_best_layout(
speed: crate::Speed,
source: &MaSource<'_>,
xsize: usize,
ysize: usize,
layouts: &[GroupLayout],
min_symbol: u32,
wp_params: WpParams,
use_wp: bool,
coarse_limit: f64,
final_limit: f64,
deepen_all: bool,
sampling: (usize, usize),
mut first_stage: Option<CoarseLearn>,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<(GroupLayout, LearnedCandidate, f64)> {
let mut best_coarse_est = f64::INFINITY;
let mut learned: Option<(GroupLayout, LearnedCandidate)> = None;
for (index, &layout) in layouts.iter().enumerate() {
if index > 0
&& let Some((_, best)) = &learned
&& best.est_real > final_limit
{
break;
}
let stage = first_stage.take().or_else(|| {
learn_ma_candidate(
source,
xsize,
ysize,
layout,
min_symbol,
wp_params,
use_wp,
source.max_leaves(),
sampling,
pool,
scratch,
)
});
let Some(stage) = stage else {
continue;
};
let coarse_est = stage.candidate.est_real;
let layout_pruned = index > 0 && !deepen_all && coarse_est > best_coarse_est;
if coarse_est > coarse_limit || layout_pruned {
best_coarse_est = best_coarse_est.min(coarse_est);
continue;
}
best_coarse_est = best_coarse_est.min(coarse_est);
let cand = finish_ma_learn(
speed,
stage,
min_symbol,
use_wp,
source.max_leaves(),
pool,
scratch,
);
if learned
.as_ref()
.is_none_or(|(_, best)| cand.est_real < best.est_real)
{
learned = Some((layout, cand));
}
}
learned.map(|(layout, cand)| (layout, cand, best_coarse_est))
}