fast_encoder.go

Documentation: github.com/klauspost/compress/flate

     1  // Copyright 2011 The Snappy-Go Authors. All rights reserved.
     2  // Modified for deflate by Klaus Post (c) 2015.
     3  // Use of this source code is governed by a BSD-style
     4  // license that can be found in the LICENSE file.
     5  
     6  package flate
     7  
     8  import (
     9  	"encoding/binary"
    10  	"fmt"
    11  )
    12  
    13  type fastEnc interface {
    14  	Encode(dst *tokens, src []byte)
    15  	Reset()
    16  }
    17  
    18  func newFastEnc(level int) fastEnc {
    19  	switch level {
    20  	case 1:
    21  		return &fastEncL1{fastGen: fastGen{cur: maxStoreBlockSize}}
    22  	case 2:
    23  		return &fastEncL2{fastGen: fastGen{cur: maxStoreBlockSize}}
    24  	case 3:
    25  		return &fastEncL3{fastGen: fastGen{cur: maxStoreBlockSize}}
    26  	case 4:
    27  		return &fastEncL4{fastGen: fastGen{cur: maxStoreBlockSize}}
    28  	case 5:
    29  		return &fastEncL5{fastGen: fastGen{cur: maxStoreBlockSize}}
    30  	case 6:
    31  		return &fastEncL6{fastGen: fastGen{cur: maxStoreBlockSize}}
    32  	default:
    33  		panic("invalid level specified")
    34  	}
    35  }
    36  
    37  const (
    38  	tableBits       = 15             // Bits used in the table
    39  	tableSize       = 1 << tableBits // Size of the table
    40  	tableShift      = 32 - tableBits // Right-shift to get the tableBits most significant bits of a uint32.
    41  	baseMatchOffset = 1              // The smallest match offset
    42  	baseMatchLength = 3              // The smallest match length per the RFC section 3.2.5
    43  	maxMatchOffset  = 1 << 15        // The largest match offset
    44  
    45  	bTableBits   = 17                                               // Bits used in the big tables
    46  	bTableSize   = 1 << bTableBits                                  // Size of the table
    47  	allocHistory = maxStoreBlockSize * 5                            // Size to preallocate for history.
    48  	bufferReset  = (1 << 31) - allocHistory - maxStoreBlockSize - 1 // Reset the buffer offset when reaching this.
    49  )
    50  
    51  const (
    52  	prime3bytes = 506832829
    53  	prime4bytes = 2654435761
    54  	prime5bytes = 889523592379
    55  	prime6bytes = 227718039650203
    56  	prime7bytes = 58295818150454627
    57  	prime8bytes = 0xcf1bbcdcb7a56463
    58  )
    59  
    60  func load3232(b []byte, i int32) uint32 {
    61  	return binary.LittleEndian.Uint32(b[i:])
    62  }
    63  
    64  func load6432(b []byte, i int32) uint64 {
    65  	return binary.LittleEndian.Uint64(b[i:])
    66  }
    67  
    68  type tableEntry struct {
    69  	offset int32
    70  }
    71  
    72  // fastGen maintains the table for matches,
    73  // and the previous byte block for level 2.
    74  // This is the generic implementation.
    75  type fastGen struct {
    76  	hist []byte
    77  	cur  int32
    78  }
    79  
    80  func (e *fastGen) addBlock(src []byte) int32 {
    81  	// check if we have space already
    82  	if len(e.hist)+len(src) > cap(e.hist) {
    83  		if cap(e.hist) == 0 {
    84  			e.hist = make([]byte, 0, allocHistory)
    85  		} else {
    86  			if cap(e.hist) < maxMatchOffset*2 {
    87  				panic("unexpected buffer size")
    88  			}
    89  			// Move down
    90  			offset := int32(len(e.hist)) - maxMatchOffset
    91  			// copy(e.hist[0:maxMatchOffset], e.hist[offset:])
    92  			*(*[maxMatchOffset]byte)(e.hist) = *(*[maxMatchOffset]byte)(e.hist[offset:])
    93  			e.cur += offset
    94  			e.hist = e.hist[:maxMatchOffset]
    95  		}
    96  	}
    97  	s := int32(len(e.hist))
    98  	e.hist = append(e.hist, src...)
    99  	return s
   100  }
   101  
   102  type tableEntryPrev struct {
   103  	Cur  tableEntry
   104  	Prev tableEntry
   105  }
   106  
   107  // hash7 returns the hash of the lowest 7 bytes of u to fit in a hash table with h bits.
   108  // Preferably h should be a constant and should always be <64.
   109  func hash7(u uint64, h uint8) uint32 {
   110  	return uint32(((u << (64 - 56)) * prime7bytes) >> ((64 - h) & reg8SizeMask64))
   111  }
   112  
   113  // hashLen returns a hash of the lowest mls bytes of with length output bits.
   114  // mls must be >=3 and <=8. Any other value will return hash for 4 bytes.
   115  // length should always be < 32.
   116  // Preferably length and mls should be a constant for inlining.
   117  func hashLen(u uint64, length, mls uint8) uint32 {
   118  	switch mls {
   119  	case 3:
   120  		return (uint32(u<<8) * prime3bytes) >> (32 - length)
   121  	case 5:
   122  		return uint32(((u << (64 - 40)) * prime5bytes) >> (64 - length))
   123  	case 6:
   124  		return uint32(((u << (64 - 48)) * prime6bytes) >> (64 - length))
   125  	case 7:
   126  		return uint32(((u << (64 - 56)) * prime7bytes) >> (64 - length))
   127  	case 8:
   128  		return uint32((u * prime8bytes) >> (64 - length))
   129  	default:
   130  		return (uint32(u) * prime4bytes) >> (32 - length)
   131  	}
   132  }
   133  
   134  // matchlen will return the match length between offsets and t in src.
   135  // The maximum length returned is maxMatchLength - 4.
   136  // It is assumed that s > t, that t >=0 and s < len(src).
   137  func (e *fastGen) matchlen(s, t int32, src []byte) int32 {
   138  	if debugDecode {
   139  		if t >= s {
   140  			panic(fmt.Sprint("t >=s:", t, s))
   141  		}
   142  		if int(s) >= len(src) {
   143  			panic(fmt.Sprint("s >= len(src):", s, len(src)))
   144  		}
   145  		if t < 0 {
   146  			panic(fmt.Sprint("t < 0:", t))
   147  		}
   148  		if s-t > maxMatchOffset {
   149  			panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
   150  		}
   151  	}
   152  	s1 := int(s) + maxMatchLength - 4
   153  	if s1 > len(src) {
   154  		s1 = len(src)
   155  	}
   156  
   157  	// Extend the match to be as long as possible.
   158  	return int32(matchLen(src[s:s1], src[t:]))
   159  }
   160  
   161  // matchlenLong will return the match length between offsets and t in src.
   162  // It is assumed that s > t, that t >=0 and s < len(src).
   163  func (e *fastGen) matchlenLong(s, t int32, src []byte) int32 {
   164  	if debugDeflate {
   165  		if t >= s {
   166  			panic(fmt.Sprint("t >=s:", t, s))
   167  		}
   168  		if int(s) >= len(src) {
   169  			panic(fmt.Sprint("s >= len(src):", s, len(src)))
   170  		}
   171  		if t < 0 {
   172  			panic(fmt.Sprint("t < 0:", t))
   173  		}
   174  		if s-t > maxMatchOffset {
   175  			panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
   176  		}
   177  	}
   178  	// Extend the match to be as long as possible.
   179  	return int32(matchLen(src[s:], src[t:]))
   180  }
   181  
   182  // Reset the encoding table.
   183  func (e *fastGen) Reset() {
   184  	if cap(e.hist) < allocHistory {
   185  		e.hist = make([]byte, 0, allocHistory)
   186  	}
   187  	// We offset current position so everything will be out of reach.
   188  	// If we are above the buffer reset it will be cleared anyway since len(hist) == 0.
   189  	if e.cur <= bufferReset {
   190  		e.cur += maxMatchOffset + int32(len(e.hist))
   191  	}
   192  	e.hist = e.hist[:0]
   193  }
   194
View as plain text