Class: Quicsilver::Protocol::Qpack::Huffman

Inherits:
Object
  • Object
show all
Defined in:
lib/quicsilver/protocol/qpack/huffman.rb

Constant Summary collapse

TABLE =

RFC 7541 Appendix B — HPACK Huffman Code Table (reused by QPACK per RFC 9204) Format: byte_value => [hex_code, bit_length] # |MSB binary with byte boundaries|

{
  0   => [0x1ff8, 13],      # |11111111|11000
  1   => [0x7fffd8, 23],    # |11111111|11111111|1011000
  2   => [0xfffffe2, 28],   # |11111111|11111111|11111110|0010
  3   => [0xfffffe3, 28],   # |11111111|11111111|11111110|0011
  4   => [0xfffffe4, 28],   # |11111111|11111111|11111110|0100
  5   => [0xfffffe5, 28],   # |11111111|11111111|11111110|0101
  6   => [0xfffffe6, 28],   # |11111111|11111111|11111110|0110
  7   => [0xfffffe7, 28],   # |11111111|11111111|11111110|0111
  8   => [0xfffffe8, 28],   # |11111111|11111111|11111110|1000
  9   => [0xffffea, 24],    # |11111111|11111111|11101010
  10  => [0x3ffffffc, 30],  # |11111111|11111111|11111111|111100
  11  => [0xfffffe9, 28],   # |11111111|11111111|11111110|1001
  12  => [0xfffffea, 28],   # |11111111|11111111|11111110|1010
  13  => [0x3ffffffd, 30],  # |11111111|11111111|11111111|111101
  14  => [0xfffffeb, 28],   # |11111111|11111111|11111110|1011
  15  => [0xfffffec, 28],   # |11111111|11111111|11111110|1100
  16  => [0xfffffed, 28],   # |11111111|11111111|11111110|1101
  17  => [0xfffffee, 28],   # |11111111|11111111|11111110|1110
  18  => [0xfffffef, 28],   # |11111111|11111111|11111110|1111
  19  => [0xffffff0, 28],   # |11111111|11111111|11111111|0000
  20  => [0xffffff1, 28],   # |11111111|11111111|11111111|0001
  21  => [0xffffff2, 28],   # |11111111|11111111|11111111|0010
  22  => [0x3ffffffe, 30],  # |11111111|11111111|11111111|111110
  23  => [0xffffff3, 28],   # |11111111|11111111|11111111|0011
  24  => [0xffffff4, 28],   # |11111111|11111111|11111111|0100
  25  => [0xffffff5, 28],   # |11111111|11111111|11111111|0101
  26  => [0xffffff6, 28],   # |11111111|11111111|11111111|0110
  27  => [0xffffff7, 28],   # |11111111|11111111|11111111|0111
  28  => [0xffffff8, 28],   # |11111111|11111111|11111111|1000
  29  => [0xffffff9, 28],   # |11111111|11111111|11111111|1001
  30  => [0xffffffa, 28],   # |11111111|11111111|11111111|1010
  31  => [0xffffffb, 28],   # |11111111|11111111|11111111|1011
  32  => [0x14, 6],         # |010100
  33  => [0x3f8, 10],       # |11111110|00
  34  => [0x3f9, 10],       # |11111110|01
  35  => [0xffa, 12],       # |11111111|1010
  36  => [0x1ff9, 13],      # |11111111|11001
  37  => [0x15, 6],         # |010101
  38  => [0xf8, 8],         # |11111000
  39  => [0x7fa, 11],       # |11111111|010
  40  => [0x3fa, 10],       # |11111110|10
  41  => [0x3fb, 10],       # |11111110|11
  42  => [0xf9, 8],         # |11111001
  43  => [0x7fb, 11],       # |11111111|011
  44  => [0xfa, 8],         # |11111010
  45  => [0x16, 6],         # |010110
  46  => [0x17, 6],         # |010111
  47  => [0x18, 6],         # |011000
  48  => [0x0, 5],          # |00000
  49  => [0x1, 5],          # |00001
  50  => [0x2, 5],          # |00010
  51  => [0x19, 6],         # |011001
  52  => [0x1a, 6],         # |011010
  53  => [0x1b, 6],         # |011011
  54  => [0x1c, 6],         # |011100
  55  => [0x1d, 6],         # |011101
  56  => [0x1e, 6],         # |011110
  57  => [0x1f, 6],         # |011111
  58  => [0x5c, 7],         # |1011100
  59  => [0xfb, 8],         # |11111011
  60  => [0x7ffc, 15],      # |11111111|1111100
  61  => [0x20, 6],         # |100000
  62  => [0xffb, 12],       # |11111111|1011
  63  => [0x3fc, 10],       # |11111111|00
  64  => [0x1ffa, 13],      # |11111111|11010
  65  => [0x21, 6],         # |100001
  66  => [0x5d, 7],         # |1011101
  67  => [0x5e, 7],         # |1011110
  68  => [0x5f, 7],         # |1011111
  69  => [0x60, 7],         # |1100000
  70  => [0x61, 7],         # |1100001
  71  => [0x62, 7],         # |1100010
  72  => [0x63, 7],         # |1100011
  73  => [0x64, 7],         # |1100100
  74  => [0x65, 7],         # |1100101
  75  => [0x66, 7],         # |1100110
  76  => [0x67, 7],         # |1100111
  77  => [0x68, 7],         # |1101000
  78  => [0x69, 7],         # |1101001
  79  => [0x6a, 7],         # |1101010
  80  => [0x6b, 7],         # |1101011
  81  => [0x6c, 7],         # |1101100
  82  => [0x6d, 7],         # |1101101
  83  => [0x6e, 7],         # |1101110
  84  => [0x6f, 7],         # |1101111
  85  => [0x70, 7],         # |1110000
  86  => [0x71, 7],         # |1110001
  87  => [0x72, 7],         # |1110010
  88  => [0xfc, 8],         # |11111100
  89  => [0x73, 7],         # |1110011
  90  => [0xfd, 8],         # |11111101
  91  => [0x1ffb, 13],      # |11111111|11011
  92  => [0x7fff0, 19],     # |11111111|11111110|000
  93  => [0x1ffc, 13],      # |11111111|11100
  94  => [0x3ffc, 14],      # |11111111|111100
  95  => [0x22, 6],         # |100010
  96  => [0x7ffd, 15],      # |11111111|1111101
  97  => [0x3, 5],          # |00011
  98  => [0x23, 6],         # |100011
  99  => [0x4, 5],          # |00100
  100 => [0x24, 6],         # |100100
  101 => [0x5, 5],          # |00101
  102 => [0x25, 6],         # |100101
  103 => [0x26, 6],         # |100110
  104 => [0x27, 6],         # |100111
  105 => [0x6, 5],          # |00110
  106 => [0x74, 7],         # |1110100
  107 => [0x75, 7],         # |1110101
  108 => [0x28, 6],         # |101000
  109 => [0x29, 6],         # |101001
  110 => [0x2a, 6],         # |101010
  111 => [0x7, 5],          # |00111
  112 => [0x2b, 6],         # |101011
  113 => [0x76, 7],         # |1110110
  114 => [0x2c, 6],         # |101100
  115 => [0x8, 5],          # |01000
  116 => [0x9, 5],          # |01001
  117 => [0x2d, 6],         # |101101
  118 => [0x77, 7],         # |1110111
  119 => [0x78, 7],         # |1111000
  120 => [0x79, 7],         # |1111001
  121 => [0x7a, 7],         # |1111010
  122 => [0x7b, 7],         # |1111011
  123 => [0x7ffe, 15],      # |11111111|1111110
  124 => [0x7fc, 11],       # |11111111|100
  125 => [0x3ffd, 14],      # |11111111|111101
  126 => [0x1ffd, 13],      # |11111111|11101
  127 => [0xffffffc, 28],   # |11111111|11111111|11111111|1100
  128 => [0xfffe6, 20],     # |11111111|11111110|0110
  129 => [0x3fffd2, 22],    # |11111111|11111111|010010
  130 => [0xfffe7, 20],     # |11111111|11111110|0111
  131 => [0xfffe8, 20],     # |11111111|11111110|1000
  132 => [0x3fffd3, 22],    # |11111111|11111111|010011
  133 => [0x3fffd4, 22],    # |11111111|11111111|010100
  134 => [0x3fffd5, 22],    # |11111111|11111111|010101
  135 => [0x7fffd9, 23],    # |11111111|11111111|1011001
  136 => [0x3fffd6, 22],    # |11111111|11111111|010110
  137 => [0x7fffda, 23],    # |11111111|11111111|1011010
  138 => [0x7fffdb, 23],    # |11111111|11111111|1011011
  139 => [0x7fffdc, 23],    # |11111111|11111111|1011100
  140 => [0x7fffdd, 23],    # |11111111|11111111|1011101
  141 => [0x7fffde, 23],    # |11111111|11111111|1011110
  142 => [0xffffeb, 24],    # |11111111|11111111|11101011
  143 => [0x7fffdf, 23],    # |11111111|11111111|1011111
  144 => [0xffffec, 24],    # |11111111|11111111|11101100
  145 => [0xffffed, 24],    # |11111111|11111111|11101101
  146 => [0x3fffd7, 22],    # |11111111|11111111|010111
  147 => [0x7fffe0, 23],    # |11111111|11111111|1100000
  148 => [0xffffee, 24],    # |11111111|11111111|11101110
  149 => [0x7fffe1, 23],    # |11111111|11111111|1100001
  150 => [0x7fffe2, 23],    # |11111111|11111111|1100010
  151 => [0x7fffe3, 23],    # |11111111|11111111|1100011
  152 => [0x7fffe4, 23],    # |11111111|11111111|1100100
  153 => [0x1fffdc, 21],    # |11111111|11111110|11100
  154 => [0x3fffd8, 22],    # |11111111|11111111|011000
  155 => [0x7fffe5, 23],    # |11111111|11111111|1100101
  156 => [0x3fffd9, 22],    # |11111111|11111111|011001
  157 => [0x7fffe6, 23],    # |11111111|11111111|1100110
  158 => [0x7fffe7, 23],    # |11111111|11111111|1100111
  159 => [0xffffef, 24],    # |11111111|11111111|11101111
  160 => [0x3fffda, 22],    # |11111111|11111111|011010
  161 => [0x1fffdd, 21],    # |11111111|11111110|11101
  162 => [0xfffe9, 20],     # |11111111|11111110|1001
  163 => [0x3fffdb, 22],    # |11111111|11111111|011011
  164 => [0x3fffdc, 22],    # |11111111|11111111|011100
  165 => [0x7fffe8, 23],    # |11111111|11111111|1101000
  166 => [0x7fffe9, 23],    # |11111111|11111111|1101001
  167 => [0x1fffde, 21],    # |11111111|11111110|11110
  168 => [0x7fffea, 23],    # |11111111|11111111|1101010
  169 => [0x3fffdd, 22],    # |11111111|11111111|011101
  170 => [0x3fffde, 22],    # |11111111|11111111|011110
  171 => [0xfffff0, 24],    # |11111111|11111111|11110000
  172 => [0x1fffdf, 21],    # |11111111|11111110|11111
  173 => [0x3fffdf, 22],    # |11111111|11111111|011111
  174 => [0x7fffeb, 23],    # |11111111|11111111|1101011
  175 => [0x7fffec, 23],    # |11111111|11111111|1101100
  176 => [0x1fffe0, 21],    # |11111111|11111111|00000
  177 => [0x1fffe1, 21],    # |11111111|11111111|00001
  178 => [0x3fffe0, 22],    # |11111111|11111111|100000
  179 => [0x1fffe2, 21],    # |11111111|11111111|00010
  180 => [0x7fffed, 23],    # |11111111|11111111|1101101
  181 => [0x3fffe1, 22],    # |11111111|11111111|100001
  182 => [0x7fffee, 23],    # |11111111|11111111|1101110
  183 => [0x7fffef, 23],    # |11111111|11111111|1101111
  184 => [0xfffea, 20],     # |11111111|11111110|1010
  185 => [0x3fffe2, 22],    # |11111111|11111111|100010
  186 => [0x3fffe3, 22],    # |11111111|11111111|100011
  187 => [0x3fffe4, 22],    # |11111111|11111111|100100
  188 => [0x7ffff0, 23],    # |11111111|11111111|1110000
  189 => [0x3fffe5, 22],    # |11111111|11111111|100101
  190 => [0x3fffe6, 22],    # |11111111|11111111|100110
  191 => [0x7ffff1, 23],    # |11111111|11111111|1110001
  192 => [0x3ffffe0, 26],   # |11111111|11111111|11111110|00
  193 => [0x3ffffe1, 26],   # |11111111|11111111|11111110|01
  194 => [0xfffeb, 20],     # |11111111|11111110|1011
  195 => [0x7fff1, 19],     # |11111111|11111110|001
  196 => [0x3fffe7, 22],    # |11111111|11111111|100111
  197 => [0x7ffff2, 23],    # |11111111|11111111|1110010
  198 => [0x3fffe8, 22],    # |11111111|11111111|101000
  199 => [0x1ffffec, 25],   # |11111111|11111111|11111110|1100
  200 => [0x3ffffe2, 26],   # |11111111|11111111|11111110|10
  201 => [0x3ffffe3, 26],   # |11111111|11111111|11111110|11
  202 => [0x3ffffe4, 26],   # |11111111|11111111|11111111|00
  203 => [0x7ffffde, 27],   # |11111111|11111111|11111111|011
  204 => [0x7ffffdf, 27],   # |11111111|11111111|11111111|100
  205 => [0x3ffffe5, 26],   # |11111111|11111111|11111111|01
  206 => [0xfffff1, 24],    # |11111111|11111111|11110001
  207 => [0x1ffffed, 25],   # |11111111|11111111|11111110|1101
  208 => [0x7fff2, 19],     # |11111111|11111110|010
  209 => [0x1fffe3, 21],    # |11111111|11111111|00011
  210 => [0x3ffffe6, 26],   # |11111111|11111111|11111111|10
  211 => [0x7ffffe0, 27],   # |11111111|11111111|11111111|110
  212 => [0x7ffffe1, 27],   # |11111111|11111111|11111111|111
  213 => [0x3ffffe7, 26],   # |11111111|11111111|11111111|11
  214 => [0x7ffffe2, 27],   # |11111111|11111111|11111110|000
  215 => [0xfffff2, 24],    # |11111111|11111111|11110010
  216 => [0x1fffe4, 21],    # |11111111|11111111|00100
  217 => [0x1fffe5, 21],    # |11111111|11111111|00101
  218 => [0x3ffffe8, 26],   # |11111111|11111111|11111110|0000
  219 => [0x3ffffe9, 26],   # |11111111|11111111|11111110|0001
  220 => [0xffffffd, 28],   # |11111111|11111111|11111111|1101
  221 => [0x7ffffe3, 27],   # |11111111|11111111|11111110|001
  222 => [0x7ffffe4, 27],   # |11111111|11111111|11111110|010
  223 => [0x7ffffe5, 27],   # |11111111|11111111|11111110|011
  224 => [0xfffec, 20],     # |11111111|11111110|1100
  225 => [0xfffff3, 24],    # |11111111|11111111|11110011
  226 => [0xfffed, 20],     # |11111111|11111110|1101
  227 => [0x1fffe6, 21],    # |11111111|11111111|00110
  228 => [0x3fffe9, 22],    # |11111111|11111111|101001
  229 => [0x1fffe7, 21],    # |11111111|11111111|00111
  230 => [0x1fffe8, 21],    # |11111111|11111111|01000
  231 => [0x7ffff3, 23],    # |11111111|11111111|1110011
  232 => [0x3fffea, 22],    # |11111111|11111111|101010
  233 => [0x3fffeb, 22],    # |11111111|11111111|101011
  234 => [0x1ffffee, 25],   # |11111111|11111111|11111110|1110
  235 => [0x1ffffef, 25],   # |11111111|11111111|11111110|1111
  236 => [0xfffff4, 24],    # |11111111|11111111|11110100
  237 => [0xfffff5, 24],    # |11111111|11111111|11110101
  238 => [0x3ffffea, 26],   # |11111111|11111111|11111110|1010
  239 => [0x7ffff4, 23],    # |11111111|11111111|1110100
  240 => [0x3ffffeb, 26],   # |11111111|11111111|11111110|1011
  241 => [0x7ffffe6, 27],   # |11111111|11111111|11111110|110
  242 => [0x3ffffec, 26],   # |11111111|11111111|11111110|1100
  243 => [0x3ffffed, 26],   # |11111111|11111111|11111110|1101
  244 => [0x7ffffe7, 27],   # |11111111|11111111|11111110|111
  245 => [0x7ffffe8, 27],   # |11111111|11111111|11111111|000
  246 => [0x7ffffe9, 27],   # |11111111|11111111|11111111|001
  247 => [0x7ffffea, 27],   # |11111111|11111111|11111111|010
  248 => [0x7ffffeb, 27],   # |11111111|11111111|11111111|011
  249 => [0xffffffe, 28],   # |11111111|11111111|11111111|1110
  250 => [0x7ffffec, 27],   # |11111111|11111111|11111111|100
  251 => [0x7ffffed, 27],   # |11111111|11111111|11111111|101
  252 => [0x7ffffee, 27],   # |11111111|11111111|11111111|110
  253 => [0x7ffffef, 27],   # |11111111|11111111|11111111|111
  254 => [0x7fffff0, 27],   # |11111111|11111111|11111110|0000
  255 => [0x3ffffee, 26],   # |11111111|11111111|11111110|1110
}.freeze
EOS =

|11111111|11111111|11111111|111111

[0x3fffffff, 30]
REVERSE_TABLE = 
TABLE.each_with_object({}) do |(byte, (code, length)), tree|
  node = tree
  # Walk bits MSB-first
  (length - 1).downto(0) do |i|
    bit = (code >> i) & 1
    node[bit] ||= {}
    node = node[bit]
  end
  node[:value] = byte
end
DECODE_ACCEL =

Build 8-bit-at-a-time decode acceleration table. DECODE_ACCEL[byte] = [new_state_id, emitted_bytes_array] State 0 = root node.

begin
  # Assign integer IDs to all tree nodes
  node_to_id = {}
  id_to_node = []
  queue = [REVERSE_TABLE]
  node_to_id[REVERSE_TABLE.object_id] = 0
  id_to_node << REVERSE_TABLE

  i = 0
  while i < queue.size
    node = queue[i]
    [0, 1].each do |bit|
      child = node[bit]
      next unless child
      unless node_to_id.key?(child.object_id)
        node_to_id[child.object_id] = id_to_node.size
        id_to_node << child
        queue << child
      end
    end
    i += 1
  end

  num_states = id_to_node.size
  table = Array.new(num_states) { Array.new(256) }

  num_states.times do |sid|
    256.times do |byte_val|
      node = id_to_node[sid]
      emitted = []
      valid = true
      trailing_bits = 0  # bits since last emitted symbol
      7.downto(0) do |bit_idx|
        bit = (byte_val >> bit_idx) & 1
        child = node[bit]
        unless child
          valid = false
          break
        end
        if child.key?(:value)
          emitted << child[:value]
          node = REVERSE_TABLE
          trailing_bits = 0
        else
          node = child
          trailing_bits += 1
        end
      end
      if valid
        new_sid = node_to_id[node.object_id]
        table[sid][byte_val] = [new_sid, emitted, trailing_bits].freeze
      else
        table[sid][byte_val] = nil
      end
    end
    table[sid].freeze
  end
  table.freeze
end
ENCODE_CODES =

Pre-compute flat arrays for faster table access (avoid hash lookup per byte)

Array.new(256) { |i| TABLE[i][0] }
ENCODE_LENGTHS = 
Array.new(256) { |i| TABLE[i][1] }
HUFF_ENCODE_CACHE =

Thread-safe caches for frequently encoded/decoded strings Using module-level constants for caches — YJIT can inline constant access

{}
HUFF_ENCODE_MUTEX = 
Mutex.new
HUFF_DECODE_CACHE = 
{}
HUFF_DECODE_MUTEX = 
Mutex.new
CACHE_MAX = 
256

Class Method Summary collapse

Class Method Details

.decode(encoded_data) ⇒ Object 



404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
 
# File 'lib/quicsilver/protocol/qpack/huffman.rb', line 404

def decode(encoded_data)
  # Check cache first (fast path) — returns frozen string
  cached = HUFF_DECODE_CACHE[encoded_data]
  return cached if cached

  return "".b if encoded_data.empty?

  result = decode_uncached(encoded_data)

  # Cache short encoded data (frozen)
  if encoded_data.bytesize <= 128 && result && HUFF_DECODE_CACHE.size < CACHE_MAX
    HUFF_DECODE_MUTEX.synchronize do
      key = encoded_data.frozen? ? encoded_data : encoded_data.dup.freeze
      HUFF_DECODE_CACHE[key] = result.freeze if HUFF_DECODE_CACHE.size < CACHE_MAX
    end
  end

  result
end

.decode_uncached(encoded_data) ⇒ Object 



424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
 
# File 'lib/quicsilver/protocol/qpack/huffman.rb', line 424

def decode_uncached(encoded_data)
  return "".b if encoded_data.empty?

  state = 0
  output = []
  bits_since_symbol = 0

  encoded_data.each_byte do |byte|
    entry = DECODE_ACCEL[state][byte]
    return nil unless entry # invalid code

    new_state, emitted, trailing = entry
    output.concat(emitted) unless emitted.empty?
    # trailing = bits since last emitted symbol within this byte processing
    # If no symbols were emitted, add 8 to running count
    bits_since_symbol = emitted.empty? ? bits_since_symbol + 8 : trailing
    state = new_state
  end

  # Padding validation (RFC 7541 §5.2):
  return nil if bits_since_symbol >= 8

  # Padding bits must all be 1
  if bits_since_symbol > 0
    last_byte = encoded_data.getbyte(-1)
    mask = (1 << bits_since_symbol) - 1
    return nil if (last_byte & mask) != mask
  end

  output.pack("C*")
end

.encode(data) ⇒ Object 



360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
 
# File 'lib/quicsilver/protocol/qpack/huffman.rb', line 360

def encode(data)
  # Check cache first (fast path) — returns frozen string
  cached = HUFF_ENCODE_CACHE[data]
  return cached if cached

  result = encode_uncached(data)

  # Cache short strings (frozen)
  if data.bytesize <= 128 && HUFF_ENCODE_CACHE.size < CACHE_MAX
    HUFF_ENCODE_MUTEX.synchronize do
      HUFF_ENCODE_CACHE[data.frozen? ? data : data.dup.freeze] = result.freeze if HUFF_ENCODE_CACHE.size < CACHE_MAX
    end
  end

  result
end

.encode_uncached(data) ⇒ Object 



377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
 
# File 'lib/quicsilver/protocol/qpack/huffman.rb', line 377

def encode_uncached(data)
  buf = 0
  buf_len = 0
  out = []

  data.each_byte do |byte|
    code = ENCODE_CODES[byte]
    length = ENCODE_LENGTHS[byte]
    buf = (buf << length) | code
    buf_len += length

    # Flush complete bytes
    while buf_len >= 8
      buf_len -= 8
      out << ((buf >> buf_len) & 0xff)
    end
  end

  # Pad with EOS prefix (1-bits) to next byte boundary
  if buf_len > 0
    padding = 8 - buf_len
    out << (((buf << padding) | ((1 << padding) - 1)) & 0xff)
  end

  out.pack("C*")
end