1 | /* Copyright 2014 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 | /* Brotli bit stream functions to support the low level format. There are no |
8 | compression algorithms here, just the right ordering of bits to match the |
9 | specs. */ |
10 | |
11 | #include "./brotli_bit_stream.h" |
12 | |
13 | #include <string.h> /* memcpy, memset */ |
14 | |
15 | #include "../common/constants.h" |
16 | #include "../common/context.h" |
17 | #include "../common/platform.h" |
18 | #include <brotli/types.h> |
19 | #include "./entropy_encode.h" |
20 | #include "./entropy_encode_static.h" |
21 | #include "./fast_log.h" |
22 | #include "./histogram.h" |
23 | #include "./memory.h" |
24 | #include "./write_bits.h" |
25 | |
26 | #if defined(__cplusplus) || defined(c_plusplus) |
27 | extern "C" { |
28 | #endif |
29 | |
30 | #define MAX_HUFFMAN_TREE_SIZE (2 * BROTLI_NUM_COMMAND_SYMBOLS + 1) |
31 | /* The maximum size of Huffman dictionary for distances assuming that |
32 | NPOSTFIX = 0 and NDIRECT = 0. */ |
33 | #define MAX_SIMPLE_DISTANCE_ALPHABET_SIZE \ |
34 | BROTLI_DISTANCE_ALPHABET_SIZE(0, 0, BROTLI_LARGE_MAX_DISTANCE_BITS) |
35 | /* MAX_SIMPLE_DISTANCE_ALPHABET_SIZE == 140 */ |
36 | |
37 | /* Represents the range of values belonging to a prefix code: |
38 | [offset, offset + 2^nbits) */ |
39 | typedef struct PrefixCodeRange { |
40 | uint32_t offset; |
41 | uint32_t nbits; |
42 | } PrefixCodeRange; |
43 | |
44 | static const PrefixCodeRange |
45 | kBlockLengthPrefixCode[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = { |
46 | { 1, 2}, { 5, 2}, { 9, 2}, {13, 2}, {17, 3}, { 25, 3}, { 33, 3}, |
47 | {41, 3}, {49, 4}, {65, 4}, {81, 4}, {97, 4}, {113, 5}, {145, 5}, |
48 | {177, 5}, { 209, 5}, { 241, 6}, { 305, 6}, { 369, 7}, { 497, 8}, |
49 | {753, 9}, {1265, 10}, {2289, 11}, {4337, 12}, {8433, 13}, {16625, 24} |
50 | }; |
51 | |
52 | static BROTLI_INLINE uint32_t BlockLengthPrefixCode(uint32_t len) { |
53 | uint32_t code = (len >= 177) ? (len >= 753 ? 20 : 14) : (len >= 41 ? 7 : 0); |
54 | while (code < (BROTLI_NUM_BLOCK_LEN_SYMBOLS - 1) && |
55 | len >= kBlockLengthPrefixCode[code + 1].offset) ++code; |
56 | return code; |
57 | } |
58 | |
59 | static BROTLI_INLINE void GetBlockLengthPrefixCode(uint32_t len, size_t* code, |
60 | uint32_t* , uint32_t* ) { |
61 | *code = BlockLengthPrefixCode(len); |
62 | *n_extra = kBlockLengthPrefixCode[*code].nbits; |
63 | *extra = len - kBlockLengthPrefixCode[*code].offset; |
64 | } |
65 | |
66 | typedef struct BlockTypeCodeCalculator { |
67 | size_t last_type; |
68 | size_t second_last_type; |
69 | } BlockTypeCodeCalculator; |
70 | |
71 | static void InitBlockTypeCodeCalculator(BlockTypeCodeCalculator* self) { |
72 | self->last_type = 1; |
73 | self->second_last_type = 0; |
74 | } |
75 | |
76 | static BROTLI_INLINE size_t NextBlockTypeCode( |
77 | BlockTypeCodeCalculator* calculator, uint8_t type) { |
78 | size_t type_code = (type == calculator->last_type + 1) ? 1u : |
79 | (type == calculator->second_last_type) ? 0u : type + 2u; |
80 | calculator->second_last_type = calculator->last_type; |
81 | calculator->last_type = type; |
82 | return type_code; |
83 | } |
84 | |
85 | /* |nibblesbits| represents the 2 bits to encode MNIBBLES (0-3) |
86 | REQUIRES: length > 0 |
87 | REQUIRES: length <= (1 << 24) */ |
88 | static void BrotliEncodeMlen(size_t length, uint64_t* bits, |
89 | size_t* numbits, uint64_t* nibblesbits) { |
90 | size_t lg = (length == 1) ? 1 : Log2FloorNonZero((uint32_t)(length - 1)) + 1; |
91 | size_t mnibbles = (lg < 16 ? 16 : (lg + 3)) / 4; |
92 | BROTLI_DCHECK(length > 0); |
93 | BROTLI_DCHECK(length <= (1 << 24)); |
94 | BROTLI_DCHECK(lg <= 24); |
95 | *nibblesbits = mnibbles - 4; |
96 | *numbits = mnibbles * 4; |
97 | *bits = length - 1; |
98 | } |
99 | |
100 | static BROTLI_INLINE void StoreCommandExtra( |
101 | const Command* cmd, size_t* storage_ix, uint8_t* storage) { |
102 | uint32_t copylen_code = CommandCopyLenCode(cmd); |
103 | uint16_t inscode = GetInsertLengthCode(cmd->insert_len_); |
104 | uint16_t copycode = GetCopyLengthCode(copylen_code); |
105 | uint32_t = GetInsertExtra(inscode); |
106 | uint64_t = cmd->insert_len_ - GetInsertBase(inscode); |
107 | uint64_t = copylen_code - GetCopyBase(copycode); |
108 | uint64_t bits = (copyextraval << insnumextra) | insextraval; |
109 | BrotliWriteBits( |
110 | insnumextra + GetCopyExtra(copycode), bits, storage_ix, storage); |
111 | } |
112 | |
113 | /* Data structure that stores almost everything that is needed to encode each |
114 | block switch command. */ |
115 | typedef struct BlockSplitCode { |
116 | BlockTypeCodeCalculator type_code_calculator; |
117 | uint8_t type_depths[BROTLI_MAX_BLOCK_TYPE_SYMBOLS]; |
118 | uint16_t type_bits[BROTLI_MAX_BLOCK_TYPE_SYMBOLS]; |
119 | uint8_t length_depths[BROTLI_NUM_BLOCK_LEN_SYMBOLS]; |
120 | uint16_t length_bits[BROTLI_NUM_BLOCK_LEN_SYMBOLS]; |
121 | } BlockSplitCode; |
122 | |
123 | /* Stores a number between 0 and 255. */ |
124 | static void StoreVarLenUint8(size_t n, size_t* storage_ix, uint8_t* storage) { |
125 | if (n == 0) { |
126 | BrotliWriteBits(1, 0, storage_ix, storage); |
127 | } else { |
128 | size_t nbits = Log2FloorNonZero(n); |
129 | BrotliWriteBits(1, 1, storage_ix, storage); |
130 | BrotliWriteBits(3, nbits, storage_ix, storage); |
131 | BrotliWriteBits(nbits, n - ((size_t)1 << nbits), storage_ix, storage); |
132 | } |
133 | } |
134 | |
135 | /* Stores the compressed meta-block header. |
136 | REQUIRES: length > 0 |
137 | REQUIRES: length <= (1 << 24) */ |
138 | static void (BROTLI_BOOL is_final_block, |
139 | size_t length, |
140 | size_t* storage_ix, |
141 | uint8_t* storage) { |
142 | uint64_t lenbits; |
143 | size_t nlenbits; |
144 | uint64_t nibblesbits; |
145 | |
146 | /* Write ISLAST bit. */ |
147 | BrotliWriteBits(1, (uint64_t)is_final_block, storage_ix, storage); |
148 | /* Write ISEMPTY bit. */ |
149 | if (is_final_block) { |
150 | BrotliWriteBits(1, 0, storage_ix, storage); |
151 | } |
152 | |
153 | BrotliEncodeMlen(length, &lenbits, &nlenbits, &nibblesbits); |
154 | BrotliWriteBits(2, nibblesbits, storage_ix, storage); |
155 | BrotliWriteBits(nlenbits, lenbits, storage_ix, storage); |
156 | |
157 | if (!is_final_block) { |
158 | /* Write ISUNCOMPRESSED bit. */ |
159 | BrotliWriteBits(1, 0, storage_ix, storage); |
160 | } |
161 | } |
162 | |
163 | /* Stores the uncompressed meta-block header. |
164 | REQUIRES: length > 0 |
165 | REQUIRES: length <= (1 << 24) */ |
166 | static void (size_t length, |
167 | size_t* storage_ix, |
168 | uint8_t* storage) { |
169 | uint64_t lenbits; |
170 | size_t nlenbits; |
171 | uint64_t nibblesbits; |
172 | |
173 | /* Write ISLAST bit. |
174 | Uncompressed block cannot be the last one, so set to 0. */ |
175 | BrotliWriteBits(1, 0, storage_ix, storage); |
176 | BrotliEncodeMlen(length, &lenbits, &nlenbits, &nibblesbits); |
177 | BrotliWriteBits(2, nibblesbits, storage_ix, storage); |
178 | BrotliWriteBits(nlenbits, lenbits, storage_ix, storage); |
179 | /* Write ISUNCOMPRESSED bit. */ |
180 | BrotliWriteBits(1, 1, storage_ix, storage); |
181 | } |
182 | |
183 | static void BrotliStoreHuffmanTreeOfHuffmanTreeToBitMask( |
184 | const int num_codes, const uint8_t* code_length_bitdepth, |
185 | size_t* storage_ix, uint8_t* storage) { |
186 | static const uint8_t kStorageOrder[BROTLI_CODE_LENGTH_CODES] = { |
187 | 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15 |
188 | }; |
189 | /* The bit lengths of the Huffman code over the code length alphabet |
190 | are compressed with the following static Huffman code: |
191 | Symbol Code |
192 | ------ ---- |
193 | 0 00 |
194 | 1 1110 |
195 | 2 110 |
196 | 3 01 |
197 | 4 10 |
198 | 5 1111 */ |
199 | static const uint8_t kHuffmanBitLengthHuffmanCodeSymbols[6] = { |
200 | 0, 7, 3, 2, 1, 15 |
201 | }; |
202 | static const uint8_t kHuffmanBitLengthHuffmanCodeBitLengths[6] = { |
203 | 2, 4, 3, 2, 2, 4 |
204 | }; |
205 | |
206 | size_t skip_some = 0; /* skips none. */ |
207 | |
208 | /* Throw away trailing zeros: */ |
209 | size_t codes_to_store = BROTLI_CODE_LENGTH_CODES; |
210 | if (num_codes > 1) { |
211 | for (; codes_to_store > 0; --codes_to_store) { |
212 | if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) { |
213 | break; |
214 | } |
215 | } |
216 | } |
217 | if (code_length_bitdepth[kStorageOrder[0]] == 0 && |
218 | code_length_bitdepth[kStorageOrder[1]] == 0) { |
219 | skip_some = 2; /* skips two. */ |
220 | if (code_length_bitdepth[kStorageOrder[2]] == 0) { |
221 | skip_some = 3; /* skips three. */ |
222 | } |
223 | } |
224 | BrotliWriteBits(2, skip_some, storage_ix, storage); |
225 | { |
226 | size_t i; |
227 | for (i = skip_some; i < codes_to_store; ++i) { |
228 | size_t l = code_length_bitdepth[kStorageOrder[i]]; |
229 | BrotliWriteBits(kHuffmanBitLengthHuffmanCodeBitLengths[l], |
230 | kHuffmanBitLengthHuffmanCodeSymbols[l], storage_ix, storage); |
231 | } |
232 | } |
233 | } |
234 | |
235 | static void BrotliStoreHuffmanTreeToBitMask( |
236 | const size_t huffman_tree_size, const uint8_t* huffman_tree, |
237 | const uint8_t* , const uint8_t* code_length_bitdepth, |
238 | const uint16_t* code_length_bitdepth_symbols, |
239 | size_t* BROTLI_RESTRICT storage_ix, uint8_t* BROTLI_RESTRICT storage) { |
240 | size_t i; |
241 | for (i = 0; i < huffman_tree_size; ++i) { |
242 | size_t ix = huffman_tree[i]; |
243 | BrotliWriteBits(code_length_bitdepth[ix], code_length_bitdepth_symbols[ix], |
244 | storage_ix, storage); |
245 | /* Extra bits */ |
246 | switch (ix) { |
247 | case BROTLI_REPEAT_PREVIOUS_CODE_LENGTH: |
248 | BrotliWriteBits(2, huffman_tree_extra_bits[i], storage_ix, storage); |
249 | break; |
250 | case BROTLI_REPEAT_ZERO_CODE_LENGTH: |
251 | BrotliWriteBits(3, huffman_tree_extra_bits[i], storage_ix, storage); |
252 | break; |
253 | } |
254 | } |
255 | } |
256 | |
257 | static void StoreSimpleHuffmanTree(const uint8_t* depths, |
258 | size_t symbols[4], |
259 | size_t num_symbols, |
260 | size_t max_bits, |
261 | size_t* storage_ix, uint8_t* storage) { |
262 | /* value of 1 indicates a simple Huffman code */ |
263 | BrotliWriteBits(2, 1, storage_ix, storage); |
264 | BrotliWriteBits(2, num_symbols - 1, storage_ix, storage); /* NSYM - 1 */ |
265 | |
266 | { |
267 | /* Sort */ |
268 | size_t i; |
269 | for (i = 0; i < num_symbols; i++) { |
270 | size_t j; |
271 | for (j = i + 1; j < num_symbols; j++) { |
272 | if (depths[symbols[j]] < depths[symbols[i]]) { |
273 | BROTLI_SWAP(size_t, symbols, j, i); |
274 | } |
275 | } |
276 | } |
277 | } |
278 | |
279 | if (num_symbols == 2) { |
280 | BrotliWriteBits(max_bits, symbols[0], storage_ix, storage); |
281 | BrotliWriteBits(max_bits, symbols[1], storage_ix, storage); |
282 | } else if (num_symbols == 3) { |
283 | BrotliWriteBits(max_bits, symbols[0], storage_ix, storage); |
284 | BrotliWriteBits(max_bits, symbols[1], storage_ix, storage); |
285 | BrotliWriteBits(max_bits, symbols[2], storage_ix, storage); |
286 | } else { |
287 | BrotliWriteBits(max_bits, symbols[0], storage_ix, storage); |
288 | BrotliWriteBits(max_bits, symbols[1], storage_ix, storage); |
289 | BrotliWriteBits(max_bits, symbols[2], storage_ix, storage); |
290 | BrotliWriteBits(max_bits, symbols[3], storage_ix, storage); |
291 | /* tree-select */ |
292 | BrotliWriteBits(1, depths[symbols[0]] == 1 ? 1 : 0, storage_ix, storage); |
293 | } |
294 | } |
295 | |
296 | /* num = alphabet size |
297 | depths = symbol depths */ |
298 | void BrotliStoreHuffmanTree(const uint8_t* depths, size_t num, |
299 | HuffmanTree* tree, |
300 | size_t* storage_ix, uint8_t* storage) { |
301 | /* Write the Huffman tree into the brotli-representation. |
302 | The command alphabet is the largest, so this allocation will fit all |
303 | alphabets. */ |
304 | uint8_t huffman_tree[BROTLI_NUM_COMMAND_SYMBOLS]; |
305 | uint8_t [BROTLI_NUM_COMMAND_SYMBOLS]; |
306 | size_t huffman_tree_size = 0; |
307 | uint8_t code_length_bitdepth[BROTLI_CODE_LENGTH_CODES] = { 0 }; |
308 | uint16_t code_length_bitdepth_symbols[BROTLI_CODE_LENGTH_CODES]; |
309 | uint32_t huffman_tree_histogram[BROTLI_CODE_LENGTH_CODES] = { 0 }; |
310 | size_t i; |
311 | int num_codes = 0; |
312 | size_t code = 0; |
313 | |
314 | BROTLI_DCHECK(num <= BROTLI_NUM_COMMAND_SYMBOLS); |
315 | |
316 | BrotliWriteHuffmanTree(depths, num, &huffman_tree_size, huffman_tree, |
317 | huffman_tree_extra_bits); |
318 | |
319 | /* Calculate the statistics of the Huffman tree in brotli-representation. */ |
320 | for (i = 0; i < huffman_tree_size; ++i) { |
321 | ++huffman_tree_histogram[huffman_tree[i]]; |
322 | } |
323 | |
324 | for (i = 0; i < BROTLI_CODE_LENGTH_CODES; ++i) { |
325 | if (huffman_tree_histogram[i]) { |
326 | if (num_codes == 0) { |
327 | code = i; |
328 | num_codes = 1; |
329 | } else if (num_codes == 1) { |
330 | num_codes = 2; |
331 | break; |
332 | } |
333 | } |
334 | } |
335 | |
336 | /* Calculate another Huffman tree to use for compressing both the |
337 | earlier Huffman tree with. */ |
338 | BrotliCreateHuffmanTree(huffman_tree_histogram, BROTLI_CODE_LENGTH_CODES, |
339 | 5, tree, code_length_bitdepth); |
340 | BrotliConvertBitDepthsToSymbols(code_length_bitdepth, |
341 | BROTLI_CODE_LENGTH_CODES, |
342 | code_length_bitdepth_symbols); |
343 | |
344 | /* Now, we have all the data, let's start storing it */ |
345 | BrotliStoreHuffmanTreeOfHuffmanTreeToBitMask(num_codes, code_length_bitdepth, |
346 | storage_ix, storage); |
347 | |
348 | if (num_codes == 1) { |
349 | code_length_bitdepth[code] = 0; |
350 | } |
351 | |
352 | /* Store the real Huffman tree now. */ |
353 | BrotliStoreHuffmanTreeToBitMask(huffman_tree_size, |
354 | huffman_tree, |
355 | huffman_tree_extra_bits, |
356 | code_length_bitdepth, |
357 | code_length_bitdepth_symbols, |
358 | storage_ix, storage); |
359 | } |
360 | |
361 | /* Builds a Huffman tree from histogram[0:length] into depth[0:length] and |
362 | bits[0:length] and stores the encoded tree to the bit stream. */ |
363 | static void BuildAndStoreHuffmanTree(const uint32_t* histogram, |
364 | const size_t histogram_length, |
365 | const size_t alphabet_size, |
366 | HuffmanTree* tree, |
367 | uint8_t* depth, |
368 | uint16_t* bits, |
369 | size_t* storage_ix, |
370 | uint8_t* storage) { |
371 | size_t count = 0; |
372 | size_t s4[4] = { 0 }; |
373 | size_t i; |
374 | size_t max_bits = 0; |
375 | for (i = 0; i < histogram_length; i++) { |
376 | if (histogram[i]) { |
377 | if (count < 4) { |
378 | s4[count] = i; |
379 | } else if (count > 4) { |
380 | break; |
381 | } |
382 | count++; |
383 | } |
384 | } |
385 | |
386 | { |
387 | size_t max_bits_counter = alphabet_size - 1; |
388 | while (max_bits_counter) { |
389 | max_bits_counter >>= 1; |
390 | ++max_bits; |
391 | } |
392 | } |
393 | |
394 | if (count <= 1) { |
395 | BrotliWriteBits(4, 1, storage_ix, storage); |
396 | BrotliWriteBits(max_bits, s4[0], storage_ix, storage); |
397 | depth[s4[0]] = 0; |
398 | bits[s4[0]] = 0; |
399 | return; |
400 | } |
401 | |
402 | memset(depth, 0, histogram_length * sizeof(depth[0])); |
403 | BrotliCreateHuffmanTree(histogram, histogram_length, 15, tree, depth); |
404 | BrotliConvertBitDepthsToSymbols(depth, histogram_length, bits); |
405 | |
406 | if (count <= 4) { |
407 | StoreSimpleHuffmanTree(depth, s4, count, max_bits, storage_ix, storage); |
408 | } else { |
409 | BrotliStoreHuffmanTree(depth, histogram_length, tree, storage_ix, storage); |
410 | } |
411 | } |
412 | |
413 | static BROTLI_INLINE BROTLI_BOOL SortHuffmanTree( |
414 | const HuffmanTree* v0, const HuffmanTree* v1) { |
415 | return TO_BROTLI_BOOL(v0->total_count_ < v1->total_count_); |
416 | } |
417 | |
418 | void BrotliBuildAndStoreHuffmanTreeFast(MemoryManager* m, |
419 | const uint32_t* histogram, |
420 | const size_t histogram_total, |
421 | const size_t max_bits, |
422 | uint8_t* depth, uint16_t* bits, |
423 | size_t* storage_ix, |
424 | uint8_t* storage) { |
425 | size_t count = 0; |
426 | size_t symbols[4] = { 0 }; |
427 | size_t length = 0; |
428 | size_t total = histogram_total; |
429 | while (total != 0) { |
430 | if (histogram[length]) { |
431 | if (count < 4) { |
432 | symbols[count] = length; |
433 | } |
434 | ++count; |
435 | total -= histogram[length]; |
436 | } |
437 | ++length; |
438 | } |
439 | |
440 | if (count <= 1) { |
441 | BrotliWriteBits(4, 1, storage_ix, storage); |
442 | BrotliWriteBits(max_bits, symbols[0], storage_ix, storage); |
443 | depth[symbols[0]] = 0; |
444 | bits[symbols[0]] = 0; |
445 | return; |
446 | } |
447 | |
448 | memset(depth, 0, length * sizeof(depth[0])); |
449 | { |
450 | const size_t max_tree_size = 2 * length + 1; |
451 | HuffmanTree* tree = BROTLI_ALLOC(m, HuffmanTree, max_tree_size); |
452 | uint32_t count_limit; |
453 | if (BROTLI_IS_OOM(m)) return; |
454 | for (count_limit = 1; ; count_limit *= 2) { |
455 | HuffmanTree* node = tree; |
456 | size_t l; |
457 | for (l = length; l != 0;) { |
458 | --l; |
459 | if (histogram[l]) { |
460 | if (BROTLI_PREDICT_TRUE(histogram[l] >= count_limit)) { |
461 | InitHuffmanTree(node, histogram[l], -1, (int16_t)l); |
462 | } else { |
463 | InitHuffmanTree(node, count_limit, -1, (int16_t)l); |
464 | } |
465 | ++node; |
466 | } |
467 | } |
468 | { |
469 | const int n = (int)(node - tree); |
470 | HuffmanTree sentinel; |
471 | int i = 0; /* Points to the next leaf node. */ |
472 | int j = n + 1; /* Points to the next non-leaf node. */ |
473 | int k; |
474 | |
475 | SortHuffmanTreeItems(tree, (size_t)n, SortHuffmanTree); |
476 | /* The nodes are: |
477 | [0, n): the sorted leaf nodes that we start with. |
478 | [n]: we add a sentinel here. |
479 | [n + 1, 2n): new parent nodes are added here, starting from |
480 | (n+1). These are naturally in ascending order. |
481 | [2n]: we add a sentinel at the end as well. |
482 | There will be (2n+1) elements at the end. */ |
483 | InitHuffmanTree(&sentinel, BROTLI_UINT32_MAX, -1, -1); |
484 | *node++ = sentinel; |
485 | *node++ = sentinel; |
486 | |
487 | for (k = n - 1; k > 0; --k) { |
488 | int left, right; |
489 | if (tree[i].total_count_ <= tree[j].total_count_) { |
490 | left = i; |
491 | ++i; |
492 | } else { |
493 | left = j; |
494 | ++j; |
495 | } |
496 | if (tree[i].total_count_ <= tree[j].total_count_) { |
497 | right = i; |
498 | ++i; |
499 | } else { |
500 | right = j; |
501 | ++j; |
502 | } |
503 | /* The sentinel node becomes the parent node. */ |
504 | node[-1].total_count_ = |
505 | tree[left].total_count_ + tree[right].total_count_; |
506 | node[-1].index_left_ = (int16_t)left; |
507 | node[-1].index_right_or_value_ = (int16_t)right; |
508 | /* Add back the last sentinel node. */ |
509 | *node++ = sentinel; |
510 | } |
511 | if (BrotliSetDepth(2 * n - 1, tree, depth, 14)) { |
512 | /* We need to pack the Huffman tree in 14 bits. If this was not |
513 | successful, add fake entities to the lowest values and retry. */ |
514 | break; |
515 | } |
516 | } |
517 | } |
518 | BROTLI_FREE(m, tree); |
519 | } |
520 | BrotliConvertBitDepthsToSymbols(depth, length, bits); |
521 | if (count <= 4) { |
522 | size_t i; |
523 | /* value of 1 indicates a simple Huffman code */ |
524 | BrotliWriteBits(2, 1, storage_ix, storage); |
525 | BrotliWriteBits(2, count - 1, storage_ix, storage); /* NSYM - 1 */ |
526 | |
527 | /* Sort */ |
528 | for (i = 0; i < count; i++) { |
529 | size_t j; |
530 | for (j = i + 1; j < count; j++) { |
531 | if (depth[symbols[j]] < depth[symbols[i]]) { |
532 | BROTLI_SWAP(size_t, symbols, j, i); |
533 | } |
534 | } |
535 | } |
536 | |
537 | if (count == 2) { |
538 | BrotliWriteBits(max_bits, symbols[0], storage_ix, storage); |
539 | BrotliWriteBits(max_bits, symbols[1], storage_ix, storage); |
540 | } else if (count == 3) { |
541 | BrotliWriteBits(max_bits, symbols[0], storage_ix, storage); |
542 | BrotliWriteBits(max_bits, symbols[1], storage_ix, storage); |
543 | BrotliWriteBits(max_bits, symbols[2], storage_ix, storage); |
544 | } else { |
545 | BrotliWriteBits(max_bits, symbols[0], storage_ix, storage); |
546 | BrotliWriteBits(max_bits, symbols[1], storage_ix, storage); |
547 | BrotliWriteBits(max_bits, symbols[2], storage_ix, storage); |
548 | BrotliWriteBits(max_bits, symbols[3], storage_ix, storage); |
549 | /* tree-select */ |
550 | BrotliWriteBits(1, depth[symbols[0]] == 1 ? 1 : 0, storage_ix, storage); |
551 | } |
552 | } else { |
553 | uint8_t previous_value = 8; |
554 | size_t i; |
555 | /* Complex Huffman Tree */ |
556 | StoreStaticCodeLengthCode(storage_ix, storage); |
557 | |
558 | /* Actual RLE coding. */ |
559 | for (i = 0; i < length;) { |
560 | const uint8_t value = depth[i]; |
561 | size_t reps = 1; |
562 | size_t k; |
563 | for (k = i + 1; k < length && depth[k] == value; ++k) { |
564 | ++reps; |
565 | } |
566 | i += reps; |
567 | if (value == 0) { |
568 | BrotliWriteBits(kZeroRepsDepth[reps], kZeroRepsBits[reps], |
569 | storage_ix, storage); |
570 | } else { |
571 | if (previous_value != value) { |
572 | BrotliWriteBits(kCodeLengthDepth[value], kCodeLengthBits[value], |
573 | storage_ix, storage); |
574 | --reps; |
575 | } |
576 | if (reps < 3) { |
577 | while (reps != 0) { |
578 | reps--; |
579 | BrotliWriteBits(kCodeLengthDepth[value], kCodeLengthBits[value], |
580 | storage_ix, storage); |
581 | } |
582 | } else { |
583 | reps -= 3; |
584 | BrotliWriteBits(kNonZeroRepsDepth[reps], kNonZeroRepsBits[reps], |
585 | storage_ix, storage); |
586 | } |
587 | previous_value = value; |
588 | } |
589 | } |
590 | } |
591 | } |
592 | |
593 | static size_t IndexOf(const uint8_t* v, size_t v_size, uint8_t value) { |
594 | size_t i = 0; |
595 | for (; i < v_size; ++i) { |
596 | if (v[i] == value) return i; |
597 | } |
598 | return i; |
599 | } |
600 | |
601 | static void MoveToFront(uint8_t* v, size_t index) { |
602 | uint8_t value = v[index]; |
603 | size_t i; |
604 | for (i = index; i != 0; --i) { |
605 | v[i] = v[i - 1]; |
606 | } |
607 | v[0] = value; |
608 | } |
609 | |
610 | static void MoveToFrontTransform(const uint32_t* BROTLI_RESTRICT v_in, |
611 | const size_t v_size, |
612 | uint32_t* v_out) { |
613 | size_t i; |
614 | uint8_t mtf[256]; |
615 | uint32_t max_value; |
616 | if (v_size == 0) { |
617 | return; |
618 | } |
619 | max_value = v_in[0]; |
620 | for (i = 1; i < v_size; ++i) { |
621 | if (v_in[i] > max_value) max_value = v_in[i]; |
622 | } |
623 | BROTLI_DCHECK(max_value < 256u); |
624 | for (i = 0; i <= max_value; ++i) { |
625 | mtf[i] = (uint8_t)i; |
626 | } |
627 | { |
628 | size_t mtf_size = max_value + 1; |
629 | for (i = 0; i < v_size; ++i) { |
630 | size_t index = IndexOf(mtf, mtf_size, (uint8_t)v_in[i]); |
631 | BROTLI_DCHECK(index < mtf_size); |
632 | v_out[i] = (uint32_t)index; |
633 | MoveToFront(mtf, index); |
634 | } |
635 | } |
636 | } |
637 | |
638 | /* Finds runs of zeros in v[0..in_size) and replaces them with a prefix code of |
639 | the run length plus extra bits (lower 9 bits is the prefix code and the rest |
640 | are the extra bits). Non-zero values in v[] are shifted by |
641 | *max_length_prefix. Will not create prefix codes bigger than the initial |
642 | value of *max_run_length_prefix. The prefix code of run length L is simply |
643 | Log2Floor(L) and the number of extra bits is the same as the prefix code. */ |
644 | static void RunLengthCodeZeros(const size_t in_size, |
645 | uint32_t* BROTLI_RESTRICT v, size_t* BROTLI_RESTRICT out_size, |
646 | uint32_t* BROTLI_RESTRICT max_run_length_prefix) { |
647 | uint32_t max_reps = 0; |
648 | size_t i; |
649 | uint32_t max_prefix; |
650 | for (i = 0; i < in_size;) { |
651 | uint32_t reps = 0; |
652 | for (; i < in_size && v[i] != 0; ++i) ; |
653 | for (; i < in_size && v[i] == 0; ++i) { |
654 | ++reps; |
655 | } |
656 | max_reps = BROTLI_MAX(uint32_t, reps, max_reps); |
657 | } |
658 | max_prefix = max_reps > 0 ? Log2FloorNonZero(max_reps) : 0; |
659 | max_prefix = BROTLI_MIN(uint32_t, max_prefix, *max_run_length_prefix); |
660 | *max_run_length_prefix = max_prefix; |
661 | *out_size = 0; |
662 | for (i = 0; i < in_size;) { |
663 | BROTLI_DCHECK(*out_size <= i); |
664 | if (v[i] != 0) { |
665 | v[*out_size] = v[i] + *max_run_length_prefix; |
666 | ++i; |
667 | ++(*out_size); |
668 | } else { |
669 | uint32_t reps = 1; |
670 | size_t k; |
671 | for (k = i + 1; k < in_size && v[k] == 0; ++k) { |
672 | ++reps; |
673 | } |
674 | i += reps; |
675 | while (reps != 0) { |
676 | if (reps < (2u << max_prefix)) { |
677 | uint32_t run_length_prefix = Log2FloorNonZero(reps); |
678 | const uint32_t = reps - (1u << run_length_prefix); |
679 | v[*out_size] = run_length_prefix + (extra_bits << 9); |
680 | ++(*out_size); |
681 | break; |
682 | } else { |
683 | const uint32_t = (1u << max_prefix) - 1u; |
684 | v[*out_size] = max_prefix + (extra_bits << 9); |
685 | reps -= (2u << max_prefix) - 1u; |
686 | ++(*out_size); |
687 | } |
688 | } |
689 | } |
690 | } |
691 | } |
692 | |
693 | #define SYMBOL_BITS 9 |
694 | |
695 | static void EncodeContextMap(MemoryManager* m, |
696 | const uint32_t* context_map, |
697 | size_t context_map_size, |
698 | size_t num_clusters, |
699 | HuffmanTree* tree, |
700 | size_t* storage_ix, uint8_t* storage) { |
701 | size_t i; |
702 | uint32_t* rle_symbols; |
703 | uint32_t max_run_length_prefix = 6; |
704 | size_t num_rle_symbols = 0; |
705 | uint32_t histogram[BROTLI_MAX_CONTEXT_MAP_SYMBOLS]; |
706 | static const uint32_t kSymbolMask = (1u << SYMBOL_BITS) - 1u; |
707 | uint8_t depths[BROTLI_MAX_CONTEXT_MAP_SYMBOLS]; |
708 | uint16_t bits[BROTLI_MAX_CONTEXT_MAP_SYMBOLS]; |
709 | |
710 | StoreVarLenUint8(num_clusters - 1, storage_ix, storage); |
711 | |
712 | if (num_clusters == 1) { |
713 | return; |
714 | } |
715 | |
716 | rle_symbols = BROTLI_ALLOC(m, uint32_t, context_map_size); |
717 | if (BROTLI_IS_OOM(m)) return; |
718 | MoveToFrontTransform(context_map, context_map_size, rle_symbols); |
719 | RunLengthCodeZeros(context_map_size, rle_symbols, |
720 | &num_rle_symbols, &max_run_length_prefix); |
721 | memset(histogram, 0, sizeof(histogram)); |
722 | for (i = 0; i < num_rle_symbols; ++i) { |
723 | ++histogram[rle_symbols[i] & kSymbolMask]; |
724 | } |
725 | { |
726 | BROTLI_BOOL use_rle = TO_BROTLI_BOOL(max_run_length_prefix > 0); |
727 | BrotliWriteBits(1, (uint64_t)use_rle, storage_ix, storage); |
728 | if (use_rle) { |
729 | BrotliWriteBits(4, max_run_length_prefix - 1, storage_ix, storage); |
730 | } |
731 | } |
732 | BuildAndStoreHuffmanTree(histogram, num_clusters + max_run_length_prefix, |
733 | num_clusters + max_run_length_prefix, |
734 | tree, depths, bits, storage_ix, storage); |
735 | for (i = 0; i < num_rle_symbols; ++i) { |
736 | const uint32_t rle_symbol = rle_symbols[i] & kSymbolMask; |
737 | const uint32_t = rle_symbols[i] >> SYMBOL_BITS; |
738 | BrotliWriteBits(depths[rle_symbol], bits[rle_symbol], storage_ix, storage); |
739 | if (rle_symbol > 0 && rle_symbol <= max_run_length_prefix) { |
740 | BrotliWriteBits(rle_symbol, extra_bits_val, storage_ix, storage); |
741 | } |
742 | } |
743 | BrotliWriteBits(1, 1, storage_ix, storage); /* use move-to-front */ |
744 | BROTLI_FREE(m, rle_symbols); |
745 | } |
746 | |
747 | /* Stores the block switch command with index block_ix to the bit stream. */ |
748 | static BROTLI_INLINE void StoreBlockSwitch(BlockSplitCode* code, |
749 | const uint32_t block_len, |
750 | const uint8_t block_type, |
751 | BROTLI_BOOL is_first_block, |
752 | size_t* storage_ix, |
753 | uint8_t* storage) { |
754 | size_t typecode = NextBlockTypeCode(&code->type_code_calculator, block_type); |
755 | size_t lencode; |
756 | uint32_t ; |
757 | uint32_t ; |
758 | if (!is_first_block) { |
759 | BrotliWriteBits(code->type_depths[typecode], code->type_bits[typecode], |
760 | storage_ix, storage); |
761 | } |
762 | GetBlockLengthPrefixCode(block_len, &lencode, &len_nextra, &len_extra); |
763 | |
764 | BrotliWriteBits(code->length_depths[lencode], code->length_bits[lencode], |
765 | storage_ix, storage); |
766 | BrotliWriteBits(len_nextra, len_extra, storage_ix, storage); |
767 | } |
768 | |
769 | /* Builds a BlockSplitCode data structure from the block split given by the |
770 | vector of block types and block lengths and stores it to the bit stream. */ |
771 | static void BuildAndStoreBlockSplitCode(const uint8_t* types, |
772 | const uint32_t* lengths, |
773 | const size_t num_blocks, |
774 | const size_t num_types, |
775 | HuffmanTree* tree, |
776 | BlockSplitCode* code, |
777 | size_t* storage_ix, |
778 | uint8_t* storage) { |
779 | uint32_t type_histo[BROTLI_MAX_BLOCK_TYPE_SYMBOLS]; |
780 | uint32_t length_histo[BROTLI_NUM_BLOCK_LEN_SYMBOLS]; |
781 | size_t i; |
782 | BlockTypeCodeCalculator type_code_calculator; |
783 | memset(type_histo, 0, (num_types + 2) * sizeof(type_histo[0])); |
784 | memset(length_histo, 0, sizeof(length_histo)); |
785 | InitBlockTypeCodeCalculator(&type_code_calculator); |
786 | for (i = 0; i < num_blocks; ++i) { |
787 | size_t type_code = NextBlockTypeCode(&type_code_calculator, types[i]); |
788 | if (i != 0) ++type_histo[type_code]; |
789 | ++length_histo[BlockLengthPrefixCode(lengths[i])]; |
790 | } |
791 | StoreVarLenUint8(num_types - 1, storage_ix, storage); |
792 | if (num_types > 1) { /* TODO: else? could StoreBlockSwitch occur? */ |
793 | BuildAndStoreHuffmanTree(&type_histo[0], num_types + 2, num_types + 2, tree, |
794 | &code->type_depths[0], &code->type_bits[0], |
795 | storage_ix, storage); |
796 | BuildAndStoreHuffmanTree(&length_histo[0], BROTLI_NUM_BLOCK_LEN_SYMBOLS, |
797 | BROTLI_NUM_BLOCK_LEN_SYMBOLS, |
798 | tree, &code->length_depths[0], |
799 | &code->length_bits[0], storage_ix, storage); |
800 | StoreBlockSwitch(code, lengths[0], types[0], 1, storage_ix, storage); |
801 | } |
802 | } |
803 | |
804 | /* Stores a context map where the histogram type is always the block type. */ |
805 | static void StoreTrivialContextMap(size_t num_types, |
806 | size_t context_bits, |
807 | HuffmanTree* tree, |
808 | size_t* storage_ix, |
809 | uint8_t* storage) { |
810 | StoreVarLenUint8(num_types - 1, storage_ix, storage); |
811 | if (num_types > 1) { |
812 | size_t repeat_code = context_bits - 1u; |
813 | size_t repeat_bits = (1u << repeat_code) - 1u; |
814 | size_t alphabet_size = num_types + repeat_code; |
815 | uint32_t histogram[BROTLI_MAX_CONTEXT_MAP_SYMBOLS]; |
816 | uint8_t depths[BROTLI_MAX_CONTEXT_MAP_SYMBOLS]; |
817 | uint16_t bits[BROTLI_MAX_CONTEXT_MAP_SYMBOLS]; |
818 | size_t i; |
819 | memset(histogram, 0, alphabet_size * sizeof(histogram[0])); |
820 | /* Write RLEMAX. */ |
821 | BrotliWriteBits(1, 1, storage_ix, storage); |
822 | BrotliWriteBits(4, repeat_code - 1, storage_ix, storage); |
823 | histogram[repeat_code] = (uint32_t)num_types; |
824 | histogram[0] = 1; |
825 | for (i = context_bits; i < alphabet_size; ++i) { |
826 | histogram[i] = 1; |
827 | } |
828 | BuildAndStoreHuffmanTree(histogram, alphabet_size, alphabet_size, |
829 | tree, depths, bits, storage_ix, storage); |
830 | for (i = 0; i < num_types; ++i) { |
831 | size_t code = (i == 0 ? 0 : i + context_bits - 1); |
832 | BrotliWriteBits(depths[code], bits[code], storage_ix, storage); |
833 | BrotliWriteBits( |
834 | depths[repeat_code], bits[repeat_code], storage_ix, storage); |
835 | BrotliWriteBits(repeat_code, repeat_bits, storage_ix, storage); |
836 | } |
837 | /* Write IMTF (inverse-move-to-front) bit. */ |
838 | BrotliWriteBits(1, 1, storage_ix, storage); |
839 | } |
840 | } |
841 | |
842 | /* Manages the encoding of one block category (literal, command or distance). */ |
843 | typedef struct BlockEncoder { |
844 | size_t histogram_length_; |
845 | size_t num_block_types_; |
846 | const uint8_t* block_types_; /* Not owned. */ |
847 | const uint32_t* block_lengths_; /* Not owned. */ |
848 | size_t num_blocks_; |
849 | BlockSplitCode block_split_code_; |
850 | size_t block_ix_; |
851 | size_t block_len_; |
852 | size_t entropy_ix_; |
853 | uint8_t* depths_; |
854 | uint16_t* bits_; |
855 | } BlockEncoder; |
856 | |
857 | static void InitBlockEncoder(BlockEncoder* self, size_t histogram_length, |
858 | size_t num_block_types, const uint8_t* block_types, |
859 | const uint32_t* block_lengths, const size_t num_blocks) { |
860 | self->histogram_length_ = histogram_length; |
861 | self->num_block_types_ = num_block_types; |
862 | self->block_types_ = block_types; |
863 | self->block_lengths_ = block_lengths; |
864 | self->num_blocks_ = num_blocks; |
865 | InitBlockTypeCodeCalculator(&self->block_split_code_.type_code_calculator); |
866 | self->block_ix_ = 0; |
867 | self->block_len_ = num_blocks == 0 ? 0 : block_lengths[0]; |
868 | self->entropy_ix_ = 0; |
869 | self->depths_ = 0; |
870 | self->bits_ = 0; |
871 | } |
872 | |
873 | static void CleanupBlockEncoder(MemoryManager* m, BlockEncoder* self) { |
874 | BROTLI_FREE(m, self->depths_); |
875 | BROTLI_FREE(m, self->bits_); |
876 | } |
877 | |
878 | /* Creates entropy codes of block lengths and block types and stores them |
879 | to the bit stream. */ |
880 | static void BuildAndStoreBlockSwitchEntropyCodes(BlockEncoder* self, |
881 | HuffmanTree* tree, size_t* storage_ix, uint8_t* storage) { |
882 | BuildAndStoreBlockSplitCode(self->block_types_, self->block_lengths_, |
883 | self->num_blocks_, self->num_block_types_, tree, &self->block_split_code_, |
884 | storage_ix, storage); |
885 | } |
886 | |
887 | /* Stores the next symbol with the entropy code of the current block type. |
888 | Updates the block type and block length at block boundaries. */ |
889 | static void StoreSymbol(BlockEncoder* self, size_t symbol, size_t* storage_ix, |
890 | uint8_t* storage) { |
891 | if (self->block_len_ == 0) { |
892 | size_t block_ix = ++self->block_ix_; |
893 | uint32_t block_len = self->block_lengths_[block_ix]; |
894 | uint8_t block_type = self->block_types_[block_ix]; |
895 | self->block_len_ = block_len; |
896 | self->entropy_ix_ = block_type * self->histogram_length_; |
897 | StoreBlockSwitch(&self->block_split_code_, block_len, block_type, 0, |
898 | storage_ix, storage); |
899 | } |
900 | --self->block_len_; |
901 | { |
902 | size_t ix = self->entropy_ix_ + symbol; |
903 | BrotliWriteBits(self->depths_[ix], self->bits_[ix], storage_ix, storage); |
904 | } |
905 | } |
906 | |
907 | /* Stores the next symbol with the entropy code of the current block type and |
908 | context value. |
909 | Updates the block type and block length at block boundaries. */ |
910 | static void StoreSymbolWithContext(BlockEncoder* self, size_t symbol, |
911 | size_t context, const uint32_t* context_map, size_t* storage_ix, |
912 | uint8_t* storage, const size_t context_bits) { |
913 | if (self->block_len_ == 0) { |
914 | size_t block_ix = ++self->block_ix_; |
915 | uint32_t block_len = self->block_lengths_[block_ix]; |
916 | uint8_t block_type = self->block_types_[block_ix]; |
917 | self->block_len_ = block_len; |
918 | self->entropy_ix_ = (size_t)block_type << context_bits; |
919 | StoreBlockSwitch(&self->block_split_code_, block_len, block_type, 0, |
920 | storage_ix, storage); |
921 | } |
922 | --self->block_len_; |
923 | { |
924 | size_t histo_ix = context_map[self->entropy_ix_ + context]; |
925 | size_t ix = histo_ix * self->histogram_length_ + symbol; |
926 | BrotliWriteBits(self->depths_[ix], self->bits_[ix], storage_ix, storage); |
927 | } |
928 | } |
929 | |
930 | #define FN(X) X ## Literal |
931 | /* NOLINTNEXTLINE(build/include) */ |
932 | #include "./block_encoder_inc.h" |
933 | #undef FN |
934 | |
935 | #define FN(X) X ## Command |
936 | /* NOLINTNEXTLINE(build/include) */ |
937 | #include "./block_encoder_inc.h" |
938 | #undef FN |
939 | |
940 | #define FN(X) X ## Distance |
941 | /* NOLINTNEXTLINE(build/include) */ |
942 | #include "./block_encoder_inc.h" |
943 | #undef FN |
944 | |
945 | static void JumpToByteBoundary(size_t* storage_ix, uint8_t* storage) { |
946 | *storage_ix = (*storage_ix + 7u) & ~7u; |
947 | storage[*storage_ix >> 3] = 0; |
948 | } |
949 | |
950 | void BrotliStoreMetaBlock(MemoryManager* m, |
951 | const uint8_t* input, size_t start_pos, size_t length, size_t mask, |
952 | uint8_t prev_byte, uint8_t prev_byte2, BROTLI_BOOL is_last, |
953 | const BrotliEncoderParams* params, ContextType literal_context_mode, |
954 | const Command* commands, size_t n_commands, const MetaBlockSplit* mb, |
955 | size_t* storage_ix, uint8_t* storage) { |
956 | |
957 | size_t pos = start_pos; |
958 | size_t i; |
959 | uint32_t num_distance_symbols = params->dist.alphabet_size; |
960 | uint32_t num_effective_distance_symbols = num_distance_symbols; |
961 | HuffmanTree* tree; |
962 | ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode); |
963 | BlockEncoder literal_enc; |
964 | BlockEncoder command_enc; |
965 | BlockEncoder distance_enc; |
966 | const BrotliDistanceParams* dist = ¶ms->dist; |
967 | if (params->large_window && |
968 | num_effective_distance_symbols > BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS) { |
969 | num_effective_distance_symbols = BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS; |
970 | } |
971 | |
972 | StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage); |
973 | |
974 | tree = BROTLI_ALLOC(m, HuffmanTree, MAX_HUFFMAN_TREE_SIZE); |
975 | if (BROTLI_IS_OOM(m)) return; |
976 | InitBlockEncoder(&literal_enc, BROTLI_NUM_LITERAL_SYMBOLS, |
977 | mb->literal_split.num_types, mb->literal_split.types, |
978 | mb->literal_split.lengths, mb->literal_split.num_blocks); |
979 | InitBlockEncoder(&command_enc, BROTLI_NUM_COMMAND_SYMBOLS, |
980 | mb->command_split.num_types, mb->command_split.types, |
981 | mb->command_split.lengths, mb->command_split.num_blocks); |
982 | InitBlockEncoder(&distance_enc, num_effective_distance_symbols, |
983 | mb->distance_split.num_types, mb->distance_split.types, |
984 | mb->distance_split.lengths, mb->distance_split.num_blocks); |
985 | |
986 | BuildAndStoreBlockSwitchEntropyCodes(&literal_enc, tree, storage_ix, storage); |
987 | BuildAndStoreBlockSwitchEntropyCodes(&command_enc, tree, storage_ix, storage); |
988 | BuildAndStoreBlockSwitchEntropyCodes( |
989 | &distance_enc, tree, storage_ix, storage); |
990 | |
991 | BrotliWriteBits(2, dist->distance_postfix_bits, storage_ix, storage); |
992 | BrotliWriteBits( |
993 | 4, dist->num_direct_distance_codes >> dist->distance_postfix_bits, |
994 | storage_ix, storage); |
995 | for (i = 0; i < mb->literal_split.num_types; ++i) { |
996 | BrotliWriteBits(2, literal_context_mode, storage_ix, storage); |
997 | } |
998 | |
999 | if (mb->literal_context_map_size == 0) { |
1000 | StoreTrivialContextMap(mb->literal_histograms_size, |
1001 | BROTLI_LITERAL_CONTEXT_BITS, tree, storage_ix, storage); |
1002 | } else { |
1003 | EncodeContextMap(m, |
1004 | mb->literal_context_map, mb->literal_context_map_size, |
1005 | mb->literal_histograms_size, tree, storage_ix, storage); |
1006 | if (BROTLI_IS_OOM(m)) return; |
1007 | } |
1008 | |
1009 | if (mb->distance_context_map_size == 0) { |
1010 | StoreTrivialContextMap(mb->distance_histograms_size, |
1011 | BROTLI_DISTANCE_CONTEXT_BITS, tree, storage_ix, storage); |
1012 | } else { |
1013 | EncodeContextMap(m, |
1014 | mb->distance_context_map, mb->distance_context_map_size, |
1015 | mb->distance_histograms_size, tree, storage_ix, storage); |
1016 | if (BROTLI_IS_OOM(m)) return; |
1017 | } |
1018 | |
1019 | BuildAndStoreEntropyCodesLiteral(m, &literal_enc, mb->literal_histograms, |
1020 | mb->literal_histograms_size, BROTLI_NUM_LITERAL_SYMBOLS, tree, |
1021 | storage_ix, storage); |
1022 | if (BROTLI_IS_OOM(m)) return; |
1023 | BuildAndStoreEntropyCodesCommand(m, &command_enc, mb->command_histograms, |
1024 | mb->command_histograms_size, BROTLI_NUM_COMMAND_SYMBOLS, tree, |
1025 | storage_ix, storage); |
1026 | if (BROTLI_IS_OOM(m)) return; |
1027 | BuildAndStoreEntropyCodesDistance(m, &distance_enc, mb->distance_histograms, |
1028 | mb->distance_histograms_size, num_distance_symbols, tree, |
1029 | storage_ix, storage); |
1030 | if (BROTLI_IS_OOM(m)) return; |
1031 | BROTLI_FREE(m, tree); |
1032 | |
1033 | for (i = 0; i < n_commands; ++i) { |
1034 | const Command cmd = commands[i]; |
1035 | size_t cmd_code = cmd.cmd_prefix_; |
1036 | StoreSymbol(&command_enc, cmd_code, storage_ix, storage); |
1037 | StoreCommandExtra(&cmd, storage_ix, storage); |
1038 | if (mb->literal_context_map_size == 0) { |
1039 | size_t j; |
1040 | for (j = cmd.insert_len_; j != 0; --j) { |
1041 | StoreSymbol(&literal_enc, input[pos & mask], storage_ix, storage); |
1042 | ++pos; |
1043 | } |
1044 | } else { |
1045 | size_t j; |
1046 | for (j = cmd.insert_len_; j != 0; --j) { |
1047 | size_t context = |
1048 | BROTLI_CONTEXT(prev_byte, prev_byte2, literal_context_lut); |
1049 | uint8_t literal = input[pos & mask]; |
1050 | StoreSymbolWithContext(&literal_enc, literal, context, |
1051 | mb->literal_context_map, storage_ix, storage, |
1052 | BROTLI_LITERAL_CONTEXT_BITS); |
1053 | prev_byte2 = prev_byte; |
1054 | prev_byte = literal; |
1055 | ++pos; |
1056 | } |
1057 | } |
1058 | pos += CommandCopyLen(&cmd); |
1059 | if (CommandCopyLen(&cmd)) { |
1060 | prev_byte2 = input[(pos - 2) & mask]; |
1061 | prev_byte = input[(pos - 1) & mask]; |
1062 | if (cmd.cmd_prefix_ >= 128) { |
1063 | size_t dist_code = cmd.dist_prefix_ & 0x3FF; |
1064 | uint32_t = cmd.dist_prefix_ >> 10; |
1065 | uint64_t = cmd.dist_extra_; |
1066 | if (mb->distance_context_map_size == 0) { |
1067 | StoreSymbol(&distance_enc, dist_code, storage_ix, storage); |
1068 | } else { |
1069 | size_t context = CommandDistanceContext(&cmd); |
1070 | StoreSymbolWithContext(&distance_enc, dist_code, context, |
1071 | mb->distance_context_map, storage_ix, storage, |
1072 | BROTLI_DISTANCE_CONTEXT_BITS); |
1073 | } |
1074 | BrotliWriteBits(distnumextra, distextra, storage_ix, storage); |
1075 | } |
1076 | } |
1077 | } |
1078 | CleanupBlockEncoder(m, &distance_enc); |
1079 | CleanupBlockEncoder(m, &command_enc); |
1080 | CleanupBlockEncoder(m, &literal_enc); |
1081 | if (is_last) { |
1082 | JumpToByteBoundary(storage_ix, storage); |
1083 | } |
1084 | } |
1085 | |
1086 | static void BuildHistograms(const uint8_t* input, |
1087 | size_t start_pos, |
1088 | size_t mask, |
1089 | const Command* commands, |
1090 | size_t n_commands, |
1091 | HistogramLiteral* lit_histo, |
1092 | HistogramCommand* cmd_histo, |
1093 | HistogramDistance* dist_histo) { |
1094 | size_t pos = start_pos; |
1095 | size_t i; |
1096 | for (i = 0; i < n_commands; ++i) { |
1097 | const Command cmd = commands[i]; |
1098 | size_t j; |
1099 | HistogramAddCommand(cmd_histo, cmd.cmd_prefix_); |
1100 | for (j = cmd.insert_len_; j != 0; --j) { |
1101 | HistogramAddLiteral(lit_histo, input[pos & mask]); |
1102 | ++pos; |
1103 | } |
1104 | pos += CommandCopyLen(&cmd); |
1105 | if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) { |
1106 | HistogramAddDistance(dist_histo, cmd.dist_prefix_ & 0x3FF); |
1107 | } |
1108 | } |
1109 | } |
1110 | |
1111 | static void StoreDataWithHuffmanCodes(const uint8_t* input, |
1112 | size_t start_pos, |
1113 | size_t mask, |
1114 | const Command* commands, |
1115 | size_t n_commands, |
1116 | const uint8_t* lit_depth, |
1117 | const uint16_t* lit_bits, |
1118 | const uint8_t* cmd_depth, |
1119 | const uint16_t* cmd_bits, |
1120 | const uint8_t* dist_depth, |
1121 | const uint16_t* dist_bits, |
1122 | size_t* storage_ix, |
1123 | uint8_t* storage) { |
1124 | size_t pos = start_pos; |
1125 | size_t i; |
1126 | for (i = 0; i < n_commands; ++i) { |
1127 | const Command cmd = commands[i]; |
1128 | const size_t cmd_code = cmd.cmd_prefix_; |
1129 | size_t j; |
1130 | BrotliWriteBits( |
1131 | cmd_depth[cmd_code], cmd_bits[cmd_code], storage_ix, storage); |
1132 | StoreCommandExtra(&cmd, storage_ix, storage); |
1133 | for (j = cmd.insert_len_; j != 0; --j) { |
1134 | const uint8_t literal = input[pos & mask]; |
1135 | BrotliWriteBits( |
1136 | lit_depth[literal], lit_bits[literal], storage_ix, storage); |
1137 | ++pos; |
1138 | } |
1139 | pos += CommandCopyLen(&cmd); |
1140 | if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) { |
1141 | const size_t dist_code = cmd.dist_prefix_ & 0x3FF; |
1142 | const uint32_t = cmd.dist_prefix_ >> 10; |
1143 | const uint32_t = cmd.dist_extra_; |
1144 | BrotliWriteBits(dist_depth[dist_code], dist_bits[dist_code], |
1145 | storage_ix, storage); |
1146 | BrotliWriteBits(distnumextra, distextra, storage_ix, storage); |
1147 | } |
1148 | } |
1149 | } |
1150 | |
1151 | void BrotliStoreMetaBlockTrivial(MemoryManager* m, |
1152 | const uint8_t* input, size_t start_pos, size_t length, size_t mask, |
1153 | BROTLI_BOOL is_last, const BrotliEncoderParams* params, |
1154 | const Command* commands, size_t n_commands, |
1155 | size_t* storage_ix, uint8_t* storage) { |
1156 | HistogramLiteral lit_histo; |
1157 | HistogramCommand cmd_histo; |
1158 | HistogramDistance dist_histo; |
1159 | uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS]; |
1160 | uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS]; |
1161 | uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS]; |
1162 | uint16_t cmd_bits[BROTLI_NUM_COMMAND_SYMBOLS]; |
1163 | uint8_t dist_depth[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE]; |
1164 | uint16_t dist_bits[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE]; |
1165 | HuffmanTree* tree; |
1166 | uint32_t num_distance_symbols = params->dist.alphabet_size; |
1167 | |
1168 | StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage); |
1169 | |
1170 | HistogramClearLiteral(&lit_histo); |
1171 | HistogramClearCommand(&cmd_histo); |
1172 | HistogramClearDistance(&dist_histo); |
1173 | |
1174 | BuildHistograms(input, start_pos, mask, commands, n_commands, |
1175 | &lit_histo, &cmd_histo, &dist_histo); |
1176 | |
1177 | BrotliWriteBits(13, 0, storage_ix, storage); |
1178 | |
1179 | tree = BROTLI_ALLOC(m, HuffmanTree, MAX_HUFFMAN_TREE_SIZE); |
1180 | if (BROTLI_IS_OOM(m)) return; |
1181 | BuildAndStoreHuffmanTree(lit_histo.data_, BROTLI_NUM_LITERAL_SYMBOLS, |
1182 | BROTLI_NUM_LITERAL_SYMBOLS, tree, |
1183 | lit_depth, lit_bits, |
1184 | storage_ix, storage); |
1185 | BuildAndStoreHuffmanTree(cmd_histo.data_, BROTLI_NUM_COMMAND_SYMBOLS, |
1186 | BROTLI_NUM_COMMAND_SYMBOLS, tree, |
1187 | cmd_depth, cmd_bits, |
1188 | storage_ix, storage); |
1189 | BuildAndStoreHuffmanTree(dist_histo.data_, MAX_SIMPLE_DISTANCE_ALPHABET_SIZE, |
1190 | num_distance_symbols, tree, |
1191 | dist_depth, dist_bits, |
1192 | storage_ix, storage); |
1193 | BROTLI_FREE(m, tree); |
1194 | StoreDataWithHuffmanCodes(input, start_pos, mask, commands, |
1195 | n_commands, lit_depth, lit_bits, |
1196 | cmd_depth, cmd_bits, |
1197 | dist_depth, dist_bits, |
1198 | storage_ix, storage); |
1199 | if (is_last) { |
1200 | JumpToByteBoundary(storage_ix, storage); |
1201 | } |
1202 | } |
1203 | |
1204 | void BrotliStoreMetaBlockFast(MemoryManager* m, |
1205 | const uint8_t* input, size_t start_pos, size_t length, size_t mask, |
1206 | BROTLI_BOOL is_last, const BrotliEncoderParams* params, |
1207 | const Command* commands, size_t n_commands, |
1208 | size_t* storage_ix, uint8_t* storage) { |
1209 | uint32_t num_distance_symbols = params->dist.alphabet_size; |
1210 | uint32_t distance_alphabet_bits = |
1211 | Log2FloorNonZero(num_distance_symbols - 1) + 1; |
1212 | |
1213 | StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage); |
1214 | |
1215 | BrotliWriteBits(13, 0, storage_ix, storage); |
1216 | |
1217 | if (n_commands <= 128) { |
1218 | uint32_t histogram[BROTLI_NUM_LITERAL_SYMBOLS] = { 0 }; |
1219 | size_t pos = start_pos; |
1220 | size_t num_literals = 0; |
1221 | size_t i; |
1222 | uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS]; |
1223 | uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS]; |
1224 | for (i = 0; i < n_commands; ++i) { |
1225 | const Command cmd = commands[i]; |
1226 | size_t j; |
1227 | for (j = cmd.insert_len_; j != 0; --j) { |
1228 | ++histogram[input[pos & mask]]; |
1229 | ++pos; |
1230 | } |
1231 | num_literals += cmd.insert_len_; |
1232 | pos += CommandCopyLen(&cmd); |
1233 | } |
1234 | BrotliBuildAndStoreHuffmanTreeFast(m, histogram, num_literals, |
1235 | /* max_bits = */ 8, |
1236 | lit_depth, lit_bits, |
1237 | storage_ix, storage); |
1238 | if (BROTLI_IS_OOM(m)) return; |
1239 | StoreStaticCommandHuffmanTree(storage_ix, storage); |
1240 | StoreStaticDistanceHuffmanTree(storage_ix, storage); |
1241 | StoreDataWithHuffmanCodes(input, start_pos, mask, commands, |
1242 | n_commands, lit_depth, lit_bits, |
1243 | kStaticCommandCodeDepth, |
1244 | kStaticCommandCodeBits, |
1245 | kStaticDistanceCodeDepth, |
1246 | kStaticDistanceCodeBits, |
1247 | storage_ix, storage); |
1248 | } else { |
1249 | HistogramLiteral lit_histo; |
1250 | HistogramCommand cmd_histo; |
1251 | HistogramDistance dist_histo; |
1252 | uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS]; |
1253 | uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS]; |
1254 | uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS]; |
1255 | uint16_t cmd_bits[BROTLI_NUM_COMMAND_SYMBOLS]; |
1256 | uint8_t dist_depth[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE]; |
1257 | uint16_t dist_bits[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE]; |
1258 | HistogramClearLiteral(&lit_histo); |
1259 | HistogramClearCommand(&cmd_histo); |
1260 | HistogramClearDistance(&dist_histo); |
1261 | BuildHistograms(input, start_pos, mask, commands, n_commands, |
1262 | &lit_histo, &cmd_histo, &dist_histo); |
1263 | BrotliBuildAndStoreHuffmanTreeFast(m, lit_histo.data_, |
1264 | lit_histo.total_count_, |
1265 | /* max_bits = */ 8, |
1266 | lit_depth, lit_bits, |
1267 | storage_ix, storage); |
1268 | if (BROTLI_IS_OOM(m)) return; |
1269 | BrotliBuildAndStoreHuffmanTreeFast(m, cmd_histo.data_, |
1270 | cmd_histo.total_count_, |
1271 | /* max_bits = */ 10, |
1272 | cmd_depth, cmd_bits, |
1273 | storage_ix, storage); |
1274 | if (BROTLI_IS_OOM(m)) return; |
1275 | BrotliBuildAndStoreHuffmanTreeFast(m, dist_histo.data_, |
1276 | dist_histo.total_count_, |
1277 | /* max_bits = */ |
1278 | distance_alphabet_bits, |
1279 | dist_depth, dist_bits, |
1280 | storage_ix, storage); |
1281 | if (BROTLI_IS_OOM(m)) return; |
1282 | StoreDataWithHuffmanCodes(input, start_pos, mask, commands, |
1283 | n_commands, lit_depth, lit_bits, |
1284 | cmd_depth, cmd_bits, |
1285 | dist_depth, dist_bits, |
1286 | storage_ix, storage); |
1287 | } |
1288 | |
1289 | if (is_last) { |
1290 | JumpToByteBoundary(storage_ix, storage); |
1291 | } |
1292 | } |
1293 | |
1294 | /* This is for storing uncompressed blocks (simple raw storage of |
1295 | bytes-as-bytes). */ |
1296 | void BrotliStoreUncompressedMetaBlock(BROTLI_BOOL is_final_block, |
1297 | const uint8_t* BROTLI_RESTRICT input, |
1298 | size_t position, size_t mask, |
1299 | size_t len, |
1300 | size_t* BROTLI_RESTRICT storage_ix, |
1301 | uint8_t* BROTLI_RESTRICT storage) { |
1302 | size_t masked_pos = position & mask; |
1303 | BrotliStoreUncompressedMetaBlockHeader(len, storage_ix, storage); |
1304 | JumpToByteBoundary(storage_ix, storage); |
1305 | |
1306 | if (masked_pos + len > mask + 1) { |
1307 | size_t len1 = mask + 1 - masked_pos; |
1308 | memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len1); |
1309 | *storage_ix += len1 << 3; |
1310 | len -= len1; |
1311 | masked_pos = 0; |
1312 | } |
1313 | memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len); |
1314 | *storage_ix += len << 3; |
1315 | |
1316 | /* We need to clear the next 4 bytes to continue to be |
1317 | compatible with BrotliWriteBits. */ |
1318 | BrotliWriteBitsPrepareStorage(*storage_ix, storage); |
1319 | |
1320 | /* Since the uncompressed block itself may not be the final block, add an |
1321 | empty one after this. */ |
1322 | if (is_final_block) { |
1323 | BrotliWriteBits(1, 1, storage_ix, storage); /* islast */ |
1324 | BrotliWriteBits(1, 1, storage_ix, storage); /* isempty */ |
1325 | JumpToByteBoundary(storage_ix, storage); |
1326 | } |
1327 | } |
1328 | |
1329 | #if defined(__cplusplus) || defined(c_plusplus) |
1330 | } /* extern "C" */ |
1331 | #endif |
1332 | |