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