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