View Javadoc
1   /*
2    * Copyright 2015 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  
17  /*
18   * Copyright 2014 Twitter, Inc.
19   *
20   * Licensed under the Apache License, Version 2.0 (the "License");
21   * you may not use this file except in compliance with the License.
22   * You may obtain a copy of the License at
23   *
24   *     http://www.apache.org/licenses/LICENSE-2.0
25   *
26   * Unless required by applicable law or agreed to in writing, software
27   * distributed under the License is distributed on an "AS IS" BASIS,
28   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
29   * See the License for the specific language governing permissions and
30   * limitations under the License.
31   */
32  package io.netty.handler.codec.http2;
33  
34  import io.netty.buffer.ByteBuf;
35  import io.netty.util.AsciiString;
36  import io.netty.util.ByteProcessor;
37  import io.netty.util.internal.ObjectUtil;
38  import io.netty.util.internal.ThrowableUtil;
39  
40  import static io.netty.handler.codec.http2.Http2Error.COMPRESSION_ERROR;
41  import static io.netty.handler.codec.http2.Http2Exception.connectionError;
42  
43  final class HpackHuffmanDecoder {
44  
45      private static final Http2Exception EOS_DECODED = ThrowableUtil.unknownStackTrace(
46              connectionError(COMPRESSION_ERROR, "HPACK - EOS Decoded"), HpackHuffmanDecoder.class, "decode(..)");
47      private static final Http2Exception INVALID_PADDING = ThrowableUtil.unknownStackTrace(
48              connectionError(COMPRESSION_ERROR, "HPACK - Invalid Padding"), HpackHuffmanDecoder.class, "decode(..)");
49  
50      private static final Node ROOT = buildTree(HpackUtil.HUFFMAN_CODES, HpackUtil.HUFFMAN_CODE_LENGTHS);
51  
52      private final DecoderProcessor processor;
53  
54      HpackHuffmanDecoder(int initialCapacity) {
55          processor = new DecoderProcessor(initialCapacity);
56      }
57  
58      /**
59       * Decompresses the given Huffman coded string literal.
60       *
61       * @param buf the string literal to be decoded
62       * @return the output stream for the compressed data
63       * @throws Http2Exception EOS Decoded
64       */
65      public AsciiString decode(ByteBuf buf, int length) throws Http2Exception {
66          processor.reset();
67          buf.forEachByte(buf.readerIndex(), length, processor);
68          buf.skipBytes(length);
69          return processor.end();
70      }
71  
72      private static final class Node {
73  
74          private final int symbol;      // terminal nodes have a symbol
75          private final int bits;        // number of bits matched by the node
76          private final Node[] children; // internal nodes have children
77  
78          /**
79           * Construct an internal node
80           */
81          Node() {
82              symbol = 0;
83              bits = 8;
84              children = new Node[256];
85          }
86  
87          /**
88           * Construct a terminal node
89           *
90           * @param symbol the symbol the node represents
91           * @param bits the number of bits matched by this node
92           */
93          Node(int symbol, int bits) {
94              assert bits > 0 && bits <= 8;
95              this.symbol = symbol;
96              this.bits = bits;
97              children = null;
98          }
99  
100         private boolean isTerminal() {
101             return children == null;
102         }
103     }
104 
105     private static Node buildTree(int[] codes, byte[] lengths) {
106         Node root = new Node();
107         for (int i = 0; i < codes.length; i++) {
108             insert(root, i, codes[i], lengths[i]);
109         }
110         return root;
111     }
112 
113     private static void insert(Node root, int symbol, int code, byte length) {
114         // traverse tree using the most significant bytes of code
115         Node current = root;
116         while (length > 8) {
117             if (current.isTerminal()) {
118                 throw new IllegalStateException("invalid Huffman code: prefix not unique");
119             }
120             length -= 8;
121             int i = (code >>> length) & 0xFF;
122             if (current.children[i] == null) {
123                 current.children[i] = new Node();
124             }
125             current = current.children[i];
126         }
127 
128         Node terminal = new Node(symbol, length);
129         int shift = 8 - length;
130         int start = (code << shift) & 0xFF;
131         int end = 1 << shift;
132         for (int i = start; i < start + end; i++) {
133             current.children[i] = terminal;
134         }
135     }
136 
137     private static final class DecoderProcessor implements ByteProcessor {
138         private final int initialCapacity;
139         private byte[] bytes;
140         private int index;
141         private Node node;
142         private int current;
143         private int currentBits;
144         private int symbolBits;
145 
146         DecoderProcessor(int initialCapacity) {
147             this.initialCapacity = ObjectUtil.checkPositive(initialCapacity, "initialCapacity");
148         }
149 
150         void reset() {
151             node = ROOT;
152             current = 0;
153             currentBits = 0;
154             symbolBits = 0;
155             bytes = new byte[initialCapacity];
156             index = 0;
157         }
158 
159         /*
160          * The idea here is to consume whole bytes at a time rather than individual bits. node
161          * represents the Huffman tree, with all bit patterns denormalized as 256 children. Each
162          * child represents the last 8 bits of the huffman code. The parents of each child each
163          * represent the successive 8 bit chunks that lead up to the last most part. 8 bit bytes
164          * from buf are used to traverse these tree until a terminal node is found.
165          *
166          * current is a bit buffer. The low order bits represent how much of the huffman code has
167          * not been used to traverse the tree. Thus, the high order bits are just garbage.
168          * currentBits represents how many of the low order bits of current are actually valid.
169          * currentBits will vary between 0 and 15.
170          *
171          * symbolBits is the number of bits of the symbol being decoded, *including* all those of
172          * the parent nodes. symbolBits tells how far down the tree we are. For example, when
173          * decoding the invalid sequence {0xff, 0xff}, currentBits will be 0, but symbolBits will be
174          * 16. This is used to know if buf ended early (before consuming a whole symbol) or if
175          * there is too much padding.
176          */
177         @Override
178         public boolean process(byte value) throws Http2Exception {
179             current = (current << 8) | (value & 0xFF);
180             currentBits += 8;
181             symbolBits += 8;
182             // While there are unconsumed bits in current, keep consuming symbols.
183             do {
184                 node = node.children[(current >>> (currentBits - 8)) & 0xFF];
185                 currentBits -= node.bits;
186                 if (node.isTerminal()) {
187                     if (node.symbol == HpackUtil.HUFFMAN_EOS) {
188                         throw EOS_DECODED;
189                     }
190                     append(node.symbol);
191                     node = ROOT;
192                     // Upon consuming a whole symbol, reset the symbol bits to the number of bits
193                     // left over in the byte.
194                     symbolBits = currentBits;
195                 }
196             } while (currentBits >= 8);
197             return true;
198         }
199 
200         AsciiString end() throws Http2Exception {
201             /*
202              * We have consumed all the bytes in buf, but haven't consumed all the symbols. We may be on
203              * a partial symbol, so consume until there is nothing left. This will loop at most 2 times.
204              */
205             while (currentBits > 0) {
206                 node = node.children[(current << (8 - currentBits)) & 0xFF];
207                 if (node.isTerminal() && node.bits <= currentBits) {
208                     if (node.symbol == HpackUtil.HUFFMAN_EOS) {
209                         throw EOS_DECODED;
210                     }
211                     currentBits -= node.bits;
212                     append(node.symbol);
213                     node = ROOT;
214                     symbolBits = currentBits;
215                 } else {
216                     break;
217                 }
218             }
219 
220             // Section 5.2. String Literal Representation
221             // A padding strictly longer than 7 bits MUST be treated as a decoding error.
222             // Padding not corresponding to the most significant bits of the code
223             // for the EOS symbol (0xFF) MUST be treated as a decoding error.
224             int mask = (1 << symbolBits) - 1;
225             if (symbolBits > 7 || (current & mask) != mask) {
226                 throw INVALID_PADDING;
227             }
228 
229             return new AsciiString(bytes, 0, index, false);
230         }
231 
232         private void append(int i) {
233             if (bytes.length == index) {
234                 // Choose an expanding strategy depending on how big the buffer already is.
235                 // 1024 was choosen as a good guess and we may be able to investigate more if there are better choices.
236                 // See also https://github.com/netty/netty/issues/6846
237                 final int newLength = bytes.length >= 1024 ? bytes.length + initialCapacity : bytes.length << 1;
238                 byte[] newBytes = new byte[newLength];
239                 System.arraycopy(bytes, 0, newBytes, 0, bytes.length);
240                 bytes = newBytes;
241             }
242             bytes[index++] = (byte) i;
243         }
244     }
245 }