hpack: huffman: refactor

2 files changed, 268 insertions, 276 deletions

diff --git a/lib/plum/hpack/constants.rb b/lib/plum/hpack/constants.rb
index 38c60d4..5c09a38 100644
--- a/lib/plum/hpack/constants.rb
+++ b/lib/plum/hpack/constants.rb
@@ -67,265 +67,265 @@ module Plum
     ]
 
     HUFFMAN_TABLE = [
-      [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] # EOS
+      "1111111111000",
+      "11111111111111111011000",
+      "1111111111111111111111100010",
+      "1111111111111111111111100011",
+      "1111111111111111111111100100",
+      "1111111111111111111111100101",
+      "1111111111111111111111100110",
+      "1111111111111111111111100111",
+      "1111111111111111111111101000",
+      "111111111111111111101010",
+      "111111111111111111111111111100",
+      "1111111111111111111111101001",
+      "1111111111111111111111101010",
+      "111111111111111111111111111101",
+      "1111111111111111111111101011",
+      "1111111111111111111111101100",
+      "1111111111111111111111101101",
+      "1111111111111111111111101110",
+      "1111111111111111111111101111",
+      "1111111111111111111111110000",
+      "1111111111111111111111110001",
+      "1111111111111111111111110010",
+      "111111111111111111111111111110",
+      "1111111111111111111111110011",
+      "1111111111111111111111110100",
+      "1111111111111111111111110101",
+      "1111111111111111111111110110",
+      "1111111111111111111111110111",
+      "1111111111111111111111111000",
+      "1111111111111111111111111001",
+      "1111111111111111111111111010",
+      "1111111111111111111111111011",
+      "010100",
+      "1111111000",
+      "1111111001",
+      "111111111010",
+      "1111111111001",
+      "010101",
+      "11111000",
+      "11111111010",
+      "1111111010",
+      "1111111011",
+      "11111001",
+      "11111111011",
+      "11111010",
+      "010110",
+      "010111",
+      "011000",
+      "00000",
+      "00001",
+      "00010",
+      "011001",
+      "011010",
+      "011011",
+      "011100",
+      "011101",
+      "011110",
+      "011111",
+      "1011100",
+      "11111011",
+      "111111111111100",
+      "100000",
+      "111111111011",
+      "1111111100",
+      "1111111111010",
+      "100001",
+      "1011101",
+      "1011110",
+      "1011111",
+      "1100000",
+      "1100001",
+      "1100010",
+      "1100011",
+      "1100100",
+      "1100101",
+      "1100110",
+      "1100111",
+      "1101000",
+      "1101001",
+      "1101010",
+      "1101011",
+      "1101100",
+      "1101101",
+      "1101110",
+      "1101111",
+      "1110000",
+      "1110001",
+      "1110010",
+      "11111100",
+      "1110011",
+      "11111101",
+      "1111111111011",
+      "1111111111111110000",
+      "1111111111100",
+      "11111111111100",
+      "100010",
+      "111111111111101",
+      "00011",
+      "100011",
+      "00100",
+      "100100",
+      "00101",
+      "100101",
+      "100110",
+      "100111",
+      "00110",
+      "1110100",
+      "1110101",
+      "101000",
+      "101001",
+      "101010",
+      "00111",
+      "101011",
+      "1110110",
+      "101100",
+      "01000",
+      "01001",
+      "101101",
+      "1110111",
+      "1111000",
+      "1111001",
+      "1111010",
+      "1111011",
+      "111111111111110",
+      "11111111100",
+      "11111111111101",
+      "1111111111101",
+      "1111111111111111111111111100",
+      "11111111111111100110",
+      "1111111111111111010010",
+      "11111111111111100111",
+      "11111111111111101000",
+      "1111111111111111010011",
+      "1111111111111111010100",
+      "1111111111111111010101",
+      "11111111111111111011001",
+      "1111111111111111010110",
+      "11111111111111111011010",
+      "11111111111111111011011",
+      "11111111111111111011100",
+      "11111111111111111011101",
+      "11111111111111111011110",
+      "111111111111111111101011",
+      "11111111111111111011111",
+      "111111111111111111101100",
+      "111111111111111111101101",
+      "1111111111111111010111",
+      "11111111111111111100000",
+      "111111111111111111101110",
+      "11111111111111111100001",
+      "11111111111111111100010",
+      "11111111111111111100011",
+      "11111111111111111100100",
+      "111111111111111011100",
+      "1111111111111111011000",
+      "11111111111111111100101",
+      "1111111111111111011001",
+      "11111111111111111100110",
+      "11111111111111111100111",
+      "111111111111111111101111",
+      "1111111111111111011010",
+      "111111111111111011101",
+      "11111111111111101001",
+      "1111111111111111011011",
+      "1111111111111111011100",
+      "11111111111111111101000",
+      "11111111111111111101001",
+      "111111111111111011110",
+      "11111111111111111101010",
+      "1111111111111111011101",
+      "1111111111111111011110",
+      "111111111111111111110000",
+      "111111111111111011111",
+      "1111111111111111011111",
+      "11111111111111111101011",
+      "11111111111111111101100",
+      "111111111111111100000",
+      "111111111111111100001",
+      "1111111111111111100000",
+      "111111111111111100010",
+      "11111111111111111101101",
+      "1111111111111111100001",
+      "11111111111111111101110",
+      "11111111111111111101111",
+      "11111111111111101010",
+      "1111111111111111100010",
+      "1111111111111111100011",
+      "1111111111111111100100",
+      "11111111111111111110000",
+      "1111111111111111100101",
+      "1111111111111111100110",
+      "11111111111111111110001",
+      "11111111111111111111100000",
+      "11111111111111111111100001",
+      "11111111111111101011",
+      "1111111111111110001",
+      "1111111111111111100111",
+      "11111111111111111110010",
+      "1111111111111111101000",
+      "1111111111111111111101100",
+      "11111111111111111111100010",
+      "11111111111111111111100011",
+      "11111111111111111111100100",
+      "111111111111111111111011110",
+      "111111111111111111111011111",
+      "11111111111111111111100101",
+      "111111111111111111110001",
+      "1111111111111111111101101",
+      "1111111111111110010",
+      "111111111111111100011",
+      "11111111111111111111100110",
+      "111111111111111111111100000",
+      "111111111111111111111100001",
+      "11111111111111111111100111",
+      "111111111111111111111100010",
+      "111111111111111111110010",
+      "111111111111111100100",
+      "111111111111111100101",
+      "11111111111111111111101000",
+      "11111111111111111111101001",
+      "1111111111111111111111111101",
+      "111111111111111111111100011",
+      "111111111111111111111100100",
+      "111111111111111111111100101",
+      "11111111111111101100",
+      "111111111111111111110011",
+      "11111111111111101101",
+      "111111111111111100110",
+      "1111111111111111101001",
+      "111111111111111100111",
+      "111111111111111101000",
+      "11111111111111111110011",
+      "1111111111111111101010",
+      "1111111111111111101011",
+      "1111111111111111111101110",
+      "1111111111111111111101111",
+      "111111111111111111110100",
+      "111111111111111111110101",
+      "11111111111111111111101010",
+      "11111111111111111110100",
+      "11111111111111111111101011",
+      "111111111111111111111100110",
+      "11111111111111111111101100",
+      "11111111111111111111101101",
+      "111111111111111111111100111",
+      "111111111111111111111101000",
+      "111111111111111111111101001",
+      "111111111111111111111101010",
+      "111111111111111111111101011",
+      "1111111111111111111111111110",
+      "111111111111111111111101100",
+      "111111111111111111111101101",
+      "111111111111111111111101110",
+      "111111111111111111111101111",
+      "111111111111111111111110000",
+      "11111111111111111111101110",
+      "111111111111111111111111111111"
     ]
     
-    HUFFMAN_DECODE_TABLE = HUFFMAN_TABLE.map {|val, len| "%0#{len}b" % val }.each_with_index.to_h
+    HUFFMAN_TABLE_INVERSED = HUFFMAN_TABLE.each_with_index.to_h
   end
 end
diff --git a/lib/plum/hpack/huffman.rb b/lib/plum/hpack/huffman.rb
index 0adeb22..2e44eba 100644
--- a/lib/plum/hpack/huffman.rb
+++ b/lib/plum/hpack/huffman.rb
@@ -7,32 +7,24 @@ module Plum
 
       # Static-Huffman-encodes the specified String.
       def encode(bytestr)
-        ret = []
-        remain = 0
+        out = ""
         bytestr.each_byte do |b|
-          val, len = HUFFMAN_TABLE[b]
-          l = len - remain
-
-          ret[-1] |= val >> l if ret.size > 0
-          while l > 0
-            ret << ((val >> (l - 8)) & 0xff)
-            l -= 8
-          end
-          remain = -l % 8
+          out << HUFFMAN_TABLE[b]
         end
-        ret[-1] |= (1 << remain) - 1 if remain > 0
-        ret.pack("C*")
+        out << "1" * (8 - (out.bytesize % 8))
+        [out].pack("B*")
       end
 
       # Static-Huffman-decodes the specified String.
       def decode(encoded)
         bits = encoded.unpack("B*")[0]
+        out = []
         buf = ""
-        outl = []
-        while (n = bits.byteshift(1)).bytesize > 0
-          if c = HUFFMAN_DECODE_TABLE[buf << n]
+        bits.each_char do |cb|
+          buf << cb
+          if c = HUFFMAN_TABLE_INVERSED[buf]
+            out << c
             buf = ""
-            outl << c
           end
         end
 
@@ -41,7 +33,7 @@ module Plum
         elsif buf != "1" * buf.bytesize
           raise HPACKError.new("huffman: unknown suffix: #{buf}")
         else
-          outl.pack("C*")
+          out.pack("C*")
         end
       end
     end