123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254 |
- // Copyright 2011 The Snappy-Go Authors. All rights reserved.
- // Modified for deflate by Klaus Post (c) 2015.
- // Use of this source code is governed by a BSD-style
- // license that can be found in the LICENSE file.
- package flate
- import (
- "fmt"
- "math/bits"
- )
- type fastEnc interface {
- Encode(dst *tokens, src []byte)
- Reset()
- }
- func newFastEnc(level int) fastEnc {
- switch level {
- case 1:
- return &fastEncL1{fastGen: fastGen{cur: maxStoreBlockSize}}
- case 2:
- return &fastEncL2{fastGen: fastGen{cur: maxStoreBlockSize}}
- case 3:
- return &fastEncL3{fastGen: fastGen{cur: maxStoreBlockSize}}
- case 4:
- return &fastEncL4{fastGen: fastGen{cur: maxStoreBlockSize}}
- case 5:
- return &fastEncL5{fastGen: fastGen{cur: maxStoreBlockSize}}
- case 6:
- return &fastEncL6{fastGen: fastGen{cur: maxStoreBlockSize}}
- default:
- panic("invalid level specified")
- }
- }
- const (
- tableBits = 15 // Bits used in the table
- tableSize = 1 << tableBits // Size of the table
- tableShift = 32 - tableBits // Right-shift to get the tableBits most significant bits of a uint32.
- baseMatchOffset = 1 // The smallest match offset
- baseMatchLength = 3 // The smallest match length per the RFC section 3.2.5
- maxMatchOffset = 1 << 15 // The largest match offset
- bTableBits = 17 // Bits used in the big tables
- bTableSize = 1 << bTableBits // Size of the table
- allocHistory = maxStoreBlockSize * 10 // Size to preallocate for history.
- bufferReset = (1 << 31) - allocHistory - maxStoreBlockSize - 1 // Reset the buffer offset when reaching this.
- )
- const (
- prime3bytes = 506832829
- prime4bytes = 2654435761
- prime5bytes = 889523592379
- prime6bytes = 227718039650203
- prime7bytes = 58295818150454627
- prime8bytes = 0xcf1bbcdcb7a56463
- )
- func load32(b []byte, i int) uint32 {
- // Help the compiler eliminate bounds checks on the read so it can be done in a single read.
- b = b[i:]
- b = b[:4]
- return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
- }
- func load64(b []byte, i int) uint64 {
- // Help the compiler eliminate bounds checks on the read so it can be done in a single read.
- b = b[i:]
- b = b[:8]
- return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
- uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
- }
- func load3232(b []byte, i int32) uint32 {
- // Help the compiler eliminate bounds checks on the read so it can be done in a single read.
- b = b[i:]
- b = b[:4]
- return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
- }
- func load6432(b []byte, i int32) uint64 {
- // Help the compiler eliminate bounds checks on the read so it can be done in a single read.
- b = b[i:]
- b = b[:8]
- return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
- uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
- }
- func hash(u uint32) uint32 {
- return (u * 0x1e35a7bd) >> tableShift
- }
- type tableEntry struct {
- offset int32
- }
- // fastGen maintains the table for matches,
- // and the previous byte block for level 2.
- // This is the generic implementation.
- type fastGen struct {
- hist []byte
- cur int32
- }
- func (e *fastGen) addBlock(src []byte) int32 {
- // check if we have space already
- if len(e.hist)+len(src) > cap(e.hist) {
- if cap(e.hist) == 0 {
- e.hist = make([]byte, 0, allocHistory)
- } else {
- if cap(e.hist) < maxMatchOffset*2 {
- panic("unexpected buffer size")
- }
- // Move down
- offset := int32(len(e.hist)) - maxMatchOffset
- copy(e.hist[0:maxMatchOffset], e.hist[offset:])
- e.cur += offset
- e.hist = e.hist[:maxMatchOffset]
- }
- }
- s := int32(len(e.hist))
- e.hist = append(e.hist, src...)
- return s
- }
- // hash4 returns the hash of u to fit in a hash table with h bits.
- // Preferably h should be a constant and should always be <32.
- func hash4u(u uint32, h uint8) uint32 {
- return (u * prime4bytes) >> ((32 - h) & 31)
- }
- type tableEntryPrev struct {
- Cur tableEntry
- Prev tableEntry
- }
- // hash4x64 returns the hash of the lowest 4 bytes of u to fit in a hash table with h bits.
- // Preferably h should be a constant and should always be <32.
- func hash4x64(u uint64, h uint8) uint32 {
- return (uint32(u) * prime4bytes) >> ((32 - h) & 31)
- }
- // hash7 returns the hash of the lowest 7 bytes of u to fit in a hash table with h bits.
- // Preferably h should be a constant and should always be <64.
- func hash7(u uint64, h uint8) uint32 {
- return uint32(((u << (64 - 56)) * prime7bytes) >> ((64 - h) & 63))
- }
- // hash8 returns the hash of u to fit in a hash table with h bits.
- // Preferably h should be a constant and should always be <64.
- func hash8(u uint64, h uint8) uint32 {
- return uint32((u * prime8bytes) >> ((64 - h) & 63))
- }
- // hash6 returns the hash of the lowest 6 bytes of u to fit in a hash table with h bits.
- // Preferably h should be a constant and should always be <64.
- func hash6(u uint64, h uint8) uint32 {
- return uint32(((u << (64 - 48)) * prime6bytes) >> ((64 - h) & 63))
- }
- // matchlen will return the match length between offsets and t in src.
- // The maximum length returned is maxMatchLength - 4.
- // It is assumed that s > t, that t >=0 and s < len(src).
- func (e *fastGen) matchlen(s, t int32, src []byte) int32 {
- if debugDecode {
- if t >= s {
- panic(fmt.Sprint("t >=s:", t, s))
- }
- if int(s) >= len(src) {
- panic(fmt.Sprint("s >= len(src):", s, len(src)))
- }
- if t < 0 {
- panic(fmt.Sprint("t < 0:", t))
- }
- if s-t > maxMatchOffset {
- panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
- }
- }
- s1 := int(s) + maxMatchLength - 4
- if s1 > len(src) {
- s1 = len(src)
- }
- // Extend the match to be as long as possible.
- return int32(matchLen(src[s:s1], src[t:]))
- }
- // matchlenLong will return the match length between offsets and t in src.
- // It is assumed that s > t, that t >=0 and s < len(src).
- func (e *fastGen) matchlenLong(s, t int32, src []byte) int32 {
- if debugDecode {
- if t >= s {
- panic(fmt.Sprint("t >=s:", t, s))
- }
- if int(s) >= len(src) {
- panic(fmt.Sprint("s >= len(src):", s, len(src)))
- }
- if t < 0 {
- panic(fmt.Sprint("t < 0:", t))
- }
- if s-t > maxMatchOffset {
- panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
- }
- }
- // Extend the match to be as long as possible.
- return int32(matchLen(src[s:], src[t:]))
- }
- // Reset the encoding table.
- func (e *fastGen) Reset() {
- if cap(e.hist) < allocHistory {
- e.hist = make([]byte, 0, allocHistory)
- }
- // We offset current position so everything will be out of reach.
- // If we are above the buffer reset it will be cleared anyway since len(hist) == 0.
- if e.cur <= bufferReset {
- e.cur += maxMatchOffset + int32(len(e.hist))
- }
- e.hist = e.hist[:0]
- }
- // matchLen returns the maximum length.
- // 'a' must be the shortest of the two.
- func matchLen(a, b []byte) int {
- b = b[:len(a)]
- var checked int
- if len(a) > 4 {
- // Try 4 bytes first
- if diff := load32(a, 0) ^ load32(b, 0); diff != 0 {
- return bits.TrailingZeros32(diff) >> 3
- }
- // Switch to 8 byte matching.
- checked = 4
- a = a[4:]
- b = b[4:]
- for len(a) >= 8 {
- b = b[:len(a)]
- if diff := load64(a, 0) ^ load64(b, 0); diff != 0 {
- return checked + (bits.TrailingZeros64(diff) >> 3)
- }
- checked += 8
- a = a[8:]
- b = b[8:]
- }
- }
- b = b[:len(a)]
- for i := range a {
- if a[i] != b[i] {
- return int(i) + checked
- }
- }
- return len(a) + checked
- }
|