diff options
Diffstat (limited to 'vendor/golang.org/x/net/http2/hpack/huffman.go')
-rw-r--r-- | vendor/golang.org/x/net/http2/hpack/huffman.go | 212 |
1 files changed, 212 insertions, 0 deletions
diff --git a/vendor/golang.org/x/net/http2/hpack/huffman.go b/vendor/golang.org/x/net/http2/hpack/huffman.go new file mode 100644 index 0000000..8850e39 --- /dev/null +++ b/vendor/golang.org/x/net/http2/hpack/huffman.go | |||
@@ -0,0 +1,212 @@ | |||
1 | // Copyright 2014 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 hpack | ||
6 | |||
7 | import ( | ||
8 | "bytes" | ||
9 | "errors" | ||
10 | "io" | ||
11 | "sync" | ||
12 | ) | ||
13 | |||
14 | var bufPool = sync.Pool{ | ||
15 | New: func() interface{} { return new(bytes.Buffer) }, | ||
16 | } | ||
17 | |||
18 | // HuffmanDecode decodes the string in v and writes the expanded | ||
19 | // result to w, returning the number of bytes written to w and the | ||
20 | // Write call's return value. At most one Write call is made. | ||
21 | func HuffmanDecode(w io.Writer, v []byte) (int, error) { | ||
22 | buf := bufPool.Get().(*bytes.Buffer) | ||
23 | buf.Reset() | ||
24 | defer bufPool.Put(buf) | ||
25 | if err := huffmanDecode(buf, 0, v); err != nil { | ||
26 | return 0, err | ||
27 | } | ||
28 | return w.Write(buf.Bytes()) | ||
29 | } | ||
30 | |||
31 | // HuffmanDecodeToString decodes the string in v. | ||
32 | func HuffmanDecodeToString(v []byte) (string, error) { | ||
33 | buf := bufPool.Get().(*bytes.Buffer) | ||
34 | buf.Reset() | ||
35 | defer bufPool.Put(buf) | ||
36 | if err := huffmanDecode(buf, 0, v); err != nil { | ||
37 | return "", err | ||
38 | } | ||
39 | return buf.String(), nil | ||
40 | } | ||
41 | |||
42 | // ErrInvalidHuffman is returned for errors found decoding | ||
43 | // Huffman-encoded strings. | ||
44 | var ErrInvalidHuffman = errors.New("hpack: invalid Huffman-encoded data") | ||
45 | |||
46 | // huffmanDecode decodes v to buf. | ||
47 | // If maxLen is greater than 0, attempts to write more to buf than | ||
48 | // maxLen bytes will return ErrStringLength. | ||
49 | func huffmanDecode(buf *bytes.Buffer, maxLen int, v []byte) error { | ||
50 | n := rootHuffmanNode | ||
51 | // cur is the bit buffer that has not been fed into n. | ||
52 | // cbits is the number of low order bits in cur that are valid. | ||
53 | // sbits is the number of bits of the symbol prefix being decoded. | ||
54 | cur, cbits, sbits := uint(0), uint8(0), uint8(0) | ||
55 | for _, b := range v { | ||
56 | cur = cur<<8 | uint(b) | ||
57 | cbits += 8 | ||
58 | sbits += 8 | ||
59 | for cbits >= 8 { | ||
60 | idx := byte(cur >> (cbits - 8)) | ||
61 | n = n.children[idx] | ||
62 | if n == nil { | ||
63 | return ErrInvalidHuffman | ||
64 | } | ||
65 | if n.children == nil { | ||
66 | if maxLen != 0 && buf.Len() == maxLen { | ||
67 | return ErrStringLength | ||
68 | } | ||
69 | buf.WriteByte(n.sym) | ||
70 | cbits -= n.codeLen | ||
71 | n = rootHuffmanNode | ||
72 | sbits = cbits | ||
73 | } else { | ||
74 | cbits -= 8 | ||
75 | } | ||
76 | } | ||
77 | } | ||
78 | for cbits > 0 { | ||
79 | n = n.children[byte(cur<<(8-cbits))] | ||
80 | if n == nil { | ||
81 | return ErrInvalidHuffman | ||
82 | } | ||
83 | if n.children != nil || n.codeLen > cbits { | ||
84 | break | ||
85 | } | ||
86 | if maxLen != 0 && buf.Len() == maxLen { | ||
87 | return ErrStringLength | ||
88 | } | ||
89 | buf.WriteByte(n.sym) | ||
90 | cbits -= n.codeLen | ||
91 | n = rootHuffmanNode | ||
92 | sbits = cbits | ||
93 | } | ||
94 | if sbits > 7 { | ||
95 | // Either there was an incomplete symbol, or overlong padding. | ||
96 | // Both are decoding errors per RFC 7541 section 5.2. | ||
97 | return ErrInvalidHuffman | ||
98 | } | ||
99 | if mask := uint(1<<cbits - 1); cur&mask != mask { | ||
100 | // Trailing bits must be a prefix of EOS per RFC 7541 section 5.2. | ||
101 | return ErrInvalidHuffman | ||
102 | } | ||
103 | |||
104 | return nil | ||
105 | } | ||
106 | |||
107 | type node struct { | ||
108 | // children is non-nil for internal nodes | ||
109 | children []*node | ||
110 | |||
111 | // The following are only valid if children is nil: | ||
112 | codeLen uint8 // number of bits that led to the output of sym | ||
113 | sym byte // output symbol | ||
114 | } | ||
115 | |||
116 | func newInternalNode() *node { | ||
117 | return &node{children: make([]*node, 256)} | ||
118 | } | ||
119 | |||
120 | var rootHuffmanNode = newInternalNode() | ||
121 | |||
122 | func init() { | ||
123 | if len(huffmanCodes) != 256 { | ||
124 | panic("unexpected size") | ||
125 | } | ||
126 | for i, code := range huffmanCodes { | ||
127 | addDecoderNode(byte(i), code, huffmanCodeLen[i]) | ||
128 | } | ||
129 | } | ||
130 | |||
131 | func addDecoderNode(sym byte, code uint32, codeLen uint8) { | ||
132 | cur := rootHuffmanNode | ||
133 | for codeLen > 8 { | ||
134 | codeLen -= 8 | ||
135 | i := uint8(code >> codeLen) | ||
136 | if cur.children[i] == nil { | ||
137 | cur.children[i] = newInternalNode() | ||
138 | } | ||
139 | cur = cur.children[i] | ||
140 | } | ||
141 | shift := 8 - codeLen | ||
142 | start, end := int(uint8(code<<shift)), int(1<<shift) | ||
143 | for i := start; i < start+end; i++ { | ||
144 | cur.children[i] = &node{sym: sym, codeLen: codeLen} | ||
145 | } | ||
146 | } | ||
147 | |||
148 | // AppendHuffmanString appends s, as encoded in Huffman codes, to dst | ||
149 | // and returns the extended buffer. | ||
150 | func AppendHuffmanString(dst []byte, s string) []byte { | ||
151 | rembits := uint8(8) | ||
152 | |||
153 | for i := 0; i < len(s); i++ { | ||
154 | if rembits == 8 { | ||
155 | dst = append(dst, 0) | ||
156 | } | ||
157 | dst, rembits = appendByteToHuffmanCode(dst, rembits, s[i]) | ||
158 | } | ||
159 | |||
160 | if rembits < 8 { | ||
161 | // special EOS symbol | ||
162 | code := uint32(0x3fffffff) | ||
163 | nbits := uint8(30) | ||
164 | |||
165 | t := uint8(code >> (nbits - rembits)) | ||
166 | dst[len(dst)-1] |= t | ||
167 | } | ||
168 | |||
169 | return dst | ||
170 | } | ||
171 | |||
172 | // HuffmanEncodeLength returns the number of bytes required to encode | ||
173 | // s in Huffman codes. The result is round up to byte boundary. | ||
174 | func HuffmanEncodeLength(s string) uint64 { | ||
175 | n := uint64(0) | ||
176 | for i := 0; i < len(s); i++ { | ||
177 | n += uint64(huffmanCodeLen[s[i]]) | ||
178 | } | ||
179 | return (n + 7) / 8 | ||
180 | } | ||
181 | |||
182 | // appendByteToHuffmanCode appends Huffman code for c to dst and | ||
183 | // returns the extended buffer and the remaining bits in the last | ||
184 | // element. The appending is not byte aligned and the remaining bits | ||
185 | // in the last element of dst is given in rembits. | ||
186 | func appendByteToHuffmanCode(dst []byte, rembits uint8, c byte) ([]byte, uint8) { | ||
187 | code := huffmanCodes[c] | ||
188 | nbits := huffmanCodeLen[c] | ||
189 | |||
190 | for { | ||
191 | if rembits > nbits { | ||
192 | t := uint8(code << (rembits - nbits)) | ||
193 | dst[len(dst)-1] |= t | ||
194 | rembits -= nbits | ||
195 | break | ||
196 | } | ||
197 | |||
198 | t := uint8(code >> (nbits - rembits)) | ||
199 | dst[len(dst)-1] |= t | ||
200 | |||
201 | nbits -= rembits | ||
202 | rembits = 8 | ||
203 | |||
204 | if nbits == 0 { | ||
205 | break | ||
206 | } | ||
207 | |||
208 | dst = append(dst, 0) | ||
209 | } | ||
210 | |||
211 | return dst, rembits | ||
212 | } | ||