hpack

defmodule HPack do
  @moduledoc """
    Implementation of the [HPack](https://http2.github.io/http2-spec/compression.html) protocol, a compression format for efficiently representing HTTP header fields, to be used in HTTP/2.
  """

  use Bitwise
  alias HPack.Huffman
  alias HPack.Table

  @type header :: {String.t(), String.t()}
  @type header_block_fragment :: binary

  @doc """
  Encodes a list of headers into a `header block fragment` as specified in RFC 7541.

  Returns the `header block fragment`.

  ### Examples

      iex> {:ok, ctx} = HPack.Table.start_link(1000)
      iex> HPack.encode([{":method", "GET"}], ctx)
      << 0b10000010 >>

  """
  @spec encode([header], Table.t()) :: header_block_fragment
  def encode(headers, table) when is_list(headers), do: encode(headers, <<>>, table)

  defp encode([], hbf, _), do: hbf

  defp encode([{key, value} | headers], hbf, table) do
    partial =
      case Table.find(key, value, table) do
        {:fullindex, index} -> encode_indexed(index)
        {:keyindex, index} -> encode_literal_indexed(index, value, table)
        {:none} -> encode_literal_not_indexed(key, value, table)
      end

    encode(headers, hbf <> partial, table)
  end

  defp encode_indexed(index), do: <<1::1, encode_int7(index)::bitstring>>

  defp encode_literal_indexed(index, value, table) do
    {name, _} = Table.lookup(index, table)
    Table.add({name, value}, table)
    <<0::1, 1::1, encode_int6(index)::bitstring, encode_string(value)::binary>>
  end

  defp encode_literal_not_indexed(name, value, table) do
    Table.add({name, value}, table)
    <<0::1, 1::1, 0::6, encode_string(name)::binary, encode_string(value)::binary>>
  end

  # defp encode_literal_never_indexed(key, value)

  defp encode_string(string) do
    huffman = Huffman.encode(string)
    length = byte_size(huffman)
    <<1::1, encode_int7(length)::bitstring, huffman::binary>>
  end

  defp encode_int6(i) when i < 0b111111, do: <<i::6>>
  defp encode_int6(i), do: <<0b111111::6, encode_big_int(i - 0b111111)::bitstring>>

  defp encode_int7(i) when i < 0b1111111, do: <<i::7>>
  defp encode_int7(i), do: <<0b1111111::7, encode_big_int(i - 0b1111111)::bitstring>>

  defp encode_big_int(i) when i < 0b10000000, do: <<0::1, i::7>>
  defp encode_big_int(i), do: <<1::1, i::7, encode_big_int(i >>> 7)::binary>>

  @doc """
  Decodes a `header block fragment` as specified in RFC 7541.

  Returns the decoded headers as a List.

  ### Examples

      iex> {:ok, ctx} = HPack.Table.start_link(1000)
      iex> HPack.decode(<< 0x82 >>, ctx)
      [{":method", "GET"}]

  """
  @spec decode(header_block_fragment, Table.t()) :: [header]
  def decode(hbf, table) do
    parse(hbf, [], table)
  end

  defp parse(<<>>, headers, _), do: Enum.reverse(headers)

  #   0   1   2   3   4   5   6   7
  # +---+---+---+---+---+---+---+---+
  # | 1 |        Index (7+)         |
  # +---+---------------------------+
  #  Figure 5: Indexed Header Field
  defp parse(<<1::1, rest::bitstring>>, headers, table) do
    {index, rest} = parse_int7(rest)
    parse(rest, [Table.lookup(index, table) | headers], table)
  end

  #   0   1   2   3   4   5   6   7
  # +---+---+---+---+---+---+---+---+
  # | 0 | 1 |           0           |
  # +---+---+-----------------------+
  # | H |     Name Length (7+)      |
  # +---+---------------------------+
  # |  Name String (Length octets)  |
  # +---+---------------------------+
  # | H |     Value Length (7+)     |
  # +---+---------------------------+
  # | Value String (Length octets)  |
  # +-------------------------------+
  # Figure 7: Literal Header Field with Incremental Indexing — New Name
  defp parse(<<0::1, 1::1, 0::6, rest::binary>>, headers, table) do
    {name, rest} = parse_string(rest)
    {value, more_headers} = parse_string(rest)
    Table.add({name, value}, table)
    parse(more_headers, [{name, value} | headers], table)
  end

  #  0   1   2   3   4   5   6   7
  # +---+---+---+---+---+---+---+---+
  # | 0 | 1 |      Index (6+)       |
  # +---+---+-----------------------+
  # | H |     Value Length (7+)     |
  # +---+---------------------------+
  # | Value String (Length octets)  |
  # +-------------------------------+
  # Figure 6: Literal Header Field with Incremental Indexing — Indexed Name
  defp parse(<<0::1, 1::1, rest::bitstring>>, headers, table) do
    {index, rest} = parse_int6(rest)
    {value, more_headers} = parse_string(rest)
    {header, _} = Table.lookup(index, table)
    Table.add({header, value}, table)
    parse(more_headers, [{header, value} | headers], table)
  end

  #   0   1   2   3   4   5   6   7
  # +---+---+---+---+---+---+---+---+
  # | 0 | 0 | 0 | 0 |       0       |
  # +---+---+-----------------------+
  # | H |     Name Length (7+)      |
  # +---+---------------------------+
  # |  Name String (Length octets)  |
  # +---+---------------------------+
  # | H |     Value Length (7+)     |
  # +---+---------------------------+
  # | Value String (Length octets)  |
  # +-------------------------------+
  # Figure 9: Literal Header Field without Indexing — New Name
  defp parse(<<0::4, 0::4, rest::binary>>, headers, table) do
    {name, rest} = parse_string(rest)
    {value, more_headers} = parse_string(rest)
    parse(more_headers, [{name, value} | headers], table)
  end

  #   0   1   2   3   4   5   6   7
  # +---+---+---+---+---+---+---+---+
  # | 0 | 0 | 0 | 0 |  Index (4+)   |
  # +---+---+-----------------------+
  # | H |     Value Length (7+)     |
  # +---+---------------------------+
  # | Value String (Length octets)  |
  # +-------------------------------+
  # Figure 8: Literal Header Field without Indexing — Indexed Name
  defp parse(<<0::4, rest::bitstring>>, headers, table) do
    {index, rest} = parse_int4(rest)
    {value, more_headers} = parse_string(rest)
    {header, _} = Table.lookup(index, table)
    parse(more_headers, [{header, value} | headers], table)
  end

  #   0   1   2   3   4   5   6   7
  # +---+---+---+---+---+---+---+---+
  # | 0 | 0 | 0 | 1 |       0       |
  # +---+---+-----------------------+
  # | H |     Name Length (7+)      |
  # +---+---------------------------+
  # |  Name String (Length octets)  |
  # +---+---------------------------+
  # | H |     Value Length (7+)     |
  # +---+---------------------------+
  # | Value String (Length octets)  |
  # +-------------------------------+
  # Figure 11: Literal Header Field Never Indexed — New Name
  defp parse(<<0::3, 1::1, 0::4, rest::binary>>, headers, table) do
    {name, rest} = parse_string(rest)
    {value, more_headers} = parse_string(rest)
    parse(more_headers, [{name, value} | headers], table)
  end

  #   0   1   2   3   4   5   6   7
  # +---+---+---+---+---+---+---+---+
  # | 0 | 0 | 0 | 1 |  Index (4+)   |
  # +---+---+-----------------------+
  # | H |     Value Length (7+)     |
  # +---+---------------------------+
  # | Value String (Length octets)  |
  # +-------------------------------+
  # Figure 10: Literal Header Field Never Indexed — Indexed Name
  defp parse(<<0::3, 1::1, rest::bitstring>>, headers, table) do
    {index, rest} = parse_int4(rest)
    {value, more_headers} = parse_string(rest)
    {header, _} = Table.lookup(index, table)
    parse(more_headers, [{header, value} | headers], table)
  end

  #   0   1   2   3   4   5   6   7
  # +---+---+---+---+---+---+---+---+
  # | 0 | 0 | 1 |   Max size (5+)   |
  # +---+---------------------------+
  # Figure 12: Maximum Dynamic Table Size Change
  defp parse(<<0::2, 1::1, rest::bitstring>>, headers, table) do
    {size, rest} = parse_int5(rest)
    Table.resize(size, table)
    parse(rest, headers, table)
  end

  defp parse_string(<<0::1, rest::bitstring>>) do
    {length, rest} = parse_int7(rest)
    <<value::binary-size(length), rest::binary>> = rest
    {value, rest}
  end

  defp parse_string(<<1::1, rest::bitstring>>) do
    {length, rest} = parse_int7(rest)
    <<value::binary-size(length), rest::binary>> = rest
    {Huffman.decode(value), rest}
  end

  defp parse_int4(<<0b1111::4, rest::binary>>), do: parse_big_int(rest, 15, 0)
  defp parse_int4(<<int::4, rest::binary>>), do: {int, rest}

  defp parse_int5(<<0b11111::5, rest::binary>>), do: parse_big_int(rest, 31, 0)
  defp parse_int5(<<int::5, rest::binary>>), do: {int, rest}

  defp parse_int6(<<0b111111::6, rest::binary>>), do: parse_big_int(rest, 63, 0)
  defp parse_int6(<<int::6, rest::binary>>), do: {int, rest}

  defp parse_int7(<<0b1111111::7, rest::binary>>), do: parse_big_int(rest, 127, 0)
  defp parse_int7(<<int::7, rest::binary>>), do: {int, rest}

  defp parse_big_int(<<0::1, value::7, rest::binary>>, int, m), do: {int + (value <<< m), rest}

  defp parse_big_int(<<1::1, value::7, rest::binary>>, int, m),
    do: parse_big_int(rest, int + (value <<< m), m + 7)
end