You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@tomcat.apache.org by re...@apache.org on 2015/03/20 19:47:04 UTC
svn commit: r1668116 - in /tomcat/trunk: java/org/apache/coyote/http2/
test/org/apache/coyote/http2/ webapps/docs/
Author: remm
Date: Fri Mar 20 18:47:03 2015
New Revision: 1668116
URL: http://svn.apache.org/r1668116
Log:
57732: Add encoder/decoder module to support the HPACK specification ( http://http2.github.io/http2-spec/compression.html ).
Code contributed by Stuart Douglas, with some adaptations to Tomcat.
Added:
tomcat/trunk/java/org/apache/coyote/http2/
tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java (with props)
tomcat/trunk/java/org/apache/coyote/http2/Hpack.java (with props)
tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java (with props)
tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java (with props)
tomcat/trunk/java/org/apache/coyote/http2/HpackException.java (with props)
tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties (with props)
tomcat/trunk/test/org/apache/coyote/http2/
tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java (with props)
Modified:
tomcat/trunk/webapps/docs/changelog.xml
Added: tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java
URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java?rev=1668116&view=auto
==============================================================================
--- tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java (added)
+++ tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java Fri Mar 20 18:47:03 2015
@@ -0,0 +1,561 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.coyote.http2;
+
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Set;
+
+import org.apache.tomcat.util.res.StringManager;
+
+public class HPackHuffman {
+
+ protected static final StringManager sm = StringManager.getManager(HPackHuffman.class);
+
+ private static final HuffmanCode[] HUFFMAN_CODES;
+
+ /**
+ * array based tree representation of a huffman code.
+ * <p/>
+ * the high two bytes corresponds to the tree node if the bit is set, and the low two bytes for if it is clear
+ * if the high bit is set it is a terminal node, otherwise it contains the next node position.
+ */
+ private static final int[] DECODING_TABLE;
+
+ private static final int LOW_TERMINAL_BIT = (0b10000000) << 8;
+ private static final int HIGH_TERMINAL_BIT = (0b10000000) << 24;
+ private static final int LOW_MASK = 0b0111111111111111;
+
+
+ static {
+
+ HuffmanCode[] codes = new HuffmanCode[257];
+
+ codes[0] = new HuffmanCode(0x1ff8, 13);
+ codes[1] = new HuffmanCode(0x7fffd8, 23);
+ codes[2] = new HuffmanCode(0xfffffe2, 28);
+ codes[3] = new HuffmanCode(0xfffffe3, 28);
+ codes[4] = new HuffmanCode(0xfffffe4, 28);
+ codes[5] = new HuffmanCode(0xfffffe5, 28);
+ codes[6] = new HuffmanCode(0xfffffe6, 28);
+ codes[7] = new HuffmanCode(0xfffffe7, 28);
+ codes[8] = new HuffmanCode(0xfffffe8, 28);
+ codes[9] = new HuffmanCode(0xffffea, 24);
+ codes[10] = new HuffmanCode(0x3ffffffc, 30);
+ codes[11] = new HuffmanCode(0xfffffe9, 28);
+ codes[12] = new HuffmanCode(0xfffffea, 28);
+ codes[13] = new HuffmanCode(0x3ffffffd, 30);
+ codes[14] = new HuffmanCode(0xfffffeb, 28);
+ codes[15] = new HuffmanCode(0xfffffec, 28);
+ codes[16] = new HuffmanCode(0xfffffed, 28);
+ codes[17] = new HuffmanCode(0xfffffee, 28);
+ codes[18] = new HuffmanCode(0xfffffef, 28);
+ codes[19] = new HuffmanCode(0xffffff0, 28);
+ codes[20] = new HuffmanCode(0xffffff1, 28);
+ codes[21] = new HuffmanCode(0xffffff2, 28);
+ codes[22] = new HuffmanCode(0x3ffffffe, 30);
+ codes[23] = new HuffmanCode(0xffffff3, 28);
+ codes[24] = new HuffmanCode(0xffffff4, 28);
+ codes[25] = new HuffmanCode(0xffffff5, 28);
+ codes[26] = new HuffmanCode(0xffffff6, 28);
+ codes[27] = new HuffmanCode(0xffffff7, 28);
+ codes[28] = new HuffmanCode(0xffffff8, 28);
+ codes[29] = new HuffmanCode(0xffffff9, 28);
+ codes[30] = new HuffmanCode(0xffffffa, 28);
+ codes[31] = new HuffmanCode(0xffffffb, 28);
+ codes[32] = new HuffmanCode(0x14, 6);
+ codes[33] = new HuffmanCode(0x3f8, 10);
+ codes[34] = new HuffmanCode(0x3f9, 10);
+ codes[35] = new HuffmanCode(0xffa, 12);
+ codes[36] = new HuffmanCode(0x1ff9, 13);
+ codes[37] = new HuffmanCode(0x15, 6);
+ codes[38] = new HuffmanCode(0xf8, 8);
+ codes[39] = new HuffmanCode(0x7fa, 11);
+ codes[40] = new HuffmanCode(0x3fa, 10);
+ codes[41] = new HuffmanCode(0x3fb, 10);
+ codes[42] = new HuffmanCode(0xf9, 8);
+ codes[43] = new HuffmanCode(0x7fb, 11);
+ codes[44] = new HuffmanCode(0xfa, 8);
+ codes[45] = new HuffmanCode(0x16, 6);
+ codes[46] = new HuffmanCode(0x17, 6);
+ codes[47] = new HuffmanCode(0x18, 6);
+ codes[48] = new HuffmanCode(0x0, 5);
+ codes[49] = new HuffmanCode(0x1, 5);
+ codes[50] = new HuffmanCode(0x2, 5);
+ codes[51] = new HuffmanCode(0x19, 6);
+ codes[52] = new HuffmanCode(0x1a, 6);
+ codes[53] = new HuffmanCode(0x1b, 6);
+ codes[54] = new HuffmanCode(0x1c, 6);
+ codes[55] = new HuffmanCode(0x1d, 6);
+ codes[56] = new HuffmanCode(0x1e, 6);
+ codes[57] = new HuffmanCode(0x1f, 6);
+ codes[58] = new HuffmanCode(0x5c, 7);
+ codes[59] = new HuffmanCode(0xfb, 8);
+ codes[60] = new HuffmanCode(0x7ffc, 15);
+ codes[61] = new HuffmanCode(0x20, 6);
+ codes[62] = new HuffmanCode(0xffb, 12);
+ codes[63] = new HuffmanCode(0x3fc, 10);
+ codes[64] = new HuffmanCode(0x1ffa, 13);
+ codes[65] = new HuffmanCode(0x21, 6);
+ codes[66] = new HuffmanCode(0x5d, 7);
+ codes[67] = new HuffmanCode(0x5e, 7);
+ codes[68] = new HuffmanCode(0x5f, 7);
+ codes[69] = new HuffmanCode(0x60, 7);
+ codes[70] = new HuffmanCode(0x61, 7);
+ codes[71] = new HuffmanCode(0x62, 7);
+ codes[72] = new HuffmanCode(0x63, 7);
+ codes[73] = new HuffmanCode(0x64, 7);
+ codes[74] = new HuffmanCode(0x65, 7);
+ codes[75] = new HuffmanCode(0x66, 7);
+ codes[76] = new HuffmanCode(0x67, 7);
+ codes[77] = new HuffmanCode(0x68, 7);
+ codes[78] = new HuffmanCode(0x69, 7);
+ codes[79] = new HuffmanCode(0x6a, 7);
+ codes[80] = new HuffmanCode(0x6b, 7);
+ codes[81] = new HuffmanCode(0x6c, 7);
+ codes[82] = new HuffmanCode(0x6d, 7);
+ codes[83] = new HuffmanCode(0x6e, 7);
+ codes[84] = new HuffmanCode(0x6f, 7);
+ codes[85] = new HuffmanCode(0x70, 7);
+ codes[86] = new HuffmanCode(0x71, 7);
+ codes[87] = new HuffmanCode(0x72, 7);
+ codes[88] = new HuffmanCode(0xfc, 8);
+ codes[89] = new HuffmanCode(0x73, 7);
+ codes[90] = new HuffmanCode(0xfd, 8);
+ codes[91] = new HuffmanCode(0x1ffb, 13);
+ codes[92] = new HuffmanCode(0x7fff0, 19);
+ codes[93] = new HuffmanCode(0x1ffc, 13);
+ codes[94] = new HuffmanCode(0x3ffc, 14);
+ codes[95] = new HuffmanCode(0x22, 6);
+ codes[96] = new HuffmanCode(0x7ffd, 15);
+ codes[97] = new HuffmanCode(0x3, 5);
+ codes[98] = new HuffmanCode(0x23, 6);
+ codes[99] = new HuffmanCode(0x4, 5);
+ codes[100] = new HuffmanCode(0x24, 6);
+ codes[101] = new HuffmanCode(0x5, 5);
+ codes[102] = new HuffmanCode(0x25, 6);
+ codes[103] = new HuffmanCode(0x26, 6);
+ codes[104] = new HuffmanCode(0x27, 6);
+ codes[105] = new HuffmanCode(0x6, 5);
+ codes[106] = new HuffmanCode(0x74, 7);
+ codes[107] = new HuffmanCode(0x75, 7);
+ codes[108] = new HuffmanCode(0x28, 6);
+ codes[109] = new HuffmanCode(0x29, 6);
+ codes[110] = new HuffmanCode(0x2a, 6);
+ codes[111] = new HuffmanCode(0x7, 5);
+ codes[112] = new HuffmanCode(0x2b, 6);
+ codes[113] = new HuffmanCode(0x76, 7);
+ codes[114] = new HuffmanCode(0x2c, 6);
+ codes[115] = new HuffmanCode(0x8, 5);
+ codes[116] = new HuffmanCode(0x9, 5);
+ codes[117] = new HuffmanCode(0x2d, 6);
+ codes[118] = new HuffmanCode(0x77, 7);
+ codes[119] = new HuffmanCode(0x78, 7);
+ codes[120] = new HuffmanCode(0x79, 7);
+ codes[121] = new HuffmanCode(0x7a, 7);
+ codes[122] = new HuffmanCode(0x7b, 7);
+ codes[123] = new HuffmanCode(0x7ffe, 15);
+ codes[124] = new HuffmanCode(0x7fc, 11);
+ codes[125] = new HuffmanCode(0x3ffd, 14);
+ codes[126] = new HuffmanCode(0x1ffd, 13);
+ codes[127] = new HuffmanCode(0xffffffc, 28);
+ codes[128] = new HuffmanCode(0xfffe6, 20);
+ codes[129] = new HuffmanCode(0x3fffd2, 22);
+ codes[130] = new HuffmanCode(0xfffe7, 20);
+ codes[131] = new HuffmanCode(0xfffe8, 20);
+ codes[132] = new HuffmanCode(0x3fffd3, 22);
+ codes[133] = new HuffmanCode(0x3fffd4, 22);
+ codes[134] = new HuffmanCode(0x3fffd5, 22);
+ codes[135] = new HuffmanCode(0x7fffd9, 23);
+ codes[136] = new HuffmanCode(0x3fffd6, 22);
+ codes[137] = new HuffmanCode(0x7fffda, 23);
+ codes[138] = new HuffmanCode(0x7fffdb, 23);
+ codes[139] = new HuffmanCode(0x7fffdc, 23);
+ codes[140] = new HuffmanCode(0x7fffdd, 23);
+ codes[141] = new HuffmanCode(0x7fffde, 23);
+ codes[142] = new HuffmanCode(0xffffeb, 24);
+ codes[143] = new HuffmanCode(0x7fffdf, 23);
+ codes[144] = new HuffmanCode(0xffffec, 24);
+ codes[145] = new HuffmanCode(0xffffed, 24);
+ codes[146] = new HuffmanCode(0x3fffd7, 22);
+ codes[147] = new HuffmanCode(0x7fffe0, 23);
+ codes[148] = new HuffmanCode(0xffffee, 24);
+ codes[149] = new HuffmanCode(0x7fffe1, 23);
+ codes[150] = new HuffmanCode(0x7fffe2, 23);
+ codes[151] = new HuffmanCode(0x7fffe3, 23);
+ codes[152] = new HuffmanCode(0x7fffe4, 23);
+ codes[153] = new HuffmanCode(0x1fffdc, 21);
+ codes[154] = new HuffmanCode(0x3fffd8, 22);
+ codes[155] = new HuffmanCode(0x7fffe5, 23);
+ codes[156] = new HuffmanCode(0x3fffd9, 22);
+ codes[157] = new HuffmanCode(0x7fffe6, 23);
+ codes[158] = new HuffmanCode(0x7fffe7, 23);
+ codes[159] = new HuffmanCode(0xffffef, 24);
+ codes[160] = new HuffmanCode(0x3fffda, 22);
+ codes[161] = new HuffmanCode(0x1fffdd, 21);
+ codes[162] = new HuffmanCode(0xfffe9, 20);
+ codes[163] = new HuffmanCode(0x3fffdb, 22);
+ codes[164] = new HuffmanCode(0x3fffdc, 22);
+ codes[165] = new HuffmanCode(0x7fffe8, 23);
+ codes[166] = new HuffmanCode(0x7fffe9, 23);
+ codes[167] = new HuffmanCode(0x1fffde, 21);
+ codes[168] = new HuffmanCode(0x7fffea, 23);
+ codes[169] = new HuffmanCode(0x3fffdd, 22);
+ codes[170] = new HuffmanCode(0x3fffde, 22);
+ codes[171] = new HuffmanCode(0xfffff0, 24);
+ codes[172] = new HuffmanCode(0x1fffdf, 21);
+ codes[173] = new HuffmanCode(0x3fffdf, 22);
+ codes[174] = new HuffmanCode(0x7fffeb, 23);
+ codes[175] = new HuffmanCode(0x7fffec, 23);
+ codes[176] = new HuffmanCode(0x1fffe0, 21);
+ codes[177] = new HuffmanCode(0x1fffe1, 21);
+ codes[178] = new HuffmanCode(0x3fffe0, 22);
+ codes[179] = new HuffmanCode(0x1fffe2, 21);
+ codes[180] = new HuffmanCode(0x7fffed, 23);
+ codes[181] = new HuffmanCode(0x3fffe1, 22);
+ codes[182] = new HuffmanCode(0x7fffee, 23);
+ codes[183] = new HuffmanCode(0x7fffef, 23);
+ codes[184] = new HuffmanCode(0xfffea, 20);
+ codes[185] = new HuffmanCode(0x3fffe2, 22);
+ codes[186] = new HuffmanCode(0x3fffe3, 22);
+ codes[187] = new HuffmanCode(0x3fffe4, 22);
+ codes[188] = new HuffmanCode(0x7ffff0, 23);
+ codes[189] = new HuffmanCode(0x3fffe5, 22);
+ codes[190] = new HuffmanCode(0x3fffe6, 22);
+ codes[191] = new HuffmanCode(0x7ffff1, 23);
+ codes[192] = new HuffmanCode(0x3ffffe0, 26);
+ codes[193] = new HuffmanCode(0x3ffffe1, 26);
+ codes[194] = new HuffmanCode(0xfffeb, 20);
+ codes[195] = new HuffmanCode(0x7fff1, 19);
+ codes[196] = new HuffmanCode(0x3fffe7, 22);
+ codes[197] = new HuffmanCode(0x7ffff2, 23);
+ codes[198] = new HuffmanCode(0x3fffe8, 22);
+ codes[199] = new HuffmanCode(0x1ffffec, 25);
+ codes[200] = new HuffmanCode(0x3ffffe2, 26);
+ codes[201] = new HuffmanCode(0x3ffffe3, 26);
+ codes[202] = new HuffmanCode(0x3ffffe4, 26);
+ codes[203] = new HuffmanCode(0x7ffffde, 27);
+ codes[204] = new HuffmanCode(0x7ffffdf, 27);
+ codes[205] = new HuffmanCode(0x3ffffe5, 26);
+ codes[206] = new HuffmanCode(0xfffff1, 24);
+ codes[207] = new HuffmanCode(0x1ffffed, 25);
+ codes[208] = new HuffmanCode(0x7fff2, 19);
+ codes[209] = new HuffmanCode(0x1fffe3, 21);
+ codes[210] = new HuffmanCode(0x3ffffe6, 26);
+ codes[211] = new HuffmanCode(0x7ffffe0, 27);
+ codes[212] = new HuffmanCode(0x7ffffe1, 27);
+ codes[213] = new HuffmanCode(0x3ffffe7, 26);
+ codes[214] = new HuffmanCode(0x7ffffe2, 27);
+ codes[215] = new HuffmanCode(0xfffff2, 24);
+ codes[216] = new HuffmanCode(0x1fffe4, 21);
+ codes[217] = new HuffmanCode(0x1fffe5, 21);
+ codes[218] = new HuffmanCode(0x3ffffe8, 26);
+ codes[219] = new HuffmanCode(0x3ffffe9, 26);
+ codes[220] = new HuffmanCode(0xffffffd, 28);
+ codes[221] = new HuffmanCode(0x7ffffe3, 27);
+ codes[222] = new HuffmanCode(0x7ffffe4, 27);
+ codes[223] = new HuffmanCode(0x7ffffe5, 27);
+ codes[224] = new HuffmanCode(0xfffec, 20);
+ codes[225] = new HuffmanCode(0xfffff3, 24);
+ codes[226] = new HuffmanCode(0xfffed, 20);
+ codes[227] = new HuffmanCode(0x1fffe6, 21);
+ codes[228] = new HuffmanCode(0x3fffe9, 22);
+ codes[229] = new HuffmanCode(0x1fffe7, 21);
+ codes[230] = new HuffmanCode(0x1fffe8, 21);
+ codes[231] = new HuffmanCode(0x7ffff3, 23);
+ codes[232] = new HuffmanCode(0x3fffea, 22);
+ codes[233] = new HuffmanCode(0x3fffeb, 22);
+ codes[234] = new HuffmanCode(0x1ffffee, 25);
+ codes[235] = new HuffmanCode(0x1ffffef, 25);
+ codes[236] = new HuffmanCode(0xfffff4, 24);
+ codes[237] = new HuffmanCode(0xfffff5, 24);
+ codes[238] = new HuffmanCode(0x3ffffea, 26);
+ codes[239] = new HuffmanCode(0x7ffff4, 23);
+ codes[240] = new HuffmanCode(0x3ffffeb, 26);
+ codes[241] = new HuffmanCode(0x7ffffe6, 27);
+ codes[242] = new HuffmanCode(0x3ffffec, 26);
+ codes[243] = new HuffmanCode(0x3ffffed, 26);
+ codes[244] = new HuffmanCode(0x7ffffe7, 27);
+ codes[245] = new HuffmanCode(0x7ffffe8, 27);
+ codes[246] = new HuffmanCode(0x7ffffe9, 27);
+ codes[247] = new HuffmanCode(0x7ffffea, 27);
+ codes[248] = new HuffmanCode(0x7ffffeb, 27);
+ codes[249] = new HuffmanCode(0xffffffe, 28);
+ codes[250] = new HuffmanCode(0x7ffffec, 27);
+ codes[251] = new HuffmanCode(0x7ffffed, 27);
+ codes[252] = new HuffmanCode(0x7ffffee, 27);
+ codes[253] = new HuffmanCode(0x7ffffef, 27);
+ codes[254] = new HuffmanCode(0x7fffff0, 27);
+ codes[255] = new HuffmanCode(0x3ffffee, 26);
+ codes[256] = new HuffmanCode(0x3fffffff, 30);
+ HUFFMAN_CODES = codes;
+
+ //lengths determined by experimentation, just set it to something large then see how large it actually ends up
+ int[] codingTree = new int[256];
+ //the current position in the tree
+ int pos = 0;
+ int allocated = 1; //the next position to allocate to
+ //map of the current state at a given position
+ //only used while building the tree
+ HuffmanCode[] currentCode = new HuffmanCode[256];
+ currentCode[0] = new HuffmanCode(0, 0);
+
+ final Set<HuffmanCode> allCodes = new HashSet<>();
+ allCodes.addAll(Arrays.asList(HUFFMAN_CODES));
+
+ while (!allCodes.isEmpty()) {
+ int length = currentCode[pos].length;
+ int code = currentCode[pos].value;
+
+ int newLength = length + 1;
+ HuffmanCode high = new HuffmanCode(code << 1 | 1, newLength);
+ HuffmanCode low = new HuffmanCode(code << 1, newLength);
+ int newVal = 0;
+ boolean highTerminal = allCodes.remove(high);
+ if (highTerminal) {
+ //bah, linear search
+ int i = 0;
+ for (i = 0; i < codes.length; ++i) {
+ if (codes[i].equals(high)) {
+ break;
+ }
+ }
+ newVal = LOW_TERMINAL_BIT | i;
+ } else {
+ int highPos = allocated++;
+ currentCode[highPos] = high;
+ newVal = highPos;
+ }
+ newVal <<= 16;
+ boolean lowTerminal = allCodes.remove(low);
+ if (lowTerminal) {
+ //bah, linear search
+ int i = 0;
+ for (i = 0; i < codes.length; ++i) {
+ if (codes[i].equals(low)) {
+ break;
+ }
+ }
+ newVal |= LOW_TERMINAL_BIT | i;
+ } else {
+ int lowPos = allocated++;
+ currentCode[lowPos] = low;
+ newVal |= lowPos;
+ }
+ codingTree[pos] = newVal;
+ pos++;
+ }
+ DECODING_TABLE = codingTree;
+ }
+
+ /**
+ * Decodes a huffman encoded string into the target StringBuilder. There must be enough space left in the buffer
+ * for this method to succeed.
+ *
+ * @param data The byte buffer
+ * @param length The data length
+ * @param target The target for the decompressed data
+ */
+ public static void decode(ByteBuffer data, int length, StringBuilder target) throws HpackException {
+ assert data.remaining() >= length;
+ int treePos = 0;
+ boolean eosBits = true;
+ for (int i = 0; i < length; ++i) {
+ byte b = data.get();
+ int bitPos = 7;
+ while (bitPos >= 0) {
+ int val = DECODING_TABLE[treePos];
+ if (((1 << bitPos) & b) == 0) {
+ eosBits = false;
+ //bit not set, we want the lower part of the tree
+ if ((val & LOW_TERMINAL_BIT) == 0) {
+ treePos = val & LOW_MASK;
+ } else {
+ target.append((char) (val & LOW_MASK));
+ treePos = 0;
+ eosBits = true;
+ }
+ } else {
+ //bit not set, we want the lower part of the tree
+ if ((val & HIGH_TERMINAL_BIT) == 0) {
+ treePos = (val >> 16) & LOW_MASK;
+ } else {
+ target.append((char) ((val >> 16) & LOW_MASK));
+ treePos = 0;
+ eosBits = true;
+ }
+ }
+ bitPos--;
+ }
+ }
+ if (!eosBits) {
+ throw new HpackException(sm.getString("hpackhuffman.huffmanEncodedHpackValueDidNotEndWithEOS"));
+ }
+ }
+
+
+ /**
+ * Encodes the given string into the buffer. If there is not enough space in the buffer, or the encoded
+ * version is bigger than the original it will return false and not modify the buffers position
+ *
+ * @param buffer The buffer to encode into
+ * @param toEncode The string to encode
+ * @param forceLowercase If the string should be encoded in lower case
+ * @return true if encoding succeeded
+ */
+ public static boolean encode(ByteBuffer buffer, String toEncode, boolean forceLowercase) {
+ if (buffer.remaining() <= toEncode.length()) {
+ return false;
+ }
+ int start = buffer.position();
+ //this sucks, but we need to put the length first
+ //and we don't really have any option but to calculate it in advance to make sure we have left enough room
+ //so we end up iterating twice
+ int length = 0;
+ for (int i = 0; i < toEncode.length(); ++i) {
+ byte c = (byte) toEncode.charAt(i);
+ if(forceLowercase) {
+ c = Hpack.toLower(c);
+ }
+ HuffmanCode code = HUFFMAN_CODES[c];
+ length += code.length;
+ }
+ int byteLength = length / 8 + (length % 8 == 0 ? 0 : 1);
+
+ buffer.put((byte) (1 << 7));
+ Hpack.encodeInteger(buffer, byteLength, 7);
+
+
+ int bytePos = 0;
+ byte currentBufferByte = 0;
+ for (int i = 0; i < toEncode.length(); ++i) {
+ byte c = (byte) toEncode.charAt(i);
+ if(forceLowercase) {
+ c = Hpack.toLower(c);
+ }
+ HuffmanCode code = HUFFMAN_CODES[c];
+ if (code.length + bytePos <= 8) {
+ //it fits in the current byte
+ currentBufferByte |= ((code.value & 0xFF) << 8 - (code.length + bytePos));
+ bytePos += code.length;
+ } else {
+ //it does not fit, it may need up to 4 bytes
+ int val = code.value;
+ int rem = code.length;
+ while (rem > 0) {
+ if (!buffer.hasRemaining()) {
+ buffer.position(start);
+ return false;
+ }
+ int remainingInByte = 8 - bytePos;
+ if (rem > remainingInByte) {
+ currentBufferByte |= (val >> (rem - remainingInByte));
+ } else {
+ currentBufferByte |= (val << (remainingInByte - rem));
+ }
+ if (rem > remainingInByte) {
+ buffer.put(currentBufferByte);
+ currentBufferByte = 0;
+ bytePos = 0;
+ } else {
+ bytePos = rem;
+ }
+ rem -= remainingInByte;
+ }
+ }
+ if (bytePos == 8) {
+ if (!buffer.hasRemaining()) {
+ buffer.position(start);
+ return false;
+ }
+ buffer.put(currentBufferByte);
+ currentBufferByte = 0;
+ bytePos = 0;
+ }
+ if (buffer.position() - start > toEncode.length()) {
+ //the encoded version is longer than the original
+ //just return false
+ buffer.position(start);
+ return false;
+ }
+ }
+ if (bytePos > 0) {
+ //add the EOS bytes if we have not finished on a single byte
+ if (!buffer.hasRemaining()) {
+ buffer.position(start);
+ return false;
+ }
+ buffer.put((byte) (currentBufferByte | ((0xFF) >> bytePos)));
+ }
+ return true;
+ }
+
+ protected static class HuffmanCode {
+ /**
+ * The value of the least significan't bits of the code
+ */
+ int value;
+ /**
+ * length of the code, in bits
+ */
+ int length;
+
+ public HuffmanCode(int value, int length) {
+ this.value = value;
+ this.length = length;
+ }
+
+ public int getValue() {
+ return value;
+ }
+
+ public int getLength() {
+ return length;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+
+
+ if (this == o) return true;
+ if (o == null || getClass() != o.getClass()) return false;
+
+ HuffmanCode that = (HuffmanCode) o;
+
+ if (length != that.length) return false;
+ if (value != that.value) return false;
+
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = value;
+ result = 31 * result + length;
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ return "HuffmanCode{" +
+ "value=" + value +
+ ", length=" + length +
+ '}';
+ }
+ }
+}
Propchange: tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: tomcat/trunk/java/org/apache/coyote/http2/Hpack.java
URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/Hpack.java?rev=1668116&view=auto
==============================================================================
--- tomcat/trunk/java/org/apache/coyote/http2/Hpack.java (added)
+++ tomcat/trunk/java/org/apache/coyote/http2/Hpack.java Fri Mar 20 18:47:03 2015
@@ -0,0 +1,215 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.coyote.http2;
+
+import java.nio.ByteBuffer;
+
+import org.apache.tomcat.util.res.StringManager;
+
+final class Hpack {
+
+ protected static final StringManager sm = StringManager.getManager(Hpack.class);
+
+ private static final byte LOWER_DIFF = 'a' - 'A';
+ static final int DEFAULT_TABLE_SIZE = 4096;
+ private static final int MAX_INTEGER_OCTETS = 8; //not sure what a good value for this is, but the spec says we need to provide an upper bound
+
+ /**
+ * table that contains powers of two,
+ * used as both bitmask and to quickly calculate 2^n
+ */
+ private static final int[] PREFIX_TABLE;
+
+
+ static final HeaderField[] STATIC_TABLE;
+ static final int STATIC_TABLE_LENGTH;
+
+ static {
+ PREFIX_TABLE = new int[32];
+ for (int i = 0; i < 32; ++i) {
+ int n = 0;
+ for (int j = 0; j < i; ++j) {
+ n = n << 1;
+ n |= 1;
+ }
+ PREFIX_TABLE[i] = n;
+ }
+
+ HeaderField[] fields = new HeaderField[62];
+ //note that zero is not used
+ fields[1] = new HeaderField(":authority", null);
+ fields[2] = new HeaderField(":method", "GET");
+ fields[3] = new HeaderField(":method", "POST");
+ fields[4] = new HeaderField(":path", "/");
+ fields[5] = new HeaderField(":path", "/index.html");
+ fields[6] = new HeaderField(":scheme", "http");
+ fields[7] = new HeaderField(":scheme", "https");
+ fields[8] = new HeaderField(":status", "200");
+ fields[9] = new HeaderField(":status", "204");
+ fields[10] = new HeaderField(":status", "206");
+ fields[11] = new HeaderField(":status", "304");
+ fields[12] = new HeaderField(":status", "400");
+ fields[13] = new HeaderField(":status", "404");
+ fields[14] = new HeaderField(":status", "500");
+ fields[15] = new HeaderField("accept-charset", null);
+ fields[16] = new HeaderField("accept-encoding", "gzip, deflate");
+ fields[17] = new HeaderField("accept-language", null);
+ fields[18] = new HeaderField("accept-ranges", null);
+ fields[19] = new HeaderField("accept", null);
+ fields[20] = new HeaderField("access-control-allow-origin", null);
+ fields[21] = new HeaderField("age", null);
+ fields[22] = new HeaderField("allow", null);
+ fields[23] = new HeaderField("authorization", null);
+ fields[24] = new HeaderField("cache-control", null);
+ fields[25] = new HeaderField("content-disposition", null);
+ fields[26] = new HeaderField("content-encoding", null);
+ fields[27] = new HeaderField("content-language", null);
+ fields[28] = new HeaderField("content-length", null);
+ fields[29] = new HeaderField("content-location", null);
+ fields[30] = new HeaderField("content-range", null);
+ fields[31] = new HeaderField("content-type", null);
+ fields[32] = new HeaderField("cookie", null);
+ fields[33] = new HeaderField("date", null);
+ fields[34] = new HeaderField("etag", null);
+ fields[35] = new HeaderField("expect", null);
+ fields[36] = new HeaderField("expires", null);
+ fields[37] = new HeaderField("from", null);
+ fields[38] = new HeaderField("host", null);
+ fields[39] = new HeaderField("if-match", null);
+ fields[40] = new HeaderField("if-modified-since", null);
+ fields[41] = new HeaderField("if-none-match", null);
+ fields[42] = new HeaderField("if-range", null);
+ fields[43] = new HeaderField("if-unmodified-since", null);
+ fields[44] = new HeaderField("last-modified", null);
+ fields[45] = new HeaderField("link", null);
+ fields[46] = new HeaderField("location", null);
+ fields[47] = new HeaderField("max-forwards", null);
+ fields[48] = new HeaderField("proxy-authenticate", null);
+ fields[49] = new HeaderField("proxy-authorization", null);
+ fields[50] = new HeaderField("range", null);
+ fields[51] = new HeaderField("referer", null);
+ fields[52] = new HeaderField("refresh", null);
+ fields[53] = new HeaderField("retry-after", null);
+ fields[54] = new HeaderField("server", null);
+ fields[55] = new HeaderField("set-cookie", null);
+ fields[56] = new HeaderField("strict-transport-security", null);
+ fields[57] = new HeaderField("transfer-encoding", null);
+ fields[58] = new HeaderField("user-agent", null);
+ fields[59] = new HeaderField("vary", null);
+ fields[60] = new HeaderField("via", null);
+ fields[61] = new HeaderField("www-authenticate", null);
+ STATIC_TABLE = fields;
+ STATIC_TABLE_LENGTH = STATIC_TABLE.length - 1;
+ }
+
+ static class HeaderField {
+ final String name;
+ final String value;
+ final int size;
+
+ HeaderField(String name, String value) {
+ this.name = name;
+ this.value = value;
+ if (value != null) {
+ this.size = 32 + name.length() + value.length();
+ } else {
+ this.size = -1;
+ }
+ }
+ }
+
+ /**
+ * Decodes an integer in the HPACK prefex format. If the return value is -1
+ * it means that there was not enough data in the buffer to complete the decoding
+ * sequence.
+ * <p/>
+ * If this method returns -1 then the source buffer will not have been modified.
+ *
+ * @param source The buffer that contains the integer
+ * @param n The encoding prefix length
+ * @return The encoded integer, or -1 if there was not enough data
+ */
+ static int decodeInteger(ByteBuffer source, int n) throws HpackException {
+ if (source.remaining() == 0) {
+ return -1;
+ }
+ int count = 1;
+ int sp = source.position();
+ int mask = PREFIX_TABLE[n];
+
+ int i = mask & source.get();
+ int b;
+ if (i < PREFIX_TABLE[n]) {
+ return i;
+ } else {
+ int m = 0;
+ do {
+ if(count++ > MAX_INTEGER_OCTETS) {
+ throw new HpackException(sm.getString("hpack.integerEncodedOverTooManyOctets", MAX_INTEGER_OCTETS));
+ }
+ if (source.remaining() == 0) {
+ //we have run out of data
+ //reset
+ source.position(sp);
+ return -1;
+ }
+ b = source.get();
+ i = i + (b & 127) * (PREFIX_TABLE[m] + 1);
+ m += 7;
+ } while ((b & 128) == 128);
+ }
+ return i;
+ }
+
+ /**
+ * Encodes an integer in the HPACK prefix format.
+ * <p/>
+ * This method assumes that the buffer has already had the first 8-n bits filled.
+ * As such it will modify the last byte that is already present in the buffer, and
+ * potentially add more if required
+ *
+ * @param source The buffer that contains the integer
+ * @param value The integer to encode
+ * @param n The encoding prefix length
+ */
+ static void encodeInteger(ByteBuffer source, int value, int n) {
+ int twoNminus1 = PREFIX_TABLE[n];
+ int pos = source.position() - 1;
+ if (value < twoNminus1) {
+ source.put(pos, (byte) (source.get(pos) | value));
+ } else {
+ source.put(pos, (byte) (source.get(pos) | twoNminus1));
+ value = value - twoNminus1;
+ while (value >= 128) {
+ source.put((byte) (value % 128 + 128));
+ value = value / 128;
+ }
+ source.put((byte) value);
+ }
+ }
+
+
+ static byte toLower(byte b) {
+ if (b >= 'A' && b <= 'Z') {
+ return (byte) (b + LOWER_DIFF);
+ }
+ return b;
+ }
+
+ private Hpack() {}
+
+}
Propchange: tomcat/trunk/java/org/apache/coyote/http2/Hpack.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java
URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java?rev=1668116&view=auto
==============================================================================
--- tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java (added)
+++ tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java Fri Mar 20 18:47:03 2015
@@ -0,0 +1,362 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.coyote.http2;
+
+import java.nio.ByteBuffer;
+
+import org.apache.tomcat.util.res.StringManager;
+
+import static org.apache.coyote.http2.Hpack.HeaderField;
+
+/**
+ * A decoder for HPACK.
+ */
+public class HpackDecoder {
+
+ protected static final StringManager sm = StringManager.getManager(HpackDecoder.class);
+
+ private static final int DEFAULT_RING_BUFFER_SIZE = 10;
+
+ /**
+ * The object that receives the headers that are emitted from this decoder
+ */
+ private HeaderEmitter headerEmitter;
+
+ /**
+ * The header table
+ */
+ private HeaderField[] headerTable;
+
+ /**
+ * The current HEAD position of the header table. We use a ring buffer type
+ * construct as it would be silly to actually shuffle the items around in the
+ * array.
+ */
+ private int firstSlotPosition = 0;
+
+ /**
+ * The current table size by index (aka the number of index positions that are filled up)
+ */
+ private int filledTableSlots = 0;
+
+ /**
+ * the current calculates memory size, as per the HPACK algorithm
+ */
+ private int currentMemorySize = 0;
+
+ /**
+ * The maximum allowed memory size
+ */
+ private int maxMemorySize;
+
+ private final StringBuilder stringBuilder = new StringBuilder();
+
+ public HpackDecoder(int maxMemorySize) {
+ this.maxMemorySize = maxMemorySize;
+ headerTable = new HeaderField[DEFAULT_RING_BUFFER_SIZE];
+ }
+
+ public HpackDecoder() {
+ this(Hpack.DEFAULT_TABLE_SIZE);
+ }
+
+ /**
+ * Decodes the provided frame data. If this method leaves data in the buffer then
+ * this buffer should be compacted so this data is preserved, unless there is no
+ * more data in which case this should be considered a protocol error.
+ *
+ * @param buffer The buffer
+ */
+ public void decode(ByteBuffer buffer) throws HpackException {
+ while (buffer.hasRemaining()) {
+ int originalPos = buffer.position();
+ byte b = buffer.get();
+ if ((b & 0b10000000) != 0) {
+ //if the first bit is set it is an indexed header field
+ buffer.position(buffer.position() - 1); //unget the byte
+ int index = Hpack.decodeInteger(buffer, 7); //prefix is 7
+ if (index == -1) {
+ buffer.position(originalPos);
+ return;
+ } else if(index == 0) {
+ throw new HpackException(sm.getString("hpackdecoder.zeroNotValidHeaderTableIndex"));
+ }
+ handleIndex(index);
+ } else if ((b & 0b01000000) != 0) {
+ //Literal Header Field with Incremental Indexing
+ String headerName = readHeaderName(buffer, 6);
+ if (headerName == null) {
+ buffer.position(originalPos);
+ return;
+ }
+ String headerValue = readHpackString(buffer);
+ if (headerValue == null) {
+ buffer.position(originalPos);
+ return;
+ }
+ headerEmitter.emitHeader(headerName, headerValue, false);
+ addEntryToHeaderTable(new HeaderField(headerName, headerValue));
+ } else if ((b & 0b11110000) == 0) {
+ //Literal Header Field without Indexing
+ String headerName = readHeaderName(buffer, 4);
+ if (headerName == null) {
+ buffer.position(originalPos);
+ return;
+ }
+ String headerValue = readHpackString(buffer);
+ if (headerValue == null) {
+ buffer.position(originalPos);
+ return;
+ }
+ headerEmitter.emitHeader(headerName, headerValue, false);
+ } else if ((b & 0b11110000) == 0b00010000) {
+ //Literal Header Field never indexed
+ String headerName = readHeaderName(buffer, 4);
+ if (headerName == null) {
+ buffer.position(originalPos);
+ return;
+ }
+ String headerValue = readHpackString(buffer);
+ if (headerValue == null) {
+ buffer.position(originalPos);
+ return;
+ }
+ headerEmitter.emitHeader(headerName, headerValue, true);
+ } else if ((b & 0b11100000) == 0b00100000) {
+ //context update max table size change
+ if (!handleMaxMemorySizeChange(buffer, originalPos)) {
+ return;
+ }
+ } else {
+ throw new RuntimeException("Not yet implemented");
+ }
+ }
+ }
+
+ private boolean handleMaxMemorySizeChange(ByteBuffer buffer, int originalPos) throws HpackException {
+ buffer.position(buffer.position() - 1); //unget the byte
+ int size = Hpack.decodeInteger(buffer, 5);
+ if (size == -1) {
+ buffer.position(originalPos);
+ return false;
+ }
+ maxMemorySize = size;
+ if (currentMemorySize > maxMemorySize) {
+ int newTableSlots = filledTableSlots;
+ int tableLength = headerTable.length;
+ int newSize = currentMemorySize;
+ while (newSize > maxMemorySize) {
+ int clearIndex = firstSlotPosition;
+ firstSlotPosition++;
+ if (firstSlotPosition == tableLength) {
+ firstSlotPosition = 0;
+ }
+ HeaderField oldData = headerTable[clearIndex];
+ headerTable[clearIndex] = null;
+ newSize -= oldData.size;
+ newTableSlots--;
+ }
+ this.filledTableSlots = newTableSlots;
+ currentMemorySize = newSize;
+ }
+ return true;
+ }
+
+ private String readHeaderName(ByteBuffer buffer, int prefixLength) throws HpackException {
+ buffer.position(buffer.position() - 1); //unget the byte
+ int index = Hpack.decodeInteger(buffer, prefixLength);
+ if (index == -1) {
+ return null;
+ } else if (index != 0) {
+ return handleIndexedHeaderName(index);
+ } else {
+ return readHpackString(buffer);
+ }
+ }
+
+ private String readHpackString(ByteBuffer buffer) throws HpackException {
+ if (!buffer.hasRemaining()) {
+ return null;
+ }
+ byte data = buffer.get(buffer.position());
+
+ int length = Hpack.decodeInteger(buffer, 7);
+ if (buffer.remaining() < length) {
+ return null;
+ }
+ boolean huffman = (data & 0b10000000) != 0;
+ if (huffman) {
+ return readHuffmanString(length, buffer);
+ }
+ for (int i = 0; i < length; ++i) {
+ stringBuilder.append((char) buffer.get());
+ }
+ String ret = stringBuilder.toString();
+ stringBuilder.setLength(0);
+ return ret;
+ }
+
+ private String readHuffmanString(int length, ByteBuffer buffer) throws HpackException {
+ HPackHuffman.decode(buffer, length, stringBuilder);
+ String ret = stringBuilder.toString();
+ stringBuilder.setLength(0);
+ return ret;
+ }
+
+ private String handleIndexedHeaderName(int index) throws HpackException {
+ if (index <= Hpack.STATIC_TABLE_LENGTH) {
+ return Hpack.STATIC_TABLE[index].name;
+ } else {
+ if (index >= Hpack.STATIC_TABLE_LENGTH + filledTableSlots) {
+ throw new HpackException();
+ }
+ int adjustedIndex = getRealIndex(index - Hpack.STATIC_TABLE_LENGTH);
+ HeaderField res = headerTable[adjustedIndex];
+ if (res == null) {
+ throw new HpackException();
+ }
+ return res.name;
+ }
+ }
+
+ /**
+ * Handle an indexed header representation
+ *
+ * @param index The index
+ * @throws HpackException
+ */
+ private void handleIndex(int index) throws HpackException {
+ if (index <= Hpack.STATIC_TABLE_LENGTH) {
+ addStaticTableEntry(index);
+ } else {
+ int adjustedIndex = getRealIndex(index - Hpack.STATIC_TABLE_LENGTH);
+ HeaderField headerField = headerTable[adjustedIndex];
+ headerEmitter.emitHeader(headerField.name, headerField.value, false);
+ }
+ }
+
+ /**
+ * because we use a ring buffer type construct, and don't actually shuffle
+ * items in the array, we need to figure out the real index to use.
+ * <p/>
+ * package private for unit tests
+ *
+ * @param index The index from the hpack
+ * @return the real index into the array
+ */
+ int getRealIndex(int index) {
+ //the index is one based, but our table is zero based, hence -1
+ //also because of our ring buffer setup the indexes are reversed
+ //index = 1 is at position firstSlotPosition + filledSlots
+ return (firstSlotPosition + (filledTableSlots - index)) % headerTable.length;
+ }
+
+ private void addStaticTableEntry(int index) throws HpackException {
+ //adds an entry from the static table.
+ //this must be an entry with a value as far as I can determine
+ HeaderField entry = Hpack.STATIC_TABLE[index];
+ if (entry.value == null) {
+ throw new HpackException();
+ }
+ headerEmitter.emitHeader(entry.name, entry.value, false);
+ }
+
+ private void addEntryToHeaderTable(HeaderField entry) {
+ if (entry.size > maxMemorySize) {
+ //it is to big to fit, so we just completely clear the table.
+ while (filledTableSlots > 0) {
+ headerTable[firstSlotPosition] = null;
+ firstSlotPosition++;
+ if (firstSlotPosition == headerTable.length) {
+ firstSlotPosition = 0;
+ }
+ filledTableSlots--;
+ }
+ currentMemorySize = 0;
+ return;
+ }
+ resizeIfRequired();
+ int newTableSlots = filledTableSlots + 1;
+ int tableLength = headerTable.length;
+ int index = (firstSlotPosition + filledTableSlots) % tableLength;
+ headerTable[index] = entry;
+ int newSize = currentMemorySize + entry.size;
+ while (newSize > maxMemorySize) {
+ int clearIndex = firstSlotPosition;
+ firstSlotPosition++;
+ if (firstSlotPosition == tableLength) {
+ firstSlotPosition = 0;
+ }
+ HeaderField oldData = headerTable[clearIndex];
+ headerTable[clearIndex] = null;
+ newSize -= oldData.size;
+ newTableSlots--;
+ }
+ this.filledTableSlots = newTableSlots;
+ currentMemorySize = newSize;
+ }
+
+ private void resizeIfRequired() {
+ if(filledTableSlots == headerTable.length) {
+ HeaderField[] newArray = new HeaderField[headerTable.length + 10]; //we only grow slowly
+ for(int i = 0; i < headerTable.length; ++i) {
+ newArray[i] = headerTable[(firstSlotPosition + i) % headerTable.length];
+ }
+ firstSlotPosition = 0;
+ headerTable = newArray;
+ }
+ }
+
+
+ /**
+ * Interface that can be used to immediately validate headers (ex: uppercase detection).
+ */
+ public interface HeaderEmitter {
+ void emitHeader(String name, String value, boolean neverIndex);
+ }
+
+
+ public HeaderEmitter getHeaderEmitter() {
+ return headerEmitter;
+ }
+
+ public void setHeaderEmitter(HeaderEmitter headerEmitter) {
+ this.headerEmitter = headerEmitter;
+ }
+
+ //package private fields for unit tests
+
+ int getFirstSlotPosition() {
+ return firstSlotPosition;
+ }
+
+ HeaderField[] getHeaderTable() {
+ return headerTable;
+ }
+
+ int getFilledTableSlots() {
+ return filledTableSlots;
+ }
+
+ int getCurrentMemorySize() {
+ return currentMemorySize;
+ }
+
+ int getMaxMemorySize() {
+ return maxMemorySize;
+ }
+}
Propchange: tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java
URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java?rev=1668116&view=auto
==============================================================================
--- tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java (added)
+++ tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java Fri Mar 20 18:47:03 2015
@@ -0,0 +1,390 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.coyote.http2;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Locale;
+import java.util.Map;
+
+import org.apache.tomcat.util.http.MimeHeaders;
+
+import static org.apache.coyote.http2.Hpack.HeaderField;
+import static org.apache.coyote.http2.Hpack.STATIC_TABLE;
+import static org.apache.coyote.http2.Hpack.STATIC_TABLE_LENGTH;
+import static org.apache.coyote.http2.Hpack.encodeInteger;
+
+/**
+ * Encoder for HPACK frames.
+ */
+public class HpackEncoder {
+
+ public static final HpackHeaderFunction DEFAULT_HEADER_FUNCTION = new HpackHeaderFunction() {
+ @Override
+ public boolean shouldUseIndexing(String headerName, String value) {
+ //content length and date change all the time
+ //no need to index them, or they will churn the table
+ return !headerName.equals("content-length") && !headerName.equals("date");
+ }
+
+ @Override
+ public boolean shouldUseHuffman(String header, String value) {
+ return value.length() > 5; //TODO: figure out a good value for this
+ }
+
+ @Override
+ public boolean shouldUseHuffman(String header) {
+ return header.length() > 5; //TODO: figure out a good value for this
+ }
+
+
+ };
+
+ private int headersIterator = -1;
+ private boolean firstPass = true;
+
+ private MimeHeaders currentHeaders;
+
+ private int entryPositionCounter;
+
+ private int newMaxHeaderSize = -1; //if the max header size has been changed
+ private int minNewMaxHeaderSize = -1; //records the smallest value of newMaxHeaderSize, as per section 4.1
+
+ private static final Map<String, TableEntry[]> ENCODING_STATIC_TABLE;
+
+ private final Deque<TableEntry> evictionQueue = new ArrayDeque<>();
+ private final Map<String, List<TableEntry>> dynamicTable = new HashMap<>(); //TODO: use a custom data structure to reduce allocations
+
+ static {
+ Map<String, TableEntry[]> map = new HashMap<>();
+ for (int i = 1; i < STATIC_TABLE.length; ++i) {
+ HeaderField m = STATIC_TABLE[i];
+ TableEntry[] existing = map.get(m.name);
+ if (existing == null) {
+ map.put(m.name, new TableEntry[]{new TableEntry(m.name, m.value, i)});
+ } else {
+ TableEntry[] newEntry = new TableEntry[existing.length + 1];
+ System.arraycopy(existing, 0, newEntry, 0, existing.length);
+ newEntry[existing.length] = new TableEntry(m.name, m.value, i);
+ map.put(m.name, newEntry);
+ }
+ }
+ ENCODING_STATIC_TABLE = Collections.unmodifiableMap(map);
+ }
+
+ /**
+ * The maximum table size
+ */
+ private int maxTableSize;
+
+ /**
+ * The current table size
+ */
+ private int currentTableSize;
+
+ private final HpackHeaderFunction hpackHeaderFunction;
+
+ public HpackEncoder(int maxTableSize, HpackHeaderFunction headerFunction) {
+ this.maxTableSize = maxTableSize;
+ this.hpackHeaderFunction = headerFunction;
+ }
+
+ public HpackEncoder(int maxTableSize) {
+ this(maxTableSize, DEFAULT_HEADER_FUNCTION);
+ }
+
+ /**
+ * Encodes the headers into a buffer.
+ *
+ * @param headers
+ * @param target
+ */
+ public State encode(MimeHeaders headers, ByteBuffer target) {
+ int it = headersIterator;
+ if (headersIterator == -1) {
+ handleTableSizeChange(target);
+ //new headers map
+ it = 0;
+ currentHeaders = headers;
+ } else {
+ if (headers != currentHeaders) {
+ throw new IllegalStateException();
+ }
+ }
+ while (it < currentHeaders.size()) {
+ // FIXME: Review lowercase policy
+ String headerName = headers.getName(it).toString().toLowerCase(Locale.US);
+ boolean skip = false;
+ if (firstPass) {
+ if (headerName.charAt(0) != ':') {
+ skip = true;
+ }
+ } else {
+ if (headerName.charAt(0) == ':') {
+ skip = true;
+ }
+ }
+ if (!skip) {
+
+ int required = 11 + headerName.length(); //we use 11 to make sure we have enough room for the variable length integers
+
+ String val = headers.getValue(it).toString();
+ TableEntry tableEntry = findInTable(headerName, val);
+
+ required += (1 + val.length());
+
+ if (target.remaining() < required) {
+ this.headersIterator = it;
+ return State.UNDERFLOW;
+ }
+ boolean canIndex = hpackHeaderFunction.shouldUseIndexing(headerName, val) && (headerName.length() + val.length() + 32) < maxTableSize; //only index if it will fit
+ if (tableEntry == null && canIndex) {
+ //add the entry to the dynamic table
+ target.put((byte) (1 << 6));
+ writeHuffmanEncodableName(target, headerName);
+ writeHuffmanEncodableValue(target, headerName, val);
+ addToDynamicTable(headerName, val);
+ } else if (tableEntry == null) {
+ //literal never indexed
+ target.put((byte) (1 << 4));
+ writeHuffmanEncodableName(target, headerName);
+ writeHuffmanEncodableValue(target, headerName, val);
+ } else {
+ //so we know something is already in the table
+ if (val.equals(tableEntry.value)) {
+ //the whole thing is in the table
+ target.put((byte) (1 << 7));
+ encodeInteger(target, tableEntry.getPosition(), 7);
+ } else {
+ if (canIndex) {
+ //add the entry to the dynamic table
+ target.put((byte) (1 << 6));
+ encodeInteger(target, tableEntry.getPosition(), 6);
+ writeHuffmanEncodableValue(target, headerName, val);
+ addToDynamicTable(headerName, val);
+
+ } else {
+ target.put((byte) (1 << 4));
+ encodeInteger(target, tableEntry.getPosition(), 4);
+ writeHuffmanEncodableValue(target, headerName, val);
+ }
+ }
+ }
+
+ }
+ if (++it == currentHeaders.size() && firstPass) {
+ firstPass = false;
+ it = 0;
+ }
+ }
+ headersIterator = -1;
+ firstPass = true;
+ return State.COMPLETE;
+ }
+
+ private void writeHuffmanEncodableName(ByteBuffer target, String headerName) {
+ if (hpackHeaderFunction.shouldUseHuffman(headerName)) {
+ if(HPackHuffman.encode(target, headerName.toString(), true)) {
+ return;
+ }
+ }
+ target.put((byte) 0); //to use encodeInteger we need to place the first byte in the buffer.
+ encodeInteger(target, headerName.length(), 7);
+ for (int j = 0; j < headerName.length(); ++j) {
+ target.put(Hpack.toLower((byte) headerName.charAt(j)));
+ }
+
+ }
+
+ private void writeHuffmanEncodableValue(ByteBuffer target, String headerName, String val) {
+ if (hpackHeaderFunction.shouldUseHuffman(headerName, val)) {
+ if (!HPackHuffman.encode(target, val, false)) {
+ writeValueString(target, val);
+ }
+ } else {
+ writeValueString(target, val);
+ }
+ }
+
+ private void writeValueString(ByteBuffer target, String val) {
+ target.put((byte) 0); //to use encodeInteger we need to place the first byte in the buffer.
+ encodeInteger(target, val.length(), 7);
+ for (int j = 0; j < val.length(); ++j) {
+ target.put((byte) val.charAt(j));
+ }
+ }
+
+ private void addToDynamicTable(String headerName, String val) {
+ int pos = entryPositionCounter++;
+ DynamicTableEntry d = new DynamicTableEntry(headerName, val, -pos);
+ List<TableEntry> existing = dynamicTable.get(headerName);
+ if (existing == null) {
+ dynamicTable.put(headerName, existing = new ArrayList<TableEntry>(1));
+ }
+ existing.add(d);
+ evictionQueue.add(d);
+ currentTableSize += d.size;
+ runEvictionIfRequired();
+ if (entryPositionCounter == Integer.MAX_VALUE) {
+ //prevent rollover
+ preventPositionRollover();
+ }
+
+ }
+
+
+ private void preventPositionRollover() {
+ //if the position counter is about to roll over we iterate all the table entries
+ //and set their position to their actual position
+ for (Map.Entry<String, List<TableEntry>> entry : dynamicTable.entrySet()) {
+ for (TableEntry t : entry.getValue()) {
+ t.position = t.getPosition();
+ }
+ }
+ entryPositionCounter = 0;
+ }
+
+ private void runEvictionIfRequired() {
+
+ while (currentTableSize > maxTableSize) {
+ TableEntry next = evictionQueue.poll();
+ if (next == null) {
+ return;
+ }
+ currentTableSize -= next.size;
+ List<TableEntry> list = dynamicTable.get(next.name);
+ list.remove(next);
+ if (list.isEmpty()) {
+ dynamicTable.remove(next.name);
+ }
+ }
+ }
+
+ private TableEntry findInTable(String headerName, String value) {
+ TableEntry[] staticTable = ENCODING_STATIC_TABLE.get(headerName);
+ if (staticTable != null) {
+ for (TableEntry st : staticTable) {
+ if (st.value != null && st.value.equals(value)) { //todo: some form of lookup?
+ return st;
+ }
+ }
+ }
+ List<TableEntry> dynamic = dynamicTable.get(headerName);
+ if (dynamic != null) {
+ for (TableEntry st : dynamic) {
+ if (st.value.equals(value)) { //todo: some form of lookup?
+ return st;
+ }
+ }
+ }
+ if (staticTable != null) {
+ return staticTable[0];
+ }
+ return null;
+ }
+
+ public void setMaxTableSize(int newSize) {
+ this.newMaxHeaderSize = newSize;
+ if (minNewMaxHeaderSize == -1) {
+ minNewMaxHeaderSize = newSize;
+ } else {
+ minNewMaxHeaderSize = Math.min(newSize, minNewMaxHeaderSize);
+ }
+ }
+
+ private void handleTableSizeChange(ByteBuffer target) {
+ if (newMaxHeaderSize == -1) {
+ return;
+ }
+ if (minNewMaxHeaderSize != newMaxHeaderSize) {
+ target.put((byte) (1 << 5));
+ encodeInteger(target, minNewMaxHeaderSize, 5);
+ }
+ target.put((byte) (1 << 5));
+ encodeInteger(target, newMaxHeaderSize, 5);
+ maxTableSize = newMaxHeaderSize;
+ runEvictionIfRequired();
+ newMaxHeaderSize = -1;
+ minNewMaxHeaderSize = -1;
+ }
+
+ public enum State {
+ COMPLETE,
+ UNDERFLOW,
+
+ }
+
+ static class TableEntry {
+ final String name;
+ final String value;
+ final int size;
+ int position;
+
+ TableEntry(String name, String value, int position) {
+ this.name = name;
+ this.value = value;
+ this.position = position;
+ if (value != null) {
+ this.size = 32 + name.length() + value.length();
+ } else {
+ this.size = -1;
+ }
+ }
+
+ public int getPosition() {
+ return position;
+ }
+ }
+
+ class DynamicTableEntry extends TableEntry {
+
+ DynamicTableEntry(String name, String value, int position) {
+ super(name, value, position);
+ }
+
+ @Override
+ public int getPosition() {
+ return super.getPosition() + entryPositionCounter + STATIC_TABLE_LENGTH;
+ }
+ }
+
+ public interface HpackHeaderFunction {
+ boolean shouldUseIndexing(String header, String value);
+
+ /**
+ * Returns true if huffman encoding should be used on the header value
+ *
+ * @param header The header name
+ * @param value The header value to be encoded
+ * @return <code>true</code> if the value should be encoded
+ */
+ boolean shouldUseHuffman(String header, String value);
+
+ /**
+ * Returns true if huffman encoding should be used on the header name
+ *
+ * @param header The header name to be encoded
+ * @return <code>true</code> if the value should be encoded
+ */
+ boolean shouldUseHuffman(String header);
+ }
+}
Propchange: tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: tomcat/trunk/java/org/apache/coyote/http2/HpackException.java
URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/HpackException.java?rev=1668116&view=auto
==============================================================================
--- tomcat/trunk/java/org/apache/coyote/http2/HpackException.java (added)
+++ tomcat/trunk/java/org/apache/coyote/http2/HpackException.java Fri Mar 20 18:47:03 2015
@@ -0,0 +1,34 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.coyote.http2;
+
+/**
+ * Exception that is thrown when the HPACK compress context is broken.
+ * <p/>
+ * In this case the connection must be closed.
+ */
+public class HpackException extends Exception {
+ public HpackException(String message, Throwable cause) {
+ super(message, cause);
+ }
+ public HpackException(String message) {
+ super(message);
+ }
+ public HpackException() {
+ super();
+ }
+}
Propchange: tomcat/trunk/java/org/apache/coyote/http2/HpackException.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties
URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties?rev=1668116&view=auto
==============================================================================
--- tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties (added)
+++ tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties Fri Mar 20 18:47:03 2015
@@ -0,0 +1,20 @@
+# Licensed to the Apache Software Foundation (ASF) under one or more
+# contributor license agreements. See the NOTICE file distributed with
+# this work for additional information regarding copyright ownership.
+# The ASF licenses this file to You under the Apache License, Version 2.0
+# (the "License"); you may not use this file except in compliance with
+# the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+hpack.integerEncodedOverTooManyOctets=HPACK variable length integer encoded over too many octets, max is {0}
+
+hpackdecoder.zeroNotValidHeaderTableIndex=Zero is not a valid header table index
+
+hpackhuffman.huffmanEncodedHpackValueDidNotEndWithEOS=Huffman encoded value in HPACK headers did not end with EOS padding
\ No newline at end of file
Propchange: tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties
------------------------------------------------------------------------------
svn:eol-style = native
Added: tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java
URL: http://svn.apache.org/viewvc/tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java?rev=1668116&view=auto
==============================================================================
--- tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java (added)
+++ tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java Fri Mar 20 18:47:03 2015
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.coyote.http2;
+
+import java.nio.ByteBuffer;
+
+import org.apache.tomcat.util.http.MimeHeaders;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class TestHpack {
+
+ @Test
+ public void testEncode() throws Exception {
+ MimeHeaders headers = new MimeHeaders();
+ headers.setValue("header1").setString("value1");
+ headers.setValue(":status").setString("200");
+ headers.setValue("header2").setString("value2");
+ ByteBuffer output = ByteBuffer.allocate(512);
+ HpackEncoder encoder = new HpackEncoder(1024);
+ encoder.encode(headers, output);
+ output.flip();
+ // Size is supposed to be 33 without huffman, or 27 with it
+ // TODO: use the HpackHeaderFunction to enable huffman predictably
+ Assert.assertEquals(27, output.remaining());
+ output.clear();
+ encoder.encode(headers, output);
+ output.flip();
+ // Size is now 3 after using the table
+ Assert.assertEquals(3, output.remaining());
+ }
+
+ @Test
+ public void testDecode() throws Exception {
+ MimeHeaders headers = new MimeHeaders();
+ headers.setValue("header1").setString("value1");
+ headers.setValue(":status").setString("200");
+ headers.setValue("header2").setString("value2");
+ ByteBuffer output = ByteBuffer.allocate(512);
+ HpackEncoder encoder = new HpackEncoder(1024);
+ encoder.encode(headers, output);
+ output.flip();
+ MimeHeaders headers2 = new MimeHeaders();
+ HpackDecoder decoder = new HpackDecoder();
+ decoder.setHeaderEmitter(new HeadersListener(headers2));
+ decoder.decode(output);
+ // Redo (table is supposed to be updated)
+ output.clear();
+ encoder.encode(headers, output);
+ output.flip();
+ headers2.recycle();
+ Assert.assertEquals(3, output.remaining());
+ // Check that the decoder is using the table right
+ decoder.decode(output);
+ Assert.assertEquals("value2", headers2.getHeader("header2"));
+ }
+
+ private static class HeadersListener implements HpackDecoder.HeaderEmitter {
+ private final MimeHeaders headers;
+ public HeadersListener(MimeHeaders headers) {
+ this.headers = headers;
+ }
+ @Override
+ public void emitHeader(String name, String value, boolean neverIndex) {
+ headers.setValue(name).setString(value);
+ }
+ }
+
+ // TODO: Write more complete tests
+
+}
Propchange: tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: tomcat/trunk/webapps/docs/changelog.xml
URL: http://svn.apache.org/viewvc/tomcat/trunk/webapps/docs/changelog.xml?rev=1668116&r1=1668115&r2=1668116&view=diff
==============================================================================
--- tomcat/trunk/webapps/docs/changelog.xml (original)
+++ tomcat/trunk/webapps/docs/changelog.xml Fri Mar 20 18:47:03 2015
@@ -73,6 +73,10 @@
<bug>55988</bug>: Add support for Java 8 JSSE server-preferred TLS
cipher suite ordering. Patch provided by Ognjen Blagojevic. (schultz)
</fix>
+ <add>
+ Add support for HPACK header encoding and decoding, contributed
+ by Stuart Douglas. (remm)
+ </add>
</changelog>
</subsection>
<subsection name="Tribes">
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@tomcat.apache.org
For additional commands, e-mail: dev-help@tomcat.apache.org