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.
14 var bufPool = sync.Pool{
15 New: func() interface{} { return new(bytes.Buffer) },
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)
24 defer bufPool.Put(buf)
25 if err := huffmanDecode(buf, 0, v); err != nil {
28 return w.Write(buf.Bytes())
31 // HuffmanDecodeToString decodes the string in v.
32 func HuffmanDecodeToString(v []byte) (string, error) {
33 buf := bufPool.Get().(*bytes.Buffer)
35 defer bufPool.Put(buf)
36 if err := huffmanDecode(buf, 0, v); err != nil {
39 return buf.String(), nil
42 // ErrInvalidHuffman is returned for errors found decoding
43 // Huffman-encoded strings.
44 var ErrInvalidHuffman = errors.New("hpack: invalid Huffman-encoded data")
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 rootHuffmanNode := getRootHuffmanNode()
52 // cur is the bit buffer that has not been fed into n.
53 // cbits is the number of low order bits in cur that are valid.
54 // sbits is the number of bits of the symbol prefix being decoded.
55 cur, cbits, sbits := uint(0), uint8(0), uint8(0)
57 cur = cur<<8 | uint(b)
61 idx := byte(cur >> (cbits - 8))
64 return ErrInvalidHuffman
66 if n.children == nil {
67 if maxLen != 0 && buf.Len() == maxLen {
68 return ErrStringLength
80 n = n.children[byte(cur<<(8-cbits))]
82 return ErrInvalidHuffman
84 if n.children != nil || n.codeLen > cbits {
87 if maxLen != 0 && buf.Len() == maxLen {
88 return ErrStringLength
96 // Either there was an incomplete symbol, or overlong padding.
97 // Both are decoding errors per RFC 7541 section 5.2.
98 return ErrInvalidHuffman
100 if mask := uint(1<<cbits - 1); cur&mask != mask {
101 // Trailing bits must be a prefix of EOS per RFC 7541 section 5.2.
102 return ErrInvalidHuffman
109 // children is non-nil for internal nodes
112 // The following are only valid if children is nil:
113 codeLen uint8 // number of bits that led to the output of sym
114 sym byte // output symbol
117 func newInternalNode() *node {
118 return &node{children: new([256]*node)}
122 buildRootOnce sync.Once
123 lazyRootHuffmanNode *node
126 func getRootHuffmanNode() *node {
127 buildRootOnce.Do(buildRootHuffmanNode)
128 return lazyRootHuffmanNode
131 func buildRootHuffmanNode() {
132 if len(huffmanCodes) != 256 {
133 panic("unexpected size")
135 lazyRootHuffmanNode = newInternalNode()
136 for i, code := range huffmanCodes {
137 addDecoderNode(byte(i), code, huffmanCodeLen[i])
141 func addDecoderNode(sym byte, code uint32, codeLen uint8) {
142 cur := lazyRootHuffmanNode
145 i := uint8(code >> codeLen)
146 if cur.children[i] == nil {
147 cur.children[i] = newInternalNode()
149 cur = cur.children[i]
152 start, end := int(uint8(code<<shift)), int(1<<shift)
153 for i := start; i < start+end; i++ {
154 cur.children[i] = &node{sym: sym, codeLen: codeLen}
158 // AppendHuffmanString appends s, as encoded in Huffman codes, to dst
159 // and returns the extended buffer.
160 func AppendHuffmanString(dst []byte, s string) []byte {
163 for i := 0; i < len(s); i++ {
167 dst, rembits = appendByteToHuffmanCode(dst, rembits, s[i])
171 // special EOS symbol
172 code := uint32(0x3fffffff)
175 t := uint8(code >> (nbits - rembits))
182 // HuffmanEncodeLength returns the number of bytes required to encode
183 // s in Huffman codes. The result is round up to byte boundary.
184 func HuffmanEncodeLength(s string) uint64 {
186 for i := 0; i < len(s); i++ {
187 n += uint64(huffmanCodeLen[s[i]])
192 // appendByteToHuffmanCode appends Huffman code for c to dst and
193 // returns the extended buffer and the remaining bits in the last
194 // element. The appending is not byte aligned and the remaining bits
195 // in the last element of dst is given in rembits.
196 func appendByteToHuffmanCode(dst []byte, rembits uint8, c byte) ([]byte, uint8) {
197 code := huffmanCodes[c]
198 nbits := huffmanCodeLen[c]
202 t := uint8(code << (rembits - nbits))
208 t := uint8(code >> (nbits - rembits))