#![allow(dead_code)]
use super::bit_cost::BrotliPopulationCost;
use super::histogram::{
CostAccessors, HistogramAddHistogram, HistogramClear, HistogramSelfAddHistogram,
};
use super::util::FastLog2;
use alloc::{Allocator, SliceWrapper, SliceWrapperMut};
use core::cmp::min;
#[derive(Clone, Copy)]
pub struct HistogramPair {
pub idx1: u32,
pub idx2: u32,
pub cost_combo: super::util::floatX,
pub cost_diff: super::util::floatX,
}
impl Default for HistogramPair {
#[inline(always)]
fn default() -> HistogramPair {
HistogramPair {
idx1: 0,
idx2: 0,
cost_combo: 0.0 as super::util::floatX,
cost_diff: 0.0 as super::util::floatX,
}
}
}
#[inline(always)]
fn ClusterCostDiff(size_a: usize, size_b: usize) -> super::util::floatX {
let size_c: usize = size_a.wrapping_add(size_b);
size_a as (super::util::floatX) * FastLog2(size_a as u64)
+ size_b as (super::util::floatX) * FastLog2(size_b as u64)
- size_c as (super::util::floatX) * FastLog2(size_c as u64)
}
#[inline(always)]
fn HistogramPairIsLess(p1: &HistogramPair, p2: &HistogramPair) -> bool {
if p1.cost_diff != p2.cost_diff {
p1.cost_diff > p2.cost_diff
} else {
p1.idx2.wrapping_sub(p1.idx1) > p2.idx2.wrapping_sub(p2.idx1)
}
}
fn BrotliCompareAndPushToQueue<
HistogramType: SliceWrapperMut<u32> + SliceWrapper<u32> + CostAccessors + Clone,
>(
out: &[HistogramType],
cluster_size: &[u32],
mut idx1: u32,
mut idx2: u32,
max_num_pairs: usize,
scratch_space: &mut HistogramType::i32vec,
pairs: &mut [HistogramPair],
num_pairs: &mut usize,
) {
let mut is_good_pair: i32 = 0i32;
let mut p: HistogramPair = HistogramPair {
idx1: 0,
idx2: 0,
cost_combo: 0.0,
cost_diff: 0.0,
};
if idx1 == idx2 {
} else {
if idx2 < idx1 {
core::mem::swap(&mut idx2, &mut idx1);
}
p.idx1 = idx1;
p.idx2 = idx2;
p.cost_diff = 0.5 as super::util::floatX
* ClusterCostDiff(
cluster_size[idx1 as usize] as usize,
cluster_size[idx2 as usize] as usize,
);
p.cost_diff -= (out[idx1 as usize]).bit_cost();
p.cost_diff -= (out[idx2 as usize]).bit_cost();
if (out[idx1 as usize]).total_count() == 0usize {
p.cost_combo = (out[idx2 as usize]).bit_cost();
is_good_pair = 1i32;
} else if (out[idx2 as usize]).total_count() == 0usize {
p.cost_combo = (out[idx1 as usize]).bit_cost();
is_good_pair = 1i32;
} else {
let threshold: super::util::floatX = if *num_pairs == 0usize {
1e38 as super::util::floatX
} else {
pairs[0].cost_diff.max(0.0)
};
let mut combo: HistogramType = out[idx1 as usize].clone();
HistogramAddHistogram(&mut combo, &out[idx2 as usize]);
let cost_combo: super::util::floatX = BrotliPopulationCost(&combo, scratch_space);
if cost_combo < threshold - p.cost_diff {
p.cost_combo = cost_combo;
is_good_pair = 1i32;
}
}
if is_good_pair != 0 {
p.cost_diff += p.cost_combo;
if *num_pairs > 0usize && HistogramPairIsLess(&pairs[0], &p) {
if *num_pairs < max_num_pairs {
pairs[*num_pairs] = pairs[0];
*num_pairs = num_pairs.wrapping_add(1);
}
pairs[0] = p;
} else if *num_pairs < max_num_pairs {
pairs[*num_pairs] = p;
*num_pairs = num_pairs.wrapping_add(1);
}
}
}
}
pub fn BrotliHistogramCombine<
HistogramType: SliceWrapperMut<u32> + SliceWrapper<u32> + CostAccessors + Clone,
>(
out: &mut [HistogramType],
cluster_size: &mut [u32],
symbols: &mut [u32],
clusters: &mut [u32],
pairs: &mut [HistogramPair],
mut num_clusters: usize,
symbols_size: usize,
max_clusters: usize,
max_num_pairs: usize,
scratch_space: &mut HistogramType::i32vec,
) -> usize {
let mut cost_diff_threshold: super::util::floatX = 0.0 as super::util::floatX;
let mut min_cluster_size: usize = 1;
let mut num_pairs: usize = 0usize;
{
for idx1 in 0..num_clusters {
for idx2 in idx1 + 1..num_clusters {
BrotliCompareAndPushToQueue(
out,
cluster_size,
clusters[idx1],
clusters[idx2],
max_num_pairs,
scratch_space,
pairs,
&mut num_pairs,
);
}
}
}
while num_clusters > min_cluster_size {
let mut i: usize;
if (pairs[0]).cost_diff >= cost_diff_threshold {
cost_diff_threshold = 1e38 as super::util::floatX;
min_cluster_size = max_clusters;
{
continue;
}
}
let best_idx1: u32 = (pairs[0]).idx1;
let best_idx2: u32 = (pairs[0]).idx2;
HistogramSelfAddHistogram(out, (best_idx1 as usize), (best_idx2 as usize));
(out[(best_idx1 as usize)]).set_bit_cost((pairs[0]).cost_combo);
{
let _rhs = cluster_size[(best_idx2 as usize)];
let _lhs = &mut cluster_size[(best_idx1 as usize)];
*_lhs = (*_lhs).wrapping_add(_rhs);
}
for i in 0usize..symbols_size {
if symbols[i] == best_idx2 {
symbols[i] = best_idx1;
}
}
i = 0usize;
'break9: while i < num_clusters {
{
if clusters[i] == best_idx2 {
for offset in 0..(num_clusters - i - 1) {
clusters[i + offset] = clusters[i + 1 + offset];
}
break 'break9;
}
}
i = i.wrapping_add(1);
}
num_clusters = num_clusters.wrapping_sub(1);
{
let mut copy_to_idx: usize = 0usize;
i = 0usize;
while i < num_pairs {
'continue12: loop {
{
let p: HistogramPair = pairs[i];
if (p).idx1 == best_idx1
|| (p).idx2 == best_idx1
|| (p).idx1 == best_idx2
|| (p).idx2 == best_idx2
{
break 'continue12;
}
if HistogramPairIsLess(&pairs[0], &p) {
let front: HistogramPair = pairs[0];
pairs[0] = p;
pairs[copy_to_idx] = front;
} else {
pairs[copy_to_idx] = p;
}
copy_to_idx = copy_to_idx.wrapping_add(1);
}
break;
}
i = i.wrapping_add(1);
}
num_pairs = copy_to_idx;
}
for i in 0usize..num_clusters {
BrotliCompareAndPushToQueue(
out,
cluster_size,
best_idx1,
clusters[i],
max_num_pairs,
scratch_space,
pairs,
&mut num_pairs,
);
}
}
num_clusters
}
#[inline(always)]
pub fn BrotliHistogramBitCostDistance<
HistogramType: SliceWrapperMut<u32> + SliceWrapper<u32> + CostAccessors + Clone,
>(
histogram: &HistogramType,
candidate: &HistogramType,
scratch_space: &mut HistogramType::i32vec,
) -> super::util::floatX {
if histogram.total_count() == 0usize {
0.0 as super::util::floatX
} else {
let mut tmp: HistogramType = histogram.clone();
HistogramAddHistogram(&mut tmp, candidate);
BrotliPopulationCost(&tmp, scratch_space) - candidate.bit_cost()
}
}
pub fn BrotliHistogramRemap<
HistogramType: SliceWrapperMut<u32> + SliceWrapper<u32> + CostAccessors + Clone,
>(
inp: &[HistogramType],
in_size: usize,
clusters: &[u32],
num_clusters: usize,
scratch_space: &mut HistogramType::i32vec,
out: &mut [HistogramType],
symbols: &mut [u32],
) {
for i in 0usize..in_size {
let mut best_out: u32 = if i == 0usize {
symbols[0]
} else {
symbols[i.wrapping_sub(1)]
};
let mut best_bits: super::util::floatX =
BrotliHistogramBitCostDistance(&inp[i], &mut out[(best_out as usize)], scratch_space);
for j in 0usize..num_clusters {
let cur_bits: super::util::floatX = BrotliHistogramBitCostDistance(
&inp[i],
&mut out[(clusters[j] as usize)],
scratch_space,
);
if cur_bits < best_bits {
best_bits = cur_bits;
best_out = clusters[j];
}
}
symbols[i] = best_out;
}
for i in 0usize..num_clusters {
HistogramClear(&mut out[(clusters[i] as usize)]);
}
for i in 0usize..in_size {
HistogramAddHistogram(&mut out[(symbols[i] as usize)], &inp[i]);
}
}
pub fn BrotliHistogramReindex<
HistogramType: SliceWrapperMut<u32> + SliceWrapper<u32> + CostAccessors + Clone,
Alloc: alloc::Allocator<u32> + alloc::Allocator<HistogramType>,
>(
alloc: &mut Alloc,
out: &mut [HistogramType],
symbols: &mut [u32],
length: usize,
) -> usize {
static kInvalidIndex: u32 = !(0u32);
let mut new_index = if length != 0 {
<Alloc as Allocator<u32>>::alloc_cell(alloc, length)
} else {
<Alloc as Allocator<u32>>::AllocatedMemory::default()
};
let mut next_index: u32;
let mut tmp: <Alloc as Allocator<HistogramType>>::AllocatedMemory;
for i in 0usize..length {
new_index.slice_mut()[i] = kInvalidIndex;
}
next_index = 0u32;
for i in 0usize..length {
if new_index.slice()[(symbols[i] as usize)] == kInvalidIndex {
new_index.slice_mut()[(symbols[i] as usize)] = next_index;
next_index = next_index.wrapping_add(1);
}
}
tmp = if next_index != 0 {
<Alloc as Allocator<HistogramType>>::alloc_cell(alloc, next_index as usize)
} else {
<Alloc as Allocator<HistogramType>>::AllocatedMemory::default()
};
next_index = 0u32;
for i in 0usize..length {
if new_index.slice()[(symbols[i] as usize)] == next_index {
tmp.slice_mut()[(next_index as usize)] = out[(symbols[i] as usize)].clone();
next_index = next_index.wrapping_add(1);
}
symbols[i] = new_index.slice()[(symbols[i] as usize)];
}
{
<Alloc as Allocator<u32>>::free_cell(alloc, new_index);
}
for i in 0usize..next_index as usize {
out[i] = tmp.slice()[i].clone();
}
{
<Alloc as Allocator<HistogramType>>::free_cell(alloc, tmp)
}
next_index as usize
}
pub fn BrotliClusterHistograms<
HistogramType: SliceWrapperMut<u32> + SliceWrapper<u32> + CostAccessors + Clone,
Alloc: alloc::Allocator<u32> + alloc::Allocator<HistogramPair> + alloc::Allocator<HistogramType>,
>(
alloc: &mut Alloc,
inp: &[HistogramType],
in_size: usize,
max_histograms: usize,
scratch_space: &mut HistogramType::i32vec,
out: &mut [HistogramType],
out_size: &mut usize,
histogram_symbols: &mut [u32],
) {
let mut cluster_size = if in_size != 0 {
<Alloc as Allocator<u32>>::alloc_cell(alloc, in_size)
} else {
<Alloc as Allocator<u32>>::AllocatedMemory::default()
};
let mut clusters = if in_size != 0 {
<Alloc as Allocator<u32>>::alloc_cell(alloc, in_size)
} else {
<Alloc as Allocator<u32>>::AllocatedMemory::default()
};
let mut num_clusters: usize = 0usize;
let max_input_histograms: usize = 64usize;
let pairs_capacity: usize = max_input_histograms
.wrapping_mul(max_input_histograms)
.wrapping_div(2);
let mut pairs =
<Alloc as Allocator<HistogramPair>>::alloc_cell(alloc, pairs_capacity.wrapping_add(1));
let mut i: usize;
for i in 0usize..in_size {
cluster_size.slice_mut()[i] = 1u32;
}
for i in 0usize..in_size {
out[i] = inp[i].clone();
(out[i]).set_bit_cost(BrotliPopulationCost(&inp[i], scratch_space));
histogram_symbols[i] = i as u32;
}
i = 0usize;
while i < in_size {
{
let num_to_combine: usize = min(in_size.wrapping_sub(i), max_input_histograms);
for j in 0usize..num_to_combine {
clusters.slice_mut()[num_clusters.wrapping_add(j)] = i.wrapping_add(j) as u32;
}
let num_new_clusters: usize = BrotliHistogramCombine(
out,
cluster_size.slice_mut(),
&mut histogram_symbols[i..],
&mut clusters.slice_mut()[num_clusters..],
pairs.slice_mut(),
num_to_combine,
num_to_combine,
max_histograms,
pairs_capacity,
scratch_space,
);
num_clusters = num_clusters.wrapping_add(num_new_clusters);
}
i = i.wrapping_add(max_input_histograms);
}
{
let max_num_pairs: usize = min(
(64usize).wrapping_mul(num_clusters),
num_clusters.wrapping_div(2).wrapping_mul(num_clusters),
);
{
if pairs_capacity < max_num_pairs.wrapping_add(1) {
let mut _new_size: usize = if pairs_capacity == 0usize {
max_num_pairs.wrapping_add(1)
} else {
pairs_capacity
};
let mut new_array: <Alloc as Allocator<HistogramPair>>::AllocatedMemory;
while _new_size < max_num_pairs.wrapping_add(1) {
_new_size = _new_size.wrapping_mul(2);
}
new_array = if _new_size != 0 {
<Alloc as Allocator<HistogramPair>>::alloc_cell(alloc, _new_size)
} else {
<Alloc as Allocator<HistogramPair>>::AllocatedMemory::default()
};
new_array.slice_mut()[..pairs_capacity]
.clone_from_slice(&pairs.slice()[..pairs_capacity]);
<Alloc as Allocator<HistogramPair>>::free_cell(
alloc,
core::mem::replace(&mut pairs, new_array),
);
}
}
num_clusters = BrotliHistogramCombine(
out,
cluster_size.slice_mut(),
histogram_symbols,
clusters.slice_mut(),
pairs.slice_mut(),
num_clusters,
in_size,
max_histograms,
max_num_pairs,
scratch_space,
);
}
<Alloc as Allocator<HistogramPair>>::free_cell(alloc, pairs);
<Alloc as Allocator<u32>>::free_cell(alloc, cluster_size);
BrotliHistogramRemap(
inp,
in_size,
clusters.slice(),
num_clusters,
scratch_space,
out,
histogram_symbols,
);
<Alloc as Allocator<u32>>::free_cell(alloc, clusters);
*out_size = BrotliHistogramReindex(alloc, out, histogram_symbols, in_size);
}