brotli/enc/
stride_eval.rs

1use super::super::alloc;
2use super::super::alloc::{Allocator, SliceWrapper, SliceWrapperMut};
3use super::backward_references::BrotliEncoderParams;
4use super::input_pair::{InputPair, InputReference, InputReferenceMut};
5use super::interface;
6use super::ir_interpret::{push_base, IRInterpreter};
7use super::prior_eval::DEFAULT_SPEED;
8use super::util::{floatX, FastLog2u16};
9use core;
10const NIBBLE_PRIOR_SIZE: usize = 16;
11pub const STRIDE_PRIOR_SIZE: usize = 256 * 256 * NIBBLE_PRIOR_SIZE * 2;
12
13pub fn local_init_cdfs(cdfs: &mut [u16]) {
14    for (index, item) in cdfs.iter_mut().enumerate() {
15        *item = 4 + 4 * (index as u16 & 0xf);
16    }
17}
18#[allow(unused_variables)]
19fn stride_lookup_lin(
20    stride_byte: u8,
21    selected_context: u8,
22    actual_context: usize,
23    high_nibble: Option<u8>,
24) -> usize {
25    if let Some(nibble) = high_nibble {
26        1 + 2 * (actual_context | ((stride_byte as usize & 0xf) << 8) | ((nibble as usize) << 12))
27    } else {
28        2 * (actual_context | ((stride_byte as usize) << 8))
29    }
30}
31
32struct CDF<'a> {
33    cdf: &'a mut [u16],
34}
35struct Stride1Prior {}
36impl Stride1Prior {
37    fn lookup_lin(
38        stride_byte: u8,
39        selected_context: u8,
40        actual_context: usize,
41        high_nibble: Option<u8>,
42    ) -> usize {
43        stride_lookup_lin(stride_byte, selected_context, actual_context, high_nibble)
44    }
45    fn lookup_mut(
46        data: &mut [u16],
47        stride_byte: u8,
48        selected_context: u8,
49        actual_context: usize,
50        high_nibble: Option<u8>,
51    ) -> CDF {
52        let index = Self::lookup_lin(stride_byte, selected_context, actual_context, high_nibble)
53            * NIBBLE_PRIOR_SIZE;
54        CDF::from(data.split_at_mut(index).1.split_at_mut(16).0)
55    }
56}
57
58impl<'a> CDF<'a> {
59    pub fn cost(&self, nibble_u8: u8) -> floatX {
60        assert_eq!(self.cdf.len(), 16);
61        let nibble = nibble_u8 as usize & 0xf;
62        let mut pdf = self.cdf[nibble];
63        if nibble_u8 != 0 {
64            pdf -= self.cdf[nibble - 1];
65        }
66        FastLog2u16(self.cdf[15]) - FastLog2u16(pdf)
67    }
68    pub fn update(&mut self, nibble_u8: u8, speed: (u16, u16)) {
69        assert_eq!(self.cdf.len(), 16);
70        for nib_range in (nibble_u8 as usize & 0xf)..16 {
71            self.cdf[nib_range] += speed.0;
72        }
73        if self.cdf[15] >= speed.1 {
74            const CDF_BIAS: [u16; 16] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
75            for nibble_index in 0..16 {
76                let tmp = &mut self.cdf[nibble_index];
77                *tmp = (tmp.wrapping_add(CDF_BIAS[nibble_index]))
78                    .wrapping_sub(tmp.wrapping_add(CDF_BIAS[nibble_index]) >> 2);
79            }
80        }
81    }
82}
83
84impl<'a> From<&'a mut [u16]> for CDF<'a> {
85    fn from(cdf: &'a mut [u16]) -> CDF<'a> {
86        assert_eq!(cdf.len(), 16);
87        CDF { cdf }
88    }
89}
90
91pub struct StrideEval<
92    'a,
93    Alloc: alloc::Allocator<u16> + alloc::Allocator<u32> + alloc::Allocator<floatX> + 'a,
94> {
95    input: InputPair<'a>,
96    alloc: &'a mut Alloc,
97    context_map: &'a interface::PredictionModeContextMap<InputReferenceMut<'a>>,
98    block_type: u8,
99    local_byte_offset: usize,
100    stride_priors: [<Alloc as Allocator<u16>>::AllocatedMemory; 8],
101    score: <Alloc as Allocator<floatX>>::AllocatedMemory,
102    cur_score_epoch: usize,
103    stride_speed: [(u16, u16); 2],
104    cur_stride: u8,
105}
106
107impl<'a, Alloc: alloc::Allocator<u16> + alloc::Allocator<u32> + alloc::Allocator<floatX> + 'a>
108    StrideEval<'a, Alloc>
109{
110    pub fn new(
111        alloc: &'a mut Alloc,
112        input: InputPair<'a>,
113        prediction_mode: &'a interface::PredictionModeContextMap<InputReferenceMut<'a>>,
114        params: &BrotliEncoderParams,
115    ) -> Self {
116        let do_alloc = true;
117        let mut stride_speed = prediction_mode.stride_context_speed();
118        if stride_speed[0] == (0, 0) {
119            stride_speed[0] = params.literal_adaptation[0]
120        }
121        if stride_speed[0] == (0, 0) {
122            stride_speed[0] = DEFAULT_SPEED;
123        }
124        if stride_speed[1] == (0, 0) {
125            stride_speed[1] = params.literal_adaptation[1]
126        }
127        if stride_speed[1] == (0, 0) {
128            stride_speed[1] = stride_speed[0];
129        }
130        let score = if do_alloc {
131            <Alloc as Allocator<floatX>>::alloc_cell(alloc, 8 * 4) // FIXME make this bigger than just 4
132        } else {
133            <Alloc as Allocator<floatX>>::AllocatedMemory::default()
134        };
135        let stride_priors = if do_alloc {
136            [
137                <Alloc as Allocator<u16>>::alloc_cell(alloc, STRIDE_PRIOR_SIZE),
138                <Alloc as Allocator<u16>>::alloc_cell(alloc, STRIDE_PRIOR_SIZE),
139                <Alloc as Allocator<u16>>::alloc_cell(alloc, STRIDE_PRIOR_SIZE),
140                <Alloc as Allocator<u16>>::alloc_cell(alloc, STRIDE_PRIOR_SIZE),
141                <Alloc as Allocator<u16>>::alloc_cell(alloc, STRIDE_PRIOR_SIZE),
142                <Alloc as Allocator<u16>>::alloc_cell(alloc, STRIDE_PRIOR_SIZE),
143                <Alloc as Allocator<u16>>::alloc_cell(alloc, STRIDE_PRIOR_SIZE),
144                <Alloc as Allocator<u16>>::alloc_cell(alloc, STRIDE_PRIOR_SIZE),
145            ]
146        } else {
147            [
148                <Alloc as Allocator<u16>>::AllocatedMemory::default(),
149                <Alloc as Allocator<u16>>::AllocatedMemory::default(),
150                <Alloc as Allocator<u16>>::AllocatedMemory::default(),
151                <Alloc as Allocator<u16>>::AllocatedMemory::default(),
152                <Alloc as Allocator<u16>>::AllocatedMemory::default(),
153                <Alloc as Allocator<u16>>::AllocatedMemory::default(),
154                <Alloc as Allocator<u16>>::AllocatedMemory::default(),
155                <Alloc as Allocator<u16>>::AllocatedMemory::default(),
156            ]
157        };
158        let mut ret = StrideEval::<Alloc> {
159            input,
160            context_map: prediction_mode,
161            block_type: 0,
162            alloc,
163            cur_stride: 1,
164            cur_score_epoch: 0,
165            local_byte_offset: 0,
166            stride_priors,
167            score,
168            stride_speed,
169        };
170        for stride_prior in ret.stride_priors.iter_mut() {
171            local_init_cdfs(stride_prior.slice_mut());
172        }
173        ret
174    }
175    pub fn alloc(&mut self) -> &mut Alloc {
176        self.alloc
177    }
178    pub fn choose_stride(&self, stride_data: &mut [u8]) {
179        assert_eq!(stride_data.len(), self.cur_score_epoch);
180        assert!(self.score.slice().len() > stride_data.len());
181        assert!(self.score.slice().len() > (stride_data.len() << 3) + 7 + 8);
182        for (index, choice) in stride_data.iter_mut().enumerate() {
183            let choices = self
184                .score
185                .slice()
186                .split_at((1 + index) << 3)
187                .1
188                .split_at(8)
189                .0;
190            let mut best_choice: u8 = 0;
191            let mut best_score = choices[0];
192            for (cur_index, cur_score) in choices.iter().enumerate() {
193                if *cur_score + 2.0 < best_score {
194                    // needs to be 2 bits better to be worth the type switch
195                    best_score = *cur_score;
196                    best_choice = cur_index as u8;
197                }
198            }
199            *choice = best_choice;
200        }
201    }
202    pub fn num_types(&self) -> usize {
203        self.cur_score_epoch
204    }
205    fn update_cost_base(
206        &mut self,
207        stride_prior: [u8; 8],
208        selected_bits: u8,
209        cm_prior: usize,
210        literal: u8,
211    ) {
212        type CurPrior = Stride1Prior;
213        {
214            for i in 0..8 {
215                let mut cdf = CurPrior::lookup_mut(
216                    self.stride_priors[i].slice_mut(),
217                    stride_prior[i],
218                    selected_bits,
219                    cm_prior,
220                    None,
221                );
222                self.score.slice_mut()[self.cur_score_epoch * 8 + i] += cdf.cost(literal >> 4);
223                cdf.update(literal >> 4, self.stride_speed[1]);
224            }
225        }
226        {
227            for i in 0..8 {
228                let mut cdf = CurPrior::lookup_mut(
229                    self.stride_priors[i].slice_mut(),
230                    stride_prior[i],
231                    selected_bits,
232                    cm_prior,
233                    Some(literal >> 4),
234                );
235                self.score.slice_mut()[self.cur_score_epoch * 8 + i] += cdf.cost(literal & 0xf);
236                cdf.update(literal & 0xf, self.stride_speed[0]);
237            }
238        }
239    }
240}
241impl<'a, Alloc: alloc::Allocator<u16> + alloc::Allocator<u32> + alloc::Allocator<floatX>> Drop
242    for StrideEval<'a, Alloc>
243{
244    fn drop(&mut self) {
245        <Alloc as Allocator<floatX>>::free_cell(self.alloc, core::mem::take(&mut self.score));
246        for i in 0..8 {
247            <Alloc as Allocator<u16>>::free_cell(
248                self.alloc,
249                core::mem::take(&mut self.stride_priors[i]),
250            );
251        }
252    }
253}
254
255impl<'a, Alloc: alloc::Allocator<u16> + alloc::Allocator<u32> + alloc::Allocator<floatX>>
256    IRInterpreter for StrideEval<'a, Alloc>
257{
258    fn inc_local_byte_offset(&mut self, inc: usize) {
259        self.local_byte_offset += inc;
260    }
261    fn local_byte_offset(&self) -> usize {
262        self.local_byte_offset
263    }
264    fn update_block_type(&mut self, new_type: u8, stride: u8) {
265        self.block_type = new_type;
266        self.cur_stride = stride;
267        self.cur_score_epoch += 1;
268        if self.cur_score_epoch * 8 + 7 >= self.score.slice().len() {
269            let new_len = self.score.slice().len() * 2;
270            let mut new_score = <Alloc as Allocator<floatX>>::alloc_cell(self.alloc, new_len);
271            for (src, dst) in self.score.slice().iter().zip(
272                new_score
273                    .slice_mut()
274                    .split_at_mut(self.score.slice().len())
275                    .0
276                    .iter_mut(),
277            ) {
278                *dst = *src;
279            }
280            <Alloc as Allocator<floatX>>::free_cell(
281                self.alloc,
282                core::mem::replace(&mut self.score, new_score),
283            );
284        }
285    }
286    fn block_type(&self) -> u8 {
287        self.block_type
288    }
289    fn literal_data_at_offset(&self, index: usize) -> u8 {
290        self.input[index]
291    }
292    fn literal_context_map(&self) -> &[u8] {
293        self.context_map.literal_context_map.slice()
294    }
295    fn prediction_mode(&self) -> ::interface::LiteralPredictionModeNibble {
296        self.context_map.literal_prediction_mode()
297    }
298    fn update_cost(
299        &mut self,
300        stride_prior: [u8; 8],
301        stride_prior_offset: usize,
302        selected_bits: u8,
303        cm_prior: usize,
304        literal: u8,
305    ) {
306        let reversed_stride_priors = [
307            stride_prior[stride_prior_offset & 7],
308            stride_prior[stride_prior_offset.wrapping_sub(1) & 7],
309            stride_prior[stride_prior_offset.wrapping_sub(2) & 7],
310            stride_prior[stride_prior_offset.wrapping_sub(3) & 7],
311            stride_prior[stride_prior_offset.wrapping_sub(4) & 7],
312            stride_prior[stride_prior_offset.wrapping_sub(5) & 7],
313            stride_prior[stride_prior_offset.wrapping_sub(6) & 7],
314            stride_prior[stride_prior_offset.wrapping_sub(7) & 7],
315        ];
316        self.update_cost_base(reversed_stride_priors, selected_bits, cm_prior, literal)
317    }
318}
319
320impl<'a, 'b, Alloc: alloc::Allocator<u16> + alloc::Allocator<u32> + alloc::Allocator<floatX>>
321    interface::CommandProcessor<'b> for StrideEval<'a, Alloc>
322{
323    fn push(&mut self, val: interface::Command<InputReference<'b>>) {
324        push_base(self, val)
325    }
326}
brotli/enc/stride_eval.rs

brotli/enc/
stride_eval.rs
