diff options
Diffstat (limited to 'src/cow_qpack.erl')
| -rw-r--r-- | src/cow_qpack.erl | 1581 |
1 files changed, 1581 insertions, 0 deletions
diff --git a/src/cow_qpack.erl b/src/cow_qpack.erl new file mode 100644 index 0000000..027e29c --- /dev/null +++ b/src/cow_qpack.erl @@ -0,0 +1,1581 @@ +%% Copyright (c) 2020-2024, 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/1]). +-export([init/3]). + +-export([decode_field_section/3]). +-export([execute_encoder_instructions/2]). +-export([decoder_cancel_stream/1]). %% @todo Use it. + +-export([encode_field_section/3]). +-export([encode_field_section/4]). +-export([execute_decoder_instructions/2]). +-export([encoder_set_settings/3]). + +-record(state, { + %% Configuration. + %% + %% For the encoder these values will be set to + %% the lowest value between configuration and SETTINGS. + + %% Whether the configured values can be used. The + %% decoder can always use the configured values. + %% The encoder must wait for the SETTINGS frame. + settings_received :: boolean(), + + %% Maximum size of the table. + max_table_capacity = 0 :: non_neg_integer(), + + %% Maximum number of potentially blocked streams. + max_blocked_streams = 0 :: non_neg_integer(), + + %% Dynamic table. + + %% The current max table capacity after the encoder + %% sent an instruction to change the capacity. + capacity = 0 :: non_neg_integer(), + + %% The size of each entry is len(Name) + len(Value) + 32. + size = 0 :: non_neg_integer(), + + %% The number of entries ever inserted in the dynamic table. + %% This value is used on the decoder's size to know whether + %% it can decode a field section; and on both sides to find + %% entries in the dynamic table. + insert_count = 0 :: non_neg_integer(), + + %% The dynamic table. The first value is the size of the entry + %% and the second value the entry (Name, Value tuple). The + %% order of the entries is from newest to oldest. + %% + %% If 4 entries were inserted, the index of each entry would + %% be [3, 2, 1, 0]. If 4 entries were inserted and 1 of them + %% was later dropped, the index of each entry remaining would + %% be [3, 2, 1] and the insert_count value would be 3, allowing + %% us to know what index the newest entry is using. + dyn_table = [] :: [{pos_integer(), {binary(), binary()}}], + + %% Decoder-specific state. + + %% We keep track of streams that are currently blocked + %% in a map for easy counting and removal. A stream may + %% be blocked at the beginning of the decoding process. + %% A stream may be unblocked after encoder instructions + %% have been processed. + blocked_streams = #{} :: #{cow_http3:stream_id() => true}, + + %% Encoder-specific state. + + %% We keep track of the known received count of the + %% decoder (the insert_count it has that we know of) + %% so that we know when we can evict an entry we + %% inserted. We cannot evict an entry before it has + %% been acknowledged. The known received count can + %% also be used to avoid blocking. + known_received_count = 0 :: non_neg_integer(), + + %% We keep track of the streams that have used the + %% dynamic table in order to increase the known + %% received count when the decoder acks a stream. + %% We only keep the insert_count value for a stream's + %% field section. + %% + %% Because a stream can send multiple field sections + %% (informational response, final response, trailers), + %% we use a list to keep track of the different sections. + %% A FIFO structure would be more adequate but we do + %% not expect a lot of field sections per stream. + references = #{} :: #{cow_http3:stream_id() => [non_neg_integer()]}, + + %% Smallest absolute index the encoder will reference. + %% Indexes below may exist in the dynamic table but are + %% in the process of being phased out and will eventually + %% be evicted. Only duplicating these indexes is allowed. + draining_index = 0 :: non_neg_integer(), + + %% Size of the dynamic table that is available for + %% eviction during encoding. Both this value and the + %% draining_index are computed at the start of encoding. + %% Note that for the encoder this cannot reach negatives, + %% but might for the decoder. + draining_size = 0 :: integer() +}). + +-opaque state() :: #state{}. +-export_type([state/0]). + +-type error() :: qpack_decompression_failed + | qpack_encoder_stream_error + | qpack_decoder_stream_error. +-export_type([error/0]). + +-type encoder_opts() :: #{ + huffman => boolean() +}. +-export_type([encoder_opts/0]). + +%-ifdef(TEST). +%-include_lib("proper/include/proper.hrl"). +%-endif. + +-include("cow_hpack_common.hrl"). + +%% State initialization. + +-spec init(decoder | encoder) -> state(). + +init(Role) -> + init(Role, 4096, 0). + +-spec init(decoder | encoder, non_neg_integer(), non_neg_integer()) -> state(). + +init(Role, MaxTableCapacity, MaxBlockedStreams) -> + #state{ + settings_received=Role =:= decoder, + max_table_capacity=MaxTableCapacity, + max_blocked_streams=MaxBlockedStreams + }. + +%% Decoding. + +-spec decode_field_section(binary(), cow_http3:stream_id(), State) + -> {ok, cow_http:headers(), binary(), State} + | {blocked, State} + | {connection_error, error(), atom()} + when State::state(). + +decode_field_section(Data, StreamID, State=#state{max_blocked_streams=MaxBlockedStreams, + insert_count=InsertCount, blocked_streams=BlockedStreams}) -> + {EncInsertCount, Rest} = dec_big_int(Data, 0, 0), + ReqInsertCount = decode_req_insert_count(EncInsertCount, State), + if + ReqInsertCount =< InsertCount -> + decode_field_section(Rest, StreamID, State, ReqInsertCount); + %% The stream is blocked and we do not allow that; + %% or there are already too many blocked streams. + map_size(BlockedStreams) > MaxBlockedStreams -> + {connection_error, qpack_decompression_failed, + 'More blocked streams than configuration allows. (RFC9204 2.1.2)'}; + %% The stream is blocked and we allow that. + %% The caller must keep the data and retry after + %% calling the execute_encoder_instructions function. + true -> + {blocked, State#state{blocked_streams=BlockedStreams#{StreamID => true}}} + end. + +decode_field_section(<<S:1,Rest0/bits>>, StreamID, + State0=#state{blocked_streams=BlockedStreams}, ReqInsertCount) -> + State1 = State0#state{ + %% The stream may have been blocked. Unblock it. + blocked_streams=maps:remove(StreamID, BlockedStreams), + %% Reset the draining_size. We don't use it, but don't + %% want the value to unnecessarily become a big int. + draining_size=0 + }, + {DeltaBase, Rest} = dec_int7(Rest0), + Base = case S of + 0 -> ReqInsertCount + DeltaBase; + 1 -> ReqInsertCount - DeltaBase - 1 + end, + case decode(Rest, State1, Base, []) of + {ok, Headers, State} when ReqInsertCount =:= 0 -> + {ok, Headers, <<>>, State}; + {ok, Headers, State} -> + {ok, Headers, enc_int7(StreamID, 2#1), State} + end. + +decode_req_insert_count(0, _) -> + 0; +decode_req_insert_count(EncInsertCount, #state{ + max_table_capacity=MaxTableCapacity, insert_count=InsertCount}) -> + MaxEntries = MaxTableCapacity div 32, + FullRange = 2 * MaxEntries, + if + EncInsertCount > FullRange -> + {connection_error, qpack_decompression_failed, + 'EncInsertCount larger than maximum possible value. (RFC9204 4.5.1.1)'}; + true -> + MaxValue = InsertCount + MaxEntries, + MaxWrapped = (MaxValue div FullRange) * FullRange, + ReqInsertCount = MaxWrapped + EncInsertCount - 1, + if + ReqInsertCount > MaxValue -> + if + ReqInsertCount =< FullRange -> + {connection_error, qpack_decompression_failed, + 'ReqInsertCount value larger than current maximum value. (RFC9204 4.5.1.1)'}; + true -> + ReqInsertCount - FullRange + end; + ReqInsertCount =:= 0 -> + {connection_error, qpack_decompression_failed, + 'ReqInsertCount value of 0 must be encoded as 0. (RFC9204 4.5.1.1)'}; + 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(NameIndex, State); + 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), + Name = table_get_name_dyn_post_base(NameIndex, Base, State), + {ValueLen, Rest2} = dec_int7(Rest1), + {Value, Rest} = maybe_dec_huffman(Rest2, ValueLen, H), + decode(Rest, State, Base, [{Name, Value}|Acc]); +%% 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, + {Name, <<>>} = maybe_dec_huffman(NameStr, NameLen, NameH), + {ValueLen, Rest3} = dec_int7(Rest2), + {Value, Rest} = maybe_dec_huffman(Rest3, ValueLen, ValueH), + decode(Rest, State, Base, [{Name, Value}|Acc]). + +-spec execute_encoder_instructions(binary(), State) + -> {ok, binary(), State} + | {connection_error, qpack_encoder_stream_error, atom()} + when State::state(). + +execute_encoder_instructions(Data, State) -> + execute_encoder_instructions(Data, State, 0). + +execute_encoder_instructions(<<>>, State, 0) -> + {ok, <<>>, State}; +execute_encoder_instructions(<<>>, State, Increment) -> + {ok, enc_int6(Increment, 2#00), State}; +%% Set dynamic table capacity. +execute_encoder_instructions(<<2#001:3,Rest0/bits>>, State=#state{ + max_table_capacity=MaxTableCapacity, capacity=Capacity0, + dyn_table=DynamicTable0}, Increment) -> + {Capacity, Rest} = dec_int5(Rest0), + if + %% Capacity larger than configured, or dynamic table + %% disabled when max_table_capacity=0. + Capacity > MaxTableCapacity -> + {connection_error, qpack_encoder_stream_error, + 'New table capacity higher than SETTINGS_QPACK_MAX_TABLE_CAPACITY. (RFC9204 3.2.3, RFC9204 4.3.1)'}; + %% Table capacity was reduced. We must evict entries. + Capacity < Capacity0 -> + {DynamicTable, Size} = table_evict(DynamicTable0, Capacity, 0, []), + execute_encoder_instructions(Rest, State#state{capacity=Capacity, + size=Size, dyn_table=DynamicTable}, Increment); + %% Table capacity equal or higher than previous. + true -> + execute_encoder_instructions(Rest, + State#state{capacity=Capacity}, Increment) + end; +%% Insert with name reference. +execute_encoder_instructions(<<2#1:1,T:1,Rest0/bits>>, State, Increment) -> + {NameIndex, <<H:1,Rest1/bits>>} = dec_int6(Rest0), + Name = case T of + 0 -> table_get_name_dyn_rel(NameIndex, State); + 1 -> table_get_name_static(NameIndex) + end, + {ValueLen, Rest2} = dec_int7(Rest1), + {Value, Rest} = maybe_dec_huffman(Rest2, ValueLen, H), + execute_insert_instruction(Rest, State, Increment, {Name, Value}); +%% Insert with literal name. +execute_encoder_instructions(<<2#01:2,NameH:1,Rest0/bits>>, State, Increment) -> + {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), + execute_insert_instruction(Rest, State, Increment, {Name, Value}); +%% Duplicate. +execute_encoder_instructions(<<2#000:3,Rest0/bits>>, State, Increment) -> + {Index, Rest} = dec_int5(Rest0), + Entry = table_get_dyn_rel(Index, State), + execute_insert_instruction(Rest, State, Increment, Entry). + +execute_insert_instruction(Rest, State0, Increment, Entry) -> + case table_insert(Entry, State0) of + {ok, State} -> + execute_encoder_instructions(Rest, State, Increment + 1); + Error = {connection_error, _, _} -> + Error + end. + +%% @todo Export / spec. + +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, <<>>). + +-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(decoder, 4096, 0)), + #state{ + capacity=0, + size=0, + insert_count=0, + dyn_table=[] + } = DecState0, + %% Stream: Encoder + {ok, EncData1, 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), + <<2#00:2,2:6>> = EncData1, + #state{ + capacity=220, + size=106, + insert_count=2, + %% 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, + %% Stream: Encoder + {ok, EncData3, 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), + <<2#00:2,1:6>> = EncData3, + #state{ + capacity=220, + size=160, + insert_count=3, + dyn_table=[ + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ] + } = DecState3, + %% Stream: Encoder + {ok, EncData4, DecState4} = execute_encoder_instructions(<< + 16#02 + >>, DecState3), + <<2#00:2,1:6>> = EncData4, + #state{ + capacity=220, + size=217, + insert_count=4, + 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 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), + %% Note that the state did not change anyway. + DecState4 = IgnoredDecState, + %% Stream: Decoder - Stream Cancellation (Stream=8) + <<16#48>> = decoder_cancel_stream(8), + {ok, EncData5, 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), + <<2#00:2,1:6>> = EncData5, + #state{ + capacity=220, + size=215, + insert_count=5, + dyn_table=[ + {55, {<<"custom-key">>, <<"custom-value2">>}}, + {57, {<<":authority">>, <<"www.example.com">>}}, + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}} + ] + } = DecState5, + ok. +-endif. + +%% Encoding. + +-spec encode_field_section(cow_http:headers(), cow_http3:stream_id(), State) + -> {ok, iolist(), iolist(), 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) -> + encode_field_section(Headers, StreamID, State0, #{}). + +-spec encode_field_section(cow_http:headers(), cow_http3:stream_id(), State, encoder_opts()) + -> {ok, iolist(), iolist(), State} when State::state(). + +encode_field_section(Headers, StreamID, State0=#state{ + max_table_capacity=MaxTableCapacity, insert_count=InsertCount, + references=Refs0}, Opts) -> + State1 = encode_update_drain_info(State0), + Base = InsertCount + 1, + {ReqInsertCount, EncData, Data, State} = encode( + Headers, StreamID, State1, + 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 + %% We inserted new entries. + ReqInsertCount > Base -> + {2#1, ReqInsertCount - Base}; + %% We only used existing entries. + ReqInsertCount =< Base -> + {2#0, ReqInsertCount - Base} + end, + %% Save the reference to avoid draining entries too quickly. + Refs = case Refs0 of + #{StreamID := ICs} -> + Refs0#{StreamID => [ReqInsertCount|ICs]}; + _ -> + Refs0#{StreamID => [ReqInsertCount]} + end, + {ok, [enc_big_int(EncInsertCount, <<>>), enc_int7(DeltaBase, S)|Data], EncData, + State#state{references=Refs}} + end. + +%% We check how many entries we can evict. The result +%% will take the form of a draining_index (the oldest +%% entry the encoder can reference) as well as a +%% draining_size (how much data can be gained by evicting). +%% +%% We first look at streams that have not been acknowledged +%% and find the smallest insert_count value from them. We +%% cannot evict any value that is newer than or equal to +%% that value. +%% +%% Then we also need to make sure we don't evict too much +%% from the table. +%% +%% Finally we go over the dynamic table to count how much +%% we can actually drain and what the draining index really is. +encode_update_drain_info(State=#state{max_table_capacity=MaxCapacity, + insert_count=InsertCount, dyn_table=DynTable, references=Refs}) -> + PendingInsertCount = if + %% When we don't use the dynamic table, or we didn't insert + %% anything yet, there are no references. We can drain + %% everything but are still constrained by the max draining size. + Refs =:= #{} -> + InsertCount; + true -> + maps:fold(fun(_, ICs, V) -> + IC = hd(lists:reverse(ICs)), + case V of + undefined -> IC; + _ -> min(IC, V) + end + end, undefined, Refs) + end, + %% We use a simple formula for calculating the maximum + %% draining size, found in nginx: we allow evicting + %% between 1/8th of the current table capacity and + %% 512 bytes, whichever is smaller. When the maximum + %% table capacity is small this formula may get us + %% a value that's too small to drain anything, so + %% we use 64 bytes as a minimum. + MaxDrainingSize0 = min(512, MaxCapacity div 8), + MaxDrainingSize = if + MaxDrainingSize0 < 64 -> 64; + true -> MaxDrainingSize0 + end, + {DrainingIndex, DrainingSize} = + encode_update_drain_loop(lists:reverse(DynTable), + InsertCount - length(DynTable), PendingInsertCount, + 0, MaxDrainingSize), + State#state{ + draining_index=DrainingIndex, + draining_size=DrainingSize + }. + +%% We go over the dynamic table in reverse order. We stop +%% when we either reach the PendingInsertCount value or get +%% above MaxDrainingSize. It's not possible to go over the +%% entire dynamic table because we have references. +encode_update_drain_loop(_, Index, PendingIndex, Size, _) + when Index =:= PendingIndex -> + {Index, Size}; +encode_update_drain_loop([{EntrySize, _}|_], Index, _, Size, MaxSize) + when Size + EntrySize > MaxSize -> + {Index, Size}; +encode_update_drain_loop([{EntrySize, _}|Tail], Index, PendingIndex, Size, MaxSize) -> + encode_update_drain_loop(Tail, Index + 1, PendingIndex, Size + EntrySize, MaxSize). + +encode([], _StreamID, State, _HuffmanOpt, + ReqInsertCount, _Base, EncAcc, Acc) -> + {ReqInsertCount, lists:reverse(EncAcc), lists:reverse(Acc), State}; +encode([{Name, Value0}|Tail], StreamID, State, HuffmanOpt, + ReqInsertCount, 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}, + encode_static([Entry|Tail], StreamID, State, HuffmanOpt, + ReqInsertCount, Base, EncAcc, Acc). + +encode_static([Entry|Tail], StreamID, State, HuffmanOpt, + ReqInsertCount, Base, EncAcc, Acc) -> + case table_find_static(Entry) of + not_found -> + encode_dyn([Entry|Tail], StreamID, State, HuffmanOpt, + ReqInsertCount, Base, EncAcc, Acc); + StaticIndex -> + encode(Tail, StreamID, State, HuffmanOpt, + ReqInsertCount, Base, EncAcc, + %% Indexed Field Line. T=1 (static). + [enc_int6(StaticIndex, 2#11)|Acc]) + end. + +encode_dyn([Entry|Tail], StreamID, State0=#state{draining_index=DrainingIndex}, + HuffmanOpt, ReqInsertCount0, Base, EncAcc, Acc) -> + case table_find_dyn(Entry, State0) of + not_found -> + encode_static_name([Entry|Tail], StreamID, State0, HuffmanOpt, + ReqInsertCount0, Base, EncAcc, Acc); + %% 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 < DrainingIndex -> + case encode_can_insert(Entry, State0) of + {true, EncInstr, State1} -> + {ok, State} = table_insert(Entry, State1), + #state{insert_count=ReqInsertCount} = State, + %% We must reference the relative index of the entry we duplicated + %% before we duplicated it. The newest entry starts at 0. If we + %% have 3 entries in the table, the oldest one will have a relative + %% index of 2. Because we already inserted the duplicate, our + %% ReqInsertCount has 1 added, so for our previously 3 entries + %% table, we end up with a ReqInsertCount of 4. This means we + %% have to remove 2 from the difference to find the relative index. + DynIndexRel = ReqInsertCount - DynIndex - 2, + encode(Tail, StreamID, State, HuffmanOpt, ReqInsertCount, Base, + %% Duplicate. + [[EncInstr|enc_int5(DynIndexRel, 2#000)]|EncAcc], + %% Indexed Field Line. T=0 (dynamic). + [enc_int6(Base - ReqInsertCount, 2#10)|Acc]); + false -> + encode_static_name([Entry|Tail], StreamID, State0, HuffmanOpt, + ReqInsertCount0, Base, EncAcc, Acc) + end; + DynIndex -> + ReqInsertCount = max(ReqInsertCount0, DynIndex), + encode(Tail, StreamID, State0, HuffmanOpt, ReqInsertCount, Base, EncAcc, + %% Indexed Field Line. T=0 (dynamic). + [enc_int6(Base - DynIndex - 1, 2#10)|Acc]) + end. + +encode_static_name([Entry = {Name, Value}|Tail], StreamID, State0, HuffmanOpt, + ReqInsertCount0, Base, EncAcc, Acc) -> + case table_find_name_static(Name) of + not_found -> + encode_dyn_name([Entry|Tail], StreamID, State0, HuffmanOpt, + ReqInsertCount0, Base, EncAcc, Acc); + StaticNameIndex -> + case encode_can_insert(Entry, State0) of + {true, EncInstr, State1} -> + {ok, State} = table_insert(Entry, State1), + #state{insert_count=ReqInsertCount} = State, + PostBaseIndex = length(EncAcc), + encode(Tail, StreamID, State, HuffmanOpt, ReqInsertCount, Base, + %% Insert with Name Reference. T=1 (static). + [[EncInstr, enc_int6(StaticNameIndex, 2#11)|enc_str(Value, HuffmanOpt)] + |EncAcc], + %% Indexed Field Line with Post-Base Index. + [enc_int4(PostBaseIndex, 2#0001)|Acc]); + false -> + encode(Tail, StreamID, State0, HuffmanOpt, ReqInsertCount0, Base, EncAcc, + %% Literal Field Line with Name Reference. N=0. T=1 (static). + [[enc_int4(StaticNameIndex, 2#0101)|enc_str(Value, HuffmanOpt)]|Acc]) + end + end. + +encode_dyn_name([Entry = {Name, Value}|Tail], StreamID, + State0=#state{draining_index=DrainingIndex}, + HuffmanOpt, ReqInsertCount0, Base, EncAcc, Acc) -> + case table_find_name_dyn(Name, State0) of + %% We can reference the dynamic name. + DynIndex when is_integer(DynIndex), DynIndex >= DrainingIndex -> + case encode_can_insert(Entry, State0) of + {true, EncInstr, State1} -> + {ok, State} = table_insert(Entry, State1), + #state{insert_count=ReqInsertCount} = State, + %% See comment in encode_dyn for why we remove 2. + DynIndexRel = ReqInsertCount - DynIndex - 2, + PostBaseIndex = length(EncAcc), + encode(Tail, StreamID, State, HuffmanOpt, ReqInsertCount, Base, + %% Insert with Name Reference. T=0 (dynamic). + [[EncInstr, enc_int6(DynIndexRel, 2#10)|enc_str(Value, HuffmanOpt)] + |EncAcc], + %% Indexed Field Line with Post-Base Index. + [enc_int4(PostBaseIndex, 2#0001)|Acc]); + false -> + encode(Tail, StreamID, State0, HuffmanOpt, ReqInsertCount0, Base, EncAcc, + %% Literal Field Line with Name Reference. N=0. T=0 (dynamic). + [[enc_int4(DynIndex, 2#0100)|enc_str(Value, HuffmanOpt)]|Acc]) + end; + %% When there are no name to reference, or the name + %% is found below the drain index, we do not attempt + %% to refer to it. + _ -> + case encode_can_insert(Entry, State0) of + {true, EncInstr, State1} -> + {ok, State} = table_insert(Entry, State1), + #state{insert_count=ReqInsertCount} = State, + PostBaseIndex = length(EncAcc), + encode(Tail, StreamID, State, HuffmanOpt, ReqInsertCount, Base, + %% Insert with Literal Name. + [[EncInstr, enc_str6(Name, HuffmanOpt, 2#01)|enc_str(Value, HuffmanOpt)] + |EncAcc], + %% Indexed Field Line with Post-Base Index. + [enc_int4(PostBaseIndex, 2#0001)|Acc]); + false -> + encode(Tail, StreamID, State0, HuffmanOpt, ReqInsertCount0, Base, EncAcc, + %% Literal Field Line with Literal Name. N=0. + [[enc_str4(Name, HuffmanOpt, 2#0010)|enc_str(Value, HuffmanOpt)]|Acc]) + end + end. + +%% @todo We should make sure we have a large enough flow control window. +%% +%% We can never insert before receiving the SETTINGS frame. +encode_can_insert(_, #state{settings_received=false}) -> + false; +encode_can_insert({Name, Value}, State=#state{ + max_table_capacity=MaxCapacity, capacity=Capacity, + size=Size, draining_size=DrainingSize}) -> + EntrySize = byte_size(Name) + byte_size(Value) + 32, + if + %% We have enough space in the current capacity, + %% without having to drain entries. + EntrySize + Size =< Capacity -> + {true, <<>>, State}; + %% We have enough space if we increase the capacity. + %% We prefer to first increase the capacity to the + %% maximum before we start draining entries. + EntrySize + Size =< MaxCapacity -> + {true, enc_int5(MaxCapacity, 2#001), + State#state{capacity=MaxCapacity}}; + %% We are already at max capacity and have enough + %% space if we drain entries. + EntrySize + Size =< Capacity + DrainingSize, Capacity =:= MaxCapacity -> + {true, <<>>, State}; + %% We are not at max capacity. We have enough space + %% if we both increase the capacity and drain entries. + EntrySize + Size =< MaxCapacity + DrainingSize -> + {true, enc_int5(MaxCapacity, 2#001), + State#state{capacity=MaxCapacity}}; + true -> + false + end. + +-spec execute_decoder_instructions(binary(), State) + -> {ok, State} | {connection_error, qpack_decoder_stream_error, atom()} + when State::state(). +execute_decoder_instructions(<<>>, State) -> + {ok, State}; +%% Section acknowledgement. +%% We remove one reference and if needed increase the known received count. +execute_decoder_instructions(<<2#1:1,Rest0/bits>>, State=#state{ + known_received_count=KnownReceivedCount0, references=Refs}) -> + {StreamID, Rest} = dec_int7(Rest0), + case Refs of + #{StreamID := [InsertCount]} -> + KnownReceivedCount = max(KnownReceivedCount0, InsertCount), + execute_decoder_instructions(Rest, State#state{ + known_received_count=KnownReceivedCount, + references=maps:remove(StreamID, Refs)}); + #{StreamID := InsertCounts} -> + [InsertCount|InsertCountsTail] = lists:reverse(InsertCounts), + KnownReceivedCount = max(KnownReceivedCount0, InsertCount), + execute_decoder_instructions(Rest, State#state{ + known_received_count=KnownReceivedCount, + references=Refs#{StreamID => lists:reverse(InsertCountsTail)}}); + _ -> + {connection_error, qpack_decoder_stream_error, + 'Acknowledgement received for stream with no pending sections. (RFC9204 4.4.1)'} + end; +%% Stream cancellation. +%% We drop all references for the given stream. +execute_decoder_instructions(<<2#01:2,Rest0/bits>>, State=#state{references=Refs}) -> + {StreamID, Rest} = dec_int6(Rest0), + case Refs of + #{StreamID := _} -> + execute_decoder_instructions(Rest, State#state{ + references=maps:remove(StreamID, Refs)}); + %% It is not an error for the reference to not exist. + %% The dynamic table may not have been used for this + %% stream. + _ -> + execute_decoder_instructions(Rest, State) + end; +%% Insert count increment. +%% We increase the known received count. +execute_decoder_instructions(<<2#00:2,Rest0/bits>>, State=#state{ + known_received_count=KnownReceivedCount}) -> + {Increment, Rest} = dec_int6(Rest0), + execute_decoder_instructions(Rest, State#state{ + known_received_count=KnownReceivedCount + Increment}). + +%% Inform the encoder of the relevant SETTINGS from the decoder. +%% The encoder will choose the smallest value between what it +%% has configured and what it received through SETTINGS. Should +%% there be no value in the SETTINGS then 0 must be given. + +-spec encoder_set_settings(non_neg_integer(), non_neg_integer(), state()) -> state(). + +encoder_set_settings(MaxTableCapacity, MaxBlockedStreams, State=#state{ + max_table_capacity=MaxTableCapacityConfigured, + max_blocked_streams=MaxBlockedStreamsConfigured}) -> + State#state{ + settings_received=true, + max_table_capacity=min(MaxTableCapacity, MaxTableCapacityConfigured), + max_blocked_streams=min(MaxBlockedStreams, MaxBlockedStreamsConfigured) + }. + +huffman_opt(#{huffman := false}) -> no_huffman; +huffman_opt(_) -> huffman. + +enc_int3(Int, Prefix) when Int < 7 -> + <<Prefix:5, Int:3>>; +enc_int3(Int, Prefix) -> + enc_big_int(Int - 7, <<Prefix:5, 2#111:3>>). + +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_str4(Str, huffman, Prefix) -> + Str2 = enc_huffman(Str, <<>>), + [enc_int3(byte_size(Str2), Prefix * 2 + 2#1)|Str2]; +enc_str4(Str, no_huffman, Prefix) -> + [enc_int3(byte_size(Str), Prefix * 2 + 2#0)|Str]. + +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]. + +-ifdef(TEST). +%% This function is a good starting point to let the calling +%% process insert entries in the dynamic table outside of +%% encoding a field section. To be usable more broadly +%% it would need to handle the case where a static name +%% is found, but also consider how it should be used: +%% do we have capacity in the table? We don't have +%% capacity before receiving the SETTINGS frame. Until +%% then it will be restricted to testing. +encoder_insert_entry(Entry={Name, Value}, State0, Opts) -> + {ok, 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 -> + %% Insert with Literal Name. + {ok, [enc_str6(Name, HuffmanOpt, 2#01)|enc_str(Value, HuffmanOpt)], State}; + DynNameIndex -> + #state{insert_count=ReqInsertCount} = State, + %% See comment in encode_dyn for why we remove 2. + DynNameIndexRel = ReqInsertCount - DynNameIndex - 2, + %% Insert with Name Reference. T=0 (dynamic). + {ok, [enc_int6(DynNameIndexRel, 2#10)|enc_str(Value, HuffmanOpt)], State} + end + end. + +appendix_b_encoder_test() -> + %% We limit the encoder to 220 bytes for table capacity. + EncState0 = init(encoder, 220, 0), + %% Stream: 0 + {ok, Data1, EncData1, EncState1} = encode_field_section([ + {<<":path">>, <<"/index.html">>} + ], 0, EncState0, #{huffman => false}), + <<>> = iolist_to_binary(EncData1), + << + 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(Data1), + #state{ + capacity=0, + size=0, + insert_count=0, + dyn_table=[] + } = EncState1, + %% Simulate receiving of the SETTINGS frame enabling the dynamic table. + EncState2 = encoder_set_settings(4096, 0, EncState1), + #state{ + settings_received=true, + max_table_capacity=220, + capacity=0 + } = EncState2, + %% Stream: 4 (and Encoder) + {ok, Data3, EncData3, EncState3} = encode_field_section([ + {<<":authority">>, <<"www.example.com">>}, + {<<":path">>, <<"/sample/path">>} + ], 4, EncState2, #{huffman => false}), + << + 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 + >> = iolist_to_binary(EncData3), + << + 16#0381:16, + 16#10, + 16#11 + >> = iolist_to_binary(Data3), + #state{ + capacity=220, + size=106, + insert_count=2, + %% The dynamic table is in reverse order. + dyn_table=[ + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ] + } = EncState3, + %% Stream: Decoder + {ok, EncState4} = execute_decoder_instructions(<<16#84>>, EncState3), + #state{ + capacity=220, + size=106, + insert_count=2, + %% The dynamic table is in reverse order. + dyn_table=[ + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ] + } = EncState4, + %% Stream: Encoder + {ok, EncData5, EncState5} = encoder_insert_entry( + {<<"custom-key">>, <<"custom-value">>}, + EncState4, #{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(EncData5), + #state{ + capacity=220, + size=160, + insert_count=3, + %% The dynamic table is in reverse order. + dyn_table=[ + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ] + } = EncState5, + %% Stream: Decoder + {ok, EncState6} = execute_decoder_instructions(<<16#01>>, EncState5), + #state{ + capacity=220, + size=160, + insert_count=3, + %% The dynamic table is in reverse order. + dyn_table=[ + {54, {<<"custom-key">>, <<"custom-value">>}}, + {49, {<<":path">>, <<"/sample/path">>}}, + {57, {<<":authority">>, <<"www.example.com">>}} + ] + } = EncState6, + %% Stream: 8 (and Encoder) + {ok, Data7, EncData7, EncState7} = encode_field_section([ + {<<":authority">>, <<"www.example.com">>}, + {<<":path">>, <<"/">>}, + {<<"custom-key">>, <<"custom-value">>} + ], 8, EncState6), + <<16#02>> = iolist_to_binary(EncData7), + << + 16#0500:16, + 16#80, + 16#c1, + 16#81 + >> = iolist_to_binary(Data7), + #state{ + capacity=220, + size=217, + insert_count=4, + %% 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">>}} + ] + } = EncState7, + %% Stream: Decoder + {ok, EncState8} = execute_decoder_instructions(<<16#48>>, EncState7), + #state{ + capacity=220, + size=217, + insert_count=4, + %% 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">>}} + ] + } = EncState8, + %% Stream: Encoder + {ok, EncData9, EncState9} = encoder_insert_entry( + {<<"custom-key">>, <<"custom-value2">>}, + EncState8, #{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(EncData9), + #state{ + capacity=220, + size=215, + insert_count=5, + %% 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">>}} + ] + } = EncState9, + ok. +-endif. + +%% 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; +%% These two values are technically invalid. An errata has already +%% been submitted to the RFC. We must however continue to include +%% them in the table for compatibility. +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">>, <<>>}; +%% These two values are technically invalid. An errata has already +%% been submitted to the RFC. We must however continue to include +%% them in the table for compatibility. +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">>. + +table_insert(Entry={Name, Value}, State=#state{capacity=Capacity, + size=Size0, insert_count=InsertCount, dyn_table=DynamicTable0, + draining_size=DrainingSize}) -> + EntrySize = byte_size(Name) + byte_size(Value) + 32, + if + EntrySize + Size0 =< Capacity -> + {ok, State#state{size=Size0 + EntrySize, insert_count=InsertCount + 1, + dyn_table=[{EntrySize, Entry}|DynamicTable0]}}; + EntrySize =< Capacity -> + {DynamicTable, Size} = table_evict(DynamicTable0, + Capacity - EntrySize, 0, []), + {ok, State#state{size=Size + EntrySize, insert_count=InsertCount + 1, + dyn_table=[{EntrySize, Entry}|DynamicTable], + %% We reduce the draining size by how much was gained from evicting. + draining_size=DrainingSize - (Size0 - Size)}}; + true -> % EntrySize > Capacity -> + {connection_error, qpack_encoder_stream_error, + 'Entry size larger than table capacity. (RFC9204 3.2.2)'} + end. + +table_evict([], _, Size, Acc) -> + {lists:reverse(Acc), Size}; +table_evict([{EntrySize, _}|_], MaxSize, Size, Acc) + when Size + EntrySize > MaxSize -> + {lists:reverse(Acc), Size}; +table_evict([Entry = {EntrySize, _}|Tail], MaxSize, Size, Acc) -> + table_evict(Tail, MaxSize, Size + EntrySize, [Entry|Acc]). + +table_find_dyn(Entry, #state{insert_count=InsertCount, dyn_table=DynamicTable}) -> + table_find_dyn(Entry, DynamicTable, InsertCount - 1). + +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{insert_count=InsertCount, dyn_table=DynamicTable}) -> + table_find_name_dyn(Name, DynamicTable, InsertCount - 1). + +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{insert_count=InsertCount, dyn_table=DynamicTable}) -> + {_, Header} = lists:nth(InsertCount - 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{insert_count=InsertCount, dyn_table=DynamicTable}) -> + BaseOffset = InsertCount - Base, + {_, Header} = lists:nth(1 + Index + BaseOffset, DynamicTable), + Header. + +table_get_dyn_post_base(Index, Base, State) -> + table_get_dyn_abs(Base + Index, State). + +table_get_name_dyn_post_base(Index, Base, State) -> + {Name, _} = table_get_dyn_abs(Base + Index, State), + Name. + +-ifdef(TEST). +do_init() -> + #state{ + settings_received=false, + max_table_capacity=1000, + capacity=1000 + }. + +do_table_insert(Entry, State0) -> + {ok, State} = table_insert(Entry, State0), + State. + +table_get_dyn_abs_test() -> + State0 = do_init(), + State1 = do_table_insert({<<"g">>, <<"h">>}, + do_table_insert({<<"e">>, <<"f">>}, + do_table_insert({<<"c">>, <<"d">>}, + do_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{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 = do_init(), + State1 = do_table_insert({<<"g">>, <<"h">>}, + do_table_insert({<<"e">>, <<"f">>}, + do_table_insert({<<"c">>, <<"d">>}, + do_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{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 = do_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 = do_init(), + State1 = do_table_insert({<<"g">>, <<"h">>}, + do_table_insert({<<"e">>, <<"f">>}, + do_table_insert({<<"c">>, <<"d">>}, + do_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{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 = do_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 = do_init(), + State1 = do_table_insert({<<"g">>, <<"h">>}, + do_table_insert({<<"e">>, <<"f">>}, + do_table_insert({<<"c">>, <<"d">>}, + do_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{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 = do_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. |