1 /* Copyright 2014 Google Inc. All Rights Reserved.
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
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
11 #include "./brotli_bit_stream.h"
13 #include <string.h> /* memcpy, memset */
15 #include "../common/constants.h"
16 #include "../common/types.h"
17 #include "./context.h"
18 #include "./entropy_encode.h"
19 #include "./entropy_encode_static.h"
20 #include "./fast_log.h"
23 #include "./write_bits.h"
25 #if defined(__cplusplus) || defined(c_plusplus)
29 #define MAX_HUFFMAN_TREE_SIZE (2 * BROTLI_NUM_COMMAND_SYMBOLS + 1)
31 /* Represents the range of values belonging to a prefix code:
32 [offset, offset + 2^nbits) */
33 typedef struct PrefixCodeRange
{
38 static const PrefixCodeRange
39 kBlockLengthPrefixCode
[BROTLI_NUM_BLOCK_LEN_SYMBOLS
] = {
40 { 1, 2}, { 5, 2}, { 9, 2}, {13, 2}, {17, 3}, { 25, 3}, { 33, 3},
41 {41, 3}, {49, 4}, {65, 4}, {81, 4}, {97, 4}, {113, 5}, {145, 5},
42 {177, 5}, { 209, 5}, { 241, 6}, { 305, 6}, { 369, 7}, { 497, 8},
43 {753, 9}, {1265, 10}, {2289, 11}, {4337, 12}, {8433, 13}, {16625, 24}
46 static BROTLI_INLINE
uint32_t BlockLengthPrefixCode(uint32_t len
) {
47 uint32_t code
= (len
>= 177) ? (len
>= 753 ? 20 : 14) : (len
>= 41 ? 7 : 0);
48 while (code
< (BROTLI_NUM_BLOCK_LEN_SYMBOLS
- 1) &&
49 len
>= kBlockLengthPrefixCode
[code
+ 1].offset
) ++code
;
53 static BROTLI_INLINE
void GetBlockLengthPrefixCode(uint32_t len
, size_t* code
,
54 uint32_t* n_extra
, uint32_t* extra
) {
55 *code
= BlockLengthPrefixCode(len
);
56 *n_extra
= kBlockLengthPrefixCode
[*code
].nbits
;
57 *extra
= len
- kBlockLengthPrefixCode
[*code
].offset
;
60 typedef struct BlockTypeCodeCalculator
{
62 size_t second_last_type
;
63 } BlockTypeCodeCalculator
;
65 static void InitBlockTypeCodeCalculator(BlockTypeCodeCalculator
* self
) {
67 self
->second_last_type
= 0;
70 static BROTLI_INLINE
size_t NextBlockTypeCode(
71 BlockTypeCodeCalculator
* calculator
, uint8_t type
) {
72 size_t type_code
= (type
== calculator
->last_type
+ 1) ? 1u :
73 (type
== calculator
->second_last_type
) ? 0u : type
+ 2u;
74 calculator
->second_last_type
= calculator
->last_type
;
75 calculator
->last_type
= type
;
79 /* nibblesbits represents the 2 bits to encode MNIBBLES (0-3)
81 REQUIRES: length <= (1 << 24) */
82 static void BrotliEncodeMlen(size_t length
, uint64_t* bits
,
83 size_t* numbits
, uint64_t* nibblesbits
) {
84 size_t lg
= (length
== 1) ? 1 : Log2FloorNonZero((uint32_t)(length
- 1)) + 1;
85 size_t mnibbles
= (lg
< 16 ? 16 : (lg
+ 3)) / 4;
87 assert(length
<= (1 << 24));
89 *nibblesbits
= mnibbles
- 4;
90 *numbits
= mnibbles
* 4;
94 static BROTLI_INLINE
void StoreCommandExtra(
95 const Command
* cmd
, size_t* storage_ix
, uint8_t* storage
) {
96 uint32_t copylen_code
= CommandCopyLenCode(cmd
);
97 uint16_t inscode
= GetInsertLengthCode(cmd
->insert_len_
);
98 uint16_t copycode
= GetCopyLengthCode(copylen_code
);
99 uint32_t insnumextra
= GetInsertExtra(inscode
);
100 uint64_t insextraval
= cmd
->insert_len_
- GetInsertBase(inscode
);
101 uint64_t copyextraval
= copylen_code
- GetCopyBase(copycode
);
102 uint64_t bits
= (copyextraval
<< insnumextra
) | insextraval
;
104 insnumextra
+ GetCopyExtra(copycode
), bits
, storage_ix
, storage
);
107 /* Data structure that stores almost everything that is needed to encode each
108 block switch command. */
109 typedef struct BlockSplitCode
{
110 BlockTypeCodeCalculator type_code_calculator
;
111 uint8_t type_depths
[BROTLI_MAX_BLOCK_TYPE_SYMBOLS
];
112 uint16_t type_bits
[BROTLI_MAX_BLOCK_TYPE_SYMBOLS
];
113 uint8_t length_depths
[BROTLI_NUM_BLOCK_LEN_SYMBOLS
];
114 uint16_t length_bits
[BROTLI_NUM_BLOCK_LEN_SYMBOLS
];
117 /* Stores a number between 0 and 255. */
118 static void StoreVarLenUint8(size_t n
, size_t* storage_ix
, uint8_t* storage
) {
120 BrotliWriteBits(1, 0, storage_ix
, storage
);
122 size_t nbits
= Log2FloorNonZero(n
);
123 BrotliWriteBits(1, 1, storage_ix
, storage
);
124 BrotliWriteBits(3, nbits
, storage_ix
, storage
);
125 BrotliWriteBits(nbits
, n
- ((size_t)1 << nbits
), storage_ix
, storage
);
129 /* Stores the compressed meta-block header.
131 REQUIRES: length <= (1 << 24) */
132 static void StoreCompressedMetaBlockHeader(BROTLI_BOOL is_final_block
,
138 uint64_t nibblesbits
;
140 /* Write ISLAST bit. */
141 BrotliWriteBits(1, (uint64_t)is_final_block
, storage_ix
, storage
);
142 /* Write ISEMPTY bit. */
143 if (is_final_block
) {
144 BrotliWriteBits(1, 0, storage_ix
, storage
);
147 BrotliEncodeMlen(length
, &lenbits
, &nlenbits
, &nibblesbits
);
148 BrotliWriteBits(2, nibblesbits
, storage_ix
, storage
);
149 BrotliWriteBits(nlenbits
, lenbits
, storage_ix
, storage
);
151 if (!is_final_block
) {
152 /* Write ISUNCOMPRESSED bit. */
153 BrotliWriteBits(1, 0, storage_ix
, storage
);
157 /* Stores the uncompressed meta-block header.
159 REQUIRES: length <= (1 << 24) */
160 static void BrotliStoreUncompressedMetaBlockHeader(size_t length
,
165 uint64_t nibblesbits
;
168 Uncompressed block cannot be the last one, so set to 0. */
169 BrotliWriteBits(1, 0, storage_ix
, storage
);
170 BrotliEncodeMlen(length
, &lenbits
, &nlenbits
, &nibblesbits
);
171 BrotliWriteBits(2, nibblesbits
, storage_ix
, storage
);
172 BrotliWriteBits(nlenbits
, lenbits
, storage_ix
, storage
);
173 /* Write ISUNCOMPRESSED bit. */
174 BrotliWriteBits(1, 1, storage_ix
, storage
);
177 static void BrotliStoreHuffmanTreeOfHuffmanTreeToBitMask(
178 const int num_codes
, const uint8_t* code_length_bitdepth
,
179 size_t* storage_ix
, uint8_t* storage
) {
180 static const uint8_t kStorageOrder
[BROTLI_CODE_LENGTH_CODES
] = {
181 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15
183 /* The bit lengths of the Huffman code over the code length alphabet
184 are compressed with the following static Huffman code:
193 static const uint8_t kHuffmanBitLengthHuffmanCodeSymbols
[6] = {
196 static const uint8_t kHuffmanBitLengthHuffmanCodeBitLengths
[6] = {
200 size_t skip_some
= 0; /* skips none. */
202 /* Throw away trailing zeros: */
203 size_t codes_to_store
= BROTLI_CODE_LENGTH_CODES
;
205 for (; codes_to_store
> 0; --codes_to_store
) {
206 if (code_length_bitdepth
[kStorageOrder
[codes_to_store
- 1]] != 0) {
211 if (code_length_bitdepth
[kStorageOrder
[0]] == 0 &&
212 code_length_bitdepth
[kStorageOrder
[1]] == 0) {
213 skip_some
= 2; /* skips two. */
214 if (code_length_bitdepth
[kStorageOrder
[2]] == 0) {
215 skip_some
= 3; /* skips three. */
218 BrotliWriteBits(2, skip_some
, storage_ix
, storage
);
221 for (i
= skip_some
; i
< codes_to_store
; ++i
) {
222 size_t l
= code_length_bitdepth
[kStorageOrder
[i
]];
223 BrotliWriteBits(kHuffmanBitLengthHuffmanCodeBitLengths
[l
],
224 kHuffmanBitLengthHuffmanCodeSymbols
[l
], storage_ix
, storage
);
229 static void BrotliStoreHuffmanTreeToBitMask(
230 const size_t huffman_tree_size
, const uint8_t* huffman_tree
,
231 const uint8_t* huffman_tree_extra_bits
, const uint8_t* code_length_bitdepth
,
232 const uint16_t* code_length_bitdepth_symbols
,
233 size_t* BROTLI_RESTRICT storage_ix
, uint8_t* BROTLI_RESTRICT storage
) {
235 for (i
= 0; i
< huffman_tree_size
; ++i
) {
236 size_t ix
= huffman_tree
[i
];
237 BrotliWriteBits(code_length_bitdepth
[ix
], code_length_bitdepth_symbols
[ix
],
238 storage_ix
, storage
);
241 case BROTLI_REPEAT_PREVIOUS_CODE_LENGTH
:
242 BrotliWriteBits(2, huffman_tree_extra_bits
[i
], storage_ix
, storage
);
244 case BROTLI_REPEAT_ZERO_CODE_LENGTH
:
245 BrotliWriteBits(3, huffman_tree_extra_bits
[i
], storage_ix
, storage
);
251 static void StoreSimpleHuffmanTree(const uint8_t* depths
,
255 size_t *storage_ix
, uint8_t *storage
) {
256 /* value of 1 indicates a simple Huffman code */
257 BrotliWriteBits(2, 1, storage_ix
, storage
);
258 BrotliWriteBits(2, num_symbols
- 1, storage_ix
, storage
); /* NSYM - 1 */
263 for (i
= 0; i
< num_symbols
; i
++) {
265 for (j
= i
+ 1; j
< num_symbols
; j
++) {
266 if (depths
[symbols
[j
]] < depths
[symbols
[i
]]) {
267 BROTLI_SWAP(size_t, symbols
, j
, i
);
273 if (num_symbols
== 2) {
274 BrotliWriteBits(max_bits
, symbols
[0], storage_ix
, storage
);
275 BrotliWriteBits(max_bits
, symbols
[1], storage_ix
, storage
);
276 } else if (num_symbols
== 3) {
277 BrotliWriteBits(max_bits
, symbols
[0], storage_ix
, storage
);
278 BrotliWriteBits(max_bits
, symbols
[1], storage_ix
, storage
);
279 BrotliWriteBits(max_bits
, symbols
[2], storage_ix
, storage
);
281 BrotliWriteBits(max_bits
, symbols
[0], storage_ix
, storage
);
282 BrotliWriteBits(max_bits
, symbols
[1], storage_ix
, storage
);
283 BrotliWriteBits(max_bits
, symbols
[2], storage_ix
, storage
);
284 BrotliWriteBits(max_bits
, symbols
[3], storage_ix
, storage
);
286 BrotliWriteBits(1, depths
[symbols
[0]] == 1 ? 1 : 0, storage_ix
, storage
);
290 /* num = alphabet size
291 depths = symbol depths */
292 void BrotliStoreHuffmanTree(const uint8_t* depths
, size_t num
,
294 size_t *storage_ix
, uint8_t *storage
) {
295 /* Write the Huffman tree into the brotli-representation.
296 The command alphabet is the largest, so this allocation will fit all
298 uint8_t huffman_tree
[BROTLI_NUM_COMMAND_SYMBOLS
];
299 uint8_t huffman_tree_extra_bits
[BROTLI_NUM_COMMAND_SYMBOLS
];
300 size_t huffman_tree_size
= 0;
301 uint8_t code_length_bitdepth
[BROTLI_CODE_LENGTH_CODES
] = { 0 };
302 uint16_t code_length_bitdepth_symbols
[BROTLI_CODE_LENGTH_CODES
];
303 uint32_t huffman_tree_histogram
[BROTLI_CODE_LENGTH_CODES
] = { 0 };
308 assert(num
<= BROTLI_NUM_COMMAND_SYMBOLS
);
310 BrotliWriteHuffmanTree(depths
, num
, &huffman_tree_size
, huffman_tree
,
311 huffman_tree_extra_bits
);
313 /* Calculate the statistics of the Huffman tree in brotli-representation. */
314 for (i
= 0; i
< huffman_tree_size
; ++i
) {
315 ++huffman_tree_histogram
[huffman_tree
[i
]];
318 for (i
= 0; i
< BROTLI_CODE_LENGTH_CODES
; ++i
) {
319 if (huffman_tree_histogram
[i
]) {
320 if (num_codes
== 0) {
323 } else if (num_codes
== 1) {
330 /* Calculate another Huffman tree to use for compressing both the
331 earlier Huffman tree with. */
332 BrotliCreateHuffmanTree(huffman_tree_histogram
, BROTLI_CODE_LENGTH_CODES
,
333 5, tree
, code_length_bitdepth
);
334 BrotliConvertBitDepthsToSymbols(code_length_bitdepth
,
335 BROTLI_CODE_LENGTH_CODES
,
336 code_length_bitdepth_symbols
);
338 /* Now, we have all the data, let's start storing it */
339 BrotliStoreHuffmanTreeOfHuffmanTreeToBitMask(num_codes
, code_length_bitdepth
,
340 storage_ix
, storage
);
342 if (num_codes
== 1) {
343 code_length_bitdepth
[code
] = 0;
346 /* Store the real huffman tree now. */
347 BrotliStoreHuffmanTreeToBitMask(huffman_tree_size
,
349 huffman_tree_extra_bits
,
350 code_length_bitdepth
,
351 code_length_bitdepth_symbols
,
352 storage_ix
, storage
);
355 /* Builds a Huffman tree from histogram[0:length] into depth[0:length] and
356 bits[0:length] and stores the encoded tree to the bit stream. */
357 static void BuildAndStoreHuffmanTree(const uint32_t *histogram
,
365 size_t s4
[4] = { 0 };
368 for (i
= 0; i
< length
; i
++) {
372 } else if (count
> 4) {
380 size_t max_bits_counter
= length
- 1;
381 while (max_bits_counter
) {
382 max_bits_counter
>>= 1;
388 BrotliWriteBits(4, 1, storage_ix
, storage
);
389 BrotliWriteBits(max_bits
, s4
[0], storage_ix
, storage
);
395 memset(depth
, 0, length
* sizeof(depth
[0]));
396 BrotliCreateHuffmanTree(histogram
, length
, 15, tree
, depth
);
397 BrotliConvertBitDepthsToSymbols(depth
, length
, bits
);
400 StoreSimpleHuffmanTree(depth
, s4
, count
, max_bits
, storage_ix
, storage
);
402 BrotliStoreHuffmanTree(depth
, length
, tree
, storage_ix
, storage
);
406 static BROTLI_INLINE BROTLI_BOOL
SortHuffmanTree(
407 const HuffmanTree
* v0
, const HuffmanTree
* v1
) {
408 return TO_BROTLI_BOOL(v0
->total_count_
< v1
->total_count_
);
411 void BrotliBuildAndStoreHuffmanTreeFast(MemoryManager
* m
,
412 const uint32_t* histogram
,
413 const size_t histogram_total
,
414 const size_t max_bits
,
415 uint8_t* depth
, uint16_t* bits
,
419 size_t symbols
[4] = { 0 };
421 size_t total
= histogram_total
;
423 if (histogram
[length
]) {
425 symbols
[count
] = length
;
428 total
-= histogram
[length
];
434 BrotliWriteBits(4, 1, storage_ix
, storage
);
435 BrotliWriteBits(max_bits
, symbols
[0], storage_ix
, storage
);
436 depth
[symbols
[0]] = 0;
437 bits
[symbols
[0]] = 0;
441 memset(depth
, 0, length
* sizeof(depth
[0]));
443 const size_t max_tree_size
= 2 * length
+ 1;
444 HuffmanTree
* tree
= BROTLI_ALLOC(m
, HuffmanTree
, max_tree_size
);
445 uint32_t count_limit
;
446 if (BROTLI_IS_OOM(m
)) return;
447 for (count_limit
= 1; ; count_limit
*= 2) {
448 HuffmanTree
* node
= tree
;
450 for (l
= length
; l
!= 0;) {
453 if (PREDICT_TRUE(histogram
[l
] >= count_limit
)) {
454 InitHuffmanTree(node
, histogram
[l
], -1, (int16_t)l
);
456 InitHuffmanTree(node
, count_limit
, -1, (int16_t)l
);
462 const int n
= (int)(node
- tree
);
463 HuffmanTree sentinel
;
464 int i
= 0; /* Points to the next leaf node. */
465 int j
= n
+ 1; /* Points to the next non-leaf node. */
468 SortHuffmanTreeItems(tree
, (size_t)n
, SortHuffmanTree
);
470 [0, n): the sorted leaf nodes that we start with.
471 [n]: we add a sentinel here.
472 [n + 1, 2n): new parent nodes are added here, starting from
473 (n+1). These are naturally in ascending order.
474 [2n]: we add a sentinel at the end as well.
475 There will be (2n+1) elements at the end. */
476 InitHuffmanTree(&sentinel
, BROTLI_UINT32_MAX
, -1, -1);
480 for (k
= n
- 1; k
> 0; --k
) {
482 if (tree
[i
].total_count_
<= tree
[j
].total_count_
) {
489 if (tree
[i
].total_count_
<= tree
[j
].total_count_
) {
496 /* The sentinel node becomes the parent node. */
497 node
[-1].total_count_
=
498 tree
[left
].total_count_
+ tree
[right
].total_count_
;
499 node
[-1].index_left_
= (int16_t)left
;
500 node
[-1].index_right_or_value_
= (int16_t)right
;
501 /* Add back the last sentinel node. */
504 if (BrotliSetDepth(2 * n
- 1, tree
, depth
, 14)) {
505 /* We need to pack the Huffman tree in 14 bits. If this was not
506 successful, add fake entities to the lowest values and retry. */
511 BROTLI_FREE(m
, tree
);
513 BrotliConvertBitDepthsToSymbols(depth
, length
, bits
);
516 /* value of 1 indicates a simple Huffman code */
517 BrotliWriteBits(2, 1, storage_ix
, storage
);
518 BrotliWriteBits(2, count
- 1, storage_ix
, storage
); /* NSYM - 1 */
521 for (i
= 0; i
< count
; i
++) {
523 for (j
= i
+ 1; j
< count
; j
++) {
524 if (depth
[symbols
[j
]] < depth
[symbols
[i
]]) {
525 BROTLI_SWAP(size_t, symbols
, j
, i
);
531 BrotliWriteBits(max_bits
, symbols
[0], storage_ix
, storage
);
532 BrotliWriteBits(max_bits
, symbols
[1], storage_ix
, storage
);
533 } else if (count
== 3) {
534 BrotliWriteBits(max_bits
, symbols
[0], storage_ix
, storage
);
535 BrotliWriteBits(max_bits
, symbols
[1], storage_ix
, storage
);
536 BrotliWriteBits(max_bits
, symbols
[2], storage_ix
, storage
);
538 BrotliWriteBits(max_bits
, symbols
[0], storage_ix
, storage
);
539 BrotliWriteBits(max_bits
, symbols
[1], storage_ix
, storage
);
540 BrotliWriteBits(max_bits
, symbols
[2], storage_ix
, storage
);
541 BrotliWriteBits(max_bits
, symbols
[3], storage_ix
, storage
);
543 BrotliWriteBits(1, depth
[symbols
[0]] == 1 ? 1 : 0, storage_ix
, storage
);
546 uint8_t previous_value
= 8;
548 /* Complex Huffman Tree */
549 StoreStaticCodeLengthCode(storage_ix
, storage
);
551 /* Actual rle coding. */
552 for (i
= 0; i
< length
;) {
553 const uint8_t value
= depth
[i
];
556 for (k
= i
+ 1; k
< length
&& depth
[k
] == value
; ++k
) {
561 BrotliWriteBits(kZeroRepsDepth
[reps
], kZeroRepsBits
[reps
],
562 storage_ix
, storage
);
564 if (previous_value
!= value
) {
565 BrotliWriteBits(kCodeLengthDepth
[value
], kCodeLengthBits
[value
],
566 storage_ix
, storage
);
572 BrotliWriteBits(kCodeLengthDepth
[value
], kCodeLengthBits
[value
],
573 storage_ix
, storage
);
577 BrotliWriteBits(kNonZeroRepsDepth
[reps
], kNonZeroRepsBits
[reps
],
578 storage_ix
, storage
);
580 previous_value
= value
;
586 static size_t IndexOf(const uint8_t* v
, size_t v_size
, uint8_t value
) {
588 for (; i
< v_size
; ++i
) {
589 if (v
[i
] == value
) return i
;
594 static void MoveToFront(uint8_t* v
, size_t index
) {
595 uint8_t value
= v
[index
];
597 for (i
= index
; i
!= 0; --i
) {
603 static void MoveToFrontTransform(const uint32_t* BROTLI_RESTRICT v_in
,
613 for (i
= 1; i
< v_size
; ++i
) {
614 if (v_in
[i
] > max_value
) max_value
= v_in
[i
];
616 assert(max_value
< 256u);
617 for (i
= 0; i
<= max_value
; ++i
) {
621 size_t mtf_size
= max_value
+ 1;
622 for (i
= 0; i
< v_size
; ++i
) {
623 size_t index
= IndexOf(mtf
, mtf_size
, (uint8_t)v_in
[i
]);
624 assert(index
< mtf_size
);
625 v_out
[i
] = (uint32_t)index
;
626 MoveToFront(mtf
, index
);
631 /* Finds runs of zeros in v[0..in_size) and replaces them with a prefix code of
632 the run length plus extra bits (lower 9 bits is the prefix code and the rest
633 are the extra bits). Non-zero values in v[] are shifted by
634 *max_length_prefix. Will not create prefix codes bigger than the initial
635 value of *max_run_length_prefix. The prefix code of run length L is simply
636 Log2Floor(L) and the number of extra bits is the same as the prefix code. */
637 static void RunLengthCodeZeros(const size_t in_size
,
638 uint32_t* BROTLI_RESTRICT v
, size_t* BROTLI_RESTRICT out_size
,
639 uint32_t* BROTLI_RESTRICT max_run_length_prefix
) {
640 uint32_t max_reps
= 0;
643 for (i
= 0; i
< in_size
;) {
645 for (; i
< in_size
&& v
[i
] != 0; ++i
) ;
646 for (; i
< in_size
&& v
[i
] == 0; ++i
) {
649 max_reps
= BROTLI_MAX(uint32_t, reps
, max_reps
);
651 max_prefix
= max_reps
> 0 ? Log2FloorNonZero(max_reps
) : 0;
652 max_prefix
= BROTLI_MIN(uint32_t, max_prefix
, *max_run_length_prefix
);
653 *max_run_length_prefix
= max_prefix
;
655 for (i
= 0; i
< in_size
;) {
656 assert(*out_size
<= i
);
658 v
[*out_size
] = v
[i
] + *max_run_length_prefix
;
664 for (k
= i
+ 1; k
< in_size
&& v
[k
] == 0; ++k
) {
669 if (reps
< (2u << max_prefix
)) {
670 uint32_t run_length_prefix
= Log2FloorNonZero(reps
);
671 const uint32_t extra_bits
= reps
- (1u << run_length_prefix
);
672 v
[*out_size
] = run_length_prefix
+ (extra_bits
<< 9);
676 const uint32_t extra_bits
= (1u << max_prefix
) - 1u;
677 v
[*out_size
] = max_prefix
+ (extra_bits
<< 9);
678 reps
-= (2u << max_prefix
) - 1u;
686 #define SYMBOL_BITS 9
688 static void EncodeContextMap(MemoryManager
* m
,
689 const uint32_t* context_map
,
690 size_t context_map_size
,
693 size_t* storage_ix
, uint8_t* storage
) {
695 uint32_t* rle_symbols
;
696 uint32_t max_run_length_prefix
= 6;
697 size_t num_rle_symbols
= 0;
698 uint32_t histogram
[BROTLI_MAX_CONTEXT_MAP_SYMBOLS
];
699 static const uint32_t kSymbolMask
= (1u << SYMBOL_BITS
) - 1u;
700 uint8_t depths
[BROTLI_MAX_CONTEXT_MAP_SYMBOLS
];
701 uint16_t bits
[BROTLI_MAX_CONTEXT_MAP_SYMBOLS
];
703 StoreVarLenUint8(num_clusters
- 1, storage_ix
, storage
);
705 if (num_clusters
== 1) {
709 rle_symbols
= BROTLI_ALLOC(m
, uint32_t, context_map_size
);
710 if (BROTLI_IS_OOM(m
)) return;
711 MoveToFrontTransform(context_map
, context_map_size
, rle_symbols
);
712 RunLengthCodeZeros(context_map_size
, rle_symbols
,
713 &num_rle_symbols
, &max_run_length_prefix
);
714 memset(histogram
, 0, sizeof(histogram
));
715 for (i
= 0; i
< num_rle_symbols
; ++i
) {
716 ++histogram
[rle_symbols
[i
] & kSymbolMask
];
719 BROTLI_BOOL use_rle
= TO_BROTLI_BOOL(max_run_length_prefix
> 0);
720 BrotliWriteBits(1, (uint64_t)use_rle
, storage_ix
, storage
);
722 BrotliWriteBits(4, max_run_length_prefix
- 1, storage_ix
, storage
);
725 BuildAndStoreHuffmanTree(histogram
, num_clusters
+ max_run_length_prefix
,
726 tree
, depths
, bits
, storage_ix
, storage
);
727 for (i
= 0; i
< num_rle_symbols
; ++i
) {
728 const uint32_t rle_symbol
= rle_symbols
[i
] & kSymbolMask
;
729 const uint32_t extra_bits_val
= rle_symbols
[i
] >> SYMBOL_BITS
;
730 BrotliWriteBits(depths
[rle_symbol
], bits
[rle_symbol
], storage_ix
, storage
);
731 if (rle_symbol
> 0 && rle_symbol
<= max_run_length_prefix
) {
732 BrotliWriteBits(rle_symbol
, extra_bits_val
, storage_ix
, storage
);
735 BrotliWriteBits(1, 1, storage_ix
, storage
); /* use move-to-front */
736 BROTLI_FREE(m
, rle_symbols
);
739 /* Stores the block switch command with index block_ix to the bit stream. */
740 static BROTLI_INLINE
void StoreBlockSwitch(BlockSplitCode
* code
,
741 const uint32_t block_len
,
742 const uint8_t block_type
,
743 BROTLI_BOOL is_first_block
,
746 size_t typecode
= NextBlockTypeCode(&code
->type_code_calculator
, block_type
);
750 if (!is_first_block
) {
751 BrotliWriteBits(code
->type_depths
[typecode
], code
->type_bits
[typecode
],
752 storage_ix
, storage
);
754 GetBlockLengthPrefixCode(block_len
, &lencode
, &len_nextra
, &len_extra
);
756 BrotliWriteBits(code
->length_depths
[lencode
], code
->length_bits
[lencode
],
757 storage_ix
, storage
);
758 BrotliWriteBits(len_nextra
, len_extra
, storage_ix
, storage
);
761 /* Builds a BlockSplitCode data structure from the block split given by the
762 vector of block types and block lengths and stores it to the bit stream. */
763 static void BuildAndStoreBlockSplitCode(const uint8_t* types
,
764 const uint32_t* lengths
,
765 const size_t num_blocks
,
766 const size_t num_types
,
768 BlockSplitCode
* code
,
771 uint32_t type_histo
[BROTLI_MAX_BLOCK_TYPE_SYMBOLS
];
772 uint32_t length_histo
[BROTLI_NUM_BLOCK_LEN_SYMBOLS
];
774 BlockTypeCodeCalculator type_code_calculator
;
775 memset(type_histo
, 0, (num_types
+ 2) * sizeof(type_histo
[0]));
776 memset(length_histo
, 0, sizeof(length_histo
));
777 InitBlockTypeCodeCalculator(&type_code_calculator
);
778 for (i
= 0; i
< num_blocks
; ++i
) {
779 size_t type_code
= NextBlockTypeCode(&type_code_calculator
, types
[i
]);
780 if (i
!= 0) ++type_histo
[type_code
];
781 ++length_histo
[BlockLengthPrefixCode(lengths
[i
])];
783 StoreVarLenUint8(num_types
- 1, storage_ix
, storage
);
784 if (num_types
> 1) { /* TODO: else? could StoreBlockSwitch occur? */
785 BuildAndStoreHuffmanTree(&type_histo
[0], num_types
+ 2, tree
,
786 &code
->type_depths
[0], &code
->type_bits
[0],
787 storage_ix
, storage
);
788 BuildAndStoreHuffmanTree(&length_histo
[0], BROTLI_NUM_BLOCK_LEN_SYMBOLS
,
789 tree
, &code
->length_depths
[0],
790 &code
->length_bits
[0], storage_ix
, storage
);
791 StoreBlockSwitch(code
, lengths
[0], types
[0], 1, storage_ix
, storage
);
795 /* Stores a context map where the histogram type is always the block type. */
796 static void StoreTrivialContextMap(size_t num_types
,
801 StoreVarLenUint8(num_types
- 1, storage_ix
, storage
);
803 size_t repeat_code
= context_bits
- 1u;
804 size_t repeat_bits
= (1u << repeat_code
) - 1u;
805 size_t alphabet_size
= num_types
+ repeat_code
;
806 uint32_t histogram
[BROTLI_MAX_CONTEXT_MAP_SYMBOLS
];
807 uint8_t depths
[BROTLI_MAX_CONTEXT_MAP_SYMBOLS
];
808 uint16_t bits
[BROTLI_MAX_CONTEXT_MAP_SYMBOLS
];
810 memset(histogram
, 0, alphabet_size
* sizeof(histogram
[0]));
812 BrotliWriteBits(1, 1, storage_ix
, storage
);
813 BrotliWriteBits(4, repeat_code
- 1, storage_ix
, storage
);
814 histogram
[repeat_code
] = (uint32_t)num_types
;
816 for (i
= context_bits
; i
< alphabet_size
; ++i
) {
819 BuildAndStoreHuffmanTree(histogram
, alphabet_size
, tree
,
820 depths
, bits
, storage_ix
, storage
);
821 for (i
= 0; i
< num_types
; ++i
) {
822 size_t code
= (i
== 0 ? 0 : i
+ context_bits
- 1);
823 BrotliWriteBits(depths
[code
], bits
[code
], storage_ix
, storage
);
825 depths
[repeat_code
], bits
[repeat_code
], storage_ix
, storage
);
826 BrotliWriteBits(repeat_code
, repeat_bits
, storage_ix
, storage
);
828 /* Write IMTF (inverse-move-to-front) bit. */
829 BrotliWriteBits(1, 1, storage_ix
, storage
);
833 /* Manages the encoding of one block category (literal, command or distance). */
834 typedef struct BlockEncoder
{
835 size_t alphabet_size_
;
836 size_t num_block_types_
;
837 const uint8_t* block_types_
; /* Not owned. */
838 const uint32_t* block_lengths_
; /* Not owned. */
840 BlockSplitCode block_split_code_
;
848 static void InitBlockEncoder(BlockEncoder
* self
, size_t alphabet_size
,
849 size_t num_block_types
, const uint8_t* block_types
,
850 const uint32_t* block_lengths
, const size_t num_blocks
) {
851 self
->alphabet_size_
= alphabet_size
;
852 self
->num_block_types_
= num_block_types
;
853 self
->block_types_
= block_types
;
854 self
->block_lengths_
= block_lengths
;
855 self
->num_blocks_
= num_blocks
;
856 InitBlockTypeCodeCalculator(&self
->block_split_code_
.type_code_calculator
);
858 self
->block_len_
= num_blocks
== 0 ? 0 : block_lengths
[0];
859 self
->entropy_ix_
= 0;
864 static void CleanupBlockEncoder(MemoryManager
* m
, BlockEncoder
* self
) {
865 BROTLI_FREE(m
, self
->depths_
);
866 BROTLI_FREE(m
, self
->bits_
);
869 /* Creates entropy codes of block lengths and block types and stores them
870 to the bit stream. */
871 static void BuildAndStoreBlockSwitchEntropyCodes(BlockEncoder
* self
,
872 HuffmanTree
* tree
, size_t* storage_ix
, uint8_t* storage
) {
873 BuildAndStoreBlockSplitCode(self
->block_types_
, self
->block_lengths_
,
874 self
->num_blocks_
, self
->num_block_types_
, tree
, &self
->block_split_code_
,
875 storage_ix
, storage
);
878 /* Stores the next symbol with the entropy code of the current block type.
879 Updates the block type and block length at block boundaries. */
880 static void StoreSymbol(BlockEncoder
* self
, size_t symbol
, size_t* storage_ix
,
882 if (self
->block_len_
== 0) {
883 size_t block_ix
= ++self
->block_ix_
;
884 uint32_t block_len
= self
->block_lengths_
[block_ix
];
885 uint8_t block_type
= self
->block_types_
[block_ix
];
886 self
->block_len_
= block_len
;
887 self
->entropy_ix_
= block_type
* self
->alphabet_size_
;
888 StoreBlockSwitch(&self
->block_split_code_
, block_len
, block_type
, 0,
889 storage_ix
, storage
);
893 size_t ix
= self
->entropy_ix_
+ symbol
;
894 BrotliWriteBits(self
->depths_
[ix
], self
->bits_
[ix
], storage_ix
, storage
);
898 /* Stores the next symbol with the entropy code of the current block type and
900 Updates the block type and block length at block boundaries. */
901 static void StoreSymbolWithContext(BlockEncoder
* self
, size_t symbol
,
902 size_t context
, const uint32_t* context_map
, size_t* storage_ix
,
903 uint8_t* storage
, const size_t context_bits
) {
904 if (self
->block_len_
== 0) {
905 size_t block_ix
= ++self
->block_ix_
;
906 uint32_t block_len
= self
->block_lengths_
[block_ix
];
907 uint8_t block_type
= self
->block_types_
[block_ix
];
908 self
->block_len_
= block_len
;
909 self
->entropy_ix_
= (size_t)block_type
<< context_bits
;
910 StoreBlockSwitch(&self
->block_split_code_
, block_len
, block_type
, 0,
911 storage_ix
, storage
);
915 size_t histo_ix
= context_map
[self
->entropy_ix_
+ context
];
916 size_t ix
= histo_ix
* self
->alphabet_size_
+ symbol
;
917 BrotliWriteBits(self
->depths_
[ix
], self
->bits_
[ix
], storage_ix
, storage
);
921 #define FN(X) X ## Literal
922 /* NOLINTNEXTLINE(build/include) */
923 #include "./block_encoder_inc.h"
926 #define FN(X) X ## Command
927 /* NOLINTNEXTLINE(build/include) */
928 #include "./block_encoder_inc.h"
931 #define FN(X) X ## Distance
932 /* NOLINTNEXTLINE(build/include) */
933 #include "./block_encoder_inc.h"
936 static void JumpToByteBoundary(size_t* storage_ix
, uint8_t* storage
) {
937 *storage_ix
= (*storage_ix
+ 7u) & ~7u;
938 storage
[*storage_ix
>> 3] = 0;
941 void BrotliStoreMetaBlock(MemoryManager
* m
,
942 const uint8_t* input
,
949 uint32_t num_direct_distance_codes
,
950 uint32_t distance_postfix_bits
,
951 ContextType literal_context_mode
,
952 const Command
*commands
,
954 const MetaBlockSplit
* mb
,
957 size_t pos
= start_pos
;
959 size_t num_distance_codes
=
960 BROTLI_NUM_DISTANCE_SHORT_CODES
+ num_direct_distance_codes
+
961 (48u << distance_postfix_bits
);
963 BlockEncoder literal_enc
;
964 BlockEncoder command_enc
;
965 BlockEncoder distance_enc
;
967 StoreCompressedMetaBlockHeader(is_last
, length
, storage_ix
, storage
);
969 tree
= BROTLI_ALLOC(m
, HuffmanTree
, MAX_HUFFMAN_TREE_SIZE
);
970 if (BROTLI_IS_OOM(m
)) return;
971 InitBlockEncoder(&literal_enc
, 256, mb
->literal_split
.num_types
,
972 mb
->literal_split
.types
, mb
->literal_split
.lengths
,
973 mb
->literal_split
.num_blocks
);
974 InitBlockEncoder(&command_enc
, BROTLI_NUM_COMMAND_SYMBOLS
,
975 mb
->command_split
.num_types
, mb
->command_split
.types
,
976 mb
->command_split
.lengths
, mb
->command_split
.num_blocks
);
977 InitBlockEncoder(&distance_enc
, num_distance_codes
,
978 mb
->distance_split
.num_types
, mb
->distance_split
.types
,
979 mb
->distance_split
.lengths
, mb
->distance_split
.num_blocks
);
981 BuildAndStoreBlockSwitchEntropyCodes(&literal_enc
, tree
, storage_ix
, storage
);
982 BuildAndStoreBlockSwitchEntropyCodes(&command_enc
, tree
, storage_ix
, storage
);
983 BuildAndStoreBlockSwitchEntropyCodes(
984 &distance_enc
, tree
, storage_ix
, storage
);
986 BrotliWriteBits(2, distance_postfix_bits
, storage_ix
, storage
);
987 BrotliWriteBits(4, num_direct_distance_codes
>> distance_postfix_bits
,
988 storage_ix
, storage
);
989 for (i
= 0; i
< mb
->literal_split
.num_types
; ++i
) {
990 BrotliWriteBits(2, literal_context_mode
, storage_ix
, storage
);
993 if (mb
->literal_context_map_size
== 0) {
994 StoreTrivialContextMap(mb
->literal_histograms_size
,
995 BROTLI_LITERAL_CONTEXT_BITS
, tree
, storage_ix
, storage
);
998 mb
->literal_context_map
, mb
->literal_context_map_size
,
999 mb
->literal_histograms_size
, tree
, storage_ix
, storage
);
1000 if (BROTLI_IS_OOM(m
)) return;
1003 if (mb
->distance_context_map_size
== 0) {
1004 StoreTrivialContextMap(mb
->distance_histograms_size
,
1005 BROTLI_DISTANCE_CONTEXT_BITS
, tree
, storage_ix
, storage
);
1008 mb
->distance_context_map
, mb
->distance_context_map_size
,
1009 mb
->distance_histograms_size
, tree
, storage_ix
, storage
);
1010 if (BROTLI_IS_OOM(m
)) return;
1013 BuildAndStoreEntropyCodesLiteral(m
, &literal_enc
, mb
->literal_histograms
,
1014 mb
->literal_histograms_size
, tree
, storage_ix
, storage
);
1015 if (BROTLI_IS_OOM(m
)) return;
1016 BuildAndStoreEntropyCodesCommand(m
, &command_enc
, mb
->command_histograms
,
1017 mb
->command_histograms_size
, tree
, storage_ix
, storage
);
1018 if (BROTLI_IS_OOM(m
)) return;
1019 BuildAndStoreEntropyCodesDistance(m
, &distance_enc
, mb
->distance_histograms
,
1020 mb
->distance_histograms_size
, tree
, storage_ix
, storage
);
1021 if (BROTLI_IS_OOM(m
)) return;
1022 BROTLI_FREE(m
, tree
);
1024 for (i
= 0; i
< n_commands
; ++i
) {
1025 const Command cmd
= commands
[i
];
1026 size_t cmd_code
= cmd
.cmd_prefix_
;
1027 StoreSymbol(&command_enc
, cmd_code
, storage_ix
, storage
);
1028 StoreCommandExtra(&cmd
, storage_ix
, storage
);
1029 if (mb
->literal_context_map_size
== 0) {
1031 for (j
= cmd
.insert_len_
; j
!= 0; --j
) {
1032 StoreSymbol(&literal_enc
, input
[pos
& mask
], storage_ix
, storage
);
1037 for (j
= cmd
.insert_len_
; j
!= 0; --j
) {
1038 size_t context
= Context(prev_byte
, prev_byte2
, literal_context_mode
);
1039 uint8_t literal
= input
[pos
& mask
];
1040 StoreSymbolWithContext(&literal_enc
, literal
, context
,
1041 mb
->literal_context_map
, storage_ix
, storage
,
1042 BROTLI_LITERAL_CONTEXT_BITS
);
1043 prev_byte2
= prev_byte
;
1044 prev_byte
= literal
;
1048 pos
+= CommandCopyLen(&cmd
);
1049 if (CommandCopyLen(&cmd
)) {
1050 prev_byte2
= input
[(pos
- 2) & mask
];
1051 prev_byte
= input
[(pos
- 1) & mask
];
1052 if (cmd
.cmd_prefix_
>= 128) {
1053 size_t dist_code
= cmd
.dist_prefix_
;
1054 uint32_t distnumextra
= cmd
.dist_extra_
>> 24;
1055 uint64_t distextra
= cmd
.dist_extra_
& 0xffffff;
1056 if (mb
->distance_context_map_size
== 0) {
1057 StoreSymbol(&distance_enc
, dist_code
, storage_ix
, storage
);
1059 size_t context
= CommandDistanceContext(&cmd
);
1060 StoreSymbolWithContext(&distance_enc
, dist_code
, context
,
1061 mb
->distance_context_map
, storage_ix
, storage
,
1062 BROTLI_DISTANCE_CONTEXT_BITS
);
1064 BrotliWriteBits(distnumextra
, distextra
, storage_ix
, storage
);
1068 CleanupBlockEncoder(m
, &distance_enc
);
1069 CleanupBlockEncoder(m
, &command_enc
);
1070 CleanupBlockEncoder(m
, &literal_enc
);
1072 JumpToByteBoundary(storage_ix
, storage
);
1076 static void BuildHistograms(const uint8_t* input
,
1079 const Command
*commands
,
1081 HistogramLiteral
* lit_histo
,
1082 HistogramCommand
* cmd_histo
,
1083 HistogramDistance
* dist_histo
) {
1084 size_t pos
= start_pos
;
1086 for (i
= 0; i
< n_commands
; ++i
) {
1087 const Command cmd
= commands
[i
];
1089 HistogramAddCommand(cmd_histo
, cmd
.cmd_prefix_
);
1090 for (j
= cmd
.insert_len_
; j
!= 0; --j
) {
1091 HistogramAddLiteral(lit_histo
, input
[pos
& mask
]);
1094 pos
+= CommandCopyLen(&cmd
);
1095 if (CommandCopyLen(&cmd
) && cmd
.cmd_prefix_
>= 128) {
1096 HistogramAddDistance(dist_histo
, cmd
.dist_prefix_
);
1101 static void StoreDataWithHuffmanCodes(const uint8_t* input
,
1104 const Command
*commands
,
1106 const uint8_t* lit_depth
,
1107 const uint16_t* lit_bits
,
1108 const uint8_t* cmd_depth
,
1109 const uint16_t* cmd_bits
,
1110 const uint8_t* dist_depth
,
1111 const uint16_t* dist_bits
,
1114 size_t pos
= start_pos
;
1116 for (i
= 0; i
< n_commands
; ++i
) {
1117 const Command cmd
= commands
[i
];
1118 const size_t cmd_code
= cmd
.cmd_prefix_
;
1121 cmd_depth
[cmd_code
], cmd_bits
[cmd_code
], storage_ix
, storage
);
1122 StoreCommandExtra(&cmd
, storage_ix
, storage
);
1123 for (j
= cmd
.insert_len_
; j
!= 0; --j
) {
1124 const uint8_t literal
= input
[pos
& mask
];
1126 lit_depth
[literal
], lit_bits
[literal
], storage_ix
, storage
);
1129 pos
+= CommandCopyLen(&cmd
);
1130 if (CommandCopyLen(&cmd
) && cmd
.cmd_prefix_
>= 128) {
1131 const size_t dist_code
= cmd
.dist_prefix_
;
1132 const uint32_t distnumextra
= cmd
.dist_extra_
>> 24;
1133 const uint32_t distextra
= cmd
.dist_extra_
& 0xffffff;
1134 BrotliWriteBits(dist_depth
[dist_code
], dist_bits
[dist_code
],
1135 storage_ix
, storage
);
1136 BrotliWriteBits(distnumextra
, distextra
, storage_ix
, storage
);
1141 void BrotliStoreMetaBlockTrivial(MemoryManager
* m
,
1142 const uint8_t* input
,
1146 BROTLI_BOOL is_last
,
1147 const Command
*commands
,
1151 HistogramLiteral lit_histo
;
1152 HistogramCommand cmd_histo
;
1153 HistogramDistance dist_histo
;
1154 uint8_t lit_depth
[256];
1155 uint16_t lit_bits
[256];
1156 uint8_t cmd_depth
[BROTLI_NUM_COMMAND_SYMBOLS
];
1157 uint16_t cmd_bits
[BROTLI_NUM_COMMAND_SYMBOLS
];
1158 uint8_t dist_depth
[64];
1159 uint16_t dist_bits
[64];
1162 StoreCompressedMetaBlockHeader(is_last
, length
, storage_ix
, storage
);
1164 HistogramClearLiteral(&lit_histo
);
1165 HistogramClearCommand(&cmd_histo
);
1166 HistogramClearDistance(&dist_histo
);
1168 BuildHistograms(input
, start_pos
, mask
, commands
, n_commands
,
1169 &lit_histo
, &cmd_histo
, &dist_histo
);
1171 BrotliWriteBits(13, 0, storage_ix
, storage
);
1173 tree
= BROTLI_ALLOC(m
, HuffmanTree
, MAX_HUFFMAN_TREE_SIZE
);
1174 if (BROTLI_IS_OOM(m
)) return;
1175 BuildAndStoreHuffmanTree(lit_histo
.data_
, 256, tree
,
1176 lit_depth
, lit_bits
,
1177 storage_ix
, storage
);
1178 BuildAndStoreHuffmanTree(cmd_histo
.data_
, BROTLI_NUM_COMMAND_SYMBOLS
, tree
,
1179 cmd_depth
, cmd_bits
,
1180 storage_ix
, storage
);
1181 BuildAndStoreHuffmanTree(dist_histo
.data_
, 64, tree
,
1182 dist_depth
, dist_bits
,
1183 storage_ix
, storage
);
1184 BROTLI_FREE(m
, tree
);
1185 StoreDataWithHuffmanCodes(input
, start_pos
, mask
, commands
,
1186 n_commands
, lit_depth
, lit_bits
,
1187 cmd_depth
, cmd_bits
,
1188 dist_depth
, dist_bits
,
1189 storage_ix
, storage
);
1191 JumpToByteBoundary(storage_ix
, storage
);
1195 void BrotliStoreMetaBlockFast(MemoryManager
* m
,
1196 const uint8_t* input
,
1200 BROTLI_BOOL is_last
,
1201 const Command
*commands
,
1205 StoreCompressedMetaBlockHeader(is_last
, length
, storage_ix
, storage
);
1207 BrotliWriteBits(13, 0, storage_ix
, storage
);
1209 if (n_commands
<= 128) {
1210 uint32_t histogram
[BROTLI_NUM_LITERAL_SYMBOLS
] = { 0 };
1211 size_t pos
= start_pos
;
1212 size_t num_literals
= 0;
1214 uint8_t lit_depth
[BROTLI_NUM_LITERAL_SYMBOLS
];
1215 uint16_t lit_bits
[BROTLI_NUM_LITERAL_SYMBOLS
];
1216 for (i
= 0; i
< n_commands
; ++i
) {
1217 const Command cmd
= commands
[i
];
1219 for (j
= cmd
.insert_len_
; j
!= 0; --j
) {
1220 ++histogram
[input
[pos
& mask
]];
1223 num_literals
+= cmd
.insert_len_
;
1224 pos
+= CommandCopyLen(&cmd
);
1226 BrotliBuildAndStoreHuffmanTreeFast(m
, histogram
, num_literals
,
1228 lit_depth
, lit_bits
,
1229 storage_ix
, storage
);
1230 if (BROTLI_IS_OOM(m
)) return;
1231 StoreStaticCommandHuffmanTree(storage_ix
, storage
);
1232 StoreStaticDistanceHuffmanTree(storage_ix
, storage
);
1233 StoreDataWithHuffmanCodes(input
, start_pos
, mask
, commands
,
1234 n_commands
, lit_depth
, lit_bits
,
1235 kStaticCommandCodeDepth
,
1236 kStaticCommandCodeBits
,
1237 kStaticDistanceCodeDepth
,
1238 kStaticDistanceCodeBits
,
1239 storage_ix
, storage
);
1241 HistogramLiteral lit_histo
;
1242 HistogramCommand cmd_histo
;
1243 HistogramDistance dist_histo
;
1244 uint8_t lit_depth
[BROTLI_NUM_LITERAL_SYMBOLS
];
1245 uint16_t lit_bits
[BROTLI_NUM_LITERAL_SYMBOLS
];
1246 uint8_t cmd_depth
[BROTLI_NUM_COMMAND_SYMBOLS
];
1247 uint16_t cmd_bits
[BROTLI_NUM_COMMAND_SYMBOLS
];
1248 uint8_t dist_depth
[64];
1249 uint16_t dist_bits
[64];
1250 HistogramClearLiteral(&lit_histo
);
1251 HistogramClearCommand(&cmd_histo
);
1252 HistogramClearDistance(&dist_histo
);
1253 BuildHistograms(input
, start_pos
, mask
, commands
, n_commands
,
1254 &lit_histo
, &cmd_histo
, &dist_histo
);
1255 BrotliBuildAndStoreHuffmanTreeFast(m
, lit_histo
.data_
,
1256 lit_histo
.total_count_
,
1258 lit_depth
, lit_bits
,
1259 storage_ix
, storage
);
1260 if (BROTLI_IS_OOM(m
)) return;
1261 BrotliBuildAndStoreHuffmanTreeFast(m
, cmd_histo
.data_
,
1262 cmd_histo
.total_count_
,
1263 /* max_bits = */ 10,
1264 cmd_depth
, cmd_bits
,
1265 storage_ix
, storage
);
1266 if (BROTLI_IS_OOM(m
)) return;
1267 BrotliBuildAndStoreHuffmanTreeFast(m
, dist_histo
.data_
,
1268 dist_histo
.total_count_
,
1270 dist_depth
, dist_bits
,
1271 storage_ix
, storage
);
1272 if (BROTLI_IS_OOM(m
)) return;
1273 StoreDataWithHuffmanCodes(input
, start_pos
, mask
, commands
,
1274 n_commands
, lit_depth
, lit_bits
,
1275 cmd_depth
, cmd_bits
,
1276 dist_depth
, dist_bits
,
1277 storage_ix
, storage
);
1281 JumpToByteBoundary(storage_ix
, storage
);
1285 /* This is for storing uncompressed blocks (simple raw storage of
1287 void BrotliStoreUncompressedMetaBlock(BROTLI_BOOL is_final_block
,
1288 const uint8_t * BROTLI_RESTRICT input
,
1289 size_t position
, size_t mask
,
1291 size_t * BROTLI_RESTRICT storage_ix
,
1292 uint8_t * BROTLI_RESTRICT storage
) {
1293 size_t masked_pos
= position
& mask
;
1294 BrotliStoreUncompressedMetaBlockHeader(len
, storage_ix
, storage
);
1295 JumpToByteBoundary(storage_ix
, storage
);
1297 if (masked_pos
+ len
> mask
+ 1) {
1298 size_t len1
= mask
+ 1 - masked_pos
;
1299 memcpy(&storage
[*storage_ix
>> 3], &input
[masked_pos
], len1
);
1300 *storage_ix
+= len1
<< 3;
1304 memcpy(&storage
[*storage_ix
>> 3], &input
[masked_pos
], len
);
1305 *storage_ix
+= len
<< 3;
1307 /* We need to clear the next 4 bytes to continue to be
1308 compatible with BrotliWriteBits. */
1309 BrotliWriteBitsPrepareStorage(*storage_ix
, storage
);
1311 /* Since the uncompressed block itself may not be the final block, add an
1312 empty one after this. */
1313 if (is_final_block
) {
1314 BrotliWriteBits(1, 1, storage_ix
, storage
); /* islast */
1315 BrotliWriteBits(1, 1, storage_ix
, storage
); /* isempty */
1316 JumpToByteBoundary(storage_ix
, storage
);
1320 void BrotliStoreSyncMetaBlock(size_t* BROTLI_RESTRICT storage_ix
,
1321 uint8_t* BROTLI_RESTRICT storage
) {
1322 /* Empty metadata meta-block bit pattern:
1324 2 bits: num nibbles (3)
1326 2 bits: metadata length bytes (0) */
1327 BrotliWriteBits(6, 6, storage_ix
, storage
);
1328 JumpToByteBoundary(storage_ix
, storage
);
1332 #if defined(__cplusplus) || defined(c_plusplus)