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