1// Copyright 2019+ Klaus Post. All rights reserved. 2// License information can be found in the LICENSE file. 3// Based on work by Yann Collet, released under BSD License. 4 5package zstd 6 7import ( 8 "errors" 9 "fmt" 10 "math" 11 "math/bits" 12 13 "github.com/klauspost/compress/huff0" 14) 15 16type blockEnc struct { 17 size int 18 literals []byte 19 sequences []seq 20 coders seqCoders 21 litEnc *huff0.Scratch 22 dictLitEnc *huff0.Scratch 23 wr bitWriter 24 25 extraLits int 26 last bool 27 28 output []byte 29 recentOffsets [3]uint32 30 prevRecentOffsets [3]uint32 31} 32 33// init should be used once the block has been created. 34// If called more than once, the effect is the same as calling reset. 35func (b *blockEnc) init() { 36 if cap(b.literals) < maxCompressedLiteralSize { 37 b.literals = make([]byte, 0, maxCompressedLiteralSize) 38 } 39 const defSeqs = 200 40 b.literals = b.literals[:0] 41 if cap(b.sequences) < defSeqs { 42 b.sequences = make([]seq, 0, defSeqs) 43 } 44 if cap(b.output) < maxCompressedBlockSize { 45 b.output = make([]byte, 0, maxCompressedBlockSize) 46 } 47 if b.coders.mlEnc == nil { 48 b.coders.mlEnc = &fseEncoder{} 49 b.coders.mlPrev = &fseEncoder{} 50 b.coders.ofEnc = &fseEncoder{} 51 b.coders.ofPrev = &fseEncoder{} 52 b.coders.llEnc = &fseEncoder{} 53 b.coders.llPrev = &fseEncoder{} 54 } 55 b.litEnc = &huff0.Scratch{WantLogLess: 4} 56 b.reset(nil) 57} 58 59// initNewEncode can be used to reset offsets and encoders to the initial state. 60func (b *blockEnc) initNewEncode() { 61 b.recentOffsets = [3]uint32{1, 4, 8} 62 b.litEnc.Reuse = huff0.ReusePolicyNone 63 b.coders.setPrev(nil, nil, nil) 64} 65 66// reset will reset the block for a new encode, but in the same stream, 67// meaning that state will be carried over, but the block content is reset. 68// If a previous block is provided, the recent offsets are carried over. 69func (b *blockEnc) reset(prev *blockEnc) { 70 b.extraLits = 0 71 b.literals = b.literals[:0] 72 b.size = 0 73 b.sequences = b.sequences[:0] 74 b.output = b.output[:0] 75 b.last = false 76 if prev != nil { 77 b.recentOffsets = prev.prevRecentOffsets 78 } 79 b.dictLitEnc = nil 80} 81 82// reset will reset the block for a new encode, but in the same stream, 83// meaning that state will be carried over, but the block content is reset. 84// If a previous block is provided, the recent offsets are carried over. 85func (b *blockEnc) swapEncoders(prev *blockEnc) { 86 b.coders.swap(&prev.coders) 87 b.litEnc, prev.litEnc = prev.litEnc, b.litEnc 88} 89 90// blockHeader contains the information for a block header. 91type blockHeader uint32 92 93// setLast sets the 'last' indicator on a block. 94func (h *blockHeader) setLast(b bool) { 95 if b { 96 *h = *h | 1 97 } else { 98 const mask = (1 << 24) - 2 99 *h = *h & mask 100 } 101} 102 103// setSize will store the compressed size of a block. 104func (h *blockHeader) setSize(v uint32) { 105 const mask = 7 106 *h = (*h)&mask | blockHeader(v<<3) 107} 108 109// setType sets the block type. 110func (h *blockHeader) setType(t blockType) { 111 const mask = 1 | (((1 << 24) - 1) ^ 7) 112 *h = (*h & mask) | blockHeader(t<<1) 113} 114 115// appendTo will append the block header to a slice. 116func (h blockHeader) appendTo(b []byte) []byte { 117 return append(b, uint8(h), uint8(h>>8), uint8(h>>16)) 118} 119 120// String returns a string representation of the block. 121func (h blockHeader) String() string { 122 return fmt.Sprintf("Type: %d, Size: %d, Last:%t", (h>>1)&3, h>>3, h&1 == 1) 123} 124 125// literalsHeader contains literals header information. 126type literalsHeader uint64 127 128// setType can be used to set the type of literal block. 129func (h *literalsHeader) setType(t literalsBlockType) { 130 const mask = math.MaxUint64 - 3 131 *h = (*h & mask) | literalsHeader(t) 132} 133 134// setSize can be used to set a single size, for uncompressed and RLE content. 135func (h *literalsHeader) setSize(regenLen int) { 136 inBits := bits.Len32(uint32(regenLen)) 137 // Only retain 2 bits 138 const mask = 3 139 lh := uint64(*h & mask) 140 switch { 141 case inBits < 5: 142 lh |= (uint64(regenLen) << 3) | (1 << 60) 143 if debug { 144 got := int(lh>>3) & 0xff 145 if got != regenLen { 146 panic(fmt.Sprint("litRegenSize = ", regenLen, "(want) != ", got, "(got)")) 147 } 148 } 149 case inBits < 12: 150 lh |= (1 << 2) | (uint64(regenLen) << 4) | (2 << 60) 151 case inBits < 20: 152 lh |= (3 << 2) | (uint64(regenLen) << 4) | (3 << 60) 153 default: 154 panic(fmt.Errorf("internal error: block too big (%d)", regenLen)) 155 } 156 *h = literalsHeader(lh) 157} 158 159// setSizes will set the size of a compressed literals section and the input length. 160func (h *literalsHeader) setSizes(compLen, inLen int, single bool) { 161 compBits, inBits := bits.Len32(uint32(compLen)), bits.Len32(uint32(inLen)) 162 // Only retain 2 bits 163 const mask = 3 164 lh := uint64(*h & mask) 165 switch { 166 case compBits <= 10 && inBits <= 10: 167 if !single { 168 lh |= 1 << 2 169 } 170 lh |= (uint64(inLen) << 4) | (uint64(compLen) << (10 + 4)) | (3 << 60) 171 if debug { 172 const mmask = (1 << 24) - 1 173 n := (lh >> 4) & mmask 174 if int(n&1023) != inLen { 175 panic(fmt.Sprint("regensize:", int(n&1023), "!=", inLen, inBits)) 176 } 177 if int(n>>10) != compLen { 178 panic(fmt.Sprint("compsize:", int(n>>10), "!=", compLen, compBits)) 179 } 180 } 181 case compBits <= 14 && inBits <= 14: 182 lh |= (2 << 2) | (uint64(inLen) << 4) | (uint64(compLen) << (14 + 4)) | (4 << 60) 183 if single { 184 panic("single stream used with more than 10 bits length.") 185 } 186 case compBits <= 18 && inBits <= 18: 187 lh |= (3 << 2) | (uint64(inLen) << 4) | (uint64(compLen) << (18 + 4)) | (5 << 60) 188 if single { 189 panic("single stream used with more than 10 bits length.") 190 } 191 default: 192 panic("internal error: block too big") 193 } 194 *h = literalsHeader(lh) 195} 196 197// appendTo will append the literals header to a byte slice. 198func (h literalsHeader) appendTo(b []byte) []byte { 199 size := uint8(h >> 60) 200 switch size { 201 case 1: 202 b = append(b, uint8(h)) 203 case 2: 204 b = append(b, uint8(h), uint8(h>>8)) 205 case 3: 206 b = append(b, uint8(h), uint8(h>>8), uint8(h>>16)) 207 case 4: 208 b = append(b, uint8(h), uint8(h>>8), uint8(h>>16), uint8(h>>24)) 209 case 5: 210 b = append(b, uint8(h), uint8(h>>8), uint8(h>>16), uint8(h>>24), uint8(h>>32)) 211 default: 212 panic(fmt.Errorf("internal error: literalsHeader has invalid size (%d)", size)) 213 } 214 return b 215} 216 217// size returns the output size with currently set values. 218func (h literalsHeader) size() int { 219 return int(h >> 60) 220} 221 222func (h literalsHeader) String() string { 223 return fmt.Sprintf("Type: %d, SizeFormat: %d, Size: 0x%d, Bytes:%d", literalsBlockType(h&3), (h>>2)&3, h&((1<<60)-1)>>4, h>>60) 224} 225 226// pushOffsets will push the recent offsets to the backup store. 227func (b *blockEnc) pushOffsets() { 228 b.prevRecentOffsets = b.recentOffsets 229} 230 231// pushOffsets will push the recent offsets to the backup store. 232func (b *blockEnc) popOffsets() { 233 b.recentOffsets = b.prevRecentOffsets 234} 235 236// matchOffset will adjust recent offsets and return the adjusted one, 237// if it matches a previous offset. 238func (b *blockEnc) matchOffset(offset, lits uint32) uint32 { 239 // Check if offset is one of the recent offsets. 240 // Adjusts the output offset accordingly. 241 // Gives a tiny bit of compression, typically around 1%. 242 if true { 243 if lits > 0 { 244 switch offset { 245 case b.recentOffsets[0]: 246 offset = 1 247 case b.recentOffsets[1]: 248 b.recentOffsets[1] = b.recentOffsets[0] 249 b.recentOffsets[0] = offset 250 offset = 2 251 case b.recentOffsets[2]: 252 b.recentOffsets[2] = b.recentOffsets[1] 253 b.recentOffsets[1] = b.recentOffsets[0] 254 b.recentOffsets[0] = offset 255 offset = 3 256 default: 257 b.recentOffsets[2] = b.recentOffsets[1] 258 b.recentOffsets[1] = b.recentOffsets[0] 259 b.recentOffsets[0] = offset 260 offset += 3 261 } 262 } else { 263 switch offset { 264 case b.recentOffsets[1]: 265 b.recentOffsets[1] = b.recentOffsets[0] 266 b.recentOffsets[0] = offset 267 offset = 1 268 case b.recentOffsets[2]: 269 b.recentOffsets[2] = b.recentOffsets[1] 270 b.recentOffsets[1] = b.recentOffsets[0] 271 b.recentOffsets[0] = offset 272 offset = 2 273 case b.recentOffsets[0] - 1: 274 b.recentOffsets[2] = b.recentOffsets[1] 275 b.recentOffsets[1] = b.recentOffsets[0] 276 b.recentOffsets[0] = offset 277 offset = 3 278 default: 279 b.recentOffsets[2] = b.recentOffsets[1] 280 b.recentOffsets[1] = b.recentOffsets[0] 281 b.recentOffsets[0] = offset 282 offset += 3 283 } 284 } 285 } else { 286 offset += 3 287 } 288 return offset 289} 290 291// encodeRaw can be used to set the output to a raw representation of supplied bytes. 292func (b *blockEnc) encodeRaw(a []byte) { 293 var bh blockHeader 294 bh.setLast(b.last) 295 bh.setSize(uint32(len(a))) 296 bh.setType(blockTypeRaw) 297 b.output = bh.appendTo(b.output[:0]) 298 b.output = append(b.output, a...) 299 if debug { 300 println("Adding RAW block, length", len(a), "last:", b.last) 301 } 302} 303 304// encodeRaw can be used to set the output to a raw representation of supplied bytes. 305func (b *blockEnc) encodeRawTo(dst, src []byte) []byte { 306 var bh blockHeader 307 bh.setLast(b.last) 308 bh.setSize(uint32(len(src))) 309 bh.setType(blockTypeRaw) 310 dst = bh.appendTo(dst) 311 dst = append(dst, src...) 312 if debug { 313 println("Adding RAW block, length", len(src), "last:", b.last) 314 } 315 return dst 316} 317 318// encodeLits can be used if the block is only litLen. 319func (b *blockEnc) encodeLits(lits []byte, raw bool) error { 320 var bh blockHeader 321 bh.setLast(b.last) 322 bh.setSize(uint32(len(lits))) 323 324 // Don't compress extremely small blocks 325 if len(lits) < 8 || (len(lits) < 32 && b.dictLitEnc == nil) || raw { 326 if debug { 327 println("Adding RAW block, length", len(lits), "last:", b.last) 328 } 329 bh.setType(blockTypeRaw) 330 b.output = bh.appendTo(b.output) 331 b.output = append(b.output, lits...) 332 return nil 333 } 334 335 var ( 336 out []byte 337 reUsed, single bool 338 err error 339 ) 340 if b.dictLitEnc != nil { 341 b.litEnc.TransferCTable(b.dictLitEnc) 342 b.litEnc.Reuse = huff0.ReusePolicyAllow 343 b.dictLitEnc = nil 344 } 345 if len(lits) >= 1024 { 346 // Use 4 Streams. 347 out, reUsed, err = huff0.Compress4X(lits, b.litEnc) 348 } else if len(lits) > 32 { 349 // Use 1 stream 350 single = true 351 out, reUsed, err = huff0.Compress1X(lits, b.litEnc) 352 } else { 353 err = huff0.ErrIncompressible 354 } 355 356 switch err { 357 case huff0.ErrIncompressible: 358 if debug { 359 println("Adding RAW block, length", len(lits), "last:", b.last) 360 } 361 bh.setType(blockTypeRaw) 362 b.output = bh.appendTo(b.output) 363 b.output = append(b.output, lits...) 364 return nil 365 case huff0.ErrUseRLE: 366 if debug { 367 println("Adding RLE block, length", len(lits)) 368 } 369 bh.setType(blockTypeRLE) 370 b.output = bh.appendTo(b.output) 371 b.output = append(b.output, lits[0]) 372 return nil 373 default: 374 return err 375 case nil: 376 } 377 // Compressed... 378 // Now, allow reuse 379 b.litEnc.Reuse = huff0.ReusePolicyAllow 380 bh.setType(blockTypeCompressed) 381 var lh literalsHeader 382 if reUsed { 383 if debug { 384 println("Reused tree, compressed to", len(out)) 385 } 386 lh.setType(literalsBlockTreeless) 387 } else { 388 if debug { 389 println("New tree, compressed to", len(out), "tree size:", len(b.litEnc.OutTable)) 390 } 391 lh.setType(literalsBlockCompressed) 392 } 393 // Set sizes 394 lh.setSizes(len(out), len(lits), single) 395 bh.setSize(uint32(len(out) + lh.size() + 1)) 396 397 // Write block headers. 398 b.output = bh.appendTo(b.output) 399 b.output = lh.appendTo(b.output) 400 // Add compressed data. 401 b.output = append(b.output, out...) 402 // No sequences. 403 b.output = append(b.output, 0) 404 return nil 405} 406 407// fuzzFseEncoder can be used to fuzz the FSE encoder. 408func fuzzFseEncoder(data []byte) int { 409 if len(data) > maxSequences || len(data) < 2 { 410 return 0 411 } 412 enc := fseEncoder{} 413 hist := enc.Histogram()[:256] 414 maxSym := uint8(0) 415 for i, v := range data { 416 v = v & 63 417 data[i] = v 418 hist[v]++ 419 if v > maxSym { 420 maxSym = v 421 } 422 } 423 if maxSym == 0 { 424 // All 0 425 return 0 426 } 427 maxCount := func(a []uint32) int { 428 var max uint32 429 for _, v := range a { 430 if v > max { 431 max = v 432 } 433 } 434 return int(max) 435 } 436 cnt := maxCount(hist[:maxSym]) 437 if cnt == len(data) { 438 // RLE 439 return 0 440 } 441 enc.HistogramFinished(maxSym, cnt) 442 err := enc.normalizeCount(len(data)) 443 if err != nil { 444 return 0 445 } 446 _, err = enc.writeCount(nil) 447 if err != nil { 448 panic(err) 449 } 450 return 1 451} 452 453// encode will encode the block and append the output in b.output. 454// Previous offset codes must be pushed if more blocks are expected. 455func (b *blockEnc) encode(org []byte, raw, rawAllLits bool) error { 456 if len(b.sequences) == 0 { 457 return b.encodeLits(b.literals, rawAllLits) 458 } 459 // We want some difference to at least account for the headers. 460 saved := b.size - len(b.literals) - (b.size >> 5) 461 if saved < 16 { 462 if org == nil { 463 return errIncompressible 464 } 465 b.popOffsets() 466 return b.encodeLits(org, rawAllLits) 467 } 468 469 var bh blockHeader 470 var lh literalsHeader 471 bh.setLast(b.last) 472 bh.setType(blockTypeCompressed) 473 // Store offset of the block header. Needed when we know the size. 474 bhOffset := len(b.output) 475 b.output = bh.appendTo(b.output) 476 477 var ( 478 out []byte 479 reUsed, single bool 480 err error 481 ) 482 if b.dictLitEnc != nil { 483 b.litEnc.TransferCTable(b.dictLitEnc) 484 b.litEnc.Reuse = huff0.ReusePolicyAllow 485 b.dictLitEnc = nil 486 } 487 if len(b.literals) >= 1024 && !raw { 488 // Use 4 Streams. 489 out, reUsed, err = huff0.Compress4X(b.literals, b.litEnc) 490 } else if len(b.literals) > 32 && !raw { 491 // Use 1 stream 492 single = true 493 out, reUsed, err = huff0.Compress1X(b.literals, b.litEnc) 494 } else { 495 err = huff0.ErrIncompressible 496 } 497 498 switch err { 499 case huff0.ErrIncompressible: 500 lh.setType(literalsBlockRaw) 501 lh.setSize(len(b.literals)) 502 b.output = lh.appendTo(b.output) 503 b.output = append(b.output, b.literals...) 504 if debug { 505 println("Adding literals RAW, length", len(b.literals)) 506 } 507 case huff0.ErrUseRLE: 508 lh.setType(literalsBlockRLE) 509 lh.setSize(len(b.literals)) 510 b.output = lh.appendTo(b.output) 511 b.output = append(b.output, b.literals[0]) 512 if debug { 513 println("Adding literals RLE") 514 } 515 default: 516 if debug { 517 println("Adding literals ERROR:", err) 518 } 519 return err 520 case nil: 521 // Compressed litLen... 522 if reUsed { 523 if debug { 524 println("reused tree") 525 } 526 lh.setType(literalsBlockTreeless) 527 } else { 528 if debug { 529 println("new tree, size:", len(b.litEnc.OutTable)) 530 } 531 lh.setType(literalsBlockCompressed) 532 if debug { 533 _, _, err := huff0.ReadTable(out, nil) 534 if err != nil { 535 panic(err) 536 } 537 } 538 } 539 lh.setSizes(len(out), len(b.literals), single) 540 if debug { 541 printf("Compressed %d literals to %d bytes", len(b.literals), len(out)) 542 println("Adding literal header:", lh) 543 } 544 b.output = lh.appendTo(b.output) 545 b.output = append(b.output, out...) 546 b.litEnc.Reuse = huff0.ReusePolicyAllow 547 if debug { 548 println("Adding literals compressed") 549 } 550 } 551 // Sequence compression 552 553 // Write the number of sequences 554 switch { 555 case len(b.sequences) < 128: 556 b.output = append(b.output, uint8(len(b.sequences))) 557 case len(b.sequences) < 0x7f00: // TODO: this could be wrong 558 n := len(b.sequences) 559 b.output = append(b.output, 128+uint8(n>>8), uint8(n)) 560 default: 561 n := len(b.sequences) - 0x7f00 562 b.output = append(b.output, 255, uint8(n), uint8(n>>8)) 563 } 564 if debug { 565 println("Encoding", len(b.sequences), "sequences") 566 } 567 b.genCodes() 568 llEnc := b.coders.llEnc 569 ofEnc := b.coders.ofEnc 570 mlEnc := b.coders.mlEnc 571 err = llEnc.normalizeCount(len(b.sequences)) 572 if err != nil { 573 return err 574 } 575 err = ofEnc.normalizeCount(len(b.sequences)) 576 if err != nil { 577 return err 578 } 579 err = mlEnc.normalizeCount(len(b.sequences)) 580 if err != nil { 581 return err 582 } 583 584 // Choose the best compression mode for each type. 585 // Will evaluate the new vs predefined and previous. 586 chooseComp := func(cur, prev, preDef *fseEncoder) (*fseEncoder, seqCompMode) { 587 // See if predefined/previous is better 588 hist := cur.count[:cur.symbolLen] 589 nSize := cur.approxSize(hist) + cur.maxHeaderSize() 590 predefSize := preDef.approxSize(hist) 591 prevSize := prev.approxSize(hist) 592 593 // Add a small penalty for new encoders. 594 // Don't bother with extremely small (<2 byte gains). 595 nSize = nSize + (nSize+2*8*16)>>4 596 switch { 597 case predefSize <= prevSize && predefSize <= nSize || forcePreDef: 598 if debug { 599 println("Using predefined", predefSize>>3, "<=", nSize>>3) 600 } 601 return preDef, compModePredefined 602 case prevSize <= nSize: 603 if debug { 604 println("Using previous", prevSize>>3, "<=", nSize>>3) 605 } 606 return prev, compModeRepeat 607 default: 608 if debug { 609 println("Using new, predef", predefSize>>3, ". previous:", prevSize>>3, ">", nSize>>3, "header max:", cur.maxHeaderSize()>>3, "bytes") 610 println("tl:", cur.actualTableLog, "symbolLen:", cur.symbolLen, "norm:", cur.norm[:cur.symbolLen], "hist", cur.count[:cur.symbolLen]) 611 } 612 return cur, compModeFSE 613 } 614 } 615 616 // Write compression mode 617 var mode uint8 618 if llEnc.useRLE { 619 mode |= uint8(compModeRLE) << 6 620 llEnc.setRLE(b.sequences[0].llCode) 621 if debug { 622 println("llEnc.useRLE") 623 } 624 } else { 625 var m seqCompMode 626 llEnc, m = chooseComp(llEnc, b.coders.llPrev, &fsePredefEnc[tableLiteralLengths]) 627 mode |= uint8(m) << 6 628 } 629 if ofEnc.useRLE { 630 mode |= uint8(compModeRLE) << 4 631 ofEnc.setRLE(b.sequences[0].ofCode) 632 if debug { 633 println("ofEnc.useRLE") 634 } 635 } else { 636 var m seqCompMode 637 ofEnc, m = chooseComp(ofEnc, b.coders.ofPrev, &fsePredefEnc[tableOffsets]) 638 mode |= uint8(m) << 4 639 } 640 641 if mlEnc.useRLE { 642 mode |= uint8(compModeRLE) << 2 643 mlEnc.setRLE(b.sequences[0].mlCode) 644 if debug { 645 println("mlEnc.useRLE, code: ", b.sequences[0].mlCode, "value", b.sequences[0].matchLen) 646 } 647 } else { 648 var m seqCompMode 649 mlEnc, m = chooseComp(mlEnc, b.coders.mlPrev, &fsePredefEnc[tableMatchLengths]) 650 mode |= uint8(m) << 2 651 } 652 b.output = append(b.output, mode) 653 if debug { 654 printf("Compression modes: 0b%b", mode) 655 } 656 b.output, err = llEnc.writeCount(b.output) 657 if err != nil { 658 return err 659 } 660 start := len(b.output) 661 b.output, err = ofEnc.writeCount(b.output) 662 if err != nil { 663 return err 664 } 665 if false { 666 println("block:", b.output[start:], "tablelog", ofEnc.actualTableLog, "maxcount:", ofEnc.maxCount) 667 fmt.Printf("selected TableLog: %d, Symbol length: %d\n", ofEnc.actualTableLog, ofEnc.symbolLen) 668 for i, v := range ofEnc.norm[:ofEnc.symbolLen] { 669 fmt.Printf("%3d: %5d -> %4d \n", i, ofEnc.count[i], v) 670 } 671 } 672 b.output, err = mlEnc.writeCount(b.output) 673 if err != nil { 674 return err 675 } 676 677 // Maybe in block? 678 wr := &b.wr 679 wr.reset(b.output) 680 681 var ll, of, ml cState 682 683 // Current sequence 684 seq := len(b.sequences) - 1 685 s := b.sequences[seq] 686 llEnc.setBits(llBitsTable[:]) 687 mlEnc.setBits(mlBitsTable[:]) 688 ofEnc.setBits(nil) 689 690 llTT, ofTT, mlTT := llEnc.ct.symbolTT[:256], ofEnc.ct.symbolTT[:256], mlEnc.ct.symbolTT[:256] 691 692 // We have 3 bounds checks here (and in the loop). 693 // Since we are iterating backwards it is kinda hard to avoid. 694 llB, ofB, mlB := llTT[s.llCode], ofTT[s.ofCode], mlTT[s.mlCode] 695 ll.init(wr, &llEnc.ct, llB) 696 of.init(wr, &ofEnc.ct, ofB) 697 wr.flush32() 698 ml.init(wr, &mlEnc.ct, mlB) 699 700 // Each of these lookups also generates a bounds check. 701 wr.addBits32NC(s.litLen, llB.outBits) 702 wr.addBits32NC(s.matchLen, mlB.outBits) 703 wr.flush32() 704 wr.addBits32NC(s.offset, ofB.outBits) 705 if debugSequences { 706 println("Encoded seq", seq, s, "codes:", s.llCode, s.mlCode, s.ofCode, "states:", ll.state, ml.state, of.state, "bits:", llB, mlB, ofB) 707 } 708 seq-- 709 if llEnc.maxBits+mlEnc.maxBits+ofEnc.maxBits <= 32 { 710 // No need to flush (common) 711 for seq >= 0 { 712 s = b.sequences[seq] 713 wr.flush32() 714 llB, ofB, mlB := llTT[s.llCode], ofTT[s.ofCode], mlTT[s.mlCode] 715 // tabelog max is 8 for all. 716 of.encode(ofB) 717 ml.encode(mlB) 718 ll.encode(llB) 719 wr.flush32() 720 721 // We checked that all can stay within 32 bits 722 wr.addBits32NC(s.litLen, llB.outBits) 723 wr.addBits32NC(s.matchLen, mlB.outBits) 724 wr.addBits32NC(s.offset, ofB.outBits) 725 726 if debugSequences { 727 println("Encoded seq", seq, s) 728 } 729 730 seq-- 731 } 732 } else { 733 for seq >= 0 { 734 s = b.sequences[seq] 735 wr.flush32() 736 llB, ofB, mlB := llTT[s.llCode], ofTT[s.ofCode], mlTT[s.mlCode] 737 // tabelog max is below 8 for each. 738 of.encode(ofB) 739 ml.encode(mlB) 740 ll.encode(llB) 741 wr.flush32() 742 743 // ml+ll = max 32 bits total 744 wr.addBits32NC(s.litLen, llB.outBits) 745 wr.addBits32NC(s.matchLen, mlB.outBits) 746 wr.flush32() 747 wr.addBits32NC(s.offset, ofB.outBits) 748 749 if debugSequences { 750 println("Encoded seq", seq, s) 751 } 752 753 seq-- 754 } 755 } 756 ml.flush(mlEnc.actualTableLog) 757 of.flush(ofEnc.actualTableLog) 758 ll.flush(llEnc.actualTableLog) 759 err = wr.close() 760 if err != nil { 761 return err 762 } 763 b.output = wr.out 764 765 if len(b.output)-3-bhOffset >= b.size { 766 // Maybe even add a bigger margin. 767 b.litEnc.Reuse = huff0.ReusePolicyNone 768 return errIncompressible 769 } 770 771 // Size is output minus block header. 772 bh.setSize(uint32(len(b.output)-bhOffset) - 3) 773 if debug { 774 println("Rewriting block header", bh) 775 } 776 _ = bh.appendTo(b.output[bhOffset:bhOffset]) 777 b.coders.setPrev(llEnc, mlEnc, ofEnc) 778 return nil 779} 780 781var errIncompressible = errors.New("incompressible") 782 783func (b *blockEnc) genCodes() { 784 if len(b.sequences) == 0 { 785 // nothing to do 786 return 787 } 788 789 if len(b.sequences) > math.MaxUint16 { 790 panic("can only encode up to 64K sequences") 791 } 792 // No bounds checks after here: 793 llH := b.coders.llEnc.Histogram()[:256] 794 ofH := b.coders.ofEnc.Histogram()[:256] 795 mlH := b.coders.mlEnc.Histogram()[:256] 796 for i := range llH { 797 llH[i] = 0 798 } 799 for i := range ofH { 800 ofH[i] = 0 801 } 802 for i := range mlH { 803 mlH[i] = 0 804 } 805 806 var llMax, ofMax, mlMax uint8 807 for i, seq := range b.sequences { 808 v := llCode(seq.litLen) 809 seq.llCode = v 810 llH[v]++ 811 if v > llMax { 812 llMax = v 813 } 814 815 v = ofCode(seq.offset) 816 seq.ofCode = v 817 ofH[v]++ 818 if v > ofMax { 819 ofMax = v 820 } 821 822 v = mlCode(seq.matchLen) 823 seq.mlCode = v 824 mlH[v]++ 825 if v > mlMax { 826 mlMax = v 827 if debugAsserts && mlMax > maxMatchLengthSymbol { 828 panic(fmt.Errorf("mlMax > maxMatchLengthSymbol (%d), matchlen: %d", mlMax, seq.matchLen)) 829 } 830 } 831 b.sequences[i] = seq 832 } 833 maxCount := func(a []uint32) int { 834 var max uint32 835 for _, v := range a { 836 if v > max { 837 max = v 838 } 839 } 840 return int(max) 841 } 842 if debugAsserts && mlMax > maxMatchLengthSymbol { 843 panic(fmt.Errorf("mlMax > maxMatchLengthSymbol (%d)", mlMax)) 844 } 845 if debugAsserts && ofMax > maxOffsetBits { 846 panic(fmt.Errorf("ofMax > maxOffsetBits (%d)", ofMax)) 847 } 848 if debugAsserts && llMax > maxLiteralLengthSymbol { 849 panic(fmt.Errorf("llMax > maxLiteralLengthSymbol (%d)", llMax)) 850 } 851 852 b.coders.mlEnc.HistogramFinished(mlMax, maxCount(mlH[:mlMax+1])) 853 b.coders.ofEnc.HistogramFinished(ofMax, maxCount(ofH[:ofMax+1])) 854 b.coders.llEnc.HistogramFinished(llMax, maxCount(llH[:llMax+1])) 855} 856