deflatefast.go

     1  // Copyright 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package flate
     6  
     7  import (
     8  	"math/bits"
     9  )
    10  
    11  const (
    12  	// tableBits is the number of bits used in the hash table.
    13  	tableBits = 15
    14  
    15  	// tableSize is the size of the hash table.
    16  	tableSize = 1 << tableBits
    17  
    18  	// hashLongBytes is the number of bytes used for long table hashes.
    19  	hashLongBytes = 7
    20  
    21  	// baseMatchOffset is the smallest match offset.
    22  	baseMatchOffset = 1
    23  
    24  	// baseMatchLength is the smallest match length per RFC section 3.2.5.
    25  	baseMatchLength = 3
    26  
    27  	// maxMatchOffset is the largest match offset.
    28  	maxMatchOffset = 1 << 15
    29  
    30  	// allocHistory is the size to preallocate for history.
    31  	allocHistory = maxStoreBlockSize * 5
    32  
    33  	// bufferReset is the buffer offset at which the history is reset.
    34  	bufferReset = (1 << 31) - allocHistory - maxStoreBlockSize - 1
    35  )
    36  
    37  // fastEncL1 to fastEncL6 provides specialized encoders for levels 1-6
    38  // that each provide a different speed/size/memory strategies.
    39  //
    40  // Level 1: Single small table, 5 byte hashes, sparse indexing.
    41  // Level 2: Single big table, 5 byte hashes, indexing ~ every 2 bytes.
    42  // Level 3: Single medium table, 5 byte hashes, 2 candidates per table entry.
    43  // Level 4: Two tables, 4/7 byte hashes, 1 candidate per table entry.
    44  // Level 5: Two tables, 4/7 byte hashes, 2 candidates per 7-byte table entry.
    45  // Level 6: Two tables, 4/7 byte hashes, full indexing, checks for repeats.
    46  //
    47  // Skipping on contiguous non-matches also decreases as levels go up.
    48  
    49  // fastEnc is the interface implemented by the level 1-6 fast encoders.
    50  type fastEnc interface {
    51  	// encode src into dst.
    52  	encode(dst *tokens, src []byte)
    53  	// reset the encoder so matches are not made with previous data.
    54  	reset()
    55  }
    56  
    57  // newFastEnc returns a fastEnc encoder for the given compression level (1-6).
    58  func newFastEnc(level int) fastEnc {
    59  	switch level {
    60  	case 1:
    61  		return &fastEncL1{fastGen: fastGen{cur: maxStoreBlockSize}}
    62  	case 2:
    63  		return &fastEncL2{fastGen: fastGen{cur: maxStoreBlockSize}}
    64  	case 3:
    65  		return &fastEncL3{fastGen: fastGen{cur: maxStoreBlockSize}}
    66  	case 4:
    67  		return &fastEncL4{fastGen: fastGen{cur: maxStoreBlockSize}}
    68  	case 5:
    69  		return &fastEncL5{fastGen: fastGen{cur: maxStoreBlockSize}}
    70  	case 6:
    71  		return &fastEncL6{fastGen: fastGen{cur: maxStoreBlockSize}}
    72  	default:
    73  		panic("invalid level specified")
    74  	}
    75  }
    76  
    77  // fastGen maintains the table for matches,
    78  // and the previous byte block for level 1 and up.
    79  // This is the generic implementation.
    80  type fastGen struct {
    81  	hist []byte
    82  	cur  int32
    83  }
    84  
    85  // addBlock appends src to the history and returns the offset where src starts in e.hist.
    86  func (e *fastGen) addBlock(src []byte) int32 {
    87  	// check if we have space already
    88  	if len(e.hist)+len(src) > cap(e.hist) {
    89  		if cap(e.hist) == 0 {
    90  			e.hist = make([]byte, 0, allocHistory)
    91  		} else {
    92  			if cap(e.hist) < maxMatchOffset*2 {
    93  				panic("unexpected buffer size")
    94  			}
    95  			// Move down
    96  			offset := int32(len(e.hist)) - maxMatchOffset
    97  			copy(e.hist[0:maxMatchOffset], e.hist[offset:offset+maxMatchOffset])
    98  			e.cur += offset
    99  			e.hist = e.hist[:maxMatchOffset]
   100  		}
   101  	}
   102  	s := int32(len(e.hist))
   103  	e.hist = append(e.hist, src...)
   104  	return s
   105  }
   106  
   107  // matchLenLimited returns the match length between offsets s and t in src.
   108  // The maximum length returned is maxMatchLength - 4.
   109  // It is assumed that s > t, that t >= 0 and s < len(src).
   110  func (e *fastGen) matchLenLimited(s, t int, src []byte) int32 {
   111  	a := src[s:min(s+maxMatchLength-4, len(src))]
   112  	b := src[t:]
   113  	return int32(matchLen(a, b))
   114  }
   115  
   116  // matchLenLong returns the match length between offsets s and t in src.
   117  // It is assumed that s > t, that t >= 0 and s < len(src).
   118  func (e *fastGen) matchLenLong(s, t int, src []byte) int32 {
   119  	return int32(matchLen(src[s:], src[t:]))
   120  }
   121  
   122  // reset resets the encoding table to prepare for a new compression stream.
   123  func (e *fastGen) reset() {
   124  	if cap(e.hist) < allocHistory {
   125  		e.hist = make([]byte, 0, allocHistory)
   126  	}
   127  	// We offset current position so everything will be out of reach.
   128  	// If we are above the buffer reset it will be cleared anyway since len(hist) == 0.
   129  	if e.cur <= bufferReset {
   130  		e.cur += maxMatchOffset + int32(len(e.hist))
   131  	}
   132  	e.hist = e.hist[:0]
   133  }
   134  
   135  func (f *fastGen) getFastGen() *fastGen { return f }
   136  
   137  // tableEntry stores the offset of a hash match in the input history.
   138  type tableEntry struct {
   139  	offset int32
   140  }
   141  
   142  // tableEntryPrev stores the current and previous offsets for a hash entry.
   143  type tableEntryPrev struct {
   144  	cur  tableEntry
   145  	prev tableEntry
   146  }
   147  
   148  const (
   149  	prime3bytes = 506832829
   150  	prime4bytes = 2654435761
   151  	prime5bytes = 889523592379
   152  	prime6bytes = 227718039650203
   153  	prime7bytes = 58295818150454627
   154  	prime8bytes = 0xcf1bbcdcb7a56463
   155  )
   156  
   157  // hashLen returns a hash of the first n bytes of u, using b output bits.
   158  // It expects 3 <= n <= 8; other values are treated as n == 4.
   159  // The bit length b must be <= 32.
   160  // b and n should be constants in speed-critical use.
   161  func hashLen(u uint64, b, n uint8) uint32 {
   162  	switch n {
   163  	case 3:
   164  		return (uint32(u<<8) * prime3bytes) >> (32 - b)
   165  	case 5:
   166  		return uint32(((u << (64 - 40)) * prime5bytes) >> (64 - b))
   167  	case 6:
   168  		return uint32(((u << (64 - 48)) * prime6bytes) >> (64 - b))
   169  	case 7:
   170  		return uint32(((u << (64 - 56)) * prime7bytes) >> (64 - b))
   171  	case 8:
   172  		return uint32((u * prime8bytes) >> (64 - b))
   173  	default:
   174  		return (uint32(u) * prime4bytes) >> (32 - b)
   175  	}
   176  }
   177  
   178  // matchLen returns the maximum common prefix length of a and b.
   179  // a must be the shortest of the two.
   180  func matchLen(a, b []byte) (n int) {
   181  	left := len(a)
   182  	for left >= 8 {
   183  		diff := loadLE64(a, n) ^ loadLE64(b, n)
   184  		if diff != 0 {
   185  			return n + bits.TrailingZeros64(diff)>>3
   186  		}
   187  		n += 8
   188  		left -= 8
   189  	}
   190  
   191  	a = a[n:]
   192  	b = b[n:]
   193  	b = b[:len(a)]
   194  	for i := range a {
   195  		if a[i] != b[i] {
   196  			break
   197  		}
   198  		n++
   199  	}
   200  	return n
   201  }
   202
View as plain text