hpax.ex (9271B)
1 defmodule HPAX do 2 @moduledoc """ 3 Support for the HPACK header compression algorithm. 4 5 This module provides support for the HPACK header compression algorithm used mainly in HTTP/2. 6 7 ## Encoding and decoding contexts 8 9 The HPACK algorithm requires both 10 11 * an encoding context on the encoder side 12 * a decoding context on the decoder side 13 14 These contexts are semantically different but structurally the same. In HPACK they are 15 implemented as **HPACK tables**. This library uses the name "tables" everywhere internally 16 17 HPACK tables can be created through the `new/1` function. 18 """ 19 20 alias HPAX.{Table, Types} 21 22 @typedoc """ 23 An HPACK header name. 24 """ 25 @type header_name() :: binary() 26 27 @typedoc """ 28 An HPACK header value. 29 """ 30 @type header_value() :: binary() 31 32 @valid_header_actions [:store, :store_name, :no_store, :never_store] 33 34 @doc """ 35 Create a new HPACK table that can be used as encoding or decoding context. 36 37 See the "Encoding and decoding contexts" section in the module documentation. 38 39 `max_table_size` is the maximum table size (in bytes) for the newly created table. 40 41 ## Examples 42 43 encoding_context = HPAX.new(4096) 44 45 """ 46 @spec new(non_neg_integer()) :: Table.t() 47 def new(max_table_size) when is_integer(max_table_size) and max_table_size >= 0 do 48 Table.new(max_table_size) 49 end 50 51 @doc """ 52 Resizes the given table to the given size. 53 54 ## Examples 55 56 decoding_context = HPAX.new(4096) 57 HPAX.resize(decoding_context, 8192) 58 59 """ 60 @spec resize(Table.t(), non_neg_integer()) :: Table.t() 61 defdelegate resize(table, new_size), to: Table 62 63 @doc """ 64 Decodes a header block fragment (HBF) through a given table. 65 66 If decoding is successful, this function returns a `{:ok, headers, updated_table}` tuple where 67 `headers` is a list of decoded headers, and `updated_table` is the updated table. If there's 68 an error in decoding, this function returns `{:error, reason}`. 69 70 ## Examples 71 72 decoding_context = HPAX.new(1000) 73 hbf = get_hbf_from_somewhere() 74 HPAX.decode(hbf, decoding_context) 75 #=> {:ok, [{":method", "GET"}], decoding_context} 76 77 """ 78 @spec decode(binary(), Table.t()) :: 79 {:ok, [{header_name(), header_value()}], Table.t()} | {:error, term()} 80 81 # Dynamic resizes must occur only at the start of a block 82 # https://datatracker.ietf.org/doc/html/rfc7541#section-4.2 83 def decode(<<0b001::3, rest::bitstring>>, %Table{} = table) do 84 {new_size, rest} = decode_integer(rest, 5) 85 86 # Dynamic resizes must be less than max table size 87 # https://datatracker.ietf.org/doc/html/rfc7541#section-6.3 88 if new_size <= table.max_table_size do 89 decode(rest, Table.resize(table, new_size)) 90 else 91 {:error, :protocol_error} 92 end 93 end 94 95 def decode(block, %Table{} = table) when is_binary(block) do 96 decode_headers(block, table, _acc = []) 97 catch 98 :throw, {:hpax, error} -> {:error, error} 99 end 100 101 @doc """ 102 Encodes a list of headers through the given table. 103 104 Returns a two-element tuple where the first element is a binary representing the encoded headers 105 and the second element is an updated table. 106 107 ## Examples 108 109 headers = [{:store, ":authority", "https://example.com"}] 110 encoding_context = HPAX.new(1000) 111 HPAX.encode(headers, encoding_context) 112 #=> {iodata, updated_encoding_context} 113 114 """ 115 @spec encode([header], Table.t()) :: {iodata(), Table.t()} 116 when header: {action, header_name(), header_value()}, 117 action: :store | :store_name | :no_store | :never_store 118 def encode(headers, %Table{} = table) when is_list(headers) do 119 encode_headers(headers, table, _acc = []) 120 end 121 122 ## Helpers 123 124 defp decode_headers(<<>>, table, acc) do 125 {:ok, Enum.reverse(acc), table} 126 end 127 128 # Indexed header field 129 # http://httpwg.org/specs/rfc7541.html#rfc.section.6.1 130 defp decode_headers(<<0b1::1, rest::bitstring>>, table, acc) do 131 {index, rest} = decode_integer(rest, 7) 132 decode_headers(rest, table, [lookup_by_index!(table, index) | acc]) 133 end 134 135 # Literal header field with incremental indexing 136 # http://httpwg.org/specs/rfc7541.html#rfc.section.6.2.1 137 defp decode_headers(<<0b01::2, rest::bitstring>>, table, acc) do 138 {name, value, rest} = 139 case rest do 140 # The header name is a string. 141 <<0::6, rest::binary>> -> 142 {name, rest} = decode_binary(rest) 143 {value, rest} = decode_binary(rest) 144 {name, value, rest} 145 146 # The header name is an index to be looked up in the table. 147 _other -> 148 {index, rest} = decode_integer(rest, 6) 149 {value, rest} = decode_binary(rest) 150 {name, _value} = lookup_by_index!(table, index) 151 {name, value, rest} 152 end 153 154 decode_headers(rest, Table.add(table, name, value), [{name, value} | acc]) 155 end 156 157 # Literal header field without indexing 158 # http://httpwg.org/specs/rfc7541.html#rfc.section.6.2.2 159 defp decode_headers(<<0b0000::4, rest::bitstring>>, table, acc) do 160 {name, value, rest} = 161 case rest do 162 <<0::4, rest::binary>> -> 163 {name, rest} = decode_binary(rest) 164 {value, rest} = decode_binary(rest) 165 {name, value, rest} 166 167 _other -> 168 {index, rest} = decode_integer(rest, 4) 169 {value, rest} = decode_binary(rest) 170 {name, _value} = lookup_by_index!(table, index) 171 {name, value, rest} 172 end 173 174 decode_headers(rest, table, [{name, value} | acc]) 175 end 176 177 # Literal header field never indexed 178 # http://httpwg.org/specs/rfc7541.html#rfc.section.6.2.3 179 defp decode_headers(<<0b0001::4, rest::bitstring>>, table, acc) do 180 {name, value, rest} = 181 case rest do 182 <<0::4, rest::binary>> -> 183 {name, rest} = decode_binary(rest) 184 {value, rest} = decode_binary(rest) 185 {name, value, rest} 186 187 _other -> 188 {index, rest} = decode_integer(rest, 4) 189 {value, rest} = decode_binary(rest) 190 {name, _value} = lookup_by_index!(table, index) 191 {name, value, rest} 192 end 193 194 # TODO: enforce the "never indexed" part somehow. 195 decode_headers(rest, table, [{name, value} | acc]) 196 end 197 198 defp decode_headers(_other, _table, _acc) do 199 throw({:hpax, :protocol_error}) 200 end 201 202 defp lookup_by_index!(table, index) do 203 case Table.lookup_by_index(table, index) do 204 {:ok, header} -> header 205 :error -> throw({:hpax, {:index_not_found, index}}) 206 end 207 end 208 209 defp decode_integer(bitstring, prefix) do 210 case Types.decode_integer(bitstring, prefix) do 211 {:ok, int, rest} -> {int, rest} 212 :error -> throw({:hpax, :bad_integer_encoding}) 213 end 214 end 215 216 defp decode_binary(binary) do 217 case Types.decode_binary(binary) do 218 {:ok, binary, rest} -> {binary, rest} 219 :error -> throw({:hpax, :bad_binary_encoding}) 220 end 221 end 222 223 defp encode_headers([], table, acc) do 224 {acc, table} 225 end 226 227 defp encode_headers([{action, name, value} | rest], table, acc) 228 when action in @valid_header_actions and is_binary(name) and is_binary(value) do 229 {encoded, table} = 230 case Table.lookup_by_header(table, name, value) do 231 {:full, index} -> 232 {encode_indexed_header(index), table} 233 234 {:name, index} when action == :store -> 235 {encode_literal_header_with_indexing(index, value), Table.add(table, name, value)} 236 237 {:name, index} when action in [:store_name, :no_store] -> 238 {encode_literal_header_without_indexing(index, value), table} 239 240 {:name, index} when action == :never_store -> 241 {encode_literal_header_never_indexed(index, value), table} 242 243 :not_found when action in [:store, :store_name] -> 244 {encode_literal_header_with_indexing(name, value), Table.add(table, name, value)} 245 246 :not_found when action == :no_store -> 247 {encode_literal_header_without_indexing(name, value), table} 248 249 :not_found when action == :never_store -> 250 {encode_literal_header_never_indexed(name, value), table} 251 end 252 253 encode_headers(rest, table, [acc, encoded]) 254 end 255 256 defp encode_indexed_header(index) do 257 <<1::1, Types.encode_integer(index, 7)::bitstring>> 258 end 259 260 defp encode_literal_header_with_indexing(index, value) when is_integer(index) do 261 [<<1::2, Types.encode_integer(index, 6)::bitstring>>, Types.encode_binary(value, false)] 262 end 263 264 defp encode_literal_header_with_indexing(name, value) when is_binary(name) do 265 [<<1::2, 0::6>>, Types.encode_binary(name, false), Types.encode_binary(value, false)] 266 end 267 268 defp encode_literal_header_without_indexing(index, value) when is_integer(index) do 269 [<<0::4, Types.encode_integer(index, 4)::bitstring>>, Types.encode_binary(value, false)] 270 end 271 272 defp encode_literal_header_without_indexing(name, value) when is_binary(name) do 273 [<<0::4, 0::4>>, Types.encode_binary(name, false), Types.encode_binary(value, false)] 274 end 275 276 defp encode_literal_header_never_indexed(index, value) when is_integer(index) do 277 [<<1::4, Types.encode_integer(index, 4)::bitstring>>, Types.encode_binary(value, false)] 278 end 279 280 defp encode_literal_header_never_indexed(name, value) when is_binary(name) do 281 [<<1::4, 0::4>>, Types.encode_binary(name, false), Types.encode_binary(value, false)] 282 end 283 end