use super::{ColorTransform, CoreFrame, SmallestFrame, 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, 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, PALETTE_COARSE_MARGIN, PALETTE_FINAL_MARGIN, build_global_palette,
};
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;
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 palette = if effort.tree_global_palette {
build_global_palette(
frame.ycocg,
frame.alpha,
frame.num_color,
frame.xsize,
frame.ysize,
pool,
scratch,
)
} else {
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);
}
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,
&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,
}
}
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 all: Vec<GroupLayout> = if dual {
vec![GroupLayout::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(
&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 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| {
rank_coarse(
source,
xsize,
ysize,
frame.min_symbol,
wp_params,
frame.use_wp,
rank_layout,
rank_sampling,
pool,
scratch,
)
};
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,
rgb_stage.take(),
self.wp_params,
&header_bits,
effort.tree_rank_deep(),
rank_layout,
self.rank_sampling,
keep_stages,
pool,
scratch,
)
};
self.wp_params = params;
rgb_stage = stage;
if let Some(&(runner_up, cost)) = color.ranked.get(1)
&& cost <= color.ranked[0].1 * RCT_RANK_MARGIN
{
rgb_stage = None;
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
&& effort.tree_rank_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.local_trees,
&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,
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((layout, cand, coarse)) = learn_best_layout(
frame.settings.speed,
&source,
frame.xsize,
frame.ysize,
&layouts.all,
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,
) else {
return;
};
if cand.est_real <= self.rgb_final * PALETTE_FINAL_MARGIN {
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.local_trees,
&mut candidate,
);
if learned_tree_is_decisive(estimated_savings) {
self.decisive = true;
color.release_planes();
}
best.offer(candidate);
}
self.best_source_coarse = self.best_source_coarse.min(coarse);
}
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 mixed = mixed_ma_source(
frame.ycocg,
frame.alpha,
frame.xsize,
&palettes,
frame.alpha_constant,
);
let layout = frame.default_layout();
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.filter(|s| s.candidate.est_real < self.best_source_coarse * PER_GROUP_MARGIN)
else {
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.local_trees,
&mut candidate,
);
if learned_tree_is_decisive(estimated_savings) {
self.decisive = true;
color.release_planes();
}
best.offer(candidate);
}
}