path: root/src/cow_qpack.erl

%% 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.