use super::dlog2::f_log2;
use super::histogram::Histogram;
use super::huffman_tree::{HuffmanNode, create_huffman_tree};
use super::prefix_code::ALPHABET_SIZE;
use crate::adaptive_quant::dirty_log2f;
use crate::util::heap_array;
use std::sync::OnceLock;
pub(crate) const CLUSTERS_LIMIT: usize = 128;
const MIN_DISTANCE_FOR_DISTINCT: f32 = 64.0;
pub(crate) struct FixedClusterScratch<const MAX_CONTEXTS: usize> {
symbols: Box<[u8; MAX_CONTEXTS]>,
in_costs: Box<[f32; MAX_CONTEXTS]>,
dists: Box<[f32; MAX_CONTEXTS]>,
clusters: Box<[Histogram; CLUSTERS_LIMIT]>,
cluster_costs: Box<[f32; CLUSTERS_LIMIT]>,
reordered: Box<[Histogram; CLUSTERS_LIMIT]>,
}
impl<const MAX_CONTEXTS: usize> Default for FixedClusterScratch<MAX_CONTEXTS> {
fn default() -> Self {
Self {
symbols: heap_array(0),
in_costs: heap_array(0.0),
dists: heap_array(0.0),
clusters: heap_array(Histogram::new()),
cluster_costs: heap_array(0.0),
reordered: heap_array(Histogram::new()),
}
}
}
type CountsBitCostFn = fn(&[u32; ALPHABET_SIZE], u32) -> f32;
#[inline]
#[cfg_attr(
any(
all(target_arch = "aarch64", feature = "neon"),
all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128")
),
allow(dead_code)
)]
fn counts_bit_cost_scalar(counts: &[u32; ALPHABET_SIZE], total_count: u32) -> f32 {
debug_assert_ne!(total_count, 0);
let log_total = dirty_log2f(total_count as f32);
let mut cost = 0.0f32;
for &count in counts {
if count != 0 {
cost += count as f32 * (log_total - dirty_log2f(count as f32));
}
}
cost.max(0.0)
}
#[cfg(any(target_arch = "x86_64", target_arch = "x86"))]
fn select_counts_bit_cost_fn() -> CountsBitCostFn {
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
if std::is_x86_feature_detected!("avx2") && std::is_x86_feature_detected!("fma") {
return |counts, total_count| unsafe {
crate::avx::counts_bit_cost_avx2(counts, total_count)
};
}
#[cfg(all(any(target_arch = "x86_64", target_arch = "x86"), feature = "sse"))]
if std::is_x86_feature_detected!("sse4.1") {
return |counts, total_count| unsafe {
crate::sse::counts_bit_cost_sse41(counts, total_count)
};
}
counts_bit_cost_scalar
}
#[cfg(all(target_arch = "aarch64", feature = "neon"))]
fn select_counts_bit_cost_fn() -> CountsBitCostFn {
|counts, total_count| unsafe { crate::neon::counts_bit_cost_neon(counts, total_count) }
}
#[cfg(all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128"))]
fn select_counts_bit_cost_fn() -> CountsBitCostFn {
crate::wasm::counts_bit_cost_wasm
}
#[cfg(not(any(
target_arch = "x86_64",
target_arch = "x86",
all(target_arch = "aarch64", feature = "neon"),
all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128")
)))]
fn select_counts_bit_cost_fn() -> CountsBitCostFn {
counts_bit_cost_scalar
}
#[inline]
fn counts_bit_cost(counts: &[u32; ALPHABET_SIZE], total_count: u32) -> f32 {
if total_count == 0 {
return 0.0;
}
let mut used_symbols = 0usize;
for &count in counts.iter() {
if count != 0 {
used_symbols += 1;
if used_symbols > 2 {
break;
}
}
}
if used_symbols <= 1 {
return 0.0;
}
if used_symbols == 2 {
return total_count as f32;
}
static COUNTS_BIT_COST_FN: OnceLock<CountsBitCostFn> = OnceLock::new();
COUNTS_BIT_COST_FN.get_or_init(select_counts_bit_cost_fn)(counts, total_count)
}
#[inline]
fn exact_counts_bit_cost(
counts: &[u32; ALPHABET_SIZE],
total_count: u32,
huffman_pool: &mut Vec<HuffmanNode>,
) -> f32 {
if total_count == 0 {
return 0.0;
}
let used_symbols = counts.iter().filter(|&&count| count != 0).count();
if used_symbols <= 1 {
return 0.0;
}
if used_symbols == 2 {
return total_count as f32;
}
let mut depths = [0u8; ALPHABET_SIZE];
create_huffman_tree(counts, 15, &mut depths, huffman_pool);
counts
.iter()
.zip(depths)
.map(|(&count, depth)| count as f32 * depth as f32)
.sum()
}
#[inline]
fn histogram_bit_cost(h: &Histogram) -> f32 {
counts_bit_cost(&h.counts, h.total_count)
}
#[inline]
fn add_counts(dst: &mut [u32; ALPHABET_SIZE], src: &[u32; ALPHABET_SIZE]) {
for (dst, &src) in dst.iter_mut().zip(src.iter()) {
*dst += src;
}
}
#[inline]
fn histogram_add(a: &mut Histogram, b: &Histogram) {
add_counts(&mut a.counts, &b.counts);
a.total_count += b.total_count;
}
#[inline]
fn histogram_sub(a: &mut Histogram, b: &Histogram) {
for (dst, &src) in a.counts.iter_mut().zip(b.counts.iter()) {
*dst -= src;
}
a.total_count -= b.total_count;
}
#[inline]
fn histogram_distance(
a: &Histogram,
b: &Histogram,
a_cost: f32,
b_cost: f32,
scratch: &mut [u32; ALPHABET_SIZE],
) -> f32 {
if a.total_count == 0 || b.total_count == 0 {
return 0.0;
}
*scratch = a.counts;
add_counts(scratch, &b.counts);
counts_bit_cost(scratch, a.total_count + b.total_count) - a_cost - b_cost
}
#[inline]
fn histogram_merge_increment(
input: &Histogram,
cluster: &Histogram,
cluster_cost: f32,
scratch: &mut [u32; ALPHABET_SIZE],
) -> f32 {
*scratch = input.counts;
add_counts(scratch, &cluster.counts);
counts_bit_cost(scratch, input.total_count + cluster.total_count) - cluster_cost
}
fn update_exact_merge_pair(
i: usize,
j: usize,
clusters: &[Histogram],
active: &[bool; CLUSTERS_LIMIT],
costs: &[f32; CLUSTERS_LIMIT],
deltas: &mut [f32; CLUSTERS_LIMIT * CLUSTERS_LIMIT],
huffman_pool: &mut Vec<HuffmanNode>,
) {
if i == j || !active[i] || !active[j] {
return;
}
let (a, b) = if i < j { (i, j) } else { (j, i) };
let mut merged_counts = clusters[a].counts;
add_counts(&mut merged_counts, &clusters[b].counts);
let combined = exact_counts_bit_cost(
&merged_counts,
clusters[a].total_count + clusters[b].total_count,
huffman_pool,
);
deltas[a * CLUSTERS_LIMIT + b] = combined - costs[a] - costs[b] - MIN_DISTANCE_FOR_DISTINCT;
}
fn exact_merge_final_clusters(
clusters: &mut [Histogram],
symbols: &mut [u8],
huffman_pool: &mut Vec<HuffmanNode>,
) {
let n = clusters.len();
if n <= 1 {
return;
}
debug_assert!(n <= CLUSTERS_LIMIT);
let mut active = [false; CLUSTERS_LIMIT];
let mut costs = [0.0f32; CLUSTERS_LIMIT];
for (i, histogram) in clusters.iter().enumerate() {
active[i] = histogram.total_count != 0;
costs[i] = exact_counts_bit_cost(&histogram.counts, histogram.total_count, huffman_pool);
}
let mut deltas = [f32::INFINITY; CLUSTERS_LIMIT * CLUSTERS_LIMIT];
for i in 0..n {
for j in i + 1..n {
update_exact_merge_pair(i, j, clusters, &active, &costs, &mut deltas, huffman_pool);
}
}
loop {
let mut best = None;
let mut best_delta = -0.01f32;
for i in 0..n {
if !active[i] {
continue;
}
for j in i + 1..n {
let delta = deltas[i * CLUSTERS_LIMIT + j];
if active[j] && delta < best_delta {
best_delta = delta;
best = Some((i, j));
}
}
}
let Some((keep, remove)) = best else {
break;
};
let removed = clusters[remove].clone();
histogram_add(&mut clusters[keep], &removed);
clusters[remove] = Histogram::new();
active[remove] = false;
costs[keep] = exact_counts_bit_cost(
&clusters[keep].counts,
clusters[keep].total_count,
huffman_pool,
);
for symbol in symbols.iter_mut() {
if *symbol as usize == remove {
*symbol = keep as u8;
}
}
for j in 0..n {
deltas[remove * CLUSTERS_LIMIT + j] = f32::INFINITY;
deltas[j * CLUSTERS_LIMIT + remove] = f32::INFINITY;
update_exact_merge_pair(
keep,
j,
clusters,
&active,
&costs,
&mut deltas,
huffman_pool,
);
}
}
}
pub(crate) fn cluster_histograms(
histograms: &mut Vec<Histogram>,
context_map: &mut Vec<u8>,
huffman_pool: &mut Vec<HuffmanNode>,
) {
cluster_histograms_inner(histograms, context_map, false, huffman_pool);
}
pub(crate) fn cluster_histograms_fixed<const MAX_CONTEXTS: usize>(
histograms: &mut [Histogram],
context_map: &mut [u8],
refined: bool,
fixed: &mut FixedClusterScratch<MAX_CONTEXTS>,
huffman_pool: &mut Vec<HuffmanNode>,
) -> usize {
let n = histograms.len();
assert!(n <= MAX_CONTEXTS);
assert!(context_map.len() >= n);
if n <= 1 {
context_map[..n].fill(0);
return n;
}
const UNMAPPED: u8 = u8::MAX;
let max_histograms = CLUSTERS_LIMIT.min(n);
let unassigned = max_histograms as u8;
let symbols = &mut fixed.symbols[..n];
symbols.fill(unassigned);
let in_costs = &mut fixed.in_costs[..n];
let dists = &mut fixed.dists[..n];
dists.fill(f32::MAX);
let mut largest_idx = 0usize;
let mut largest_count = 0u32;
for (i, (((hist, symbol), dist), cost)) in histograms
.iter()
.zip(symbols.iter_mut())
.zip(dists.iter_mut())
.zip(in_costs.iter_mut())
.enumerate()
{
let total_count = hist.total_count;
if total_count == 0 {
*symbol = 0;
*dist = 0.0;
continue;
}
*cost = histogram_bit_cost(hist);
if total_count > largest_count {
largest_count = total_count;
largest_idx = i;
}
}
if largest_count == 0 {
histograms[0] = Histogram::new();
context_map[..n].fill(0);
return 1;
}
let clusters = &mut fixed.clusters;
let cluster_costs = &mut fixed.cluster_costs;
let mut num_clusters = 0usize;
let mut counts_scratch = [0u32; ALPHABET_SIZE];
while num_clusters < max_histograms {
let candidate = largest_idx;
clusters[num_clusters] = histograms[largest_idx].clone();
cluster_costs[num_clusters] = in_costs[largest_idx];
let mut saving = if dists[largest_idx] == f32::MAX {
f32::INFINITY
} else {
dists[largest_idx]
};
dists[largest_idx] = 0.0;
let last_hist = &clusters[num_clusters];
let last_cost = cluster_costs[num_clusters];
let mut next_largest_idx = candidate;
let mut next_largest_dist = 0.0f32;
for (i, ((hist, &in_cost), dist)) in histograms
.iter()
.zip(in_costs.iter())
.zip(dists.iter_mut())
.enumerate()
{
if *dist == 0.0 {
continue;
}
let distance =
histogram_distance(hist, last_hist, in_cost, last_cost, &mut counts_scratch);
if distance < *dist {
if *dist != f32::MAX {
saving += *dist - distance;
}
*dist = distance;
}
if *dist > next_largest_dist {
next_largest_dist = *dist;
next_largest_idx = i;
}
}
if num_clusters > 0 && saving < MIN_DISTANCE_FOR_DISTINCT {
break;
}
symbols[candidate] = num_clusters as u8;
num_clusters += 1;
largest_idx = next_largest_idx;
if next_largest_dist == 0.0 {
break; }
}
if !refined {
for ((hist, &in_cost), symbol) in histograms
.iter()
.zip(in_costs.iter())
.zip(symbols.iter_mut())
{
if *symbol != unassigned {
continue;
}
let mut best = 0usize;
let mut best_dist = histogram_distance(
hist,
&clusters[0],
in_cost,
cluster_costs[0],
&mut counts_scratch,
);
for candidate in 1..num_clusters {
let distance = histogram_distance(
hist,
&clusters[candidate],
in_cost,
cluster_costs[candidate],
&mut counts_scratch,
);
if distance < best_dist {
best = candidate;
best_dist = distance;
}
}
histogram_add(&mut clusters[best], hist);
cluster_costs[best] = histogram_bit_cost(&clusters[best]);
*symbol = best as u8;
}
} else {
for ((hist, &in_cost), symbol) in histograms
.iter()
.zip(in_costs.iter())
.zip(symbols.iter_mut())
{
if *symbol != unassigned {
continue;
}
let mut best = 0usize;
let mut best_dist = histogram_distance(
hist,
&clusters[0],
in_cost,
cluster_costs[0],
&mut counts_scratch,
);
for candidate in 1..num_clusters {
let distance = histogram_distance(
hist,
&clusters[candidate],
in_cost,
cluster_costs[candidate],
&mut counts_scratch,
);
if distance < best_dist {
best = candidate;
best_dist = distance;
}
}
*symbol = best as u8;
}
clusters[..num_clusters].fill(Histogram::new());
for (hist, &symbol) in histograms.iter().zip(symbols.iter()) {
histogram_add(&mut clusters[symbol as usize], hist);
}
for cluster in 0..num_clusters {
cluster_costs[cluster] = histogram_bit_cost(&clusters[cluster]);
}
for _ in 0..2 {
let mut changed = false;
for (hist, symbol) in histograms.iter().zip(symbols.iter_mut()) {
if hist.total_count == 0 {
continue;
}
let old = *symbol as usize;
let mut old_without = clusters[old].clone();
histogram_sub(&mut old_without, hist);
let remove_delta = histogram_bit_cost(&old_without) - cluster_costs[old];
let mut best = old;
let mut best_delta = 0.0f32;
for candidate in 0..num_clusters {
if candidate == old || clusters[candidate].total_count == 0 {
continue;
}
let add_delta = histogram_merge_increment(
hist,
&clusters[candidate],
cluster_costs[candidate],
&mut counts_scratch,
);
let delta = remove_delta + add_delta;
if delta < best_delta - 0.01 {
best_delta = delta;
best = candidate;
}
}
if best != old {
histogram_sub(&mut clusters[old], hist);
histogram_add(&mut clusters[best], hist);
cluster_costs[old] = histogram_bit_cost(&clusters[old]);
cluster_costs[best] = histogram_bit_cost(&clusters[best]);
*symbol = best as u8;
changed = true;
}
}
if !changed {
break;
}
}
}
exact_merge_final_clusters(&mut clusters[..num_clusters], symbols, huffman_pool);
let mut compact = [UNMAPPED; CLUSTERS_LIMIT];
let mut compact_len = 0usize;
for (old, histogram) in clusters[..num_clusters].iter().enumerate() {
if histogram.total_count != 0 {
compact[old] = compact_len as u8;
fixed.reordered[compact_len] = histogram.clone();
compact_len += 1;
}
}
for symbol in symbols.iter_mut() {
*symbol = compact[*symbol as usize];
}
clusters[..compact_len].clone_from_slice(&fixed.reordered[..compact_len]);
num_clusters = compact_len;
let mut remap = [UNMAPPED; CLUSTERS_LIMIT];
let mut reordered_len = 0usize;
for (i, &symbol) in symbols.iter().enumerate() {
debug_assert_ne!(symbol, unassigned);
let old_index = symbol as usize;
debug_assert!(old_index < num_clusters);
if remap[old_index] == UNMAPPED {
remap[old_index] = reordered_len as u8;
fixed.reordered[reordered_len] = clusters[old_index].clone();
reordered_len += 1;
}
context_map[i] = remap[old_index];
}
histograms[..reordered_len].clone_from_slice(&fixed.reordered[..reordered_len]);
reordered_len
}
fn cluster_histograms_inner(
histograms: &mut Vec<Histogram>,
context_map: &mut Vec<u8>,
refined: bool,
huffman_pool: &mut Vec<HuffmanNode>,
) {
if histograms.len() <= 1 {
context_map.clear();
context_map.resize(histograms.len(), 0);
return;
}
const UNMAPPED: u8 = u8::MAX;
let max_histograms = CLUSTERS_LIMIT.min(histograms.len());
let unassigned = max_histograms as u8;
let inp = core::mem::take(histograms);
let n = inp.len();
let mut symbols: Vec<u8> = vec![unassigned; n];
let mut in_costs = vec![0.0f32; n];
let mut dists = vec![f32::MAX; n];
let mut largest_idx = 0usize;
let mut largest_count = 0u32;
for (i, (((hist, symbol), dist), cost)) in inp
.iter()
.zip(symbols.iter_mut())
.zip(dists.iter_mut())
.zip(in_costs.iter_mut())
.enumerate()
{
let total_count = hist.total_count;
if total_count == 0 {
*symbol = 0;
*dist = 0.0;
continue;
}
*cost = histogram_bit_cost(hist);
if total_count > largest_count {
largest_count = total_count;
largest_idx = i;
}
}
if largest_count == 0 {
*histograms = vec![Histogram::new()];
context_map.clear();
context_map.resize(n, 0);
return;
}
let mut out: Vec<Histogram> = Vec::with_capacity(max_histograms);
let mut out_costs: Vec<f32> = Vec::with_capacity(max_histograms);
let mut scratch = [0u32; ALPHABET_SIZE];
while out.len() < max_histograms {
let candidate = largest_idx;
out.push(inp[candidate].clone());
out_costs.push(in_costs[candidate]);
let mut saving = if dists[candidate] == f32::MAX {
f32::INFINITY
} else {
dists[candidate]
};
dists[candidate] = 0.0;
let last_idx = out.len() - 1;
let last_hist = &out[last_idx];
let last_cost = out_costs[last_idx];
let mut next_largest_idx = candidate;
let mut next_largest_dist = 0.0f32;
for (i, ((hist, &in_cost), dist)) in inp
.iter()
.zip(in_costs.iter())
.zip(dists.iter_mut())
.enumerate()
{
if *dist == 0.0 {
continue;
}
let d = histogram_distance(hist, last_hist, in_cost, last_cost, &mut scratch);
if d < *dist {
if *dist != f32::MAX {
saving += *dist - d;
}
*dist = d;
}
if *dist > next_largest_dist {
next_largest_dist = *dist;
next_largest_idx = i;
}
}
if out.len() > 1 && saving < MIN_DISTANCE_FOR_DISTINCT {
out.pop();
out_costs.pop();
break;
}
symbols[candidate] = (out.len() - 1) as u8;
largest_idx = next_largest_idx;
if next_largest_dist == 0.0 {
break;
}
}
if !refined {
for ((hist, &in_cost), symbol) in inp.iter().zip(in_costs.iter()).zip(symbols.iter_mut()) {
if *symbol != unassigned {
continue;
}
let mut best = 0usize;
let mut best_dist =
histogram_distance(hist, &out[0], in_cost, out_costs[0], &mut scratch);
for (j, (candidate, &candidate_cost)) in
out.iter().zip(out_costs.iter()).enumerate().skip(1)
{
let d = histogram_distance(hist, candidate, in_cost, candidate_cost, &mut scratch);
if d < best_dist {
best = j;
best_dist = d;
}
}
histogram_add(&mut out[best], hist);
out_costs[best] = histogram_bit_cost(&out[best]);
*symbol = best as u8;
}
} else {
for ((hist, &in_cost), symbol) in inp.iter().zip(in_costs.iter()).zip(symbols.iter_mut()) {
if *symbol != unassigned {
continue;
}
let mut best = 0usize;
let mut best_dist =
histogram_distance(hist, &out[0], in_cost, out_costs[0], &mut scratch);
for (j, (candidate, &candidate_cost)) in
out.iter().zip(out_costs.iter()).enumerate().skip(1)
{
let d = histogram_distance(hist, candidate, in_cost, candidate_cost, &mut scratch);
if d < best_dist {
best = j;
best_dist = d;
}
}
*symbol = best as u8;
}
out.fill(Histogram::new());
for (hist, &symbol) in inp.iter().zip(symbols.iter()) {
histogram_add(&mut out[symbol as usize], hist);
}
for (cost, hist) in out_costs.iter_mut().zip(out.iter()) {
*cost = histogram_bit_cost(hist);
}
for _ in 0..2 {
let mut changed = false;
for (hist, symbol) in inp.iter().zip(symbols.iter_mut()) {
if hist.total_count == 0 {
continue;
}
let old = *symbol as usize;
let mut old_without = out[old].clone();
histogram_sub(&mut old_without, hist);
let remove_delta = histogram_bit_cost(&old_without) - out_costs[old];
let mut best = old;
let mut best_delta = 0.0f32;
for candidate in 0..out.len() {
if candidate == old || out[candidate].total_count == 0 {
continue;
}
let add_delta = histogram_merge_increment(
hist,
&out[candidate],
out_costs[candidate],
&mut scratch,
);
let delta = remove_delta + add_delta;
if delta < best_delta - 0.01 {
best_delta = delta;
best = candidate;
}
}
if best != old {
histogram_sub(&mut out[old], hist);
histogram_add(&mut out[best], hist);
out_costs[old] = histogram_bit_cost(&out[old]);
out_costs[best] = histogram_bit_cost(&out[best]);
*symbol = best as u8;
changed = true;
}
}
if !changed {
break;
}
}
}
exact_merge_final_clusters(&mut out, &mut symbols, huffman_pool);
let mut compact = vec![UNMAPPED; out.len()];
let mut compact_out = Vec::with_capacity(out.len());
for (old, hist) in out.into_iter().enumerate() {
if hist.total_count != 0 {
compact[old] = compact_out.len() as u8;
compact_out.push(hist);
}
}
for symbol in &mut symbols {
*symbol = compact[*symbol as usize];
}
out = compact_out;
let mut remap = [UNMAPPED; CLUSTERS_LIMIT];
let mut tmp: Vec<Option<Histogram>> = out.into_iter().map(Some).collect();
let mut reordered: Vec<Histogram> = Vec::with_capacity(tmp.len());
let mut next_index = 0u8;
for &symbol in &symbols {
debug_assert_ne!(symbol, unassigned);
let old_index = symbol as usize;
debug_assert!(old_index < tmp.len());
let mapped = &mut remap[old_index];
if *mapped == UNMAPPED {
*mapped = next_index;
reordered.push(
tmp[old_index]
.take()
.expect("cluster must be reindexed once"),
);
next_index += 1;
}
}
*histograms = reordered;
context_map.clear();
context_map.reserve(symbols.len());
context_map.extend(symbols.iter().map(|&symbol| remap[symbol as usize]));
}
fn context_map_merge_saving(a: usize, b: usize) -> f64 {
if a == 0 || b == 0 {
return 0.0;
}
let (a, b) = (a as f64, b as f64);
let merged = a + b;
a * f_log2(merged / a) + b * f_log2(merged / b)
}
pub(crate) fn cluster_histograms_ans(
histograms: &mut [Histogram],
context_map: &mut [u8],
pool: Option<&crate::thread_pool::ThreadPool>,
charge_context_map: bool,
) -> usize {
use super::ans::{AnsCostScratch, fast_ans_population_cost_scratch};
use crate::coder_scratch::CoderScratch;
use crate::thread_pool::ThreadPool;
let n = histograms.len();
assert!(context_map.len() >= n);
if n <= 1 {
context_map[..n].fill(0);
return n;
}
fn cost_of(h: &Histogram, s: &mut AnsCostScratch) -> f64 {
if h.total_count == 0 {
0.0
} else {
fast_ans_population_cost_scratch(&h.counts, 1, s)
}
}
fn merge_cost(a: &Histogram, b: &Histogram, s: &mut AnsCostScratch) -> f64 {
s.merged = a.counts;
add_counts(&mut s.merged, &b.counts);
let merged = s.merged;
fast_ans_population_cost_scratch(&merged, 1, s)
}
fn par_map<R: Send>(
n: usize,
workers: &mut Option<(&ThreadPool, CoderScratch)>,
f: impl Fn(usize, &mut AnsCostScratch) -> R + Sync,
) -> Vec<R> {
let Some((pool, caller_scratch)) = workers else {
let mut s = AnsCostScratch::new();
return (0..n).map(|i| f(i, &mut s)).collect();
};
let threads = pool.num_threads().min(n);
let chunk = n.div_ceil(threads);
let parts = pool.steal_map(caller_scratch, n.div_ceil(chunk), |part, _| {
let begin = part * chunk;
let end = (begin + chunk).min(n);
let mut s = AnsCostScratch::new();
(begin..end).map(|i| f(i, &mut s)).collect::<Vec<R>>()
});
parts.into_iter().flatten().collect()
}
let mut workers = pool
.filter(|pool| n >= 64 && pool.num_threads() > 1)
.map(|pool| (pool, CoderScratch::lossless()));
let mut scratch = AnsCostScratch::new();
let in_costs: Vec<f64> = par_map(n, &mut workers, |i, s| cost_of(&histograms[i], s));
let mut clusters: Vec<Histogram> = Vec::new();
let mut cluster_costs: Vec<f64> = Vec::new();
let mut dists = vec![f64::MAX; n];
let mut seed = 0usize;
let mut seed_count = 0u32;
for (i, h) in histograms.iter().enumerate() {
if h.total_count > seed_count {
seed_count = h.total_count;
seed = i;
}
}
if seed_count == 0 {
histograms[0] = Histogram::new();
context_map[..n].fill(0);
return 1;
}
while clusters.len() < CLUSTERS_LIMIT {
clusters.push(histograms[seed].clone());
cluster_costs.push(in_costs[seed]);
dists[seed] = 0.0;
let last = &clusters[clusters.len() - 1];
let last_cost = cluster_costs[clusters.len() - 1];
let updated: Vec<f64> = {
let dists = &dists;
par_map(n, &mut workers, |i, s| {
let h = &histograms[i];
if h.total_count == 0 {
return 0.0;
}
if dists[i] == 0.0 {
return 0.0;
}
let d = merge_cost(h, last, s) - in_costs[i] - last_cost;
dists[i].min(d)
})
};
dists = updated;
let mut next_seed = seed;
let mut next_dist = 0.0f64;
for (i, &d) in dists.iter().enumerate() {
if d > next_dist {
next_dist = d;
next_seed = i;
}
}
if next_dist <= 0.0 {
break;
}
seed = next_seed;
}
let num_seeds = clusters.len();
let mut assignment: Vec<u8> = {
let clusters = &clusters;
let cluster_costs = &cluster_costs;
par_map(n, &mut workers, |i, s| {
let h = &histograms[i];
if h.total_count == 0 {
return 0u8;
}
let mut best = 0usize;
let mut best_d = f64::MAX;
for c in 0..num_seeds {
let d = merge_cost(h, &clusters[c], s) - cluster_costs[c];
if d < best_d {
best_d = d;
best = c;
}
}
best as u8
})
};
let rebuild = |clusters: &mut Vec<Histogram>,
cluster_costs: &mut Vec<f64>,
assignment: &[u8],
s: &mut AnsCostScratch| {
for c in clusters.iter_mut() {
*c = Histogram::new();
}
for (h, &a) in histograms.iter().zip(assignment) {
histogram_add(&mut clusters[a as usize], h);
}
for (c, cost) in clusters.iter().zip(cluster_costs.iter_mut()) {
*cost = cost_of(c, s);
}
};
rebuild(&mut clusters, &mut cluster_costs, &assignment, &mut scratch);
for _ in 0..2 {
let proposals: Vec<Option<u8>> = {
let clusters = &clusters;
let cluster_costs = &cluster_costs;
let assignment = &assignment;
par_map(n, &mut workers, |i, s| {
let h = &histograms[i];
if h.total_count == 0 {
return None;
}
let old = assignment[i] as usize;
let mut without = clusters[old].clone();
histogram_sub(&mut without, h);
let remove_delta = cost_of(&without, s) - cluster_costs[old];
let mut best = old;
let mut best_delta = 0.0f64;
for c in 0..num_seeds {
if c == old {
continue;
}
let delta = remove_delta + merge_cost(h, &clusters[c], s) - cluster_costs[c];
if delta < best_delta - 0.01 {
best_delta = delta;
best = c;
}
}
(best != old).then_some(best as u8)
})
};
let mut changed = false;
for (i, proposal) in proposals.iter().enumerate() {
let Some(best) = *proposal else { continue };
let best = best as usize;
let old = assignment[i] as usize;
let h = &histograms[i];
let mut without = clusters[old].clone();
histogram_sub(&mut without, h);
let remove_delta = cost_of(&without, &mut scratch) - cluster_costs[old];
let add_delta = merge_cost(h, &clusters[best], &mut scratch) - cluster_costs[best];
if remove_delta + add_delta < -0.01 {
histogram_sub(&mut clusters[old], h);
histogram_add(&mut clusters[best], h);
cluster_costs[old] = cost_of(&clusters[old], &mut scratch);
cluster_costs[best] = cost_of(&clusters[best], &mut scratch);
assignment[i] = best as u8;
changed = true;
}
}
if !changed {
break;
}
}
let mut active: Vec<bool> = clusters.iter().map(|c| c.total_count != 0).collect();
let mut members = vec![0usize; num_seeds];
for (h, &a) in histograms.iter().zip(&assignment) {
if h.total_count != 0 {
members[a as usize] += 1;
}
}
loop {
let mut best_pair = None;
let mut best_delta = -1e-6f64;
for a in 0..num_seeds {
if !active[a] {
continue;
}
for b in a + 1..num_seeds {
if !active[b] {
continue;
}
let delta = merge_cost(&clusters[a], &clusters[b], &mut scratch)
- cluster_costs[a]
- cluster_costs[b]
- if charge_context_map {
context_map_merge_saving(members[a], members[b])
} else {
0.0
};
if delta < best_delta {
best_delta = delta;
best_pair = Some((a, b));
}
}
}
let Some((a, b)) = best_pair else { break };
let bh = clusters[b].clone();
histogram_add(&mut clusters[a], &bh);
cluster_costs[a] = cost_of(&clusters[a], &mut scratch);
members[a] += members[b];
active[b] = false;
for m in assignment.iter_mut() {
if *m == b as u8 {
*m = a as u8;
}
}
}
let mut remap = vec![u8::MAX; num_seeds];
let mut ordered: Vec<Histogram> = Vec::new();
for (i, &a) in assignment.iter().enumerate() {
let a = a as usize;
if remap[a] == u8::MAX {
remap[a] = ordered.len() as u8;
ordered.push(clusters[a].clone());
}
context_map[i] = remap[a];
}
let num = ordered.len();
histograms[..num].clone_from_slice(&ordered);
num
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn ans_clustering_is_independent_of_thread_count() {
let n = 300usize;
let mut state = 0x9E37_79B9u32;
let mut next = || {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
state
};
let base: Vec<Histogram> = (0..n)
.map(|i| {
let mut h = Histogram::new();
let total = 50 + next() % 5000;
let p_one = (i as u32 * 7 + next() % 40) % 1000;
let ones = (total as u64 * p_one as u64 / 1000) as u32;
for _ in 0..(total - ones) {
h.add(0);
}
for _ in 0..ones {
h.add(1 + next() % 3);
}
h
})
.collect();
for len in [0, 1, 63, 64, 65, n] {
let run = |threads: usize| {
let mut histograms = base[..len].to_vec();
let mut map = vec![0u8; len];
let pool = crate::thread_pool::ThreadPool::new_lossless(threads);
let num = cluster_histograms_ans(&mut histograms, &mut map, Some(&pool), true);
(num, map, histograms[..num].to_vec())
};
let (num1, map1, hist1) = run(1);
if len == n {
assert!(num1 > 2, "expected several clusters, got {num1}");
}
for threads in [0, 2, 3, 8] {
let (num, map, hist) = run(threads);
assert_eq!(
num, num1,
"cluster count differs: len={len}, threads={threads}"
);
assert_eq!(
map, map1,
"context map differs: len={len}, threads={threads}"
);
assert!(
hist.iter().zip(&hist1).all(|(a, b)| a.counts == b.counts),
"cluster histograms differ: len={len}, threads={threads}"
);
}
}
}
fn histogram(entries: &[(usize, u32)]) -> Histogram {
let mut histogram = Histogram::new();
for &(symbol, count) in entries {
histogram.counts[symbol] = count;
histogram.total_count += count;
}
histogram
}
#[allow(dead_code)]
fn assert_simd_counts_bit_cost_matches_scalar(
mut simd_cost: impl FnMut(&[u32; ALPHABET_SIZE], u32) -> f32,
) {
let mut wide_counts = [0u32; ALPHABET_SIZE];
wide_counts[0] = 0x8000_0000;
wide_counts[1] = 0x4000_0000;
wide_counts[2] = 1;
let wide_total = 0xc000_0001;
let scalar = counts_bit_cost_scalar(&wide_counts, wide_total);
let simd = simd_cost(&wide_counts, wide_total);
let tolerance = 0.05f32.max(scalar.abs() * 2e-6);
assert!(
(simd - scalar).abs() <= tolerance,
"unsigned conversion: simd={simd} scalar={scalar}"
);
let mut state = 0x1234_5678u32;
for case in 0..256 {
let mut counts = [0u32; ALPHABET_SIZE];
for count in &mut counts {
state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
*count = if state & 7 == 0 {
0
} else {
(state >> (case % 17)) & 0x3fff
};
}
let total: u32 = counts.iter().sum();
let scalar = counts_bit_cost_scalar(&counts, total);
let simd = simd_cost(&counts, total);
let tolerance = 0.05f32.max(scalar.abs() * 2e-6);
assert!(
(simd - scalar).abs() <= tolerance,
"case {case}: simd={simd} scalar={scalar}"
);
}
}
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
#[test]
fn avx2_counts_bit_cost_matches_scalar() {
if !std::is_x86_feature_detected!("avx2") || !std::is_x86_feature_detected!("fma") {
return;
}
assert_simd_counts_bit_cost_matches_scalar(|counts, total| unsafe {
crate::avx::counts_bit_cost_avx2(counts, total)
});
}
#[cfg(all(any(target_arch = "x86_64", target_arch = "x86"), feature = "sse"))]
#[test]
fn sse41_counts_bit_cost_matches_scalar() {
if !std::is_x86_feature_detected!("sse4.1") {
return;
}
assert_simd_counts_bit_cost_matches_scalar(|counts, total| unsafe {
crate::sse::counts_bit_cost_sse41(counts, total)
});
}
#[cfg(all(target_arch = "aarch64", feature = "neon"))]
#[test]
fn neon_counts_bit_cost_matches_scalar() {
assert_simd_counts_bit_cost_matches_scalar(|counts, total| unsafe {
crate::neon::counts_bit_cost_neon(counts, total)
});
}
#[cfg(all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128"))]
#[test]
fn wasm_counts_bit_cost_matches_scalar() {
assert_simd_counts_bit_cost_matches_scalar(|counts, total| {
crate::wasm::counts_bit_cost_wasm(counts, total)
});
}
fn exact_model_cost(histograms: &[Histogram], huffman_pool: &mut Vec<HuffmanNode>) -> f32 {
histograms
.iter()
.filter(|histogram| histogram.total_count != 0)
.map(|histogram| {
exact_counts_bit_cost(&histogram.counts, histogram.total_count, huffman_pool)
+ MIN_DISTANCE_FOR_DISTINCT
})
.sum()
}
fn inputs(n: usize) -> Vec<Histogram> {
(0..n)
.map(|context| {
let mut histogram = Histogram::new();
if context % 11 != 0 {
for symbol in 0..ALPHABET_SIZE {
let count = ((context * 17 + symbol * 13 + context * symbol) % 19) as u32;
histogram.counts[symbol] = count;
histogram.total_count += count;
}
}
histogram
})
.collect()
}
fn assert_fixed_matches_allocating(n: usize, refined: bool) {
let mut expected = inputs(n);
let mut expected_map = Vec::new();
let mut expected_pool = Vec::with_capacity(1024);
cluster_histograms_inner(
&mut expected,
&mut expected_map,
refined,
&mut expected_pool,
);
let mut actual = inputs(n);
let mut actual_map = vec![0; n];
let mut actual_pool = Vec::with_capacity(1024);
let mut scratch = FixedClusterScratch::<221>::default();
let actual_len = cluster_histograms_fixed(
&mut actual,
&mut actual_map,
refined,
&mut scratch,
&mut actual_pool,
);
assert_eq!(actual_len, expected.len());
assert_eq!(actual_map, expected_map);
for (actual, expected) in actual[..actual_len].iter().zip(expected.iter()) {
assert_eq!(actual.total_count, expected.total_count);
assert_eq!(actual.counts, expected.counts);
}
}
#[test]
fn fixed_clustering_matches_allocating_path() {
for n in [0, 1, 2, 7, 64, 65, 128, 221] {
assert_fixed_matches_allocating(n, false);
assert_fixed_matches_allocating(n, true);
}
}
#[test]
fn exact_final_pass_accepts_only_cost_reducing_merge() {
let mut clusters = [
histogram(&[(0, 100), (1, 50), (2, 25)]),
histogram(&[(0, 90), (1, 45), (2, 20)]),
];
let mut symbols = [0, 1];
let mut huffman_pool = Vec::new();
let before = exact_model_cost(&clusters, &mut huffman_pool);
exact_merge_final_clusters(&mut clusters, &mut symbols, &mut huffman_pool);
let after = exact_model_cost(&clusters, &mut huffman_pool);
assert!(after < before);
assert_eq!(symbols, [0, 0]);
assert_eq!(clusters[1].total_count, 0);
}
#[test]
fn exact_final_pass_rejects_cost_increasing_merge() {
let mut clusters = [histogram(&[(0, 100)]), histogram(&[(1, 100)])];
let mut symbols = [0, 1];
let mut huffman_pool = Vec::new();
let before = exact_model_cost(&clusters, &mut huffman_pool);
exact_merge_final_clusters(&mut clusters, &mut symbols, &mut huffman_pool);
let after = exact_model_cost(&clusters, &mut huffman_pool);
assert_eq!(after, before);
assert_eq!(symbols, [0, 1]);
assert_eq!(clusters[0].total_count, 100);
assert_eq!(clusters[1].total_count, 100);
}
}