brotli/enc/
bit_cost.rs

Help
1use alloc::SliceWrapperMut;
2use core::cmp::{max, min};
3
4use super::super::alloc::SliceWrapper;
5use super::histogram::CostAccessors;
6use super::util::{FastLog2, FastLog2u16};
7use super::vectorization::Mem256i;
8use crate::enc::floatX;
9
10const BROTLI_REPEAT_ZERO_CODE_LENGTH: usize = 17;
11const BROTLI_CODE_LENGTH_CODES: usize = BROTLI_REPEAT_ZERO_CODE_LENGTH + 1;
12
13#[deprecated(note = "use shannon_entropy instead")]
14pub fn ShannonEntropy(population: &[u32], size: usize, total: &mut usize) -> floatX {
15    let (result, tot) = shannon_entropy(population, size);
16    *total = tot;
17    result
18}
19
20pub(crate) fn shannon_entropy(mut population: &[u32], size: usize) -> (floatX, usize) {
21    let mut sum: usize = 0;
22    let mut retval: floatX = 0.0;
23
24    if (size & 1) != 0 && !population.is_empty() {
25        let p = population[0] as usize;
26        population = population.split_at(1).1;
27        sum = sum.wrapping_add(p);
28        retval -= p as floatX * FastLog2u16(p as u16);
29    }
30    for pop_iter in population.split_at((size >> 1) << 1).0 {
31        let p = *pop_iter as usize;
32        sum = sum.wrapping_add(p);
33        retval -= p as floatX * FastLog2u16(p as u16);
34    }
35    if sum != 0 {
36        retval += sum as floatX * FastLog2(sum as u64); // not sure it's 16 bit
37    }
38
39    (retval, sum)
40}
41
42#[inline(always)]
43pub fn BitsEntropy(population: &[u32], size: usize) -> floatX {
44    let (mut retval, sum) = shannon_entropy(population, size);
45    if retval < sum as floatX {
46        retval = sum as floatX;
47    }
48    retval
49}
50
51#[allow(clippy::excessive_precision)]
52fn CostComputation<T: SliceWrapper<Mem256i>>(
53    depth_histo: &mut [u32; BROTLI_CODE_LENGTH_CODES],
54    nnz_data: &T,
55    nnz: usize,
56    _total_count: floatX,
57    log2total: floatX,
58) -> floatX {
59    let mut bits: floatX = 0.0;
60    let mut max_depth: usize = 1;
61    for i in 0..nnz {
62        // Compute -log2(P(symbol)) = -log2(count(symbol)/total_count) =
63        //                            = log2(total_count) - log2(count(symbol))
64        let element = nnz_data.slice()[i >> 3][i & 7];
65        let log2p = log2total - FastLog2u16(element as u16);
66        // Approximate the bit depth by round(-log2(P(symbol)))
67        let depth = min((log2p + 0.5) as u8, 15u8);
68        bits += (element as floatX) * log2p;
69        if (depth as usize) > max_depth {
70            max_depth = depth as usize;
71        }
72        depth_histo[depth as usize] += 1;
73    }
74
75    // Add the estimated encoding cost of the code length code histogram.
76    bits += (18 + 2 * max_depth) as floatX;
77    // Add the entropy of the code length code histogram.
78    bits += BitsEntropy(depth_histo, BROTLI_CODE_LENGTH_CODES);
79    //println_stderr!("{:?} {:?}", &depth_histo[..], bits);
80    bits
81}
82
83pub fn BrotliPopulationCost<HistogramType: SliceWrapper<u32> + CostAccessors>(
84    histogram: &HistogramType,
85    nnz_data: &mut HistogramType::i32vec,
86) -> floatX {
87    static kOneSymbolHistogramCost: floatX = 12.0;
88    static kTwoSymbolHistogramCost: floatX = 20.0;
89    static kThreeSymbolHistogramCost: floatX = 28.0;
90    static kFourSymbolHistogramCost: floatX = 37.0;
91
92    let data_size: usize = histogram.slice().len();
93    let mut count = 0;
94    let mut s: [usize; 5] = [0; 5];
95    let mut bits: floatX = 0.0;
96
97    if histogram.total_count() == 0 {
98        return kOneSymbolHistogramCost;
99    }
100    for i in 0..data_size {
101        if histogram.slice()[i] > 0 {
102            s[count] = i;
103            count += 1;
104            if count > 4 {
105                break;
106            }
107        }
108    }
109    match count {
110        1 => return kOneSymbolHistogramCost,
111        2 => return kTwoSymbolHistogramCost + histogram.total_count() as floatX,
112        3 => {
113            let histo0: u32 = histogram.slice()[s[0]];
114            let histo1: u32 = histogram.slice()[s[1]];
115            let histo2: u32 = histogram.slice()[s[2]];
116            let histomax: u32 = max(histo0, max(histo1, histo2));
117            return kThreeSymbolHistogramCost
118                + (2u32).wrapping_mul(histo0.wrapping_add(histo1).wrapping_add(histo2)) as floatX
119                - histomax as floatX;
120        }
121        4 => {
122            let mut histo: [u32; 4] = [0; 4];
123
124            for i in 0..4 {
125                histo[i] = histogram.slice()[s[i]];
126            }
127            for i in 0..4 {
128                for j in i + 1..4 {
129                    if histo[j] > histo[i] {
130                        histo.swap(j, i);
131                    }
132                }
133            }
134            let h23: u32 = histo[2].wrapping_add(histo[3]);
135            let histomax: u32 = max(h23, histo[0]);
136            return kFourSymbolHistogramCost
137                + (3u32).wrapping_mul(h23) as floatX
138                + (2u32).wrapping_mul(histo[0].wrapping_add(histo[1])) as floatX
139                - histomax as floatX;
140        }
141        _ => {}
142    }
143
144    if cfg!(feature = "vector_scratch_space") {
145        // vectorization failed: it's faster to do things inline than split into two loops
146        let mut nnz: usize = 0;
147        let mut depth_histo = [0u32; 18];
148        let total_count = histogram.total_count() as floatX;
149        let log2total = FastLog2(histogram.total_count() as u64);
150        let mut i: usize = 0;
151        while i < data_size {
152            if histogram.slice()[i] > 0 {
153                let nnz_val = &mut nnz_data.slice_mut()[nnz >> 3];
154                nnz_val[nnz & 7] = histogram.slice()[i] as i32;
155                i += 1;
156                nnz += 1;
157            } else {
158                let mut reps: u32 = 1;
159                for hd in histogram.slice()[i + 1..data_size].iter() {
160                    if *hd != 0 {
161                        break;
162                    }
163                    reps += 1
164                }
165                i += reps as usize;
166                if i == data_size {
167                    break;
168                }
169                if reps < 3 {
170                    depth_histo[0] += reps;
171                } else {
172                    reps -= 2;
173                    let mut depth_histo_adds: u32 = 0;
174                    while reps > 0 {
175                        depth_histo_adds += 1;
176                        bits += 3.0;
177                        reps >>= 3;
178                    }
179                    depth_histo[BROTLI_REPEAT_ZERO_CODE_LENGTH] += depth_histo_adds;
180                }
181            }
182        }
183        bits += CostComputation(&mut depth_histo, nnz_data, nnz, total_count, log2total);
184    } else {
185        let mut max_depth: usize = 1;
186        let mut depth_histo = [0u32; 18];
187        let log2total: floatX = FastLog2(histogram.total_count() as u64); // 64 bit here
188        let mut reps: u32 = 0;
189        for histo in histogram.slice()[..data_size].iter() {
190            if *histo != 0 {
191                if reps != 0 {
192                    if reps < 3 {
193                        depth_histo[0] += reps;
194                    } else {
195                        reps -= 2;
196                        while reps > 0 {
197                            depth_histo[17] += 1;
198                            bits += 3.0;
199                            reps >>= 3;
200                        }
201                    }
202                    reps = 0;
203                }
204                let log2p = log2total - FastLog2u16(*histo as u16);
205                let mut depth = (log2p + 0.5) as usize;
206                bits += *histo as floatX * log2p;
207                depth = min(depth, 15);
208                max_depth = max(depth, max_depth);
209                depth_histo[depth] += 1;
210            } else {
211                reps += 1;
212            }
213        }
214        bits += (18usize).wrapping_add((2usize).wrapping_mul(max_depth)) as floatX;
215        bits += BitsEntropy(&depth_histo[..], 18);
216    }
217    bits
218}
brotli/enc/bit_cost.rs

brotli/enc/
bit_cost.rs
