brotli/enc/
bit_cost.rs

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

brotli/enc/
bit_cost.rs
