1 | /* Copyright 2015 Google Inc. All Rights Reserved. |
2 | |
3 | Distributed under MIT license. |
4 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
5 | */ |
6 | |
7 | /* Function for fast encoding of an input fragment, independently from the input |
8 | history. This function uses two-pass processing: in the first pass we save |
9 | the found backward matches and literal bytes into a buffer, and in the |
10 | second pass we emit them into the bit stream using prefix codes built based |
11 | on the actual command and literal byte histograms. */ |
12 | |
13 | #include "./compress_fragment_two_pass.h" |
14 | |
15 | #include <string.h> /* memcmp, memcpy, memset */ |
16 | |
17 | #include "../common/constants.h" |
18 | #include "../common/platform.h" |
19 | #include <brotli/types.h> |
20 | #include "./bit_cost.h" |
21 | #include "./brotli_bit_stream.h" |
22 | #include "./entropy_encode.h" |
23 | #include "./fast_log.h" |
24 | #include "./find_match_length.h" |
25 | #include "./memory.h" |
26 | #include "./write_bits.h" |
27 | |
28 | #if defined(__cplusplus) || defined(c_plusplus) |
29 | extern "C" { |
30 | #endif |
31 | |
32 | #define MAX_DISTANCE (long)BROTLI_MAX_BACKWARD_LIMIT(18) |
33 | |
34 | /* kHashMul32 multiplier has these properties: |
35 | * The multiplier must be odd. Otherwise we may lose the highest bit. |
36 | * No long streaks of ones or zeros. |
37 | * There is no effort to ensure that it is a prime, the oddity is enough |
38 | for this use. |
39 | * The number has been tuned heuristically against compression benchmarks. */ |
40 | static const uint32_t kHashMul32 = 0x1E35A7BD; |
41 | |
42 | static BROTLI_INLINE uint32_t Hash(const uint8_t* p, |
43 | size_t shift, size_t length) { |
44 | const uint64_t h = |
45 | (BROTLI_UNALIGNED_LOAD64LE(p) << ((8 - length) * 8)) * kHashMul32; |
46 | return (uint32_t)(h >> shift); |
47 | } |
48 | |
49 | static BROTLI_INLINE uint32_t HashBytesAtOffset(uint64_t v, size_t offset, |
50 | size_t shift, size_t length) { |
51 | BROTLI_DCHECK(offset <= 8 - length); |
52 | { |
53 | const uint64_t h = ((v >> (8 * offset)) << ((8 - length) * 8)) * kHashMul32; |
54 | return (uint32_t)(h >> shift); |
55 | } |
56 | } |
57 | |
58 | static BROTLI_INLINE BROTLI_BOOL IsMatch(const uint8_t* p1, const uint8_t* p2, |
59 | size_t length) { |
60 | if (BrotliUnalignedRead32(p1) == BrotliUnalignedRead32(p2)) { |
61 | if (length == 4) return BROTLI_TRUE; |
62 | return TO_BROTLI_BOOL(p1[4] == p2[4] && p1[5] == p2[5]); |
63 | } |
64 | return BROTLI_FALSE; |
65 | } |
66 | |
67 | /* Builds a command and distance prefix code (each 64 symbols) into "depth" and |
68 | "bits" based on "histogram" and stores it into the bit stream. */ |
69 | static void BuildAndStoreCommandPrefixCode( |
70 | const uint32_t histogram[128], |
71 | uint8_t depth[128], uint16_t bits[128], |
72 | size_t* storage_ix, uint8_t* storage) { |
73 | /* Tree size for building a tree over 64 symbols is 2 * 64 + 1. */ |
74 | HuffmanTree tree[129]; |
75 | uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS] = { 0 }; |
76 | uint16_t cmd_bits[64]; |
77 | BrotliCreateHuffmanTree(histogram, 64, 15, tree, depth); |
78 | BrotliCreateHuffmanTree(&histogram[64], 64, 14, tree, &depth[64]); |
79 | /* We have to jump through a few hoops here in order to compute |
80 | the command bits because the symbols are in a different order than in |
81 | the full alphabet. This looks complicated, but having the symbols |
82 | in this order in the command bits saves a few branches in the Emit* |
83 | functions. */ |
84 | memcpy(cmd_depth, depth + 24, 24); |
85 | memcpy(cmd_depth + 24, depth, 8); |
86 | memcpy(cmd_depth + 32, depth + 48, 8); |
87 | memcpy(cmd_depth + 40, depth + 8, 8); |
88 | memcpy(cmd_depth + 48, depth + 56, 8); |
89 | memcpy(cmd_depth + 56, depth + 16, 8); |
90 | BrotliConvertBitDepthsToSymbols(cmd_depth, 64, cmd_bits); |
91 | memcpy(bits, cmd_bits + 24, 16); |
92 | memcpy(bits + 8, cmd_bits + 40, 16); |
93 | memcpy(bits + 16, cmd_bits + 56, 16); |
94 | memcpy(bits + 24, cmd_bits, 48); |
95 | memcpy(bits + 48, cmd_bits + 32, 16); |
96 | memcpy(bits + 56, cmd_bits + 48, 16); |
97 | BrotliConvertBitDepthsToSymbols(&depth[64], 64, &bits[64]); |
98 | { |
99 | /* Create the bit length array for the full command alphabet. */ |
100 | size_t i; |
101 | memset(cmd_depth, 0, 64); /* only 64 first values were used */ |
102 | memcpy(cmd_depth, depth + 24, 8); |
103 | memcpy(cmd_depth + 64, depth + 32, 8); |
104 | memcpy(cmd_depth + 128, depth + 40, 8); |
105 | memcpy(cmd_depth + 192, depth + 48, 8); |
106 | memcpy(cmd_depth + 384, depth + 56, 8); |
107 | for (i = 0; i < 8; ++i) { |
108 | cmd_depth[128 + 8 * i] = depth[i]; |
109 | cmd_depth[256 + 8 * i] = depth[8 + i]; |
110 | cmd_depth[448 + 8 * i] = depth[16 + i]; |
111 | } |
112 | BrotliStoreHuffmanTree( |
113 | cmd_depth, BROTLI_NUM_COMMAND_SYMBOLS, tree, storage_ix, storage); |
114 | } |
115 | BrotliStoreHuffmanTree(&depth[64], 64, tree, storage_ix, storage); |
116 | } |
117 | |
118 | static BROTLI_INLINE void EmitInsertLen( |
119 | uint32_t insertlen, uint32_t** commands) { |
120 | if (insertlen < 6) { |
121 | **commands = insertlen; |
122 | } else if (insertlen < 130) { |
123 | const uint32_t tail = insertlen - 2; |
124 | const uint32_t nbits = Log2FloorNonZero(tail) - 1u; |
125 | const uint32_t prefix = tail >> nbits; |
126 | const uint32_t inscode = (nbits << 1) + prefix + 2; |
127 | const uint32_t = tail - (prefix << nbits); |
128 | **commands = inscode | (extra << 8); |
129 | } else if (insertlen < 2114) { |
130 | const uint32_t tail = insertlen - 66; |
131 | const uint32_t nbits = Log2FloorNonZero(tail); |
132 | const uint32_t code = nbits + 10; |
133 | const uint32_t = tail - (1u << nbits); |
134 | **commands = code | (extra << 8); |
135 | } else if (insertlen < 6210) { |
136 | const uint32_t = insertlen - 2114; |
137 | **commands = 21 | (extra << 8); |
138 | } else if (insertlen < 22594) { |
139 | const uint32_t = insertlen - 6210; |
140 | **commands = 22 | (extra << 8); |
141 | } else { |
142 | const uint32_t = insertlen - 22594; |
143 | **commands = 23 | (extra << 8); |
144 | } |
145 | ++(*commands); |
146 | } |
147 | |
148 | static BROTLI_INLINE void EmitCopyLen(size_t copylen, uint32_t** commands) { |
149 | if (copylen < 10) { |
150 | **commands = (uint32_t)(copylen + 38); |
151 | } else if (copylen < 134) { |
152 | const size_t tail = copylen - 6; |
153 | const size_t nbits = Log2FloorNonZero(tail) - 1; |
154 | const size_t prefix = tail >> nbits; |
155 | const size_t code = (nbits << 1) + prefix + 44; |
156 | const size_t = tail - (prefix << nbits); |
157 | **commands = (uint32_t)(code | (extra << 8)); |
158 | } else if (copylen < 2118) { |
159 | const size_t tail = copylen - 70; |
160 | const size_t nbits = Log2FloorNonZero(tail); |
161 | const size_t code = nbits + 52; |
162 | const size_t = tail - ((size_t)1 << nbits); |
163 | **commands = (uint32_t)(code | (extra << 8)); |
164 | } else { |
165 | const size_t = copylen - 2118; |
166 | **commands = (uint32_t)(63 | (extra << 8)); |
167 | } |
168 | ++(*commands); |
169 | } |
170 | |
171 | static BROTLI_INLINE void EmitCopyLenLastDistance( |
172 | size_t copylen, uint32_t** commands) { |
173 | if (copylen < 12) { |
174 | **commands = (uint32_t)(copylen + 20); |
175 | ++(*commands); |
176 | } else if (copylen < 72) { |
177 | const size_t tail = copylen - 8; |
178 | const size_t nbits = Log2FloorNonZero(tail) - 1; |
179 | const size_t prefix = tail >> nbits; |
180 | const size_t code = (nbits << 1) + prefix + 28; |
181 | const size_t = tail - (prefix << nbits); |
182 | **commands = (uint32_t)(code | (extra << 8)); |
183 | ++(*commands); |
184 | } else if (copylen < 136) { |
185 | const size_t tail = copylen - 8; |
186 | const size_t code = (tail >> 5) + 54; |
187 | const size_t = tail & 31; |
188 | **commands = (uint32_t)(code | (extra << 8)); |
189 | ++(*commands); |
190 | **commands = 64; |
191 | ++(*commands); |
192 | } else if (copylen < 2120) { |
193 | const size_t tail = copylen - 72; |
194 | const size_t nbits = Log2FloorNonZero(tail); |
195 | const size_t code = nbits + 52; |
196 | const size_t = tail - ((size_t)1 << nbits); |
197 | **commands = (uint32_t)(code | (extra << 8)); |
198 | ++(*commands); |
199 | **commands = 64; |
200 | ++(*commands); |
201 | } else { |
202 | const size_t = copylen - 2120; |
203 | **commands = (uint32_t)(63 | (extra << 8)); |
204 | ++(*commands); |
205 | **commands = 64; |
206 | ++(*commands); |
207 | } |
208 | } |
209 | |
210 | static BROTLI_INLINE void EmitDistance(uint32_t distance, uint32_t** commands) { |
211 | uint32_t d = distance + 3; |
212 | uint32_t nbits = Log2FloorNonZero(d) - 1; |
213 | const uint32_t prefix = (d >> nbits) & 1; |
214 | const uint32_t offset = (2 + prefix) << nbits; |
215 | const uint32_t distcode = 2 * (nbits - 1) + prefix + 80; |
216 | uint32_t = d - offset; |
217 | **commands = distcode | (extra << 8); |
218 | ++(*commands); |
219 | } |
220 | |
221 | /* REQUIRES: len <= 1 << 24. */ |
222 | static void ( |
223 | size_t len, BROTLI_BOOL is_uncompressed, size_t* storage_ix, |
224 | uint8_t* storage) { |
225 | size_t nibbles = 6; |
226 | /* ISLAST */ |
227 | BrotliWriteBits(1, 0, storage_ix, storage); |
228 | if (len <= (1U << 16)) { |
229 | nibbles = 4; |
230 | } else if (len <= (1U << 20)) { |
231 | nibbles = 5; |
232 | } |
233 | BrotliWriteBits(2, nibbles - 4, storage_ix, storage); |
234 | BrotliWriteBits(nibbles * 4, len - 1, storage_ix, storage); |
235 | /* ISUNCOMPRESSED */ |
236 | BrotliWriteBits(1, (uint64_t)is_uncompressed, storage_ix, storage); |
237 | } |
238 | |
239 | static BROTLI_INLINE void CreateCommands(const uint8_t* input, |
240 | size_t block_size, size_t input_size, const uint8_t* base_ip, int* table, |
241 | size_t table_bits, size_t min_match, |
242 | uint8_t** literals, uint32_t** commands) { |
243 | /* "ip" is the input pointer. */ |
244 | const uint8_t* ip = input; |
245 | const size_t shift = 64u - table_bits; |
246 | const uint8_t* ip_end = input + block_size; |
247 | /* "next_emit" is a pointer to the first byte that is not covered by a |
248 | previous copy. Bytes between "next_emit" and the start of the next copy or |
249 | the end of the input will be emitted as literal bytes. */ |
250 | const uint8_t* next_emit = input; |
251 | |
252 | int last_distance = -1; |
253 | const size_t kInputMarginBytes = BROTLI_WINDOW_GAP; |
254 | |
255 | if (BROTLI_PREDICT_TRUE(block_size >= kInputMarginBytes)) { |
256 | /* For the last block, we need to keep a 16 bytes margin so that we can be |
257 | sure that all distances are at most window size - 16. |
258 | For all other blocks, we only need to keep a margin of 5 bytes so that |
259 | we don't go over the block size with a copy. */ |
260 | const size_t len_limit = BROTLI_MIN(size_t, block_size - min_match, |
261 | input_size - kInputMarginBytes); |
262 | const uint8_t* ip_limit = input + len_limit; |
263 | |
264 | uint32_t next_hash; |
265 | for (next_hash = Hash(++ip, shift, min_match); ; ) { |
266 | /* Step 1: Scan forward in the input looking for a 6-byte-long match. |
267 | If we get close to exhausting the input then goto emit_remainder. |
268 | |
269 | Heuristic match skipping: If 32 bytes are scanned with no matches |
270 | found, start looking only at every other byte. If 32 more bytes are |
271 | scanned, look at every third byte, etc.. When a match is found, |
272 | immediately go back to looking at every byte. This is a small loss |
273 | (~5% performance, ~0.1% density) for compressible data due to more |
274 | bookkeeping, but for non-compressible data (such as JPEG) it's a huge |
275 | win since the compressor quickly "realizes" the data is incompressible |
276 | and doesn't bother looking for matches everywhere. |
277 | |
278 | The "skip" variable keeps track of how many bytes there are since the |
279 | last match; dividing it by 32 (ie. right-shifting by five) gives the |
280 | number of bytes to move ahead for each iteration. */ |
281 | uint32_t skip = 32; |
282 | |
283 | const uint8_t* next_ip = ip; |
284 | const uint8_t* candidate; |
285 | |
286 | BROTLI_DCHECK(next_emit < ip); |
287 | trawl: |
288 | do { |
289 | uint32_t hash = next_hash; |
290 | uint32_t bytes_between_hash_lookups = skip++ >> 5; |
291 | ip = next_ip; |
292 | BROTLI_DCHECK(hash == Hash(ip, shift, min_match)); |
293 | next_ip = ip + bytes_between_hash_lookups; |
294 | if (BROTLI_PREDICT_FALSE(next_ip > ip_limit)) { |
295 | goto emit_remainder; |
296 | } |
297 | next_hash = Hash(next_ip, shift, min_match); |
298 | candidate = ip - last_distance; |
299 | if (IsMatch(ip, candidate, min_match)) { |
300 | if (BROTLI_PREDICT_TRUE(candidate < ip)) { |
301 | table[hash] = (int)(ip - base_ip); |
302 | break; |
303 | } |
304 | } |
305 | candidate = base_ip + table[hash]; |
306 | BROTLI_DCHECK(candidate >= base_ip); |
307 | BROTLI_DCHECK(candidate < ip); |
308 | |
309 | table[hash] = (int)(ip - base_ip); |
310 | } while (BROTLI_PREDICT_TRUE(!IsMatch(ip, candidate, min_match))); |
311 | |
312 | /* Check copy distance. If candidate is not feasible, continue search. |
313 | Checking is done outside of hot loop to reduce overhead. */ |
314 | if (ip - candidate > MAX_DISTANCE) goto trawl; |
315 | |
316 | /* Step 2: Emit the found match together with the literal bytes from |
317 | "next_emit", and then see if we can find a next match immediately |
318 | afterwards. Repeat until we find no match for the input |
319 | without emitting some literal bytes. */ |
320 | |
321 | { |
322 | /* We have a 6-byte match at ip, and we need to emit bytes in |
323 | [next_emit, ip). */ |
324 | const uint8_t* base = ip; |
325 | size_t matched = min_match + FindMatchLengthWithLimit( |
326 | candidate + min_match, ip + min_match, |
327 | (size_t)(ip_end - ip) - min_match); |
328 | int distance = (int)(base - candidate); /* > 0 */ |
329 | int insert = (int)(base - next_emit); |
330 | ip += matched; |
331 | BROTLI_DCHECK(0 == memcmp(base, candidate, matched)); |
332 | EmitInsertLen((uint32_t)insert, commands); |
333 | memcpy(*literals, next_emit, (size_t)insert); |
334 | *literals += insert; |
335 | if (distance == last_distance) { |
336 | **commands = 64; |
337 | ++(*commands); |
338 | } else { |
339 | EmitDistance((uint32_t)distance, commands); |
340 | last_distance = distance; |
341 | } |
342 | EmitCopyLenLastDistance(matched, commands); |
343 | |
344 | next_emit = ip; |
345 | if (BROTLI_PREDICT_FALSE(ip >= ip_limit)) { |
346 | goto emit_remainder; |
347 | } |
348 | { |
349 | /* We could immediately start working at ip now, but to improve |
350 | compression we first update "table" with the hashes of some |
351 | positions within the last copy. */ |
352 | uint64_t input_bytes; |
353 | uint32_t cur_hash; |
354 | uint32_t prev_hash; |
355 | if (min_match == 4) { |
356 | input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 3); |
357 | cur_hash = HashBytesAtOffset(input_bytes, 3, shift, min_match); |
358 | prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match); |
359 | table[prev_hash] = (int)(ip - base_ip - 3); |
360 | prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match); |
361 | table[prev_hash] = (int)(ip - base_ip - 2); |
362 | prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match); |
363 | table[prev_hash] = (int)(ip - base_ip - 1); |
364 | } else { |
365 | input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 5); |
366 | prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match); |
367 | table[prev_hash] = (int)(ip - base_ip - 5); |
368 | prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match); |
369 | table[prev_hash] = (int)(ip - base_ip - 4); |
370 | prev_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match); |
371 | table[prev_hash] = (int)(ip - base_ip - 3); |
372 | input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 2); |
373 | cur_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match); |
374 | prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match); |
375 | table[prev_hash] = (int)(ip - base_ip - 2); |
376 | prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match); |
377 | table[prev_hash] = (int)(ip - base_ip - 1); |
378 | } |
379 | |
380 | candidate = base_ip + table[cur_hash]; |
381 | table[cur_hash] = (int)(ip - base_ip); |
382 | } |
383 | } |
384 | |
385 | while (ip - candidate <= MAX_DISTANCE && |
386 | IsMatch(ip, candidate, min_match)) { |
387 | /* We have a 6-byte match at ip, and no need to emit any |
388 | literal bytes prior to ip. */ |
389 | const uint8_t* base = ip; |
390 | size_t matched = min_match + FindMatchLengthWithLimit( |
391 | candidate + min_match, ip + min_match, |
392 | (size_t)(ip_end - ip) - min_match); |
393 | ip += matched; |
394 | last_distance = (int)(base - candidate); /* > 0 */ |
395 | BROTLI_DCHECK(0 == memcmp(base, candidate, matched)); |
396 | EmitCopyLen(matched, commands); |
397 | EmitDistance((uint32_t)last_distance, commands); |
398 | |
399 | next_emit = ip; |
400 | if (BROTLI_PREDICT_FALSE(ip >= ip_limit)) { |
401 | goto emit_remainder; |
402 | } |
403 | { |
404 | /* We could immediately start working at ip now, but to improve |
405 | compression we first update "table" with the hashes of some |
406 | positions within the last copy. */ |
407 | uint64_t input_bytes; |
408 | uint32_t cur_hash; |
409 | uint32_t prev_hash; |
410 | if (min_match == 4) { |
411 | input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 3); |
412 | cur_hash = HashBytesAtOffset(input_bytes, 3, shift, min_match); |
413 | prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match); |
414 | table[prev_hash] = (int)(ip - base_ip - 3); |
415 | prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match); |
416 | table[prev_hash] = (int)(ip - base_ip - 2); |
417 | prev_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match); |
418 | table[prev_hash] = (int)(ip - base_ip - 1); |
419 | } else { |
420 | input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 5); |
421 | prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match); |
422 | table[prev_hash] = (int)(ip - base_ip - 5); |
423 | prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match); |
424 | table[prev_hash] = (int)(ip - base_ip - 4); |
425 | prev_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match); |
426 | table[prev_hash] = (int)(ip - base_ip - 3); |
427 | input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 2); |
428 | cur_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match); |
429 | prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match); |
430 | table[prev_hash] = (int)(ip - base_ip - 2); |
431 | prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match); |
432 | table[prev_hash] = (int)(ip - base_ip - 1); |
433 | } |
434 | |
435 | candidate = base_ip + table[cur_hash]; |
436 | table[cur_hash] = (int)(ip - base_ip); |
437 | } |
438 | } |
439 | |
440 | next_hash = Hash(++ip, shift, min_match); |
441 | } |
442 | } |
443 | |
444 | emit_remainder: |
445 | BROTLI_DCHECK(next_emit <= ip_end); |
446 | /* Emit the remaining bytes as literals. */ |
447 | if (next_emit < ip_end) { |
448 | const uint32_t insert = (uint32_t)(ip_end - next_emit); |
449 | EmitInsertLen(insert, commands); |
450 | memcpy(*literals, next_emit, insert); |
451 | *literals += insert; |
452 | } |
453 | } |
454 | |
455 | static void StoreCommands(MemoryManager* m, |
456 | const uint8_t* literals, const size_t num_literals, |
457 | const uint32_t* commands, const size_t num_commands, |
458 | size_t* storage_ix, uint8_t* storage) { |
459 | static const uint32_t [128] = { |
460 | 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 12, 14, 24, |
461 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, |
462 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 24, |
463 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
464 | 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, |
465 | 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, |
466 | 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, |
467 | }; |
468 | static const uint32_t kInsertOffset[24] = { |
469 | 0, 1, 2, 3, 4, 5, 6, 8, 10, 14, 18, 26, 34, 50, 66, 98, 130, 194, 322, 578, |
470 | 1090, 2114, 6210, 22594, |
471 | }; |
472 | |
473 | uint8_t lit_depths[256]; |
474 | uint16_t lit_bits[256]; |
475 | uint32_t lit_histo[256] = { 0 }; |
476 | uint8_t cmd_depths[128] = { 0 }; |
477 | uint16_t cmd_bits[128] = { 0 }; |
478 | uint32_t cmd_histo[128] = { 0 }; |
479 | size_t i; |
480 | for (i = 0; i < num_literals; ++i) { |
481 | ++lit_histo[literals[i]]; |
482 | } |
483 | BrotliBuildAndStoreHuffmanTreeFast(m, lit_histo, num_literals, |
484 | /* max_bits = */ 8, |
485 | lit_depths, lit_bits, |
486 | storage_ix, storage); |
487 | if (BROTLI_IS_OOM(m)) return; |
488 | |
489 | for (i = 0; i < num_commands; ++i) { |
490 | const uint32_t code = commands[i] & 0xFF; |
491 | BROTLI_DCHECK(code < 128); |
492 | ++cmd_histo[code]; |
493 | } |
494 | cmd_histo[1] += 1; |
495 | cmd_histo[2] += 1; |
496 | cmd_histo[64] += 1; |
497 | cmd_histo[84] += 1; |
498 | BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depths, cmd_bits, |
499 | storage_ix, storage); |
500 | |
501 | for (i = 0; i < num_commands; ++i) { |
502 | const uint32_t cmd = commands[i]; |
503 | const uint32_t code = cmd & 0xFF; |
504 | const uint32_t = cmd >> 8; |
505 | BROTLI_DCHECK(code < 128); |
506 | BrotliWriteBits(cmd_depths[code], cmd_bits[code], storage_ix, storage); |
507 | BrotliWriteBits(kNumExtraBits[code], extra, storage_ix, storage); |
508 | if (code < 24) { |
509 | const uint32_t insert = kInsertOffset[code] + extra; |
510 | uint32_t j; |
511 | for (j = 0; j < insert; ++j) { |
512 | const uint8_t lit = *literals; |
513 | BrotliWriteBits(lit_depths[lit], lit_bits[lit], storage_ix, storage); |
514 | ++literals; |
515 | } |
516 | } |
517 | } |
518 | } |
519 | |
520 | /* Acceptable loss for uncompressible speedup is 2% */ |
521 | #define MIN_RATIO 0.98 |
522 | #define SAMPLE_RATE 43 |
523 | |
524 | static BROTLI_BOOL ShouldCompress( |
525 | const uint8_t* input, size_t input_size, size_t num_literals) { |
526 | double corpus_size = (double)input_size; |
527 | if (num_literals < MIN_RATIO * corpus_size) { |
528 | return BROTLI_TRUE; |
529 | } else { |
530 | uint32_t literal_histo[256] = { 0 }; |
531 | const double max_total_bit_cost = corpus_size * 8 * MIN_RATIO / SAMPLE_RATE; |
532 | size_t i; |
533 | for (i = 0; i < input_size; i += SAMPLE_RATE) { |
534 | ++literal_histo[input[i]]; |
535 | } |
536 | return TO_BROTLI_BOOL(BitsEntropy(literal_histo, 256) < max_total_bit_cost); |
537 | } |
538 | } |
539 | |
540 | static void RewindBitPosition(const size_t new_storage_ix, |
541 | size_t* storage_ix, uint8_t* storage) { |
542 | const size_t bitpos = new_storage_ix & 7; |
543 | const size_t mask = (1u << bitpos) - 1; |
544 | storage[new_storage_ix >> 3] &= (uint8_t)mask; |
545 | *storage_ix = new_storage_ix; |
546 | } |
547 | |
548 | static void EmitUncompressedMetaBlock(const uint8_t* input, size_t input_size, |
549 | size_t* storage_ix, uint8_t* storage) { |
550 | BrotliStoreMetaBlockHeader(input_size, 1, storage_ix, storage); |
551 | *storage_ix = (*storage_ix + 7u) & ~7u; |
552 | memcpy(&storage[*storage_ix >> 3], input, input_size); |
553 | *storage_ix += input_size << 3; |
554 | storage[*storage_ix >> 3] = 0; |
555 | } |
556 | |
557 | static BROTLI_INLINE void BrotliCompressFragmentTwoPassImpl( |
558 | MemoryManager* m, const uint8_t* input, size_t input_size, |
559 | BROTLI_BOOL is_last, uint32_t* command_buf, uint8_t* literal_buf, |
560 | int* table, size_t table_bits, size_t min_match, |
561 | size_t* storage_ix, uint8_t* storage) { |
562 | /* Save the start of the first block for position and distance computations. |
563 | */ |
564 | const uint8_t* base_ip = input; |
565 | BROTLI_UNUSED(is_last); |
566 | |
567 | while (input_size > 0) { |
568 | size_t block_size = |
569 | BROTLI_MIN(size_t, input_size, kCompressFragmentTwoPassBlockSize); |
570 | uint32_t* commands = command_buf; |
571 | uint8_t* literals = literal_buf; |
572 | size_t num_literals; |
573 | CreateCommands(input, block_size, input_size, base_ip, table, |
574 | table_bits, min_match, &literals, &commands); |
575 | num_literals = (size_t)(literals - literal_buf); |
576 | if (ShouldCompress(input, block_size, num_literals)) { |
577 | const size_t num_commands = (size_t)(commands - command_buf); |
578 | BrotliStoreMetaBlockHeader(block_size, 0, storage_ix, storage); |
579 | /* No block splits, no contexts. */ |
580 | BrotliWriteBits(13, 0, storage_ix, storage); |
581 | StoreCommands(m, literal_buf, num_literals, command_buf, num_commands, |
582 | storage_ix, storage); |
583 | if (BROTLI_IS_OOM(m)) return; |
584 | } else { |
585 | /* Since we did not find many backward references and the entropy of |
586 | the data is close to 8 bits, we can simply emit an uncompressed block. |
587 | This makes compression speed of uncompressible data about 3x faster. */ |
588 | EmitUncompressedMetaBlock(input, block_size, storage_ix, storage); |
589 | } |
590 | input += block_size; |
591 | input_size -= block_size; |
592 | } |
593 | } |
594 | |
595 | #define FOR_TABLE_BITS_(X) \ |
596 | X(8) X(9) X(10) X(11) X(12) X(13) X(14) X(15) X(16) X(17) |
597 | |
598 | #define BAKE_METHOD_PARAM_(B) \ |
599 | static BROTLI_NOINLINE void BrotliCompressFragmentTwoPassImpl ## B( \ |
600 | MemoryManager* m, const uint8_t* input, size_t input_size, \ |
601 | BROTLI_BOOL is_last, uint32_t* command_buf, uint8_t* literal_buf, \ |
602 | int* table, size_t* storage_ix, uint8_t* storage) { \ |
603 | size_t min_match = (B <= 15) ? 4 : 6; \ |
604 | BrotliCompressFragmentTwoPassImpl(m, input, input_size, is_last, command_buf,\ |
605 | literal_buf, table, B, min_match, storage_ix, storage); \ |
606 | } |
607 | FOR_TABLE_BITS_(BAKE_METHOD_PARAM_) |
608 | #undef BAKE_METHOD_PARAM_ |
609 | |
610 | void BrotliCompressFragmentTwoPass( |
611 | MemoryManager* m, const uint8_t* input, size_t input_size, |
612 | BROTLI_BOOL is_last, uint32_t* command_buf, uint8_t* literal_buf, |
613 | int* table, size_t table_size, size_t* storage_ix, uint8_t* storage) { |
614 | const size_t initial_storage_ix = *storage_ix; |
615 | const size_t table_bits = Log2FloorNonZero(table_size); |
616 | switch (table_bits) { |
617 | #define CASE_(B) \ |
618 | case B: \ |
619 | BrotliCompressFragmentTwoPassImpl ## B( \ |
620 | m, input, input_size, is_last, command_buf, \ |
621 | literal_buf, table, storage_ix, storage); \ |
622 | break; |
623 | FOR_TABLE_BITS_(CASE_) |
624 | #undef CASE_ |
625 | default: BROTLI_DCHECK(0); break; |
626 | } |
627 | |
628 | /* If output is larger than single uncompressed block, rewrite it. */ |
629 | if (*storage_ix - initial_storage_ix > 31 + (input_size << 3)) { |
630 | RewindBitPosition(initial_storage_ix, storage_ix, storage); |
631 | EmitUncompressedMetaBlock(input, input_size, storage_ix, storage); |
632 | } |
633 | |
634 | if (is_last) { |
635 | BrotliWriteBits(1, 1, storage_ix, storage); /* islast */ |
636 | BrotliWriteBits(1, 1, storage_ix, storage); /* isempty */ |
637 | *storage_ix = (*storage_ix + 7u) & ~7u; |
638 | } |
639 | } |
640 | |
641 | #undef FOR_TABLE_BITS_ |
642 | |
643 | #if defined(__cplusplus) || defined(c_plusplus) |
644 | } /* extern "C" */ |
645 | #endif |
646 | |