diff options
author | Loïc Hoguin <[email protected]> | 2020-12-23 17:50:12 +0100 |
---|---|---|
committer | Loïc Hoguin <[email protected]> | 2020-12-23 17:50:12 +0100 |
commit | fa3eed6ec6b4ad9cafde37b242d0fa7003783ed5 (patch) | |
tree | 3a92460eef542eb0a3cdbfd7695443a14633f3c8 | |
parent | 6deddc7d3360aa0f50eb2375cc0226157185c472 (diff) | |
download | cowlib-fa3eed6ec6b4ad9cafde37b242d0fa7003783ed5.tar.gz cowlib-fa3eed6ec6b4ad9cafde37b242d0fa7003783ed5.tar.bz2 cowlib-fa3eed6ec6b4ad9cafde37b242d0fa7003783ed5.zip |
WIP appendix examples working
-rw-r--r-- | ebin/cowlib.app | 2 | ||||
-rw-r--r-- | src/cow_hpack.erl | 353 | ||||
-rw-r--r-- | src/cow_hpack_common.hrl | 376 | ||||
-rw-r--r-- | src/cow_qpack.erl | 1198 |
4 files changed, 1578 insertions, 351 deletions
diff --git a/ebin/cowlib.app b/ebin/cowlib.app index d089998..da42177 100644 --- a/ebin/cowlib.app +++ b/ebin/cowlib.app @@ -1,7 +1,7 @@ {application, 'cowlib', [ {description, "Support library for manipulating Web protocols."}, {vsn, "2.10.1"}, - {modules, ['cow_base64url','cow_cookie','cow_date','cow_hpack','cow_http','cow_http2','cow_http2_machine','cow_http_hd','cow_http_struct_hd','cow_http_te','cow_iolists','cow_link','cow_mimetypes','cow_multipart','cow_qs','cow_spdy','cow_sse','cow_uri','cow_uri_template','cow_ws']}, + {modules, ['cow_base64url','cow_cookie','cow_date','cow_hpack','cow_http','cow_http2','cow_http2_machine','cow_http_hd','cow_http_struct_hd','cow_http_te','cow_iolists','cow_link','cow_mimetypes','cow_multipart','cow_qpack','cow_qs','cow_spdy','cow_sse','cow_uri','cow_uri_template','cow_ws']}, {registered, []}, {applications, [kernel,stdlib,crypto]}, {env, []} diff --git a/src/cow_hpack.erl b/src/cow_hpack.erl index 4a02d79..f7fbd84 100644 --- a/src/cow_hpack.erl +++ b/src/cow_hpack.erl @@ -1,4 +1,4 @@ -%% Copyright (c) 2015-2018, Loïc Hoguin <[email protected]> +%% Copyright (c) 2015-2020, Loïc Hoguin <[email protected]> %% %% Permission to use, copy, modify, and/or distribute this software for any %% purpose with or without fee is hereby granted, provided that the above @@ -47,6 +47,8 @@ -include_lib("proper/include/proper.hrl"). -endif. +-include("cow_hpack_common.hrl"). + %% State initialization. -spec init() -> state(). @@ -182,22 +184,6 @@ dec_lit_no_index(Rest, State, Acc, Name) -> %% @todo Literal header field never indexed. -%% Decode an integer. - -%% The HPACK format has 4 different integer prefixes length (from 4 to 7) -%% and each can be used to create an indefinite length integer if all bits -%% of the prefix are set to 1. - -dec_int5(<< 2#11111:5, Rest/bits >>) -> - dec_big_int(Rest, 31, 0); -dec_int5(<< Int:5, Rest/bits >>) -> - {Int, Rest}. - -dec_big_int(<< 0:1, Value:7, Rest/bits >>, Int, M) -> - {Int + (Value bsl M), Rest}; -dec_big_int(<< 1:1, Value:7, Rest/bits >>, Int, M) -> - dec_big_int(Rest, Int + (Value bsl M), M + 7). - %% Decode a string. dec_str(<<0:1, 2#1111111:7, Rest0/bits>>) -> @@ -213,41 +199,6 @@ dec_str(<<1:1, 2#1111111:7, Rest0/bits>>) -> dec_str(<<1:1, Length:7, Rest/bits>>) -> dec_huffman(Rest, Length, 0, <<>>). -%% We use a lookup table that allows us to benefit from -%% the binary match context optimization. A more naive -%% implementation using bit pattern matching cannot reuse -%% a match context because it wouldn't always match on -%% byte boundaries. -%% -%% See cow_hpack_dec_huffman_lookup.hrl for more details. - -dec_huffman(<<A:4, B:4, R/bits>>, Len, Huff0, Acc) when Len > 1 -> - {_, CharA, Huff1} = dec_huffman_lookup(Huff0, A), - {_, CharB, Huff} = dec_huffman_lookup(Huff1, B), - case {CharA, CharB} of - {undefined, undefined} -> dec_huffman(R, Len - 1, Huff, Acc); - {CharA, undefined} -> dec_huffman(R, Len - 1, Huff, <<Acc/binary, CharA>>); - {undefined, CharB} -> dec_huffman(R, Len - 1, Huff, <<Acc/binary, CharB>>); - {CharA, CharB} -> dec_huffman(R, Len - 1, Huff, <<Acc/binary, CharA, CharB>>) - end; -dec_huffman(<<A:4, B:4, Rest/bits>>, 1, Huff0, Acc) -> - {_, CharA, Huff} = dec_huffman_lookup(Huff0, A), - {ok, CharB, _} = dec_huffman_lookup(Huff, B), - case {CharA, CharB} of - %% {undefined, undefined} (> 7-bit final padding) is rejected with a crash. - {CharA, undefined} -> - {<<Acc/binary, CharA>>, Rest}; - {undefined, CharB} -> - {<<Acc/binary, CharB>>, Rest}; - _ -> - {<<Acc/binary, CharA, CharB>>, Rest} - end; -%% Can only be reached when the string length to decode is 0. -dec_huffman(Rest, 0, _, <<>>) -> - {<<>>, Rest}. - --include("cow_hpack_dec_huffman_lookup.hrl"). - -ifdef(TEST). %% Test case extracted from h2spec. decode_reject_eos_test() -> @@ -569,304 +520,6 @@ encode([{Name, Value0}|Tail], State, HuffmanOpt, Acc) -> [[<< 0:1, 1:1, 0:6 >>|[enc_str(Name, HuffmanOpt)|enc_str(Value, HuffmanOpt)]]|Acc]) end. -%% Encode an integer. - -enc_int5(Int, Prefix) when Int < 31 -> - << Prefix:3, Int:5 >>; -enc_int5(Int, Prefix) -> - enc_big_int(Int - 31, << Prefix:3, 2#11111:5 >>). - -enc_int6(Int, Prefix) when Int < 63 -> - << Prefix:2, Int:6 >>; -enc_int6(Int, Prefix) -> - enc_big_int(Int - 63, << Prefix:2, 2#111111:6 >>). - -enc_int7(Int, Prefix) when Int < 127 -> - << Prefix:1, Int:7 >>; -enc_int7(Int, Prefix) -> - enc_big_int(Int - 127, << Prefix:1, 2#1111111:7 >>). - -enc_big_int(Int, Acc) when Int < 128 -> - <<Acc/binary, Int:8>>; -enc_big_int(Int, Acc) -> - enc_big_int(Int bsr 7, <<Acc/binary, 1:1, Int:7>>). - -%% Encode a string. - -enc_str(Str, huffman) -> - Str2 = enc_huffman(Str, <<>>), - [enc_int7(byte_size(Str2), 2#1)|Str2]; -enc_str(Str, no_huffman) -> - [enc_int7(byte_size(Str), 2#0)|Str]. - -enc_huffman(<<>>, Acc) -> - case bit_size(Acc) rem 8 of - 1 -> << Acc/bits, 2#1111111:7 >>; - 2 -> << Acc/bits, 2#111111:6 >>; - 3 -> << Acc/bits, 2#11111:5 >>; - 4 -> << Acc/bits, 2#1111:4 >>; - 5 -> << Acc/bits, 2#111:3 >>; - 6 -> << Acc/bits, 2#11:2 >>; - 7 -> << Acc/bits, 2#1:1 >>; - 0 -> Acc - end; -enc_huffman(<< 0, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111000:13 >>); -enc_huffman(<< 1, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111011000:23 >>); -enc_huffman(<< 2, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111100010:28 >>); -enc_huffman(<< 3, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111100011:28 >>); -enc_huffman(<< 4, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111100100:28 >>); -enc_huffman(<< 5, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111100101:28 >>); -enc_huffman(<< 6, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111100110:28 >>); -enc_huffman(<< 7, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111100111:28 >>); -enc_huffman(<< 8, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111101000:28 >>); -enc_huffman(<< 9, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111101010:24 >>); -enc_huffman(<< 10, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111111111100:30 >>); -enc_huffman(<< 11, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111101001:28 >>); -enc_huffman(<< 12, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111101010:28 >>); -enc_huffman(<< 13, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111111111101:30 >>); -enc_huffman(<< 14, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111101011:28 >>); -enc_huffman(<< 15, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111101100:28 >>); -enc_huffman(<< 16, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111101101:28 >>); -enc_huffman(<< 17, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111101110:28 >>); -enc_huffman(<< 18, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111101111:28 >>); -enc_huffman(<< 19, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111110000:28 >>); -enc_huffman(<< 20, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111110001:28 >>); -enc_huffman(<< 21, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111110010:28 >>); -enc_huffman(<< 22, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111111111110:30 >>); -enc_huffman(<< 23, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111110011:28 >>); -enc_huffman(<< 24, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111110100:28 >>); -enc_huffman(<< 25, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111110101:28 >>); -enc_huffman(<< 26, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111110110:28 >>); -enc_huffman(<< 27, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111110111:28 >>); -enc_huffman(<< 28, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111111000:28 >>); -enc_huffman(<< 29, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111111001:28 >>); -enc_huffman(<< 30, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111111010:28 >>); -enc_huffman(<< 31, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111111011:28 >>); -enc_huffman(<< 32, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#010100:6 >>); -enc_huffman(<< 33, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111000:10 >>); -enc_huffman(<< 34, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111001:10 >>); -enc_huffman(<< 35, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111010:12 >>); -enc_huffman(<< 36, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111001:13 >>); -enc_huffman(<< 37, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#010101:6 >>); -enc_huffman(<< 38, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111000:8 >>); -enc_huffman(<< 39, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111010:11 >>); -enc_huffman(<< 40, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111010:10 >>); -enc_huffman(<< 41, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111011:10 >>); -enc_huffman(<< 42, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111001:8 >>); -enc_huffman(<< 43, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111011:11 >>); -enc_huffman(<< 44, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111010:8 >>); -enc_huffman(<< 45, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#010110:6 >>); -enc_huffman(<< 46, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#010111:6 >>); -enc_huffman(<< 47, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#011000:6 >>); -enc_huffman(<< 48, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#00000:5 >>); -enc_huffman(<< 49, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#00001:5 >>); -enc_huffman(<< 50, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#00010:5 >>); -enc_huffman(<< 51, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#011001:6 >>); -enc_huffman(<< 52, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#011010:6 >>); -enc_huffman(<< 53, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#011011:6 >>); -enc_huffman(<< 54, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#011100:6 >>); -enc_huffman(<< 55, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#011101:6 >>); -enc_huffman(<< 56, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#011110:6 >>); -enc_huffman(<< 57, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#011111:6 >>); -enc_huffman(<< 58, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1011100:7 >>); -enc_huffman(<< 59, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111011:8 >>); -enc_huffman(<< 60, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111100:15 >>); -enc_huffman(<< 61, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#100000:6 >>); -enc_huffman(<< 62, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111011:12 >>); -enc_huffman(<< 63, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111100:10 >>); -enc_huffman(<< 64, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111010:13 >>); -enc_huffman(<< 65, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#100001:6 >>); -enc_huffman(<< 66, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1011101:7 >>); -enc_huffman(<< 67, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1011110:7 >>); -enc_huffman(<< 68, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1011111:7 >>); -enc_huffman(<< 69, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1100000:7 >>); -enc_huffman(<< 70, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1100001:7 >>); -enc_huffman(<< 71, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1100010:7 >>); -enc_huffman(<< 72, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1100011:7 >>); -enc_huffman(<< 73, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1100100:7 >>); -enc_huffman(<< 74, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1100101:7 >>); -enc_huffman(<< 75, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1100110:7 >>); -enc_huffman(<< 76, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1100111:7 >>); -enc_huffman(<< 77, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1101000:7 >>); -enc_huffman(<< 78, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1101001:7 >>); -enc_huffman(<< 79, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1101010:7 >>); -enc_huffman(<< 80, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1101011:7 >>); -enc_huffman(<< 81, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1101100:7 >>); -enc_huffman(<< 82, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1101101:7 >>); -enc_huffman(<< 83, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1101110:7 >>); -enc_huffman(<< 84, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1101111:7 >>); -enc_huffman(<< 85, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1110000:7 >>); -enc_huffman(<< 86, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1110001:7 >>); -enc_huffman(<< 87, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1110010:7 >>); -enc_huffman(<< 88, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111100:8 >>); -enc_huffman(<< 89, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1110011:7 >>); -enc_huffman(<< 90, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111101:8 >>); -enc_huffman(<< 91, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111011:13 >>); -enc_huffman(<< 92, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111110000:19 >>); -enc_huffman(<< 93, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111100:13 >>); -enc_huffman(<< 94, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111100:14 >>); -enc_huffman(<< 95, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#100010:6 >>); -enc_huffman(<< 96, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111101:15 >>); -enc_huffman(<< 97, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#00011:5 >>); -enc_huffman(<< 98, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#100011:6 >>); -enc_huffman(<< 99, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#00100:5 >>); -enc_huffman(<< 100, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#100100:6 >>); -enc_huffman(<< 101, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#00101:5 >>); -enc_huffman(<< 102, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#100101:6 >>); -enc_huffman(<< 103, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#100110:6 >>); -enc_huffman(<< 104, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#100111:6 >>); -enc_huffman(<< 105, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#00110:5 >>); -enc_huffman(<< 106, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1110100:7 >>); -enc_huffman(<< 107, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1110101:7 >>); -enc_huffman(<< 108, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#101000:6 >>); -enc_huffman(<< 109, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#101001:6 >>); -enc_huffman(<< 110, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#101010:6 >>); -enc_huffman(<< 111, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#00111:5 >>); -enc_huffman(<< 112, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#101011:6 >>); -enc_huffman(<< 113, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1110110:7 >>); -enc_huffman(<< 114, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#101100:6 >>); -enc_huffman(<< 115, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#01000:5 >>); -enc_huffman(<< 116, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#01001:5 >>); -enc_huffman(<< 117, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#101101:6 >>); -enc_huffman(<< 118, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1110111:7 >>); -enc_huffman(<< 119, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111000:7 >>); -enc_huffman(<< 120, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111001:7 >>); -enc_huffman(<< 121, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111010:7 >>); -enc_huffman(<< 122, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111011:7 >>); -enc_huffman(<< 123, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111110:15 >>); -enc_huffman(<< 124, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111100:11 >>); -enc_huffman(<< 125, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111101:14 >>); -enc_huffman(<< 126, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111101:13 >>); -enc_huffman(<< 127, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111111100:28 >>); -enc_huffman(<< 128, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111100110:20 >>); -enc_huffman(<< 129, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111010010:22 >>); -enc_huffman(<< 130, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111100111:20 >>); -enc_huffman(<< 131, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111101000:20 >>); -enc_huffman(<< 132, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111010011:22 >>); -enc_huffman(<< 133, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111010100:22 >>); -enc_huffman(<< 134, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111010101:22 >>); -enc_huffman(<< 135, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111011001:23 >>); -enc_huffman(<< 136, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111010110:22 >>); -enc_huffman(<< 137, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111011010:23 >>); -enc_huffman(<< 138, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111011011:23 >>); -enc_huffman(<< 139, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111011100:23 >>); -enc_huffman(<< 140, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111011101:23 >>); -enc_huffman(<< 141, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111011110:23 >>); -enc_huffman(<< 142, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111101011:24 >>); -enc_huffman(<< 143, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111011111:23 >>); -enc_huffman(<< 144, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111101100:24 >>); -enc_huffman(<< 145, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111101101:24 >>); -enc_huffman(<< 146, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111010111:22 >>); -enc_huffman(<< 147, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111100000:23 >>); -enc_huffman(<< 148, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111101110:24 >>); -enc_huffman(<< 149, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111100001:23 >>); -enc_huffman(<< 150, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111100010:23 >>); -enc_huffman(<< 151, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111100011:23 >>); -enc_huffman(<< 152, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111100100:23 >>); -enc_huffman(<< 153, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111011100:21 >>); -enc_huffman(<< 154, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111011000:22 >>); -enc_huffman(<< 155, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111100101:23 >>); -enc_huffman(<< 156, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111011001:22 >>); -enc_huffman(<< 157, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111100110:23 >>); -enc_huffman(<< 158, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111100111:23 >>); -enc_huffman(<< 159, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111101111:24 >>); -enc_huffman(<< 160, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111011010:22 >>); -enc_huffman(<< 161, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111011101:21 >>); -enc_huffman(<< 162, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111101001:20 >>); -enc_huffman(<< 163, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111011011:22 >>); -enc_huffman(<< 164, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111011100:22 >>); -enc_huffman(<< 165, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111101000:23 >>); -enc_huffman(<< 166, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111101001:23 >>); -enc_huffman(<< 167, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111011110:21 >>); -enc_huffman(<< 168, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111101010:23 >>); -enc_huffman(<< 169, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111011101:22 >>); -enc_huffman(<< 170, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111011110:22 >>); -enc_huffman(<< 171, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111110000:24 >>); -enc_huffman(<< 172, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111011111:21 >>); -enc_huffman(<< 173, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111011111:22 >>); -enc_huffman(<< 174, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111101011:23 >>); -enc_huffman(<< 175, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111101100:23 >>); -enc_huffman(<< 176, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111100000:21 >>); -enc_huffman(<< 177, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111100001:21 >>); -enc_huffman(<< 178, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111100000:22 >>); -enc_huffman(<< 179, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111100010:21 >>); -enc_huffman(<< 180, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111101101:23 >>); -enc_huffman(<< 181, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111100001:22 >>); -enc_huffman(<< 182, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111101110:23 >>); -enc_huffman(<< 183, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111101111:23 >>); -enc_huffman(<< 184, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111101010:20 >>); -enc_huffman(<< 185, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111100010:22 >>); -enc_huffman(<< 186, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111100011:22 >>); -enc_huffman(<< 187, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111100100:22 >>); -enc_huffman(<< 188, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111110000:23 >>); -enc_huffman(<< 189, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111100101:22 >>); -enc_huffman(<< 190, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111100110:22 >>); -enc_huffman(<< 191, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111110001:23 >>); -enc_huffman(<< 192, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111100000:26 >>); -enc_huffman(<< 193, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111100001:26 >>); -enc_huffman(<< 194, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111101011:20 >>); -enc_huffman(<< 195, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111110001:19 >>); -enc_huffman(<< 196, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111100111:22 >>); -enc_huffman(<< 197, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111110010:23 >>); -enc_huffman(<< 198, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111101000:22 >>); -enc_huffman(<< 199, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111101100:25 >>); -enc_huffman(<< 200, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111100010:26 >>); -enc_huffman(<< 201, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111100011:26 >>); -enc_huffman(<< 202, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111100100:26 >>); -enc_huffman(<< 203, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111011110:27 >>); -enc_huffman(<< 204, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111011111:27 >>); -enc_huffman(<< 205, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111100101:26 >>); -enc_huffman(<< 206, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111110001:24 >>); -enc_huffman(<< 207, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111101101:25 >>); -enc_huffman(<< 208, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111110010:19 >>); -enc_huffman(<< 209, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111100011:21 >>); -enc_huffman(<< 210, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111100110:26 >>); -enc_huffman(<< 211, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111100000:27 >>); -enc_huffman(<< 212, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111100001:27 >>); -enc_huffman(<< 213, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111100111:26 >>); -enc_huffman(<< 214, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111100010:27 >>); -enc_huffman(<< 215, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111110010:24 >>); -enc_huffman(<< 216, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111100100:21 >>); -enc_huffman(<< 217, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111100101:21 >>); -enc_huffman(<< 218, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111101000:26 >>); -enc_huffman(<< 219, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111101001:26 >>); -enc_huffman(<< 220, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111111101:28 >>); -enc_huffman(<< 221, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111100011:27 >>); -enc_huffman(<< 222, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111100100:27 >>); -enc_huffman(<< 223, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111100101:27 >>); -enc_huffman(<< 224, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111101100:20 >>); -enc_huffman(<< 225, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111110011:24 >>); -enc_huffman(<< 226, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111101101:20 >>); -enc_huffman(<< 227, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111100110:21 >>); -enc_huffman(<< 228, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111101001:22 >>); -enc_huffman(<< 229, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111100111:21 >>); -enc_huffman(<< 230, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111101000:21 >>); -enc_huffman(<< 231, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111110011:23 >>); -enc_huffman(<< 232, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111101010:22 >>); -enc_huffman(<< 233, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111101011:22 >>); -enc_huffman(<< 234, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111101110:25 >>); -enc_huffman(<< 235, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111101111:25 >>); -enc_huffman(<< 236, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111110100:24 >>); -enc_huffman(<< 237, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111110101:24 >>); -enc_huffman(<< 238, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111101010:26 >>); -enc_huffman(<< 239, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111110100:23 >>); -enc_huffman(<< 240, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111101011:26 >>); -enc_huffman(<< 241, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111100110:27 >>); -enc_huffman(<< 242, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111101100:26 >>); -enc_huffman(<< 243, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111101101:26 >>); -enc_huffman(<< 244, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111100111:27 >>); -enc_huffman(<< 245, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111101000:27 >>); -enc_huffman(<< 246, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111101001:27 >>); -enc_huffman(<< 247, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111101010:27 >>); -enc_huffman(<< 248, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111101011:27 >>); -enc_huffman(<< 249, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#1111111111111111111111111110:28 >>); -enc_huffman(<< 250, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111101100:27 >>); -enc_huffman(<< 251, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111101101:27 >>); -enc_huffman(<< 252, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111101110:27 >>); -enc_huffman(<< 253, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111101111:27 >>); -enc_huffman(<< 254, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#111111111111111111111110000:27 >>); -enc_huffman(<< 255, R/bits >>, A) -> enc_huffman(R, << A/bits, 2#11111111111111111111101110:26 >>). - -ifdef(TEST). req_encode_test() -> %% First request (raw then huffman). diff --git a/src/cow_hpack_common.hrl b/src/cow_hpack_common.hrl new file mode 100644 index 0000000..92f9514 --- /dev/null +++ b/src/cow_hpack_common.hrl @@ -0,0 +1,376 @@ +%% Copyright (c) 2015-2020, Loïc Hoguin <[email protected]> +%% +%% Permission to use, copy, modify, and/or distribute this software for any +%% purpose with or without fee is hereby granted, provided that the above +%% copyright notice and this permission notice appear in all copies. +%% +%% THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +%% WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +%% MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +%% ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +%% WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +%% ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +%% OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +%% The prefixed integer and the string formats are common +%% to both HPACK and QPACK. They are included directly in +%% each module in order to avoid fully-qualified calls and +%% slightly improve performance. +%% +%% Some functions are only used in one or the other even +%% though the format is the same. In that case the functions +%% can be found in the relevant module. +%% +%% Any tests relevant to these functions should be added to +%% cow_hpack since HPACK is where these originate from. + +%% Prefix decoding. +%% +%% The HPACK format has 4 different integer prefixes length (from 4 to 7) +%% and each can be used to create an indefinite length integer if all bits +%% of the prefix are set to 1. + +dec_int5(<<2#11111:5, Rest/bits>>) -> + dec_big_int(Rest, 31, 0); +dec_int5(<<Int:5, Rest/bits>>) -> + {Int, Rest}. + +dec_big_int(<<0:1, Value:7, Rest/bits>>, Int, M) -> + {Int + (Value bsl M), Rest}; +dec_big_int(<<1:1, Value:7, Rest/bits>>, Int, M) -> + dec_big_int(Rest, Int + (Value bsl M), M + 7). + +%% Prefix encoding. + +enc_int5(Int, Prefix) when Int < 31 -> + <<Prefix:3, Int:5>>; +enc_int5(Int, Prefix) -> + enc_big_int(Int - 31, <<Prefix:3, 2#11111:5>>). + +enc_int6(Int, Prefix) when Int < 63 -> + <<Prefix:2, Int:6>>; +enc_int6(Int, Prefix) -> + enc_big_int(Int - 63, <<Prefix:2, 2#111111:6>>). + +enc_int7(Int, Prefix) when Int < 127 -> + <<Prefix:1, Int:7>>; +enc_int7(Int, Prefix) -> + enc_big_int(Int - 127, <<Prefix:1, 2#1111111:7>>). + +enc_big_int(Int, Acc) when Int < 128 -> + <<Acc/binary, Int:8>>; +enc_big_int(Int, Acc) -> + enc_big_int(Int bsr 7, <<Acc/binary, 1:1, Int:7>>). + +%% String decoding. +%% +%% We use a lookup table that allows us to benefit from +%% the binary match context optimization. A more naive +%% implementation using bit pattern matching cannot reuse +%% a match context because it wouldn't always match on +%% byte boundaries. +%% +%% See cow_hpack_dec_huffman_lookup.hrl for more details. + +dec_huffman(<<A:4, B:4, R/bits>>, Len, Huff0, Acc) when Len > 1 -> + {_, CharA, Huff1} = dec_huffman_lookup(Huff0, A), + {_, CharB, Huff} = dec_huffman_lookup(Huff1, B), + case {CharA, CharB} of + {undefined, undefined} -> dec_huffman(R, Len - 1, Huff, Acc); + {CharA, undefined} -> dec_huffman(R, Len - 1, Huff, <<Acc/binary, CharA>>); + {undefined, CharB} -> dec_huffman(R, Len - 1, Huff, <<Acc/binary, CharB>>); + {CharA, CharB} -> dec_huffman(R, Len - 1, Huff, <<Acc/binary, CharA, CharB>>) + end; +dec_huffman(<<A:4, B:4, Rest/bits>>, 1, Huff0, Acc) -> + {_, CharA, Huff} = dec_huffman_lookup(Huff0, A), + {ok, CharB, _} = dec_huffman_lookup(Huff, B), + case {CharA, CharB} of + %% {undefined, undefined} (> 7-bit final padding) is rejected with a crash. + {CharA, undefined} -> + {<<Acc/binary, CharA>>, Rest}; + {undefined, CharB} -> + {<<Acc/binary, CharB>>, Rest}; + _ -> + {<<Acc/binary, CharA, CharB>>, Rest} + end; +%% Can only be reached when the string length to decode is 0. +dec_huffman(Rest, 0, _, <<>>) -> + {<<>>, Rest}. + +-include("cow_hpack_dec_huffman_lookup.hrl"). + +%% String encoding. + +enc_str(Str, huffman) -> + Str2 = enc_huffman(Str, <<>>), + [enc_int7(byte_size(Str2), 2#1)|Str2]; +enc_str(Str, no_huffman) -> + [enc_int7(byte_size(Str), 2#0)|Str]. + +enc_huffman(<<>>, Acc) -> + case bit_size(Acc) rem 8 of + 1 -> <<Acc/bits, 2#1111111:7>>; + 2 -> <<Acc/bits, 2#111111:6>>; + 3 -> <<Acc/bits, 2#11111:5>>; + 4 -> <<Acc/bits, 2#1111:4>>; + 5 -> <<Acc/bits, 2#111:3>>; + 6 -> <<Acc/bits, 2#11:2>>; + 7 -> <<Acc/bits, 2#1:1>>; + 0 -> Acc + end; +enc_huffman(<<0, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111000:13>>); +enc_huffman(<<1, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111011000:23>>); +enc_huffman(<<2, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111100010:28>>); +enc_huffman(<<3, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111100011:28>>); +enc_huffman(<<4, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111100100:28>>); +enc_huffman(<<5, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111100101:28>>); +enc_huffman(<<6, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111100110:28>>); +enc_huffman(<<7, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111100111:28>>); +enc_huffman(<<8, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111101000:28>>); +enc_huffman(<<9, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111101010:24>>); +enc_huffman(<<10, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111111111100:30>>); +enc_huffman(<<11, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111101001:28>>); +enc_huffman(<<12, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111101010:28>>); +enc_huffman(<<13, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111111111101:30>>); +enc_huffman(<<14, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111101011:28>>); +enc_huffman(<<15, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111101100:28>>); +enc_huffman(<<16, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111101101:28>>); +enc_huffman(<<17, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111101110:28>>); +enc_huffman(<<18, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111101111:28>>); +enc_huffman(<<19, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111110000:28>>); +enc_huffman(<<20, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111110001:28>>); +enc_huffman(<<21, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111110010:28>>); +enc_huffman(<<22, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111111111110:30>>); +enc_huffman(<<23, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111110011:28>>); +enc_huffman(<<24, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111110100:28>>); +enc_huffman(<<25, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111110101:28>>); +enc_huffman(<<26, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111110110:28>>); +enc_huffman(<<27, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111110111:28>>); +enc_huffman(<<28, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111111000:28>>); +enc_huffman(<<29, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111111001:28>>); +enc_huffman(<<30, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111111010:28>>); +enc_huffman(<<31, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111111011:28>>); +enc_huffman(<<32, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#010100:6>>); +enc_huffman(<<33, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111000:10>>); +enc_huffman(<<34, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111001:10>>); +enc_huffman(<<35, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111010:12>>); +enc_huffman(<<36, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111001:13>>); +enc_huffman(<<37, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#010101:6>>); +enc_huffman(<<38, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111000:8>>); +enc_huffman(<<39, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111010:11>>); +enc_huffman(<<40, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111010:10>>); +enc_huffman(<<41, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111011:10>>); +enc_huffman(<<42, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111001:8>>); +enc_huffman(<<43, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111011:11>>); +enc_huffman(<<44, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111010:8>>); +enc_huffman(<<45, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#010110:6>>); +enc_huffman(<<46, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#010111:6>>); +enc_huffman(<<47, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#011000:6>>); +enc_huffman(<<48, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#00000:5>>); +enc_huffman(<<49, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#00001:5>>); +enc_huffman(<<50, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#00010:5>>); +enc_huffman(<<51, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#011001:6>>); +enc_huffman(<<52, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#011010:6>>); +enc_huffman(<<53, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#011011:6>>); +enc_huffman(<<54, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#011100:6>>); +enc_huffman(<<55, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#011101:6>>); +enc_huffman(<<56, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#011110:6>>); +enc_huffman(<<57, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#011111:6>>); +enc_huffman(<<58, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1011100:7>>); +enc_huffman(<<59, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111011:8>>); +enc_huffman(<<60, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111100:15>>); +enc_huffman(<<61, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#100000:6>>); +enc_huffman(<<62, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111011:12>>); +enc_huffman(<<63, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111100:10>>); +enc_huffman(<<64, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111010:13>>); +enc_huffman(<<65, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#100001:6>>); +enc_huffman(<<66, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1011101:7>>); +enc_huffman(<<67, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1011110:7>>); +enc_huffman(<<68, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1011111:7>>); +enc_huffman(<<69, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1100000:7>>); +enc_huffman(<<70, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1100001:7>>); +enc_huffman(<<71, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1100010:7>>); +enc_huffman(<<72, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1100011:7>>); +enc_huffman(<<73, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1100100:7>>); +enc_huffman(<<74, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1100101:7>>); +enc_huffman(<<75, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1100110:7>>); +enc_huffman(<<76, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1100111:7>>); +enc_huffman(<<77, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1101000:7>>); +enc_huffman(<<78, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1101001:7>>); +enc_huffman(<<79, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1101010:7>>); +enc_huffman(<<80, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1101011:7>>); +enc_huffman(<<81, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1101100:7>>); +enc_huffman(<<82, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1101101:7>>); +enc_huffman(<<83, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1101110:7>>); +enc_huffman(<<84, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1101111:7>>); +enc_huffman(<<85, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1110000:7>>); +enc_huffman(<<86, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1110001:7>>); +enc_huffman(<<87, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1110010:7>>); +enc_huffman(<<88, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111100:8>>); +enc_huffman(<<89, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1110011:7>>); +enc_huffman(<<90, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111101:8>>); +enc_huffman(<<91, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111011:13>>); +enc_huffman(<<92, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111110000:19>>); +enc_huffman(<<93, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111100:13>>); +enc_huffman(<<94, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111100:14>>); +enc_huffman(<<95, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#100010:6>>); +enc_huffman(<<96, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111101:15>>); +enc_huffman(<<97, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#00011:5>>); +enc_huffman(<<98, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#100011:6>>); +enc_huffman(<<99, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#00100:5>>); +enc_huffman(<<100, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#100100:6>>); +enc_huffman(<<101, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#00101:5>>); +enc_huffman(<<102, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#100101:6>>); +enc_huffman(<<103, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#100110:6>>); +enc_huffman(<<104, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#100111:6>>); +enc_huffman(<<105, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#00110:5>>); +enc_huffman(<<106, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1110100:7>>); +enc_huffman(<<107, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1110101:7>>); +enc_huffman(<<108, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#101000:6>>); +enc_huffman(<<109, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#101001:6>>); +enc_huffman(<<110, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#101010:6>>); +enc_huffman(<<111, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#00111:5>>); +enc_huffman(<<112, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#101011:6>>); +enc_huffman(<<113, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1110110:7>>); +enc_huffman(<<114, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#101100:6>>); +enc_huffman(<<115, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#01000:5>>); +enc_huffman(<<116, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#01001:5>>); +enc_huffman(<<117, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#101101:6>>); +enc_huffman(<<118, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1110111:7>>); +enc_huffman(<<119, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111000:7>>); +enc_huffman(<<120, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111001:7>>); +enc_huffman(<<121, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111010:7>>); +enc_huffman(<<122, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111011:7>>); +enc_huffman(<<123, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111110:15>>); +enc_huffman(<<124, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111100:11>>); +enc_huffman(<<125, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111101:14>>); +enc_huffman(<<126, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111101:13>>); +enc_huffman(<<127, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111111100:28>>); +enc_huffman(<<128, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111100110:20>>); +enc_huffman(<<129, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111010010:22>>); +enc_huffman(<<130, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111100111:20>>); +enc_huffman(<<131, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111101000:20>>); +enc_huffman(<<132, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111010011:22>>); +enc_huffman(<<133, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111010100:22>>); +enc_huffman(<<134, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111010101:22>>); +enc_huffman(<<135, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111011001:23>>); +enc_huffman(<<136, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111010110:22>>); +enc_huffman(<<137, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111011010:23>>); +enc_huffman(<<138, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111011011:23>>); +enc_huffman(<<139, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111011100:23>>); +enc_huffman(<<140, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111011101:23>>); +enc_huffman(<<141, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111011110:23>>); +enc_huffman(<<142, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111101011:24>>); +enc_huffman(<<143, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111011111:23>>); +enc_huffman(<<144, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111101100:24>>); +enc_huffman(<<145, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111101101:24>>); +enc_huffman(<<146, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111010111:22>>); +enc_huffman(<<147, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111100000:23>>); +enc_huffman(<<148, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111101110:24>>); +enc_huffman(<<149, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111100001:23>>); +enc_huffman(<<150, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111100010:23>>); +enc_huffman(<<151, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111100011:23>>); +enc_huffman(<<152, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111100100:23>>); +enc_huffman(<<153, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111011100:21>>); +enc_huffman(<<154, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111011000:22>>); +enc_huffman(<<155, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111100101:23>>); +enc_huffman(<<156, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111011001:22>>); +enc_huffman(<<157, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111100110:23>>); +enc_huffman(<<158, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111100111:23>>); +enc_huffman(<<159, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111101111:24>>); +enc_huffman(<<160, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111011010:22>>); +enc_huffman(<<161, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111011101:21>>); +enc_huffman(<<162, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111101001:20>>); +enc_huffman(<<163, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111011011:22>>); +enc_huffman(<<164, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111011100:22>>); +enc_huffman(<<165, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111101000:23>>); +enc_huffman(<<166, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111101001:23>>); +enc_huffman(<<167, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111011110:21>>); +enc_huffman(<<168, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111101010:23>>); +enc_huffman(<<169, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111011101:22>>); +enc_huffman(<<170, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111011110:22>>); +enc_huffman(<<171, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111110000:24>>); +enc_huffman(<<172, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111011111:21>>); +enc_huffman(<<173, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111011111:22>>); +enc_huffman(<<174, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111101011:23>>); +enc_huffman(<<175, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111101100:23>>); +enc_huffman(<<176, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111100000:21>>); +enc_huffman(<<177, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111100001:21>>); +enc_huffman(<<178, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111100000:22>>); +enc_huffman(<<179, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111100010:21>>); +enc_huffman(<<180, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111101101:23>>); +enc_huffman(<<181, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111100001:22>>); +enc_huffman(<<182, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111101110:23>>); +enc_huffman(<<183, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111101111:23>>); +enc_huffman(<<184, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111101010:20>>); +enc_huffman(<<185, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111100010:22>>); +enc_huffman(<<186, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111100011:22>>); +enc_huffman(<<187, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111100100:22>>); +enc_huffman(<<188, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111110000:23>>); +enc_huffman(<<189, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111100101:22>>); +enc_huffman(<<190, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111100110:22>>); +enc_huffman(<<191, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111110001:23>>); +enc_huffman(<<192, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111100000:26>>); +enc_huffman(<<193, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111100001:26>>); +enc_huffman(<<194, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111101011:20>>); +enc_huffman(<<195, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111110001:19>>); +enc_huffman(<<196, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111100111:22>>); +enc_huffman(<<197, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111110010:23>>); +enc_huffman(<<198, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111101000:22>>); +enc_huffman(<<199, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111101100:25>>); +enc_huffman(<<200, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111100010:26>>); +enc_huffman(<<201, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111100011:26>>); +enc_huffman(<<202, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111100100:26>>); +enc_huffman(<<203, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111011110:27>>); +enc_huffman(<<204, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111011111:27>>); +enc_huffman(<<205, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111100101:26>>); +enc_huffman(<<206, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111110001:24>>); +enc_huffman(<<207, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111101101:25>>); +enc_huffman(<<208, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111110010:19>>); +enc_huffman(<<209, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111100011:21>>); +enc_huffman(<<210, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111100110:26>>); +enc_huffman(<<211, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111100000:27>>); +enc_huffman(<<212, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111100001:27>>); +enc_huffman(<<213, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111100111:26>>); +enc_huffman(<<214, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111100010:27>>); +enc_huffman(<<215, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111110010:24>>); +enc_huffman(<<216, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111100100:21>>); +enc_huffman(<<217, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111100101:21>>); +enc_huffman(<<218, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111101000:26>>); +enc_huffman(<<219, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111101001:26>>); +enc_huffman(<<220, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111111101:28>>); +enc_huffman(<<221, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111100011:27>>); +enc_huffman(<<222, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111100100:27>>); +enc_huffman(<<223, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111100101:27>>); +enc_huffman(<<224, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111101100:20>>); +enc_huffman(<<225, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111110011:24>>); +enc_huffman(<<226, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111101101:20>>); +enc_huffman(<<227, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111100110:21>>); +enc_huffman(<<228, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111101001:22>>); +enc_huffman(<<229, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111100111:21>>); +enc_huffman(<<230, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111101000:21>>); +enc_huffman(<<231, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111110011:23>>); +enc_huffman(<<232, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111101010:22>>); +enc_huffman(<<233, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111101011:22>>); +enc_huffman(<<234, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111101110:25>>); +enc_huffman(<<235, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111101111:25>>); +enc_huffman(<<236, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111110100:24>>); +enc_huffman(<<237, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111110101:24>>); +enc_huffman(<<238, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111101010:26>>); +enc_huffman(<<239, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111110100:23>>); +enc_huffman(<<240, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111101011:26>>); +enc_huffman(<<241, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111100110:27>>); +enc_huffman(<<242, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111101100:26>>); +enc_huffman(<<243, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111101101:26>>); +enc_huffman(<<244, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111100111:27>>); +enc_huffman(<<245, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111101000:27>>); +enc_huffman(<<246, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111101001:27>>); +enc_huffman(<<247, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111101010:27>>); +enc_huffman(<<248, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111101011:27>>); +enc_huffman(<<249, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#1111111111111111111111111110:28>>); +enc_huffman(<<250, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111101100:27>>); +enc_huffman(<<251, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111101101:27>>); +enc_huffman(<<252, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111101110:27>>); +enc_huffman(<<253, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111101111:27>>); +enc_huffman(<<254, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#111111111111111111111110000:27>>); +enc_huffman(<<255, R/bits>>, A) -> enc_huffman(R, <<A/bits, 2#11111111111111111111101110:26>>). diff --git a/src/cow_qpack.erl b/src/cow_qpack.erl new file mode 100644 index 0000000..a0bb0ee --- /dev/null +++ b/src/cow_qpack.erl @@ -0,0 +1,1198 @@ +%% Copyright (c) 2020, Loïc Hoguin <[email protected]> +%% +%% Permission to use, copy, modify, and/or distribute this software for any +%% purpose with or without fee is hereby granted, provided that the above +%% copyright notice and this permission notice appear in all copies. +%% +%% THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +%% WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +%% MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +%% ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +%% WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +%% ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +%% OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +-module(cow_qpack). +-dialyzer(no_improper_lists). + +-export([init/0]). + +-export([decode_field_section/3]). +-export([execute_encoder_instructions/2]). +-export([decoder_cancel_stream/1]). + +-export([encode_field_section/3]). +-export([execute_decoder_instructions/2]). + +-record(state, { + %% Entries common to encoder and decoder. + size = 0 :: non_neg_integer(), + max_table_capacity = 0 :: non_neg_integer(), + num_dropped = 0 :: non_neg_integer(), + dyn_table = [] :: [{pos_integer(), {binary(), binary()}}], + + %% Entries specific to encoder. + draining_index = 0 +}). + +-opaque state() :: #state{}. +-export_type([state/0]). + +%-ifdef(TEST). +%-include_lib("proper/include/proper.hrl"). +%-endif. + +-include("cow_hpack_common.hrl"). + +%% State initialization. + +-spec init() -> state(). +init() -> + #state{}. + +%% Decoding. + +-spec decode_field_section(binary(), non_neg_integer(), State) + -> {ok, cow_http:headers(), binary(), State} + | {error, qpack_decompression_failed | qpack_encoder_stream_error, atom()} + when State::state(). +decode_field_section(Data, StreamID, State0) -> + {EncodedInsertCount, <<S:1,Rest0/bits>>} = dec_big_int(Data, 0, 0), + ReqInsertCount = decode_req_insert_count(EncodedInsertCount, State0), + {DeltaBase, Rest} = dec_int7(Rest0), + Base = case S of + 0 -> ReqInsertCount + DeltaBase; + 1 -> ReqInsertCount - DeltaBase - 1 + end, + case decode(Rest, State0, Base, []) of + {ok, Headers, State} when ReqInsertCount =:= 0 -> + {ok, Headers, <<>>, State}; + {ok, Headers, State} -> + {ok, Headers, enc_int7(StreamID, 2#1), State}; + Error -> + Error + end. + +decode_req_insert_count(0, _) -> + 0; +decode_req_insert_count(EncodedInsertCount, #state{max_table_capacity=MaxTableCapacity, + num_dropped=NumDropped, dyn_table=DynamicTable}) -> + MaxEntries = MaxTableCapacity div 32, + FullRange = 2 * MaxEntries, + if + EncodedInsertCount > FullRange -> + {error, qpack_decompression_failed, 'TODO'}; + true -> + TotalNumberOfInserts = NumDropped + length(DynamicTable), + MaxValue = TotalNumberOfInserts + MaxEntries, + MaxWrapped = (MaxValue div FullRange) * FullRange, + ReqInsertCount = MaxWrapped + EncodedInsertCount - 1, + if + ReqInsertCount > MaxValue -> + if + ReqInsertCount =< FullRange -> + {error, qpack_decompression_failed, 'TODO'}; + true -> + ReqInsertCount - FullRange + end; + ReqInsertCount =:= 0 -> + {error, qpack_decompression_failed, 'TODO'}; + true -> + ReqInsertCount + end + end. + +decode(<<>>, State, _, Acc) -> + {ok, lists:reverse(Acc), State}; +%% Indexed field line. +decode(<<2#1:1,T:1,Rest0/bits>>, State, Base, Acc) -> + {Index, Rest} = dec_int6(Rest0), + Entry = case T of + 0 -> table_get_dyn_pre_base(Index, Base, State); + 1 -> table_get_static(Index) + end, + decode(Rest, State, Base, [Entry|Acc]); +%% Indexed field line with post-base index. +decode(<<2#0001:4,Rest0/bits>>, State, Base, Acc) -> + {Index, Rest} = dec_int4(Rest0), + Entry = table_get_dyn_post_base(Index, Base, State), + decode(Rest, State, Base, [Entry|Acc]); +%% Literal field line with name reference. +decode(<<2#01:2,N:1,T:1,Rest0/bits>>, State, Base, Acc) -> + %% @todo N=1 the encoded field line MUST be encoded as literal, need to return metadata about this? + {NameIndex, <<H:1,Rest1/bits>>} = dec_int4(Rest0), + Name = case T of +% 0 -> table_get_name_dyn_rel( @todo + 1 -> table_get_name_static(NameIndex) + end, + {ValueLen, Rest2} = dec_int7(Rest1), + {Value, Rest} = maybe_dec_huffman(Rest2, ValueLen, H), + decode(Rest, State, Base, [{Name, Value}|Acc]); +%% Literal field line with post-base name reference. +decode(<<2#0000:4,N:1,Rest0/bits>>, State, Base, Acc) -> + %% @todo N=1 the encoded field line MUST be encoded as literal, need to return metadata about this? + {NameIndex, <<H:1,Rest1/bits>>} = dec_int3(Rest0), + %% @todo NameIndex < Base + %% @todo table_get_name_dyn_post_base( + {ValueLen, Rest2} = dec_int7(Rest1), + <<ValueStr:ValueLen/binary,Rest/bits>> = Rest2, + %% @todo huffman decode when H=1 + todo; +%% Literal field line with literal name. +decode(<<2#001:3,N:1,NameH:1,Rest0/bits>>, State, Base, Acc) -> + %% @todo N=1 the encoded field line MUST be encoded as literal, need to return metadata about this? + {NameLen, Rest1} = dec_int3(Rest0), + <<NameStr:NameLen/binary,ValueH:1,Rest2/bits>> = Rest1, + %% @todo huffman decode when NameH=1 + {ValueLen, Rest3} = dec_int7(Rest2), + <<ValueStr:ValueLen/binary,Rest/bits>> = Rest3, + %% @todo huffman decode when ValueH=1 + todo. + +-spec execute_encoder_instructions(binary(), State) + -> {ok, State} | {error, qpack_encoder_stream_error, atom()} + when State::state(). +execute_encoder_instructions(<<>>, State) -> + {ok, State}; +%% Set dynamic table capacity. +execute_encoder_instructions(<<2#001:3,Rest0/bits>>, State) -> + {Capacity, Rest} = dec_int5(Rest0), + %% @todo + may result in an error + execute_encoder_instructions(Rest, State#state{max_table_capacity=Capacity}); +%% Insert with name reference. +execute_encoder_instructions(<<2#1:1,T:1,Rest0/bits>>, State0) -> + {NameIndex, <<H:1,Rest1/bits>>} = dec_int6(Rest0), + Name = case T of + 0 -> table_get_name_dyn_rel(NameIndex, State0); + 1 -> table_get_name_static(NameIndex) + end, + {ValueLen, Rest2} = dec_int7(Rest1), + {Value, Rest} = maybe_dec_huffman(Rest2, ValueLen, H), + State = table_insert({Name, Value}, State0), + execute_encoder_instructions(Rest, State); +%% Insert with literal name. +execute_encoder_instructions(<<2#01:2,NameH:1,Rest0/bits>>, State0) -> + {NameLen, Rest1} = dec_int5(Rest0), + {Name, <<ValueH:1,Rest2/bits>>} = maybe_dec_huffman(Rest1, NameLen, NameH), + {ValueLen, Rest3} = dec_int7(Rest2), + {Value, Rest} = maybe_dec_huffman(Rest3, ValueLen, ValueH), + State = table_insert({Name, Value}, State0), + execute_encoder_instructions(Rest, State); +%% Duplicate. +execute_encoder_instructions(<<2#000:3,Rest0/bits>>, State0) -> + {Index, Rest} = dec_int5(Rest0), + Entry = table_get_dyn_rel(Index, State0), + State = table_insert(Entry, State0), + execute_encoder_instructions(Rest, State). + +decoder_cancel_stream(StreamID) -> + enc_int6(StreamID, 2#01). + +dec_int3(<<2#111:3,Rest/bits>>) -> + dec_big_int(Rest, 7, 0); +dec_int3(<<Int:3,Rest/bits>>) -> + {Int, Rest}. + +dec_int4(<<2#1111:4,Rest/bits>>) -> + dec_big_int(Rest, 15, 0); +dec_int4(<<Int:4,Rest/bits>>) -> + {Int, Rest}. + +dec_int6(<<2#111111:6,Rest/bits>>) -> + dec_big_int(Rest, 63, 0); +dec_int6(<<Int:6,Rest/bits>>) -> + {Int, Rest}. + +dec_int7(<<2#1111111:7,Rest/bits>>) -> + dec_big_int(Rest, 127, 0); +dec_int7(<<Int:7,Rest/bits>>) -> + {Int, Rest}. + +maybe_dec_huffman(Data, ValueLen, 0) -> + <<Value:ValueLen/binary,Rest/bits>> = Data, + {Value, Rest}; +maybe_dec_huffman(Data, ValueLen, 1) -> + dec_huffman(Data, ValueLen, 0, <<>>). + +%% Encoding. + +-spec encode_field_section(cow_http:headers(), non_neg_integer(), State) + -> {ok, iodata(), binary(), State} when State::state(). +%% @todo Would be good to know encoder stream flow control to avoid writing there. Opts? +encode_field_section(Headers, StreamID, State0) -> + %% @todo Avoid this call, duplicate like in cow_hpack. + encode_field_section(Headers, StreamID, State0, #{}). + +encode_field_section(Headers, StreamID, State0=#state{max_table_capacity=MaxTableCapacity, + num_dropped=NumDropped, dyn_table=DynamicTable}, Opts) -> + Base = NumDropped + length(DynamicTable) + 1, + {ReqInsertCount, EncData, Data, State} = encode( + Headers, StreamID, State0, + huffman_opt(Opts), 0, Base, [], []), + case ReqInsertCount of + 0 -> + {ok, [<<0:16>>|Data], EncData, State}; + _ -> + MaxEntries = MaxTableCapacity div 32, + EncInsertCount = (ReqInsertCount rem (2 * MaxEntries)) + 1, + {S, DeltaBase} = if + ReqInsertCount > Base -> + {2#1, ReqInsertCount - Base}; + %% We never have a base higher than ReqInsertCount because + %% we are updating the dynamic table as we go. + ReqInsertCount =:= Base -> + {2#0, 0} + end, + {ok, [enc_big_int(EncInsertCount, <<>>), enc_int7(DeltaBase, S)|Data], EncData, State} + end. + +encode([], _, State, HuffmanOpt, ReqInsertCount, _, EncAcc, Acc) -> + {ReqInsertCount, lists:reverse(EncAcc), lists:reverse(Acc), State}; +encode([{Name, Value0}|Tail], StreamID, State0, HuffmanOpt, ReqInsertCount0, Base, EncAcc, Acc) -> + %% We conditionally call iolist_to_binary/1 because a small + %% but noticeable speed improvement happens when we do this. + %% (Or at least it did for cow_hpack.) + Value = if + is_binary(Value0) -> Value0; + true -> iolist_to_binary(Value0) + end, + Entry = {Name, Value}, + DrainIndex = 1, %% @todo + case table_find_static(Entry) of + not_found -> + case table_find_dyn(Entry, State0) of + not_found -> + case table_find_name_static(Name) of + not_found -> + todo; + StaticNameIndex -> + case table_can_insert(Entry, State0) of + true -> + State = table_insert(Entry, State0), + #state{num_dropped=NumDropped, dyn_table=DynamicTable} = State, + ReqInsertCount = NumDropped + length(DynamicTable), + PostBaseIndex = length(EncAcc), + encode(Tail, StreamID, State, HuffmanOpt, ReqInsertCount, Base, + [[enc_int6(StaticNameIndex, 2#11)|enc_str(Value, HuffmanOpt)]|EncAcc], + [enc_int4(PostBaseIndex, 2#0001)|Acc]); + false -> + encode(Tail, StreamID, State0, HuffmanOpt, ReqInsertCount0, Base, EncAcc, + [[enc_int4(StaticNameIndex, 2#0101)|enc_str(Value, HuffmanOpt)]|Acc]) + end + end; + %% When the index is below the drain index and there is enough + %% space in the table for duplicating the value, we do that + %% and use the duplicated index. If we can't then we must not + %% use the dynamic index for the field. + DynIndex when DynIndex =< DrainIndex -> + case table_can_insert(Entry, State0) of + true -> + State = table_insert(Entry, State0), + #state{num_dropped=NumDropped, dyn_table=DynamicTable} = State, + ReqInsertCount = NumDropped + length(DynamicTable), + %% - 1 because we already inserted the new entry in the table. + DynIndexRel = ReqInsertCount - DynIndex - 1, + PostBaseIndex = length(EncAcc), + encode(Tail, StreamID, State, HuffmanOpt, ReqInsertCount, Base, + [enc_int5(DynIndexRel, 2#000)|EncAcc], + [enc_int6(Base - ReqInsertCount, 2#10)|Acc]); + false -> + todo %% @todo Same as not_found. + end; + DynIndex -> + %% @todo We should check whether the value is below the drain index + %% and if that's the case we either duplicate or not use the index + %% depending on capacity. + ReqInsertCount = if + ReqInsertCount0 > DynIndex -> ReqInsertCount0; + true -> DynIndex + end, + encode(Tail, StreamID, State0, HuffmanOpt, ReqInsertCount0, Base, EncAcc, + [enc_int6(Base - DynIndex, 2#10)|Acc]) + end; + StaticIndex -> + encode(Tail, StreamID, State0, HuffmanOpt, ReqInsertCount0, Base, EncAcc, + [enc_int6(StaticIndex, 2#11)|Acc]) + end. + +-spec execute_decoder_instructions(binary(), State) + -> {ok, State} | {error, qpack_decoder_stream_error, atom()} + when State::state(). +execute_decoder_instructions(<<>>, State) -> + {ok, State}; +%% Section acknowledgement. +execute_decoder_instructions(<<2#1:1,Rest0/bits>>, State) -> + {StreamID, Rest} = dec_int7(Rest0), + %% @todo Keep track of references. + execute_decoder_instructions(Rest, State); +%% Stream cancellation. +execute_decoder_instructions(<<2#01:2,Rest0/bits>>, State) -> + {StreamID, Rest} = dec_int6(Rest0), + %% @todo Drop references. + execute_decoder_instructions(Rest, State); +%% Insert count increment. +execute_decoder_instructions(<<2#00:2,Rest0/bits>>, State) -> + {Increment, Rest} = dec_int6(Rest0), + %% @todo Keep track of references. + execute_decoder_instructions(Rest, State). + +%% @todo spec +encoder_set_table_capacity(Capacity, State) -> + {ok, enc_int5(Capacity, 2#001), State#state{max_table_capacity=Capacity}}. + +%% @todo spec +encoder_insert_entry(Entry={Name, Value}, State0, Opts) -> + State = table_insert(Entry, State0), + HuffmanOpt = huffman_opt(Opts), + case table_find_name_static(Name) of + not_found -> + case table_find_name_dyn(Name, State0) of + not_found -> + {ok, [enc_str6(Name, HuffmanOpt, 2#01)|enc_str(Value, HuffmanOpt)], State}; + DynNameIndex -> + #state{num_dropped=NumDropped0, dyn_table=DynamicTable0} = State0, + DynNameIndexRel = NumDropped0 + length(DynamicTable0) - DynNameIndex, + {ok, [enc_int6(DynNameIndexRel, 2#10)|enc_str(Value, HuffmanOpt)], State} + end; + StaticNameIndex -> + todo + end. + +huffman_opt(#{huffman := false}) -> no_huffman; +huffman_opt(_) -> huffman. + +enc_int4(Int, Prefix) when Int < 15 -> + <<Prefix:4, Int:4>>; +enc_int4(Int, Prefix) -> + enc_big_int(Int - 15, <<Prefix:4, 2#1111:4>>). + +enc_str6(Str, huffman, Prefix) -> + Str2 = enc_huffman(Str, <<>>), + [enc_int5(byte_size(Str2), Prefix * 2 + 2#1)|Str2]; +enc_str6(Str, no_huffman, Prefix) -> + [enc_int5(byte_size(Str), Prefix * 2 + 2#0)|Str]. + +%% Static and dynamic tables. + +table_find_static({<<":authority">>, <<>>}) -> 0; +table_find_static({<<":path">>, <<"/">>}) -> 1; +table_find_static({<<"age">>, <<"0">>}) -> 2; +table_find_static({<<"content-disposition">>, <<>>}) -> 3; +table_find_static({<<"content-length">>, <<"0">>}) -> 4; +table_find_static({<<"cookie">>, <<>>}) -> 5; +table_find_static({<<"date">>, <<>>}) -> 6; +table_find_static({<<"etag">>, <<>>}) -> 7; +table_find_static({<<"if-modified-since">>, <<>>}) -> 8; +table_find_static({<<"if-none-match">>, <<>>}) -> 9; +table_find_static({<<"last-modified">>, <<>>}) -> 10; +table_find_static({<<"link">>, <<>>}) -> 11; +table_find_static({<<"location">>, <<>>}) -> 12; +table_find_static({<<"referer">>, <<>>}) -> 13; +table_find_static({<<"set-cookie">>, <<>>}) -> 14; +table_find_static({<<":method">>, <<"CONNECT">>}) -> 15; +table_find_static({<<":method">>, <<"DELETE">>}) -> 16; +table_find_static({<<":method">>, <<"GET">>}) -> 17; +table_find_static({<<":method">>, <<"HEAD">>}) -> 18; +table_find_static({<<":method">>, <<"OPTIONS">>}) -> 19; +table_find_static({<<":method">>, <<"POST">>}) -> 20; +table_find_static({<<":method">>, <<"PUT">>}) -> 21; +table_find_static({<<":scheme">>, <<"http">>}) -> 22; +table_find_static({<<":scheme">>, <<"https">>}) -> 23; +table_find_static({<<":status">>, <<"103">>}) -> 24; +table_find_static({<<":status">>, <<"200">>}) -> 25; +table_find_static({<<":status">>, <<"304">>}) -> 26; +table_find_static({<<":status">>, <<"404">>}) -> 27; +table_find_static({<<":status">>, <<"503">>}) -> 28; +table_find_static({<<"accept">>, <<"*/*">>}) -> 29; +table_find_static({<<"accept">>, <<"application/dns-message">>}) -> 30; +table_find_static({<<"accept-encoding">>, <<"gzip, deflate, br">>}) -> 31; +table_find_static({<<"accept-ranges">>, <<"bytes">>}) -> 32; +table_find_static({<<"access-control-allow-headers">>, <<"cache-control">>}) -> 33; +table_find_static({<<"access-control-allow-headers">>, <<"content-type">>}) -> 34; +table_find_static({<<"access-control-allow-origin">>, <<"*">>}) -> 35; +table_find_static({<<"cache-control">>, <<"max-age=0">>}) -> 36; +table_find_static({<<"cache-control">>, <<"max-age=2592000">>}) -> 37; +table_find_static({<<"cache-control">>, <<"max-age=604800">>}) -> 38; +table_find_static({<<"cache-control">>, <<"no-cache">>}) -> 39; +table_find_static({<<"cache-control">>, <<"no-store">>}) -> 40; +table_find_static({<<"cache-control">>, <<"public, max-age=31536000">>}) -> 41; +table_find_static({<<"content-encoding">>, <<"br">>}) -> 42; +table_find_static({<<"content-encoding">>, <<"gzip">>}) -> 43; +table_find_static({<<"content-type">>, <<"application/dns-message">>}) -> 44; +table_find_static({<<"content-type">>, <<"application/javascript">>}) -> 45; +table_find_static({<<"content-type">>, <<"application/json">>}) -> 46; +table_find_static({<<"content-type">>, <<"application/x-www-form-urlencoded">>}) -> 47; +table_find_static({<<"content-type">>, <<"image/gif">>}) -> 48; +table_find_static({<<"content-type">>, <<"image/jpeg">>}) -> 49; +table_find_static({<<"content-type">>, <<"image/png">>}) -> 50; +table_find_static({<<"content-type">>, <<"text/css">>}) -> 51; +table_find_static({<<"content-type">>, <<"text/html; charset=utf-8">>}) -> 52; +table_find_static({<<"content-type">>, <<"text/plain">>}) -> 53; +table_find_static({<<"content-type">>, <<"text/plain;charset=utf-8">>}) -> 54; +table_find_static({<<"range">>, <<"bytes=0-">>}) -> 55; +table_find_static({<<"strict-transport-security">>, <<"max-age=31536000">>}) -> 56; +table_find_static({<<"strict-transport-security">>, <<"max-age=31536000; includesubdomains">>}) -> 57; +table_find_static({<<"strict-transport-security">>, <<"max-age=31536000; includesubdomains; preload">>}) -> 58; +table_find_static({<<"vary">>, <<"accept-encoding">>}) -> 59; +table_find_static({<<"vary">>, <<"origin">>}) -> 60; +table_find_static({<<"x-content-type-options">>, <<"nosniff">>}) -> 61; +table_find_static({<<"x-xss-protection">>, <<"1; mode=block">>}) -> 62; +table_find_static({<<":status">>, <<"100">>}) -> 63; +table_find_static({<<":status">>, <<"204">>}) -> 64; +table_find_static({<<":status">>, <<"206">>}) -> 65; +table_find_static({<<":status">>, <<"302">>}) -> 66; +table_find_static({<<":status">>, <<"400">>}) -> 67; +table_find_static({<<":status">>, <<"403">>}) -> 68; +table_find_static({<<":status">>, <<"421">>}) -> 69; +table_find_static({<<":status">>, <<"425">>}) -> 70; +table_find_static({<<":status">>, <<"500">>}) -> 71; +table_find_static({<<"accept-language">>, <<>>}) -> 72; +table_find_static({<<"access-control-allow-credentials">>, <<"FALSE">>}) -> 73; +table_find_static({<<"access-control-allow-credentials">>, <<"TRUE">>}) -> 74; +table_find_static({<<"access-control-allow-headers">>, <<"*">>}) -> 75; +table_find_static({<<"access-control-allow-methods">>, <<"get">>}) -> 76; +table_find_static({<<"access-control-allow-methods">>, <<"get, post, options">>}) -> 77; +table_find_static({<<"access-control-allow-methods">>, <<"options">>}) -> 78; +table_find_static({<<"access-control-expose-headers">>, <<"content-length">>}) -> 79; +table_find_static({<<"access-control-request-headers">>, <<"content-type">>}) -> 80; +table_find_static({<<"access-control-request-method">>, <<"get">>}) -> 81; +table_find_static({<<"access-control-request-method">>, <<"post">>}) -> 82; +table_find_static({<<"alt-svc">>, <<"clear">>}) -> 83; +table_find_static({<<"authorization">>, <<>>}) -> 84; +table_find_static({<<"content-security-policy">>, <<"script-src 'none'; object-src 'none'; base-uri 'none'">>}) -> 85; +table_find_static({<<"early-data">>, <<"1">>}) -> 86; +table_find_static({<<"expect-ct">>, <<>>}) -> 87; +table_find_static({<<"forwarded">>, <<>>}) -> 88; +table_find_static({<<"if-range">>, <<>>}) -> 89; +table_find_static({<<"origin">>, <<>>}) -> 90; +table_find_static({<<"purpose">>, <<"prefetch">>}) -> 91; +table_find_static({<<"server">>, <<>>}) -> 92; +table_find_static({<<"timing-allow-origin">>, <<"*">>}) -> 93; +table_find_static({<<"upgrade-insecure-requests">>, <<"1">>}) -> 94; +table_find_static({<<"user-agent">>, <<>>}) -> 95; +table_find_static({<<"x-forwarded-for">>, <<>>}) -> 96; +table_find_static({<<"x-frame-options">>, <<"deny">>}) -> 97; +table_find_static({<<"x-frame-options">>, <<"sameorigin">>}) -> 98; +table_find_static(_) -> not_found. + +table_find_name_static(<<":authority">>) -> 0; +table_find_name_static(<<":path">>) -> 1; +table_find_name_static(<<"age">>) -> 2; +table_find_name_static(<<"content-disposition">>) -> 3; +table_find_name_static(<<"content-length">>) -> 4; +table_find_name_static(<<"cookie">>) -> 5; +table_find_name_static(<<"date">>) -> 6; +table_find_name_static(<<"etag">>) -> 7; +table_find_name_static(<<"if-modified-since">>) -> 8; +table_find_name_static(<<"if-none-match">>) -> 9; +table_find_name_static(<<"last-modified">>) -> 10; +table_find_name_static(<<"link">>) -> 11; +table_find_name_static(<<"location">>) -> 12; +table_find_name_static(<<"referer">>) -> 13; +table_find_name_static(<<"set-cookie">>) -> 14; +table_find_name_static(<<":method">>) -> 15; +table_find_name_static(<<":scheme">>) -> 22; +table_find_name_static(<<":status">>) -> 24; +table_find_name_static(<<"accept">>) -> 29; +table_find_name_static(<<"accept-encoding">>) -> 31; +table_find_name_static(<<"accept-ranges">>) -> 32; +table_find_name_static(<<"access-control-allow-headers">>) -> 33; +table_find_name_static(<<"access-control-allow-origin">>) -> 35; +table_find_name_static(<<"cache-control">>) -> 36; +table_find_name_static(<<"content-encoding">>) -> 42; +table_find_name_static(<<"content-type">>) -> 44; +table_find_name_static(<<"range">>) -> 55; +table_find_name_static(<<"strict-transport-security">>) -> 56; +table_find_name_static(<<"vary">>) -> 59; +table_find_name_static(<<"x-content-type-options">>) -> 61; +table_find_name_static(<<"x-xss-protection">>) -> 62; +table_find_name_static(<<"accept-language">>) -> 72; +table_find_name_static(<<"access-control-allow-credentials">>) -> 73; +table_find_name_static(<<"access-control-allow-methods">>) -> 76; +table_find_name_static(<<"access-control-expose-headers">>) -> 79; +table_find_name_static(<<"access-control-request-headers">>) -> 80; +table_find_name_static(<<"access-control-request-method">>) -> 81; +table_find_name_static(<<"alt-svc">>) -> 83; +table_find_name_static(<<"authorization">>) -> 84; +table_find_name_static(<<"content-security-policy">>) -> 85; +table_find_name_static(<<"early-data">>) -> 86; +table_find_name_static(<<"expect-ct">>) -> 87; +table_find_name_static(<<"forwarded">>) -> 88; +table_find_name_static(<<"if-range">>) -> 89; +table_find_name_static(<<"origin">>) -> 90; +table_find_name_static(<<"purpose">>) -> 91; +table_find_name_static(<<"server">>) -> 92; +table_find_name_static(<<"timing-allow-origin">>) -> 93; +table_find_name_static(<<"upgrade-insecure-requests">>) -> 94; +table_find_name_static(<<"user-agent">>) -> 95; +table_find_name_static(<<"x-forwarded-for">>) -> 96; +table_find_name_static(<<"x-frame-options">>) -> 97; +table_find_name_static(_) -> not_found. + +table_get_static(0) -> {<<":authority">>, <<>>}; +table_get_static(1) -> {<<":path">>, <<"/">>}; +table_get_static(2) -> {<<"age">>, <<"0">>}; +table_get_static(3) -> {<<"content-disposition">>, <<>>}; +table_get_static(4) -> {<<"content-length">>, <<"0">>}; +table_get_static(5) -> {<<"cookie">>, <<>>}; +table_get_static(6) -> {<<"date">>, <<>>}; +table_get_static(7) -> {<<"etag">>, <<>>}; +table_get_static(8) -> {<<"if-modified-since">>, <<>>}; +table_get_static(9) -> {<<"if-none-match">>, <<>>}; +table_get_static(10) -> {<<"last-modified">>, <<>>}; +table_get_static(11) -> {<<"link">>, <<>>}; +table_get_static(12) -> {<<"location">>, <<>>}; +table_get_static(13) -> {<<"referer">>, <<>>}; +table_get_static(14) -> {<<"set-cookie">>, <<>>}; +table_get_static(15) -> {<<":method">>, <<"CONNECT">>}; +table_get_static(16) -> {<<":method">>, <<"DELETE">>}; +table_get_static(17) -> {<<":method">>, <<"GET">>}; +table_get_static(18) -> {<<":method">>, <<"HEAD">>}; +table_get_static(19) -> {<<":method">>, <<"OPTIONS">>}; +table_get_static(20) -> {<<":method">>, <<"POST">>}; +table_get_static(21) -> {<<":method">>, <<"PUT">>}; +table_get_static(22) -> {<<":scheme">>, <<"http">>}; +table_get_static(23) -> {<<":scheme">>, <<"https">>}; +table_get_static(24) -> {<<":status">>, <<"103">>}; +table_get_static(25) -> {<<":status">>, <<"200">>}; +table_get_static(26) -> {<<":status">>, <<"304">>}; +table_get_static(27) -> {<<":status">>, <<"404">>}; +table_get_static(28) -> {<<":status">>, <<"503">>}; +table_get_static(29) -> {<<"accept">>, <<"*/*">>}; +table_get_static(30) -> {<<"accept">>, <<"application/dns-message">>}; +table_get_static(31) -> {<<"accept-encoding">>, <<"gzip, deflate, br">>}; +table_get_static(32) -> {<<"accept-ranges">>, <<"bytes">>}; +table_get_static(33) -> {<<"access-control-allow-headers">>, <<"cache-control">>}; +table_get_static(34) -> {<<"access-control-allow-headers">>, <<"content-type">>}; +table_get_static(35) -> {<<"access-control-allow-origin">>, <<"*">>}; +table_get_static(36) -> {<<"cache-control">>, <<"max-age=0">>}; +table_get_static(37) -> {<<"cache-control">>, <<"max-age=2592000">>}; +table_get_static(38) -> {<<"cache-control">>, <<"max-age=604800">>}; +table_get_static(39) -> {<<"cache-control">>, <<"no-cache">>}; +table_get_static(40) -> {<<"cache-control">>, <<"no-store">>}; +table_get_static(41) -> {<<"cache-control">>, <<"public, max-age=31536000">>}; +table_get_static(42) -> {<<"content-encoding">>, <<"br">>}; +table_get_static(43) -> {<<"content-encoding">>, <<"gzip">>}; +table_get_static(44) -> {<<"content-type">>, <<"application/dns-message">>}; +table_get_static(45) -> {<<"content-type">>, <<"application/javascript">>}; +table_get_static(46) -> {<<"content-type">>, <<"application/json">>}; +table_get_static(47) -> {<<"content-type">>, <<"application/x-www-form-urlencoded">>}; +table_get_static(48) -> {<<"content-type">>, <<"image/gif">>}; +table_get_static(49) -> {<<"content-type">>, <<"image/jpeg">>}; +table_get_static(50) -> {<<"content-type">>, <<"image/png">>}; +table_get_static(51) -> {<<"content-type">>, <<"text/css">>}; +table_get_static(52) -> {<<"content-type">>, <<"text/html; charset=utf-8">>}; +table_get_static(53) -> {<<"content-type">>, <<"text/plain">>}; +table_get_static(54) -> {<<"content-type">>, <<"text/plain;charset=utf-8">>}; +table_get_static(55) -> {<<"range">>, <<"bytes=0-">>}; +table_get_static(56) -> {<<"strict-transport-security">>, <<"max-age=31536000">>}; +table_get_static(57) -> {<<"strict-transport-security">>, <<"max-age=31536000; includesubdomains">>}; +table_get_static(58) -> {<<"strict-transport-security">>, <<"max-age=31536000; includesubdomains; preload">>}; +table_get_static(59) -> {<<"vary">>, <<"accept-encoding">>}; +table_get_static(60) -> {<<"vary">>, <<"origin">>}; +table_get_static(61) -> {<<"x-content-type-options">>, <<"nosniff">>}; +table_get_static(62) -> {<<"x-xss-protection">>, <<"1; mode=block">>}; +table_get_static(63) -> {<<":status">>, <<"100">>}; +table_get_static(64) -> {<<":status">>, <<"204">>}; +table_get_static(65) -> {<<":status">>, <<"206">>}; +table_get_static(66) -> {<<":status">>, <<"302">>}; +table_get_static(67) -> {<<":status">>, <<"400">>}; +table_get_static(68) -> {<<":status">>, <<"403">>}; +table_get_static(69) -> {<<":status">>, <<"421">>}; +table_get_static(70) -> {<<":status">>, <<"425">>}; +table_get_static(71) -> {<<":status">>, <<"500">>}; +table_get_static(72) -> {<<"accept-language">>, <<>>}; +table_get_static(73) -> {<<"access-control-allow-credentials">>, <<"FALSE">>}; +table_get_static(74) -> {<<"access-control-allow-credentials">>, <<"TRUE">>}; +table_get_static(75) -> {<<"access-control-allow-headers">>, <<"*">>}; +table_get_static(76) -> {<<"access-control-allow-methods">>, <<"get">>}; +table_get_static(77) -> {<<"access-control-allow-methods">>, <<"get, post, options">>}; +table_get_static(78) -> {<<"access-control-allow-methods">>, <<"options">>}; +table_get_static(79) -> {<<"access-control-expose-headers">>, <<"content-length">>}; +table_get_static(80) -> {<<"access-control-request-headers">>, <<"content-type">>}; +table_get_static(81) -> {<<"access-control-request-method">>, <<"get">>}; +table_get_static(82) -> {<<"access-control-request-method">>, <<"post">>}; +table_get_static(83) -> {<<"alt-svc">>, <<"clear">>}; +table_get_static(84) -> {<<"authorization">>, <<>>}; +table_get_static(85) -> {<<"content-security-policy">>, <<"script-src 'none'; object-src 'none'; base-uri 'none'">>}; +table_get_static(86) -> {<<"early-data">>, <<"1">>}; +table_get_static(87) -> {<<"expect-ct">>, <<>>}; +table_get_static(88) -> {<<"forwarded">>, <<>>}; +table_get_static(89) -> {<<"if-range">>, <<>>}; +table_get_static(90) -> {<<"origin">>, <<>>}; +table_get_static(91) -> {<<"purpose">>, <<"prefetch">>}; +table_get_static(92) -> {<<"server">>, <<>>}; +table_get_static(93) -> {<<"timing-allow-origin">>, <<"*">>}; +table_get_static(94) -> {<<"upgrade-insecure-requests">>, <<"1">>}; +table_get_static(95) -> {<<"user-agent">>, <<>>}; +table_get_static(96) -> {<<"x-forwarded-for">>, <<>>}; +table_get_static(97) -> {<<"x-frame-options">>, <<"deny">>}; +table_get_static(98) -> {<<"x-frame-options">>, <<"sameorigin">>}. + +table_get_name_static(0) -> <<":authority">>; +table_get_name_static(1) -> <<":path">>; +table_get_name_static(2) -> <<"age">>; +table_get_name_static(3) -> <<"content-disposition">>; +table_get_name_static(4) -> <<"content-length">>; +table_get_name_static(5) -> <<"cookie">>; +table_get_name_static(6) -> <<"date">>; +table_get_name_static(7) -> <<"etag">>; +table_get_name_static(8) -> <<"if-modified-since">>; +table_get_name_static(9) -> <<"if-none-match">>; +table_get_name_static(10) -> <<"last-modified">>; +table_get_name_static(11) -> <<"link">>; +table_get_name_static(12) -> <<"location">>; +table_get_name_static(13) -> <<"referer">>; +table_get_name_static(14) -> <<"set-cookie">>; +table_get_name_static(15) -> <<":method">>; +table_get_name_static(16) -> <<":method">>; +table_get_name_static(17) -> <<":method">>; +table_get_name_static(18) -> <<":method">>; +table_get_name_static(19) -> <<":method">>; +table_get_name_static(20) -> <<":method">>; +table_get_name_static(21) -> <<":method">>; +table_get_name_static(22) -> <<":scheme">>; +table_get_name_static(23) -> <<":scheme">>; +table_get_name_static(24) -> <<":status">>; +table_get_name_static(25) -> <<":status">>; +table_get_name_static(26) -> <<":status">>; +table_get_name_static(27) -> <<":status">>; +table_get_name_static(28) -> <<":status">>; +table_get_name_static(29) -> <<"accept">>; +table_get_name_static(30) -> <<"accept">>; +table_get_name_static(31) -> <<"accept-encoding">>; +table_get_name_static(32) -> <<"accept-ranges">>; +table_get_name_static(33) -> <<"access-control-allow-headers">>; +table_get_name_static(34) -> <<"access-control-allow-headers">>; +table_get_name_static(35) -> <<"access-control-allow-origin">>; +table_get_name_static(36) -> <<"cache-control">>; +table_get_name_static(37) -> <<"cache-control">>; +table_get_name_static(38) -> <<"cache-control">>; +table_get_name_static(39) -> <<"cache-control">>; +table_get_name_static(40) -> <<"cache-control">>; +table_get_name_static(41) -> <<"cache-control">>; +table_get_name_static(42) -> <<"content-encoding">>; +table_get_name_static(43) -> <<"content-encoding">>; +table_get_name_static(44) -> <<"content-type">>; +table_get_name_static(45) -> <<"content-type">>; +table_get_name_static(46) -> <<"content-type">>; +table_get_name_static(47) -> <<"content-type">>; +table_get_name_static(48) -> <<"content-type">>; +table_get_name_static(49) -> <<"content-type">>; +table_get_name_static(50) -> <<"content-type">>; +table_get_name_static(51) -> <<"content-type">>; +table_get_name_static(52) -> <<"content-type">>; +table_get_name_static(53) -> <<"content-type">>; +table_get_name_static(54) -> <<"content-type">>; +table_get_name_static(55) -> <<"range">>; +table_get_name_static(56) -> <<"strict-transport-security">>; +table_get_name_static(57) -> <<"strict-transport-security">>; +table_get_name_static(58) -> <<"strict-transport-security">>; +table_get_name_static(59) -> <<"vary">>; +table_get_name_static(60) -> <<"vary">>; +table_get_name_static(61) -> <<"x-content-type-options">>; +table_get_name_static(62) -> <<"x-xss-protection">>; +table_get_name_static(63) -> <<":status">>; +table_get_name_static(64) -> <<":status">>; +table_get_name_static(65) -> <<":status">>; +table_get_name_static(66) -> <<":status">>; +table_get_name_static(67) -> <<":status">>; +table_get_name_static(68) -> <<":status">>; +table_get_name_static(69) -> <<":status">>; +table_get_name_static(70) -> <<":status">>; +table_get_name_static(71) -> <<":status">>; +table_get_name_static(72) -> <<"accept-language">>; +table_get_name_static(73) -> <<"access-control-allow-credentials">>; +table_get_name_static(74) -> <<"access-control-allow-credentials">>; +table_get_name_static(75) -> <<"access-control-allow-headers">>; +table_get_name_static(76) -> <<"access-control-allow-methods">>; +table_get_name_static(77) -> <<"access-control-allow-methods">>; +table_get_name_static(78) -> <<"access-control-allow-methods">>; +table_get_name_static(79) -> <<"access-control-expose-headers">>; +table_get_name_static(80) -> <<"access-control-request-headers">>; +table_get_name_static(81) -> <<"access-control-request-method">>; +table_get_name_static(82) -> <<"access-control-request-method">>; +table_get_name_static(83) -> <<"alt-svc">>; +table_get_name_static(84) -> <<"authorization">>; +table_get_name_static(85) -> <<"content-security-policy">>; +table_get_name_static(86) -> <<"early-data">>; +table_get_name_static(87) -> <<"expect-ct">>; +table_get_name_static(88) -> <<"forwarded">>; +table_get_name_static(89) -> <<"if-range">>; +table_get_name_static(90) -> <<"origin">>; +table_get_name_static(91) -> <<"purpose">>; +table_get_name_static(92) -> <<"server">>; +table_get_name_static(93) -> <<"timing-allow-origin">>; +table_get_name_static(94) -> <<"upgrade-insecure-requests">>; +table_get_name_static(95) -> <<"user-agent">>; +table_get_name_static(96) -> <<"x-forwarded-for">>; +table_get_name_static(97) -> <<"x-frame-options">>; +table_get_name_static(98) -> <<"x-frame-options">>. + +%% @todo We should check if we can evict. +%% @todo We should make sure we have a large enough flow control window. +table_can_insert({Name, Value}, #state{size=Size, max_table_capacity=MaxTableCapacity}) -> + EntrySize = byte_size(Name) + byte_size(Value) + 32, + if + EntrySize + Size =< MaxTableCapacity -> + true; + true -> + false + end. + +table_insert(Entry={Name, Value}, State=#state{size=Size0, max_table_capacity=MaxTableCapacity, + num_dropped=NumDropped, dyn_table=DynamicTable0}) -> + EntrySize = byte_size(Name) + byte_size(Value) + 32, + if + EntrySize + Size0 =< MaxTableCapacity -> + State#state{size=Size0 + EntrySize, dyn_table=[{EntrySize, Entry}|DynamicTable0]}; + EntrySize =< MaxTableCapacity -> + case table_evict(DynamicTable0, MaxTableCapacity - EntrySize, 0, []) of + Error={error, _, _} -> + Error; + {DynamicTable, Size, NewDropped} -> + State#state{size=Size + EntrySize, num_dropped=NumDropped + NewDropped, + dyn_table=[{EntrySize, Entry}|DynamicTable]} + end; + true -> % EntrySize > MaxTableCapacity -> + {error, qpack_encoder_stream_error, 'TODO'} + end. + +table_evict([], _, Size, Acc) -> + {lists:reverse(Acc), Size, 0}; +%% @todo Need to check whether entries are evictable. +table_evict(Dropped=[{EntrySize, _}|_], MaxSize, Size, Acc) when Size + EntrySize > MaxSize -> + {lists:reverse(Acc), Size, length(Dropped)}; +table_evict([Entry = {EntrySize, _}|Tail], MaxSize, Size, Acc) -> + table_evict(Tail, MaxSize, Size + EntrySize, [Entry|Acc]). + +table_find_dyn(Entry, #state{num_dropped=NumDropped, dyn_table=DynamicTable}) -> + table_find_dyn(Entry, DynamicTable, NumDropped + length(DynamicTable)). + +table_find_dyn(_, [], _) -> + not_found; +table_find_dyn(Entry, [{_, Entry}|_], Index) -> + Index; +table_find_dyn(Entry, [_|Tail], Index) -> + table_find_dyn(Entry, Tail, Index - 1). + +table_find_name_dyn(Name, #state{num_dropped=NumDropped, dyn_table=DynamicTable}) -> + table_find_name_dyn(Name, DynamicTable, NumDropped + length(DynamicTable)). + +table_find_name_dyn(_, [], _) -> + not_found; +table_find_name_dyn(Name, [{_, {Name, _}}|_], Index) -> + Index; +table_find_name_dyn(Name, [_|Tail], Index) -> + table_find_name_dyn(Name, Tail, Index - 1). + +%% @todo These functions may error out if the encoder is invalid (2.2.3. Invalid References). +table_get_dyn_abs(Index, #state{num_dropped=NumDropped, dyn_table=DynamicTable}) -> + %% @todo Perhaps avoid this length/1 call. + {_, Header} = lists:nth(NumDropped + length(DynamicTable) - Index, DynamicTable), + Header. + +table_get_dyn_rel(Index, #state{dyn_table=DynamicTable}) -> + {_, Header} = lists:nth(1 + Index, DynamicTable), + Header. + +table_get_name_dyn_rel(Index, State) -> + {Name, _} = table_get_dyn_rel(Index, State), + Name. + +table_get_dyn_pre_base(Index, Base, #state{num_dropped=NumDropped, dyn_table=DynamicTable}) -> + %% @todo Perhaps avoid this length/1 call. + BaseOffset = NumDropped + length(DynamicTable) - Base, + {_, Header} = lists:nth(1 + Index + BaseOffset, DynamicTable), + Header. + +table_get_dyn_post_base(Index, Base, State) -> + table_get_dyn_abs(Base + Index, State). + +-ifdef(TEST). +%% @todo table_insert_test including evictions + +table_get_dyn_abs_test() -> + State0 = (init())#state{max_table_capacity=1000}, + State1 = table_insert({<<"g">>, <<"h">>}, + table_insert({<<"e">>, <<"f">>}, + table_insert({<<"c">>, <<"d">>}, + table_insert({<<"a">>, <<"b">>}, + State0)))), + {<<"a">>, <<"b">>} = table_get_dyn_abs(0, State1), + {<<"c">>, <<"d">>} = table_get_dyn_abs(1, State1), + {<<"e">>, <<"f">>} = table_get_dyn_abs(2, State1), + {<<"g">>, <<"h">>} = table_get_dyn_abs(3, State1), + %% Evict one member from the table. + #state{dyn_table=DynamicTable} = State1, + State2 = State1#state{num_dropped=1, dyn_table=lists:reverse(tl(lists:reverse(DynamicTable)))}, + {<<"c">>, <<"d">>} = table_get_dyn_abs(1, State2), + {<<"e">>, <<"f">>} = table_get_dyn_abs(2, State2), + {<<"g">>, <<"h">>} = table_get_dyn_abs(3, State2), + ok. + +table_get_dyn_rel_test() -> + State0 = (init())#state{max_table_capacity=1000}, + State1 = table_insert({<<"g">>, <<"h">>}, + table_insert({<<"e">>, <<"f">>}, + table_insert({<<"c">>, <<"d">>}, + table_insert({<<"a">>, <<"b">>}, + State0)))), + {<<"g">>, <<"h">>} = table_get_dyn_rel(0, State1), + {<<"e">>, <<"f">>} = table_get_dyn_rel(1, State1), + {<<"c">>, <<"d">>} = table_get_dyn_rel(2, State1), + {<<"a">>, <<"b">>} = table_get_dyn_rel(3, State1), + %% Evict one member from the table. + #state{dyn_table=DynamicTable} = State1, + State2 = State1#state{num_dropped=1, dyn_table=lists:reverse(tl(lists:reverse(DynamicTable)))}, + {<<"g">>, <<"h">>} = table_get_dyn_rel(0, State2), + {<<"e">>, <<"f">>} = table_get_dyn_rel(1, State2), + {<<"c">>, <<"d">>} = table_get_dyn_rel(2, State2), + %% Add a member to the table. + State3 = table_insert({<<"i">>, <<"j">>}, State2), + {<<"i">>, <<"j">>} = table_get_dyn_rel(0, State3), + {<<"g">>, <<"h">>} = table_get_dyn_rel(1, State3), + {<<"e">>, <<"f">>} = table_get_dyn_rel(2, State3), + {<<"c">>, <<"d">>} = table_get_dyn_rel(3, State3), + ok. + +table_get_dyn_pre_base_test() -> + State0 = (init())#state{max_table_capacity=1000}, + State1 = table_insert({<<"g">>, <<"h">>}, + table_insert({<<"e">>, <<"f">>}, + table_insert({<<"c">>, <<"d">>}, + table_insert({<<"a">>, <<"b">>}, + State0)))), + {<<"e">>, <<"f">>} = table_get_dyn_pre_base(0, 3, State1), + {<<"c">>, <<"d">>} = table_get_dyn_pre_base(1, 3, State1), + {<<"a">>, <<"b">>} = table_get_dyn_pre_base(2, 3, State1), + %% Evict one member from the table. + #state{dyn_table=DynamicTable} = State1, + State2 = State1#state{num_dropped=1, dyn_table=lists:reverse(tl(lists:reverse(DynamicTable)))}, + {<<"e">>, <<"f">>} = table_get_dyn_pre_base(0, 3, State2), + {<<"c">>, <<"d">>} = table_get_dyn_pre_base(1, 3, State2), + %% Add a member to the table. + State3 = table_insert({<<"i">>, <<"j">>}, State2), + {<<"e">>, <<"f">>} = table_get_dyn_pre_base(0, 3, State3), + {<<"c">>, <<"d">>} = table_get_dyn_pre_base(1, 3, State3), + ok. + +table_get_dyn_post_base_test() -> + State0 = (init())#state{max_table_capacity=1000}, + State1 = table_insert({<<"g">>, <<"h">>}, + table_insert({<<"e">>, <<"f">>}, + table_insert({<<"c">>, <<"d">>}, + table_insert({<<"a">>, <<"b">>}, + State0)))), + {<<"e">>, <<"f">>} = table_get_dyn_post_base(0, 2, State1), + {<<"g">>, <<"h">>} = table_get_dyn_post_base(1, 2, State1), + %% Evict one member from the table. + #state{dyn_table=DynamicTable} = State1, + State2 = State1#state{num_dropped=1, dyn_table=lists:reverse(tl(lists:reverse(DynamicTable)))}, + {<<"e">>, <<"f">>} = table_get_dyn_post_base(0, 2, State2), + {<<"g">>, <<"h">>} = table_get_dyn_post_base(1, 2, State2), + %% Add a member to the table. + State3 = table_insert({<<"i">>, <<"j">>}, State2), + {<<"e">>, <<"f">>} = table_get_dyn_post_base(0, 2, State3), + {<<"g">>, <<"h">>} = table_get_dyn_post_base(1, 2, State3), + {<<"i">>, <<"j">>} = table_get_dyn_post_base(2, 2, State3), + ok. +-endif. + +-ifdef(TEST). +appendix_b_decoder_test() -> + %% Stream: 0 + {ok, [ + {<<":path">>, <<"/index.html">>} + ], <<>>, DecState0} = decode_field_section(<< + 16#0000:16, + 16#510b:16, 16#2f69:16, 16#6e64:16, 16#6578:16, + 16#2e68:16, 16#746d:16, 16#6c + >>, 0, init()), + #state{ + size=0, + max_table_capacity=0, + num_dropped=0, + dyn_table=[] + } = DecState0, + %% Stream: Encoder + {ok, DecState1} = execute_encoder_instructions(<< + 16#3fbd01:24, + 16#c00f:16, 16#7777:16, 16#772e:16, 16#6578:16, + 16#616d:16, 16#706c:16, 16#652e:16, 16#636f:16, + 16#6d, + 16#c10c:16, 16#2f73:16, 16#616d:16, 16#706c:16, + 16#652f:16, 16#7061:16, 16#7468:16 + >>, DecState0), + #state{ + size=106, + max_table_capacity=220, + num_dropped=0, + %% The dynamic table is in reverse order. + dyn_table=[ + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ] + } = DecState1, + %% Stream: 4 + {ok, [ + {<<":authority">>, <<"www.example.com">>}, + {<<":path">>, <<"/sample/path">>} + ], <<16#84>>, DecState2} = decode_field_section(<< + 16#0381:16, + 16#10, + 16#11 + >>, 4, DecState1), + DecState1 = DecState2, +%% @todo +%% Stream: Decoder +% {ok, EncState3} = execute_decoder_instructions(<< +% 16#84 +% >>, EncState2), + %% Stream: Encoder + {ok, DecState3} = execute_encoder_instructions(<< + 16#4a63:16, 16#7573:16, 16#746f:16, 16#6d2d:16, + 16#6b65:16, 16#790c:16, 16#6375:16, 16#7374:16, + 16#6f6d:16, 16#2d76:16, 16#616c:16, 16#7565:16 + >>, DecState2), + #state{ + size=160, + max_table_capacity=220, + num_dropped=0, + dyn_table=[ + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ] + } = DecState3, +%% @todo +%% Stream: Decoder +% {ok, EncStateX} = execute_decoder_instructions(<< +% 16#01 +% >>, EncStateY), + %% Stream: Encoder + {ok, DecState4} = execute_encoder_instructions(<< + 16#02 + >>, DecState3), + #state{ + size=217, + max_table_capacity=220, + num_dropped=0, + dyn_table=[ + {57, {<<":authority">>, <<"www.example.com">>}}, + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ] + } = DecState4, + %% Stream: 8 + %% + %% Note that this one is not really received by the decoder + %% so we will ignore the decoder state and instructions before we continue. + {ok, [ + {<<":authority">>, <<"www.example.com">>}, + {<<":path">>, <<"/">>}, + {<<"custom-key">>, <<"custom-value">>} + ], <<16#88>>, IgnoredDecState} = decode_field_section(<< + 16#0500:16, + 16#80, + 16#c1, + 16#81 + >>, 8, DecState4), + %% @todo True for now, but we need to keep track of non-evictable entries. (Even in the decoder though?) + DecState4 = IgnoredDecState, + %% Stream: Decoder - Stream Cancellation (Stream=8) + <<16#48>> = decoder_cancel_stream(8), +%% @todo +%% Stream: Decoder +% {ok, EncStateX} = execute_decoder_instructions(<< +% 16#48 +% >>, EncStateY), + {ok, DecState5} = execute_encoder_instructions(<< + 16#810d:16, 16#6375:16, 16#7374:16, 16#6f6d:16, + 16#2d76:16, 16#616c:16, 16#7565:16, 16#32 + >>, DecState4), + #state{ + size=215, + max_table_capacity=220, + num_dropped=1, + dyn_table=[ + {55, {<<"custom-key">>, <<"custom-value2">>}}, + {57, {<<":authority">>, <<"www.example.com">>}}, + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}} + ] + } = DecState5, + ok. + +appendix_b_encoder_test() -> + %% Stream: 0 + {ok, Data0, EncData0, EncState0} = encode_field_section([ + {<<":path">>, <<"/index.html">>} + ], 0, init(), #{huffman => false}), + <<>> = iolist_to_binary(EncData0), + << + 16#0000:16, + 16#510b:16, 16#2f69:16, 16#6e64:16, 16#6578:16, + 16#2e68:16, 16#746d:16, 16#6c + >> = iolist_to_binary(Data0), + #state{ + size=0, + max_table_capacity=0, + num_dropped=0, + dyn_table=[], + draining_index=0 + } = EncState0, + %% Stream: Encoder + {ok, <<16#3fbd01:24>>, EncState1} = encoder_set_table_capacity(220, EncState0), + #state{ + size=0, + max_table_capacity=220, + num_dropped=0, + dyn_table=[], + draining_index=0 + } = EncState1, + %% Stream: 4 (and Encoder) + {ok, Data2, EncData2, EncState2} = encode_field_section([ + {<<":authority">>, <<"www.example.com">>}, + {<<":path">>, <<"/sample/path">>} + ], 4, EncState1, #{huffman => false}), + << + 16#c00f:16, 16#7777:16, 16#772e:16, 16#6578:16, + 16#616d:16, 16#706c:16, 16#652e:16, 16#636f:16, + 16#6d, + 16#c10c:16, 16#2f73:16, 16#616d:16, 16#706c:16, + 16#652f:16, 16#7061:16, 16#7468:16 + >> = iolist_to_binary(EncData2), + << + 16#0381:16, + 16#10, + 16#11 + >> = iolist_to_binary(Data2), + #state{ + size=106, + max_table_capacity=220, + num_dropped=0, + %% The dynamic table is in reverse order. + dyn_table=[ + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ], + draining_index=0 + } = EncState2, + %% Stream: Decoder + {ok, EncState3} = execute_decoder_instructions(<<16#84>>, EncState2), + %% @todo We should keep track of what was acknowledged. + #state{ + size=106, + max_table_capacity=220, + num_dropped=0, + %% The dynamic table is in reverse order. + dyn_table=[ + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ], + draining_index=0 + } = EncState3, + %% Stream: Encoder + {ok, EncData4, EncState4} = encoder_insert_entry( + {<<"custom-key">>, <<"custom-value">>}, + EncState3, #{huffman => false}), + << + 16#4a63:16, 16#7573:16, 16#746f:16, 16#6d2d:16, + 16#6b65:16, 16#790c:16, 16#6375:16, 16#7374:16, + 16#6f6d:16, 16#2d76:16, 16#616c:16, 16#7565:16 + >> = iolist_to_binary(EncData4), + %% @todo This is probably where we ought to increment the draining_index. + #state{ + size=160, + max_table_capacity=220, + num_dropped=0, + %% The dynamic table is in reverse order. + dyn_table=[ + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ], + draining_index=0 + } = EncState4, + %% Stream: Decoder + {ok, EncState5} = execute_decoder_instructions(<<16#01>>, EncState4), + %% @todo We should keep track of what was acknowledged. + #state{ + size=160, + max_table_capacity=220, + num_dropped=0, + %% The dynamic table is in reverse order. + dyn_table=[ + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ], + draining_index=0 + } = EncState5, + %% Stream: 8 (and Encoder) + {ok, Data6, EncData6, EncState6} = encode_field_section([ + {<<":authority">>, <<"www.example.com">>}, + {<<":path">>, <<"/">>}, + {<<"custom-key">>, <<"custom-value">>} + ], 8, EncState5), + <<16#02>> = iolist_to_binary(EncData6), + << + 16#0500:16, + 16#80, + 16#c1, + 16#81 + >> = iolist_to_binary(Data6), + #state{ + size=217, + max_table_capacity=220, + num_dropped=0, + %% The dynamic table is in reverse order. + dyn_table=[ + {57, {<<":authority">>, <<"www.example.com">>}}, + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ], + draining_index=0 + } = EncState6, + %% Stream: Decoder + {ok, EncState7} = execute_decoder_instructions(<<16#48>>, EncState6), + %% @todo We should keep track of references. + #state{ + size=217, + max_table_capacity=220, + num_dropped=0, + %% The dynamic table is in reverse order. + dyn_table=[ + {57, {<<":authority">>, <<"www.example.com">>}}, + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ], + draining_index=0 + } = EncState7, + %% Stream: Encoder + {ok, EncData8, EncState8} = encoder_insert_entry( + {<<"custom-key">>, <<"custom-value2">>}, + EncState7, #{huffman => false}), + << + 16#810d:16, 16#6375:16, 16#7374:16, 16#6f6d:16, + 16#2d76:16, 16#616c:16, 16#7565:16, 16#32 + >> = iolist_to_binary(EncData8), + #state{ + size=215, + max_table_capacity=220, + num_dropped=1, + %% The dynamic table is in reverse order. + dyn_table=[ + {55, {<<"custom-key">>, <<"custom-value2">>}}, + {57, {<<":authority">>, <<"www.example.com">>}}, + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}} + ], + draining_index=0 + } = EncState8, + ok. +-endif. |