TS-3890: Errors in the huffman tree for HTTP/2 (cherry picked from commit 6f151efcf4282587b4e7edbfaa9222d477b8adfc) (cherry picked from commit 03fec13971a9b789292608951a79d9013079f98d)
Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/b3d75bf3 Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/b3d75bf3 Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/b3d75bf3 Branch: refs/heads/5.3.x Commit: b3d75bf3de392ce01c184cf31ed07b1e1bca4769 Parents: ac2ec86 Author: Bryan Call <[email protected]> Authored: Thu Sep 3 12:19:09 2015 -0700 Committer: Phil Sorber <[email protected]> Committed: Tue Sep 8 14:24:37 2015 -0600 ---------------------------------------------------------------------- proxy/http2/HuffmanCodec.cc | 6 ++-- proxy/http2/test_Huffmancode.cc | 67 +++++++++++++++++++++++++++++++++--- 2 files changed, 66 insertions(+), 7 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/b3d75bf3/proxy/http2/HuffmanCodec.cc ---------------------------------------------------------------------- diff --git a/proxy/http2/HuffmanCodec.cc b/proxy/http2/HuffmanCodec.cc index 0efe589..4b8c671 100644 --- a/proxy/http2/HuffmanCodec.cc +++ b/proxy/http2/HuffmanCodec.cc @@ -171,7 +171,7 @@ static const huffman_entry huffman_table[] = {{0x1ff8, 13}, {0x7fffdc, 23}, {0x7fffdd, 23}, {0x7fffde, 23}, - {0xffffeb, 23}, + {0xffffeb, 24}, {0x7fffdf, 23}, {0xffffec, 24}, {0xffffed, 24}, @@ -197,7 +197,7 @@ static const huffman_entry huffman_table[] = {{0x1ff8, 13}, {0x7fffe8, 23}, {0x7fffe9, 23}, {0x1fffde, 21}, - {0x7fffde, 23}, + {0x7fffea, 23}, {0x3fffdd, 22}, {0x3fffde, 22}, {0xfffff0, 24}, @@ -243,7 +243,7 @@ static const huffman_entry huffman_table[] = {{0x1ff8, 13}, {0x7ffffe0, 27}, {0x7ffffe1, 27}, {0x3ffffe7, 26}, - {0x3ffffe2, 27}, + {0x7ffffe2, 27}, {0xfffff2, 24}, {0x1fffe4, 21}, {0x1fffe5, 21}, http://git-wip-us.apache.org/repos/asf/trafficserver/blob/b3d75bf3/proxy/http2/test_Huffmancode.cc ---------------------------------------------------------------------- diff --git a/proxy/http2/test_Huffmancode.cc b/proxy/http2/test_Huffmancode.cc index e7a973f..d00839d 100644 --- a/proxy/http2/test_Huffmancode.cc +++ b/proxy/http2/test_Huffmancode.cc @@ -1,11 +1,15 @@ #include "HuffmanCodec.h" #include <stdlib.h> #include <iostream> +#include <assert.h> using namespace std; +uint32_t test_values[] = {0x1ff8, 13, 0x7fffd8, 23, 0xfffffe2, 28, 0xfffffe3, 28, 0xfffffe4, 28, 0xfffffe5, 28, 0xfffffe6, 28, 0xfffffe7, 28, 0xfffffe8, 28, 0xffffea, 24, 0x3ffffffc, 30, 0xfffffe9, 28, 0xfffffea, 28, 0x3ffffffd, 30, 0xfffffeb, 28, 0xfffffec, 28, 0xfffffed, 28, 0xfffffee, 28, 0xfffffef, 28, 0xffffff0, 28, 0xffffff1, 28, 0xffffff2, 28, 0x3ffffffe, 30, 0xffffff3, 28, 0xffffff4, 28, 0xffffff5, 28, 0xffffff6, 28, 0xffffff7, 28, 0xffffff8, 28, 0xffffff9, 28, 0xffffffa, 28, 0xffffffb, 28, 0x14, 6, 0x3f8, 10, 0x3f9, 10, 0xffa, 12, 0x1ff9, 13, 0x15, 6, 0xf8, 8, 0x7fa, 11, 0x3fa, 10, 0x3fb, 10, 0xf9, 8, 0x7fb, 11, 0xfa, 8, 0x16, 6, 0x17, 6, 0x18, 6, 0x0, 5, 0x1, 5, 0x2, 5, 0x19, 6, 0x1a, 6, 0x1b, 6, 0x1c, 6, 0x1d, 6, 0x1e, 6, 0x1f, 6, 0x5c, 7, 0xfb, 8, 0x7ffc, 15, 0x20, 6, 0xffb, 12, 0x3fc, 10, 0x1ffa, 13, 0x21, 6, 0x5d, 7, 0x5e, 7, 0x5f, 7, 0x60, 7, 0x61, 7, 0x62, 7, 0x63, 7, 0x64, 7, 0x65, 7, 0x66, 7, 0x67, 7, 0x68, 7, 0x69, 7, 0x6a, 7, 0x6b, 7, 0x6c, 7, 0x6d, 7, 0x6e, 7, 0 x6f, 7, 0x70, 7, 0x71, 7, 0x72, 7, 0xfc, 8, 0x73, 7, 0xfd, 8, 0x1ffb, 13, 0x7fff0, 19, 0x1ffc, 13, 0x3ffc, 14, 0x22, 6, 0x7ffd, 15, 0x3, 5, 0x23, 6, 0x4, 5, 0x24, 6, 0x5, 5, 0x25, 6, 0x26, 6, 0x27, 6, 0x6, 5, 0x74, 7, 0x75, 7, 0x28, 6, 0x29, 6, 0x2a, 6, 0x7, 5, 0x2b, 6, 0x76, 7, 0x2c, 6, 0x8, 5, 0x9, 5, 0x2d, 6, 0x77, 7, 0x78, 7, 0x79, 7, 0x7a, 7, 0x7b, 7, 0x7ffe, 15, 0x7fc, 11, 0x3ffd, 14, 0x1ffd, 13, 0xffffffc, 28, 0xfffe6, 20, 0x3fffd2, 22, 0xfffe7, 20, 0xfffe8, 20, 0x3fffd3, 22, 0x3fffd4, 22, 0x3fffd5, 22, 0x7fffd9, 23, 0x3fffd6, 22, 0x7fffda, 23, 0x7fffdb, 23, 0x7fffdc, 23, 0x7fffdd, 23, 0x7fffde, 23, 0xffffeb, 24, 0x7fffdf, 23, 0xffffec, 24, 0xffffed, 24, 0x3fffd7, 22, 0x7fffe0, 23, 0xffffee, 24, 0x7fffe1, 23, 0x7fffe2, 23, 0x7fffe3, 23, 0x7fffe4, 23, 0x1fffdc, 21, 0x3fffd8, 22, 0x7fffe5, 23, 0x3fffd9, 22, 0x7fffe6, 23, 0x7fffe7, 23, 0xffffef, 24, 0x3fffda, 22, 0x1fffdd, 21, 0xfffe9, 20, 0x3fffdb, 22, 0x3fffdc, 22, 0x7fffe8, 23, 0x7fffe9, 23, 0x1fffde, 21, 0x7fffea, 23, 0x3fff dd, 22, 0x3fffde, 22, 0xfffff0, 24, 0x1fffdf, 21, 0x3fffdf, 22, 0x7fffeb, 23, 0x7fffec, 23, 0x1fffe0, 21, 0x1fffe1, 21, 0x3fffe0, 22, 0x1fffe2, 21, 0x7fffed, 23, 0x3fffe1, 22, 0x7fffee, 23, 0x7fffef, 23, 0xfffea, 20, 0x3fffe2, 22, 0x3fffe3, 22, 0x3fffe4, 22, 0x7ffff0, 23, 0x3fffe5, 22, 0x3fffe6, 22, 0x7ffff1, 23, 0x3ffffe0, 26, 0x3ffffe1, 26, 0xfffeb, 20, 0x7fff1, 19, 0x3fffe7, 22, 0x7ffff2, 23, 0x3fffe8, 22, 0x1ffffec, 25, 0x3ffffe2, 26, 0x3ffffe3, 26, 0x3ffffe4, 26, 0x7ffffde, 27, 0x7ffffdf, 27, 0x3ffffe5, 26, 0xfffff1, 24, 0x1ffffed, 25, 0x7fff2, 19, 0x1fffe3, 21, 0x3ffffe6, 26, 0x7ffffe0, 27, 0x7ffffe1, 27, 0x3ffffe7, 26, 0x7ffffe2, 27, 0xfffff2, 24, 0x1fffe4, 21, 0x1fffe5, 21, 0x3ffffe8, 26, 0x3ffffe9, 26, 0xffffffd, 28, 0x7ffffe3, 27, 0x7ffffe4, 27, 0x7ffffe5, 27, 0xfffec, 20, 0xfffff3, 24, 0xfffed, 20, 0x1fffe6, 21, 0x3fffe9, 22, 0x1fffe7, 21, 0x1fffe8, 21, 0x7ffff3, 23, 0x3fffea, 22, 0x3fffeb, 22, 0x1ffffee, 25, 0x1ffffef, 25, 0xfffff4, 24, 0xfffff5, 24, 0x3ffffea, 26, 0x7ff ff4, 23, 0x3ffffeb, 26, 0x7ffffe6, 27, 0x3ffffec, 26, 0x3ffffed, 26, 0x7ffffe7, 27, 0x7ffffe8, 27, 0x7ffffe9, 27, 0x7ffffea, 27, 0x7ffffeb, 27, 0xffffffe, 28, 0x7ffffec, 27, 0x7ffffed, 27, 0x7ffffee, 27, 0x7ffffef, 27, 0x7fffff0, 27, 0x3ffffee, 26, 0x3fffffff, 30}; + + void -test() +random_test() { const int size = 1024; char *dst_start = (char *)malloc(size * 2); @@ -19,22 +23,77 @@ test() int bytes = huffman_decode(dst_start, src, src_len); - cout << "bytes: " << bytes << endl; + //cout << "bytes: " << bytes << endl; for (int i = 0; i < bytes; i++) { - cout << i << " " << (int)dst_start[i] << " " << dst_start[i] << endl; + //cout << i << " " << (int)dst_start[i] << " " << dst_start[i] << endl; } free(dst_start); } +union Value { + uint32_t x; + uint8_t y[4]; +}; + +void +values_test() +{ + + char dst_start[4]; + int size = sizeof(test_values) / 4; + for (int i = 0; i < size; i += 2) { + const uint32_t value = test_values[i]; + const uint32_t bits = test_values[i+1]; + + // copy the bits and set remaining bits to 1 + union Value encoded; + union Value encoded_mapped; + encoded.x = 0; + uint32_t bits_counter = bits; + for (uint32_t pos = 32; pos > 0; pos--) { + if (bits_counter > 0) { + if (value & (1 << (bits_counter-1))) { + encoded.x = encoded.x | (1 << (pos-1)); + } + bits_counter--; + } else { + encoded.x = encoded.x | (1 << (pos-1)); + } + } + + int encoded_size = 0; + if (bits > 24) { + encoded_size = 4; + } else if (bits > 16) { + encoded_size = 3; + } else if (bits > 8) { + encoded_size = 2; + } else { + encoded_size = 1; + } + + encoded_mapped.y[0] = encoded.y[3]; + encoded_mapped.y[1] = encoded.y[2]; + encoded_mapped.y[2] = encoded.y[1]; + encoded_mapped.y[3] = encoded.y[0]; + + int bytes = huffman_decode(dst_start, encoded_mapped.y, encoded_size); + char ascii_value = i / 2; + assert(dst_start[0] == ascii_value); + assert(bytes == 1); + } +} + int main() { hpack_huffman_init(); for (int i = 0; i < 100; i++) { - test(); + random_test(); } + values_test(); hpack_huffman_fin(); return 0;
