package brotliimport/* Copyright 2015 Google Inc. All Rights Reserved. Distributed under MIT license. See file LICENSE for detail or copy at https://opensource.org/licenses/MIT*//* Function for fast encoding of an input fragment, independently from the input history. This function uses two-pass processing: in the first pass we save the found backward matches and literal bytes into a buffer, and in the second pass we emit them into the bit stream using prefix codes built based on the actual command and literal byte histograms. */const kCompressFragmentTwoPassBlockSize uint = 1 << 17func hash1( []byte, uint, uint) uint32 {varuint64 = (binary.LittleEndian.Uint64() << ((8 - ) * 8)) * uint64(kHashMul32)returnuint32( >> )}func hashBytesAtOffset( uint64, uint, uint, uint) uint32 {assert( <= 8-) {varuint64 = (( >> (8 * )) << ((8 - ) * 8)) * uint64(kHashMul32)returnuint32( >> ) }}func isMatch1( []byte, []byte, uint) bool {ifbinary.LittleEndian.Uint32() != binary.LittleEndian.Uint32() {returnfalse }if == 4 {returntrue }return [4] == [4] && [5] == [5]}/* Builds a command and distance prefix code (each 64 symbols) into "depth" and "bits" based on "histogram" and stores it into the bit stream. */func buildAndStoreCommandPrefixCode( []uint32, []byte, []uint16, *uint, []byte) {var [129]huffmanTreevar = [numCommandSymbols]byte{0}/* Tree size for building a tree over 64 symbols is 2 * 64 + 1. */var [64]uint16createHuffmanTree(, 64, 15, [:], )createHuffmanTree([64:], 64, 14, [:], [64:])/* We have to jump through a few hoops here in order to compute the command bits because the symbols are in a different order than in the full alphabet. This looks complicated, but having the symbols in this order in the command bits saves a few branches in the Emit* functions. */copy([:], [24:][:24])copy([24:][:], [:8])copy([32:][:], [48:][:8])copy([40:][:], [8:][:8])copy([48:][:], [56:][:8])copy([56:][:], [16:][:8])convertBitDepthsToSymbols([:], 64, [:])copy(, [24:][:8])copy([8:], [40:][:8])copy([16:], [56:][:8])copy([24:], [:24])copy([48:], [32:][:8])copy([56:], [48:][:8])convertBitDepthsToSymbols([64:], 64, [64:]) {/* Create the bit length array for the full command alphabet. */varuintfor := 0; < int(64); ++ { [] = 0 } /* only 64 first values were used */copy([:], [24:][:8])copy([64:][:], [32:][:8])copy([128:][:], [40:][:8])copy([192:][:], [48:][:8])copy([384:][:], [56:][:8])for = 0; < 8; ++ { [128+8*] = [] [256+8*] = [8+] [448+8*] = [16+] }storeHuffmanTree([:], numCommandSymbols, [:], , ) }storeHuffmanTree([64:], 64, [:], , )}func emitInsertLen( uint32, *[]uint32) {if < 6 { (*)[0] = } elseif < 130 {varuint32 = - 2varuint32 = log2FloorNonZero(uint()) - 1varuint32 = >> varuint32 = ( << 1) + + 2varuint32 = - ( << ) (*)[0] = | <<8 } elseif < 2114 {varuint32 = - 66varuint32 = log2FloorNonZero(uint())varuint32 = + 10varuint32 = - (1 << ) (*)[0] = | <<8 } elseif < 6210 {varuint32 = - 2114 (*)[0] = 21 | <<8 } elseif < 22594 {varuint32 = - 6210 (*)[0] = 22 | <<8 } else {varuint32 = - 22594 (*)[0] = 23 | <<8 } * = (*)[1:]}func emitCopyLen( uint, *[]uint32) {if < 10 { (*)[0] = uint32( + 38) } elseif < 134 {varuint = - 6varuint = uint(log2FloorNonZero() - 1)varuint = >> varuint = ( << 1) + + 44varuint = - ( << ) (*)[0] = uint32( | <<8) } elseif < 2118 {varuint = - 70varuint = uint(log2FloorNonZero())varuint = + 52varuint = - (uint(1) << ) (*)[0] = uint32( | <<8) } else {varuint = - 2118 (*)[0] = uint32(63 | <<8) } * = (*)[1:]}func emitCopyLenLastDistance( uint, *[]uint32) {if < 12 { (*)[0] = uint32( + 20) * = (*)[1:] } elseif < 72 {varuint = - 8varuint = uint(log2FloorNonZero() - 1)varuint = >> varuint = ( << 1) + + 28varuint = - ( << ) (*)[0] = uint32( | <<8) * = (*)[1:] } elseif < 136 {varuint = - 8varuint = ( >> 5) + 54varuint = & 31 (*)[0] = uint32( | <<8) * = (*)[1:] (*)[0] = 64 * = (*)[1:] } elseif < 2120 {varuint = - 72varuint = uint(log2FloorNonZero())varuint = + 52varuint = - (uint(1) << ) (*)[0] = uint32( | <<8) * = (*)[1:] (*)[0] = 64 * = (*)[1:] } else {varuint = - 2120 (*)[0] = uint32(63 | <<8) * = (*)[1:] (*)[0] = 64 * = (*)[1:] }}func emitDistance( uint32, *[]uint32) {varuint32 = + 3varuint32 = log2FloorNonZero(uint()) - 1varuint32 = ( >> ) & 1varuint32 = (2 + ) << varuint32 = 2*(-1) + + 80varuint32 = - (*)[0] = | <<8 * = (*)[1:]}/* REQUIRES: len <= 1 << 24. */func storeMetaBlockHeader( uint, bool, *uint, []byte) {varuint = 6/* ISLAST */writeBits(1, 0, , )if <= 1<<16 { = 4 } elseif <= 1<<20 { = 5 }writeBits(2, uint64()-4, , )writeBits(*4, uint64()-1, , )/* ISUNCOMPRESSED */writeSingleBit(, , )}func createCommands( []byte, uint, uint, []byte, []int, uint, uint, *[]byte, *[]uint32) {varint = 0varuint = 64 - varint = int()varint = -cap() + cap()varint = 0varint = -1/* "ip" is the input pointer. */constuint = windowGap/* "next_emit" is a pointer to the first byte that is not covered by a previous copy. Bytes between "next_emit" and the start of the next copy or the end of the input will be emitted as literal bytes. */if >= {varuint = brotli_min_size_t(-, -)varint = int()/* For the last block, we need to keep a 16 bytes margin so that we can be sure that all distances are at most window size - 16. For all other blocks, we only need to keep a margin of 5 bytes so that we don't go over the block size with a copy. */varuint32 ++for = hash1([:], , ); ; {varuint32 = 32varint = /* Step 1: Scan forward in the input looking for a 6-byte-long match. If we get close to exhausting the input then goto emit_remainder. Heuristic match skipping: If 32 bytes are scanned with no matches found, start looking only at every other byte. If 32 more bytes are scanned, look at every third byte, etc.. When a match is found, immediately go back to looking at every byte. This is a small loss (~5% performance, ~0.1% density) for compressible data due to more bookkeeping, but for non-compressible data (such as JPEG) it's a huge win since the compressor quickly "realizes" the data is incompressible and doesn't bother looking for matches everywhere. The "skip" variable keeps track of how many bytes there are since the last match; dividing it by 32 (ie. right-shifting by five) gives the number of bytes to move ahead for each iteration. */varintassert( < ) :for {varuint32 = varuint32 = >> 5 ++ = assert( == hash1([:], , )) = int(uint32() + )if > {goto } = hash1([:], , ) = - ifisMatch1([:], [-:], ) {if < { [] = int( - )break } } = + []assert( >= )assert( < ) [] = int( - )ifisMatch1([:], [-:], ) {break } }/* Check copy distance. If candidate is not feasible, continue search. Checking is done outside of hot loop to reduce overhead. */if - > maxDistance_compress_fragment {goto }/* Step 2: Emit the found match together with the literal bytes from "next_emit", and then see if we can find a next match immediately afterwards. Repeat until we find no match for the input without emitting some literal bytes. */ {varint = /* > 0 */varuint = + findMatchLengthWithLimit([uint(-)+:], [uint()+:], uint(-)-)varint = int( - )/* We have a 6-byte match at ip, and we need to emit bytes in [next_emit, ip). */varint = int( - ) += int()emitInsertLen(uint32(), )copy(*, [:][:uint()]) * = (*)[:]if == { (*)[0] = 64 * = (*)[1:] } else {emitDistance(uint32(), ) = }emitCopyLenLastDistance(, ) = if >= {goto } {varuint64varuint32/* We could immediately start working at ip now, but to improve compression we first update "table" with the hashes of some positions within the last copy. */varuint32if == 4 { = binary.LittleEndian.Uint64([-3:]) = hashBytesAtOffset(, 3, , ) = hashBytesAtOffset(, 0, , ) [] = int( - - 3) = hashBytesAtOffset(, 1, , ) [] = int( - - 2) = hashBytesAtOffset(, 0, , ) [] = int( - - 1) } else { = binary.LittleEndian.Uint64([-5:]) = hashBytesAtOffset(, 0, , ) [] = int( - - 5) = hashBytesAtOffset(, 1, , ) [] = int( - - 4) = hashBytesAtOffset(, 2, , ) [] = int( - - 3) = binary.LittleEndian.Uint64([-2:]) = hashBytesAtOffset(, 2, , ) = hashBytesAtOffset(, 0, , ) [] = int( - - 2) = hashBytesAtOffset(, 1, , ) [] = int( - - 1) } = + [] [] = int( - ) } }for - <= maxDistance_compress_fragment && isMatch1([:], [-:], ) {varint = /* We have a 6-byte match at ip, and no need to emit any literal bytes prior to ip. */varuint = + findMatchLengthWithLimit([uint(-)+:], [uint()+:], uint(-)-) += int() = int( - ) /* > 0 */emitCopyLen(, )emitDistance(uint32(), ) = if >= {goto } {varuint64varuint32/* We could immediately start working at ip now, but to improve compression we first update "table" with the hashes of some positions within the last copy. */varuint32if == 4 { = binary.LittleEndian.Uint64([-3:]) = hashBytesAtOffset(, 3, , ) = hashBytesAtOffset(, 0, , ) [] = int( - - 3) = hashBytesAtOffset(, 1, , ) [] = int( - - 2) = hashBytesAtOffset(, 2, , ) [] = int( - - 1) } else { = binary.LittleEndian.Uint64([-5:]) = hashBytesAtOffset(, 0, , ) [] = int( - - 5) = hashBytesAtOffset(, 1, , ) [] = int( - - 4) = hashBytesAtOffset(, 2, , ) [] = int( - - 3) = binary.LittleEndian.Uint64([-2:]) = hashBytesAtOffset(, 2, , ) = hashBytesAtOffset(, 0, , ) [] = int( - - 2) = hashBytesAtOffset(, 1, , ) [] = int( - - 1) } = + [] [] = int( - ) } } ++ = hash1([:], , ) } }:assert( <= )/* Emit the remaining bytes as literals. */if < {varuint32 = uint32( - )emitInsertLen(, )copy(*, [:][:]) * = (*)[:] }}var storeCommands_kNumExtraBits = [128]uint32{0,0,0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,7,8,9,10,12,14,24,0,0,0,0,0,0,0,0,1,1,2,2,3,3,4,4,0,0,0,0,0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,7,8,9,10,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,}var storeCommands_kInsertOffset = [24]uint32{0,1,2,3,4,5,6,8,10,14,18,26,34,50,66,98,130,194,322,578,1090,2114,6210,22594,}func storeCommands( []byte, uint, []uint32, uint, *uint, []byte) {var [256]bytevar [256]uint16var = [256]uint32{0}var = [128]byte{0}var = [128]uint16{0}var = [128]uint32{0}varuintfor = 0; < ; ++ { [[]]++ }buildAndStoreHuffmanTreeFast([:], , /* max_bits = */8, [:], [:], , )for = 0; < ; ++ {varuint32 = [] & 0xFFassert( < 128) []++ } [1] += 1 [2] += 1 [64] += 1 [84] += 1buildAndStoreCommandPrefixCode([:], [:], [:], , )for = 0; < ; ++ {varuint32 = []varuint32 = & 0xFFvaruint32 = >> 8assert( < 128)writeBits(uint([]), uint64([]), , )writeBits(uint(storeCommands_kNumExtraBits[]), uint64(), , )if < 24 {varuint32 = storeCommands_kInsertOffset[] + varuint32for = 0; < ; ++ {varbyte = [0]writeBits(uint([]), uint64([]), , ) = [1:] } } }}/* Acceptable loss for uncompressible speedup is 2% */const minRatio = 0.98const sampleRate = 43func shouldCompress( []byte, uint, uint) bool {varfloat64 = float64()iffloat64() < minRatio* {returntrue } else {var = [256]uint32{0}varfloat64 = * 8 * minRatio / sampleRatevaruintfor = 0; < ; += sampleRate { [[]]++ }returnbitsEntropy([:], 256) < }}func rewindBitPosition( uint, *uint, []byte) {varuint = & 7varuint = (1 << ) - 1 [>>3] &= byte() * = }func emitUncompressedMetaBlock( []byte, uint, *uint, []byte) {storeMetaBlockHeader(, true, , ) * = (* + 7) &^ 7copy([*>>3:], [:]) * += << 3 [*>>3] = 0}func compressFragmentTwoPassImpl( []byte, uint, bool, []uint32, []byte, []int, uint, uint, *uint, []byte) {/* Save the start of the first block for position and distance computations. */var []byte = for > 0 {varuint = brotli_min_size_t(, kCompressFragmentTwoPassBlockSize)var []uint32 = var []byte = varuintcreateCommands(, , , , , , , &, &) = uint(-cap() + cap())ifshouldCompress(, , ) {varuint = uint(-cap() + cap())storeMetaBlockHeader(, false, , )/* No block splits, no contexts. */writeBits(13, 0, , )storeCommands(, , , , , ) } else {/* Since we did not find many backward references and the entropy of the data is close to 8 bits, we can simply emit an uncompressed block. This makes compression speed of uncompressible data about 3x faster. */emitUncompressedMetaBlock(, , , ) } = [:] -= }}/* Compresses "input" string to the "*storage" buffer as one or more complete meta-blocks, and updates the "*storage_ix" bit position. If "is_last" is 1, emits an additional empty last meta-block. REQUIRES: "input_size" is greater than zero, or "is_last" is 1. REQUIRES: "input_size" is less or equal to maximal metablock size (1 << 24). REQUIRES: "command_buf" and "literal_buf" point to at least kCompressFragmentTwoPassBlockSize long arrays. REQUIRES: All elements in "table[0..table_size-1]" are initialized to zero. REQUIRES: "table_size" is a power of two OUTPUT: maximal copy distance <= |input_size| OUTPUT: maximal copy distance <= BROTLI_MAX_BACKWARD_LIMIT(18) */func compressFragmentTwoPass( []byte, uint, bool, []uint32, []byte, []int, uint, *uint, []byte) {varuint = *varuint = uint(log2FloorNonZero())varuintif <= 15 { = 4 } else { = 6 }compressFragmentTwoPassImpl(, , , , , , , , , )/* If output is larger than single uncompressed block, rewrite it. */if *- > 31+(<<3) {rewindBitPosition(, , )emitUncompressedMetaBlock(, , , ) }if {writeBits(1, 1, , ) /* islast */writeBits(1, 1, , ) /* isempty */ * = (* + 7) &^ 7 }}
The pages are generated with Goldsv0.6.7. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.