brotli/enc/
histogram.rs

1#![allow(dead_code)]
2
3use super::super::alloc::{SliceWrapper, SliceWrapperMut};
4use super::block_split::BlockSplit;
5use super::command::Command;
6use super::constants::{kSigned3BitContextLookup, kUTF8ContextLookup};
7use super::vectorization::Mem256i;
8use core::cmp::min;
9static kBrotliMinWindowBits: i32 = 10i32;
10
11static kBrotliMaxWindowBits: i32 = 24i32;
12
13//#[derive(Clone)] clone is broken for arrays > 32
14pub struct HistogramLiteral {
15    pub data_: [u32; 256],
16    pub total_count_: usize,
17    pub bit_cost_: super::util::floatX,
18}
19impl Clone for HistogramLiteral {
20    #[inline(always)]
21    fn clone(&self) -> HistogramLiteral {
22        HistogramLiteral {
23            data_: self.data_,
24            total_count_: self.total_count_,
25            bit_cost_: self.bit_cost_,
26        }
27    }
28}
29impl Default for HistogramLiteral {
30    #[inline(always)]
31    fn default() -> HistogramLiteral {
32        HistogramLiteral {
33            data_: [0; 256],
34            total_count_: 0,
35            bit_cost_: 3.402e+38 as super::util::floatX,
36        }
37    }
38}
39//#[derive(Clone)] clone is broken for arrays > 32
40pub struct HistogramCommand {
41    pub data_: [u32; 704],
42    pub total_count_: usize,
43    pub bit_cost_: super::util::floatX,
44}
45impl Clone for HistogramCommand {
46    #[inline(always)]
47    fn clone(&self) -> HistogramCommand {
48        HistogramCommand {
49            data_: self.data_,
50            total_count_: self.total_count_,
51            bit_cost_: self.bit_cost_,
52        }
53    }
54}
55impl Default for HistogramCommand {
56    #[inline(always)]
57    fn default() -> HistogramCommand {
58        HistogramCommand {
59            data_: [0; 704],
60            total_count_: 0,
61            bit_cost_: 3.402e+38 as super::util::floatX,
62        }
63    }
64}
65//#[derive(Clone)] // #derive is broken for arrays > 32
66
67#[cfg(not(feature = "disallow_large_window_size"))]
68const BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS: usize = 544;
69#[cfg(feature = "disallow_large_window_size")]
70const BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS: usize = 520;
71
72pub struct HistogramDistance {
73    pub data_: [u32; BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS],
74    pub total_count_: usize,
75    pub bit_cost_: super::util::floatX,
76}
77impl Clone for HistogramDistance {
78    fn clone(&self) -> HistogramDistance {
79        HistogramDistance {
80            data_: self.data_,
81            total_count_: self.total_count_,
82            bit_cost_: self.bit_cost_,
83        }
84    }
85}
86impl Default for HistogramDistance {
87    fn default() -> HistogramDistance {
88        HistogramDistance {
89            data_: [0; BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS],
90            total_count_: 0,
91            bit_cost_: 3.402e+38 as super::util::floatX,
92        }
93    }
94}
95
96pub trait CostAccessors {
97    type i32vec: Sized + SliceWrapper<Mem256i> + SliceWrapperMut<Mem256i>;
98    fn make_nnz_storage() -> Self::i32vec;
99    fn total_count(&self) -> usize;
100    fn bit_cost(&self) -> super::util::floatX;
101    fn set_bit_cost(&mut self, cost: super::util::floatX);
102    fn set_total_count(&mut self, count: usize);
103}
104impl SliceWrapper<u32> for HistogramLiteral {
105    #[inline(always)]
106    fn slice(&self) -> &[u32] {
107        &self.data_[..]
108    }
109}
110impl SliceWrapperMut<u32> for HistogramLiteral {
111    #[inline(always)]
112    fn slice_mut(&mut self) -> &mut [u32] {
113        &mut self.data_[..]
114    }
115}
116pub struct Array264i([Mem256i; 33]);
117impl SliceWrapperMut<Mem256i> for Array264i {
118    #[inline(always)]
119    fn slice_mut(&mut self) -> &mut [Mem256i] {
120        &mut self.0[..]
121    }
122}
123
124impl SliceWrapper<Mem256i> for Array264i {
125    #[inline(always)]
126    fn slice(&self) -> &[Mem256i] {
127        &self.0[..]
128    }
129}
130impl Default for Array264i {
131    #[inline(always)]
132    fn default() -> Array264i {
133        Array264i([Mem256i::default(); 33])
134    }
135}
136pub struct Array528i([Mem256i; 66]);
137impl SliceWrapperMut<Mem256i> for Array528i {
138    #[inline(always)]
139    fn slice_mut(&mut self) -> &mut [Mem256i] {
140        &mut self.0[..]
141    }
142}
143impl SliceWrapper<Mem256i> for Array528i {
144    #[inline(always)]
145    fn slice(&self) -> &[Mem256i] {
146        &self.0[..]
147    }
148}
149impl Default for Array528i {
150    #[inline(always)]
151    fn default() -> Array528i {
152        Array528i([Mem256i::default(); 66])
153    }
154}
155
156pub struct Array712i([Mem256i; 89]);
157impl SliceWrapperMut<Mem256i> for Array712i {
158    #[inline(always)]
159    fn slice_mut(&mut self) -> &mut [Mem256i] {
160        &mut self.0[..]
161    }
162}
163impl SliceWrapper<Mem256i> for Array712i {
164    #[inline(always)]
165    fn slice(&self) -> &[Mem256i] {
166        &self.0[..]
167    }
168}
169impl Default for Array712i {
170    #[inline(always)]
171    fn default() -> Array712i {
172        Array712i([Mem256i::default(); 89])
173    }
174}
175
176pub struct EmptyIVec {}
177
178impl SliceWrapperMut<Mem256i> for EmptyIVec {
179    #[inline(always)]
180    fn slice_mut(&mut self) -> &mut [Mem256i] {
181        &mut []
182    }
183}
184impl SliceWrapper<Mem256i> for EmptyIVec {
185    #[inline(always)]
186    fn slice(&self) -> &[Mem256i] {
187        &[]
188    }
189}
190
191impl Default for EmptyIVec {
192    #[inline(always)]
193    fn default() -> EmptyIVec {
194        EmptyIVec {}
195    }
196}
197
198#[cfg(feature = "vector_scratch_space")]
199pub type HistogramLiteralScratch = Array264i;
200
201#[cfg(not(feature = "vector_scratch_space"))]
202pub type HistogramLiteralScratch = EmptyIVec;
203
204impl CostAccessors for HistogramLiteral {
205    type i32vec = HistogramLiteralScratch;
206    fn make_nnz_storage() -> Self::i32vec {
207        HistogramLiteralScratch::default()
208    }
209    #[inline(always)]
210    fn total_count(&self) -> usize {
211        self.total_count_
212    }
213    #[inline(always)]
214    fn bit_cost(&self) -> super::util::floatX {
215        self.bit_cost_
216    }
217    #[inline(always)]
218    fn set_bit_cost(&mut self, data: super::util::floatX) {
219        self.bit_cost_ = data;
220    }
221    #[inline(always)]
222    fn set_total_count(&mut self, data: usize) {
223        self.total_count_ = data;
224    }
225}
226
227impl SliceWrapper<u32> for HistogramCommand {
228    #[inline(always)]
229    fn slice(&self) -> &[u32] {
230        &self.data_[..]
231    }
232}
233impl SliceWrapperMut<u32> for HistogramCommand {
234    #[inline(always)]
235    fn slice_mut(&mut self) -> &mut [u32] {
236        &mut self.data_[..]
237    }
238}
239
240#[cfg(feature = "vector_scratch_space")]
241pub type HistogramCommandScratch = Array712i;
242
243#[cfg(not(feature = "vector_scratch_space"))]
244pub type HistogramCommandScratch = EmptyIVec;
245
246impl CostAccessors for HistogramCommand {
247    type i32vec = HistogramCommandScratch;
248    fn make_nnz_storage() -> Self::i32vec {
249        HistogramCommandScratch::default()
250    }
251    #[inline(always)]
252    fn total_count(&self) -> usize {
253        self.total_count_
254    }
255    #[inline(always)]
256    fn bit_cost(&self) -> super::util::floatX {
257        self.bit_cost_
258    }
259    #[inline(always)]
260    fn set_bit_cost(&mut self, data: super::util::floatX) {
261        self.bit_cost_ = data;
262    }
263    #[inline(always)]
264    fn set_total_count(&mut self, data: usize) {
265        self.total_count_ = data;
266    }
267}
268
269impl SliceWrapper<u32> for HistogramDistance {
270    #[inline(always)]
271    fn slice(&self) -> &[u32] {
272        &self.data_[..]
273    }
274}
275impl SliceWrapperMut<u32> for HistogramDistance {
276    #[inline(always)]
277    fn slice_mut(&mut self) -> &mut [u32] {
278        &mut self.data_[..]
279    }
280}
281
282#[cfg(feature = "vector_scratch_space")]
283pub type HistogramDistanceScratch = Array528i;
284
285#[cfg(not(feature = "vector_scratch_space"))]
286pub type HistogramDistanceScratch = EmptyIVec;
287
288impl CostAccessors for HistogramDistance {
289    type i32vec = HistogramDistanceScratch;
290    fn make_nnz_storage() -> Self::i32vec {
291        HistogramDistanceScratch::default()
292    }
293
294    #[inline(always)]
295    fn total_count(&self) -> usize {
296        self.total_count_
297    }
298    #[inline(always)]
299    fn bit_cost(&self) -> super::util::floatX {
300        self.bit_cost_
301    }
302    #[inline(always)]
303    fn set_bit_cost(&mut self, data: super::util::floatX) {
304        self.bit_cost_ = data;
305    }
306    #[inline(always)]
307    fn set_total_count(&mut self, data: usize) {
308        self.total_count_ = data;
309    }
310}
311
312#[derive(Copy, Clone)]
313pub enum ContextType {
314    CONTEXT_LSB6 = 0,
315    CONTEXT_MSB6 = 1,
316    CONTEXT_UTF8 = 2,
317    CONTEXT_SIGNED = 3,
318}
319
320impl Default for ContextType {
321    #[inline(always)]
322    fn default() -> ContextType {
323        ContextType::CONTEXT_LSB6
324    }
325}
326
327pub struct BlockSplitIterator<'a, Alloc: alloc::Allocator<u8> + 'a + alloc::Allocator<u32> + 'a> {
328    pub split_: &'a BlockSplit<Alloc>,
329    pub idx_: usize,
330    pub type_: usize,
331    pub length_: usize,
332}
333
334impl<'a, Alloc: alloc::Allocator<u8> + alloc::Allocator<u32> + 'a> BlockSplitIterator<'a, Alloc> {
335    fn new(split: &'a BlockSplit<Alloc>) -> Self {
336        Self {
337            split_: split,
338            idx_: 0,
339            type_: 0,
340            length_: if !split.lengths.slice().is_empty() {
341                split.lengths.slice()[0] as usize
342            } else {
343                0
344            },
345        }
346    }
347
348    fn next(&mut self) {
349        if self.length_ == 0 {
350            self.idx_ = self.idx_.wrapping_add(1);
351            self.type_ = self.split_.types.slice()[self.idx_] as usize;
352            self.length_ = self.split_.lengths.slice()[self.idx_] as usize;
353        }
354        self.length_ = self.length_.wrapping_sub(1);
355    }
356}
357
358pub fn HistogramAddItem<HistogramType: SliceWrapper<u32> + SliceWrapperMut<u32> + CostAccessors>(
359    xself: &mut HistogramType,
360    val: usize,
361) {
362    {
363        let _rhs = 1;
364        let _lhs = &mut xself.slice_mut()[val];
365        let val = (*_lhs).wrapping_add(_rhs as u32);
366        *_lhs = val;
367    }
368    let new_count = xself.total_count().wrapping_add(1);
369    xself.set_total_count(new_count);
370}
371pub fn HistogramAddVector<
372    HistogramType: SliceWrapper<u32> + SliceWrapperMut<u32> + CostAccessors,
373    IntegerType: Sized + Clone,
374>(
375    xself: &mut HistogramType,
376    p: &[IntegerType],
377    n: usize,
378) where
379    u64: core::convert::From<IntegerType>,
380{
381    let new_tc = xself.total_count().wrapping_add(n);
382    xself.set_total_count(new_tc);
383    for p_item in p[..n].iter() {
384        let _rhs = 1;
385        let index: usize = u64::from(p_item.clone()) as usize;
386        let _lhs = &mut xself.slice_mut()[index];
387        *_lhs = (*_lhs).wrapping_add(_rhs as u32);
388    }
389}
390
391#[inline(always)]
392pub fn HistogramClear<HistogramType: SliceWrapperMut<u32> + CostAccessors>(
393    xself: &mut HistogramType,
394) {
395    for data_elem in xself.slice_mut().iter_mut() {
396        *data_elem = 0;
397    }
398    xself.set_total_count(0);
399    xself.set_bit_cost(3.402e+38 as super::util::floatX);
400}
401pub fn ClearHistograms<HistogramType: SliceWrapperMut<u32> + CostAccessors>(
402    array: &mut [HistogramType],
403    length: usize,
404) {
405    for item in array[..length].iter_mut() {
406        HistogramClear(item)
407    }
408}
409
410#[inline(always)]
411pub fn HistogramAddHistogram<
412    HistogramType: SliceWrapperMut<u32> + SliceWrapper<u32> + CostAccessors,
413>(
414    xself: &mut HistogramType,
415    v: &HistogramType,
416) {
417    let old_total_count = xself.total_count();
418    xself.set_total_count(old_total_count + (*v).total_count());
419    let h0 = xself.slice_mut();
420    let h1 = v.slice();
421    let n = min(h0.len(), h1.len());
422    for i in 0..n {
423        let h0val = &mut h0[i];
424        let val = h0val.wrapping_add(h1[i]);
425        *h0val = val;
426    }
427}
428pub fn HistogramSelfAddHistogram<
429    HistogramType: SliceWrapperMut<u32> + SliceWrapper<u32> + CostAccessors,
430>(
431    xself: &mut [HistogramType],
432    i0: usize,
433    i1: usize,
434) {
435    let tc_new = xself[i1].total_count();
436    let tc_old = xself[i0].total_count();
437    xself[i0].set_total_count(tc_old.wrapping_add(tc_new));
438    let h0 = xself[i0].slice().len();
439    let h0a = xself[i0].slice().len();
440    let h1 = xself[i1].slice().len();
441    let n = min(h0, min(h0a, h1));
442    for h_index in 0..n {
443        let val = xself[i0].slice()[h_index].wrapping_add(xself[i1].slice()[h_index]);
444        xself[i0].slice_mut()[h_index] = val;
445    }
446}
447
448#[inline(always)]
449pub fn Context(p1: u8, p2: u8, mode: ContextType) -> u8 {
450    match mode {
451        ContextType::CONTEXT_SIGNED => {
452            (((kSigned3BitContextLookup[p1 as usize] as i32) << 3)
453                + kSigned3BitContextLookup[p2 as usize] as i32) as u8
454        }
455        ContextType::CONTEXT_UTF8 => {
456            (kUTF8ContextLookup[p1 as usize] as i32
457                | kUTF8ContextLookup[(p2 as i32 + 256i32) as usize] as i32) as u8
458        }
459        ContextType::CONTEXT_MSB6 => (p1 as i32 >> 2) as u8,
460        ContextType::CONTEXT_LSB6 => (p1 as i32 & 0x3fi32) as u8, /* else {
461                                                                  0u8
462                                                                  }*/
463    }
464}
465
466pub fn BrotliBuildHistogramsWithContext<'a, Alloc: alloc::Allocator<u8> + alloc::Allocator<u32>>(
467    cmds: &[Command],
468    num_commands: usize,
469    literal_split: &BlockSplit<Alloc>,
470    insert_and_copy_split: &BlockSplit<Alloc>,
471    dist_split: &BlockSplit<Alloc>,
472    ringbuffer: &[u8],
473    start_pos: usize,
474    mask: usize,
475    mut prev_byte: u8,
476    mut prev_byte2: u8,
477    context_modes: &[ContextType],
478    literal_histograms: &mut [HistogramLiteral],
479    insert_and_copy_histograms: &mut [HistogramCommand],
480    copy_dist_histograms: &mut [HistogramDistance],
481) {
482    let mut pos: usize = start_pos;
483    let mut literal_it: BlockSplitIterator<Alloc>;
484    let mut insert_and_copy_it: BlockSplitIterator<Alloc>;
485    let mut dist_it: BlockSplitIterator<Alloc>;
486    literal_it = BlockSplitIterator::new(literal_split);
487    insert_and_copy_it = BlockSplitIterator::new(insert_and_copy_split);
488    dist_it = BlockSplitIterator::new(dist_split);
489    for i in 0usize..num_commands {
490        let cmd = &cmds[i];
491        let mut j: usize;
492        insert_and_copy_it.next();
493        HistogramAddItem(
494            &mut insert_and_copy_histograms[insert_and_copy_it.type_],
495            cmd.cmd_prefix_ as usize,
496        );
497        j = cmd.insert_len_ as usize;
498        while j != 0usize {
499            {
500                literal_it.next();
501                let context: usize = if !context_modes.is_empty() {
502                    (literal_it.type_ << 6).wrapping_add(Context(
503                        prev_byte,
504                        prev_byte2,
505                        context_modes[literal_it.type_],
506                    ) as usize)
507                } else {
508                    literal_it.type_
509                };
510                HistogramAddItem(
511                    &mut literal_histograms[(context as usize)],
512                    ringbuffer[(pos & mask)] as usize,
513                );
514                prev_byte2 = prev_byte;
515                prev_byte = ringbuffer[(pos & mask)];
516                pos = pos.wrapping_add(1);
517            }
518            j = j.wrapping_sub(1);
519        }
520        pos = pos.wrapping_add(cmd.copy_len() as usize);
521        if cmd.copy_len() != 0 {
522            prev_byte2 = ringbuffer[(pos.wrapping_sub(2) & mask)];
523            prev_byte = ringbuffer[(pos.wrapping_sub(1) & mask)];
524            if cmd.cmd_prefix_ as i32 >= 128i32 {
525                dist_it.next();
526                let context: usize =
527                    (dist_it.type_ << 2).wrapping_add(cmd.distance_context() as usize);
528                HistogramAddItem(
529                    &mut copy_dist_histograms[(context as usize)],
530                    cmd.dist_prefix_ as usize & 0x3ff,
531                );
532            }
533        }
534    }
535}
brotli/enc/histogram.rs

brotli/enc/
histogram.rs
