1 /* 2 * Copyright (c) 2014, 2017, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package jdk.incubator.http.internal.hpack; 26 27 import jdk.internal.vm.annotation.Stable; 28 29 import java.io.IOException; 30 import java.io.UncheckedIOException; 31 import java.net.ProtocolException; 32 import java.nio.ByteBuffer; 33 34 import static java.lang.String.format; 35 import static java.util.Objects.requireNonNull; 36 37 /** 38 * Decodes headers from their binary representation. 39 * 40 * <p>Typical lifecycle looks like this: 41 * 42 * <p> {@link #Decoder(int) new Decoder} 43 * ({@link #setMaxCapacity(int) setMaxCapacity}? 44 * {@link #decode(ByteBuffer, boolean, DecodingCallback) decode})* 45 * 46 * @apiNote 47 * 48 * <p> The design intentions behind Decoder were to facilitate flexible and 49 * incremental style of processing. 50 * 51 * <p> {@code Decoder} does not require a complete header block in a single 52 * {@code ByteBuffer}. The header block can be spread across many buffers of any 53 * size and decoded one-by-one the way it makes most sense for the user. This 54 * way also allows not to limit the size of the header block. 55 * 56 * <p> Headers are delivered to the {@linkplain DecodingCallback callback} as 57 * soon as they become decoded. Using the callback also gives the user a freedom 58 * to decide how headers are processed. The callback does not limit the number 59 * of headers decoded during single decoding operation. 60 * 61 * @since 9 62 */ 63 public final class Decoder { 64 65 @Stable 66 private static final State[] states = new State[256]; 67 68 static { 69 // To be able to do a quick lookup, each of 256 possibilities are mapped 70 // to corresponding states. 71 // 72 // We can safely do this since patterns 1, 01, 001, 0001, 0000 are 73 // Huffman prefixes and therefore are inherently not ambiguous. 74 // 75 // I do it mainly for better debugging (to not go each time step by step 76 // through if...else tree). As for performance win for the decoding, I 77 // believe is negligible. 78 for (int i = 0; i < states.length; i++) { 79 if ((i & 0b1000_0000) == 0b1000_0000) { 80 states[i] = State.INDEXED; 81 } else if ((i & 0b1100_0000) == 0b0100_0000) { 82 states[i] = State.LITERAL_WITH_INDEXING; 83 } else if ((i & 0b1110_0000) == 0b0010_0000) { 84 states[i] = State.SIZE_UPDATE; 85 } else if ((i & 0b1111_0000) == 0b0001_0000) { 86 states[i] = State.LITERAL_NEVER_INDEXED; 87 } else if ((i & 0b1111_0000) == 0b0000_0000) { 88 states[i] = State.LITERAL; 89 } else { 90 throw new InternalError(String.valueOf(i)); 91 } 92 } 93 } 94 95 private final HeaderTable table; 96 97 private State state = State.READY; 98 private final IntegerReader integerReader; 99 private final StringReader stringReader; 100 private final StringBuilder name; 101 private final StringBuilder value; 102 private int intValue; 103 private boolean firstValueRead; 104 private boolean firstValueIndex; 105 private boolean nameHuffmanEncoded; 106 private boolean valueHuffmanEncoded; 107 private int capacity; 108 109 /** 110 * Constructs a {@code Decoder} with the specified initial capacity of the 111 * header table. 112 * 113 * <p> The value has to be agreed between decoder and encoder out-of-band, 114 * e.g. by a protocol that uses HPACK (see <a 115 * href="https://tools.ietf.org/html/rfc7541#section-4.2">4.2. Maximum Table 116 * Size</a>). 117 * 118 * @param capacity 119 * a non-negative integer 120 * 121 * @throws IllegalArgumentException 122 * if capacity is negative 123 */ 124 public Decoder(int capacity) { 125 setMaxCapacity(capacity); 126 table = new HeaderTable(capacity); 127 integerReader = new IntegerReader(); 128 stringReader = new StringReader(); 129 name = new StringBuilder(512); 130 value = new StringBuilder(1024); 131 } 132 133 /** 134 * Sets a maximum capacity of the header table. 135 * 136 * <p> The value has to be agreed between decoder and encoder out-of-band, 137 * e.g. by a protocol that uses HPACK (see <a 138 * href="https://tools.ietf.org/html/rfc7541#section-4.2">4.2. Maximum Table 139 * Size</a>). 140 * 141 * @param capacity 142 * a non-negative integer 143 * 144 * @throws IllegalArgumentException 145 * if capacity is negative 146 */ 147 public void setMaxCapacity(int capacity) { 148 if (capacity < 0) { 149 throw new IllegalArgumentException("capacity >= 0: " + capacity); 150 } 151 // FIXME: await capacity update if less than what was prior to it 152 this.capacity = capacity; 153 } 154 155 /** 156 * Decodes a header block from the given buffer to the given callback. 157 * 158 * <p> Suppose a header block is represented by a sequence of {@code 159 * ByteBuffer}s in the form of {@code Iterator<ByteBuffer>}. And the 160 * consumer of decoded headers is represented by the callback. Then to 161 * decode the header block, the following approach might be used: 162 * 163 * <pre>{@code 164 * while (buffers.hasNext()) { 165 * ByteBuffer input = buffers.next(); 166 * decoder.decode(input, callback, !buffers.hasNext()); 167 * } 168 * }</pre> 169 * 170 * <p> The decoder reads as much as possible of the header block from the 171 * given buffer, starting at the buffer's position, and increments its 172 * position to reflect the bytes read. The buffer's mark and limit will not 173 * be modified. 174 * 175 * <p> Once the method is invoked with {@code endOfHeaderBlock == true}, the 176 * current header block is deemed ended, and inconsistencies, if any, are 177 * reported immediately by throwing an {@code UncheckedIOException}. 178 * 179 * <p> Each callback method is called only after the implementation has 180 * processed the corresponding bytes. If the bytes revealed a decoding 181 * error, the callback method is not called. 182 * 183 * <p> In addition to exceptions thrown directly by the method, any 184 * exceptions thrown from the {@code callback} will bubble up. 185 * 186 * @apiNote The method asks for {@code endOfHeaderBlock} flag instead of 187 * returning it for two reasons. The first one is that the user of the 188 * decoder always knows which chunk is the last. The second one is to throw 189 * the most detailed exception possible, which might be useful for 190 * diagnosing issues. 191 * 192 * @implNote This implementation is not atomic in respect to decoding 193 * errors. In other words, if the decoding operation has thrown a decoding 194 * error, the decoder is no longer usable. 195 * 196 * @param headerBlock 197 * the chunk of the header block, may be empty 198 * @param endOfHeaderBlock 199 * true if the chunk is the final (or the only one) in the sequence 200 * 201 * @param consumer 202 * the callback 203 * @throws UncheckedIOException 204 * in case of a decoding error 205 * @throws NullPointerException 206 * if either headerBlock or consumer are null 207 */ 208 public void decode(ByteBuffer headerBlock, boolean endOfHeaderBlock, 209 DecodingCallback consumer) { 210 requireNonNull(headerBlock, "headerBlock"); 211 requireNonNull(consumer, "consumer"); 212 while (headerBlock.hasRemaining()) { 213 proceed(headerBlock, consumer); 214 } 215 if (endOfHeaderBlock && state != State.READY) { 216 throw new UncheckedIOException( 217 new ProtocolException("Unexpected end of header block")); 218 } 219 } 220 221 private void proceed(ByteBuffer input, DecodingCallback action) { 222 switch (state) { 223 case READY: 224 resumeReady(input); 225 break; 226 case INDEXED: 227 resumeIndexed(input, action); 228 break; 229 case LITERAL: 230 resumeLiteral(input, action); 231 break; 232 case LITERAL_WITH_INDEXING: 233 resumeLiteralWithIndexing(input, action); 234 break; 235 case LITERAL_NEVER_INDEXED: 236 resumeLiteralNeverIndexed(input, action); 237 break; 238 case SIZE_UPDATE: 239 resumeSizeUpdate(input, action); 240 break; 241 default: 242 throw new InternalError( 243 "Unexpected decoder state: " + String.valueOf(state)); 244 } 245 } 246 247 private void resumeReady(ByteBuffer input) { 248 int b = input.get(input.position()) & 0xff; // absolute read 249 State s = states[b]; 250 switch (s) { 251 case INDEXED: 252 integerReader.configure(7); 253 state = State.INDEXED; 254 firstValueIndex = true; 255 break; 256 case LITERAL: 257 state = State.LITERAL; 258 firstValueIndex = (b & 0b0000_1111) != 0; 259 if (firstValueIndex) { 260 integerReader.configure(4); 261 } 262 break; 263 case LITERAL_WITH_INDEXING: 264 state = State.LITERAL_WITH_INDEXING; 265 firstValueIndex = (b & 0b0011_1111) != 0; 266 if (firstValueIndex) { 267 integerReader.configure(6); 268 } 269 break; 270 case LITERAL_NEVER_INDEXED: 271 state = State.LITERAL_NEVER_INDEXED; 272 firstValueIndex = (b & 0b0000_1111) != 0; 273 if (firstValueIndex) { 274 integerReader.configure(4); 275 } 276 break; 277 case SIZE_UPDATE: 278 integerReader.configure(5); 279 state = State.SIZE_UPDATE; 280 firstValueIndex = true; 281 break; 282 default: 283 throw new InternalError(String.valueOf(s)); 284 } 285 if (!firstValueIndex) { 286 input.get(); // advance, next stop: "String Literal" 287 } 288 } 289 290 // 0 1 2 3 4 5 6 7 291 // +---+---+---+---+---+---+---+---+ 292 // | 1 | Index (7+) | 293 // +---+---------------------------+ 294 // 295 private void resumeIndexed(ByteBuffer input, DecodingCallback action) { 296 if (!integerReader.read(input)) { 297 return; 298 } 299 intValue = integerReader.get(); 300 integerReader.reset(); 301 try { 302 HeaderTable.HeaderField f = table.get(intValue); 303 action.onIndexed(intValue, f.name, f.value); 304 } finally { 305 state = State.READY; 306 } 307 } 308 309 // 0 1 2 3 4 5 6 7 310 // +---+---+---+---+---+---+---+---+ 311 // | 0 | 0 | 0 | 0 | Index (4+) | 312 // +---+---+-----------------------+ 313 // | H | Value Length (7+) | 314 // +---+---------------------------+ 315 // | Value String (Length octets) | 316 // +-------------------------------+ 317 // 318 // 0 1 2 3 4 5 6 7 319 // +---+---+---+---+---+---+---+---+ 320 // | 0 | 0 | 0 | 0 | 0 | 321 // +---+---+-----------------------+ 322 // | H | Name Length (7+) | 323 // +---+---------------------------+ 324 // | Name String (Length octets) | 325 // +---+---------------------------+ 326 // | H | Value Length (7+) | 327 // +---+---------------------------+ 328 // | Value String (Length octets) | 329 // +-------------------------------+ 330 // 331 private void resumeLiteral(ByteBuffer input, DecodingCallback action) { 332 if (!completeReading(input)) { 333 return; 334 } 335 try { 336 if (firstValueIndex) { 337 HeaderTable.HeaderField f = table.get(intValue); 338 action.onLiteral(intValue, f.name, value, valueHuffmanEncoded); 339 } else { 340 action.onLiteral(name, nameHuffmanEncoded, value, valueHuffmanEncoded); 341 } 342 } finally { 343 cleanUpAfterReading(); 344 } 345 } 346 347 // 348 // 0 1 2 3 4 5 6 7 349 // +---+---+---+---+---+---+---+---+ 350 // | 0 | 1 | Index (6+) | 351 // +---+---+-----------------------+ 352 // | H | Value Length (7+) | 353 // +---+---------------------------+ 354 // | Value String (Length octets) | 355 // +-------------------------------+ 356 // 357 // 0 1 2 3 4 5 6 7 358 // +---+---+---+---+---+---+---+---+ 359 // | 0 | 1 | 0 | 360 // +---+---+-----------------------+ 361 // | H | Name Length (7+) | 362 // +---+---------------------------+ 363 // | Name String (Length octets) | 364 // +---+---------------------------+ 365 // | H | Value Length (7+) | 366 // +---+---------------------------+ 367 // | Value String (Length octets) | 368 // +-------------------------------+ 369 // 370 private void resumeLiteralWithIndexing(ByteBuffer input, DecodingCallback action) { 371 if (!completeReading(input)) { 372 return; 373 } 374 try { 375 // 376 // 1. (name, value) will be stored in the table as strings 377 // 2. Most likely the callback will also create strings from them 378 // ------------------------------------------------------------------------ 379 // Let's create those string beforehand (and only once!) to benefit everyone 380 // 381 String n; 382 String v = value.toString(); 383 if (firstValueIndex) { 384 HeaderTable.HeaderField f = table.get(intValue); 385 n = f.name; 386 action.onLiteralWithIndexing(intValue, n, v, valueHuffmanEncoded); 387 } else { 388 n = name.toString(); 389 action.onLiteralWithIndexing(n, nameHuffmanEncoded, v, valueHuffmanEncoded); 390 } 391 table.put(n, v); 392 } catch (IllegalArgumentException | IllegalStateException e) { 393 throw new UncheckedIOException( 394 (IOException) new ProtocolException().initCause(e)); 395 } finally { 396 cleanUpAfterReading(); 397 } 398 } 399 400 // 0 1 2 3 4 5 6 7 401 // +---+---+---+---+---+---+---+---+ 402 // | 0 | 0 | 0 | 1 | Index (4+) | 403 // +---+---+-----------------------+ 404 // | H | Value Length (7+) | 405 // +---+---------------------------+ 406 // | Value String (Length octets) | 407 // +-------------------------------+ 408 // 409 // 0 1 2 3 4 5 6 7 410 // +---+---+---+---+---+---+---+---+ 411 // | 0 | 0 | 0 | 1 | 0 | 412 // +---+---+-----------------------+ 413 // | H | Name Length (7+) | 414 // +---+---------------------------+ 415 // | Name String (Length octets) | 416 // +---+---------------------------+ 417 // | H | Value Length (7+) | 418 // +---+---------------------------+ 419 // | Value String (Length octets) | 420 // +-------------------------------+ 421 // 422 private void resumeLiteralNeverIndexed(ByteBuffer input, DecodingCallback action) { 423 if (!completeReading(input)) { 424 return; 425 } 426 try { 427 if (firstValueIndex) { 428 HeaderTable.HeaderField f = table.get(intValue); 429 action.onLiteralNeverIndexed(intValue, f.name, value, valueHuffmanEncoded); 430 } else { 431 action.onLiteralNeverIndexed(name, nameHuffmanEncoded, value, valueHuffmanEncoded); 432 } 433 } finally { 434 cleanUpAfterReading(); 435 } 436 } 437 438 // 0 1 2 3 4 5 6 7 439 // +---+---+---+---+---+---+---+---+ 440 // | 0 | 0 | 1 | Max size (5+) | 441 // +---+---------------------------+ 442 // 443 private void resumeSizeUpdate(ByteBuffer input, DecodingCallback action) { 444 if (!integerReader.read(input)) { 445 return; 446 } 447 intValue = integerReader.get(); 448 assert intValue >= 0; 449 if (intValue > capacity) { 450 throw new UncheckedIOException(new ProtocolException( 451 format("Received capacity exceeds expected: " + 452 "capacity=%s, expected=%s", intValue, capacity))); 453 } 454 integerReader.reset(); 455 try { 456 action.onSizeUpdate(intValue); 457 table.setMaxSize(intValue); 458 } finally { 459 state = State.READY; 460 } 461 } 462 463 private boolean completeReading(ByteBuffer input) { 464 if (!firstValueRead) { 465 if (firstValueIndex) { 466 if (!integerReader.read(input)) { 467 return false; 468 } 469 intValue = integerReader.get(); 470 integerReader.reset(); 471 } else { 472 if (!stringReader.read(input, name)) { 473 return false; 474 } 475 nameHuffmanEncoded = stringReader.isHuffmanEncoded(); 476 stringReader.reset(); 477 } 478 firstValueRead = true; 479 return false; 480 } else { 481 if (!stringReader.read(input, value)) { 482 return false; 483 } 484 } 485 valueHuffmanEncoded = stringReader.isHuffmanEncoded(); 486 stringReader.reset(); 487 return true; 488 } 489 490 private void cleanUpAfterReading() { 491 name.setLength(0); 492 value.setLength(0); 493 firstValueRead = false; 494 state = State.READY; 495 } 496 497 private enum State { 498 READY, 499 INDEXED, 500 LITERAL_NEVER_INDEXED, 501 LITERAL, 502 LITERAL_WITH_INDEXING, 503 SIZE_UPDATE 504 } 505 506 HeaderTable getTable() { 507 return table; 508 } 509 }