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); }
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#[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 let element = nnz_data.slice()[i >> 3][i & 7];
92 let log2p = log2total - FastLog2u16(element as u16);
93 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 bits += (18 + 2 * max_depth) as super::util::floatX;
104 bits += BitsEntropy(depth_histo, BROTLI_CODE_LENGTH_CODES);
106 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 let ele = nnz_data_vec[i];
119 let log2p = log2total - FastLog2u16(ele as u16);
120 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 let element = last_vec[i];
139 let log2p = log2total - FastLog2u16(element as u16);
140 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 bits += (18 + 2 * max_depth) as super::util::floatX;
149 bits += BitsEntropy(depth_histo, BROTLI_CODE_LENGTH_CODES);
151 return bits;
153 }
154 let pow2l: v256 = [
155 1.0as 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 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.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 {
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; 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 bits += (18 + 2 * max_depth) as super::util::floatX;
238 bits += BitsEntropy(depth_histo, BROTLI_CODE_LENGTH_CODES);
240 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 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); 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