encodeBlockGo encodes a non-empty src to a guaranteed-large-enough dst. It assumes that the varint-encoded length of the decompressed bytes has already been written. It also assumes that: len(dst) >= MaxEncodedLen(len(src)) && minNonLiteralBlockSize <= len(src) && len(src) <= maxBlockSize
(dst, src []byte)
| 70 | // len(dst) >= MaxEncodedLen(len(src)) && |
| 71 | // minNonLiteralBlockSize <= len(src) && len(src) <= maxBlockSize |
| 72 | func encodeBlockGo(dst, src []byte) (d int) { |
| 73 | // Initialize the hash table. |
| 74 | const ( |
| 75 | tableBits = 14 |
| 76 | maxTableSize = 1 << tableBits |
| 77 | |
| 78 | debug = false |
| 79 | ) |
| 80 | var table [maxTableSize]uint32 |
| 81 | |
| 82 | // sLimit is when to stop looking for offset/length copies. The inputMargin |
| 83 | // lets us use a fast path for emitLiteral in the main loop, while we are |
| 84 | // looking for copies. |
| 85 | sLimit := len(src) - inputMargin |
| 86 | |
| 87 | // Bail if we can't compress to at least this. |
| 88 | dstLimit := len(src) - len(src)>>5 - 5 |
| 89 | |
| 90 | // nextEmit is where in src the next emitLiteral should start from. |
| 91 | nextEmit := 0 |
| 92 | |
| 93 | // The encoded form must start with a literal, as there are no previous |
| 94 | // bytes to copy, so we start looking for hash matches at s == 1. |
| 95 | s := 1 |
| 96 | cv := load64(src, s) |
| 97 | |
| 98 | // We search for a repeat at -1, but don't output repeats when nextEmit == 0 |
| 99 | repeat := 1 |
| 100 | |
| 101 | for { |
| 102 | candidate := 0 |
| 103 | for { |
| 104 | // Next src position to check |
| 105 | nextS := s + (s-nextEmit)>>6 + 4 |
| 106 | if nextS > sLimit { |
| 107 | goto emitRemainder |
| 108 | } |
| 109 | hash0 := hash6(cv, tableBits) |
| 110 | hash1 := hash6(cv>>8, tableBits) |
| 111 | candidate = int(table[hash0]) |
| 112 | candidate2 := int(table[hash1]) |
| 113 | table[hash0] = uint32(s) |
| 114 | table[hash1] = uint32(s + 1) |
| 115 | hash2 := hash6(cv>>16, tableBits) |
| 116 | |
| 117 | // Check repeat at offset checkRep. |
| 118 | const checkRep = 1 |
| 119 | if uint32(cv>>(checkRep*8)) == load32(src, s-repeat+checkRep) { |
| 120 | base := s + checkRep |
| 121 | // Extend back |
| 122 | for i := base - repeat; base > nextEmit && i > 0 && src[i-1] == src[base-1]; { |
| 123 | i-- |
| 124 | base-- |
| 125 | } |
| 126 | |
| 127 | // Bail if we exceed the maximum size. |
| 128 | if d+(base-nextEmit) > dstLimit { |
| 129 | return 0 |
searching dependent graphs…