huffman.ex (2522B)
1 defmodule HPAX.Huffman do 2 @moduledoc false 3 4 import Bitwise, only: [>>>: 2] 5 6 # This file is downloaded from the spec directly. 7 # http://httpwg.org/specs/rfc7541.html#huffman.code 8 table_file = Path.absname("huffman_table", __DIR__) 9 @external_resource table_file 10 11 entries = 12 Enum.map(File.stream!(table_file), fn line -> 13 [byte_value, bits, _hex, bit_count] = 14 line 15 |> case do 16 <<?', _, ?', ?\s, rest::binary>> -> rest 17 "EOS " <> rest -> rest 18 _other -> line 19 end 20 |> String.replace(["|", "(", ")", "[", "]"], "") 21 |> String.split() 22 23 byte_value = String.to_integer(byte_value) 24 bits = String.to_integer(bits, 2) 25 bit_count = String.to_integer(bit_count) 26 27 {byte_value, bits, bit_count} 28 end) 29 30 {regular_entries, [eos_entry]} = Enum.split(entries, -1) 31 {_eos_byte_value, eos_bits, eos_bit_count} = eos_entry 32 33 ## Encoding 34 35 @spec encode(binary()) :: binary() 36 def encode(binary) do 37 encode(binary, _acc = <<>>) 38 end 39 40 for {byte_value, bits, bit_count} <- regular_entries do 41 defp encode(<<unquote(byte_value), rest::binary>>, acc) do 42 encode(rest, <<acc::bitstring, unquote(bits)::size(unquote(bit_count))>>) 43 end 44 end 45 46 defp encode(<<>>, acc) do 47 overflowing_bits = rem(bit_size(acc), 8) 48 49 if overflowing_bits == 0 do 50 acc 51 else 52 bits_to_add = 8 - overflowing_bits 53 54 value_of_bits_to_add = 55 take_significant_bits(unquote(eos_bits), unquote(eos_bit_count), bits_to_add) 56 57 <<acc::bitstring, value_of_bits_to_add::size(bits_to_add)>> 58 end 59 end 60 61 ## Decoding 62 63 @spec decode(binary()) :: binary() 64 def decode(binary) 65 66 for {byte_value, bits, bit_count} <- regular_entries do 67 def decode(<<unquote(bits)::size(unquote(bit_count)), rest::bitstring>>) do 68 <<unquote(byte_value), decode(rest)::binary>> 69 end 70 end 71 72 def decode(<<>>) do 73 <<>> 74 end 75 76 # Use binary syntax for single match context optimization. 77 def decode(<<padding::bitstring>>) when bit_size(padding) in 1..7 do 78 padding_size = bit_size(padding) 79 <<padding::size(padding_size)>> = padding 80 81 if take_significant_bits(unquote(eos_bits), unquote(eos_bit_count), padding_size) == padding do 82 <<>> 83 else 84 throw({:hpax, {:protocol_error, :invalid_huffman_encoding}}) 85 end 86 end 87 88 ## Helpers 89 90 @compile {:inline, take_significant_bits: 3} 91 defp take_significant_bits(value, bit_count, bits_to_take) do 92 value >>> (bit_count - bits_to_take) 93 end 94 end