jdk-sandbox: comparison src/java.net.http/share/classes/jdk/internal/net/http/hpack/QuickHuffman.java

equal deleted inserted replaced

-:818a23db260c
+:4254bed3c09d
 * questions.
 */
 package jdk.internal.net.http.hpack;
+import jdk.internal.net.http.hpack.HPACK.BufferUpdateConsumer;
 import java.io.IOException;
 import java.nio.ByteBuffer;
 import java.util.List;
 import java.util.Objects;
+import static jdk.internal.net.http.hpack.HPACK.bytesForBits;
 public final class QuickHuffman {
 /*
-* Huffman codes for encoding.
+* Mapping of characters to their code information. Code information
-*
+* consists of a code value and a code length. Both components are packed in
-* EOS will never be matched, since there is no symbol for it, thus no need
+* a single long as follows:
-* to store it in the array. Thus, the length of the array is 256, not 257.
-* Code information for each character is encoded as follows:
 *
 *     MSB                             LSB
 *     +----------------+----------------+
 *     |~code           |         length~|
 *     +----------------+----------------+
 *     |<----- 32 ----->|<----- 32 ----->|
 *     |<------------- 64 -------------->|
 *
-* The leftmost 32 bits hold the code value. This value is aligned left
+* The leftmost 32 bits hold the code value. This value is aligned left (or
-* (or MSB). The rightmost 32 bits hold the length of the code value.
+* MSB). The rightmost 32 bits hold the code length. This length is aligned
-* This length is aligned right (or LSB).
+* right (or LSB). Such structure is possible thanks to codes being up to 30
+* bits long and their lengths being up to 5 bits long (length = 5..30).
+* This allows both components to fit into long and, thus, better locality.
+*
+* Input strings never contain EOS. Thus there's no need to provide EOS
+* mapping. Hence, the length of the array is 256, not 257.
 */
 private static final long[] codes = new long[256];
 private static long codeValueOf(char c) {
 return codes[c] & 0xffffffff00000000L;
 return codes[c] & 0x00000000ffffffffL;
 }
 private static final int EOS_LENGTH = 30;
 private static final int EOS_LSB = 0x3fffffff;
-private static final long EOS_MSB = EOS_LSB << (64 - EOS_LENGTH);
+// EOS_LSB is casted to long before the shift, to allow long shift (6 bits)
+// instead of int shift (5 bits):
+private static final long EOS_MSB = ((long) EOS_LSB) << (64 - EOS_LENGTH);
 /*
-* Huffman codes for decoding.
+* Huffman trie.
 *
-* Root node contains 257 descendant nodes, including EOS.
+* The root node leads to 257 descendant leaf nodes, of which 256 nodes
+* correspond to characters and 1 node correspond to EOS.
 */
-private static final Node root;
+private static final Node root = buildTrie();
-static {
+private static Node buildTrie() {
 TemporaryNode tmpRoot = new TemporaryNode();
 addChar(tmpRoot,   0, 0x1ff8,     13);
 addChar(tmpRoot,   1, 0x7fffd8,   23);
 addChar(tmpRoot,   2, 0xfffffe2,  28);
 addChar(tmpRoot,   3, 0xfffffe3,  28);
 addChar(tmpRoot, 255, 0x3ffffee,  26);
 addEOS (tmpRoot, 256, EOS_LSB, EOS_LENGTH);
 // The difference in performance can always be checked by not using
 // the immutable trie:
-//     root = tmpRoot;
+//     return tmpRoot;
-root = ImmutableNode.copyOf(tmpRoot);
+return ImmutableNode.copyOf(tmpRoot);
 }
 private QuickHuffman() { }
 private static void addChar(Node root, int symbol, int code, int bitLength)
 }
 }
 static final class Reader implements Huffman.Reader {
+private final BufferUpdateConsumer UPDATER =
+(buf, bufLen) -> {
+buffer = buf;
+bufferLen = bufLen;
+};
 private Node curr = root;  // current position in the trie
 private long buffer;       // bits left from the previous match (aligned to the left, or MSB)
 private int bufferLen;     // number of bits in the buffer
 private int len;           // length (in bits) of path to curr
 private boolean done;
 @Override
 public void read(ByteBuffer source,
 Appendable destination,
 boolean isLast) throws IOException
 {
-read(source, destination, true, isLast);
-}
-@Override
-public void reset() {
-curr = root;
-len = 0;
-buffer = 0;
-bufferLen = 0;
-done = false;
-}
-@SuppressWarnings("fallthrough")
-void read(ByteBuffer source,
-Appendable destination,
-boolean reportEOS, /* reportEOS is exposed for tests */
-boolean isLast) throws IOException
-{
 while (!done) {
-// read as much as possible (up to 8 bytes)
 int remaining = source.remaining();
-int nBytes = Math.min((64 - bufferLen) >> 3, remaining);
+int nBytes = HPACK.read(source, buffer, bufferLen, UPDATER);
-switch (nBytes) {
-case 0:
-break;
-case 3:
-readByte(source);
-case 2:
-readByte(source);
-case 1:
-readByte(source);
-break;
-case 7:
-readByte(source);
-case 6:
-readByte(source);
-case 5:
-readByte(source);
-case 4:
-readInt(source);
-break;
-case 8:
-readLong(source);
-break;
-default:
-throw new InternalError(String.valueOf(nBytes));
-}
 // write as much as possible
 while (true) {
 if (bufferLen < 8) {
 if (nBytes < remaining) { // read again
 break;
 } else if (!isLast) { // exit the method to accept more input
 return;
 } else if (bufferLen > 0) { // no more data is expected, pad
 // (this padding may be done more than once)
 buffer |= ((0xff00000000000000L >>> bufferLen)
 & 0xff00000000000000L);
 // do not update bufferLen, since all those ones are
 // synthetic and are appended merely for the sake of
 // lookup
 if (node.isLeaf()) {
 if (node.getLength() > bufferLen) { // matched more than we actually could (because of padding)
 throw new IOException(
 "Not a EOS prefix padding or unexpected end of data");
 }
-if (reportEOS && node.isEOSPath()) {
+if (node.isEOSPath()) {
 throw new IOException("Encountered EOS");
 }
 destination.append(node.getSymbol());
 curr = root;
 len = 0;
 + "or unexpected end of data");
 }
 }
 }
-private void readLong(ByteBuffer source) {
+@Override
-buffer = source.getLong();
+public void reset() {
-bufferLen = 64;
+curr = root;
-}
+len = 0;
+buffer = 0;
-private void readInt(ByteBuffer source) {
+bufferLen = 0;
-long b;
+done = false;
-b = source.getInt() & 0x00000000ffffffffL;
-buffer |= (b << (32 - bufferLen));
-bufferLen += 32;
-}
-private void readByte(ByteBuffer source) {
-long b = source.get() & 0x00000000000000ffL;
-buffer |= (b << (56 - bufferLen));
-bufferLen += 8;
 }
 }
 static final class Writer implements Huffman.Writer {
+private final BufferUpdateConsumer UPDATER =
+(buf, bufLen) -> {
+buffer = buf;
+bufferLen = bufLen;
+};
 private CharSequence source;
 private boolean padded;
 private int pos;
 private int end;
 this.end = end;
 this.source = input;
 return this;
 }
-@SuppressWarnings("fallthrough")
 @Override
 public boolean write(ByteBuffer destination) {
 while (true) {
-while (bufferLen < 32 && pos < end) {
+while (true) { // stuff codes into long
-char c = source.charAt(pos++);
+if (pos >= end) {
-buffer |= (codeValueOf(c) >>> bufferLen); // append
+break;
-bufferLen += codeLengthOf(c);
+}
+char c = source.charAt(pos);
+if (c > 255) {
+throw new IllegalArgumentException("char=" + ((int) c));
+}
+long len = codeLengthOf(c);
+if (bufferLen + len <= 64) {
+buffer |= (codeValueOf(c) >>> bufferLen); // append
+bufferLen += len;
+pos++;
+} else {
+break;
+}
 }
 if (bufferLen == 0) {
 return true;
 }
-if (pos >= end && !padded) { // no more chars, pad
+if (pos >= end && !padded) { // no more input chars are expected, pad
 padded = true;
-buffer |= (EOS_MSB >>> bufferLen);
+// A long shift to 64 will result in the same long, not
-bufferLen = bytesForBits(bufferLen) << 3;
+// necessarily 0L. In which case padding will be performed
+// incorrectly. If bufferLen is equal to 64, the shift (and
+// padding) in not performed.
+// (see https://docs.oracle.com/javase/specs/jls/se10/html/jls-15.html#jls-15.19)
+if (bufferLen != 64) {
+buffer |= (EOS_MSB >>> bufferLen);
+bufferLen = bytesForBits(bufferLen) << 3;
+}
 }
-// The number of bytes that can be written at once
+int nBytes = HPACK.write(buffer, bufferLen, UPDATER, destination);
-// (calculating in bytes, not bits, since
+if (nBytes == 0) {
-//  destination.remaining() * 8 might overflow)
+return false;
-int nBytes = Math.min(bytesForBits(bufferLen), destination.remaining()); // ceil?
-switch (nBytes) {
-case 0:
-return false;
-case 1:
-case 2:
-case 3:
-destination.put((byte) (buffer >>> 56));
-buffer <<= 8;
-bufferLen -= 8;
-break;
-default:
-destination.putInt((int) (buffer >>> 32));
-buffer <<= 32;
-bufferLen -= 32;
-break;
 }
 }
 }
 @Override
 len += codeLengthOf(c);
 }
 return bytesForBits(len);
 }
 }
-/*
-* Returns the number of bytes the given number of bits constitute.
-*/
-private static int bytesForBits(int n) {
-assert (n / 8 + (n % 8 != 0 ? 1 : 0)) == (n + 7) / 8
-&& (n + 7) / 8 == ((n + 7) >> 3) : n;
-return (n + 7) >> 3;
-}
 }

changeset 50681	4254bed3c09d
parent 49944	4690a2871b44
child 56795	03ece2518428