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
5package flate
6
7const (
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]
20var 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
49var 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
68type token uint32
69
70// Convert a literal into a literal token.
71func literalToken(literal uint32) token { return token(literalType + literal) }
72
73// Convert a < xlength, xoffset > pair into a match token.
74func matchToken(xlength uint32, xoffset uint32) token {
75	return token(matchType + xlength<<lengthShift + xoffset)
76}
77
78// Returns the literal of a literal token.
79func (t token) literal() uint32 { return uint32(t - literalType) }
80
81// Returns the extra offset of a match token.
82func (t token) offset() uint32 { return uint32(t) & offsetMask }
83
84func (t token) length() uint32 { return uint32((t - matchType) >> lengthShift) }
85
86func lengthCode(len uint32) uint32 { return lengthCodes[len] }
87
88// Returns the offset code corresponding to a specific offset.
89func offsetCode(off uint32) uint32 {
90	if off < uint32(len(offsetCodes)) {
91		return offsetCodes[off]
92	}
93	if off>>7 < uint32(len(offsetCodes)) {
94		return offsetCodes[off>>7] + 14
95	}
96	return offsetCodes[off>>14] + 28
97}
98