use super::{ColorTransform, CoreFrame, SmallestFrame, TreeSearch, learned_tree_is_decisive};
use crate::bit_writer::BitWriter;
use crate::coder_scratch::CoderScratch;
use crate::lossless::GroupLayout;
use crate::lossless::ma_encoding::write_learned_tree_frame;
use crate::lossless::ma_learning::{
RANK_COARSE_PRUNE, RCT_RANK_MARGIN, finish_ma_learn, learn_best_layout, learn_ma_candidate,
rank_bits, rank_coarse, rank_presets,
};
use crate::lossless::ma_source::{
CoarseLearn, DENSE_FINAL_MIN_BITS_PER_VALUE, LearnedCandidate, MA_COARSE_TARGET_SAMPLES,
MA_DENSE_SAMPLING, MA_FULL_SAMPLING, MA_LITE_SAMPLING, MaSource, PALETTE_LAYOUT_MARGIN,
PER_GROUP_MARGIN, RANK_MIN_VALUES, RGB_SINGLE_LAYOUT_MIN_VALUES, mixed_ma_source,
rgb_ma_source, source_values_of,
};
use crate::lossless::palette::{
self, GlobalPalette, OrderRace, PALETTE_COARSE_MARGIN, PALETTE_FINAL_MARGIN,
build_global_palettes,
};
use crate::lossless::rct::rct_planes;
use crate::patches::ModularFrameKind;
use crate::thread_pool::ThreadPool;
use crate::weighted_predictor::WpParams;
const MA_ALTERNATIVES_MIN_SAVINGS: f64 = 0.05;
const VECTOR_PALETTE_MAX_SHARE: f64 = 0.75;
pub(super) struct TreeOutcome {
pub(super) layout: GroupLayout,
pub(super) wp_params: WpParams,
pub(super) decisive: bool,
pub(super) skip_alternatives: bool,
}
pub(super) fn learn_tree_candidates(
frame: &CoreFrame<'_>,
color: &mut ColorTransform<'_>,
wp_params: WpParams,
best: &mut SmallestFrame,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> TreeOutcome {
let layouts = LayoutPlan::new(frame);
if !frame.compare_tree_candidates {
return TreeOutcome {
layout: layouts.all[0],
wp_params,
decisive: false,
skip_alternatives: false,
};
}
let effort = frame.effort;
let palettes = if effort.tree_global_palette {
build_global_palettes(
frame.ycocg,
frame.alpha,
frame.num_color,
frame.xsize,
frame.ysize,
(effort.palette_order_race || matches!(frame.tree_search, TreeSearch::Vector))
.then_some(OrderRace {
min_symbol: frame.min_symbol,
use_wp: frame.use_wp,
}),
pool,
scratch,
)
} else {
None
};
let (palette, raced_palette) = match palettes {
Some((palette, raced)) => (Some(palette), raced),
None => (None, None),
};
let mut sources = SourcePlan::new(frame, wp_params, palette.is_some());
if effort.tree_rank && matches!(frame.settings.decoding_speed, crate::DecodingSpeed::Slow) {
sources.rank(frame, color, palette.as_ref(), &layouts, pool, scratch);
} else if matches!(frame.tree_search, TreeSearch::Vector)
&& let Some(palette) = &palette
{
sources.rank_vector(frame, color, palette, layouts.rank_layout(), pool, scratch);
}
sources.keep_reusable_stages(&layouts);
let mut tournament = Tournament::new(layouts.all[0]);
if sources.rgb {
tournament.learn_rgb(frame, color, &mut sources, &layouts, best, pool, scratch);
}
if tournament.decisive {
color.release_planes();
}
let bits_before_palette = best.bits();
if sources.palette
&& let Some(palette) = &palette
{
tournament.learn_global_palette(
frame,
color,
&mut sources,
palette,
raced_palette.as_ref(),
&layouts,
best,
pool,
scratch,
);
}
let global_palette_won = best.bits() != bits_before_palette;
if effort.tree_group_palette && frame.num_color == 3 && !global_palette_won {
tournament.learn_group_palettes(frame, color, &sources, best, pool, scratch);
}
TreeOutcome {
layout: tournament.layout,
wp_params: sources.wp_params,
decisive: tournament.decisive,
skip_alternatives: tournament.skip_alternatives,
}
}
const ORDER_RACE_MARGIN: f64 = 1.02;
const ORDER_RACE_BOTH_MAX_BITS: f64 = 65536.0;
const ORDERED_GROUP_PALETTE_MARGIN: f64 = 0.97;
const PARALLEL_MIN_GROUPS: usize = 6;
struct LayoutPlan {
all: Vec<GroupLayout>,
rgb_count: usize,
}
impl LayoutPlan {
fn new(frame: &CoreFrame<'_>) -> Self {
let dual = frame.compare_tree_candidates
&& frame.effort.tree_dual_layout
&& matches!(frame.settings.decoding_speed, crate::DecodingSpeed::Slow)
&& (frame.xsize > GroupLayout::DEFAULT.dim() || frame.ysize > GroupLayout::DEFAULT.dim());
let large = (GroupLayout::DEFAULT.shift..=GroupLayout::LARGE.shift)
.rev()
.map(|shift| GroupLayout {
shift,
..GroupLayout::DEFAULT
})
.find(|layout| {
frame.xsize.div_ceil(layout.dim()) * frame.ysize.div_ceil(layout.dim())
>= PARALLEL_MIN_GROUPS
})
.unwrap_or(GroupLayout::LARGE);
let all: Vec<GroupLayout> = if dual && large != GroupLayout::DEFAULT {
vec![large, GroupLayout::DEFAULT]
} else {
vec![GroupLayout::DEFAULT]
}
.into_iter()
.map(|layout| layout.with_upsampling(frame.settings.upsampling))
.collect();
let rgb_count = if dual
&& source_values_of(frame.xsize, frame.ysize, frame.coded_chans)
> RGB_SINGLE_LAYOUT_MIN_VALUES
{
1
} else {
all.len()
};
Self { all, rgb_count }
}
fn rank_layout(&self) -> GroupLayout {
self.all[0]
}
fn rgb(&self) -> &[GroupLayout] {
&self.all[..self.rgb_count]
}
}
struct SourcePlan {
rgb: bool,
palette: bool,
wp_params: WpParams,
palette_wp: WpParams,
rank_sampling: (usize, usize),
final_sampling: (usize, usize),
rgb_stage: Option<CoarseLearn>,
palette_stage: Option<CoarseLearn>,
}
impl SourcePlan {
fn new(frame: &CoreFrame<'_>, wp_params: WpParams, has_palette: bool) -> Self {
let sampling = if frame.effort.tree_full_sampling {
MA_FULL_SAMPLING
} else {
MA_LITE_SAMPLING
};
Self {
rgb: true,
palette: has_palette,
wp_params,
palette_wp: wp_params,
rank_sampling: sampling,
final_sampling: sampling,
rgb_stage: None,
palette_stage: None,
}
}
fn rank_vector(
&mut self,
frame: &CoreFrame<'_>,
color: &mut ColorTransform<'_>,
palette: &GlobalPalette,
layout: GroupLayout,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) {
let sample = |source: &MaSource<'_>, scratch: &mut CoderScratch| {
rank_coarse(
source,
frame.xsize,
frame.ysize,
frame.min_symbol,
self.wp_params,
frame.use_wp,
layout,
self.rank_sampling,
pool,
scratch,
)
};
let palette = palette.source(frame.xsize, frame.ysize);
if palette.total_values() <= MA_COARSE_TARGET_SAMPLES {
return;
}
let Some(palette_stage) = sample(&palette, scratch)
.filter(|stage| stage.samples.len() > MA_COARSE_TARGET_SAMPLES)
else {
return;
};
let rct_type = color.rct_type;
let planes = color.planes(pool, scratch);
let rgb = rgb_ma_source(
planes,
frame.alpha,
frame.xsize,
rct_type,
frame.alpha_constant,
frame.num_color,
);
if let Some(rgb_stage) = sample(&rgb, scratch) {
if palette_stage.candidate.est_real
<= VECTOR_PALETTE_MAX_SHARE * rgb_stage.candidate.est_real
{
self.rgb = false;
} else if rgb_stage.samples.len() > MA_COARSE_TARGET_SAMPLES {
self.rgb_stage = Some(rgb_stage);
}
}
self.palette_stage = Some(palette_stage);
}
fn rank(
&mut self,
frame: &CoreFrame<'_>,
color: &mut ColorTransform<'_>,
palette: Option<&GlobalPalette>,
layouts: &LayoutPlan,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) {
let (xsize, ysize) = (frame.xsize, frame.ysize);
let effort = frame.effort;
let rank_layout = layouts.rank_layout();
let header_bits = |params: WpParams| frame.wp_header_bits(params);
let keep_stages = !effort.tree_fresh_final_samples;
let rank_presets_deep = effort.tree_rank_deep();
let palette_only =
matches!(frame.kind, ModularFrameKind::XybBlend { .. }) && palette.is_some();
let rank_sampling = self.rank_sampling;
let coarse = |source: &MaSource<'_>, wp_params: WpParams, scratch: &mut CoderScratch| {
let mut stage = rank_coarse(
source,
xsize,
ysize,
frame.min_symbol,
wp_params,
frame.use_wp,
rank_layout,
rank_sampling,
pool,
scratch,
)?;
if !keep_stages && !rank_presets_deep {
stage.samples = crate::ma_tree::MaSamples::with_capacity(0);
}
Some(stage)
};
let wp_params = self.wp_params;
let mut rgb_stage = if palette_only {
None
} else {
let rct_type = color.rct_type;
let planes = color.planes(pool, scratch);
let source = rgb_ma_source(
planes,
frame.alpha,
xsize,
rct_type,
frame.alpha_constant,
frame.num_color,
);
coarse(&source, wp_params, scratch)
};
let mut palette_stage =
palette.and_then(|p| coarse(&p.source(xsize, ysize), wp_params, scratch));
let coarse_of = |stage: &Option<CoarseLearn>| {
stage.as_ref().map_or(f64::INFINITY, |s| {
s.candidate.est_real + header_bits(wp_params)
})
};
let (rgb_coarse, palette_coarse) = (coarse_of(&rgb_stage), coarse_of(&palette_stage));
if effort.tree_dense_sampling
&& rgb_stage.as_ref().is_some_and(|stage| {
stage.candidate.est_real
>= DENSE_FINAL_MIN_BITS_PER_VALUE
* source_values_of(xsize, ysize, frame.coded_chans) as f64
})
{
self.final_sampling = MA_DENSE_SAMPLING;
}
self.rgb = rgb_coarse <= palette_coarse * PALETTE_COARSE_MARGIN;
self.palette =
palette_stage.is_some() && palette_coarse <= rgb_coarse * PALETTE_COARSE_MARGIN;
let rank_more = source_values_of(xsize, ysize, frame.coded_chans) >= RANK_MIN_VALUES;
if self.rgb && rank_more {
let (best_bits, best_coarse, params, stage) = {
let rct_type = color.rct_type;
let planes = color.planes(pool, scratch);
let source = rgb_ma_source(
planes,
frame.alpha,
xsize,
rct_type,
frame.alpha_constant,
frame.num_color,
);
rank_presets(
&source,
xsize,
ysize,
frame.min_symbol,
frame.use_wp,
if palette_only {
coarse(&source, self.wp_params, scratch)
} else {
rgb_stage.take()
},
self.wp_params,
&header_bits,
rank_presets_deep,
rank_layout,
self.rank_sampling,
keep_stages,
pool,
scratch,
)
};
self.wp_params = params;
rgb_stage = stage;
if let Some((runner_up, cost)) = color.runner_up()
&& cost <= color.ranked[0].1 * RCT_RANK_MARGIN
{
rgb_stage = rgb_stage.filter(|stage| {
let rows = stage.samples.len();
self.final_sampling == self.rank_sampling
&& rows > MA_COARSE_TARGET_SAMPLES
&& rows <= self.rank_sampling.0 / 2
});
let planes = (runner_up != 6)
.then(|| rct_planes(color.ycocg, xsize, ysize, runner_up, pool, scratch));
let source = rgb_ma_source(
planes.as_ref().unwrap_or(color.ycocg),
frame.alpha,
xsize,
runner_up,
frame.alpha_constant,
frame.num_color,
);
if let Some(stage) = coarse(&source, self.wp_params, scratch)
&& stage.candidate.est_real + header_bits(self.wp_params)
<= best_coarse * RANK_COARSE_PRUNE
&& rank_bits(&stage) + header_bits(self.wp_params) < best_bits
{
color.adopt(runner_up, planes);
rgb_stage = keep_stages.then_some(stage);
}
}
}
if self.palette
&& rank_more
&& rank_presets_deep
&& let Some(p) = palette
{
let (_, _, params, stage) = rank_presets(
&p.source(xsize, ysize),
xsize,
ysize,
frame.min_symbol,
frame.use_wp,
palette_stage.take(),
self.wp_params,
&header_bits,
true,
rank_layout,
self.rank_sampling,
keep_stages,
pool,
scratch,
);
self.palette_wp = params;
palette_stage = stage;
}
if keep_stages {
(self.rgb_stage, self.palette_stage) = (rgb_stage, palette_stage);
}
}
fn keep_reusable_stages(&mut self, layouts: &LayoutPlan) {
let same_budget = self.final_sampling == self.rank_sampling;
let reusable = |stage: Option<CoarseLearn>, final_layout: GroupLayout| {
stage.filter(|stage| {
final_layout == layouts.rank_layout()
&& same_budget
&& stage.samples.len() > MA_COARSE_TARGET_SAMPLES
})
};
self.rgb_stage = reusable(self.rgb_stage.take(), layouts.rgb()[0]);
self.palette_stage = reusable(self.palette_stage.take(), layouts.all[0]);
}
}
struct Tournament {
layout: GroupLayout,
decisive: bool,
skip_alternatives: bool,
rgb_coarse: f64,
rgb_final: f64,
best_source_coarse: f64,
}
impl Tournament {
fn new(layout: GroupLayout) -> Self {
Self {
layout,
decisive: false,
skip_alternatives: false,
rgb_coarse: f64::INFINITY,
rgb_final: f64::INFINITY,
best_source_coarse: f64::INFINITY,
}
}
#[allow(clippy::too_many_arguments)]
fn learn_rgb(
&mut self,
frame: &CoreFrame<'_>,
color: &mut ColorTransform<'_>,
sources: &mut SourcePlan,
layouts: &LayoutPlan,
best: &mut SmallestFrame,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) {
let first_stage = sources.rgb_stage.take();
let rct_type = color.rct_type;
let planes = color.planes(pool, scratch);
let source = rgb_ma_source(
planes,
frame.alpha,
frame.xsize,
rct_type,
frame.alpha_constant,
frame.num_color,
);
let Some((layout, cand, coarse)) = learn_best_layout(
frame.settings.speed,
&source,
frame.xsize,
frame.ysize,
layouts.rgb(),
frame.min_symbol,
sources.wp_params,
frame.use_wp,
f64::INFINITY,
f64::INFINITY,
false,
sources.final_sampling,
first_stage,
pool,
scratch,
) else {
return;
};
self.layout = layout;
self.rgb_coarse = coarse;
self.rgb_final = cand.est_real;
self.best_source_coarse = coarse;
let mut candidate = BitWriter::new();
let estimated_savings = write_learned_tree_frame(
frame.settings.speed,
&source,
frame.alpha.is_some(),
frame.kind,
frame.xsize,
frame.ysize,
layout,
frame.min_symbol,
pool,
scratch,
sources.wp_params,
frame.use_wp,
&cand,
frame.tree_search,
&mut candidate,
);
self.decisive = learned_tree_is_decisive(estimated_savings);
self.skip_alternatives = estimated_savings >= MA_ALTERNATIVES_MIN_SAVINGS;
best.offer(candidate);
}
#[allow(clippy::too_many_arguments)]
fn learn_global_palette(
&mut self,
frame: &CoreFrame<'_>,
color: &mut ColorTransform<'_>,
sources: &mut SourcePlan,
palette: &GlobalPalette,
raced: Option<&GlobalPalette>,
layouts: &LayoutPlan,
best: &mut SmallestFrame,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) {
let first_stage = sources.palette_stage.take();
let source = palette.source(frame.xsize, frame.ysize);
let Some(raced) = raced else {
if let Some((layout, cand, coarse)) = self.learn_palette_layouts(
frame,
sources,
&source,
&layouts.all,
first_stage,
pool,
scratch,
) {
self.write_palette(
frame, color, sources, &source, layout, &cand, best, pool, scratch,
);
self.best_source_coarse = self.best_source_coarse.min(coarse);
}
return;
};
let raced_source = raced.source(frame.xsize, frame.ysize);
let (head, tail) = layouts.all.split_at(1);
let mut learns = [(&source, first_stage), (&raced_source, None)].map(|(source, stage)| {
let learn =
self.learn_palette_layouts(frame, sources, source, head, stage, pool, scratch);
(source, learn)
});
let est_of = |learn: &Option<(GroupLayout, LearnedCandidate, f64)>| {
learn
.as_ref()
.map_or(f64::INFINITY, |(_, cand, _)| cand.est_real)
};
let lead = est_of(&learns[0].1).min(est_of(&learns[1].1));
let limit = if lead <= ORDER_RACE_BOTH_MAX_BITS {
f64::INFINITY
} else {
lead * ORDER_RACE_MARGIN
};
let final_limit = self.rgb_final * PALETTE_FINAL_MARGIN * PALETTE_LAYOUT_MARGIN;
for (source, learn) in learns.iter_mut() {
let Some((mut layout, mut cand, mut coarse)) = learn.take() else {
continue;
};
if cand.est_real > limit {
self.best_source_coarse = self.best_source_coarse.min(coarse);
continue;
}
if !tail.is_empty()
&& cand.est_real <= final_limit
&& let Some((tail_layout, tail_cand, tail_coarse)) =
self.learn_palette_layouts(frame, sources, source, tail, None, pool, scratch)
{
coarse = coarse.min(tail_coarse);
if tail_cand.est_real < cand.est_real {
(layout, cand) = (tail_layout, tail_cand);
}
}
self.write_palette(
frame, color, sources, source, layout, &cand, best, pool, scratch,
);
self.best_source_coarse = self.best_source_coarse.min(coarse);
}
}
#[allow(clippy::too_many_arguments)]
fn learn_palette_layouts(
&self,
frame: &CoreFrame<'_>,
sources: &SourcePlan,
source: &MaSource<'_>,
layouts: &[GroupLayout],
first_stage: Option<CoarseLearn>,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<(GroupLayout, LearnedCandidate, f64)> {
learn_best_layout(
frame.settings.speed,
source,
frame.xsize,
frame.ysize,
layouts,
frame.min_symbol,
sources.palette_wp,
frame.use_wp,
self.rgb_coarse * PALETTE_COARSE_MARGIN,
self.rgb_final * PALETTE_FINAL_MARGIN * PALETTE_LAYOUT_MARGIN,
true,
sources.final_sampling,
first_stage,
pool,
scratch,
)
}
#[allow(clippy::too_many_arguments)]
fn write_palette(
&mut self,
frame: &CoreFrame<'_>,
color: &mut ColorTransform<'_>,
sources: &SourcePlan,
source: &MaSource<'_>,
layout: GroupLayout,
cand: &LearnedCandidate,
best: &mut SmallestFrame,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) {
if cand.est_real > self.rgb_final * PALETTE_FINAL_MARGIN {
return;
}
let mut candidate = BitWriter::new();
let estimated_savings = write_learned_tree_frame(
frame.settings.speed,
source,
frame.alpha.is_some(),
frame.kind,
frame.xsize,
frame.ysize,
layout,
frame.min_symbol,
pool,
scratch,
sources.palette_wp,
frame.use_wp,
cand,
frame.tree_search,
&mut candidate,
);
if learned_tree_is_decisive(estimated_savings) {
self.decisive = true;
color.release_planes();
}
best.offer(candidate);
}
fn learn_group_palettes(
&mut self,
frame: &CoreFrame<'_>,
color: &mut ColorTransform<'_>,
sources: &SourcePlan,
best: &mut SmallestFrame,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) {
let grid = frame.grid;
if grid.single_group() {
return;
}
let palettes: Vec<Option<palette::LocalPaletteGroup>> =
pool.steal_map(scratch, grid.num_groups(), |group_index, _scratch| {
let (x0, y0, w, h) = grid.rect(group_index);
palette::build_local_palette_group_limited(
frame.ycocg,
frame.alpha,
frame.xsize,
x0,
y0,
w,
h,
palette::LOCAL_PALETTE_MAX_COLORS,
)
});
let covered: usize = palettes
.iter()
.flatten()
.map(|palette| palette.w * palette.h)
.sum();
if covered * 2 < frame.xsize * frame.ysize {
return;
}
let ordered: Vec<Option<palette::LocalPaletteGroup>> =
pool.steal_map(scratch, grid.num_groups(), |group_index, _scratch| {
palette::ordered_local_palette(palettes[group_index].as_ref()?)
});
let layout = frame.default_layout();
let mut raced: Option<(MaSource<'_>, CoarseLearn)> = None;
let has_reordered = ordered.iter().any(Option::is_some);
for use_reordered in [false, true]
.into_iter()
.take(1 + usize::from(has_reordered))
{
let groups = palettes.iter().zip(&ordered).map(|(original, changed)| {
if use_reordered {
changed.as_ref().or(original.as_ref())
} else {
original.as_ref()
}
});
let mixed = mixed_ma_source(
frame.ycocg,
frame.alpha,
frame.xsize,
groups,
frame.alpha_constant,
);
let stage = learn_ma_candidate(
&mixed,
frame.xsize,
frame.ysize,
layout,
frame.min_symbol,
sources.wp_params,
frame.use_wp,
mixed.max_leaves(),
sources.final_sampling,
pool,
scratch,
);
let Some(stage) = stage else {
continue;
};
if raced.as_ref().is_none_or(|(_, leader)| {
stage.candidate.est_real < leader.candidate.est_real * ORDERED_GROUP_PALETTE_MARGIN
}) {
raced = Some((mixed, stage));
}
}
let Some((mixed, stage)) = raced else {
return;
};
if stage.candidate.est_real >= self.best_source_coarse * PER_GROUP_MARGIN {
return;
}
let cand = finish_ma_learn(
frame.settings.speed,
stage,
frame.min_symbol,
frame.use_wp,
mixed.max_leaves(),
pool,
scratch,
);
let mut candidate = BitWriter::new();
let estimated_savings = write_learned_tree_frame(
frame.settings.speed,
&mixed,
frame.alpha.is_some(),
frame.kind,
frame.xsize,
frame.ysize,
layout,
frame.min_symbol,
pool,
scratch,
sources.wp_params,
frame.use_wp,
&cand,
frame.tree_search,
&mut candidate,
);
if learned_tree_is_decisive(estimated_savings) {
self.decisive = true;
color.release_planes();
}
best.offer(candidate);
}
}