1 // 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<<lengthShift - 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<<lengthShift + xoffset) 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 } 103
