level4.go

Documentation: github.com/klauspost/compress/flate

     1  package flate
     2  
     3  import "fmt"
     4  
     5  type fastEncL4 struct {
     6  	fastGen
     7  	table  [tableSize]tableEntry
     8  	bTable [tableSize]tableEntry
     9  }
    10  
    11  func (e *fastEncL4) 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  	// Protect against e.cur wraparound.
    21  	for e.cur >= bufferReset {
    22  		if len(e.hist) == 0 {
    23  			for i := range e.table[:] {
    24  				e.table[i] = tableEntry{}
    25  			}
    26  			for i := range e.bTable[:] {
    27  				e.bTable[i] = tableEntry{}
    28  			}
    29  			e.cur = maxMatchOffset
    30  			break
    31  		}
    32  		// Shift down everything in the table that isn't already too far away.
    33  		minOff := e.cur + int32(len(e.hist)) - maxMatchOffset
    34  		for i := range e.table[:] {
    35  			v := e.table[i].offset
    36  			if v <= minOff {
    37  				v = 0
    38  			} else {
    39  				v = v - e.cur + maxMatchOffset
    40  			}
    41  			e.table[i].offset = v
    42  		}
    43  		for i := range e.bTable[:] {
    44  			v := e.bTable[i].offset
    45  			if v <= minOff {
    46  				v = 0
    47  			} else {
    48  				v = v - e.cur + maxMatchOffset
    49  			}
    50  			e.bTable[i].offset = v
    51  		}
    52  		e.cur = maxMatchOffset
    53  	}
    54  
    55  	s := e.addBlock(src)
    56  
    57  	// This check isn't in the Snappy implementation, but there, the caller
    58  	// instead of the callee handles this case.
    59  	if len(src) < minNonLiteralBlockSize {
    60  		// We do not fill the token table.
    61  		// This will be picked up by caller.
    62  		dst.n = uint16(len(src))
    63  		return
    64  	}
    65  
    66  	// Override src
    67  	src = e.hist
    68  	nextEmit := s
    69  
    70  	// sLimit is when to stop looking for offset/length copies. The inputMargin
    71  	// lets us use a fast path for emitLiteral in the main loop, while we are
    72  	// looking for copies.
    73  	sLimit := int32(len(src) - inputMargin)
    74  
    75  	// nextEmit is where in src the next emitLiteral should start from.
    76  	cv := load6432(src, s)
    77  	for {
    78  		const skipLog = 6
    79  		const doEvery = 1
    80  
    81  		nextS := s
    82  		var t int32
    83  		for {
    84  			nextHashS := hashLen(cv, tableBits, hashShortBytes)
    85  			nextHashL := hash7(cv, tableBits)
    86  
    87  			s = nextS
    88  			nextS = s + doEvery + (s-nextEmit)>>skipLog
    89  			if nextS > sLimit {
    90  				goto emitRemainder
    91  			}
    92  			// Fetch a short+long candidate
    93  			sCandidate := e.table[nextHashS]
    94  			lCandidate := e.bTable[nextHashL]
    95  			next := load6432(src, nextS)
    96  			entry := tableEntry{offset: s + e.cur}
    97  			e.table[nextHashS] = entry
    98  			e.bTable[nextHashL] = entry
    99  
   100  			t = lCandidate.offset - e.cur
   101  			if s-t < maxMatchOffset && uint32(cv) == load3232(src, lCandidate.offset-e.cur) {
   102  				// We got a long match. Use that.
   103  				break
   104  			}
   105  
   106  			t = sCandidate.offset - e.cur
   107  			if s-t < maxMatchOffset && uint32(cv) == load3232(src, sCandidate.offset-e.cur) {
   108  				// Found a 4 match...
   109  				lCandidate = e.bTable[hash7(next, tableBits)]
   110  
   111  				// If the next long is a candidate, check if we should use that instead...
   112  				lOff := nextS - (lCandidate.offset - e.cur)
   113  				if lOff < maxMatchOffset && load3232(src, lCandidate.offset-e.cur) == uint32(next) {
   114  					l1, l2 := matchLen(src[s+4:], src[t+4:]), matchLen(src[nextS+4:], src[nextS-lOff+4:])
   115  					if l2 > l1 {
   116  						s = nextS
   117  						t = lCandidate.offset - e.cur
   118  					}
   119  				}
   120  				break
   121  			}
   122  			cv = next
   123  		}
   124  
   125  		// A 4-byte match has been found. We'll later see if more than 4 bytes
   126  		// match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
   127  		// them as literal bytes.
   128  
   129  		// Extend the 4-byte match as long as possible.
   130  		l := e.matchlenLong(s+4, t+4, src) + 4
   131  
   132  		// Extend backwards
   133  		for t > 0 && s > nextEmit && src[t-1] == src[s-1] {
   134  			s--
   135  			t--
   136  			l++
   137  		}
   138  		if nextEmit < s {
   139  			if false {
   140  				emitLiteral(dst, src[nextEmit:s])
   141  			} else {
   142  				for _, v := range src[nextEmit:s] {
   143  					dst.tokens[dst.n] = token(v)
   144  					dst.litHist[v]++
   145  					dst.n++
   146  				}
   147  			}
   148  		}
   149  		if debugDeflate {
   150  			if t >= s {
   151  				panic("s-t")
   152  			}
   153  			if (s - t) > maxMatchOffset {
   154  				panic(fmt.Sprintln("mmo", t))
   155  			}
   156  			if l < baseMatchLength {
   157  				panic("bml")
   158  			}
   159  		}
   160  
   161  		dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
   162  		s += l
   163  		nextEmit = s
   164  		if nextS >= s {
   165  			s = nextS + 1
   166  		}
   167  
   168  		if s >= sLimit {
   169  			// Index first pair after match end.
   170  			if int(s+8) < len(src) {
   171  				cv := load6432(src, s)
   172  				e.table[hashLen(cv, tableBits, hashShortBytes)] = tableEntry{offset: s + e.cur}
   173  				e.bTable[hash7(cv, tableBits)] = tableEntry{offset: s + e.cur}
   174  			}
   175  			goto emitRemainder
   176  		}
   177  
   178  		// Store every 3rd hash in-between
   179  		if true {
   180  			i := nextS
   181  			if i < s-1 {
   182  				cv := load6432(src, i)
   183  				t := tableEntry{offset: i + e.cur}
   184  				t2 := tableEntry{offset: t.offset + 1}
   185  				e.bTable[hash7(cv, tableBits)] = t
   186  				e.bTable[hash7(cv>>8, tableBits)] = t2
   187  				e.table[hashLen(cv>>8, tableBits, hashShortBytes)] = t2
   188  
   189  				i += 3
   190  				for ; i < s-1; i += 3 {
   191  					cv := load6432(src, i)
   192  					t := tableEntry{offset: i + e.cur}
   193  					t2 := tableEntry{offset: t.offset + 1}
   194  					e.bTable[hash7(cv, tableBits)] = t
   195  					e.bTable[hash7(cv>>8, tableBits)] = t2
   196  					e.table[hashLen(cv>>8, tableBits, hashShortBytes)] = t2
   197  				}
   198  			}
   199  		}
   200  
   201  		// We could immediately start working at s now, but to improve
   202  		// compression we first update the hash table at s-1 and at s.
   203  		x := load6432(src, s-1)
   204  		o := e.cur + s - 1
   205  		prevHashS := hashLen(x, tableBits, hashShortBytes)
   206  		prevHashL := hash7(x, tableBits)
   207  		e.table[prevHashS] = tableEntry{offset: o}
   208  		e.bTable[prevHashL] = tableEntry{offset: o}
   209  		cv = x >> 8
   210  	}
   211  
   212  emitRemainder:
   213  	if int(nextEmit) < len(src) {
   214  		// If nothing was added, don't encode literals.
   215  		if dst.n == 0 {
   216  			return
   217  		}
   218  
   219  		emitLiteral(dst, src[nextEmit:])
   220  	}
   221  }
   222
View as plain text