require_relative 'error' module HTTP2 # Implementation of huffman encoding for HPACK # # - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 module Header # Huffman encoder/decoder class Huffman include Error BITS_AT_ONCE = 4 BINARY = "binary" EOS = 256 private_constant :BINARY, :EOS def initialize @@encode_table ||= CODES.map{|c,l| [c].pack("N").unpack("B*").first[-l..-1]} end # Encodes provided value via huffman encoding. # Length is not encoded in this method. # # @param str [String] # @return [String] binary string def encode(str) bitstring = str.each_byte.map{|chr| @@encode_table[chr]}.join bitstring << "1" * ((8 - bitstring.size) % 8) [bitstring].pack("B*") end # Decodes provided Huffman coded string. # # @param buf [Buffer] # @return [String] binary string # @raise [CompressionError] when Huffman coded string is malformed def decode(buf) emit = '' state = 0 # start state mask = (1 << BITS_AT_ONCE) - 1 buf.each_byte do |chr| (8 / BITS_AT_ONCE - 1).downto(0) do |shift| branch = (chr >> (shift * BITS_AT_ONCE)) & mask # MACHINE[state] = [final, [transitions]] # [final] unfinished bits so far are prefix of the EOS code. # Each transition is [emit, next] # [emit] character to be emitted on this transition, empty string, or EOS. # [next] next state number. trans = MACHINE[state][branch] trans.first == EOS and raise CompressionError.new('Huffman decode error (EOS found)') trans.first && emit << trans.first state = trans.last end end # Check whether partial input is correctly filled unless state <= MAX_FINAL_STATE raise CompressionError.new('Huffman decode error (EOS invalid)') end emit.force_encoding(BINARY) end # Huffman table as specified in # - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08#appendix-C CODES = [ [ 0x1ff8, 13], [ 0x7fffd8, 23], [ 0xfffffe2, 28], [ 0xfffffe3, 28], [ 0xfffffe4, 28], [ 0xfffffe5, 28], [ 0xfffffe6, 28], [ 0xfffffe7, 28], [ 0xfffffe8, 28], [ 0xffffea, 24], [0x3ffffffc, 30], [ 0xfffffe9, 28], [ 0xfffffea, 28], [0x3ffffffd, 30], [ 0xfffffeb, 28], [ 0xfffffec, 28], [ 0xfffffed, 28], [ 0xfffffee, 28], [ 0xfffffef, 28], [ 0xffffff0, 28], [ 0xffffff1, 28], [ 0xffffff2, 28], [0x3ffffffe, 30], [ 0xffffff3, 28], [ 0xffffff4, 28], [ 0xffffff5, 28], [ 0xffffff6, 28], [ 0xffffff7, 28], [ 0xffffff8, 28], [ 0xffffff9, 28], [ 0xffffffa, 28], [ 0xffffffb, 28], [ 0x14, 6], [ 0x3f8, 10], [ 0x3f9, 10], [ 0xffa, 12], [ 0x1ff9, 13], [ 0x15, 6], [ 0xf8, 8], [ 0x7fa, 11], [ 0x3fa, 10], [ 0x3fb, 10], [ 0xf9, 8], [ 0x7fb, 11], [ 0xfa, 8], [ 0x16, 6], [ 0x17, 6], [ 0x18, 6], [ 0x0, 5], [ 0x1, 5], [ 0x2, 5], [ 0x19, 6], [ 0x1a, 6], [ 0x1b, 6], [ 0x1c, 6], [ 0x1d, 6], [ 0x1e, 6], [ 0x1f, 6], [ 0x5c, 7], [ 0xfb, 8], [ 0x7ffc, 15], [ 0x20, 6], [ 0xffb, 12], [ 0x3fc, 10], [ 0x1ffa, 13], [ 0x21, 6], [ 0x5d, 7], [ 0x5e, 7], [ 0x5f, 7], [ 0x60, 7], [ 0x61, 7], [ 0x62, 7], [ 0x63, 7], [ 0x64, 7], [ 0x65, 7], [ 0x66, 7], [ 0x67, 7], [ 0x68, 7], [ 0x69, 7], [ 0x6a, 7], [ 0x6b, 7], [ 0x6c, 7], [ 0x6d, 7], [ 0x6e, 7], [ 0x6f, 7], [ 0x70, 7], [ 0x71, 7], [ 0x72, 7], [ 0xfc, 8], [ 0x73, 7], [ 0xfd, 8], [ 0x1ffb, 13], [ 0x7fff0, 19], [ 0x1ffc, 13], [ 0x3ffc, 14], [ 0x22, 6], [ 0x7ffd, 15], [ 0x3, 5], [ 0x23, 6], [ 0x4, 5], [ 0x24, 6], [ 0x5, 5], [ 0x25, 6], [ 0x26, 6], [ 0x27, 6], [ 0x6, 5], [ 0x74, 7], [ 0x75, 7], [ 0x28, 6], [ 0x29, 6], [ 0x2a, 6], [ 0x7, 5], [ 0x2b, 6], [ 0x76, 7], [ 0x2c, 6], [ 0x8, 5], [ 0x9, 5], [ 0x2d, 6], [ 0x77, 7], [ 0x78, 7], [ 0x79, 7], [ 0x7a, 7], [ 0x7b, 7], [ 0x7ffe, 15], [ 0x7fc, 11], [ 0x3ffd, 14], [ 0x1ffd, 13], [ 0xffffffc, 28], [ 0xfffe6, 20], [ 0x3fffd2, 22], [ 0xfffe7, 20], [ 0xfffe8, 20], [ 0x3fffd3, 22], [ 0x3fffd4, 22], [ 0x3fffd5, 22], [ 0x7fffd9, 23], [ 0x3fffd6, 22], [ 0x7fffda, 23], [ 0x7fffdb, 23], [ 0x7fffdc, 23], [ 0x7fffdd, 23], [ 0x7fffde, 23], [ 0xffffeb, 24], [ 0x7fffdf, 23], [ 0xffffec, 24], [ 0xffffed, 24], [ 0x3fffd7, 22], [ 0x7fffe0, 23], [ 0xffffee, 24], [ 0x7fffe1, 23], [ 0x7fffe2, 23], [ 0x7fffe3, 23], [ 0x7fffe4, 23], [ 0x1fffdc, 21], [ 0x3fffd8, 22], [ 0x7fffe5, 23], [ 0x3fffd9, 22], [ 0x7fffe6, 23], [ 0x7fffe7, 23], [ 0xffffef, 24], [ 0x3fffda, 22], [ 0x1fffdd, 21], [ 0xfffe9, 20], [ 0x3fffdb, 22], [ 0x3fffdc, 22], [ 0x7fffe8, 23], [ 0x7fffe9, 23], [ 0x1fffde, 21], [ 0x7fffea, 23], [ 0x3fffdd, 22], [ 0x3fffde, 22], [ 0xfffff0, 24], [ 0x1fffdf, 21], [ 0x3fffdf, 22], [ 0x7fffeb, 23], [ 0x7fffec, 23], [ 0x1fffe0, 21], [ 0x1fffe1, 21], [ 0x3fffe0, 22], [ 0x1fffe2, 21], [ 0x7fffed, 23], [ 0x3fffe1, 22], [ 0x7fffee, 23], [ 0x7fffef, 23], [ 0xfffea, 20], [ 0x3fffe2, 22], [ 0x3fffe3, 22], [ 0x3fffe4, 22], [ 0x7ffff0, 23], [ 0x3fffe5, 22], [ 0x3fffe6, 22], [ 0x7ffff1, 23], [ 0x3ffffe0, 26], [ 0x3ffffe1, 26], [ 0xfffeb, 20], [ 0x7fff1, 19], [ 0x3fffe7, 22], [ 0x7ffff2, 23], [ 0x3fffe8, 22], [ 0x1ffffec, 25], [ 0x3ffffe2, 26], [ 0x3ffffe3, 26], [ 0x3ffffe4, 26], [ 0x7ffffde, 27], [ 0x7ffffdf, 27], [ 0x3ffffe5, 26], [ 0xfffff1, 24], [ 0x1ffffed, 25], [ 0x7fff2, 19], [ 0x1fffe3, 21], [ 0x3ffffe6, 26], [ 0x7ffffe0, 27], [ 0x7ffffe1, 27], [ 0x3ffffe7, 26], [ 0x7ffffe2, 27], [ 0xfffff2, 24], [ 0x1fffe4, 21], [ 0x1fffe5, 21], [ 0x3ffffe8, 26], [ 0x3ffffe9, 26], [ 0xffffffd, 28], [ 0x7ffffe3, 27], [ 0x7ffffe4, 27], [ 0x7ffffe5, 27], [ 0xfffec, 20], [ 0xfffff3, 24], [ 0xfffed, 20], [ 0x1fffe6, 21], [ 0x3fffe9, 22], [ 0x1fffe7, 21], [ 0x1fffe8, 21], [ 0x7ffff3, 23], [ 0x3fffea, 22], [ 0x3fffeb, 22], [ 0x1ffffee, 25], [ 0x1ffffef, 25], [ 0xfffff4, 24], [ 0xfffff5, 24], [ 0x3ffffea, 26], [ 0x7ffff4, 23], [ 0x3ffffeb, 26], [ 0x7ffffe6, 27], [ 0x3ffffec, 26], [ 0x3ffffed, 26], [ 0x7ffffe7, 27], [ 0x7ffffe8, 27], [ 0x7ffffe9, 27], [ 0x7ffffea, 27], [ 0x7ffffeb, 27], [ 0xffffffe, 28], [ 0x7ffffec, 27], [ 0x7ffffed, 27], [ 0x7ffffee, 27], [ 0x7ffffef, 27], [ 0x7fffff0, 27], [ 0x3ffffee, 26], [0x3fffffff, 30], ] end end end