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