brotli/enc/
bit_cost.rs

1#![allow(dead_code)]
2use super::super::alloc::SliceWrapper;
3use super::histogram::CostAccessors;
4use core;
5#[cfg(feature = "simd")]
6use core::simd::prelude::SimdPartialOrd;
7
8use super::util::{brotli_max_uint32_t, floatX, FastLog2, FastLog2u16};
9use super::vectorization::{cast_f32_to_i32, cast_i32_to_f32, log2i, sum8, v256, v256i, Mem256i};
10
11static kCopyBase: [u32; 24] = [
12    2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18, 22, 30, 38, 54, 70, 102, 134, 198, 326, 582, 1094, 2118,
13];
14
15static kCopyExtra: [u32; 24] = [
16    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 24,
17];
18
19static kBrotliMinWindowBits: i32 = 10i32;
20
21static kBrotliMaxWindowBits: i32 = 24i32;
22
23pub fn ShannonEntropy(
24    mut population: &[u32],
25    size: usize,
26    total: &mut usize,
27) -> super::util::floatX {
28    let mut sum: usize = 0usize;
29    let mut retval: super::util::floatX = 0i32 as super::util::floatX;
30    let mut p: usize;
31    if size & 1 != 0 && !population.is_empty() {
32        p = population[0] as usize;
33        population = population.split_at(1).1;
34        sum = sum.wrapping_add(p);
35        retval -= p as super::util::floatX * FastLog2u16(p as u16);
36    }
37    for pop_iter in population.split_at((size >> 1) << 1).0 {
38        p = *pop_iter as usize;
39        sum = sum.wrapping_add(p);
40        retval -= p as super::util::floatX * FastLog2u16(p as u16);
41    }
42    if sum != 0 {
43        retval += sum as super::util::floatX * FastLog2(sum as u64); // not sure it's 16 bit
44    }
45    *total = sum;
46    retval
47}
48
49#[inline(always)]
50pub fn BitsEntropy(population: &[u32], size: usize) -> super::util::floatX {
51    let mut sum: usize = 0;
52    let mut retval: super::util::floatX = ShannonEntropy(population, size, &mut sum);
53    if retval < sum as super::util::floatX {
54        retval = sum as super::util::floatX;
55    }
56    retval
57}
58
59const BROTLI_REPEAT_ZERO_CODE_LENGTH: usize = 17;
60const BROTLI_CODE_LENGTH_CODES: usize = BROTLI_REPEAT_ZERO_CODE_LENGTH + 1;
61/*
62use std::io::{self, Error, ErrorKind, Read, Write};
63
64macro_rules! println_stderr(
65    ($($val:tt)*) => { {
66        writeln!(&mut ::std::io::stderr(), $($val)*).unwrap();
67    } }
68);
69*/
70
71#[cfg(feature = "vector_scratch_space")]
72const vectorize_population_cost: bool = true;
73
74#[cfg(not(feature = "vector_scratch_space"))]
75const vectorize_population_cost: bool = false;
76
77#[allow(clippy::excessive_precision)]
78fn CostComputation<T: SliceWrapper<Mem256i>>(
79    depth_histo: &mut [u32; BROTLI_CODE_LENGTH_CODES],
80    nnz_data: &T,
81    nnz: usize,
82    total_count: super::util::floatX,
83    log2total: super::util::floatX,
84) -> super::util::floatX {
85    let mut bits: super::util::floatX = 0.0 as super::util::floatX;
86    if true {
87        let mut max_depth: usize = 1;
88        for i in 0..nnz {
89            // Compute -log2(P(symbol)) = -log2(count(symbol)/total_count) =
90            //                            = log2(total_count) - log2(count(symbol))
91            let element = nnz_data.slice()[i >> 3][i & 7];
92            let log2p = log2total - FastLog2u16(element as u16);
93            // Approximate the bit depth by round(-log2(P(symbol)))
94            let depth = core::cmp::min((log2p + 0.5) as u8, 15u8);
95            bits += element as super::util::floatX * log2p;
96            if (depth as usize > max_depth) {
97                max_depth = depth as usize;
98            }
99            depth_histo[depth as usize] += 1;
100        }
101
102        // Add the estimated encoding cost of the code length code histogram.
103        bits += (18 + 2 * max_depth) as super::util::floatX;
104        // Add the entropy of the code length code histogram.
105        bits += BitsEntropy(depth_histo, BROTLI_CODE_LENGTH_CODES);
106        //println_stderr!("{:?} {:?}", &depth_histo[..], bits);
107        return bits;
108    }
109    let rem = nnz & 7;
110    let nnz_srl_3 = nnz >> 3;
111    if true {
112        let mut vec_max_depth: [i32; 8] = [1; 8];
113        let mut depth_histo_vec = [[0i32; BROTLI_CODE_LENGTH_CODES]; 8];
114        for nnz_data_vec in nnz_data.slice().split_at(nnz_srl_3).0.iter() {
115            for i in 0..8 {
116                // Compute -log2(P(symbol)) = -log2(count(symbol)/total_count) =
117                //                            = log2(total_count) - log2(count(symbol))
118                let ele = nnz_data_vec[i];
119                let log2p = log2total - FastLog2u16(ele as u16);
120                // Approximate the bit depth by round(-log2(P(symbol)))
121                let depth = core::cmp::min((log2p + 0.5) as i32, 15) as i32;
122                bits += ele as super::util::floatX * log2p;
123                vec_max_depth[i] = core::cmp::max(vec_max_depth[i], depth);
124                depth_histo_vec[i][depth as usize] += 1;
125            }
126        }
127        let mut max_depth = vec_max_depth[7];
128        for i in 0..8 {
129            for j in 0..BROTLI_CODE_LENGTH_CODES {
130                depth_histo[j] += depth_histo_vec[i][j] as u32;
131            }
132            max_depth = core::cmp::max(vec_max_depth[i], max_depth);
133        }
134        if rem != 0 {
135            let last_vec = nnz_data.slice()[nnz_srl_3];
136            for i in 0..rem {
137                // remainder won't have last element for sure
138                let element = last_vec[i];
139                let log2p = log2total - FastLog2u16(element as u16);
140                // Approximate the bit depth by round(-log2(P(symbol)))
141                let depth = core::cmp::min((log2p + 0.5) as i32, 15);
142                bits += element as super::util::floatX * log2p;
143                max_depth = core::cmp::max(depth, max_depth);
144                depth_histo[depth as usize] += 1;
145            }
146        }
147        // Add the estimated encoding cost of the code length code histogram.
148        bits += (18 + 2 * max_depth) as super::util::floatX;
149        // Add the entropy of the code length code histogram.
150        bits += BitsEntropy(depth_histo, BROTLI_CODE_LENGTH_CODES);
151        //println_stderr!("{:?} {:?}", &depth_histo[..], bits);
152        return bits;
153    }
154    let pow2l: v256 = [
155        1.0/*0.7071067811865476*/ as floatX,
156        0.3535533905932738 as floatX,
157        0.1767766952966369 as floatX,
158        0.0883883476483184 as floatX,
159        0.0441941738241592 as floatX,
160        0.0220970869120796 as floatX,
161        0.0110485434560398 as floatX,
162        0.0055242717280199 as floatX,
163    ]
164    .into();
165    let pow2h: v256 = [
166        //FIXME: setr
167        0.0027621358640100 as floatX,
168        0.0013810679320050 as floatX,
169        0.0006905339660025 as floatX,
170        0.0003452669830012 as floatX,
171        0.0001726334915006 as floatX,
172        0.0000863167457503 as floatX,
173        0.0000431583728752 as floatX,
174        /*0.0000215791864376f*/ 0.0 as floatX,
175    ]
176    .into();
177    let ymm_tc = v256::splat(total_count as floatX);
178    let search_depthl = cast_f32_to_i32(pow2l * ymm_tc);
179    let search_depthh = cast_f32_to_i32(pow2h * ymm_tc);
180    let mut suml = v256i::splat(0);
181    let mut sumh = v256i::splat(0);
182    for nnz_data_vec in nnz_data.slice().split_at(nnz_srl_3).0.iter() {
183        for sub_data_item_index in 0..8 {
184            let count = v256i::splat(nnz_data_vec[sub_data_item_index]);
185            let cmpl: v256i = count.simd_gt(search_depthl).to_int();
186            let cmph: v256i = count.simd_gt(search_depthh).to_int();
187            suml = suml + cmpl;
188            sumh = sumh + cmph;
189        }
190    }
191    if rem != 0 {
192        let last_element = nnz_data.slice()[nnz >> 3];
193        for sub_index in 0..rem {
194            let count = v256i::splat(last_element[sub_index & 7]);
195            let cmpl: v256i = count.simd_gt(search_depthl).to_int();
196            let cmph: v256i = count.simd_gt(search_depthh).to_int();
197            suml = suml + cmpl;
198            sumh = sumh + cmph;
199        }
200    }
201    let mut max_depth: usize = 1;
202    // Deal with depth_histo and max_depth
203    {
204        let cumulative_sum: [Mem256i; 2] = [suml, sumh];
205        let mut prev = cumulative_sum[0][0];
206        for j in 1..16 {
207            let cur = cumulative_sum[(j & 8) >> 3][j & 7];
208            let delta = cur - prev;
209            prev = cur;
210            let cur = &mut depth_histo[j];
211            *cur = (*cur as i32 + delta) as u32; // depth_histo[j] += delta
212            if delta != 0 {
213                max_depth = j;
214            }
215        }
216    }
217    let ymm_log2total = v256::splat(log2total);
218    let mut bits_cumulative = v256::splat(0.0 as floatX);
219    for nnz_data_item in nnz_data.slice().split_at(nnz_srl_3).0.iter() {
220        let counts = cast_i32_to_f32(*nnz_data_item);
221        let log_counts = log2i(*nnz_data_item);
222        let log2p = ymm_log2total - log_counts;
223        let tmp = counts * log2p;
224        bits_cumulative += tmp;
225    }
226    bits += sum8(bits_cumulative);
227    if rem != 0 {
228        let last_vec = nnz_data.slice()[nnz_srl_3];
229        for i in 0..rem {
230            let last_item = last_vec[i];
231            let log2p = log2total - FastLog2u16(last_item as u16);
232            bits += last_item as super::util::floatX * log2p;
233        }
234    }
235
236    // Add the estimated encoding cost of the code length code histogram.
237    bits += (18 + 2 * max_depth) as super::util::floatX;
238    // Add the entropy of the code length code histogram.
239    bits += BitsEntropy(depth_histo, BROTLI_CODE_LENGTH_CODES);
240    //println_stderr!("{:?} {:?}", depth_histo, bits);
241    bits
242}
243use alloc::SliceWrapperMut;
244
245pub fn BrotliPopulationCost<HistogramType: SliceWrapper<u32> + CostAccessors>(
246    histogram: &HistogramType,
247    nnz_data: &mut HistogramType::i32vec,
248) -> super::util::floatX {
249    static kOneSymbolHistogramCost: super::util::floatX = 12i32 as super::util::floatX;
250    static kTwoSymbolHistogramCost: super::util::floatX = 20i32 as super::util::floatX;
251    static kThreeSymbolHistogramCost: super::util::floatX = 28i32 as super::util::floatX;
252    static kFourSymbolHistogramCost: super::util::floatX = 37i32 as super::util::floatX;
253    let data_size: usize = histogram.slice().len();
254    let mut count: i32 = 0i32;
255    let mut s: [usize; 5] = [0; 5];
256
257    let mut bits: super::util::floatX = 0.0 as super::util::floatX;
258    let mut i: usize;
259    if histogram.total_count() == 0usize {
260        return kOneSymbolHistogramCost;
261    }
262    i = 0usize;
263    'break1: while i < data_size {
264        {
265            if histogram.slice()[i] > 0u32 {
266                s[count as usize] = i;
267                count += 1;
268                if count > 4i32 {
269                    {
270                        break 'break1;
271                    }
272                }
273            }
274        }
275        i = i.wrapping_add(1);
276    }
277    if count == 1i32 {
278        return kOneSymbolHistogramCost;
279    }
280    if count == 2i32 {
281        return kTwoSymbolHistogramCost + histogram.total_count() as super::util::floatX;
282    }
283    if count == 3i32 {
284        let histo0: u32 = histogram.slice()[s[0]];
285        let histo1: u32 = histogram.slice()[s[1]];
286        let histo2: u32 = histogram.slice()[s[2]];
287        let histomax: u32 = brotli_max_uint32_t(histo0, brotli_max_uint32_t(histo1, histo2));
288        return kThreeSymbolHistogramCost
289            + (2u32).wrapping_mul(histo0.wrapping_add(histo1).wrapping_add(histo2))
290                as super::util::floatX
291            - histomax as super::util::floatX;
292    }
293    if count == 4i32 {
294        let mut histo: [u32; 4] = [0; 4];
295
296        i = 0usize;
297        while i < 4usize {
298            {
299                histo[i] = histogram.slice()[s[i]];
300            }
301            i = i.wrapping_add(1);
302        }
303        i = 0usize;
304        while i < 4usize {
305            {
306                let mut j: usize;
307                j = i.wrapping_add(1);
308                while j < 4usize {
309                    {
310                        if histo[j] > histo[i] {
311                            histo.swap(j, i);
312                        }
313                    }
314                    j = j.wrapping_add(1);
315                }
316            }
317            i = i.wrapping_add(1);
318        }
319        let h23: u32 = histo[2].wrapping_add(histo[3]);
320        let histomax: u32 = brotli_max_uint32_t(h23, histo[0]);
321        return kFourSymbolHistogramCost
322            + (3u32).wrapping_mul(h23) as super::util::floatX
323            + (2u32).wrapping_mul(histo[0].wrapping_add(histo[1])) as super::util::floatX
324            - histomax as super::util::floatX;
325    }
326    if vectorize_population_cost {
327        // vectorization failed: it's faster to do things inline than split into two loops
328        let mut nnz: usize = 0;
329        let mut depth_histo = [0u32; 18];
330        let total_count = histogram.total_count() as super::util::floatX;
331        let log2total = FastLog2(histogram.total_count() as u64);
332        i = 0usize;
333        while i < data_size {
334            if histogram.slice()[i] > 0u32 {
335                let nnz_val = &mut nnz_data.slice_mut()[nnz >> 3];
336                nnz_val[nnz & 7] = histogram.slice()[i] as i32;
337                i += 1;
338                nnz += 1;
339            } else {
340                let mut reps: u32 = 1;
341                for hd in histogram.slice()[i + 1..data_size].iter() {
342                    if *hd != 0 {
343                        break;
344                    }
345                    reps += 1
346                }
347                i += reps as usize;
348                if i == data_size {
349                    {
350                        break;
351                    }
352                }
353                if reps < 3 {
354                    depth_histo[0] += reps
355                } else {
356                    reps -= 2;
357                    let mut depth_histo_adds: u32 = 0;
358                    while reps > 0u32 {
359                        depth_histo_adds += 1;
360                        bits += 3i32 as super::util::floatX;
361                        reps >>= 3i32;
362                    }
363                    depth_histo[BROTLI_REPEAT_ZERO_CODE_LENGTH] += depth_histo_adds;
364                }
365            }
366        }
367        bits += CostComputation(&mut depth_histo, nnz_data, nnz, total_count, log2total);
368    } else {
369        let mut max_depth: usize = 1;
370        let mut depth_histo = [0u32; 18];
371        let log2total: super::util::floatX = FastLog2(histogram.total_count() as u64); // 64 bit here
372        let mut reps: u32 = 0;
373        for histo in histogram.slice()[..data_size].iter() {
374            if *histo != 0 {
375                if reps != 0 {
376                    if reps < 3 {
377                        depth_histo[0] += reps;
378                    } else {
379                        reps -= 2;
380                        while reps > 0u32 {
381                            depth_histo[17] += 1;
382                            bits += 3 as super::util::floatX;
383                            reps >>= 3;
384                        }
385                    }
386                    reps = 0;
387                }
388                let log2p: super::util::floatX = log2total - FastLog2u16(*histo as u16);
389                let mut depth: usize = (log2p + 0.5 as super::util::floatX) as usize;
390                bits += *histo as super::util::floatX * log2p;
391                depth = core::cmp::min(depth, 15);
392                max_depth = core::cmp::max(depth, max_depth);
393                depth_histo[depth] += 1;
394            } else {
395                reps += 1;
396            }
397        }
398        bits += (18usize).wrapping_add((2usize).wrapping_mul(max_depth)) as super::util::floatX;
399        bits += BitsEntropy(&depth_histo[..], 18usize);
400    }
401    bits
402}
403/*
404fn HistogramDataSizeCommand() -> usize {
405    704usize
406}*/
407
408/*
409fn HistogramDataSizeDistance() -> usize {
410    520usize
411}
412*/