Repository: trafficserver Updated Branches: refs/heads/master 46edbd72c -> d7170e2d7
TS-3852: Add Huffman Encoder in HPACK This closes #294 Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/d7170e2d Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/d7170e2d Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/d7170e2d Branch: refs/heads/master Commit: d7170e2d7030bb37febeb25e512c20149d86bb1f Parents: 46edbd7 Author: Masaori Koshiba <[email protected]> Authored: Wed Sep 16 18:15:18 2015 -0700 Committer: Bryan Call <[email protected]> Committed: Wed Sep 16 18:15:18 2015 -0700 ---------------------------------------------------------------------- proxy/http2/HuffmanCodec.cc | 50 ++++++++++++++++++++++++++++++++++++ proxy/http2/HuffmanCodec.h | 2 ++ proxy/http2/test_Huffmancode.cc | 31 ++++++++++++++++++++++ 3 files changed, 83 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d7170e2d/proxy/http2/HuffmanCodec.cc ---------------------------------------------------------------------- diff --git a/proxy/http2/HuffmanCodec.cc b/proxy/http2/HuffmanCodec.cc index 020426f..e5b9c80 100644 --- a/proxy/http2/HuffmanCodec.cc +++ b/proxy/http2/HuffmanCodec.cc @@ -391,3 +391,53 @@ huffman_decode(char *dst_start, const uint8_t *src, uint32_t src_len) return dst_end - dst_start; } + +uint8_t * +huffman_encode_append(uint8_t *dst, uint32_t src, int n = 0) +{ + for (int j = 3; j >= n; --j) { + *dst++ = ((src >> (8 * j)) & 255); + } + return dst; +} + +int64_t +huffman_encode(uint8_t *dst_start, const uint8_t *src, uint32_t src_len) +{ + uint8_t *dst = dst_start; + // NOTE: The maximum length of Huffman Code is 30, thus using uint32_t as buffer. + uint32_t buf = 0; + uint32_t remain_bits = 32; + + for (uint32_t i = 0; i < src_len; ++i) { + const uint32_t hex = huffman_table[src[i]].code_as_hex; + const uint32_t bit_len = huffman_table[src[i]].bit_len; + + if (remain_bits > bit_len) { + remain_bits = remain_bits - bit_len; + buf |= hex << remain_bits; + } else if (remain_bits == bit_len) { + buf |= hex; + dst = huffman_encode_append(dst, buf); + remain_bits = 32; + buf = 0; + } else { + buf |= hex >> (bit_len - remain_bits); + dst = huffman_encode_append(dst, buf); + remain_bits = (32 - (bit_len - remain_bits)); + buf = hex << remain_bits; + } + } + + if (buf != 0) { + dst = huffman_encode_append(dst, buf, remain_bits / 8); + } + + // NOTE: Add padding w/ EOS + uint32_t pad_len = remain_bits % 8; + if (pad_len) { + *(dst - 1) |= 0xff >> (8 - pad_len); + } + + return dst - dst_start; +} http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d7170e2d/proxy/http2/HuffmanCodec.h ---------------------------------------------------------------------- diff --git a/proxy/http2/HuffmanCodec.h b/proxy/http2/HuffmanCodec.h index 19b7621..49b5f0c 100644 --- a/proxy/http2/HuffmanCodec.h +++ b/proxy/http2/HuffmanCodec.h @@ -30,5 +30,7 @@ void hpack_huffman_init(); void hpack_huffman_fin(); int64_t huffman_decode(char *dst_start, const uint8_t *src, uint32_t src_len); +uint8_t *huffman_encode_append(uint8_t *dst, uint32_t src, int n); +int64_t huffman_encode(uint8_t *dst_start, const uint8_t *src, uint32_t src_len); #endif /* __HPACK_Huffman_H__ */ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d7170e2d/proxy/http2/test_Huffmancode.cc ---------------------------------------------------------------------- diff --git a/proxy/http2/test_Huffmancode.cc b/proxy/http2/test_Huffmancode.cc index 8c3a19d..8463f93 100644 --- a/proxy/http2/test_Huffmancode.cc +++ b/proxy/http2/test_Huffmancode.cc @@ -25,6 +25,7 @@ #include <stdlib.h> #include <iostream> #include <assert.h> +#include <string.h> using namespace std; @@ -141,6 +142,34 @@ values_test() } } +// NOTE: Test data from "C.6.1 First Response" in RFC 7541. +const static struct { + uint8_t *src; + int64_t src_len; + uint8_t *expect; + int64_t expect_len; +} huffman_encode_test_data[] = { + {(uint8_t *)"302", 3, (uint8_t *) "\x64\x02", 2}, + {(uint8_t *)"private", 7, (uint8_t *) "\xae\xc3\x77\x1a\x4b", 5}, + {(uint8_t *)"Mon, 21 Oct 2013 20:13:21 GMT", 29, + (uint8_t *) "\xd0\x7a\xbe\x94\x10\x54\xd4\x44\xa8\x20\x05\x95\x04\x0b\x81\x66\xe0\x82\xa6\x2d\x1b\xff", 22}, + {(uint8_t *)"https://www.example.com";, 23, (uint8_t *) "\x9d\x29\xad\x17\x18\x63\xc7\x8f\x0b\x97\xc8\xe9\xae\x82\xae\x43\xd3", + 17}}; + +void +encode_test() +{ + for (uint64_t i = 0; i < sizeof(huffman_encode_test_data) / sizeof(huffman_encode_test_data[0]); ++i) { + uint8_t *dst = static_cast<uint8_t *>(malloc(huffman_encode_test_data[i].expect_len)); + int64_t encoded_len = huffman_encode(dst, huffman_encode_test_data[i].src, huffman_encode_test_data[i].src_len); + + assert(encoded_len == huffman_encode_test_data[i].expect_len); + assert(memcmp(huffman_encode_test_data[i].expect, dst, encoded_len) == 0); + + free(dst); + } +} + int main() { @@ -152,5 +181,7 @@ main() values_test(); hpack_huffman_fin(); + + encode_test(); return 0; }
