1package flate 2 3import "fmt" 4 5// fastEncL3 6type fastEncL3 struct { 7 fastGen 8 table [tableSize]tableEntryPrev 9} 10 11// Encode uses a similar algorithm to level 2, will check up to two candidates. 12func (e *fastEncL3) Encode(dst *tokens, src []byte) { 13 const ( 14 inputMargin = 8 - 1 15 minNonLiteralBlockSize = 1 + 1 + inputMargin 16 ) 17 18 if debugDeflate && e.cur < 0 { 19 panic(fmt.Sprint("e.cur < 0: ", e.cur)) 20 } 21 22 // Protect against e.cur wraparound. 23 for e.cur >= bufferReset { 24 if len(e.hist) == 0 { 25 for i := range e.table[:] { 26 e.table[i] = tableEntryPrev{} 27 } 28 e.cur = maxMatchOffset 29 break 30 } 31 // Shift down everything in the table that isn't already too far away. 32 minOff := e.cur + int32(len(e.hist)) - maxMatchOffset 33 for i := range e.table[:] { 34 v := e.table[i] 35 if v.Cur.offset <= minOff { 36 v.Cur.offset = 0 37 } else { 38 v.Cur.offset = v.Cur.offset - e.cur + maxMatchOffset 39 } 40 if v.Prev.offset <= minOff { 41 v.Prev.offset = 0 42 } else { 43 v.Prev.offset = v.Prev.offset - e.cur + maxMatchOffset 44 } 45 e.table[i] = v 46 } 47 e.cur = maxMatchOffset 48 } 49 50 s := e.addBlock(src) 51 52 // Skip if too small. 53 if len(src) < minNonLiteralBlockSize { 54 // We do not fill the token table. 55 // This will be picked up by caller. 56 dst.n = uint16(len(src)) 57 return 58 } 59 60 // Override src 61 src = e.hist 62 nextEmit := s 63 64 // sLimit is when to stop looking for offset/length copies. The inputMargin 65 // lets us use a fast path for emitLiteral in the main loop, while we are 66 // looking for copies. 67 sLimit := int32(len(src) - inputMargin) 68 69 // nextEmit is where in src the next emitLiteral should start from. 70 cv := load3232(src, s) 71 for { 72 const skipLog = 6 73 nextS := s 74 var candidate tableEntry 75 for { 76 nextHash := hash(cv) 77 s = nextS 78 nextS = s + 1 + (s-nextEmit)>>skipLog 79 if nextS > sLimit { 80 goto emitRemainder 81 } 82 candidates := e.table[nextHash] 83 now := load3232(src, nextS) 84 85 // Safe offset distance until s + 4... 86 minOffset := e.cur + s - (maxMatchOffset - 4) 87 e.table[nextHash] = tableEntryPrev{Prev: candidates.Cur, Cur: tableEntry{offset: s + e.cur}} 88 89 // Check both candidates 90 candidate = candidates.Cur 91 if candidate.offset < minOffset { 92 cv = now 93 // Previous will also be invalid, we have nothing. 94 continue 95 } 96 97 if cv == load3232(src, candidate.offset-e.cur) { 98 if candidates.Prev.offset < minOffset || cv != load3232(src, candidates.Prev.offset-e.cur) { 99 break 100 } 101 // Both match and are valid, pick longest. 102 offset := s - (candidate.offset - e.cur) 103 o2 := s - (candidates.Prev.offset - e.cur) 104 l1, l2 := matchLen(src[s+4:], src[s-offset+4:]), matchLen(src[s+4:], src[s-o2+4:]) 105 if l2 > l1 { 106 candidate = candidates.Prev 107 } 108 break 109 } else { 110 // We only check if value mismatches. 111 // Offset will always be invalid in other cases. 112 candidate = candidates.Prev 113 if candidate.offset > minOffset && cv == load3232(src, candidate.offset-e.cur) { 114 break 115 } 116 } 117 cv = now 118 } 119 120 // Call emitCopy, and then see if another emitCopy could be our next 121 // move. Repeat until we find no match for the input immediately after 122 // what was consumed by the last emitCopy call. 123 // 124 // If we exit this loop normally then we need to call emitLiteral next, 125 // though we don't yet know how big the literal will be. We handle that 126 // by proceeding to the next iteration of the main loop. We also can 127 // exit this loop via goto if we get close to exhausting the input. 128 for { 129 // Invariant: we have a 4-byte match at s, and no need to emit any 130 // literal bytes prior to s. 131 132 // Extend the 4-byte match as long as possible. 133 // 134 t := candidate.offset - e.cur 135 l := e.matchlenLong(s+4, t+4, src) + 4 136 137 // Extend backwards 138 for t > 0 && s > nextEmit && src[t-1] == src[s-1] { 139 s-- 140 t-- 141 l++ 142 } 143 if nextEmit < s { 144 emitLiteral(dst, src[nextEmit:s]) 145 } 146 147 dst.AddMatchLong(l, uint32(s-t-baseMatchOffset)) 148 s += l 149 nextEmit = s 150 if nextS >= s { 151 s = nextS + 1 152 } 153 154 if s >= sLimit { 155 t += l 156 // Index first pair after match end. 157 if int(t+4) < len(src) && t > 0 { 158 cv := load3232(src, t) 159 nextHash := hash(cv) 160 e.table[nextHash] = tableEntryPrev{ 161 Prev: e.table[nextHash].Cur, 162 Cur: tableEntry{offset: e.cur + t}, 163 } 164 } 165 goto emitRemainder 166 } 167 168 // We could immediately start working at s now, but to improve 169 // compression we first update the hash table at s-3 to s. 170 x := load6432(src, s-3) 171 prevHash := hash(uint32(x)) 172 e.table[prevHash] = tableEntryPrev{ 173 Prev: e.table[prevHash].Cur, 174 Cur: tableEntry{offset: e.cur + s - 3}, 175 } 176 x >>= 8 177 prevHash = hash(uint32(x)) 178 179 e.table[prevHash] = tableEntryPrev{ 180 Prev: e.table[prevHash].Cur, 181 Cur: tableEntry{offset: e.cur + s - 2}, 182 } 183 x >>= 8 184 prevHash = hash(uint32(x)) 185 186 e.table[prevHash] = tableEntryPrev{ 187 Prev: e.table[prevHash].Cur, 188 Cur: tableEntry{offset: e.cur + s - 1}, 189 } 190 x >>= 8 191 currHash := hash(uint32(x)) 192 candidates := e.table[currHash] 193 cv = uint32(x) 194 e.table[currHash] = tableEntryPrev{ 195 Prev: candidates.Cur, 196 Cur: tableEntry{offset: s + e.cur}, 197 } 198 199 // Check both candidates 200 candidate = candidates.Cur 201 minOffset := e.cur + s - (maxMatchOffset - 4) 202 203 if candidate.offset > minOffset && cv != load3232(src, candidate.offset-e.cur) { 204 // We only check if value mismatches. 205 // Offset will always be invalid in other cases. 206 candidate = candidates.Prev 207 if candidate.offset > minOffset && cv == load3232(src, candidate.offset-e.cur) { 208 offset := s - (candidate.offset - e.cur) 209 if offset <= maxMatchOffset { 210 continue 211 } 212 } 213 } 214 cv = uint32(x >> 8) 215 s++ 216 break 217 } 218 } 219 220emitRemainder: 221 if int(nextEmit) < len(src) { 222 // If nothing was added, don't encode literals. 223 if dst.n == 0 { 224 return 225 } 226 227 emitLiteral(dst, src[nextEmit:]) 228 } 229} 230