brotli/enc/
histogram.rs

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

brotli/enc/
histogram.rs
