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