]>
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 one-pass processing: when we find a backward\r | |
9 | match, we immediately emit the corresponding command and literal codes to\r | |
10 | the bit stream.\r | |
11 | \r | |
12 | Adapted from the CompressFragment() function in\r | |
13 | https://github.com/google/snappy/blob/master/snappy.cc */\r | |
14 | \r | |
15 | #include "./compress_fragment.h"\r | |
16 | \r | |
17 | #include <string.h> /* memcmp, memcpy, memset */\r | |
18 | \r | |
19 | #include "../common/types.h"\r | |
20 | #include "./brotli_bit_stream.h"\r | |
21 | #include "./entropy_encode.h"\r | |
22 | #include "./fast_log.h"\r | |
23 | #include "./find_match_length.h"\r | |
24 | #include "./memory.h"\r | |
25 | #include "./port.h"\r | |
26 | #include "./write_bits.h"\r | |
27 | \r | |
28 | \r | |
29 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
30 | extern "C" {\r | |
31 | #endif\r | |
32 | \r | |
33 | /* kHashMul32 multiplier has these properties:\r | |
34 | * The multiplier must be odd. Otherwise we may lose the highest bit.\r | |
35 | * No long streaks of 1s or 0s.\r | |
36 | * There is no effort to ensure that it is a prime, the oddity is enough\r | |
37 | for this use.\r | |
38 | * The number has been tuned heuristically against compression benchmarks. */\r | |
39 | static const uint32_t kHashMul32 = 0x1e35a7bd;\r | |
40 | \r | |
41 | static BROTLI_INLINE uint32_t Hash(const uint8_t* p, size_t shift) {\r | |
42 | const uint64_t h = (BROTLI_UNALIGNED_LOAD64(p) << 24) * kHashMul32;\r | |
43 | return (uint32_t)(h >> shift);\r | |
44 | }\r | |
45 | \r | |
46 | static BROTLI_INLINE uint32_t HashBytesAtOffset(\r | |
47 | uint64_t v, int offset, size_t shift) {\r | |
48 | assert(offset >= 0);\r | |
49 | assert(offset <= 3);\r | |
50 | {\r | |
51 | const uint64_t h = ((v >> (8 * offset)) << 24) * kHashMul32;\r | |
52 | return (uint32_t)(h >> shift);\r | |
53 | }\r | |
54 | }\r | |
55 | \r | |
56 | static BROTLI_INLINE BROTLI_BOOL IsMatch(const uint8_t* p1, const uint8_t* p2) {\r | |
57 | return TO_BROTLI_BOOL(\r | |
58 | BROTLI_UNALIGNED_LOAD32(p1) == BROTLI_UNALIGNED_LOAD32(p2) &&\r | |
59 | p1[4] == p2[4]);\r | |
60 | }\r | |
61 | \r | |
62 | /* Builds a literal prefix code into "depths" and "bits" based on the statistics\r | |
63 | of the "input" string and stores it into the bit stream.\r | |
64 | Note that the prefix code here is built from the pre-LZ77 input, therefore\r | |
65 | we can only approximate the statistics of the actual literal stream.\r | |
66 | Moreover, for long inputs we build a histogram from a sample of the input\r | |
67 | and thus have to assign a non-zero depth for each literal.\r | |
68 | Returns estimated compression ratio millibytes/char for encoding given input\r | |
69 | with generated code. */\r | |
70 | static size_t BuildAndStoreLiteralPrefixCode(MemoryManager* m,\r | |
71 | const uint8_t* input,\r | |
72 | const size_t input_size,\r | |
73 | uint8_t depths[256],\r | |
74 | uint16_t bits[256],\r | |
75 | size_t* storage_ix,\r | |
76 | uint8_t* storage) {\r | |
77 | uint32_t histogram[256] = { 0 };\r | |
78 | size_t histogram_total;\r | |
79 | size_t i;\r | |
80 | if (input_size < (1 << 15)) {\r | |
81 | for (i = 0; i < input_size; ++i) {\r | |
82 | ++histogram[input[i]];\r | |
83 | }\r | |
84 | histogram_total = input_size;\r | |
85 | for (i = 0; i < 256; ++i) {\r | |
86 | /* We weigh the first 11 samples with weight 3 to account for the\r | |
87 | balancing effect of the LZ77 phase on the histogram. */\r | |
88 | const uint32_t adjust = 2 * BROTLI_MIN(uint32_t, histogram[i], 11u);\r | |
89 | histogram[i] += adjust;\r | |
90 | histogram_total += adjust;\r | |
91 | }\r | |
92 | } else {\r | |
93 | static const size_t kSampleRate = 29;\r | |
94 | for (i = 0; i < input_size; i += kSampleRate) {\r | |
95 | ++histogram[input[i]];\r | |
96 | }\r | |
97 | histogram_total = (input_size + kSampleRate - 1) / kSampleRate;\r | |
98 | for (i = 0; i < 256; ++i) {\r | |
99 | /* We add 1 to each population count to avoid 0 bit depths (since this is\r | |
100 | only a sample and we don't know if the symbol appears or not), and we\r | |
101 | weigh the first 11 samples with weight 3 to account for the balancing\r | |
102 | effect of the LZ77 phase on the histogram (more frequent symbols are\r | |
103 | more likely to be in backward references instead as literals). */\r | |
104 | const uint32_t adjust = 1 + 2 * BROTLI_MIN(uint32_t, histogram[i], 11u);\r | |
105 | histogram[i] += adjust;\r | |
106 | histogram_total += adjust;\r | |
107 | }\r | |
108 | }\r | |
109 | BrotliBuildAndStoreHuffmanTreeFast(m, histogram, histogram_total,\r | |
110 | /* max_bits = */ 8,\r | |
111 | depths, bits, storage_ix, storage);\r | |
112 | if (BROTLI_IS_OOM(m)) return 0;\r | |
113 | {\r | |
114 | size_t literal_ratio = 0;\r | |
115 | for (i = 0; i < 256; ++i) {\r | |
116 | if (histogram[i]) literal_ratio += histogram[i] * depths[i];\r | |
117 | }\r | |
118 | /* Estimated encoding ratio, millibytes per symbol. */\r | |
119 | return (literal_ratio * 125) / histogram_total;\r | |
120 | }\r | |
121 | }\r | |
122 | \r | |
123 | /* Builds a command and distance prefix code (each 64 symbols) into "depth" and\r | |
124 | "bits" based on "histogram" and stores it into the bit stream. */\r | |
125 | static void BuildAndStoreCommandPrefixCode(const uint32_t histogram[128],\r | |
126 | uint8_t depth[128], uint16_t bits[128], size_t* storage_ix,\r | |
127 | uint8_t* storage) {\r | |
128 | /* Tree size for building a tree over 64 symbols is 2 * 64 + 1. */\r | |
129 | HuffmanTree tree[129];\r | |
130 | uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS] = { 0 };\r | |
131 | uint16_t cmd_bits[64];\r | |
132 | \r | |
133 | BrotliCreateHuffmanTree(histogram, 64, 15, tree, depth);\r | |
134 | BrotliCreateHuffmanTree(&histogram[64], 64, 14, tree, &depth[64]);\r | |
135 | /* We have to jump through a few hoopes here in order to compute\r | |
136 | the command bits because the symbols are in a different order than in\r | |
137 | the full alphabet. This looks complicated, but having the symbols\r | |
138 | in this order in the command bits saves a few branches in the Emit*\r | |
139 | functions. */\r | |
140 | memcpy(cmd_depth, depth, 24);\r | |
141 | memcpy(cmd_depth + 24, depth + 40, 8);\r | |
142 | memcpy(cmd_depth + 32, depth + 24, 8);\r | |
143 | memcpy(cmd_depth + 40, depth + 48, 8);\r | |
144 | memcpy(cmd_depth + 48, depth + 32, 8);\r | |
145 | memcpy(cmd_depth + 56, depth + 56, 8);\r | |
146 | BrotliConvertBitDepthsToSymbols(cmd_depth, 64, cmd_bits);\r | |
147 | memcpy(bits, cmd_bits, 48);\r | |
148 | memcpy(bits + 24, cmd_bits + 32, 16);\r | |
149 | memcpy(bits + 32, cmd_bits + 48, 16);\r | |
150 | memcpy(bits + 40, cmd_bits + 24, 16);\r | |
151 | memcpy(bits + 48, cmd_bits + 40, 16);\r | |
152 | memcpy(bits + 56, cmd_bits + 56, 16);\r | |
153 | BrotliConvertBitDepthsToSymbols(&depth[64], 64, &bits[64]);\r | |
154 | {\r | |
155 | /* Create the bit length array for the full command alphabet. */\r | |
156 | size_t i;\r | |
157 | memset(cmd_depth, 0, 64); /* only 64 first values were used */\r | |
158 | memcpy(cmd_depth, depth, 8);\r | |
159 | memcpy(cmd_depth + 64, depth + 8, 8);\r | |
160 | memcpy(cmd_depth + 128, depth + 16, 8);\r | |
161 | memcpy(cmd_depth + 192, depth + 24, 8);\r | |
162 | memcpy(cmd_depth + 384, depth + 32, 8);\r | |
163 | for (i = 0; i < 8; ++i) {\r | |
164 | cmd_depth[128 + 8 * i] = depth[40 + i];\r | |
165 | cmd_depth[256 + 8 * i] = depth[48 + i];\r | |
166 | cmd_depth[448 + 8 * i] = depth[56 + i];\r | |
167 | }\r | |
168 | BrotliStoreHuffmanTree(\r | |
169 | cmd_depth, BROTLI_NUM_COMMAND_SYMBOLS, tree, storage_ix, storage);\r | |
170 | }\r | |
171 | BrotliStoreHuffmanTree(&depth[64], 64, tree, storage_ix, storage);\r | |
172 | }\r | |
173 | \r | |
174 | /* REQUIRES: insertlen < 6210 */\r | |
175 | static BROTLI_INLINE void EmitInsertLen(size_t insertlen,\r | |
176 | const uint8_t depth[128],\r | |
177 | const uint16_t bits[128],\r | |
178 | uint32_t histo[128],\r | |
179 | size_t* storage_ix,\r | |
180 | uint8_t* storage) {\r | |
181 | if (insertlen < 6) {\r | |
182 | const size_t code = insertlen + 40;\r | |
183 | BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r | |
184 | ++histo[code];\r | |
185 | } else if (insertlen < 130) {\r | |
186 | const size_t tail = insertlen - 2;\r | |
187 | const uint32_t nbits = Log2FloorNonZero(tail) - 1u;\r | |
188 | const size_t prefix = tail >> nbits;\r | |
189 | const size_t inscode = (nbits << 1) + prefix + 42;\r | |
190 | BrotliWriteBits(depth[inscode], bits[inscode], storage_ix, storage);\r | |
191 | BrotliWriteBits(nbits, tail - (prefix << nbits), storage_ix, storage);\r | |
192 | ++histo[inscode];\r | |
193 | } else if (insertlen < 2114) {\r | |
194 | const size_t tail = insertlen - 66;\r | |
195 | const uint32_t nbits = Log2FloorNonZero(tail);\r | |
196 | const size_t code = nbits + 50;\r | |
197 | BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r | |
198 | BrotliWriteBits(nbits, tail - ((size_t)1 << nbits), storage_ix, storage);\r | |
199 | ++histo[code];\r | |
200 | } else {\r | |
201 | BrotliWriteBits(depth[61], bits[61], storage_ix, storage);\r | |
202 | BrotliWriteBits(12, insertlen - 2114, storage_ix, storage);\r | |
203 | ++histo[21];\r | |
204 | }\r | |
205 | }\r | |
206 | \r | |
207 | static BROTLI_INLINE void EmitLongInsertLen(size_t insertlen,\r | |
208 | const uint8_t depth[128],\r | |
209 | const uint16_t bits[128],\r | |
210 | uint32_t histo[128],\r | |
211 | size_t* storage_ix,\r | |
212 | uint8_t* storage) {\r | |
213 | if (insertlen < 22594) {\r | |
214 | BrotliWriteBits(depth[62], bits[62], storage_ix, storage);\r | |
215 | BrotliWriteBits(14, insertlen - 6210, storage_ix, storage);\r | |
216 | ++histo[22];\r | |
217 | } else {\r | |
218 | BrotliWriteBits(depth[63], bits[63], storage_ix, storage);\r | |
219 | BrotliWriteBits(24, insertlen - 22594, storage_ix, storage);\r | |
220 | ++histo[23];\r | |
221 | }\r | |
222 | }\r | |
223 | \r | |
224 | static BROTLI_INLINE void EmitCopyLen(size_t copylen,\r | |
225 | const uint8_t depth[128],\r | |
226 | const uint16_t bits[128],\r | |
227 | uint32_t histo[128],\r | |
228 | size_t* storage_ix,\r | |
229 | uint8_t* storage) {\r | |
230 | if (copylen < 10) {\r | |
231 | BrotliWriteBits(\r | |
232 | depth[copylen + 14], bits[copylen + 14], storage_ix, storage);\r | |
233 | ++histo[copylen + 14];\r | |
234 | } else if (copylen < 134) {\r | |
235 | const size_t tail = copylen - 6;\r | |
236 | const uint32_t nbits = Log2FloorNonZero(tail) - 1u;\r | |
237 | const size_t prefix = tail >> nbits;\r | |
238 | const size_t code = (nbits << 1) + prefix + 20;\r | |
239 | BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r | |
240 | BrotliWriteBits(nbits, tail - (prefix << nbits), storage_ix, storage);\r | |
241 | ++histo[code];\r | |
242 | } else if (copylen < 2118) {\r | |
243 | const size_t tail = copylen - 70;\r | |
244 | const uint32_t nbits = Log2FloorNonZero(tail);\r | |
245 | const size_t code = nbits + 28;\r | |
246 | BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r | |
247 | BrotliWriteBits(nbits, tail - ((size_t)1 << nbits), storage_ix, storage);\r | |
248 | ++histo[code];\r | |
249 | } else {\r | |
250 | BrotliWriteBits(depth[39], bits[39], storage_ix, storage);\r | |
251 | BrotliWriteBits(24, copylen - 2118, storage_ix, storage);\r | |
252 | ++histo[47];\r | |
253 | }\r | |
254 | }\r | |
255 | \r | |
256 | static BROTLI_INLINE void EmitCopyLenLastDistance(size_t copylen,\r | |
257 | const uint8_t depth[128],\r | |
258 | const uint16_t bits[128],\r | |
259 | uint32_t histo[128],\r | |
260 | size_t* storage_ix,\r | |
261 | uint8_t* storage) {\r | |
262 | if (copylen < 12) {\r | |
263 | BrotliWriteBits(depth[copylen - 4], bits[copylen - 4], storage_ix, storage);\r | |
264 | ++histo[copylen - 4];\r | |
265 | } else if (copylen < 72) {\r | |
266 | const size_t tail = copylen - 8;\r | |
267 | const uint32_t nbits = Log2FloorNonZero(tail) - 1;\r | |
268 | const size_t prefix = tail >> nbits;\r | |
269 | const size_t code = (nbits << 1) + prefix + 4;\r | |
270 | BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r | |
271 | BrotliWriteBits(nbits, tail - (prefix << nbits), storage_ix, storage);\r | |
272 | ++histo[code];\r | |
273 | } else if (copylen < 136) {\r | |
274 | const size_t tail = copylen - 8;\r | |
275 | const size_t code = (tail >> 5) + 30;\r | |
276 | BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r | |
277 | BrotliWriteBits(5, tail & 31, storage_ix, storage);\r | |
278 | BrotliWriteBits(depth[64], bits[64], storage_ix, storage);\r | |
279 | ++histo[code];\r | |
280 | ++histo[64];\r | |
281 | } else if (copylen < 2120) {\r | |
282 | const size_t tail = copylen - 72;\r | |
283 | const uint32_t nbits = Log2FloorNonZero(tail);\r | |
284 | const size_t code = nbits + 28;\r | |
285 | BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r | |
286 | BrotliWriteBits(nbits, tail - ((size_t)1 << nbits), storage_ix, storage);\r | |
287 | BrotliWriteBits(depth[64], bits[64], storage_ix, storage);\r | |
288 | ++histo[code];\r | |
289 | ++histo[64];\r | |
290 | } else {\r | |
291 | BrotliWriteBits(depth[39], bits[39], storage_ix, storage);\r | |
292 | BrotliWriteBits(24, copylen - 2120, storage_ix, storage);\r | |
293 | BrotliWriteBits(depth[64], bits[64], storage_ix, storage);\r | |
294 | ++histo[47];\r | |
295 | ++histo[64];\r | |
296 | }\r | |
297 | }\r | |
298 | \r | |
299 | static BROTLI_INLINE void EmitDistance(size_t distance,\r | |
300 | const uint8_t depth[128],\r | |
301 | const uint16_t bits[128],\r | |
302 | uint32_t histo[128],\r | |
303 | size_t* storage_ix, uint8_t* storage) {\r | |
304 | const size_t d = distance + 3;\r | |
305 | const uint32_t nbits = Log2FloorNonZero(d) - 1u;\r | |
306 | const size_t prefix = (d >> nbits) & 1;\r | |
307 | const size_t offset = (2 + prefix) << nbits;\r | |
308 | const size_t distcode = 2 * (nbits - 1) + prefix + 80;\r | |
309 | BrotliWriteBits(depth[distcode], bits[distcode], storage_ix, storage);\r | |
310 | BrotliWriteBits(nbits, d - offset, storage_ix, storage);\r | |
311 | ++histo[distcode];\r | |
312 | }\r | |
313 | \r | |
314 | static BROTLI_INLINE void EmitLiterals(const uint8_t* input, const size_t len,\r | |
315 | const uint8_t depth[256],\r | |
316 | const uint16_t bits[256],\r | |
317 | size_t* storage_ix, uint8_t* storage) {\r | |
318 | size_t j;\r | |
319 | for (j = 0; j < len; j++) {\r | |
320 | const uint8_t lit = input[j];\r | |
321 | BrotliWriteBits(depth[lit], bits[lit], storage_ix, storage);\r | |
322 | }\r | |
323 | }\r | |
324 | \r | |
325 | /* REQUIRES: len <= 1 << 20. */\r | |
326 | static void BrotliStoreMetaBlockHeader(\r | |
327 | size_t len, BROTLI_BOOL is_uncompressed, size_t* storage_ix,\r | |
328 | uint8_t* storage) {\r | |
329 | /* ISLAST */\r | |
330 | BrotliWriteBits(1, 0, storage_ix, storage);\r | |
331 | if (len <= (1U << 16)) {\r | |
332 | /* MNIBBLES is 4 */\r | |
333 | BrotliWriteBits(2, 0, storage_ix, storage);\r | |
334 | BrotliWriteBits(16, len - 1, storage_ix, storage);\r | |
335 | } else {\r | |
336 | /* MNIBBLES is 5 */\r | |
337 | BrotliWriteBits(2, 1, storage_ix, storage);\r | |
338 | BrotliWriteBits(20, len - 1, storage_ix, storage);\r | |
339 | }\r | |
340 | /* ISUNCOMPRESSED */\r | |
341 | BrotliWriteBits(1, (uint64_t)is_uncompressed, storage_ix, storage);\r | |
342 | }\r | |
343 | \r | |
344 | static void UpdateBits(size_t n_bits, uint32_t bits, size_t pos,\r | |
345 | uint8_t *array) {\r | |
346 | while (n_bits > 0) {\r | |
347 | size_t byte_pos = pos >> 3;\r | |
348 | size_t n_unchanged_bits = pos & 7;\r | |
349 | size_t n_changed_bits = BROTLI_MIN(size_t, n_bits, 8 - n_unchanged_bits);\r | |
350 | size_t total_bits = n_unchanged_bits + n_changed_bits;\r | |
351 | uint32_t mask =\r | |
352 | (~((1u << total_bits) - 1u)) | ((1u << n_unchanged_bits) - 1u);\r | |
353 | uint32_t unchanged_bits = array[byte_pos] & mask;\r | |
354 | uint32_t changed_bits = bits & ((1u << n_changed_bits) - 1u);\r | |
355 | array[byte_pos] =\r | |
356 | (uint8_t)((changed_bits << n_unchanged_bits) | unchanged_bits);\r | |
357 | n_bits -= n_changed_bits;\r | |
358 | bits >>= n_changed_bits;\r | |
359 | pos += n_changed_bits;\r | |
360 | }\r | |
361 | }\r | |
362 | \r | |
363 | static void RewindBitPosition(const size_t new_storage_ix,\r | |
364 | size_t* storage_ix, uint8_t* storage) {\r | |
365 | const size_t bitpos = new_storage_ix & 7;\r | |
366 | const size_t mask = (1u << bitpos) - 1;\r | |
367 | storage[new_storage_ix >> 3] &= (uint8_t)mask;\r | |
368 | *storage_ix = new_storage_ix;\r | |
369 | }\r | |
370 | \r | |
371 | static BROTLI_BOOL ShouldMergeBlock(\r | |
372 | const uint8_t* data, size_t len, const uint8_t* depths) {\r | |
373 | size_t histo[256] = { 0 };\r | |
374 | static const size_t kSampleRate = 43;\r | |
375 | size_t i;\r | |
376 | for (i = 0; i < len; i += kSampleRate) {\r | |
377 | ++histo[data[i]];\r | |
378 | }\r | |
379 | {\r | |
380 | const size_t total = (len + kSampleRate - 1) / kSampleRate;\r | |
381 | double r = (FastLog2(total) + 0.5) * (double)total + 200;\r | |
382 | for (i = 0; i < 256; ++i) {\r | |
383 | r -= (double)histo[i] * (depths[i] + FastLog2(histo[i]));\r | |
384 | }\r | |
385 | return TO_BROTLI_BOOL(r >= 0.0);\r | |
386 | }\r | |
387 | }\r | |
388 | \r | |
389 | /* Acceptable loss for uncompressible speedup is 2% */\r | |
390 | #define MIN_RATIO 980\r | |
391 | \r | |
392 | static BROTLI_INLINE BROTLI_BOOL ShouldUseUncompressedMode(\r | |
393 | const uint8_t* metablock_start, const uint8_t* next_emit,\r | |
394 | const size_t insertlen, const size_t literal_ratio) {\r | |
395 | const size_t compressed = (size_t)(next_emit - metablock_start);\r | |
396 | if (compressed * 50 > insertlen) {\r | |
397 | return BROTLI_FALSE;\r | |
398 | } else {\r | |
399 | return TO_BROTLI_BOOL(literal_ratio > MIN_RATIO);\r | |
400 | }\r | |
401 | }\r | |
402 | \r | |
403 | static void EmitUncompressedMetaBlock(const uint8_t* begin, const uint8_t* end,\r | |
404 | const size_t storage_ix_start,\r | |
405 | size_t* storage_ix, uint8_t* storage) {\r | |
406 | const size_t len = (size_t)(end - begin);\r | |
407 | RewindBitPosition(storage_ix_start, storage_ix, storage);\r | |
408 | BrotliStoreMetaBlockHeader(len, 1, storage_ix, storage);\r | |
409 | *storage_ix = (*storage_ix + 7u) & ~7u;\r | |
410 | memcpy(&storage[*storage_ix >> 3], begin, len);\r | |
411 | *storage_ix += len << 3;\r | |
412 | storage[*storage_ix >> 3] = 0;\r | |
413 | }\r | |
414 | \r | |
415 | static uint32_t kCmdHistoSeed[128] = {\r | |
416 | 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1,\r | |
417 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,\r | |
418 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,\r | |
419 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\r | |
420 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\r | |
421 | 1, 1, 1, 1, 0, 0, 0, 0,\r | |
422 | };\r | |
423 | \r | |
424 | void BrotliCompressFragmentFast(MemoryManager* m,\r | |
425 | const uint8_t* input, size_t input_size,\r | |
426 | BROTLI_BOOL is_last,\r | |
427 | int* table, size_t table_size,\r | |
428 | uint8_t cmd_depth[128], uint16_t cmd_bits[128],\r | |
429 | size_t* cmd_code_numbits, uint8_t* cmd_code,\r | |
430 | size_t* storage_ix, uint8_t* storage) {\r | |
431 | uint32_t cmd_histo[128];\r | |
432 | const uint8_t* ip_end;\r | |
433 | \r | |
434 | /* "next_emit" is a pointer to the first byte that is not covered by a\r | |
435 | previous copy. Bytes between "next_emit" and the start of the next copy or\r | |
436 | the end of the input will be emitted as literal bytes. */\r | |
437 | const uint8_t* next_emit = input;\r | |
438 | /* Save the start of the first block for position and distance computations.\r | |
439 | */\r | |
440 | const uint8_t* base_ip = input;\r | |
441 | \r | |
442 | static const size_t kFirstBlockSize = 3 << 15;\r | |
443 | static const size_t kMergeBlockSize = 1 << 16;\r | |
444 | \r | |
445 | const size_t kInputMarginBytes = 16;\r | |
446 | const size_t kMinMatchLen = 5;\r | |
447 | \r | |
448 | const uint8_t* metablock_start = input;\r | |
449 | size_t block_size = BROTLI_MIN(size_t, input_size, kFirstBlockSize);\r | |
450 | size_t total_block_size = block_size;\r | |
451 | /* Save the bit position of the MLEN field of the meta-block header, so that\r | |
452 | we can update it later if we decide to extend this meta-block. */\r | |
453 | size_t mlen_storage_ix = *storage_ix + 3;\r | |
454 | \r | |
455 | uint8_t lit_depth[256];\r | |
456 | uint16_t lit_bits[256];\r | |
457 | \r | |
458 | size_t literal_ratio;\r | |
459 | \r | |
460 | const uint8_t* ip;\r | |
461 | int last_distance;\r | |
462 | \r | |
463 | const size_t shift = 64u - Log2FloorNonZero(table_size);\r | |
464 | assert(table_size);\r | |
465 | assert(table_size <= (1u << 31));\r | |
466 | /* table must be power of two */\r | |
467 | assert((table_size & (table_size - 1)) == 0);\r | |
468 | assert(table_size - 1 ==\r | |
469 | (size_t)(MAKE_UINT64_T(0xFFFFFFFF, 0xFFFFFF) >> shift));\r | |
470 | \r | |
471 | if (input_size == 0) {\r | |
472 | assert(is_last);\r | |
473 | BrotliWriteBits(1, 1, storage_ix, storage); /* islast */\r | |
474 | BrotliWriteBits(1, 1, storage_ix, storage); /* isempty */\r | |
475 | *storage_ix = (*storage_ix + 7u) & ~7u;\r | |
476 | return;\r | |
477 | }\r | |
478 | \r | |
479 | BrotliStoreMetaBlockHeader(block_size, 0, storage_ix, storage);\r | |
480 | /* No block splits, no contexts. */\r | |
481 | BrotliWriteBits(13, 0, storage_ix, storage);\r | |
482 | \r | |
483 | literal_ratio = BuildAndStoreLiteralPrefixCode(\r | |
484 | m, input, block_size, lit_depth, lit_bits, storage_ix, storage);\r | |
485 | if (BROTLI_IS_OOM(m)) return;\r | |
486 | \r | |
487 | {\r | |
488 | /* Store the pre-compressed command and distance prefix codes. */\r | |
489 | size_t i;\r | |
490 | for (i = 0; i + 7 < *cmd_code_numbits; i += 8) {\r | |
491 | BrotliWriteBits(8, cmd_code[i >> 3], storage_ix, storage);\r | |
492 | }\r | |
493 | }\r | |
494 | BrotliWriteBits(*cmd_code_numbits & 7, cmd_code[*cmd_code_numbits >> 3],\r | |
495 | storage_ix, storage);\r | |
496 | \r | |
497 | emit_commands:\r | |
498 | /* Initialize the command and distance histograms. We will gather\r | |
499 | statistics of command and distance codes during the processing\r | |
500 | of this block and use it to update the command and distance\r | |
501 | prefix codes for the next block. */\r | |
502 | memcpy(cmd_histo, kCmdHistoSeed, sizeof(kCmdHistoSeed));\r | |
503 | \r | |
504 | /* "ip" is the input pointer. */\r | |
505 | ip = input;\r | |
506 | last_distance = -1;\r | |
507 | ip_end = input + block_size;\r | |
508 | \r | |
509 | if (PREDICT_TRUE(block_size >= kInputMarginBytes)) {\r | |
510 | /* For the last block, we need to keep a 16 bytes margin so that we can be\r | |
511 | sure that all distances are at most window size - 16.\r | |
512 | For all other blocks, we only need to keep a margin of 5 bytes so that\r | |
513 | we don't go over the block size with a copy. */\r | |
514 | const size_t len_limit = BROTLI_MIN(size_t, block_size - kMinMatchLen,\r | |
515 | input_size - kInputMarginBytes);\r | |
516 | const uint8_t* ip_limit = input + len_limit;\r | |
517 | \r | |
518 | uint32_t next_hash;\r | |
519 | for (next_hash = Hash(++ip, shift); ; ) {\r | |
520 | /* Step 1: Scan forward in the input looking for a 5-byte-long match.\r | |
521 | If we get close to exhausting the input then goto emit_remainder.\r | |
522 | \r | |
523 | Heuristic match skipping: If 32 bytes are scanned with no matches\r | |
524 | found, start looking only at every other byte. If 32 more bytes are\r | |
525 | scanned, look at every third byte, etc.. When a match is found,\r | |
526 | immediately go back to looking at every byte. This is a small loss\r | |
527 | (~5% performance, ~0.1% density) for compressible data due to more\r | |
528 | bookkeeping, but for non-compressible data (such as JPEG) it's a huge\r | |
529 | win since the compressor quickly "realizes" the data is incompressible\r | |
530 | and doesn't bother looking for matches everywhere.\r | |
531 | \r | |
532 | The "skip" variable keeps track of how many bytes there are since the\r | |
533 | last match; dividing it by 32 (ie. right-shifting by five) gives the\r | |
534 | number of bytes to move ahead for each iteration. */\r | |
535 | uint32_t skip = 32;\r | |
536 | \r | |
537 | const uint8_t* next_ip = ip;\r | |
538 | const uint8_t* candidate;\r | |
539 | assert(next_emit < ip);\r | |
540 | \r | |
541 | do {\r | |
542 | uint32_t hash = next_hash;\r | |
543 | uint32_t bytes_between_hash_lookups = skip++ >> 5;\r | |
544 | assert(hash == Hash(next_ip, shift));\r | |
545 | ip = next_ip;\r | |
546 | next_ip = ip + bytes_between_hash_lookups;\r | |
547 | if (PREDICT_FALSE(next_ip > ip_limit)) {\r | |
548 | goto emit_remainder;\r | |
549 | }\r | |
550 | next_hash = Hash(next_ip, shift);\r | |
551 | candidate = ip - last_distance;\r | |
552 | if (IsMatch(ip, candidate)) {\r | |
553 | if (PREDICT_TRUE(candidate < ip)) {\r | |
554 | table[hash] = (int)(ip - base_ip);\r | |
555 | break;\r | |
556 | }\r | |
557 | }\r | |
558 | candidate = base_ip + table[hash];\r | |
559 | assert(candidate >= base_ip);\r | |
560 | assert(candidate < ip);\r | |
561 | \r | |
562 | table[hash] = (int)(ip - base_ip);\r | |
563 | } while (PREDICT_TRUE(!IsMatch(ip, candidate)));\r | |
564 | \r | |
565 | /* Step 2: Emit the found match together with the literal bytes from\r | |
566 | "next_emit" to the bit stream, and then see if we can find a next macth\r | |
567 | immediately afterwards. Repeat until we find no match for the input\r | |
568 | without emitting some literal bytes. */\r | |
569 | \r | |
570 | {\r | |
571 | /* We have a 5-byte match at ip, and we need to emit bytes in\r | |
572 | [next_emit, ip). */\r | |
573 | const uint8_t* base = ip;\r | |
574 | size_t matched = 5 + FindMatchLengthWithLimit(\r | |
575 | candidate + 5, ip + 5, (size_t)(ip_end - ip) - 5);\r | |
576 | int distance = (int)(base - candidate); /* > 0 */\r | |
577 | size_t insert = (size_t)(base - next_emit);\r | |
578 | ip += matched;\r | |
579 | assert(0 == memcmp(base, candidate, matched));\r | |
580 | if (PREDICT_TRUE(insert < 6210)) {\r | |
581 | EmitInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,\r | |
582 | storage_ix, storage);\r | |
583 | } else if (ShouldUseUncompressedMode(metablock_start, next_emit, insert,\r | |
584 | literal_ratio)) {\r | |
585 | EmitUncompressedMetaBlock(metablock_start, base, mlen_storage_ix - 3,\r | |
586 | storage_ix, storage);\r | |
587 | input_size -= (size_t)(base - input);\r | |
588 | input = base;\r | |
589 | next_emit = input;\r | |
590 | goto next_block;\r | |
591 | } else {\r | |
592 | EmitLongInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,\r | |
593 | storage_ix, storage);\r | |
594 | }\r | |
595 | EmitLiterals(next_emit, insert, lit_depth, lit_bits,\r | |
596 | storage_ix, storage);\r | |
597 | if (distance == last_distance) {\r | |
598 | BrotliWriteBits(cmd_depth[64], cmd_bits[64], storage_ix, storage);\r | |
599 | ++cmd_histo[64];\r | |
600 | } else {\r | |
601 | EmitDistance((size_t)distance, cmd_depth, cmd_bits,\r | |
602 | cmd_histo, storage_ix, storage);\r | |
603 | last_distance = distance;\r | |
604 | }\r | |
605 | EmitCopyLenLastDistance(matched, cmd_depth, cmd_bits, cmd_histo,\r | |
606 | storage_ix, storage);\r | |
607 | \r | |
608 | next_emit = ip;\r | |
609 | if (PREDICT_FALSE(ip >= ip_limit)) {\r | |
610 | goto emit_remainder;\r | |
611 | }\r | |
612 | /* We could immediately start working at ip now, but to improve\r | |
613 | compression we first update "table" with the hashes of some positions\r | |
614 | within the last copy. */\r | |
615 | {\r | |
616 | uint64_t input_bytes = BROTLI_UNALIGNED_LOAD64(ip - 3);\r | |
617 | uint32_t prev_hash = HashBytesAtOffset(input_bytes, 0, shift);\r | |
618 | uint32_t cur_hash = HashBytesAtOffset(input_bytes, 3, shift);\r | |
619 | table[prev_hash] = (int)(ip - base_ip - 3);\r | |
620 | prev_hash = HashBytesAtOffset(input_bytes, 1, shift);\r | |
621 | table[prev_hash] = (int)(ip - base_ip - 2);\r | |
622 | prev_hash = HashBytesAtOffset(input_bytes, 2, shift);\r | |
623 | table[prev_hash] = (int)(ip - base_ip - 1);\r | |
624 | \r | |
625 | candidate = base_ip + table[cur_hash];\r | |
626 | table[cur_hash] = (int)(ip - base_ip);\r | |
627 | }\r | |
628 | }\r | |
629 | \r | |
630 | while (IsMatch(ip, candidate)) {\r | |
631 | /* We have a 5-byte match at ip, and no need to emit any literal bytes\r | |
632 | prior to ip. */\r | |
633 | const uint8_t* base = ip;\r | |
634 | size_t matched = 5 + FindMatchLengthWithLimit(\r | |
635 | candidate + 5, ip + 5, (size_t)(ip_end - ip) - 5);\r | |
636 | ip += matched;\r | |
637 | last_distance = (int)(base - candidate); /* > 0 */\r | |
638 | assert(0 == memcmp(base, candidate, matched));\r | |
639 | EmitCopyLen(matched, cmd_depth, cmd_bits, cmd_histo,\r | |
640 | storage_ix, storage);\r | |
641 | EmitDistance((size_t)last_distance, cmd_depth, cmd_bits,\r | |
642 | cmd_histo, storage_ix, storage);\r | |
643 | \r | |
644 | next_emit = ip;\r | |
645 | if (PREDICT_FALSE(ip >= ip_limit)) {\r | |
646 | goto emit_remainder;\r | |
647 | }\r | |
648 | /* We could immediately start working at ip now, but to improve\r | |
649 | compression we first update "table" with the hashes of some positions\r | |
650 | within the last copy. */\r | |
651 | {\r | |
652 | uint64_t input_bytes = BROTLI_UNALIGNED_LOAD64(ip - 3);\r | |
653 | uint32_t prev_hash = HashBytesAtOffset(input_bytes, 0, shift);\r | |
654 | uint32_t cur_hash = HashBytesAtOffset(input_bytes, 3, shift);\r | |
655 | table[prev_hash] = (int)(ip - base_ip - 3);\r | |
656 | prev_hash = HashBytesAtOffset(input_bytes, 1, shift);\r | |
657 | table[prev_hash] = (int)(ip - base_ip - 2);\r | |
658 | prev_hash = HashBytesAtOffset(input_bytes, 2, shift);\r | |
659 | table[prev_hash] = (int)(ip - base_ip - 1);\r | |
660 | \r | |
661 | candidate = base_ip + table[cur_hash];\r | |
662 | table[cur_hash] = (int)(ip - base_ip);\r | |
663 | }\r | |
664 | }\r | |
665 | \r | |
666 | next_hash = Hash(++ip, shift);\r | |
667 | }\r | |
668 | }\r | |
669 | \r | |
670 | emit_remainder:\r | |
671 | assert(next_emit <= ip_end);\r | |
672 | input += block_size;\r | |
673 | input_size -= block_size;\r | |
674 | block_size = BROTLI_MIN(size_t, input_size, kMergeBlockSize);\r | |
675 | \r | |
676 | /* Decide if we want to continue this meta-block instead of emitting the\r | |
677 | last insert-only command. */\r | |
678 | if (input_size > 0 &&\r | |
679 | total_block_size + block_size <= (1 << 20) &&\r | |
680 | ShouldMergeBlock(input, block_size, lit_depth)) {\r | |
681 | assert(total_block_size > (1 << 16));\r | |
682 | /* Update the size of the current meta-block and continue emitting commands.\r | |
683 | We can do this because the current size and the new size both have 5\r | |
684 | nibbles. */\r | |
685 | total_block_size += block_size;\r | |
686 | UpdateBits(20, (uint32_t)(total_block_size - 1), mlen_storage_ix, storage);\r | |
687 | goto emit_commands;\r | |
688 | }\r | |
689 | \r | |
690 | /* Emit the remaining bytes as literals. */\r | |
691 | if (next_emit < ip_end) {\r | |
692 | const size_t insert = (size_t)(ip_end - next_emit);\r | |
693 | if (PREDICT_TRUE(insert < 6210)) {\r | |
694 | EmitInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,\r | |
695 | storage_ix, storage);\r | |
696 | EmitLiterals(next_emit, insert, lit_depth, lit_bits, storage_ix, storage);\r | |
697 | } else if (ShouldUseUncompressedMode(metablock_start, next_emit, insert,\r | |
698 | literal_ratio)) {\r | |
699 | EmitUncompressedMetaBlock(metablock_start, ip_end, mlen_storage_ix - 3,\r | |
700 | storage_ix, storage);\r | |
701 | } else {\r | |
702 | EmitLongInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,\r | |
703 | storage_ix, storage);\r | |
704 | EmitLiterals(next_emit, insert, lit_depth, lit_bits,\r | |
705 | storage_ix, storage);\r | |
706 | }\r | |
707 | }\r | |
708 | next_emit = ip_end;\r | |
709 | \r | |
710 | next_block:\r | |
711 | /* If we have more data, write a new meta-block header and prefix codes and\r | |
712 | then continue emitting commands. */\r | |
713 | if (input_size > 0) {\r | |
714 | metablock_start = input;\r | |
715 | block_size = BROTLI_MIN(size_t, input_size, kFirstBlockSize);\r | |
716 | total_block_size = block_size;\r | |
717 | /* Save the bit position of the MLEN field of the meta-block header, so that\r | |
718 | we can update it later if we decide to extend this meta-block. */\r | |
719 | mlen_storage_ix = *storage_ix + 3;\r | |
720 | BrotliStoreMetaBlockHeader(block_size, 0, storage_ix, storage);\r | |
721 | /* No block splits, no contexts. */\r | |
722 | BrotliWriteBits(13, 0, storage_ix, storage);\r | |
723 | literal_ratio = BuildAndStoreLiteralPrefixCode(\r | |
724 | m, input, block_size, lit_depth, lit_bits, storage_ix, storage);\r | |
725 | if (BROTLI_IS_OOM(m)) return;\r | |
726 | BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depth, cmd_bits,\r | |
727 | storage_ix, storage);\r | |
728 | goto emit_commands;\r | |
729 | }\r | |
730 | \r | |
731 | if (is_last) {\r | |
732 | BrotliWriteBits(1, 1, storage_ix, storage); /* islast */\r | |
733 | BrotliWriteBits(1, 1, storage_ix, storage); /* isempty */\r | |
734 | *storage_ix = (*storage_ix + 7u) & ~7u;\r | |
735 | } else {\r | |
736 | /* If this is not the last block, update the command and distance prefix\r | |
737 | codes for the next block and store the compressed forms. */\r | |
738 | cmd_code[0] = 0;\r | |
739 | *cmd_code_numbits = 0;\r | |
740 | BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depth, cmd_bits,\r | |
741 | cmd_code_numbits, cmd_code);\r | |
742 | }\r | |
743 | }\r | |
744 | \r | |
745 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
746 | } /* extern "C" */\r | |
747 | #endif\r |