diff options
Diffstat (limited to 'src/plugins')
| -rw-r--r-- | src/plugins/http/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/plugins/http/extras/mk_huffman_table.py | 416 | ||||
| -rw-r--r-- | src/plugins/http/http2/hpack.c | 297 | ||||
| -rw-r--r-- | src/plugins/http/http2/hpack.h | 76 | ||||
| -rw-r--r-- | src/plugins/http/http2/huffman_table.h | 319 | ||||
| -rw-r--r-- | src/plugins/http/test/http_test.c | 202 |
6 files changed, 1311 insertions, 0 deletions
diff --git a/src/plugins/http/CMakeLists.txt b/src/plugins/http/CMakeLists.txt index ad584821c06..95b5102684a 100644 --- a/src/plugins/http/CMakeLists.txt +++ b/src/plugins/http/CMakeLists.txt @@ -13,6 +13,7 @@ add_vpp_plugin(http SOURCES + http2/hpack.c http.c http_buffer.c http_timer.c diff --git a/src/plugins/http/extras/mk_huffman_table.py b/src/plugins/http/extras/mk_huffman_table.py new file mode 100644 index 00000000000..378544b0dce --- /dev/null +++ b/src/plugins/http/extras/mk_huffman_table.py @@ -0,0 +1,416 @@ +#!/usr/bin/env python3 +from io import StringIO + + +# SPDX-License-Identifier: Apache-2.0 +# Copyright(c) 2025 Cisco Systems, Inc. + + +# e.g. 5 bit code symbol has 8 slots (2^8-5), last 3 bits are irrelevant +def generate_slots(fh, s, cl): + for i in range(1 << 8 - cl): + fh.write(" { 0x%02X, %d },\n" % (s, cl)) + + +# list of code and code length tuples +huff_code_table = [] + +# Huffman code from RFC7541 Appendix B, EOS removed +rfc7541_huffman_code = """\ + ( 0) |11111111|11000 1ff8 [13] + ( 1) |11111111|11111111|1011000 7fffd8 [23] + ( 2) |11111111|11111111|11111110|0010 fffffe2 [28] + ( 3) |11111111|11111111|11111110|0011 fffffe3 [28] + ( 4) |11111111|11111111|11111110|0100 fffffe4 [28] + ( 5) |11111111|11111111|11111110|0101 fffffe5 [28] + ( 6) |11111111|11111111|11111110|0110 fffffe6 [28] + ( 7) |11111111|11111111|11111110|0111 fffffe7 [28] + ( 8) |11111111|11111111|11111110|1000 fffffe8 [28] + ( 9) |11111111|11111111|11101010 ffffea [24] + ( 10) |11111111|11111111|11111111|111100 3ffffffc [30] + ( 11) |11111111|11111111|11111110|1001 fffffe9 [28] + ( 12) |11111111|11111111|11111110|1010 fffffea [28] + ( 13) |11111111|11111111|11111111|111101 3ffffffd [30] + ( 14) |11111111|11111111|11111110|1011 fffffeb [28] + ( 15) |11111111|11111111|11111110|1100 fffffec [28] + ( 16) |11111111|11111111|11111110|1101 fffffed [28] + ( 17) |11111111|11111111|11111110|1110 fffffee [28] + ( 18) |11111111|11111111|11111110|1111 fffffef [28] + ( 19) |11111111|11111111|11111111|0000 ffffff0 [28] + ( 20) |11111111|11111111|11111111|0001 ffffff1 [28] + ( 21) |11111111|11111111|11111111|0010 ffffff2 [28] + ( 22) |11111111|11111111|11111111|111110 3ffffffe [30] + ( 23) |11111111|11111111|11111111|0011 ffffff3 [28] + ( 24) |11111111|11111111|11111111|0100 ffffff4 [28] + ( 25) |11111111|11111111|11111111|0101 ffffff5 [28] + ( 26) |11111111|11111111|11111111|0110 ffffff6 [28] + ( 27) |11111111|11111111|11111111|0111 ffffff7 [28] + ( 28) |11111111|11111111|11111111|1000 ffffff8 [28] + ( 29) |11111111|11111111|11111111|1001 ffffff9 [28] + ( 30) |11111111|11111111|11111111|1010 ffffffa [28] + ( 31) |11111111|11111111|11111111|1011 ffffffb [28] +' ' ( 32) |010100 14 [ 6] +'!' ( 33) |11111110|00 3f8 [10] +'"' ( 34) |11111110|01 3f9 [10] +'#' ( 35) |11111111|1010 ffa [12] +'$' ( 36) |11111111|11001 1ff9 [13] +'%' ( 37) |010101 15 [ 6] +'&' ( 38) |11111000 f8 [ 8] +''' ( 39) |11111111|010 7fa [11] +'(' ( 40) |11111110|10 3fa [10] +')' ( 41) |11111110|11 3fb [10] +'*' ( 42) |11111001 f9 [ 8] +'+' ( 43) |11111111|011 7fb [11] +',' ( 44) |11111010 fa [ 8] +'-' ( 45) |010110 16 [ 6] +'.' ( 46) |010111 17 [ 6] +'/' ( 47) |011000 18 [ 6] +'0' ( 48) |00000 0 [ 5] +'1' ( 49) |00001 1 [ 5] +'2' ( 50) |00010 2 [ 5] +'3' ( 51) |011001 19 [ 6] +'4' ( 52) |011010 1a [ 6] +'5' ( 53) |011011 1b [ 6] +'6' ( 54) |011100 1c [ 6] +'7' ( 55) |011101 1d [ 6] +'8' ( 56) |011110 1e [ 6] +'9' ( 57) |011111 1f [ 6] +':' ( 58) |1011100 5c [ 7] +';' ( 59) |11111011 fb [ 8] +'<' ( 60) |11111111|1111100 7ffc [15] +'=' ( 61) |100000 20 [ 6] +'>' ( 62) |11111111|1011 ffb [12] +'?' ( 63) |11111111|00 3fc [10] +'@' ( 64) |11111111|11010 1ffa [13] +'A' ( 65) |100001 21 [ 6] +'B' ( 66) |1011101 5d [ 7] +'C' ( 67) |1011110 5e [ 7] +'D' ( 68) |1011111 5f [ 7] +'E' ( 69) |1100000 60 [ 7] +'F' ( 70) |1100001 61 [ 7] +'G' ( 71) |1100010 62 [ 7] +'H' ( 72) |1100011 63 [ 7] +'I' ( 73) |1100100 64 [ 7] +'J' ( 74) |1100101 65 [ 7] +'K' ( 75) |1100110 66 [ 7] +'L' ( 76) |1100111 67 [ 7] +'M' ( 77) |1101000 68 [ 7] +'N' ( 78) |1101001 69 [ 7] +'O' ( 79) |1101010 6a [ 7] +'P' ( 80) |1101011 6b [ 7] +'Q' ( 81) |1101100 6c [ 7] +'R' ( 82) |1101101 6d [ 7] +'S' ( 83) |1101110 6e [ 7] +'T' ( 84) |1101111 6f [ 7] +'U' ( 85) |1110000 70 [ 7] +'V' ( 86) |1110001 71 [ 7] +'W' ( 87) |1110010 72 [ 7] +'X' ( 88) |11111100 fc [ 8] +'Y' ( 89) |1110011 73 [ 7] +'Z' ( 90) |11111101 fd [ 8] +'[' ( 91) |11111111|11011 1ffb [13] +'\' ( 92) |11111111|11111110|000 7fff0 [19] +']' ( 93) |11111111|11100 1ffc [13] +'^' ( 94) |11111111|111100 3ffc [14] +'_' ( 95) |100010 22 [ 6] +'`' ( 96) |11111111|1111101 7ffd [15] +'a' ( 97) |00011 3 [ 5] +'b' ( 98) |100011 23 [ 6] +'c' ( 99) |00100 4 [ 5] +'d' (100) |100100 24 [ 6] +'e' (101) |00101 5 [ 5] +'f' (102) |100101 25 [ 6] +'g' (103) |100110 26 [ 6] +'h' (104) |100111 27 [ 6] +'i' (105) |00110 6 [ 5] +'j' (106) |1110100 74 [ 7] +'k' (107) |1110101 75 [ 7] +'l' (108) |101000 28 [ 6] +'m' (109) |101001 29 [ 6] +'n' (110) |101010 2a [ 6] +'o' (111) |00111 7 [ 5] +'p' (112) |101011 2b [ 6] +'q' (113) |1110110 76 [ 7] +'r' (114) |101100 2c [ 6] +'s' (115) |01000 8 [ 5] +'t' (116) |01001 9 [ 5] +'u' (117) |101101 2d [ 6] +'v' (118) |1110111 77 [ 7] +'w' (119) |1111000 78 [ 7] +'x' (120) |1111001 79 [ 7] +'y' (121) |1111010 7a [ 7] +'z' (122) |1111011 7b [ 7] +'{' (123) |11111111|1111110 7ffe [15] +'|' (124) |11111111|100 7fc [11] +'}' (125) |11111111|111101 3ffd [14] +'~' (126) |11111111|11101 1ffd [13] + (127) |11111111|11111111|11111111|1100 ffffffc [28] + (128) |11111111|11111110|0110 fffe6 [20] + (129) |11111111|11111111|010010 3fffd2 [22] + (130) |11111111|11111110|0111 fffe7 [20] + (131) |11111111|11111110|1000 fffe8 [20] + (132) |11111111|11111111|010011 3fffd3 [22] + (133) |11111111|11111111|010100 3fffd4 [22] + (134) |11111111|11111111|010101 3fffd5 [22] + (135) |11111111|11111111|1011001 7fffd9 [23] + (136) |11111111|11111111|010110 3fffd6 [22] + (137) |11111111|11111111|1011010 7fffda [23] + (138) |11111111|11111111|1011011 7fffdb [23] + (139) |11111111|11111111|1011100 7fffdc [23] + (140) |11111111|11111111|1011101 7fffdd [23] + (141) |11111111|11111111|1011110 7fffde [23] + (142) |11111111|11111111|11101011 ffffeb [24] + (143) |11111111|11111111|1011111 7fffdf [23] + (144) |11111111|11111111|11101100 ffffec [24] + (145) |11111111|11111111|11101101 ffffed [24] + (146) |11111111|11111111|010111 3fffd7 [22] + (147) |11111111|11111111|1100000 7fffe0 [23] + (148) |11111111|11111111|11101110 ffffee [24] + (149) |11111111|11111111|1100001 7fffe1 [23] + (150) |11111111|11111111|1100010 7fffe2 [23] + (151) |11111111|11111111|1100011 7fffe3 [23] + (152) |11111111|11111111|1100100 7fffe4 [23] + (153) |11111111|11111110|11100 1fffdc [21] + (154) |11111111|11111111|011000 3fffd8 [22] + (155) |11111111|11111111|1100101 7fffe5 [23] + (156) |11111111|11111111|011001 3fffd9 [22] + (157) |11111111|11111111|1100110 7fffe6 [23] + (158) |11111111|11111111|1100111 7fffe7 [23] + (159) |11111111|11111111|11101111 ffffef [24] + (160) |11111111|11111111|011010 3fffda [22] + (161) |11111111|11111110|11101 1fffdd [21] + (162) |11111111|11111110|1001 fffe9 [20] + (163) |11111111|11111111|011011 3fffdb [22] + (164) |11111111|11111111|011100 3fffdc [22] + (165) |11111111|11111111|1101000 7fffe8 [23] + (166) |11111111|11111111|1101001 7fffe9 [23] + (167) |11111111|11111110|11110 1fffde [21] + (168) |11111111|11111111|1101010 7fffea [23] + (169) |11111111|11111111|011101 3fffdd [22] + (170) |11111111|11111111|011110 3fffde [22] + (171) |11111111|11111111|11110000 fffff0 [24] + (172) |11111111|11111110|11111 1fffdf [21] + (173) |11111111|11111111|011111 3fffdf [22] + (174) |11111111|11111111|1101011 7fffeb [23] + (175) |11111111|11111111|1101100 7fffec [23] + (176) |11111111|11111111|00000 1fffe0 [21] + (177) |11111111|11111111|00001 1fffe1 [21] + (178) |11111111|11111111|100000 3fffe0 [22] + (179) |11111111|11111111|00010 1fffe2 [21] + (180) |11111111|11111111|1101101 7fffed [23] + (181) |11111111|11111111|100001 3fffe1 [22] + (182) |11111111|11111111|1101110 7fffee [23] + (183) |11111111|11111111|1101111 7fffef [23] + (184) |11111111|11111110|1010 fffea [20] + (185) |11111111|11111111|100010 3fffe2 [22] + (186) |11111111|11111111|100011 3fffe3 [22] + (187) |11111111|11111111|100100 3fffe4 [22] + (188) |11111111|11111111|1110000 7ffff0 [23] + (189) |11111111|11111111|100101 3fffe5 [22] + (190) |11111111|11111111|100110 3fffe6 [22] + (191) |11111111|11111111|1110001 7ffff1 [23] + (192) |11111111|11111111|11111000|00 3ffffe0 [26] + (193) |11111111|11111111|11111000|01 3ffffe1 [26] + (194) |11111111|11111110|1011 fffeb [20] + (195) |11111111|11111110|001 7fff1 [19] + (196) |11111111|11111111|100111 3fffe7 [22] + (197) |11111111|11111111|1110010 7ffff2 [23] + (198) |11111111|11111111|101000 3fffe8 [22] + (199) |11111111|11111111|11110110|0 1ffffec [25] + (200) |11111111|11111111|11111000|10 3ffffe2 [26] + (201) |11111111|11111111|11111000|11 3ffffe3 [26] + (202) |11111111|11111111|11111001|00 3ffffe4 [26] + (203) |11111111|11111111|11111011|110 7ffffde [27] + (204) |11111111|11111111|11111011|111 7ffffdf [27] + (205) |11111111|11111111|11111001|01 3ffffe5 [26] + (206) |11111111|11111111|11110001 fffff1 [24] + (207) |11111111|11111111|11110110|1 1ffffed [25] + (208) |11111111|11111110|010 7fff2 [19] + (209) |11111111|11111111|00011 1fffe3 [21] + (210) |11111111|11111111|11111001|10 3ffffe6 [26] + (211) |11111111|11111111|11111100|000 7ffffe0 [27] + (212) |11111111|11111111|11111100|001 7ffffe1 [27] + (213) |11111111|11111111|11111001|11 3ffffe7 [26] + (214) |11111111|11111111|11111100|010 7ffffe2 [27] + (215) |11111111|11111111|11110010 fffff2 [24] + (216) |11111111|11111111|00100 1fffe4 [21] + (217) |11111111|11111111|00101 1fffe5 [21] + (218) |11111111|11111111|11111010|00 3ffffe8 [26] + (219) |11111111|11111111|11111010|01 3ffffe9 [26] + (220) |11111111|11111111|11111111|1101 ffffffd [28] + (221) |11111111|11111111|11111100|011 7ffffe3 [27] + (222) |11111111|11111111|11111100|100 7ffffe4 [27] + (223) |11111111|11111111|11111100|101 7ffffe5 [27] + (224) |11111111|11111110|1100 fffec [20] + (225) |11111111|11111111|11110011 fffff3 [24] + (226) |11111111|11111110|1101 fffed [20] + (227) |11111111|11111111|00110 1fffe6 [21] + (228) |11111111|11111111|101001 3fffe9 [22] + (229) |11111111|11111111|00111 1fffe7 [21] + (230) |11111111|11111111|01000 1fffe8 [21] + (231) |11111111|11111111|1110011 7ffff3 [23] + (232) |11111111|11111111|101010 3fffea [22] + (233) |11111111|11111111|101011 3fffeb [22] + (234) |11111111|11111111|11110111|0 1ffffee [25] + (235) |11111111|11111111|11110111|1 1ffffef [25] + (236) |11111111|11111111|11110100 fffff4 [24] + (237) |11111111|11111111|11110101 fffff5 [24] + (238) |11111111|11111111|11111010|10 3ffffea [26] + (239) |11111111|11111111|1110100 7ffff4 [23] + (240) |11111111|11111111|11111010|11 3ffffeb [26] + (241) |11111111|11111111|11111100|110 7ffffe6 [27] + (242) |11111111|11111111|11111011|00 3ffffec [26] + (243) |11111111|11111111|11111011|01 3ffffed [26] + (244) |11111111|11111111|11111100|111 7ffffe7 [27] + (245) |11111111|11111111|11111101|000 7ffffe8 [27] + (246) |11111111|11111111|11111101|001 7ffffe9 [27] + (247) |11111111|11111111|11111101|010 7ffffea [27] + (248) |11111111|11111111|11111101|011 7ffffeb [27] + (249) |11111111|11111111|11111111|1110 ffffffe [28] + (250) |11111111|11111111|11111101|100 7ffffec [27] + (251) |11111111|11111111|11111101|101 7ffffed [27] + (252) |11111111|11111111|11111101|110 7ffffee [27] + (253) |11111111|11111111|11111101|111 7ffffef [27] + (254) |11111111|11111111|11111110|000 7fffff0 [27] + (255) |11111111|11111111|11111011|10 3ffffee [26]""" + +# parse Huffman code +for line in StringIO(rfc7541_huffman_code): + # we need just last two columns + l = line.rstrip().split(" ") + # len in bits + code_len = l[-1][1:-1].strip() + # code as hex aligned to LSB + code = l[-2].strip() + huff_code_table.append((code_len, code)) + +f = open("../http2/huffman_table.h", "w") +f.write( + """/* SPDX-License-Identifier: Apache-2.0 + * Copyright(c) 2025 Cisco Systems, Inc. + */ + +/* generated by mk_huffman_table.py */ + +#ifndef SRC_PLUGINS_HTTP_HUFFMAN_TABLE_H_ +#define SRC_PLUGINS_HTTP_HUFFMAN_TABLE_H_ + +#include <vppinfra/types.h> + +typedef struct +{ + u8 code_len; + u32 code; +} hpack_huffman_symbol_t; + +static hpack_huffman_symbol_t huff_sym_table[] = { +""" +) + +# encoding table +[f.write(" {" + code[0] + ", 0x" + code[1] + "},\n") for code in huff_code_table] + +f.write( + """}; + +typedef struct +{ + u8 symbol; + u8 code_len; +} hpack_huffman_code_t; + +static hpack_huffman_code_t huff_code_table_fast[] = { +""" +) + +# fast decoding table, symbols with code length from 5 to 8 bits (most of printable ASCII characters) +[generate_slots(f, i, 5) for i, code in enumerate(huff_code_table) if code[0] == "5"] +[generate_slots(f, i, 6) for i, code in enumerate(huff_code_table) if code[0] == "6"] +[generate_slots(f, i, 7) for i, code in enumerate(huff_code_table) if code[0] == "7"] +[generate_slots(f, i, 8) for i, code in enumerate(huff_code_table) if code[0] == "8"] + +# last 2 entries are longer codes prefixes, code_len set to 0 +f.write(" { 0x00, 0 },\n") +f.write(" { 0x00, 0 },\n") + +f.write( + """}; + +typedef struct +{ + u32 first_code; + u8 code_len; + u8 symbols[29]; +} hpack_huffman_group_t; + +/* clang-format off */ + +static hpack_huffman_group_t huff_code_table_slow[] = { +""" +) +for i in range(10, 31): + symbols = [ + (symbol, code[1]) + for symbol, code in enumerate(huff_code_table) + if code[0] == str(i) + ] + if symbols: + _, first_code = symbols[0] + f.write(" {\n 0x" + first_code + ", /* first_code */\n") + f.write(" " + str(i) + ", /* code_len */\n") + f.write(" {\n ") + [f.write(" 0x%02X," % s) for s, c in symbols[:10]] + if len(symbols) > 10: + f.write("\n ") + [f.write(" 0x%02X," % s) for s, c in symbols[10:20]] + if len(symbols) > 20: + f.write("\n ") + [f.write(" 0x%02X," % s) for s, c in symbols[20:30]] + f.write("\n } /* symbols */\n },\n") + +f.write( + """}; + +/* clang format-on */ + +always_inline hpack_huffman_group_t * +hpack_huffman_get_group (u32 value) +{ +""" +) + +index = 0 + +symbols = [ + (symbol, code[1]) for symbol, code in enumerate(huff_code_table) if code[0] == "10" +] +_, last_code = symbols[-1] +boundary = (int(last_code, 16) + 1) << 22 +f.write(" if (value < 0x%X)\n" % boundary) +f.write(" return &huff_code_table_slow[%d];\n" % index) +index += 1 + +for i in range(11, 30): + symbols = [ + (symbol, code[1]) + for symbol, code in enumerate(huff_code_table) + if code[0] == str(i) + ] + if symbols: + _, last_code = symbols[-1] + boundary = (int(last_code, 16) + 1) << (32 - i) + f.write(" else if (value < 0x%X)\n" % boundary) + f.write(" return &huff_code_table_slow[%d];\n" % index) + index += 1 + +f.write(" else\n") +f.write(" return &huff_code_table_slow[%d];\n" % index) + +f.write( + """} + +#endif /* SRC_PLUGINS_HTTP_HUFFMAN_TABLE_H_ */ +""" +) + +f.close() diff --git a/src/plugins/http/http2/hpack.c b/src/plugins/http/http2/hpack.c new file mode 100644 index 00000000000..f279bd9f1b8 --- /dev/null +++ b/src/plugins/http/http2/hpack.c @@ -0,0 +1,297 @@ +/* SPDX-License-Identifier: Apache-2.0 + * Copyright(c) 2025 Cisco Systems, Inc. + */ + +#include <vppinfra/error.h> +#include <http/http2/hpack.h> +#include <http/http2/huffman_table.h> + +__clib_export uword +hpack_decode_int (u8 **src, u8 *end, u8 prefix_len) +{ + uword value, new_value; + u8 *p, shift = 0, byte; + u16 prefix_max; + + ASSERT (*src < end); + ASSERT (prefix_len >= 1 && prefix_len <= 8); + + p = *src; + prefix_max = (1 << prefix_len) - 1; + value = *p & (u8) prefix_max; + p++; + /* if integer value is less than 2^prefix_len-1 it's encoded within prefix */ + if (value != prefix_max) + { + *src = p; + return value; + } + + while (p != end) + { + byte = *p; + p++; + new_value = value + ((uword) (byte & 0x7F) << shift); + shift += 7; + /* check for overflow */ + if (new_value < value) + return HPACK_INVALID_INT; + value = new_value; + /* MSB of the last byte is zero */ + if ((byte & 0x80) == 0) + { + *src = p; + return value; + } + } + + return HPACK_INVALID_INT; +} + +int +hpack_decode_huffman (u8 **src, u8 *end, u8 **buf, uword *buf_len) +{ + u64 accumulator = 0; + u8 accumulator_len = 0; + u8 *p; + hpack_huffman_code_t *code; + + p = *src; + while (1) + { + /* out of space? */ + if (*buf_len == 0) + return -1; + /* refill */ + while (p < end && accumulator_len <= 56) + { + accumulator <<= 8; + accumulator_len += 8; + accumulator |= (u64) *p++; + } + /* first try short codes (5 - 8 bits) */ + code = + &huff_code_table_fast[(u8) (accumulator >> (accumulator_len - 8))]; + /* zero code length mean no luck */ + if (PREDICT_TRUE (code->code_len)) + { + **buf = code->symbol; + (*buf)++; + (*buf_len)--; + accumulator_len -= code->code_len; + } + else + { + /* slow path / long codes (10 - 30 bits) */ + u32 tmp; + /* group boundaries are aligned to 32 bits */ + if (accumulator_len < 32) + tmp = accumulator << (32 - accumulator_len); + else + tmp = accumulator >> (accumulator_len - 32); + /* figure out which interval code falls into, this is possible + * because HPACK use canonical Huffman codes + * see Schwartz, E. and B. Kallick, “Generating a canonical prefix + * encoding” + */ + hpack_huffman_group_t *hg = hpack_huffman_get_group (tmp); + /* trim code to correct length */ + u32 code = (accumulator >> (accumulator_len - hg->code_len)) & + ((1 << hg->code_len) - 1); + /* find symbol in the list */ + **buf = hg->symbols[code - hg->first_code]; + (*buf)++; + (*buf_len)--; + accumulator_len -= hg->code_len; + } + /* all done */ + if (p == end && accumulator_len < 8) + { + /* there might be one more symbol encoded with short code */ + if (accumulator_len >= 5) + { + /* first check EOF case */ + if (((1 << accumulator_len) - 1) == + (accumulator & ((1 << accumulator_len) - 1))) + break; + + /* out of space? */ + if (*buf_len == 0) + return -1; + + /* if bogus EOF check bellow will fail */ + code = &huff_code_table_fast[(u8) (accumulator + << (8 - accumulator_len))]; + **buf = code->symbol; + (*buf)++; + (*buf_len)--; + accumulator_len -= code->code_len; + /* end at byte boundary? */ + if (accumulator_len == 0) + break; + } + /* we must end with EOF here */ + if (((1 << accumulator_len) - 1) != + (accumulator & ((1 << accumulator_len) - 1))) + return -1; + break; + } + } + return 0; +} + +__clib_export int +hpack_decode_string (u8 **src, u8 *end, u8 **buf, uword *buf_len) +{ + u8 *p, is_huffman; + uword len; + + ASSERT (*src < end); + + p = *src; + /* H flag in first bit */ + is_huffman = *p & 0x80; + + /* length is integer with 7 bit prefix */ + len = hpack_decode_int (&p, end, 7); + if (PREDICT_FALSE (len == HPACK_INVALID_INT)) + return -1; + + /* do we have everything? */ + if (len > (end - p)) + return -1; + + if (is_huffman) + { + *src = (p + len); + return hpack_decode_huffman (&p, p + len, buf, buf_len); + } + else + { + /* enough space? */ + if (len > *buf_len) + return -1; + + clib_memcpy (*buf, p, len); + *buf_len -= len; + *buf += len; + *src = (p + len); + return 0; + } +} + +__clib_export u8 * +hpack_encode_int (u8 *dst, uword value, u8 prefix_len) +{ + u16 prefix_max; + + ASSERT (prefix_len >= 1 && prefix_len <= 8); + + prefix_max = (1 << prefix_len) - 1; + + /* if integer value is less than 2^prefix_len-1 it's encoded within prefix */ + if (value < prefix_max) + { + *dst++ |= (u8) value; + return dst; + } + + /* otherwise all bits of the prefix are set to 1 */ + *dst++ |= (u8) prefix_max; + /* and the value is decreased by 2^prefix_len-1 */ + value -= prefix_max; + /* MSB of each byte is used as continuation flag */ + for (; value >= 0x80; value >>= 7) + *dst++ = 0x80 | (value & 0x7F); + /* except for the last byte */ + *dst++ = (u8) value; + + return dst; +} + +uword +hpack_huffman_encoded_len (const u8 *value, uword value_len) +{ + uword len = 0; + u8 *end; + hpack_huffman_symbol_t *sym; + + end = (u8 *) value + value_len; + while (value != end) + { + sym = &huff_sym_table[*value++]; + len += sym->code_len; + } + /* round up to byte boundary */ + return (len + 7) / 8; +} + +u8 * +hpack_encode_huffman (u8 *dst, const u8 *value, uword value_len) +{ + u8 *end; + hpack_huffman_symbol_t *sym; + u8 accumulator_len = 40; /* leftover (1 byte) + max code_len (4 bytes) */ + u64 accumulator = 0; /* to fit leftover and current code */ + + end = (u8 *) value + value_len; + + while (value != end) + { + sym = &huff_sym_table[*value++]; + /* add current code to leftover of previous one */ + accumulator |= (u64) sym->code << (accumulator_len - sym->code_len); + accumulator_len -= sym->code_len; + /* write only fully occupied bytes (max 4) */ + switch (accumulator_len) + { + case 1 ... 8: +#define WRITE_BYTE() \ + *dst = (u8) (accumulator >> 32); \ + accumulator_len += 8; \ + accumulator <<= 8; \ + dst++; + WRITE_BYTE (); + case 9 ... 16: + WRITE_BYTE (); + case 17 ... 24: + WRITE_BYTE (); + case 25 ... 32: + WRITE_BYTE (); + default: + break; + } + } + + /* padding (0-7 bits)*/ + ASSERT (accumulator_len > 32 && accumulator_len <= 40); + if (accumulator_len != 40) + { + accumulator |= (u64) 0x7F << (accumulator_len - 7); + *dst = (u8) (accumulator >> 32); + dst++; + } + return dst; +} + +__clib_export u8 * +hpack_encode_string (u8 *dst, const u8 *value, uword value_len) +{ + uword huff_len; + + huff_len = hpack_huffman_encoded_len (value, value_len); + /* raw bytes might take fewer bytes */ + if (huff_len >= value_len) + { + *dst = 0; /* clear H flag */ + dst = hpack_encode_int (dst, value_len, 7); + clib_memcpy (dst, value, value_len); + return dst + value_len; + } + + *dst = 0x80; /* set H flag */ + dst = hpack_encode_int (dst, huff_len, 7); + dst = hpack_encode_huffman (dst, value, value_len); + + return dst; +} diff --git a/src/plugins/http/http2/hpack.h b/src/plugins/http/http2/hpack.h new file mode 100644 index 00000000000..6bd6a3c25f1 --- /dev/null +++ b/src/plugins/http/http2/hpack.h @@ -0,0 +1,76 @@ +/* SPDX-License-Identifier: Apache-2.0 + * Copyright(c) 2025 Cisco Systems, Inc. + */ + +#ifndef SRC_PLUGINS_HTTP_HPACK_H_ +#define SRC_PLUGINS_HTTP_HPACK_H_ + +#include <vppinfra/types.h> + +#define HPACK_INVALID_INT CLIB_UWORD_MAX +#if uword_bits == 64 +#define HPACK_ENCODED_INT_MAX_LEN 10 +#else +#define HPACK_ENCODED_INT_MAX_LEN 6 +#endif + +/** + * Decode unsigned variable-length integer (RFC7541 section 5.1) + * + * @param src Pointer to source buffer which will be advanced + * @param end End of the source buffer + * @param prefix_len Number of bits of the prefix (between 1 and 8) + * + * @return Decoded integer or @c HPACK_INVALID_INT in case of error + */ +uword hpack_decode_int (u8 **src, u8 *end, u8 prefix_len); + +/** + * Encode given value as unsigned variable-length integer (RFC7541 section 5.1) + * + * @param dst Pointer to destination buffer, should have enough space + * @param value Integer value to encode (up to @c CLIB_WORD_MAX) + * @param prefix_len Number of bits of the prefix (between 1 and 8) + * + * @return Advanced pointer to the destination buffer + * + * @note Encoded integer will take maximum @c HPACK_ENCODED_INT_MAX_LEN bytes + */ +u8 *hpack_encode_int (u8 *dst, uword value, u8 prefix_len); + +/** + * Decode + * + * @param src Pointer to source buffer which will be advanced + * @param end End of the source buffer + * @param buf Pointer to the buffer where string is decoded which will be + * advanced by number of written bytes + * @param buf_len Length the buffer, will be decreased + * + * @return @c 0 on success. + */ +int hpack_decode_huffman (u8 **src, u8 *end, u8 **buf, uword *buf_len); + +/** + * Encode given string in Huffman codes. + * + * @param dst Pointer to destination buffer, should have enough space + * @param value String to encode + * @param value_len Length of the string + * + * @return Advanced pointer to the destination buffer + */ +u8 *hpack_encode_huffman (u8 *dst, const u8 *value, uword value_len); + +/** + * Number of bytes required to encode given string in Huffman codes + * + * @param value Pointer to buffer with string to encode + * @param value_len Length of the string + * + * @return number of bytes required to encode string in Huffman codes, round up + * to byte boundary + */ +uword hpack_huffman_encoded_len (const u8 *value, uword value_len); + +#endif /* SRC_PLUGINS_HTTP_HPACK_H_ */ diff --git a/src/plugins/http/http2/huffman_table.h b/src/plugins/http/http2/huffman_table.h new file mode 100644 index 00000000000..66afffbc54a --- /dev/null +++ b/src/plugins/http/http2/huffman_table.h @@ -0,0 +1,319 @@ +/* SPDX-License-Identifier: Apache-2.0 + * Copyright(c) 2025 Cisco Systems, Inc. + */ + +/* generated by mk_huffman_table.py */ + +#ifndef SRC_PLUGINS_HTTP_HUFFMAN_TABLE_H_ +#define SRC_PLUGINS_HTTP_HUFFMAN_TABLE_H_ + +#include <vppinfra/types.h> + +typedef struct +{ + u8 code_len; + u32 code; +} hpack_huffman_symbol_t; + +static hpack_huffman_symbol_t huff_sym_table[] = { + { 13, 0x1ff8 }, { 23, 0x7fffd8 }, { 28, 0xfffffe2 }, { 28, 0xfffffe3 }, + { 28, 0xfffffe4 }, { 28, 0xfffffe5 }, { 28, 0xfffffe6 }, { 28, 0xfffffe7 }, + { 28, 0xfffffe8 }, { 24, 0xffffea }, { 30, 0x3ffffffc }, { 28, 0xfffffe9 }, + { 28, 0xfffffea }, { 30, 0x3ffffffd }, { 28, 0xfffffeb }, { 28, 0xfffffec }, + { 28, 0xfffffed }, { 28, 0xfffffee }, { 28, 0xfffffef }, { 28, 0xffffff0 }, + { 28, 0xffffff1 }, { 28, 0xffffff2 }, { 30, 0x3ffffffe }, { 28, 0xffffff3 }, + { 28, 0xffffff4 }, { 28, 0xffffff5 }, { 28, 0xffffff6 }, { 28, 0xffffff7 }, + { 28, 0xffffff8 }, { 28, 0xffffff9 }, { 28, 0xffffffa }, { 28, 0xffffffb }, + { 6, 0x14 }, { 10, 0x3f8 }, { 10, 0x3f9 }, { 12, 0xffa }, + { 13, 0x1ff9 }, { 6, 0x15 }, { 8, 0xf8 }, { 11, 0x7fa }, + { 10, 0x3fa }, { 10, 0x3fb }, { 8, 0xf9 }, { 11, 0x7fb }, + { 8, 0xfa }, { 6, 0x16 }, { 6, 0x17 }, { 6, 0x18 }, + { 5, 0x0 }, { 5, 0x1 }, { 5, 0x2 }, { 6, 0x19 }, + { 6, 0x1a }, { 6, 0x1b }, { 6, 0x1c }, { 6, 0x1d }, + { 6, 0x1e }, { 6, 0x1f }, { 7, 0x5c }, { 8, 0xfb }, + { 15, 0x7ffc }, { 6, 0x20 }, { 12, 0xffb }, { 10, 0x3fc }, + { 13, 0x1ffa }, { 6, 0x21 }, { 7, 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, 0x6f }, { 7, 0x70 }, { 7, 0x71 }, { 7, 0x72 }, + { 8, 0xfc }, { 7, 0x73 }, { 8, 0xfd }, { 13, 0x1ffb }, + { 19, 0x7fff0 }, { 13, 0x1ffc }, { 14, 0x3ffc }, { 6, 0x22 }, + { 15, 0x7ffd }, { 5, 0x3 }, { 6, 0x23 }, { 5, 0x4 }, + { 6, 0x24 }, { 5, 0x5 }, { 6, 0x25 }, { 6, 0x26 }, + { 6, 0x27 }, { 5, 0x6 }, { 7, 0x74 }, { 7, 0x75 }, + { 6, 0x28 }, { 6, 0x29 }, { 6, 0x2a }, { 5, 0x7 }, + { 6, 0x2b }, { 7, 0x76 }, { 6, 0x2c }, { 5, 0x8 }, + { 5, 0x9 }, { 6, 0x2d }, { 7, 0x77 }, { 7, 0x78 }, + { 7, 0x79 }, { 7, 0x7a }, { 7, 0x7b }, { 15, 0x7ffe }, + { 11, 0x7fc }, { 14, 0x3ffd }, { 13, 0x1ffd }, { 28, 0xffffffc }, + { 20, 0xfffe6 }, { 22, 0x3fffd2 }, { 20, 0xfffe7 }, { 20, 0xfffe8 }, + { 22, 0x3fffd3 }, { 22, 0x3fffd4 }, { 22, 0x3fffd5 }, { 23, 0x7fffd9 }, + { 22, 0x3fffd6 }, { 23, 0x7fffda }, { 23, 0x7fffdb }, { 23, 0x7fffdc }, + { 23, 0x7fffdd }, { 23, 0x7fffde }, { 24, 0xffffeb }, { 23, 0x7fffdf }, + { 24, 0xffffec }, { 24, 0xffffed }, { 22, 0x3fffd7 }, { 23, 0x7fffe0 }, + { 24, 0xffffee }, { 23, 0x7fffe1 }, { 23, 0x7fffe2 }, { 23, 0x7fffe3 }, + { 23, 0x7fffe4 }, { 21, 0x1fffdc }, { 22, 0x3fffd8 }, { 23, 0x7fffe5 }, + { 22, 0x3fffd9 }, { 23, 0x7fffe6 }, { 23, 0x7fffe7 }, { 24, 0xffffef }, + { 22, 0x3fffda }, { 21, 0x1fffdd }, { 20, 0xfffe9 }, { 22, 0x3fffdb }, + { 22, 0x3fffdc }, { 23, 0x7fffe8 }, { 23, 0x7fffe9 }, { 21, 0x1fffde }, + { 23, 0x7fffea }, { 22, 0x3fffdd }, { 22, 0x3fffde }, { 24, 0xfffff0 }, + { 21, 0x1fffdf }, { 22, 0x3fffdf }, { 23, 0x7fffeb }, { 23, 0x7fffec }, + { 21, 0x1fffe0 }, { 21, 0x1fffe1 }, { 22, 0x3fffe0 }, { 21, 0x1fffe2 }, + { 23, 0x7fffed }, { 22, 0x3fffe1 }, { 23, 0x7fffee }, { 23, 0x7fffef }, + { 20, 0xfffea }, { 22, 0x3fffe2 }, { 22, 0x3fffe3 }, { 22, 0x3fffe4 }, + { 23, 0x7ffff0 }, { 22, 0x3fffe5 }, { 22, 0x3fffe6 }, { 23, 0x7ffff1 }, + { 26, 0x3ffffe0 }, { 26, 0x3ffffe1 }, { 20, 0xfffeb }, { 19, 0x7fff1 }, + { 22, 0x3fffe7 }, { 23, 0x7ffff2 }, { 22, 0x3fffe8 }, { 25, 0x1ffffec }, + { 26, 0x3ffffe2 }, { 26, 0x3ffffe3 }, { 26, 0x3ffffe4 }, { 27, 0x7ffffde }, + { 27, 0x7ffffdf }, { 26, 0x3ffffe5 }, { 24, 0xfffff1 }, { 25, 0x1ffffed }, + { 19, 0x7fff2 }, { 21, 0x1fffe3 }, { 26, 0x3ffffe6 }, { 27, 0x7ffffe0 }, + { 27, 0x7ffffe1 }, { 26, 0x3ffffe7 }, { 27, 0x7ffffe2 }, { 24, 0xfffff2 }, + { 21, 0x1fffe4 }, { 21, 0x1fffe5 }, { 26, 0x3ffffe8 }, { 26, 0x3ffffe9 }, + { 28, 0xffffffd }, { 27, 0x7ffffe3 }, { 27, 0x7ffffe4 }, { 27, 0x7ffffe5 }, + { 20, 0xfffec }, { 24, 0xfffff3 }, { 20, 0xfffed }, { 21, 0x1fffe6 }, + { 22, 0x3fffe9 }, { 21, 0x1fffe7 }, { 21, 0x1fffe8 }, { 23, 0x7ffff3 }, + { 22, 0x3fffea }, { 22, 0x3fffeb }, { 25, 0x1ffffee }, { 25, 0x1ffffef }, + { 24, 0xfffff4 }, { 24, 0xfffff5 }, { 26, 0x3ffffea }, { 23, 0x7ffff4 }, + { 26, 0x3ffffeb }, { 27, 0x7ffffe6 }, { 26, 0x3ffffec }, { 26, 0x3ffffed }, + { 27, 0x7ffffe7 }, { 27, 0x7ffffe8 }, { 27, 0x7ffffe9 }, { 27, 0x7ffffea }, + { 27, 0x7ffffeb }, { 28, 0xffffffe }, { 27, 0x7ffffec }, { 27, 0x7ffffed }, + { 27, 0x7ffffee }, { 27, 0x7ffffef }, { 27, 0x7fffff0 }, { 26, 0x3ffffee }, +}; + +typedef struct +{ + u8 symbol; + u8 code_len; +} hpack_huffman_code_t; + +static hpack_huffman_code_t huff_code_table_fast[] = { + { 0x30, 5 }, { 0x30, 5 }, { 0x30, 5 }, { 0x30, 5 }, { 0x30, 5 }, { 0x30, 5 }, + { 0x30, 5 }, { 0x30, 5 }, { 0x31, 5 }, { 0x31, 5 }, { 0x31, 5 }, { 0x31, 5 }, + { 0x31, 5 }, { 0x31, 5 }, { 0x31, 5 }, { 0x31, 5 }, { 0x32, 5 }, { 0x32, 5 }, + { 0x32, 5 }, { 0x32, 5 }, { 0x32, 5 }, { 0x32, 5 }, { 0x32, 5 }, { 0x32, 5 }, + { 0x61, 5 }, { 0x61, 5 }, { 0x61, 5 }, { 0x61, 5 }, { 0x61, 5 }, { 0x61, 5 }, + { 0x61, 5 }, { 0x61, 5 }, { 0x63, 5 }, { 0x63, 5 }, { 0x63, 5 }, { 0x63, 5 }, + { 0x63, 5 }, { 0x63, 5 }, { 0x63, 5 }, { 0x63, 5 }, { 0x65, 5 }, { 0x65, 5 }, + { 0x65, 5 }, { 0x65, 5 }, { 0x65, 5 }, { 0x65, 5 }, { 0x65, 5 }, { 0x65, 5 }, + { 0x69, 5 }, { 0x69, 5 }, { 0x69, 5 }, { 0x69, 5 }, { 0x69, 5 }, { 0x69, 5 }, + { 0x69, 5 }, { 0x69, 5 }, { 0x6F, 5 }, { 0x6F, 5 }, { 0x6F, 5 }, { 0x6F, 5 }, + { 0x6F, 5 }, { 0x6F, 5 }, { 0x6F, 5 }, { 0x6F, 5 }, { 0x73, 5 }, { 0x73, 5 }, + { 0x73, 5 }, { 0x73, 5 }, { 0x73, 5 }, { 0x73, 5 }, { 0x73, 5 }, { 0x73, 5 }, + { 0x74, 5 }, { 0x74, 5 }, { 0x74, 5 }, { 0x74, 5 }, { 0x74, 5 }, { 0x74, 5 }, + { 0x74, 5 }, { 0x74, 5 }, { 0x20, 6 }, { 0x20, 6 }, { 0x20, 6 }, { 0x20, 6 }, + { 0x25, 6 }, { 0x25, 6 }, { 0x25, 6 }, { 0x25, 6 }, { 0x2D, 6 }, { 0x2D, 6 }, + { 0x2D, 6 }, { 0x2D, 6 }, { 0x2E, 6 }, { 0x2E, 6 }, { 0x2E, 6 }, { 0x2E, 6 }, + { 0x2F, 6 }, { 0x2F, 6 }, { 0x2F, 6 }, { 0x2F, 6 }, { 0x33, 6 }, { 0x33, 6 }, + { 0x33, 6 }, { 0x33, 6 }, { 0x34, 6 }, { 0x34, 6 }, { 0x34, 6 }, { 0x34, 6 }, + { 0x35, 6 }, { 0x35, 6 }, { 0x35, 6 }, { 0x35, 6 }, { 0x36, 6 }, { 0x36, 6 }, + { 0x36, 6 }, { 0x36, 6 }, { 0x37, 6 }, { 0x37, 6 }, { 0x37, 6 }, { 0x37, 6 }, + { 0x38, 6 }, { 0x38, 6 }, { 0x38, 6 }, { 0x38, 6 }, { 0x39, 6 }, { 0x39, 6 }, + { 0x39, 6 }, { 0x39, 6 }, { 0x3D, 6 }, { 0x3D, 6 }, { 0x3D, 6 }, { 0x3D, 6 }, + { 0x41, 6 }, { 0x41, 6 }, { 0x41, 6 }, { 0x41, 6 }, { 0x5F, 6 }, { 0x5F, 6 }, + { 0x5F, 6 }, { 0x5F, 6 }, { 0x62, 6 }, { 0x62, 6 }, { 0x62, 6 }, { 0x62, 6 }, + { 0x64, 6 }, { 0x64, 6 }, { 0x64, 6 }, { 0x64, 6 }, { 0x66, 6 }, { 0x66, 6 }, + { 0x66, 6 }, { 0x66, 6 }, { 0x67, 6 }, { 0x67, 6 }, { 0x67, 6 }, { 0x67, 6 }, + { 0x68, 6 }, { 0x68, 6 }, { 0x68, 6 }, { 0x68, 6 }, { 0x6C, 6 }, { 0x6C, 6 }, + { 0x6C, 6 }, { 0x6C, 6 }, { 0x6D, 6 }, { 0x6D, 6 }, { 0x6D, 6 }, { 0x6D, 6 }, + { 0x6E, 6 }, { 0x6E, 6 }, { 0x6E, 6 }, { 0x6E, 6 }, { 0x70, 6 }, { 0x70, 6 }, + { 0x70, 6 }, { 0x70, 6 }, { 0x72, 6 }, { 0x72, 6 }, { 0x72, 6 }, { 0x72, 6 }, + { 0x75, 6 }, { 0x75, 6 }, { 0x75, 6 }, { 0x75, 6 }, { 0x3A, 7 }, { 0x3A, 7 }, + { 0x42, 7 }, { 0x42, 7 }, { 0x43, 7 }, { 0x43, 7 }, { 0x44, 7 }, { 0x44, 7 }, + { 0x45, 7 }, { 0x45, 7 }, { 0x46, 7 }, { 0x46, 7 }, { 0x47, 7 }, { 0x47, 7 }, + { 0x48, 7 }, { 0x48, 7 }, { 0x49, 7 }, { 0x49, 7 }, { 0x4A, 7 }, { 0x4A, 7 }, + { 0x4B, 7 }, { 0x4B, 7 }, { 0x4C, 7 }, { 0x4C, 7 }, { 0x4D, 7 }, { 0x4D, 7 }, + { 0x4E, 7 }, { 0x4E, 7 }, { 0x4F, 7 }, { 0x4F, 7 }, { 0x50, 7 }, { 0x50, 7 }, + { 0x51, 7 }, { 0x51, 7 }, { 0x52, 7 }, { 0x52, 7 }, { 0x53, 7 }, { 0x53, 7 }, + { 0x54, 7 }, { 0x54, 7 }, { 0x55, 7 }, { 0x55, 7 }, { 0x56, 7 }, { 0x56, 7 }, + { 0x57, 7 }, { 0x57, 7 }, { 0x59, 7 }, { 0x59, 7 }, { 0x6A, 7 }, { 0x6A, 7 }, + { 0x6B, 7 }, { 0x6B, 7 }, { 0x71, 7 }, { 0x71, 7 }, { 0x76, 7 }, { 0x76, 7 }, + { 0x77, 7 }, { 0x77, 7 }, { 0x78, 7 }, { 0x78, 7 }, { 0x79, 7 }, { 0x79, 7 }, + { 0x7A, 7 }, { 0x7A, 7 }, { 0x26, 8 }, { 0x2A, 8 }, { 0x2C, 8 }, { 0x3B, 8 }, + { 0x58, 8 }, { 0x5A, 8 }, { 0x00, 0 }, { 0x00, 0 }, +}; + +typedef struct +{ + u32 first_code; + u8 code_len; + u8 symbols[29]; +} hpack_huffman_group_t; + +/* clang-format off */ + +static hpack_huffman_group_t huff_code_table_slow[] = { + { + 0x3f8, /* first_code */ + 10, /* code_len */ + { + 0x21, 0x22, 0x28, 0x29, 0x3F, + } /* symbols */ + }, + { + 0x7fa, /* first_code */ + 11, /* code_len */ + { + 0x27, 0x2B, 0x7C, + } /* symbols */ + }, + { + 0xffa, /* first_code */ + 12, /* code_len */ + { + 0x23, 0x3E, + } /* symbols */ + }, + { + 0x1ff8, /* first_code */ + 13, /* code_len */ + { + 0x00, 0x24, 0x40, 0x5B, 0x5D, 0x7E, + } /* symbols */ + }, + { + 0x3ffc, /* first_code */ + 14, /* code_len */ + { + 0x5E, 0x7D, + } /* symbols */ + }, + { + 0x7ffc, /* first_code */ + 15, /* code_len */ + { + 0x3C, 0x60, 0x7B, + } /* symbols */ + }, + { + 0x7fff0, /* first_code */ + 19, /* code_len */ + { + 0x5C, 0xC3, 0xD0, + } /* symbols */ + }, + { + 0xfffe6, /* first_code */ + 20, /* code_len */ + { + 0x80, 0x82, 0x83, 0xA2, 0xB8, 0xC2, 0xE0, 0xE2, + } /* symbols */ + }, + { + 0x1fffdc, /* first_code */ + 21, /* code_len */ + { + 0x99, 0xA1, 0xA7, 0xAC, 0xB0, 0xB1, 0xB3, 0xD1, 0xD8, 0xD9, + 0xE3, 0xE5, 0xE6, + } /* symbols */ + }, + { + 0x3fffd2, /* first_code */ + 22, /* code_len */ + { + 0x81, 0x84, 0x85, 0x86, 0x88, 0x92, 0x9A, 0x9C, 0xA0, 0xA3, + 0xA4, 0xA9, 0xAA, 0xAD, 0xB2, 0xB5, 0xB9, 0xBA, 0xBB, 0xBD, + 0xBE, 0xC4, 0xC6, 0xE4, 0xE8, 0xE9, + } /* symbols */ + }, + { + 0x7fffd8, /* first_code */ + 23, /* code_len */ + { + 0x01, 0x87, 0x89, 0x8A, 0x8B, 0x8C, 0x8D, 0x8F, 0x93, 0x95, + 0x96, 0x97, 0x98, 0x9B, 0x9D, 0x9E, 0xA5, 0xA6, 0xA8, 0xAE, + 0xAF, 0xB4, 0xB6, 0xB7, 0xBC, 0xBF, 0xC5, 0xE7, 0xEF, + } /* symbols */ + }, + { + 0xffffea, /* first_code */ + 24, /* code_len */ + { + 0x09, 0x8E, 0x90, 0x91, 0x94, 0x9F, 0xAB, 0xCE, 0xD7, 0xE1, + 0xEC, 0xED, + } /* symbols */ + }, + { + 0x1ffffec, /* first_code */ + 25, /* code_len */ + { + 0xC7, 0xCF, 0xEA, 0xEB, + } /* symbols */ + }, + { + 0x3ffffe0, /* first_code */ + 26, /* code_len */ + { + 0xC0, 0xC1, 0xC8, 0xC9, 0xCA, 0xCD, 0xD2, 0xD5, 0xDA, 0xDB, + 0xEE, 0xF0, 0xF2, 0xF3, 0xFF, + } /* symbols */ + }, + { + 0x7ffffde, /* first_code */ + 27, /* code_len */ + { + 0xCB, 0xCC, 0xD3, 0xD4, 0xD6, 0xDD, 0xDE, 0xDF, 0xF1, 0xF4, + 0xF5, 0xF6, 0xF7, 0xF8, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, + } /* symbols */ + }, + { + 0xfffffe2, /* first_code */ + 28, /* code_len */ + { + 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x0B, 0x0C, 0x0E, + 0x0F, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x17, 0x18, 0x19, + 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x1F, 0x7F, 0xDC, 0xF9, + } /* symbols */ + }, + { + 0x3ffffffc, /* first_code */ + 30, /* code_len */ + { + 0x0A, 0x0D, 0x16, + } /* symbols */ + }, +}; + +/* clang format-on */ + +always_inline hpack_huffman_group_t * +hpack_huffman_get_group (u32 value) +{ + if (value < 0xFF400000) + return &huff_code_table_slow[0]; + else if (value < 0xFFA00000) + return &huff_code_table_slow[1]; + else if (value < 0xFFC00000) + return &huff_code_table_slow[2]; + else if (value < 0xFFF00000) + return &huff_code_table_slow[3]; + else if (value < 0xFFF80000) + return &huff_code_table_slow[4]; + else if (value < 0xFFFE0000) + return &huff_code_table_slow[5]; + else if (value < 0xFFFE6000) + return &huff_code_table_slow[6]; + else if (value < 0xFFFEE000) + return &huff_code_table_slow[7]; + else if (value < 0xFFFF4800) + return &huff_code_table_slow[8]; + else if (value < 0xFFFFB000) + return &huff_code_table_slow[9]; + else if (value < 0xFFFFEA00) + return &huff_code_table_slow[10]; + else if (value < 0xFFFFF600) + return &huff_code_table_slow[11]; + else if (value < 0xFFFFF800) + return &huff_code_table_slow[12]; + else if (value < 0xFFFFFBC0) + return &huff_code_table_slow[13]; + else if (value < 0xFFFFFE20) + return &huff_code_table_slow[14]; + else if (value < 0xFFFFFFF0) + return &huff_code_table_slow[15]; + else + return &huff_code_table_slow[16]; +} + +#endif /* SRC_PLUGINS_HTTP_HUFFMAN_TABLE_H_ */ diff --git a/src/plugins/http/test/http_test.c b/src/plugins/http/test/http_test.c index bfaa285eb35..04db580cb59 100644 --- a/src/plugins/http/test/http_test.c +++ b/src/plugins/http/test/http_test.c @@ -6,6 +6,7 @@ #include <vpp/app/version.h> #include <http/http.h> #include <http/http_header_names.h> +#include <http/http2/hpack.h> #define HTTP_TEST_I(_cond, _comment, _args...) \ ({ \ @@ -533,6 +534,203 @@ http_test_http_header_table (vlib_main_t *vm) return 0; } +static int +http_test_hpack (vlib_main_t *vm) +{ + vlib_cli_output (vm, "hpack_decode_int"); + + static uword (*_hpack_decode_int) (u8 * *pos, u8 * end, u8 prefix_len); + _hpack_decode_int = + vlib_get_plugin_symbol ("http_plugin.so", "hpack_decode_int"); + + u8 *pos, *end, *input = 0; + uword value; +#define TEST(i, pl, e) \ + vec_validate (input, sizeof (i) - 2); \ + memcpy (input, i, sizeof (i) - 1); \ + pos = input; \ + end = vec_end (input); \ + value = _hpack_decode_int (&pos, end, (u8) pl); \ + HTTP_TEST ((value == (uword) e && pos == end), \ + "%U with prefix length %u is %llu", format_hex_bytes, input, \ + vec_len (input), (u8) pl, value); \ + vec_free (input); + + TEST ("\x00", 8, 0); + TEST ("\x2A", 8, 42); + TEST ("\x72", 4, 2); + TEST ("\x7F\x00", 7, 127); + TEST ("\x7F\x01", 7, 128); + TEST ("\x9F\x9A\x0A", 5, 1337); + TEST ("\xFF\x80\x01", 7, 255); + /* max value to decode is CLIB_WORD_MAX, CLIB_UWORD_MAX is error */ + TEST ("\x7F\x80\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x7F", 7, CLIB_WORD_MAX); + +#undef TEST + +#define N_TEST(i, pl) \ + vec_validate (input, sizeof (i) - 2); \ + memcpy (input, i, sizeof (i) - 1); \ + pos = input; \ + end = vec_end (input); \ + value = _hpack_decode_int (&pos, end, (u8) pl); \ + HTTP_TEST ((value == HPACK_INVALID_INT), \ + "%U with prefix length %u should be invalid", format_hex_bytes, \ + input, vec_len (input), (u8) pl); \ + vec_free (input); + + /* incomplete */ + N_TEST ("\x7F", 7); + N_TEST ("\x0F\xFF\xFF", 4); + /* overflow */ + N_TEST ("\x0F\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x00", 4); + N_TEST ("\x0F\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x00", 4); + +#undef N_TEST + + vlib_cli_output (vm, "hpack_encode_int"); + + static u8 *(*_hpack_encode_int) (u8 * dst, uword value, u8 prefix_len); + _hpack_encode_int = + vlib_get_plugin_symbol ("http_plugin.so", "hpack_encode_int"); + + u8 *buf = 0; + u8 *p; + +#define TEST(v, pl, e) \ + vec_validate_init_empty (buf, 15, 0); \ + p = _hpack_encode_int (buf, v, (u8) pl); \ + HTTP_TEST (((p - buf) == (sizeof (e) - 1) && !memcmp (buf, e, p - buf)), \ + "%llu with prefix length %u is encoded as %U", v, (u8) pl, \ + format_hex_bytes, buf, p - buf); \ + vec_free (buf); + + TEST (0, 8, "\x00"); + TEST (2, 4, "\x02"); + TEST (42, 8, "\x2A"); + TEST (127, 7, "\x7F\x00"); + TEST (128, 7, "\x7F\x01"); + TEST (255, 7, "\x7F\x80\x01"); + TEST (1337, 5, "\x1F\x9A\x0A"); + TEST (CLIB_WORD_MAX, 7, "\x7F\x80\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x7F"); +#undef TEST + + vlib_cli_output (vm, "hpack_decode_string"); + + static int (*_hpack_decode_string) (u8 * *src, u8 * end, u8 * *buf, + uword * buf_len); + _hpack_decode_string = + vlib_get_plugin_symbol ("http_plugin.so", "hpack_decode_string"); + + u8 *bp; + uword blen, len; + int rv; + +#define TEST(i, e) \ + vec_validate (input, sizeof (i) - 2); \ + memcpy (input, i, sizeof (i) - 1); \ + pos = input; \ + vec_validate_init_empty (buf, 63, 0); \ + bp = buf; \ + blen = vec_len (buf); \ + rv = _hpack_decode_string (&pos, vec_end (input), &bp, &blen); \ + len = vec_len (buf) - blen; \ + HTTP_TEST ((len == strlen (e) && !memcmp (buf, e, len) && \ + pos == vec_end (input) && bp == buf + len && rv == 0), \ + "%U is decoded as %U", format_hex_bytes, input, vec_len (input), \ + format_http_bytes, buf, len); \ + vec_free (input); \ + vec_free (buf); + + /* raw coding */ + TEST ("\x07private", "private"); + /* Huffman coding */ + TEST ("\x85\xAE\xC3\x77\x1A\x4B", "private"); + TEST ("\x86\xA8\xEB\x10\x64\x9C\xBF", "no-cache"); + TEST ("\x8C\xF1\xE3\xC2\xE5\xF2\x3A\x6B\xA0\xAB\x90\xF4\xFF", + "www.example.com"); + TEST ("\x96\xD0\x7A\xBE\x94\x10\x54\xD4\x44\xA8\x20\x05\x95\x04\x0B\x81\x66" + "\xE0\x82\xA6\x2D\x1B\xFF", + "Mon, 21 Oct 2013 20:13:21 GMT") + TEST ("\xAD\x94\xE7\x82\x1D\xD7\xF2\xE6\xC7\xB3\x35\xDF\xDF\xCD\x5B\x39\x60" + "\xD5\xAF\x27\x08\x7F\x36\x72\xC1\xAB\x27\x0F\xB5\x29\x1F\x95\x87\x31" + "\x60\x65\xC0\x03\xED\x4E\xE5\xB1\x06\x3D\x50\x07", + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"); + TEST ("\x8A\x9C\xB4\x50\x75\x3C\x1E\xCA\x24\xFE\x3F", "hello world!") + TEST ("\x8A\xFF\xFE\x03\x18\xC6\x31\x8C\x63\x18\xC7", "\\aaaaaaaaaaaa"); + TEST ("\x8C\x1F\xFF\xF0\x18\xC6\x31\x80\x03\x18\xC6\x31\x8F", + "a\\aaaaa00aaaaaaa"); + TEST ("\x87\x1F\xFF\xF0\xFF\xFE\x11\xFF", "a\\\\b"); + TEST ("\x84\x1F\xF9\xFE\xA3", "a?'b"); + TEST ("\x84\x1F\xFA\xFF\x23", "a'?b"); + TEST ("\x8D\x1F\xFF\xFF\xFF\x0C\x63\x18\xC0\x01\x8C\x63\x18\xC7", + "\x61\xF9\x61\x61\x61\x61\x61\x30\x30\x61\x61\x61\x61\x61\x61\x61") +#undef TEST + +#define N_TEST(i) \ + vec_validate (input, sizeof (i) - 2); \ + memcpy (input, i, sizeof (i) - 1); \ + pos = input; \ + vec_validate_init_empty (buf, 15, 0); \ + bp = buf; \ + blen = vec_len (buf); \ + rv = _hpack_decode_string (&pos, vec_end (input), &bp, &blen); \ + HTTP_TEST ((rv != 0), "%U should be invalid", format_hex_bytes, input, \ + vec_len (input)); \ + vec_free (input); \ + vec_free (buf); + + /* incomplete */ + N_TEST ("\x07priv"); + /* invalid length */ + N_TEST ("\x7Fprivate"); + /* invalid EOF */ + N_TEST ("\x81\x8C"); + /* not enough space for decoding */ + N_TEST ( + "\x96\xD0\x7A\xBE\x94\x10\x54\xD4\x44\xA8\x20\x05\x95\x04\x0B\x81\x66" + "\xE0\x82\xA6\x2D\x1B\xFF"); +#undef N_TEST + + vlib_cli_output (vm, "hpack_encode_string"); + + static u8 *(*_hpack_encode_string) (u8 * dst, const u8 *value, + uword value_len); + _hpack_encode_string = + vlib_get_plugin_symbol ("http_plugin.so", "hpack_encode_string"); + +#define TEST(i, e) \ + vec_validate (input, sizeof (i) - 2); \ + memcpy (input, i, sizeof (i) - 1); \ + pos = input; \ + vec_validate_init_empty (buf, 63, 0); \ + p = _hpack_encode_string (buf, input, vec_len (input)); \ + HTTP_TEST (((p - buf) == (sizeof (e) - 1) && !memcmp (buf, e, p - buf)), \ + "%v is encoded as %U", input, format_hex_bytes, buf, p - buf); \ + vec_free (input); \ + vec_free (buf); + + /* Huffman coding */ + TEST ("private", "\x85\xAE\xC3\x77\x1A\x4B"); + TEST ("no-cache", "\x86\xA8\xEB\x10\x64\x9C\xBF"); + TEST ("www.example.com", + "\x8C\xF1\xE3\xC2\xE5\xF2\x3A\x6B\xA0\xAB\x90\xF4\xFF"); + TEST ("Mon, 21 Oct 2013 20:13:21 GMT", + "\x96\xD0\x7A\xBE\x94\x10\x54\xD4\x44\xA8\x20\x05\x95\x04\x0B\x81\x66" + "\xE0\x82\xA6\x2D\x1B\xFF") + TEST ("foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", + "\xAD\x94\xE7\x82\x1D\xD7\xF2\xE6\xC7\xB3\x35\xDF\xDF\xCD\x5B\x39\x60" + "\xD5\xAF\x27\x08\x7F\x36\x72\xC1\xAB\x27\x0F\xB5\x29\x1F\x95\x87\x31" + "\x60\x65\xC0\x03\xED\x4E\xE5\xB1\x06\x3D\x50\x07"); + TEST ("hello world!", "\x8A\x9C\xB4\x50\x75\x3C\x1E\xCA\x24\xFE\x3F") + TEST ("\\aaaaaaaaaaaa", "\x8A\xFF\xFE\x03\x18\xC6\x31\x8C\x63\x18\xC7"); + /* raw coding */ + TEST ("[XZ]", "\x4[XZ]"); +#undef TEST + + return 0; +} + static clib_error_t * test_http_command_fn (vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd) @@ -550,6 +748,8 @@ test_http_command_fn (vlib_main_t *vm, unformat_input_t *input, res = http_test_http_token_is_case (vm); else if (unformat (input, "header-table")) res = http_test_http_header_table (vm); + else if (unformat (input, "hpack")) + res = http_test_hpack (vm); else if (unformat (input, "all")) { if ((res = http_test_parse_authority (vm))) @@ -562,6 +762,8 @@ test_http_command_fn (vlib_main_t *vm, unformat_input_t *input, goto done; if ((res = http_test_http_header_table (vm))) goto done; + if ((res = http_test_hpack (vm))) + goto done; } else break; |