1 /* 2 * Copyright (c) 2014, 2016, 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 java.io.IOException; 28 import java.io.UncheckedIOException; 29 import java.nio.ByteBuffer; 30 31 import static java.lang.String.format; 32 33 /** 34 * Huffman coding table. 35 * 36 * <p> Instances of this class are safe for use by multiple threads. 37 * 38 * @since 9 39 */ 40 public final class Huffman { 41 42 // TODO: check if reset is done in both reader and writer 43 44 static final class Reader { 45 46 private Node curr; // position in the trie 47 private int len; // length of the path from the root to 'curr' 48 private int p; // byte probe 49 50 { 51 reset(); 52 } 53 54 public void read(ByteBuffer source, Appendable destination, 55 boolean isLast) { 56 read(source, destination, true, isLast); 57 } 58 59 // Takes 'isLast' rather than returns whether the reading is done or 60 // not, for more informative exceptions. 61 void read(ByteBuffer source, Appendable destination, boolean reportEOS, 62 boolean isLast) { 63 64 Node c = curr; 65 int l = len; 66 /* 67 Since ByteBuffer is itself stateful, its position is 68 remembered here NOT as a part of Reader's state, 69 but to set it back in the case of a failure 70 */ 71 int pos = source.position(); 72 73 while (source.hasRemaining()) { 74 int d = source.get(); 75 for (; p != 0; p >>= 1) { 76 c = c.getChild(p & d); 77 l++; 78 if (c.isLeaf()) { 79 if (reportEOS && c.isEOSPath) { 80 throw new IllegalArgumentException("Encountered EOS"); 81 } 82 try { 83 destination.append(c.getChar()); 84 } catch (RuntimeException | Error e) { 85 source.position(pos); 86 throw e; 87 } catch (IOException e) { 88 source.position(pos); 89 throw new UncheckedIOException(e); 90 } 91 c = INSTANCE.root; 92 l = 0; 93 } 94 curr = c; 95 len = l; 96 } 97 resetProbe(); 98 pos++; 99 } 100 if (!isLast) { 101 return; // it's too early to jump to any conclusions, let's wait 102 } 103 if (c.isLeaf()) { 104 return; // it's perfectly ok, no extra padding bits 105 } 106 if (c.isEOSPath && len <= 7) { 107 return; // it's ok, some extra padding bits 108 } 109 if (c.isEOSPath) { 110 throw new IllegalArgumentException( 111 "Padding is too long (len=" + len + ") " + 112 "or unexpected end of data"); 113 } 114 throw new IllegalArgumentException( 115 "Not a EOS prefix padding or unexpected end of data"); 116 } 117 118 public void reset() { 119 curr = INSTANCE.root; 120 len = 0; 121 resetProbe(); 122 } 123 124 private void resetProbe() { 125 p = 0x80; 126 } 127 } 128 129 static final class Writer { 130 131 private int pos; // position in 'source' 132 private int avail = 8; // number of least significant bits available in 'curr' 133 private int curr; // next byte to put to the destination 134 private int rem; // number of least significant bits in 'code' yet to be processed 492 public int lengthOf(CharSequence value) { 493 return lengthOf(value, 0, value.length()); 494 } 495 496 /** 497 * Calculates the number of bytes required to represent a subsequence of the 498 * given {@code CharSequence} with the Huffman coding. 499 * 500 * @param value 501 * characters 502 * @param start 503 * the start index, inclusive 504 * @param end 505 * the end index, exclusive 506 * 507 * @return number of bytes 508 * 509 * @throws NullPointerException 510 * if the value is null 511 * @throws IndexOutOfBoundsException 512 * if any invocation of {@code value.charAt(i)}, where {@code start 513 * <= i < end} would throw an IndexOutOfBoundsException 514 */ 515 public int lengthOf(CharSequence value, int start, int end) { 516 int len = 0; 517 for (int i = start; i < end; i++) { 518 char c = value.charAt(i); 519 len += INSTANCE.codeOf(c).length; 520 } 521 // Integer division with ceiling, assumption: 522 assert (len / 8 + (len % 8 != 0 ? 1 : 0)) == (len + 7) / 8 : len; 523 return (len + 7) / 8; 524 } 525 526 private void addChar(int c, int code, int bitLength) { 527 addLeaf(c, code, bitLength, false); 528 codes[c] = new Code(code, bitLength); 529 } 530 531 private void addEOS(int c, int code, int bitLength) { 532 addLeaf(c, code, bitLength, true); 533 codes[c] = new Code(code, bitLength); | 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 java.io.IOException; 28 import java.nio.ByteBuffer; 29 30 import static java.lang.String.format; 31 32 /** 33 * Huffman coding table. 34 * 35 * <p> Instances of this class are safe for use by multiple threads. 36 * 37 * @since 9 38 */ 39 public final class Huffman { 40 41 // TODO: check if reset is done in both reader and writer 42 43 static final class Reader { 44 45 private Node curr; // position in the trie 46 private int len; // length of the path from the root to 'curr' 47 private int p; // byte probe 48 49 { 50 reset(); 51 } 52 53 public void read(ByteBuffer source, 54 Appendable destination, 55 boolean isLast) throws IOException { 56 read(source, destination, true, isLast); 57 } 58 59 // Takes 'isLast' rather than returns whether the reading is done or 60 // not, for more informative exceptions. 61 void read(ByteBuffer source, 62 Appendable destination, 63 boolean reportEOS, /* reportEOS is exposed for tests */ 64 boolean isLast) throws IOException { 65 Node c = curr; 66 int l = len; 67 /* 68 Since ByteBuffer is itself stateful, its position is 69 remembered here NOT as a part of Reader's state, 70 but to set it back in the case of a failure 71 */ 72 int pos = source.position(); 73 74 while (source.hasRemaining()) { 75 int d = source.get(); 76 for (; p != 0; p >>= 1) { 77 c = c.getChild(p & d); 78 l++; 79 if (c.isLeaf()) { 80 if (reportEOS && c.isEOSPath) { 81 throw new IOException("Encountered EOS"); 82 } 83 char ch; 84 try { 85 ch = c.getChar(); 86 } catch (IllegalStateException e) { 87 source.position(pos); // do we need this? 88 throw new IOException(e); 89 } 90 try { 91 destination.append(ch); 92 } catch (IOException e) { 93 source.position(pos); // do we need this? 94 throw e; 95 } 96 c = INSTANCE.root; 97 l = 0; 98 } 99 curr = c; 100 len = l; 101 } 102 resetProbe(); 103 pos++; 104 } 105 if (!isLast) { 106 return; // it's too early to jump to any conclusions, let's wait 107 } 108 if (c.isLeaf()) { 109 return; // it's perfectly ok, no extra padding bits 110 } 111 if (c.isEOSPath && len <= 7) { 112 return; // it's ok, some extra padding bits 113 } 114 if (c.isEOSPath) { 115 throw new IOException( 116 "Padding is too long (len=" + len + ") " + 117 "or unexpected end of data"); 118 } 119 throw new IOException( 120 "Not a EOS prefix padding or unexpected end of data"); 121 } 122 123 public void reset() { 124 curr = INSTANCE.root; 125 len = 0; 126 resetProbe(); 127 } 128 129 private void resetProbe() { 130 p = 0x80; 131 } 132 } 133 134 static final class Writer { 135 136 private int pos; // position in 'source' 137 private int avail = 8; // number of least significant bits available in 'curr' 138 private int curr; // next byte to put to the destination 139 private int rem; // number of least significant bits in 'code' yet to be processed 497 public int lengthOf(CharSequence value) { 498 return lengthOf(value, 0, value.length()); 499 } 500 501 /** 502 * Calculates the number of bytes required to represent a subsequence of the 503 * given {@code CharSequence} with the Huffman coding. 504 * 505 * @param value 506 * characters 507 * @param start 508 * the start index, inclusive 509 * @param end 510 * the end index, exclusive 511 * 512 * @return number of bytes 513 * 514 * @throws NullPointerException 515 * if the value is null 516 * @throws IndexOutOfBoundsException 517 * if any invocation of {@code value.charAt(i)}, where 518 * {@code start <= i < end} would throw an IndexOutOfBoundsException 519 */ 520 public int lengthOf(CharSequence value, int start, int end) { 521 int len = 0; 522 for (int i = start; i < end; i++) { 523 char c = value.charAt(i); 524 len += INSTANCE.codeOf(c).length; 525 } 526 // Integer division with ceiling, assumption: 527 assert (len / 8 + (len % 8 != 0 ? 1 : 0)) == (len + 7) / 8 : len; 528 return (len + 7) / 8; 529 } 530 531 private void addChar(int c, int code, int bitLength) { 532 addLeaf(c, code, bitLength, false); 533 codes[c] = new Code(code, bitLength); 534 } 535 536 private void addEOS(int c, int code, int bitLength) { 537 addLeaf(c, code, bitLength, true); 538 codes[c] = new Code(code, bitLength); |