level6.go

Documentation: github.com/klauspost/compress/flate

     1  package flate
     2  
     3  import "fmt"
     4  
     5  type fastEncL6 struct {
     6  	fastGen
     7  	table  [tableSize]tableEntry
     8  	bTable [tableSize]tableEntryPrev
     9  }
    10  
    11  func (e *fastEncL6) Encode(dst *tokens, src []byte) {
    12  	const (
    13  		inputMargin            = 12 - 1
    14  		minNonLiteralBlockSize = 1 + 1 + inputMargin
    15  		hashShortBytes         = 4
    16  	)
    17  	if debugDeflate && e.cur < 0 {
    18  		panic(fmt.Sprint("e.cur < 0: ", e.cur))
    19  	}
    20  
    21  	// Protect against e.cur wraparound.
    22  	for e.cur >= bufferReset {
    23  		if len(e.hist) == 0 {
    24  			for i := range e.table[:] {
    25  				e.table[i] = tableEntry{}
    26  			}
    27  			for i := range e.bTable[:] {
    28  				e.bTable[i] = tableEntryPrev{}
    29  			}
    30  			e.cur = maxMatchOffset
    31  			break
    32  		}
    33  		// Shift down everything in the table that isn't already too far away.
    34  		minOff := e.cur + int32(len(e.hist)) - maxMatchOffset
    35  		for i := range e.table[:] {
    36  			v := e.table[i].offset
    37  			if v <= minOff {
    38  				v = 0
    39  			} else {
    40  				v = v - e.cur + maxMatchOffset
    41  			}
    42  			e.table[i].offset = v
    43  		}
    44  		for i := range e.bTable[:] {
    45  			v := e.bTable[i]
    46  			if v.Cur.offset <= minOff {
    47  				v.Cur.offset = 0
    48  				v.Prev.offset = 0
    49  			} else {
    50  				v.Cur.offset = v.Cur.offset - e.cur + maxMatchOffset
    51  				if v.Prev.offset <= minOff {
    52  					v.Prev.offset = 0
    53  				} else {
    54  					v.Prev.offset = v.Prev.offset - e.cur + maxMatchOffset
    55  				}
    56  			}
    57  			e.bTable[i] = v
    58  		}
    59  		e.cur = maxMatchOffset
    60  	}
    61  
    62  	s := e.addBlock(src)
    63  
    64  	// This check isn't in the Snappy implementation, but there, the caller
    65  	// instead of the callee handles this case.
    66  	if len(src) < minNonLiteralBlockSize {
    67  		// We do not fill the token table.
    68  		// This will be picked up by caller.
    69  		dst.n = uint16(len(src))
    70  		return
    71  	}
    72  
    73  	// Override src
    74  	src = e.hist
    75  	nextEmit := s
    76  
    77  	// sLimit is when to stop looking for offset/length copies. The inputMargin
    78  	// lets us use a fast path for emitLiteral in the main loop, while we are
    79  	// looking for copies.
    80  	sLimit := int32(len(src) - inputMargin)
    81  
    82  	// nextEmit is where in src the next emitLiteral should start from.
    83  	cv := load6432(src, s)
    84  	// Repeat MUST be > 1 and within range
    85  	repeat := int32(1)
    86  	for {
    87  		const skipLog = 7
    88  		const doEvery = 1
    89  
    90  		nextS := s
    91  		var l int32
    92  		var t int32
    93  		for {
    94  			nextHashS := hashLen(cv, tableBits, hashShortBytes)
    95  			nextHashL := hash7(cv, tableBits)
    96  			s = nextS
    97  			nextS = s + doEvery + (s-nextEmit)>>skipLog
    98  			if nextS > sLimit {
    99  				goto emitRemainder
   100  			}
   101  			// Fetch a short+long candidate
   102  			sCandidate := e.table[nextHashS]
   103  			lCandidate := e.bTable[nextHashL]
   104  			next := load6432(src, nextS)
   105  			entry := tableEntry{offset: s + e.cur}
   106  			e.table[nextHashS] = entry
   107  			eLong := &e.bTable[nextHashL]
   108  			eLong.Cur, eLong.Prev = entry, eLong.Cur
   109  
   110  			// Calculate hashes of 'next'
   111  			nextHashS = hashLen(next, tableBits, hashShortBytes)
   112  			nextHashL = hash7(next, tableBits)
   113  
   114  			t = lCandidate.Cur.offset - e.cur
   115  			if s-t < maxMatchOffset {
   116  				if uint32(cv) == load3232(src, lCandidate.Cur.offset-e.cur) {
   117  					// Long candidate matches at least 4 bytes.
   118  
   119  					// Store the next match
   120  					e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
   121  					eLong := &e.bTable[nextHashL]
   122  					eLong.Cur, eLong.Prev = tableEntry{offset: nextS + e.cur}, eLong.Cur
   123  
   124  					// Check the previous long candidate as well.
   125  					t2 := lCandidate.Prev.offset - e.cur
   126  					if s-t2 < maxMatchOffset && uint32(cv) == load3232(src, lCandidate.Prev.offset-e.cur) {
   127  						l = e.matchlen(s+4, t+4, src) + 4
   128  						ml1 := e.matchlen(s+4, t2+4, src) + 4
   129  						if ml1 > l {
   130  							t = t2
   131  							l = ml1
   132  							break
   133  						}
   134  					}
   135  					break
   136  				}
   137  				// Current value did not match, but check if previous long value does.
   138  				t = lCandidate.Prev.offset - e.cur
   139  				if s-t < maxMatchOffset && uint32(cv) == load3232(src, lCandidate.Prev.offset-e.cur) {
   140  					// Store the next match
   141  					e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
   142  					eLong := &e.bTable[nextHashL]
   143  					eLong.Cur, eLong.Prev = tableEntry{offset: nextS + e.cur}, eLong.Cur
   144  					break
   145  				}
   146  			}
   147  
   148  			t = sCandidate.offset - e.cur
   149  			if s-t < maxMatchOffset && uint32(cv) == load3232(src, sCandidate.offset-e.cur) {
   150  				// Found a 4 match...
   151  				l = e.matchlen(s+4, t+4, src) + 4
   152  
   153  				// Look up next long candidate (at nextS)
   154  				lCandidate = e.bTable[nextHashL]
   155  
   156  				// Store the next match
   157  				e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
   158  				eLong := &e.bTable[nextHashL]
   159  				eLong.Cur, eLong.Prev = tableEntry{offset: nextS + e.cur}, eLong.Cur
   160  
   161  				// Check repeat at s + repOff
   162  				const repOff = 1
   163  				t2 := s - repeat + repOff
   164  				if load3232(src, t2) == uint32(cv>>(8*repOff)) {
   165  					ml := e.matchlen(s+4+repOff, t2+4, src) + 4
   166  					if ml > l {
   167  						t = t2
   168  						l = ml
   169  						s += repOff
   170  						// Not worth checking more.
   171  						break
   172  					}
   173  				}
   174  
   175  				// If the next long is a candidate, use that...
   176  				t2 = lCandidate.Cur.offset - e.cur
   177  				if nextS-t2 < maxMatchOffset {
   178  					if load3232(src, lCandidate.Cur.offset-e.cur) == uint32(next) {
   179  						ml := e.matchlen(nextS+4, t2+4, src) + 4
   180  						if ml > l {
   181  							t = t2
   182  							s = nextS
   183  							l = ml
   184  							// This is ok, but check previous as well.
   185  						}
   186  					}
   187  					// If the previous long is a candidate, use that...
   188  					t2 = lCandidate.Prev.offset - e.cur
   189  					if nextS-t2 < maxMatchOffset && load3232(src, lCandidate.Prev.offset-e.cur) == uint32(next) {
   190  						ml := e.matchlen(nextS+4, t2+4, src) + 4
   191  						if ml > l {
   192  							t = t2
   193  							s = nextS
   194  							l = ml
   195  							break
   196  						}
   197  					}
   198  				}
   199  				break
   200  			}
   201  			cv = next
   202  		}
   203  
   204  		// A 4-byte match has been found. We'll later see if more than 4 bytes
   205  		// match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
   206  		// them as literal bytes.
   207  
   208  		// Extend the 4-byte match as long as possible.
   209  		if l == 0 {
   210  			l = e.matchlenLong(s+4, t+4, src) + 4
   211  		} else if l == maxMatchLength {
   212  			l += e.matchlenLong(s+l, t+l, src)
   213  		}
   214  
   215  		// Try to locate a better match by checking the end-of-match...
   216  		if sAt := s + l; sAt < sLimit {
   217  			// Allow some bytes at the beginning to mismatch.
   218  			// Sweet spot is 2/3 bytes depending on input.
   219  			// 3 is only a little better when it is but sometimes a lot worse.
   220  			// The skipped bytes are tested in Extend backwards,
   221  			// and still picked up as part of the match if they do.
   222  			const skipBeginning = 2
   223  			eLong := &e.bTable[hash7(load6432(src, sAt), tableBits)]
   224  			// Test current
   225  			t2 := eLong.Cur.offset - e.cur - l + skipBeginning
   226  			s2 := s + skipBeginning
   227  			off := s2 - t2
   228  			if off < maxMatchOffset {
   229  				if off > 0 && t2 >= 0 {
   230  					if l2 := e.matchlenLong(s2, t2, src); l2 > l {
   231  						t = t2
   232  						l = l2
   233  						s = s2
   234  					}
   235  				}
   236  				// Test next:
   237  				t2 = eLong.Prev.offset - e.cur - l + skipBeginning
   238  				off := s2 - t2
   239  				if off > 0 && off < maxMatchOffset && t2 >= 0 {
   240  					if l2 := e.matchlenLong(s2, t2, src); l2 > l {
   241  						t = t2
   242  						l = l2
   243  						s = s2
   244  					}
   245  				}
   246  			}
   247  		}
   248  
   249  		// Extend backwards
   250  		for t > 0 && s > nextEmit && src[t-1] == src[s-1] {
   251  			s--
   252  			t--
   253  			l++
   254  		}
   255  		if nextEmit < s {
   256  			if false {
   257  				emitLiteral(dst, src[nextEmit:s])
   258  			} else {
   259  				for _, v := range src[nextEmit:s] {
   260  					dst.tokens[dst.n] = token(v)
   261  					dst.litHist[v]++
   262  					dst.n++
   263  				}
   264  			}
   265  		}
   266  		if false {
   267  			if t >= s {
   268  				panic(fmt.Sprintln("s-t", s, t))
   269  			}
   270  			if (s - t) > maxMatchOffset {
   271  				panic(fmt.Sprintln("mmo", s-t))
   272  			}
   273  			if l < baseMatchLength {
   274  				panic("bml")
   275  			}
   276  		}
   277  
   278  		dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
   279  		repeat = s - t
   280  		s += l
   281  		nextEmit = s
   282  		if nextS >= s {
   283  			s = nextS + 1
   284  		}
   285  
   286  		if s >= sLimit {
   287  			// Index after match end.
   288  			for i := nextS + 1; i < int32(len(src))-8; i += 2 {
   289  				cv := load6432(src, i)
   290  				e.table[hashLen(cv, tableBits, hashShortBytes)] = tableEntry{offset: i + e.cur}
   291  				eLong := &e.bTable[hash7(cv, tableBits)]
   292  				eLong.Cur, eLong.Prev = tableEntry{offset: i + e.cur}, eLong.Cur
   293  			}
   294  			goto emitRemainder
   295  		}
   296  
   297  		// Store every long hash in-between and every second short.
   298  		if true {
   299  			for i := nextS + 1; i < s-1; i += 2 {
   300  				cv := load6432(src, i)
   301  				t := tableEntry{offset: i + e.cur}
   302  				t2 := tableEntry{offset: t.offset + 1}
   303  				eLong := &e.bTable[hash7(cv, tableBits)]
   304  				eLong2 := &e.bTable[hash7(cv>>8, tableBits)]
   305  				e.table[hashLen(cv, tableBits, hashShortBytes)] = t
   306  				eLong.Cur, eLong.Prev = t, eLong.Cur
   307  				eLong2.Cur, eLong2.Prev = t2, eLong2.Cur
   308  			}
   309  		}
   310  
   311  		// We could immediately start working at s now, but to improve
   312  		// compression we first update the hash table at s-1 and at s.
   313  		cv = load6432(src, s)
   314  	}
   315  
   316  emitRemainder:
   317  	if int(nextEmit) < len(src) {
   318  		// If nothing was added, don't encode literals.
   319  		if dst.n == 0 {
   320  			return
   321  		}
   322  
   323  		emitLiteral(dst, src[nextEmit:])
   324  	}
   325  }
   326
View as plain text