hpack: implement HPACK decoding

3 files changed, 207 insertions, 0 deletions

diff --git a/lib/plum/hpack/context.rb b/lib/plum/hpack/context.rb
new file mode 100644
index 0000000..4bc492b
--- /dev/null
+++ b/lib/plum/hpack/context.rb
@@ -0,0 +1,35 @@
+module Plum
+  module HPACK
+    class Context
+      attr_reader :dynamic_table
+
+      def initialize(limit = nil)
+        @dynamic_table = []
+        @size = 0
+        @limit = limit # TODO SETTINGS_HEADER_TABLE_SIZE
+      end
+
+      def evict
+        while @limit && @size > @limit
+          name, value = @dynamic_table.pop
+          @size -= name.bytesize + value.to_s.bytesize + 32
+        end
+      end
+
+      def add(name, value)
+        @dynamic_table.unshift([name, value])
+        @size += name.bytesize + value.to_s.bytesize + 32
+        evict
+      end
+
+      def fetch(index)
+        STATIC_TABLE[index - 1] || @dynamic_table[index - STATIC_TABLE.size - 1] or raise HPACKError.new("invalid index")
+      end
+
+      def limit=(value)
+        @limit = value
+        evict
+      end
+    end
+  end
+end
diff --git a/lib/plum/hpack/decoder.rb b/lib/plum/hpack/decoder.rb
new file mode 100644
index 0000000..139b3eb
--- /dev/null
+++ b/lib/plum/hpack/decoder.rb
@@ -0,0 +1,134 @@
+module Plum
+  module HPACK
+    class Decoder
+      attr_reader :context
+
+      def initialize(dynamic_table_limit)
+        @context = Context.new(dynamic_table_limit)
+      end
+
+      def decode(str)
+        str = str.dup
+        headers = []
+        while str.size > 0
+          headers << parse!(str)
+        end
+        headers
+      end
+
+      private
+      def read_integer!(str, prefix_length)
+        mask = (1 << prefix_length) - 1
+        i = str.slice!(0, 1).ord & mask
+
+        if i == mask
+          m = 0
+          begin
+            next_value = str.slice!(0, 1).ord
+            i += (next_value & ~(0b10000000)) << m
+            m += 7
+          end until next_value & 0b10000000 == 0
+        end
+
+        i
+      end
+
+      def read_string!(str, length, huffman)
+        bin = str.slice!(0, length)
+        bin = Huffman.decode(bin) if huffman
+        bin
+      end
+
+      def parse!(str)
+        first_byte = str[0].ord
+        if first_byte & 0b10000000 == 0b10000000
+          # indexed
+          # +---+---+---+---+---+---+---+---+
+          # | 1 |        Index (7+)         |
+          # +---+---------------------------+
+          index = read_integer!(str, 7)
+          if index == 0
+            raise HPACKError.new("index can't be 0 in indexed heaeder field representation")
+          else
+            @context.fetch(index)
+          end
+        elsif first_byte & 0b11000000 == 0b01000000
+          # +---+---+---+---+---+---+---+---+
+          # | 0 | 1 |      Index (6+)       |
+          # +---+---+-----------------------+
+          # | H |     Value Length (7+)     |
+          # +---+---------------------------+
+          # | Value String (Length octets)  |
+          # +-------------------------------+
+          # or
+          # +---+---+---+---+---+---+---+---+
+          # | 0 | 1 |           0           |
+          # +---+---+-----------------------+
+          # | H |     Name Length (7+)      |
+          # +---+---------------------------+
+          # |  Name String (Length octets)  |
+          # +---+---------------------------+
+          # | H |     Value Length (7+)     |
+          # +---+---------------------------+
+          # | Value String (Length octets)  |
+          # +-------------------------------+
+          index = read_integer!(str, 6)
+          if index == 0
+            hname = (str[0].ord >> 7) == 1
+            lname = read_integer!(str, 7)
+            name = read_string!(str, lname, hname)
+          else
+            name, = @context.fetch(index)
+          end
+
+          hval = (str[0].ord >> 7) == 1
+          lval = read_integer!(str, 7)
+          val = read_string!(str, lval, hval)
+          @context.add(name, val)
+
+          [name, val]
+        elsif first_byte & 0b11110000 == 0b00000000 || # without indexing
+              first_byte & 0b11110000 == 0b00010000    # never indexing
+          # +---+---+---+---+---+---+---+---+
+          # | 0 | 0 | 0 |0,1|  Index (4+)   |
+          # +---+---+-----------------------+
+          # | H |     Value Length (7+)     |
+          # +---+---------------------------+
+          # | Value String (Length octets)  |
+          # +-------------------------------+
+          # or
+          # +---+---+---+---+---+---+---+---+
+          # | 0 | 0 | 0 |0,1|       0       |
+          # +---+---+-----------------------+
+          # | H |     Name Length (7+)      |
+          # +---+---------------------------+
+          # |  Name String (Length octets)  |
+          # +---+---------------------------+
+          # | H |     Value Length (7+)     |
+          # +---+---------------------------+
+          # | Value String (Length octets)  |
+          # +-------------------------------+
+          index = read_integer!(str, 4)
+          if index == 0
+            hname = (str[0].ord >> 7) == 1
+            lname = read_integer!(str, 7)
+            name = read_string!(str, lname, hname)
+          else
+            name, = @context.fetch(index)
+          end
+
+          hval = (str[0].ord >> 7) == 1
+          lval = read_integer!(str, 7)
+          val = read_string!(str, lval, hval)
+
+          [name, val]
+        elsif first_byte & 0b11100000 == 0b00100000
+          @context.limit = read_integer!(str, 5)
+          nil
+        else
+          raise HPACKError.new("invalid header firld representation")
+        end
+      end
+    end
+  end
+end
diff --git a/lib/plum/hpack/huffman.rb b/lib/plum/hpack/huffman.rb
new file mode 100644
index 0000000..a3f5ce3
--- /dev/null
+++ b/lib/plum/hpack/huffman.rb
@@ -0,0 +1,38 @@
+module Plum
+  module HPACK
+    module Huffman
+      extend self
+
+      # TODO: performance
+      def encode(bytestr)
+        out = ""
+        bytestr.bytes.each do |b|
+          out << HUFFMAN_TABLE[b]
+        end
+        out << "1" * (8 - (out.size % 8))
+        [out].pack("B*").b
+      end
+
+      # TODO: performance
+      def decode(encoded)
+        bits = encoded.unpack("B*")[0]
+        buf = ""
+        outl = []
+        while (n = bits.slice!(0, 1)).size > 0
+          if c = HUFFMAN_DECODE_TABLE[buf << n]
+            buf = ""
+            outl << c
+          end
+        end
+
+        if buf.size > 7
+          raise HPACKError.new("huffman: padding is too large (> 7 bits)")
+        elsif buf != "1" * buf.size
+          raise HPACKError.new("huffman: unknown suffix: #{buf}")
+        else
+          outl.pack("C*").b
+        end
+      end
+    end
+  end
+end