| 1 |
747 |
jeremybenn |
// Copyright 2009 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 |
|
|
const (
|
| 8 |
|
|
// 2 bits: type 0 = literal 1=EOF 2=Match 3=Unused
|
| 9 |
|
|
// 8 bits: xlength = length - MIN_MATCH_LENGTH
|
| 10 |
|
|
// 22 bits xoffset = offset - MIN_OFFSET_SIZE, or literal
|
| 11 |
|
|
lengthShift = 22
|
| 12 |
|
|
offsetMask = 1<
|
| 13 |
|
|
typeMask = 3 << 30
|
| 14 |
|
|
literalType = 0 << 30
|
| 15 |
|
|
matchType = 1 << 30
|
| 16 |
|
|
)
|
| 17 |
|
|
|
| 18 |
|
|
// The length code for length X (MIN_MATCH_LENGTH <= X <= MAX_MATCH_LENGTH)
|
| 19 |
|
|
// is lengthCodes[length - MIN_MATCH_LENGTH]
|
| 20 |
|
|
var lengthCodes = [...]uint32{
|
| 21 |
|
|
0, 1, 2, 3, 4, 5, 6, 7, 8, 8,
|
| 22 |
|
|
9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
|
| 23 |
|
|
13, 13, 13, 13, 14, 14, 14, 14, 15, 15,
|
| 24 |
|
|
15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
|
| 25 |
|
|
17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
|
| 26 |
|
|
18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
|
| 27 |
|
|
19, 19, 19, 19, 20, 20, 20, 20, 20, 20,
|
| 28 |
|
|
20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
|
| 29 |
|
|
21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
|
| 30 |
|
|
21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
|
| 31 |
|
|
22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
|
| 32 |
|
|
22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
|
| 33 |
|
|
23, 23, 23, 23, 23, 23, 23, 23, 24, 24,
|
| 34 |
|
|
24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
|
| 35 |
|
|
24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
|
| 36 |
|
|
24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
|
| 37 |
|
|
25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
|
| 38 |
|
|
25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
|
| 39 |
|
|
25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
|
| 40 |
|
|
25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
|
| 41 |
|
|
26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
|
| 42 |
|
|
26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
|
| 43 |
|
|
26, 26, 26, 26, 27, 27, 27, 27, 27, 27,
|
| 44 |
|
|
27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
|
| 45 |
|
|
27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
|
| 46 |
|
|
27, 27, 27, 27, 27, 28,
|
| 47 |
|
|
}
|
| 48 |
|
|
|
| 49 |
|
|
var offsetCodes = [...]uint32{
|
| 50 |
|
|
0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
|
| 51 |
|
|
8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
|
| 52 |
|
|
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
|
| 53 |
|
|
11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
|
| 54 |
|
|
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
|
| 55 |
|
|
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
|
| 56 |
|
|
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
|
| 57 |
|
|
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
|
| 58 |
|
|
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
|
| 59 |
|
|
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
|
| 60 |
|
|
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
|
| 61 |
|
|
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
|
| 62 |
|
|
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
|
| 63 |
|
|
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
|
| 64 |
|
|
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
|
| 65 |
|
|
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
|
| 66 |
|
|
}
|
| 67 |
|
|
|
| 68 |
|
|
type token uint32
|
| 69 |
|
|
|
| 70 |
|
|
// Convert a literal into a literal token.
|
| 71 |
|
|
func literalToken(literal uint32) token { return token(literalType + literal) }
|
| 72 |
|
|
|
| 73 |
|
|
// Convert a < xlength, xoffset > pair into a match token.
|
| 74 |
|
|
func matchToken(xlength uint32, xoffset uint32) token {
|
| 75 |
|
|
return token(matchType + xlength<
|
| 76 |
|
|
}
|
| 77 |
|
|
|
| 78 |
|
|
// Returns the type of a token
|
| 79 |
|
|
func (t token) typ() uint32 { return uint32(t) & typeMask }
|
| 80 |
|
|
|
| 81 |
|
|
// Returns the literal of a literal token
|
| 82 |
|
|
func (t token) literal() uint32 { return uint32(t - literalType) }
|
| 83 |
|
|
|
| 84 |
|
|
// Returns the extra offset of a match token
|
| 85 |
|
|
func (t token) offset() uint32 { return uint32(t) & offsetMask }
|
| 86 |
|
|
|
| 87 |
|
|
func (t token) length() uint32 { return uint32((t - matchType) >> lengthShift) }
|
| 88 |
|
|
|
| 89 |
|
|
func lengthCode(len uint32) uint32 { return lengthCodes[len] }
|
| 90 |
|
|
|
| 91 |
|
|
// Returns the offset code corresponding to a specific offset
|
| 92 |
|
|
func offsetCode(off uint32) uint32 {
|
| 93 |
|
|
const n = uint32(len(offsetCodes))
|
| 94 |
|
|
switch {
|
| 95 |
|
|
case off < n:
|
| 96 |
|
|
return offsetCodes[off]
|
| 97 |
|
|
case off>>7 < n:
|
| 98 |
|
|
return offsetCodes[off>>7] + 14
|
| 99 |
|
|
default:
|
| 100 |
|
|
return offsetCodes[off>>14] + 28
|
| 101 |
|
|
}
|
| 102 |
|
|
panic("unreachable")
|
| 103 |
|
|
}
|
