brotli/enc/
command.rs

1use super::encode::BROTLI_NUM_DISTANCE_SHORT_CODES;
2use super::util::Log2FloorNonZero;
3#[derive(Copy, Clone, Debug)]
4pub struct BrotliDistanceParams {
5    pub distance_postfix_bits: u32,
6    pub num_direct_distance_codes: u32,
7    pub alphabet_size: u32,
8    pub max_distance: usize,
9}
10
11#[derive(Clone, Copy, Debug, Default)]
12pub struct Command {
13    // stores copy_len in low 25 bits and copy_code - copy_len in high 7 bit
14    pub insert_len_: u32,
15    pub copy_len_: u32,
16    //stores distance_extra bits
17    pub dist_extra_: u32,
18    pub cmd_prefix_: u16,
19    // stores distance code in low 10 bits and num extra bits in high 6 bits
20    pub dist_prefix_: u16,
21}
22
23impl Command {
24    pub fn copy_len(&self) -> u32 {
25        self.copy_len_ & 0x01ff_ffff
26    }
27
28    pub fn distance_context(&self) -> u32 {
29        let r: u32 = (self.cmd_prefix_ as i32 >> 6) as u32;
30        let c: u32 = (self.cmd_prefix_ as i32 & 7i32) as u32;
31        if (r == 0 || r == 2 || r == 4 || r == 7) && c <= 2 {
32            c
33        } else {
34            3
35        }
36    }
37
38    pub fn init_insert(&mut self, insertlen: usize) {
39        self.insert_len_ = insertlen as u32;
40        self.copy_len_ = (4i32 << 25) as u32;
41        self.dist_extra_ = 0u32;
42        self.dist_prefix_ = (1u16 << 10) | BROTLI_NUM_DISTANCE_SHORT_CODES as u16;
43        get_length_code(insertlen, 4usize, false, &mut self.cmd_prefix_);
44    }
45}
46
47#[inline(always)]
48pub fn ComputeDistanceCode(distance: usize, max_distance: usize, dist_cache: &[i32]) -> usize {
49    if distance <= max_distance {
50        let distance_plus_3: usize = distance.wrapping_add(3);
51        let offset0: usize = distance_plus_3.wrapping_sub(dist_cache[0] as usize);
52        let offset1: usize = distance_plus_3.wrapping_sub(dist_cache[1] as usize);
53        if distance == dist_cache[0] as usize {
54            return 0usize;
55        } else if distance == dist_cache[1] as usize {
56            return 1;
57        } else if offset0 < 7usize {
58            return (0x0975_0468_i32 >> (4usize).wrapping_mul(offset0) & 0xfi32) as usize;
59        } else if offset1 < 7usize {
60            return (0x0fdb_1ace_i32 >> (4usize).wrapping_mul(offset1) & 0xfi32) as usize;
61        } else if distance == dist_cache[2] as usize {
62            return 2usize;
63        } else if distance == dist_cache[3] as usize {
64            return 3usize;
65        }
66    }
67    distance.wrapping_add(16).wrapping_sub(1)
68}
69
70#[inline(always)]
71pub fn GetInsertLengthCode(insertlen: usize) -> u16 {
72    if insertlen < 6usize {
73        insertlen as u16
74    } else if insertlen < 130usize {
75        let nbits: u32 = Log2FloorNonZero(insertlen.wrapping_sub(2) as u64).wrapping_sub(1);
76        ((nbits << 1) as usize)
77            .wrapping_add(insertlen.wrapping_sub(2) >> nbits)
78            .wrapping_add(2) as u16
79    } else if insertlen < 2114usize {
80        Log2FloorNonZero(insertlen.wrapping_sub(66) as u64).wrapping_add(10) as u16
81    } else if insertlen < 6210usize {
82        21u32 as u16
83    } else if insertlen < 22594usize {
84        22u32 as u16
85    } else {
86        23u32 as u16
87    }
88}
89
90#[inline(always)]
91pub fn GetCopyLengthCode(copylen: usize) -> u16 {
92    if copylen < 10usize {
93        copylen.wrapping_sub(2) as u16
94    } else if copylen < 134usize {
95        let nbits: u32 = Log2FloorNonZero(copylen.wrapping_sub(6) as u64).wrapping_sub(1);
96        ((nbits << 1) as usize)
97            .wrapping_add(copylen.wrapping_sub(6) >> nbits)
98            .wrapping_add(4) as u16
99    } else if copylen < 2118usize {
100        Log2FloorNonZero(copylen.wrapping_sub(70) as u64).wrapping_add(12) as u16
101    } else {
102        23u32 as u16
103    }
104}
105
106#[inline(always)]
107pub(crate) fn combine_length_codes(inscode: u16, copycode: u16, use_last_distance: bool) -> u16 {
108    let bits64: u16 = (copycode as u32 & 0x7u32 | (inscode as u32 & 0x7u32) << 3) as u16;
109    if use_last_distance && inscode < 8 && copycode < 16 {
110        if (copycode as i32) < 8i32 {
111            bits64
112        } else {
113            let s64: u16 = 64u16;
114            (bits64 as i32 | s64 as i32) as u16
115        }
116    } else {
117        let sub_offset: i32 = 2i32 * ((copycode as i32 >> 3) + 3i32 * (inscode as i32 >> 3));
118        let offset = (sub_offset << 5) + 0x40i32 + (0x520d40i32 >> sub_offset & 0xc0i32);
119        (offset as u16 as i32 | bits64 as i32) as u16
120    }
121}
122
123#[inline(always)]
124pub(crate) fn get_length_code(
125    insertlen: usize,
126    copylen: usize,
127    use_last_distance: bool,
128    code: &mut u16,
129) {
130    let inscode: u16 = GetInsertLengthCode(insertlen);
131    let copycode: u16 = GetCopyLengthCode(copylen);
132    *code = combine_length_codes(inscode, copycode, use_last_distance);
133}
134pub fn PrefixEncodeCopyDistance(
135    distance_code: usize,
136    num_direct_codes: usize,
137    postfix_bits: u64,
138    code: &mut u16,
139    extra_bits: &mut u32,
140) {
141    if distance_code < (BROTLI_NUM_DISTANCE_SHORT_CODES as usize).wrapping_add(num_direct_codes) {
142        *code = distance_code as u16;
143        *extra_bits = 0u32;
144    } else {
145        let dist: u64 = (1u64 << postfix_bits.wrapping_add(2u32 as (u64))).wrapping_add(
146            (distance_code as u64)
147                .wrapping_sub(BROTLI_NUM_DISTANCE_SHORT_CODES as u64)
148                .wrapping_sub(num_direct_codes as u64),
149        );
150        let bucket: u64 = Log2FloorNonZero(dist).wrapping_sub(1) as (u64);
151        let postfix_mask: u64 = (1u32 << postfix_bits).wrapping_sub(1) as (u64);
152        let postfix: u64 = dist & postfix_mask;
153        let prefix: u64 = (dist >> bucket) & 1;
154        let offset: u64 = (2u64).wrapping_add(prefix) << bucket;
155        let nbits: u64 = bucket.wrapping_sub(postfix_bits);
156        *code = ((nbits << 10)
157            | ((BROTLI_NUM_DISTANCE_SHORT_CODES as u64)
158                .wrapping_add(num_direct_codes as u64)
159                .wrapping_add(
160                    2u64.wrapping_mul(nbits.wrapping_sub(1))
161                        .wrapping_add(prefix)
162                        << postfix_bits,
163                )
164                .wrapping_add(postfix))) as u16;
165        *extra_bits = (dist.wrapping_sub(offset) >> postfix_bits) as u32;
166        /*(16u64)
167        .wrapping_add(num_direct_codes as u64)
168        .wrapping_add((2u64).wrapping_mul(nbits.wrapping_sub(1)).wrapping_add(prefix) <<
169                      postfix_bits)
170        .wrapping_add(postfix) as u16;*/
171        //*extra_bits = (nbits << 24 | dist.wrapping_sub(offset) >> postfix_bits) as u32;
172    }
173}
174
175impl Command {
176    pub fn restore_distance_code(&self, dist: &BrotliDistanceParams) -> u32 {
177        if (self.dist_prefix_ as i32 & 0x3ff)
178            < BROTLI_NUM_DISTANCE_SHORT_CODES as i32 + dist.num_direct_distance_codes as i32
179        {
180            self.dist_prefix_ as u32 & 0x3ff
181        } else {
182            let dcode = self.dist_prefix_ as u32 & 0x3ff;
183            let nbits: u32 = u32::from(self.dist_prefix_ >> 10);
184            let extra: u32 = self.dist_extra_;
185            let postfix_mask = (1u32 << dist.distance_postfix_bits) - 1;
186            let hcode = dcode
187                .wrapping_sub(dist.num_direct_distance_codes)
188                .wrapping_sub(BROTLI_NUM_DISTANCE_SHORT_CODES)
189                >> dist.distance_postfix_bits;
190            let lcode = dcode
191                .wrapping_sub(dist.num_direct_distance_codes)
192                .wrapping_sub(BROTLI_NUM_DISTANCE_SHORT_CODES)
193                & postfix_mask;
194            let offset = (2u32.wrapping_add((hcode & 1)) << nbits).wrapping_sub(4);
195            (offset.wrapping_add(extra) << dist.distance_postfix_bits)
196                .wrapping_add(lcode)
197                .wrapping_add(dist.num_direct_distance_codes)
198                .wrapping_add(BROTLI_NUM_DISTANCE_SHORT_CODES)
199        }
200    }
201
202    // returns which distance code to use ( 0 means none, 1 means last, 2 means penultimate, 3 means the prior to penultimate
203    pub fn distance_index_and_offset(&self, dist: &BrotliDistanceParams) -> (usize, isize) {
204        let n_postfix = dist.distance_postfix_bits;
205        let n_direct = dist.num_direct_distance_codes;
206        let dextra = self.dist_extra_;
207        let dprefix = self.dist_prefix_ & 0x3ff;
208        let n_dist_bits = self.dist_prefix_ >> 10;
209        if u32::from(dprefix) < BROTLI_NUM_DISTANCE_SHORT_CODES {
210            let table: [(usize, isize); 16] = [
211                (1, 0),
212                (2, 0),
213                (3, 0),
214                (4, 0),
215                (1, -1),
216                (1, 1),
217                (1, -2),
218                (1, 2),
219                (1, -3),
220                (1, 3),
221                (2, -1),
222                (2, 1),
223                (2, -2),
224                (2, 2),
225                (2, -3),
226                (2, 3),
227            ];
228            //eprint!("AA {:?} {:?} -> {:?}\n",*self, *dist, table[dprefix as usize]);
229            return table[dprefix as usize];
230        }
231        if (dprefix as usize) < BROTLI_NUM_DISTANCE_SHORT_CODES as usize + n_direct as usize {
232            let ret = dprefix as isize + 1 - BROTLI_NUM_DISTANCE_SHORT_CODES as isize;
233            //eprint!("BB {:?} {:?} -> {:?}\n",*self, *dist, ret);
234            return (0, ret);
235        }
236        let postfix_mask = (1 << n_postfix) - 1;
237        let dcode = dprefix as u32 - BROTLI_NUM_DISTANCE_SHORT_CODES - n_direct;
238        let hcode = dcode >> n_postfix;
239        let lcode = dcode & postfix_mask;
240        let offset = ((2 + (hcode & 1)) << n_dist_bits) - 4;
241
242        let ret = (((offset + dextra) << n_postfix) + lcode + n_direct + 1) as isize;
243        //assert!(ret != 0);
244        (0, ret)
245    }
246}
247
248pub fn RecomputeDistancePrefixes(
249    cmds: &mut [Command],
250    num_commands: usize,
251    num_direct_distance_codes: u32,
252    distance_postfix_bits: u32,
253    dist: &BrotliDistanceParams,
254) {
255    if num_direct_distance_codes == 0u32 && (distance_postfix_bits == 0u32) {
256        return;
257    }
258    for i in 0usize..num_commands {
259        let cmd: &mut Command = &mut cmds[i];
260        if cmd.copy_len() != 0 && cmd.cmd_prefix_ >= 128 {
261            PrefixEncodeCopyDistance(
262                cmd.restore_distance_code(dist) as usize,
263                num_direct_distance_codes as usize,
264                distance_postfix_bits as (u64),
265                &mut cmd.dist_prefix_,
266                &mut cmd.dist_extra_,
267            );
268        }
269    }
270}
271
272impl Command {
273    pub fn init(
274        &mut self,
275        dist: &BrotliDistanceParams,
276        insertlen: usize,
277        copylen: usize,
278        copylen_code: usize,
279        distance_code: usize,
280    ) {
281        self.insert_len_ = insertlen as u32;
282        let copylen_code_delta = (copylen_code as i32 - copylen as i32) as i8;
283        self.copy_len_ = (copylen as u32 | (u32::from(copylen_code_delta as u8) << 25));
284        PrefixEncodeCopyDistance(
285            distance_code,
286            dist.num_direct_distance_codes as usize,
287            u64::from(dist.distance_postfix_bits),
288            &mut self.dist_prefix_,
289            &mut self.dist_extra_,
290        );
291        get_length_code(
292            insertlen,
293            copylen_code,
294            (self.dist_prefix_ & 0x3ff) == 0,
295            &mut self.cmd_prefix_,
296        );
297    }
298
299    pub fn new(
300        dist: &BrotliDistanceParams,
301        insertlen: usize,
302        copylen: usize,
303        copylen_code: usize,
304        distance_code: usize,
305    ) -> Self {
306        let mut cmd = Command {
307            insert_len_: insertlen as u32,
308            copy_len_: (copylen | ((copylen_code ^ copylen) << 25)) as u32,
309            dist_extra_: 0,
310            cmd_prefix_: 0,
311            dist_prefix_: 0,
312        };
313        cmd.init(dist, insertlen, copylen, copylen_code, distance_code);
314        cmd
315    }
316}
317
318#[cfg(test)]
319mod test {
320    // returns which distance code to use ( 0 means none, 1 means last, 2 means penultimate, 3 means the prior to penultimate
321    pub fn helperCommandDistanceIndexAndOffset(
322        cmd: &super::Command,
323        dist: &super::BrotliDistanceParams,
324    ) -> (usize, isize) {
325        let n_postfix = dist.distance_postfix_bits;
326        let n_direct = dist.num_direct_distance_codes;
327        let dextra = cmd.dist_extra_;
328        let dist_prefix = cmd.dist_prefix_ & 0x3ff;
329        if dist_prefix < 16 {
330            let table: [(usize, isize); 16] = [
331                (1, 0),
332                (2, 0),
333                (3, 0),
334                (4, 0),
335                (1, -1),
336                (1, 1),
337                (1, -2),
338                (1, 2),
339                (1, -3),
340                (1, 3),
341                (2, -1),
342                (2, 1),
343                (2, -2),
344                (2, 2),
345                (2, -3),
346                (2, 3),
347            ];
348            return table[cmd.dist_prefix_ as usize];
349        }
350        if (dist_prefix as usize) < 16 + n_direct as usize {
351            return (0, dist_prefix as isize + 1 - 16);
352        }
353        let postfix_mask = (1 << n_postfix) - 1;
354        let dcode = dist_prefix as u32 - 16 - n_direct;
355        let n_dist_bits = 1 + (dcode >> (n_postfix + 1));
356
357        let hcode = dcode >> n_postfix;
358        let lcode = dcode & postfix_mask;
359        let offset = ((2 + (hcode & 1)) << n_dist_bits) - 4;
360        (
361            0,
362            (((offset + dextra) << n_postfix) + lcode + n_direct + 1) as isize,
363        )
364    }
365    #[test]
366    fn test_command_return_distance_index_offset() {
367        let param = super::BrotliDistanceParams {
368            distance_postfix_bits: 2,
369            num_direct_distance_codes: 16,
370            alphabet_size: 224,
371            max_distance: 268435456,
372        };
373        let mut cmd = super::Command::default();
374        cmd.insert_len_ = 63;
375        cmd.copy_len_ = 3;
376        cmd.dist_extra_ = 3;
377        cmd.cmd_prefix_ = 297;
378        cmd.dist_prefix_ = 2089;
379
380        assert_eq!(cmd.distance_index_and_offset(&param), (0, 46));
381        assert_eq!(
382            cmd.distance_index_and_offset(&param),
383            helperCommandDistanceIndexAndOffset(&cmd, &param)
384        );
385        cmd = super::Command {
386            insert_len_: 27,
387            copy_len_: 3,
388            dist_extra_: 0,
389            cmd_prefix_: 281,
390            dist_prefix_: 6,
391        };
392        assert_eq!(cmd.distance_index_and_offset(&param), (1, -2));
393        assert_eq!(
394            cmd.distance_index_and_offset(&param),
395            helperCommandDistanceIndexAndOffset(&cmd, &param)
396        );
397        cmd = super::Command {
398            insert_len_: 1,
399            copy_len_: 3,
400            dist_extra_: 0,
401            cmd_prefix_: 137,
402            dist_prefix_: 27,
403        };
404        assert_eq!(cmd.distance_index_and_offset(&param), (0, 12));
405        assert_eq!(
406            cmd.distance_index_and_offset(&param),
407            helperCommandDistanceIndexAndOffset(&cmd, &param)
408        );
409        cmd = super::Command {
410            insert_len_: 5,
411            copy_len_: 4,
412            dist_extra_: 297,
413            cmd_prefix_: 170,
414            dist_prefix_: 11377,
415        };
416        assert_eq!(cmd.distance_index_and_offset(&param), (0, 17574));
417        assert_eq!(
418            cmd.distance_index_and_offset(&param),
419            helperCommandDistanceIndexAndOffset(&cmd, &param)
420        );
421        cmd.init_insert(24);
422        assert_eq!(cmd.distance_index_and_offset(&param), (0, 1));
423    }
424    /*
425    #[test]
426    fn test_restore_distance_code() {
427        for dist_code in 0..50000 {
428            let mut cmd = super::Command::default();
429            let param =super::BrotliDistanceParams{
430                distance_postfix_bits:2,
431                num_direct_distance_codes:16,
432                alphabet_size:224,
433                max_distance:268435456,
434            };
435            super::InitCommand(&mut cmd, &param, 4, 4, 4, dist_code);
436            let exp_dist_code = super::CommandRestoreDistanceCode(&cmd, &param);
437            assert_eq!(exp_dist_code as u32, dist_code as u32);
438        }
439    }*/
440}
brotli/enc/command.rs

brotli/enc/
command.rs
