1 // Copyright 2009 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package flate 6 7 import ( 8 "io" 9 ) 10 11 const ( 12 // The largest offset code. 13 offsetCodeCount = 30 14 15 // The special code used to mark the end of a block. 16 endBlockMarker = 256 17 18 // The first length code. 19 lengthCodesStart = 257 20 21 // The number of codegen codes. 22 codegenCodeCount = 19 23 badCode = 255 24 25 // bufferFlushSize indicates the buffer size 26 // after which bytes are flushed to the writer. 27 // Should preferably be a multiple of 6, since 28 // we accumulate 6 bytes between writes to the buffer. 29 bufferFlushSize = 240 30 31 // bufferSize is the actual output byte buffer size. 32 // It must have additional headroom for a flush 33 // which can contain up to 8 bytes. 34 bufferSize = bufferFlushSize + 8 35 ) 36 37 // The number of extra bits needed by length code X - LENGTH_CODES_START. 38 var lengthExtraBits = []int8{ 39 /* 257 */ 0, 0, 0, 40 /* 260 */ 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 41 /* 270 */ 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 42 /* 280 */ 4, 5, 5, 5, 5, 0, 43 } 44 45 // The length indicated by length code X - LENGTH_CODES_START. 46 var lengthBase = []uint32{ 47 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 48 12, 14, 16, 20, 24, 28, 32, 40, 48, 56, 49 64, 80, 96, 112, 128, 160, 192, 224, 255, 50 } 51 52 // offset code word extra bits. 53 var offsetExtraBits = []int8{ 54 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 55 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 56 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 57 /* extended window */ 58 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 59 } 60 61 var offsetBase = []uint32{ 62 /* normal deflate */ 63 0x000000, 0x000001, 0x000002, 0x000003, 0x000004, 64 0x000006, 0x000008, 0x00000c, 0x000010, 0x000018, 65 0x000020, 0x000030, 0x000040, 0x000060, 0x000080, 66 0x0000c0, 0x000100, 0x000180, 0x000200, 0x000300, 67 0x000400, 0x000600, 0x000800, 0x000c00, 0x001000, 68 0x001800, 0x002000, 0x003000, 0x004000, 0x006000, 69 70 /* extended window */ 71 0x008000, 0x00c000, 0x010000, 0x018000, 0x020000, 72 0x030000, 0x040000, 0x060000, 0x080000, 0x0c0000, 73 0x100000, 0x180000, 0x200000, 0x300000, 74 } 75 76 // The odd order in which the codegen code sizes are written. 77 var codegenOrder = []uint32{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15} 78 79 type huffmanBitWriter struct { 80 // writer is the underlying writer. 81 // Do not use it directly; use the write method, which ensures 82 // that Write errors are sticky. 83 writer io.Writer 84 85 // Data waiting to be written is bytes[0:nbytes] 86 // and then the low nbits of bits. 87 bits uint64 88 nbits uint 89 bytes [bufferSize]byte 90 codegenFreq [codegenCodeCount]int32 91 nbytes int 92 literalFreq []int32 93 offsetFreq []int32 94 codegen []uint8 95 literalEncoding *huffmanEncoder 96 offsetEncoding *huffmanEncoder 97 codegenEncoding *huffmanEncoder 98 err error 99 } 100 101 func newHuffmanBitWriter(w io.Writer) *huffmanBitWriter { 102 return &huffmanBitWriter{ 103 writer: w, 104 literalFreq: make([]int32, maxNumLit), 105 offsetFreq: make([]int32, offsetCodeCount), 106 codegen: make([]uint8, maxNumLit+offsetCodeCount+1), 107 literalEncoding: newHuffmanEncoder(maxNumLit), 108 codegenEncoding: newHuffmanEncoder(codegenCodeCount), 109 offsetEncoding: newHuffmanEncoder(offsetCodeCount), 110 } 111 } 112 113 func (w *huffmanBitWriter) reset(writer io.Writer) { 114 w.writer = writer 115 w.bits, w.nbits, w.nbytes, w.err = 0, 0, 0, nil 116 w.bytes = [bufferSize]byte{} 117 } 118 119 func (w *huffmanBitWriter) flush() { 120 if w.err != nil { 121 w.nbits = 0 122 return 123 } 124 n := w.nbytes 125 for w.nbits != 0 { 126 w.bytes[n] = byte(w.bits) 127 w.bits >>= 8 128 if w.nbits > 8 { // Avoid underflow 129 w.nbits -= 8 130 } else { 131 w.nbits = 0 132 } 133 n++ 134 } 135 w.bits = 0 136 w.write(w.bytes[:n]) 137 w.nbytes = 0 138 } 139 140 func (w *huffmanBitWriter) write(b []byte) { 141 if w.err != nil { 142 return 143 } 144 _, w.err = w.writer.Write(b) 145 } 146 147 func (w *huffmanBitWriter) writeBits(b int32, nb uint) { 148 if w.err != nil { 149 return 150 } 151 w.bits |= uint64(b) << w.nbits 152 w.nbits += nb 153 if w.nbits >= 48 { 154 bits := w.bits 155 w.bits >>= 48 156 w.nbits -= 48 157 n := w.nbytes 158 bytes := w.bytes[n : n+6] 159 bytes[0] = byte(bits) 160 bytes[1] = byte(bits >> 8) 161 bytes[2] = byte(bits >> 16) 162 bytes[3] = byte(bits >> 24) 163 bytes[4] = byte(bits >> 32) 164 bytes[5] = byte(bits >> 40) 165 n += 6 166 if n >= bufferFlushSize { 167 w.write(w.bytes[:n]) 168 n = 0 169 } 170 w.nbytes = n 171 } 172 } 173 174 func (w *huffmanBitWriter) writeBytes(bytes []byte) { 175 if w.err != nil { 176 return 177 } 178 n := w.nbytes 179 if w.nbits&7 != 0 { 180 w.err = InternalError("writeBytes with unfinished bits") 181 return 182 } 183 for w.nbits != 0 { 184 w.bytes[n] = byte(w.bits) 185 w.bits >>= 8 186 w.nbits -= 8 187 n++ 188 } 189 if n != 0 { 190 w.write(w.bytes[:n]) 191 } 192 w.nbytes = 0 193 w.write(bytes) 194 } 195 196 // RFC 1951 3.2.7 specifies a special run-length encoding for specifying 197 // the literal and offset lengths arrays (which are concatenated into a single 198 // array). This method generates that run-length encoding. 199 // 200 // The result is written into the codegen array, and the frequencies 201 // of each code is written into the codegenFreq array. 202 // Codes 0-15 are single byte codes. Codes 16-18 are followed by additional 203 // information. Code badCode is an end marker 204 // 205 // numLiterals The number of literals in literalEncoding 206 // numOffsets The number of offsets in offsetEncoding 207 // litenc, offenc The literal and offset encoder to use 208 func (w *huffmanBitWriter) generateCodegen(numLiterals int, numOffsets int, litEnc, offEnc *huffmanEncoder) { 209 for i := range w.codegenFreq { 210 w.codegenFreq[i] = 0 211 } 212 // Note that we are using codegen both as a temporary variable for holding 213 // a copy of the frequencies, and as the place where we put the result. 214 // This is fine because the output is always shorter than the input used 215 // so far. 216 codegen := w.codegen // cache 217 // Copy the concatenated code sizes to codegen. Put a marker at the end. 218 cgnl := codegen[:numLiterals] 219 for i := range cgnl { 220 cgnl[i] = uint8(litEnc.codes[i].len) 221 } 222 223 cgnl = codegen[numLiterals : numLiterals+numOffsets] 224 for i := range cgnl { 225 cgnl[i] = uint8(offEnc.codes[i].len) 226 } 227 codegen[numLiterals+numOffsets] = badCode 228 229 size := codegen[0] 230 count := 1 231 outIndex := 0 232 for inIndex := 1; size != badCode; inIndex++ { 233 // INVARIANT: We have seen "count" copies of size that have not yet 234 // had output generated for them. 235 nextSize := codegen[inIndex] 236 if nextSize == size { 237 count++ 238 continue 239 } 240 // We need to generate codegen indicating "count" of size. 241 if size != 0 { 242 codegen[outIndex] = size 243 outIndex++ 244 w.codegenFreq[size]++ 245 count-- 246 for count >= 3 { 247 n := 6 248 if n > count { 249 n = count 250 } 251 codegen[outIndex] = 16 252 outIndex++ 253 codegen[outIndex] = uint8(n - 3) 254 outIndex++ 255 w.codegenFreq[16]++ 256 count -= n 257 } 258 } else { 259 for count >= 11 { 260 n := 138 261 if n > count { 262 n = count 263 } 264 codegen[outIndex] = 18 265 outIndex++ 266 codegen[outIndex] = uint8(n - 11) 267 outIndex++ 268 w.codegenFreq[18]++ 269 count -= n 270 } 271 if count >= 3 { 272 // count >= 3 && count <= 10 273 codegen[outIndex] = 17 274 outIndex++ 275 codegen[outIndex] = uint8(count - 3) 276 outIndex++ 277 w.codegenFreq[17]++ 278 count = 0 279 } 280 } 281 count-- 282 for ; count >= 0; count-- { 283 codegen[outIndex] = size 284 outIndex++ 285 w.codegenFreq[size]++ 286 } 287 // Set up invariant for next time through the loop. 288 size = nextSize 289 count = 1 290 } 291 // Marker indicating the end of the codegen. 292 codegen[outIndex] = badCode 293 } 294 295 // dynamicSize returns the size of dynamically encoded data in bits. 296 func (w *huffmanBitWriter) dynamicSize(litEnc, offEnc *huffmanEncoder, extraBits int) (size, numCodegens int) { 297 numCodegens = len(w.codegenFreq) 298 for numCodegens > 4 && w.codegenFreq[codegenOrder[numCodegens-1]] == 0 { 299 numCodegens-- 300 } 301 header := 3 + 5 + 5 + 4 + (3 * numCodegens) + 302 w.codegenEncoding.bitLength(w.codegenFreq[:]) + 303 int(w.codegenFreq[16])*2 + 304 int(w.codegenFreq[17])*3 + 305 int(w.codegenFreq[18])*7 306 size = header + 307 litEnc.bitLength(w.literalFreq) + 308 offEnc.bitLength(w.offsetFreq) + 309 extraBits 310 311 return size, numCodegens 312 } 313 314 // fixedSize returns the size of dynamically encoded data in bits. 315 func (w *huffmanBitWriter) fixedSize(extraBits int) int { 316 return 3 + 317 fixedLiteralEncoding.bitLength(w.literalFreq) + 318 fixedOffsetEncoding.bitLength(w.offsetFreq) + 319 extraBits 320 } 321 322 // storedSize calculates the stored size, including header. 323 // The function returns the size in bits and whether the block 324 // fits inside a single block. 325 func (w *huffmanBitWriter) storedSize(in []byte) (int, bool) { 326 if in == nil { 327 return 0, false 328 } 329 if len(in) <= maxStoreBlockSize { 330 return (len(in) + 5) * 8, true 331 } 332 return 0, false 333 } 334 335 func (w *huffmanBitWriter) writeCode(c hcode) { 336 if w.err != nil { 337 return 338 } 339 w.bits |= uint64(c.code) << w.nbits 340 w.nbits += uint(c.len) 341 if w.nbits >= 48 { 342 bits := w.bits 343 w.bits >>= 48 344 w.nbits -= 48 345 n := w.nbytes 346 bytes := w.bytes[n : n+6] 347 bytes[0] = byte(bits) 348 bytes[1] = byte(bits >> 8) 349 bytes[2] = byte(bits >> 16) 350 bytes[3] = byte(bits >> 24) 351 bytes[4] = byte(bits >> 32) 352 bytes[5] = byte(bits >> 40) 353 n += 6 354 if n >= bufferFlushSize { 355 w.write(w.bytes[:n]) 356 n = 0 357 } 358 w.nbytes = n 359 } 360 } 361 362 // Write the header of a dynamic Huffman block to the output stream. 363 // 364 // numLiterals The number of literals specified in codegen 365 // numOffsets The number of offsets specified in codegen 366 // numCodegens The number of codegens used in codegen 367 func (w *huffmanBitWriter) writeDynamicHeader(numLiterals int, numOffsets int, numCodegens int, isEof bool) { 368 if w.err != nil { 369 return 370 } 371 var firstBits int32 = 4 372 if isEof { 373 firstBits = 5 374 } 375 w.writeBits(firstBits, 3) 376 w.writeBits(int32(numLiterals-257), 5) 377 w.writeBits(int32(numOffsets-1), 5) 378 w.writeBits(int32(numCodegens-4), 4) 379 380 for i := 0; i < numCodegens; i++ { 381 value := uint(w.codegenEncoding.codes[codegenOrder[i]].len) 382 w.writeBits(int32(value), 3) 383 } 384 385 i := 0 386 for { 387 var codeWord int = int(w.codegen[i]) 388 i++ 389 if codeWord == badCode { 390 break 391 } 392 w.writeCode(w.codegenEncoding.codes[uint32(codeWord)]) 393 394 switch codeWord { 395 case 16: 396 w.writeBits(int32(w.codegen[i]), 2) 397 i++ 398 break 399 case 17: 400 w.writeBits(int32(w.codegen[i]), 3) 401 i++ 402 break 403 case 18: 404 w.writeBits(int32(w.codegen[i]), 7) 405 i++ 406 break 407 } 408 } 409 } 410 411 func (w *huffmanBitWriter) writeStoredHeader(length int, isEof bool) { 412 if w.err != nil { 413 return 414 } 415 var flag int32 416 if isEof { 417 flag = 1 418 } 419 w.writeBits(flag, 3) 420 w.flush() 421 w.writeBits(int32(length), 16) 422 w.writeBits(int32(^uint16(length)), 16) 423 } 424 425 func (w *huffmanBitWriter) writeFixedHeader(isEof bool) { 426 if w.err != nil { 427 return 428 } 429 // Indicate that we are a fixed Huffman block 430 var value int32 = 2 431 if isEof { 432 value = 3 433 } 434 w.writeBits(value, 3) 435 } 436 437 // writeBlock will write a block of tokens with the smallest encoding. 438 // The original input can be supplied, and if the huffman encoded data 439 // is larger than the original bytes, the data will be written as a 440 // stored block. 441 // If the input is nil, the tokens will always be Huffman encoded. 442 func (w *huffmanBitWriter) writeBlock(tokens []token, eof bool, input []byte) { 443 if w.err != nil { 444 return 445 } 446 447 tokens = append(tokens, endBlockMarker) 448 numLiterals, numOffsets := w.indexTokens(tokens) 449 450 var extraBits int 451 storedSize, storable := w.storedSize(input) 452 if storable { 453 // We only bother calculating the costs of the extra bits required by 454 // the length of offset fields (which will be the same for both fixed 455 // and dynamic encoding), if we need to compare those two encodings 456 // against stored encoding. 457 for lengthCode := lengthCodesStart + 8; lengthCode < numLiterals; lengthCode++ { 458 // First eight length codes have extra size = 0. 459 extraBits += int(w.literalFreq[lengthCode]) * int(lengthExtraBits[lengthCode-lengthCodesStart]) 460 } 461 for offsetCode := 4; offsetCode < numOffsets; offsetCode++ { 462 // First four offset codes have extra size = 0. 463 extraBits += int(w.offsetFreq[offsetCode]) * int(offsetExtraBits[offsetCode]) 464 } 465 } 466 467 // Figure out smallest code. 468 // Fixed Huffman baseline. 469 var literalEncoding = fixedLiteralEncoding 470 var offsetEncoding = fixedOffsetEncoding 471 var size = w.fixedSize(extraBits) 472 473 // Dynamic Huffman? 474 var numCodegens int 475 476 // Generate codegen and codegenFrequencies, which indicates how to encode 477 // the literalEncoding and the offsetEncoding. 478 w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding) 479 w.codegenEncoding.generate(w.codegenFreq[:], 7) 480 dynamicSize, numCodegens := w.dynamicSize(w.literalEncoding, w.offsetEncoding, extraBits) 481 482 if dynamicSize < size { 483 size = dynamicSize 484 literalEncoding = w.literalEncoding 485 offsetEncoding = w.offsetEncoding 486 } 487 488 // Stored bytes? 489 if storable && storedSize < size { 490 w.writeStoredHeader(len(input), eof) 491 w.writeBytes(input) 492 return 493 } 494 495 // Huffman. 496 if literalEncoding == fixedLiteralEncoding { 497 w.writeFixedHeader(eof) 498 } else { 499 w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof) 500 } 501 502 // Write the tokens. 503 w.writeTokens(tokens, literalEncoding.codes, offsetEncoding.codes) 504 } 505 506 // writeBlockDynamic encodes a block using a dynamic Huffman table. 507 // This should be used if the symbols used have a disproportionate 508 // histogram distribution. 509 // If input is supplied and the compression savings are below 1/16th of the 510 // input size the block is stored. 511 func (w *huffmanBitWriter) writeBlockDynamic(tokens []token, eof bool, input []byte) { 512 if w.err != nil { 513 return 514 } 515 516 tokens = append(tokens, endBlockMarker) 517 numLiterals, numOffsets := w.indexTokens(tokens) 518 519 // Generate codegen and codegenFrequencies, which indicates how to encode 520 // the literalEncoding and the offsetEncoding. 521 w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding) 522 w.codegenEncoding.generate(w.codegenFreq[:], 7) 523 size, numCodegens := w.dynamicSize(w.literalEncoding, w.offsetEncoding, 0) 524 525 // Store bytes, if we don't get a reasonable improvement. 526 if ssize, storable := w.storedSize(input); storable && ssize < (size+size>>4) { 527 w.writeStoredHeader(len(input), eof) 528 w.writeBytes(input) 529 return 530 } 531 532 // Write Huffman table. 533 w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof) 534 535 // Write the tokens. 536 w.writeTokens(tokens, w.literalEncoding.codes, w.offsetEncoding.codes) 537 } 538 539 // indexTokens indexes a slice of tokens, and updates 540 // literalFreq and offsetFreq, and generates literalEncoding 541 // and offsetEncoding. 542 // The number of literal and offset tokens is returned. 543 func (w *huffmanBitWriter) indexTokens(tokens []token) (numLiterals, numOffsets int) { 544 for i := range w.literalFreq { 545 w.literalFreq[i] = 0 546 } 547 for i := range w.offsetFreq { 548 w.offsetFreq[i] = 0 549 } 550 551 for _, t := range tokens { 552 if t < matchType { 553 w.literalFreq[t.literal()]++ 554 continue 555 } 556 length := t.length() 557 offset := t.offset() 558 w.literalFreq[lengthCodesStart+lengthCode(length)]++ 559 w.offsetFreq[offsetCode(offset)]++ 560 } 561 562 // get the number of literals 563 numLiterals = len(w.literalFreq) 564 for w.literalFreq[numLiterals-1] == 0 { 565 numLiterals-- 566 } 567 // get the number of offsets 568 numOffsets = len(w.offsetFreq) 569 for numOffsets > 0 && w.offsetFreq[numOffsets-1] == 0 { 570 numOffsets-- 571 } 572 if numOffsets == 0 { 573 // We haven't found a single match. If we want to go with the dynamic encoding, 574 // we should count at least one offset to be sure that the offset huffman tree could be encoded. 575 w.offsetFreq[0] = 1 576 numOffsets = 1 577 } 578 w.literalEncoding.generate(w.literalFreq, 15) 579 w.offsetEncoding.generate(w.offsetFreq, 15) 580 return 581 } 582 583 // writeTokens writes a slice of tokens to the output. 584 // codes for literal and offset encoding must be supplied. 585 func (w *huffmanBitWriter) writeTokens(tokens []token, leCodes, oeCodes []hcode) { 586 if w.err != nil { 587 return 588 } 589 for _, t := range tokens { 590 if t < matchType { 591 w.writeCode(leCodes[t.literal()]) 592 continue 593 } 594 // Write the length 595 length := t.length() 596 lengthCode := lengthCode(length) 597 w.writeCode(leCodes[lengthCode+lengthCodesStart]) 598 extraLengthBits := uint(lengthExtraBits[lengthCode]) 599 if extraLengthBits > 0 { 600 extraLength := int32(length - lengthBase[lengthCode]) 601 w.writeBits(extraLength, extraLengthBits) 602 } 603 // Write the offset 604 offset := t.offset() 605 offsetCode := offsetCode(offset) 606 w.writeCode(oeCodes[offsetCode]) 607 extraOffsetBits := uint(offsetExtraBits[offsetCode]) 608 if extraOffsetBits > 0 { 609 extraOffset := int32(offset - offsetBase[offsetCode]) 610 w.writeBits(extraOffset, extraOffsetBits) 611 } 612 } 613 } 614 615 // huffOffset is a static offset encoder used for huffman only encoding. 616 // It can be reused since we will not be encoding offset values. 617 var huffOffset *huffmanEncoder 618 619 func init() { 620 w := newHuffmanBitWriter(nil) 621 w.offsetFreq[0] = 1 622 huffOffset = newHuffmanEncoder(offsetCodeCount) 623 huffOffset.generate(w.offsetFreq, 15) 624 } 625 626 // writeBlockHuff encodes a block of bytes as either 627 // Huffman encoded literals or uncompressed bytes if the 628 // results only gains very little from compression. 629 func (w *huffmanBitWriter) writeBlockHuff(eof bool, input []byte) { 630 if w.err != nil { 631 return 632 } 633 634 // Clear histogram 635 for i := range w.literalFreq { 636 w.literalFreq[i] = 0 637 } 638 639 // Add everything as literals 640 histogram(input, w.literalFreq) 641 642 w.literalFreq[endBlockMarker] = 1 643 644 const numLiterals = endBlockMarker + 1 645 const numOffsets = 1 646 647 w.literalEncoding.generate(w.literalFreq, 15) 648 649 // Figure out smallest code. 650 // Always use dynamic Huffman or Store 651 var numCodegens int 652 653 // Generate codegen and codegenFrequencies, which indicates how to encode 654 // the literalEncoding and the offsetEncoding. 655 w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, huffOffset) 656 w.codegenEncoding.generate(w.codegenFreq[:], 7) 657 size, numCodegens := w.dynamicSize(w.literalEncoding, huffOffset, 0) 658 659 // Store bytes, if we don't get a reasonable improvement. 660 if ssize, storable := w.storedSize(input); storable && ssize < (size+size>>4) { 661 w.writeStoredHeader(len(input), eof) 662 w.writeBytes(input) 663 return 664 } 665 666 // Huffman. 667 w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof) 668 encoding := w.literalEncoding.codes[:257] 669 n := w.nbytes 670 for _, t := range input { 671 // Bitwriting inlined, ~30% speedup 672 c := encoding[t] 673 w.bits |= uint64(c.code) << w.nbits 674 w.nbits += uint(c.len) 675 if w.nbits < 48 { 676 continue 677 } 678 // Store 6 bytes 679 bits := w.bits 680 w.bits >>= 48 681 w.nbits -= 48 682 bytes := w.bytes[n : n+6] 683 bytes[0] = byte(bits) 684 bytes[1] = byte(bits >> 8) 685 bytes[2] = byte(bits >> 16) 686 bytes[3] = byte(bits >> 24) 687 bytes[4] = byte(bits >> 32) 688 bytes[5] = byte(bits >> 40) 689 n += 6 690 if n < bufferFlushSize { 691 continue 692 } 693 w.write(w.bytes[:n]) 694 if w.err != nil { 695 return // Return early in the event of write failures 696 } 697 n = 0 698 } 699 w.nbytes = n 700 w.writeCode(encoding[endBlockMarker]) 701 } 702 703 // histogram accumulates a histogram of b in h. 704 // 705 // len(h) must be >= 256, and h's elements must be all zeroes. 706 func histogram(b []byte, h []int32) { 707 h = h[:256] 708 for _, t := range b { 709 h[t]++ 710 } 711 } 712