brotli/enc/
find_stride.rs

1use super::super::alloc;
2use super::super::alloc::{SliceWrapper, SliceWrapperMut};
3use super::input_pair::{InputPair, InputReference};
4use super::interface;
5use super::util::FastLog2;
6use core::cmp;
7
8use core::ops::{Index, IndexMut, Range};
9// float32 doesn't have enough resolution for blocks of data more than 3.5 megs
10pub type floatY = f64;
11// the cost of storing a particular population of data including the approx
12// cost of a huffman table to describe the frequencies of each symbol
13pub fn HuffmanCost(population: &[u32]) -> floatY {
14    assert_eq!(population.len(), 256 * 256);
15    let mut cost: floatY = 0.0 as floatY;
16    let mut sum: floatY = 0.0 as floatY;
17    let mut buckets: floatY = 0.0 as floatY;
18    for pop in population.iter() {
19        if *pop == 0 {
20            continue;
21        }
22        cost -= *pop as floatY * FastLog2(*pop as u64) as floatY;
23        sum += *pop as floatY;
24        buckets += 1.0 as floatY;
25    }
26
27    //println!("Observed {} nonzero buckets with a sum of {}, hc={}", buckets, sum, cost);
28
29    16.0 as floatY * buckets + cost + sum * FastLog2(sum as u64) as floatY
30}
31
32// this holds a population of data assuming 1 byte of prior for that data
33// bucket_populations is therefore a 65536-long dynamically allocated buffer
34pub struct EntropyBucketPopulation<AllocU32: alloc::Allocator<u32>> {
35    pub bucket_populations: AllocU32::AllocatedMemory,
36    pub cached_bit_entropy: floatY,
37}
38impl<AllocU32: alloc::Allocator<u32>> EntropyBucketPopulation<AllocU32> {
39    pub fn new(m32: &mut AllocU32) -> Self {
40        let size = 256 * 256;
41        EntropyBucketPopulation::<AllocU32> {
42            cached_bit_entropy: 0.0,
43            bucket_populations: m32.alloc_cell(size),
44        }
45    }
46    pub fn free(&mut self, m32: &mut AllocU32) {
47        m32.free_cell(core::mem::take(&mut self.bucket_populations));
48    }
49    fn clone_from(&mut self, other: &EntropyBucketPopulation<AllocU32>) {
50        self.bucket_populations
51            .slice_mut()
52            .clone_from_slice(other.bucket_populations.slice());
53    }
54    fn add_assign(&mut self, other: &EntropyBucketPopulation<AllocU32>) {
55        assert_eq!(
56            self.bucket_populations.slice().len(),
57            other.bucket_populations.slice().len()
58        );
59        for (item, other_item) in self
60            .bucket_populations
61            .slice_mut()
62            .iter_mut()
63            .zip(other.bucket_populations.slice().iter())
64        {
65            *item += *other_item;
66        }
67        self.cached_bit_entropy = HuffmanCost(self.bucket_populations.slice());
68    }
69    // clear the allocated memory and reset literal population to zero
70    fn bzero(&mut self) {
71        self.cached_bit_entropy = 0.0;
72        for bp in self.bucket_populations.slice_mut().iter_mut() {
73            *bp = 0;
74        }
75    }
76    // setup population to the sum of an array of populations where the stride of that row matches. Additionally allow another optional
77    fn initiate_from(
78        &mut self,
79        rows: [&[Self]; 2],
80        rows_stride: [&[u8]; 2],
81        stride: u8,
82        do_clear: bool,
83    ) {
84        self.cached_bit_entropy = 0.0;
85        let mut found_any = false;
86        for (sub_row, sub_stride) in rows.iter().zip(rows_stride.iter()) {
87            for (item, istride) in sub_row.iter().zip(sub_stride.iter()) {
88                if *istride != stride {
89                    continue; // if we chain, then optional was already filtered by stride
90                }
91                if do_clear && !found_any {
92                    self.bucket_populations
93                        .slice_mut()
94                        .clone_from_slice(item.bucket_populations.slice());
95                    found_any = true;
96                } else {
97                    for (dst, src) in self
98                        .bucket_populations
99                        .slice_mut()
100                        .iter_mut()
101                        .zip(item.bucket_populations.slice().iter())
102                    {
103                        *dst += *src;
104                    }
105                }
106            }
107        }
108        if do_clear && !found_any {
109            self.bzero();
110        } else {
111            self.cached_bit_entropy = HuffmanCost(self.bucket_populations.slice());
112        }
113    }
114    fn bit_cost_of_data_subset(
115        &mut self,
116        data0: &[u8],
117        mut stride: u8,
118        mut prev_bytes: [u8; NUM_STRIDES],
119        scratch: &mut EntropyBucketPopulation<AllocU32>,
120    ) -> floatY {
121        prev_bytes.reverse();
122        stride = cmp::max(1, stride); // we return stride=1 to mean 1 away
123        scratch
124            .bucket_populations
125            .slice_mut()
126            .clone_from_slice(self.bucket_populations.slice());
127        scratch.bucket_populations.slice_mut()[65535] += 1; // to demonstrate that we have
128        scratch.bucket_populations.slice_mut()[65535] -= 1; // to demonstrate that we have write capability
129        let mut stray_count = 0.0 as floatY;
130        assert_eq!((NUM_STRIDES - 1) & NUM_STRIDES, 0); // must be power of two
131        for (index, val) in data0.iter().enumerate() {
132            let prior_byte =
133                prev_bytes[(index + (NUM_STRIDES - stride as usize)) & (NUM_STRIDES - 1)];
134            let loc = &mut scratch.bucket_populations.slice_mut()
135                [prior_byte as usize * 256 + *val as usize];
136            if *loc == 0 {
137                stray_count += 1.0;
138            } else {
139                *loc -= 1;
140            }
141            prev_bytes[index & (NUM_STRIDES - 1)] = *val;
142        }
143        if self.cached_bit_entropy == 0.0 as floatY {
144            self.cached_bit_entropy = HuffmanCost(self.bucket_populations.slice());
145        }
146        debug_assert_eq!(
147            HuffmanCost(self.bucket_populations.slice()),
148            self.cached_bit_entropy
149        );
150
151        scratch.cached_bit_entropy = HuffmanCost(scratch.bucket_populations.slice());
152        self.cached_bit_entropy - scratch.cached_bit_entropy + stray_count * 8.0
153    }
154}
155
156const NUM_STRIDES: usize = 8;
157#[derive(Copy, Clone)]
158pub struct BucketPopIndex {
159    pub val: u8,
160    pub six_bits: u8,
161    pub stride: u8,
162}
163
164impl<AllocU32: alloc::Allocator<u32>> Index<BucketPopIndex> for EntropyBucketPopulation<AllocU32> {
165    type Output = u32;
166    fn index(&self, index: BucketPopIndex) -> &u32 {
167        &self.bucket_populations.slice()
168            [index.val as usize + index.six_bits as usize * 256 + index.stride as usize * 256 * 64]
169    }
170}
171impl<AllocU32: alloc::Allocator<u32>> IndexMut<BucketPopIndex>
172    for EntropyBucketPopulation<AllocU32>
173{
174    fn index_mut(&mut self, index: BucketPopIndex) -> &mut u32 {
175        &mut self.bucket_populations.slice_mut()
176            [index.val as usize + index.six_bits as usize * 256 + index.stride as usize * 256 * 64]
177    }
178}
179
180pub struct EntropyTally<AllocU32: alloc::Allocator<u32>> {
181    pop: [EntropyBucketPopulation<AllocU32>; NUM_STRIDES],
182}
183
184const NUM_LEVELS: usize = 4;
185const NUM_NODES: usize = (1 << (NUM_LEVELS)) - 1;
186pub const NUM_LEAF_NODES: usize = (NUM_NODES + 1) >> 1;
187
188pub struct EntropyPyramid<AllocU32: alloc::Allocator<u32>> {
189    pop: [EntropyBucketPopulation<AllocU32>; NUM_NODES],
190    stride: [u8; NUM_NODES],
191}
192
193impl<AllocU32: alloc::Allocator<u32>> EntropyPyramid<AllocU32> {
194    pub fn last_level_range(&self) -> Range<usize> {
195        (NUM_NODES - (1 << (NUM_LEVELS - 1)))..NUM_NODES
196    }
197    pub fn byte_index_to_pyramid_index(&self, byte_index: usize, metablock_size: usize) -> usize {
198        let range = self.last_level_range();
199        cmp::min(
200            range.start + (range.end - range.start) * byte_index / metablock_size,
201            range.end - 1,
202        ) // since we tally after the end of the literal block, it could be after the pyramid
203    }
204    pub fn reset_scratch_to_deepest_level(&self, output: &mut EntropyTally<AllocU32>) {
205        let mut has_modified = [false; NUM_STRIDES];
206        //println!("Last level range {:?}", self.last_level_range());
207        for index in self.last_level_range() {
208            if has_modified[self.stride[index] as usize] {
209                output.pop[self.stride[index] as usize].add_assign(&self.pop[index]);
210            } else {
211                output.pop[self.stride[index] as usize].clone_from(&self.pop[index]);
212                has_modified[self.stride[index] as usize] = true;
213            }
214        }
215        for stride in 0..NUM_STRIDES {
216            if !has_modified[stride] {
217                output.pop[stride].bzero();
218                output.pop[stride].cached_bit_entropy = 0.0;
219            } else {
220                output.pop[stride].cached_bit_entropy =
221                    HuffmanCost(output.pop[stride].bucket_populations.slice());
222            }
223            //println!("BASE PYRAMID {} = {}", stride,output.pop[stride].cached_bit_entropy);
224        }
225    }
226    pub fn stride_last_level_range(&self) -> [u8; NUM_LEAF_NODES] {
227        let mut ret = [0u8; NUM_LEAF_NODES];
228        ret.clone_from_slice(self.stride.split_at(self.stride.len() - NUM_LEAF_NODES).1);
229        ret
230    }
231    pub fn free(&mut self, m32: &mut AllocU32) {
232        for item in self.pop.iter_mut() {
233            item.free(m32);
234        }
235    }
236    pub fn disabled_placeholder(_m32: &mut AllocU32) -> Self {
237        EntropyPyramid::<AllocU32> {
238            pop: [
239                EntropyBucketPopulation::<AllocU32> {
240                    cached_bit_entropy: 0.0,
241                    bucket_populations: AllocU32::AllocatedMemory::default(),
242                },
243                EntropyBucketPopulation::<AllocU32> {
244                    cached_bit_entropy: 0.0,
245                    bucket_populations: AllocU32::AllocatedMemory::default(),
246                },
247                EntropyBucketPopulation::<AllocU32> {
248                    cached_bit_entropy: 0.0,
249                    bucket_populations: AllocU32::AllocatedMemory::default(),
250                },
251                EntropyBucketPopulation::<AllocU32> {
252                    cached_bit_entropy: 0.0,
253                    bucket_populations: AllocU32::AllocatedMemory::default(),
254                },
255                EntropyBucketPopulation::<AllocU32> {
256                    cached_bit_entropy: 0.0,
257                    bucket_populations: AllocU32::AllocatedMemory::default(),
258                },
259                EntropyBucketPopulation::<AllocU32> {
260                    cached_bit_entropy: 0.0,
261                    bucket_populations: AllocU32::AllocatedMemory::default(),
262                },
263                EntropyBucketPopulation::<AllocU32> {
264                    cached_bit_entropy: 0.0,
265                    bucket_populations: AllocU32::AllocatedMemory::default(),
266                },
267                EntropyBucketPopulation::<AllocU32> {
268                    cached_bit_entropy: 0.0,
269                    bucket_populations: AllocU32::AllocatedMemory::default(),
270                },
271                EntropyBucketPopulation::<AllocU32> {
272                    cached_bit_entropy: 0.0,
273                    bucket_populations: AllocU32::AllocatedMemory::default(),
274                },
275                EntropyBucketPopulation::<AllocU32> {
276                    cached_bit_entropy: 0.0,
277                    bucket_populations: AllocU32::AllocatedMemory::default(),
278                },
279                EntropyBucketPopulation::<AllocU32> {
280                    cached_bit_entropy: 0.0,
281                    bucket_populations: AllocU32::AllocatedMemory::default(),
282                },
283                EntropyBucketPopulation::<AllocU32> {
284                    cached_bit_entropy: 0.0,
285                    bucket_populations: AllocU32::AllocatedMemory::default(),
286                },
287                EntropyBucketPopulation::<AllocU32> {
288                    cached_bit_entropy: 0.0,
289                    bucket_populations: AllocU32::AllocatedMemory::default(),
290                },
291                EntropyBucketPopulation::<AllocU32> {
292                    cached_bit_entropy: 0.0,
293                    bucket_populations: AllocU32::AllocatedMemory::default(),
294                },
295                EntropyBucketPopulation::<AllocU32> {
296                    cached_bit_entropy: 0.0,
297                    bucket_populations: AllocU32::AllocatedMemory::default(),
298                },
299            ],
300            stride: [0; NUM_NODES],
301        }
302    }
303    pub fn new(m32: &mut AllocU32) -> Self {
304        let size = 256 * 256;
305        EntropyPyramid::<AllocU32> {
306            pop: [
307                EntropyBucketPopulation::<AllocU32> {
308                    cached_bit_entropy: 0.0,
309                    bucket_populations: m32.alloc_cell(size),
310                },
311                EntropyBucketPopulation::<AllocU32> {
312                    cached_bit_entropy: 0.0,
313                    bucket_populations: m32.alloc_cell(size),
314                },
315                EntropyBucketPopulation::<AllocU32> {
316                    cached_bit_entropy: 0.0,
317                    bucket_populations: m32.alloc_cell(size),
318                },
319                EntropyBucketPopulation::<AllocU32> {
320                    cached_bit_entropy: 0.0,
321                    bucket_populations: m32.alloc_cell(size),
322                },
323                EntropyBucketPopulation::<AllocU32> {
324                    cached_bit_entropy: 0.0,
325                    bucket_populations: m32.alloc_cell(size),
326                },
327                EntropyBucketPopulation::<AllocU32> {
328                    cached_bit_entropy: 0.0,
329                    bucket_populations: m32.alloc_cell(size),
330                },
331                EntropyBucketPopulation::<AllocU32> {
332                    cached_bit_entropy: 0.0,
333                    bucket_populations: m32.alloc_cell(size),
334                },
335                EntropyBucketPopulation::<AllocU32> {
336                    cached_bit_entropy: 0.0,
337                    bucket_populations: m32.alloc_cell(size),
338                },
339                EntropyBucketPopulation::<AllocU32> {
340                    cached_bit_entropy: 0.0,
341                    bucket_populations: m32.alloc_cell(size),
342                },
343                EntropyBucketPopulation::<AllocU32> {
344                    cached_bit_entropy: 0.0,
345                    bucket_populations: m32.alloc_cell(size),
346                },
347                EntropyBucketPopulation::<AllocU32> {
348                    cached_bit_entropy: 0.0,
349                    bucket_populations: m32.alloc_cell(size),
350                },
351                EntropyBucketPopulation::<AllocU32> {
352                    cached_bit_entropy: 0.0,
353                    bucket_populations: m32.alloc_cell(size),
354                },
355                EntropyBucketPopulation::<AllocU32> {
356                    cached_bit_entropy: 0.0,
357                    bucket_populations: m32.alloc_cell(size),
358                },
359                EntropyBucketPopulation::<AllocU32> {
360                    cached_bit_entropy: 0.0,
361                    bucket_populations: m32.alloc_cell(size),
362                },
363                EntropyBucketPopulation::<AllocU32> {
364                    cached_bit_entropy: 0.0,
365                    bucket_populations: m32.alloc_cell(size),
366                },
367            ],
368            stride: [0; NUM_NODES],
369        }
370    }
371    pub fn bit_cost_of_literals(
372        &mut self,
373        data0: &[u8],
374        start_index: u32,
375        metablock_len: usize,
376        stride: u8,
377        previous_bytes: [u8; NUM_STRIDES],
378        scratch: &mut EntropyTally<AllocU32>,
379    ) -> floatY {
380        assert!(stride as usize <= NUM_STRIDES);
381
382        self.pop[self.byte_index_to_pyramid_index(start_index as usize, metablock_len)]
383            .bit_cost_of_data_subset(data0, stride, previous_bytes, &mut scratch.pop[0])
384    }
385    fn populate_entry_stride1(&mut self, input: InputPair, index: u32) {
386        let mut prev_val = 0;
387        let pyr_item = &mut self.pop[index as usize];
388        pyr_item.bzero();
389        assert_eq!(pyr_item.bucket_populations.slice()[65535], 0);
390        for val in input.0.slice().iter().chain(input.1.slice().iter()) {
391            pyr_item.bucket_populations.slice_mut()[prev_val as usize * 256 + *val as usize] += 1;
392            prev_val = *val;
393        }
394        pyr_item.cached_bit_entropy = HuffmanCost(pyr_item.bucket_populations.slice());
395        self.stride[index as usize] = 0;
396    }
397    fn populate_entry(
398        &mut self,
399        input: InputPair,
400        scratch: &mut EntropyTally<AllocU32>,
401        index: u32,
402        mirror_range: Option<Range<usize>>,
403        prev_range: Option<Range<usize>>,
404    ) {
405        let mut initial_entropies = [0.0 as floatY; NUM_STRIDES];
406        let nothing: &[EntropyBucketPopulation<AllocU32>] = &[];
407        let nothing_u8: &[u8] = &[];
408        {
409            let pop_ranges = [
410                match mirror_range {
411                    None => nothing,
412                    Some(ref ir) => &self.pop[ir.clone()],
413                },
414                match prev_range {
415                    None => nothing,
416                    Some(ref pr) => &self.pop[pr.clone()],
417                },
418            ];
419            let stride_ranges = [
420                match mirror_range {
421                    None => nothing_u8,
422                    Some(ref ir) => &self.stride[ir.clone()],
423                },
424                match prev_range {
425                    None => nothing_u8,
426                    Some(ref pr) => &self.stride[pr.clone()],
427                },
428            ];
429            for stride in 0..NUM_STRIDES {
430                scratch.pop[stride].initiate_from(pop_ranges, stride_ranges, stride as u8, true);
431                initial_entropies[stride] = scratch.pop[stride].cached_bit_entropy;
432            }
433        }
434        scratch.observe_input_stream(input.0.slice(), input.1.slice());
435        let mut best_entropy_index = 0;
436        let mut min_entropy_value = (scratch.pop[0].cached_bit_entropy - initial_entropies[0]);
437        //println!("{} OLD ENTROPY {:} NEW_ENTROPY {:}", best_entropy_index, scratch.pop[0].cached_bit_entropy, initial_entropies[0]);
438        for stride in 1..NUM_STRIDES {
439            let entropy_value = scratch.pop[stride].cached_bit_entropy - initial_entropies[stride];
440            //println!("{} OLD ENTROPY {:} NEW_ENTROPY {:}", stride, scratch.pop[stride].cached_bit_entropy, initial_entropies[stride]);
441            if entropy_value < min_entropy_value {
442                best_entropy_index = stride;
443                min_entropy_value = entropy_value;
444            }
445        }
446        self.pop[index as usize].clone_from(&scratch.pop[best_entropy_index]);
447        self.stride[index as usize] = best_entropy_index as u8;
448    }
449    pub fn populate_stride1(&mut self, input0: &[u8], input1: &[u8]) {
450        let input = InputPair(
451            InputReference {
452                data: input0,
453                orig_offset: 0,
454            },
455            InputReference {
456                data: input1,
457                orig_offset: input0.len(),
458            },
459        );
460        for i in 0..2 {
461            let first_range = if i == 0 {
462                input.split_at(input.len() >> 1).0
463            } else {
464                input.split_at(input.len() >> 1).1
465            };
466            for j in 0..2 {
467                let second_range = if j == 0 {
468                    first_range.split_at(input.len() >> 2).0
469                } else {
470                    first_range.split_at(input.len() >> 2).1
471                };
472                if NUM_LEVELS == 4 {
473                    for k in 0..2 {
474                        let third_range = if j == 0 {
475                            second_range.split_at(input.len() >> 3).0
476                        } else {
477                            second_range.split_at(input.len() >> 3).1
478                        };
479                        self.populate_entry_stride1(third_range, 7 + ((i << 2) + (j << 1) + k));
480                    }
481                } else {
482                    assert_eq!(NUM_LEVELS, 3); // we hard coded the 3 levels for now... we can add more later or make this into some kind of recursion
483                    self.populate_entry_stride1(second_range, 3 + ((i << 1) + j));
484                }
485            }
486        }
487    }
488    pub fn populate(&mut self, input0: &[u8], input1: &[u8], scratch: &mut EntropyTally<AllocU32>) {
489        let input = InputPair(
490            InputReference {
491                data: input0,
492                orig_offset: 0,
493            },
494            InputReference {
495                data: input1,
496                orig_offset: input0.len(),
497            },
498        );
499        self.populate_entry(input, scratch, 0, None, None); // BASE
500
501        // LEVEL 1
502        self.populate_entry(
503            input.split_at(input.len() >> 1).0,
504            scratch,
505            1,
506            Some(0..1),
507            None,
508        );
509        self.populate_entry(
510            input.split_at(input.len() >> 1).1,
511            scratch,
512            2,
513            None,
514            Some(1..2),
515        ); // should we use the range from 0..1??
516
517        // LEVEL 2
518        self.populate_entry(
519            input.split_at(input.len() >> 2).0,
520            scratch,
521            3,
522            Some(1..3),
523            None,
524        );
525        self.populate_entry(
526            input
527                .split_at(input.len() >> 1)
528                .0
529                .split_at(input.len() >> 2)
530                .1,
531            scratch,
532            4,
533            Some(2..3),
534            Some(3..4),
535        );
536        self.populate_entry(
537            input
538                .split_at(input.len() >> 1)
539                .1
540                .split_at(input.len() >> 2)
541                .0,
542            scratch,
543            5,
544            Some(3..5),
545            None,
546        );
547        self.populate_entry(
548            input
549                .split_at(input.len() >> 1)
550                .1
551                .split_at(input.len() >> 2)
552                .1,
553            scratch,
554            6,
555            Some(3..6),
556            None,
557        );
558        if NUM_LEVELS == 4 {
559            // level 4
560            self.populate_entry(
561                input
562                    .split_at(input.len() >> 1)
563                    .0
564                    .split_at(input.len() >> 2)
565                    .0
566                    .split_at(input.len() >> 3)
567                    .0,
568                scratch,
569                7,
570                Some(4..7),
571                None,
572            );
573            self.populate_entry(
574                input
575                    .split_at(input.len() >> 1)
576                    .0
577                    .split_at(input.len() >> 2)
578                    .0
579                    .split_at(input.len() >> 3)
580                    .1,
581                scratch,
582                8,
583                Some(4..7),
584                Some(7..8),
585            );
586            self.populate_entry(
587                input
588                    .split_at(input.len() >> 1)
589                    .0
590                    .split_at(input.len() >> 2)
591                    .1
592                    .split_at(input.len() >> 3)
593                    .0,
594                scratch,
595                9,
596                Some(5..7),
597                Some(7..9),
598            );
599            self.populate_entry(
600                input
601                    .split_at(input.len() >> 1)
602                    .0
603                    .split_at(input.len() >> 2)
604                    .1
605                    .split_at(input.len() >> 3)
606                    .1,
607                scratch,
608                0xa,
609                Some(5..7),
610                Some(7..0xa),
611            );
612
613            self.populate_entry(
614                input
615                    .split_at(input.len() >> 1)
616                    .1
617                    .split_at(input.len() >> 2)
618                    .0
619                    .split_at(input.len() >> 3)
620                    .0,
621                scratch,
622                0xb,
623                Some(6..7),
624                Some(7..0xb),
625            );
626            self.populate_entry(
627                input
628                    .split_at(input.len() >> 1)
629                    .1
630                    .split_at(input.len() >> 2)
631                    .0
632                    .split_at(input.len() >> 3)
633                    .1,
634                scratch,
635                0xc,
636                Some(6..7),
637                Some(7..0xc),
638            );
639            self.populate_entry(
640                input
641                    .split_at(input.len() >> 1)
642                    .1
643                    .split_at(input.len() >> 2)
644                    .1
645                    .split_at(input.len() >> 3)
646                    .0,
647                scratch,
648                0xd,
649                None,
650                Some(7..0xd),
651            );
652            self.populate_entry(
653                input
654                    .split_at(input.len() >> 1)
655                    .1
656                    .split_at(input.len() >> 2)
657                    .1
658                    .split_at(input.len() >> 3)
659                    .1,
660                scratch,
661                0xe,
662                None,
663                Some(7..0xe),
664            );
665        } else {
666            assert_eq!(NUM_LEVELS, 3); // we hard coded the 3 levels for now... we can add more later or make this into some kind of recursion
667        }
668    }
669}
670
671impl<AllocU32: alloc::Allocator<u32>> EntropyTally<AllocU32> {
672    pub fn new(m32: &mut AllocU32, max_stride_arg: Option<u8>) -> EntropyTally<AllocU32> {
673        let size = 256 * 256;
674        let max_stride = max_stride_arg.unwrap_or(NUM_STRIDES as u8);
675        EntropyTally::<AllocU32> {
676            pop: [
677                EntropyBucketPopulation::<AllocU32> {
678                    cached_bit_entropy: 0.0,
679                    bucket_populations: if 0 < max_stride {
680                        m32.alloc_cell(size)
681                    } else {
682                        AllocU32::AllocatedMemory::default()
683                    },
684                },
685                EntropyBucketPopulation::<AllocU32> {
686                    cached_bit_entropy: 0.0,
687                    bucket_populations: if 1 < max_stride {
688                        m32.alloc_cell(size)
689                    } else {
690                        AllocU32::AllocatedMemory::default()
691                    },
692                },
693                EntropyBucketPopulation::<AllocU32> {
694                    cached_bit_entropy: 0.0,
695                    bucket_populations: if 2 < max_stride {
696                        m32.alloc_cell(size)
697                    } else {
698                        AllocU32::AllocatedMemory::default()
699                    },
700                },
701                EntropyBucketPopulation::<AllocU32> {
702                    cached_bit_entropy: 0.0,
703                    bucket_populations: if 3 < max_stride {
704                        m32.alloc_cell(size)
705                    } else {
706                        AllocU32::AllocatedMemory::default()
707                    },
708                },
709                EntropyBucketPopulation::<AllocU32> {
710                    cached_bit_entropy: 0.0,
711                    bucket_populations: if 4 < max_stride {
712                        m32.alloc_cell(size)
713                    } else {
714                        AllocU32::AllocatedMemory::default()
715                    },
716                },
717                EntropyBucketPopulation::<AllocU32> {
718                    cached_bit_entropy: 0.0,
719                    bucket_populations: if 5 < max_stride {
720                        m32.alloc_cell(size)
721                    } else {
722                        AllocU32::AllocatedMemory::default()
723                    },
724                },
725                EntropyBucketPopulation::<AllocU32> {
726                    cached_bit_entropy: 0.0,
727                    bucket_populations: if 6 < max_stride {
728                        m32.alloc_cell(size)
729                    } else {
730                        AllocU32::AllocatedMemory::default()
731                    },
732                },
733                EntropyBucketPopulation::<AllocU32> {
734                    cached_bit_entropy: 0.0,
735                    bucket_populations: if 7 < max_stride {
736                        m32.alloc_cell(size)
737                    } else {
738                        AllocU32::AllocatedMemory::default()
739                    },
740                },
741            ],
742        }
743    }
744    pub fn disabled_placeholder(m32: &mut AllocU32) -> EntropyTally<AllocU32> {
745        Self::new(m32, Some(0))
746    }
747    fn observe_input_stream(&mut self, input0: &[u8], input1: &[u8]) {
748        let mut priors = [0u8; NUM_STRIDES];
749        for val in input0.iter().chain(input1.iter()) {
750            for stride in 0..NUM_STRIDES {
751                self.pop[stride].bucket_populations.slice_mut()
752                    [priors[stride] as usize * 256 + (*val as usize)] += 1;
753            }
754            {
755                let mut tmp = [0u8; NUM_STRIDES - 1];
756                tmp.clone_from_slice(&priors[..(NUM_STRIDES - 1)]);
757                priors[1..].clone_from_slice(&tmp[..]);
758                priors[0] = *val;
759            }
760        }
761        for stride in 0..NUM_STRIDES {
762            self.pop[stride].cached_bit_entropy =
763                HuffmanCost(self.pop[stride].bucket_populations.slice());
764        }
765    }
766    fn identify_best_population_and_update_cache(&mut self) -> u8 {
767        let mut old_bit_entropy: [floatY; NUM_STRIDES] = [0.0; NUM_STRIDES];
768        for (obe, be) in old_bit_entropy.iter_mut().zip(self.pop.iter_mut()) {
769            *obe = be.cached_bit_entropy;
770            if *obe != 0.0 {
771                be.cached_bit_entropy = HuffmanCost(be.bucket_populations.slice());
772            }
773        }
774        let mut best_stride = 0u8;
775        let mut best_entropy = self.pop[0].cached_bit_entropy - old_bit_entropy[0];
776        //println!("Weighing {} as {}", best_stride, best_entropy);
777        for index in 1..NUM_STRIDES {
778            let cur = self.pop[index].cached_bit_entropy - old_bit_entropy[index];
779            //println!("Weighing {} as {} = [{} - {}]", index, cur, self.pop[index].cached_bit_entropy, old_bit_entropy[index]);
780            if (best_entropy == 0.0 || cur < best_entropy) && old_bit_entropy[index] > 0.0 {
781                best_stride = index as u8;
782                best_entropy = cur;
783            }
784        }
785        best_stride
786    }
787    pub fn peek(&mut self) -> &mut EntropyBucketPopulation<AllocU32> {
788        &mut self.pop[0]
789    }
790    pub fn get_previous_bytes(
791        &self,
792        input0: &[u8],
793        input1: &[u8],
794        bytes_processed: usize,
795    ) -> [u8; NUM_STRIDES] {
796        let mut retval = [0u8; NUM_STRIDES];
797        for index in 0..NUM_STRIDES {
798            let bp_offset = index + 1;
799            if bp_offset <= bytes_processed {
800                let offset = bytes_processed - bp_offset;
801                if offset >= input0.len() {
802                    retval[index] = input1[offset - input0.len()];
803                } else {
804                    retval[index] = input0[offset];
805                }
806            }
807        }
808        retval
809    }
810    pub fn pick_best_stride<InputReference: SliceWrapper<u8>>(
811        &mut self,
812        commands: &[interface::Command<InputReference>],
813        input0: &[u8],
814        input1: &[u8],
815        bytes_processed: &mut usize,
816        entropy_pyramid: &EntropyPyramid<AllocU32>,
817        stride_detection_quality: u8,
818    ) -> u8 {
819        if stride_detection_quality == 0 {
820            return 0;
821        }
822        //println!("ENTROPY PYRAMID {:?}", entropy_pyramid.stride);
823        if stride_detection_quality > 1 {
824            entropy_pyramid.reset_scratch_to_deepest_level(self);
825        }
826        let mut pyramid_byte_index: usize = 0;
827        for cmd in commands.iter() {
828            match *cmd {
829                interface::Command::Copy(ref copy) => {
830                    *bytes_processed += copy.num_bytes as usize;
831                }
832                interface::Command::Dict(ref dict) => {
833                    *bytes_processed += dict.final_size as usize;
834                }
835                interface::Command::Literal(ref lit) => {
836                    if stride_detection_quality > 1 {
837                        let mut priors = self.get_previous_bytes(input0, input1, *bytes_processed);
838                        for (lindex, val) in lit.data.slice().iter().enumerate() {
839                            if lindex == NUM_STRIDES {
840                                let vpriors = self.get_previous_bytes(
841                                    input0,
842                                    input1,
843                                    NUM_STRIDES + *bytes_processed,
844                                );
845                                assert_eq!(vpriors, priors);
846                            }
847                            for (index, prior) in priors.iter().enumerate() {
848                                self.pop[index].bucket_populations.slice_mut()
849                                    [256 * (*prior as usize) + *val as usize] += 1;
850                                // increment the population value of this literal
851                                // for the respective prior for the stride index
852                            }
853                            {
854                                //reset prior values for the next item
855                                let mut tmp = [0u8; 7];
856                                tmp.clone_from_slice(&priors[..7]);
857                                priors[1..].clone_from_slice(&tmp[..]);
858                                priors[0] = *val;
859                            }
860                        }
861                    }
862                    *bytes_processed += lit.data.slice().len();
863                    pyramid_byte_index = *bytes_processed;
864                }
865                interface::Command::BlockSwitchCommand(_)
866                | interface::Command::BlockSwitchLiteral(_)
867                | interface::Command::BlockSwitchDistance(_)
868                | interface::Command::PredictionMode(_) => {}
869            }
870        }
871
872        //println!("ENTROPY PYRAMID {:?} selected {}", entropy_pyramid.stride, best_stride);
873
874        if stride_detection_quality > 1 {
875            self.identify_best_population_and_update_cache() + 1
876        } else {
877            entropy_pyramid.stride[entropy_pyramid
878                .byte_index_to_pyramid_index(pyramid_byte_index, input0.len() + input1.len())]
879                + 1
880        }
881    }
882    pub fn free(&mut self, m32: &mut AllocU32) {
883        for item in self.pop.iter_mut() {
884            m32.free_cell(core::mem::take(&mut item.bucket_populations))
885        }
886    }
887    pub fn is_free(&mut self) -> bool {
888        self.pop[0].bucket_populations.slice().is_empty()
889    }
890}
brotli/enc/find_stride.rs

brotli/enc/
find_stride.rs
