cmd/bpa-operator/vendor/golang.org/x/net/http2/hpack/huffman.go

   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         rootHuffmanNode := getRootHuffmanNode()
  51         n := rootHuffmanNode
  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)
  56         for _, b := range v {
  57                 cur = cur<<8 | uint(b)
  58                 cbits += 8
  59                 sbits += 8
  60                 for cbits >= 8 {
  61                         idx := byte(cur >> (cbits - 8))
  62                         n = n.children[idx]
  63                         if n == nil {
  64                                 return ErrInvalidHuffman
  65                         }
  66                         if n.children == nil {
  67                                 if maxLen != 0 && buf.Len() == maxLen {
  68                                         return ErrStringLength
  69                                 }
  70                                 buf.WriteByte(n.sym)
  71                                 cbits -= n.codeLen
  72                                 n = rootHuffmanNode
  73                                 sbits = cbits
  74                         } else {
  75                                 cbits -= 8
  76                         }
  77                 }
  78         }
  79         for cbits > 0 {
  80                 n = n.children[byte(cur<<(8-cbits))]
  81                 if n == nil {
  82                         return ErrInvalidHuffman
  83                 }
  84                 if n.children != nil || n.codeLen > cbits {
  85                         break
  86                 }
  87                 if maxLen != 0 && buf.Len() == maxLen {
  88                         return ErrStringLength
  89                 }
  90                 buf.WriteByte(n.sym)
  91                 cbits -= n.codeLen
  92                 n = rootHuffmanNode
  93                 sbits = cbits
  94         }
  95         if sbits > 7 {
  96                 // Either there was an incomplete symbol, or overlong padding.
  97                 // Both are decoding errors per RFC 7541 section 5.2.
  98                 return ErrInvalidHuffman
  99         }
 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
 103         }
 104
 105         return nil
 106 }
 107
 108 type node struct {
 109         // children is non-nil for internal nodes
 110         children *[256]*node
 111
 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
 115 }
 116
 117 func newInternalNode() *node {
 118         return &node{children: new([256]*node)}
 119 }
 120
 121 var (
 122         buildRootOnce       sync.Once
 123         lazyRootHuffmanNode *node
 124 )
 125
 126 func getRootHuffmanNode() *node {
 127         buildRootOnce.Do(buildRootHuffmanNode)
 128         return lazyRootHuffmanNode
 129 }
 130
 131 func buildRootHuffmanNode() {
 132         if len(huffmanCodes) != 256 {
 133                 panic("unexpected size")
 134         }
 135         lazyRootHuffmanNode = newInternalNode()
 136         for i, code := range huffmanCodes {
 137                 addDecoderNode(byte(i), code, huffmanCodeLen[i])
 138         }
 139 }
 140
 141 func addDecoderNode(sym byte, code uint32, codeLen uint8) {
 142         cur := lazyRootHuffmanNode
 143         for codeLen > 8 {
 144                 codeLen -= 8
 145                 i := uint8(code >> codeLen)
 146                 if cur.children[i] == nil {
 147                         cur.children[i] = newInternalNode()
 148                 }
 149                 cur = cur.children[i]
 150         }
 151         shift := 8 - codeLen
 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}
 155         }
 156 }
 157
 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 {
 161         rembits := uint8(8)
 162
 163         for i := 0; i < len(s); i++ {
 164                 if rembits == 8 {
 165                         dst = append(dst, 0)
 166                 }
 167                 dst, rembits = appendByteToHuffmanCode(dst, rembits, s[i])
 168         }
 169
 170         if rembits < 8 {
 171                 // special EOS symbol
 172                 code := uint32(0x3fffffff)
 173                 nbits := uint8(30)
 174
 175                 t := uint8(code >> (nbits - rembits))
 176                 dst[len(dst)-1] |= t
 177         }
 178
 179         return dst
 180 }
 181
 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 {
 185         n := uint64(0)
 186         for i := 0; i < len(s); i++ {
 187                 n += uint64(huffmanCodeLen[s[i]])
 188         }
 189         return (n + 7) / 8
 190 }
 191
 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]
 199
 200         for {
 201                 if rembits > nbits {
 202                         t := uint8(code << (rembits - nbits))
 203                         dst[len(dst)-1] |= t
 204                         rembits -= nbits
 205                         break
 206                 }
 207
 208                 t := uint8(code >> (nbits - rembits))
 209                 dst[len(dst)-1] |= t
 210
 211                 nbits -= rembits
 212                 rembits = 8
 213
 214                 if nbits == 0 {
 215                         break
 216                 }
 217
 218                 dst = append(dst, 0)
 219         }
 220
 221         return dst, rembits
 222 }