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