class HuffmanTable::Node

Attributes

root[R]
depth[RW]
emit[RW]
final[RW]
id[RW]
next[RW]
transitions[RW]

Public Class Methods

decode(input) click to toggle source

Test decoder

# File lib/tasks/generate_huffman_table.rb, line 150
def self.decode(input)
  emit = ''
  n = root
  nibbles = input.unpack('C*').flat_map { |b| [((b & 0xf0) >> 4), b & 0xf] }
  until nibbles.empty?
    nb = nibbles.shift
    t = n.transitions[nb]
    emit << t.emit
    n = t.node
  end
  unless n.final && nibbles.all? { |x| x == 0xf }
    puts "len = #{emit.size} n.final = #{n.final} nibbles = #{nibbles}"
  end
  emit
end
generate_machine() click to toggle source
# File lib/tasks/generate_huffman_table.rb, line 55
def self.generate_machine
  generate_tree
  togo = Set[@root]
  @states = Set[@root]

  until togo.empty?
    node = togo.first
    togo.delete(node)

    next if node.transitions
    node.transitions = Array[1 << BITS_AT_ONCE]

    (1 << BITS_AT_ONCE).times do |input|
      n = node
      emit = ''
      (BITS_AT_ONCE - 1).downto(0) do |i|
        bit = (input & (1 << i)).zero? ? 0 : 1
        n = n.next[bit]
        next unless n.emit
        if n.emit == EOS
          emit = EOS # cause error on decoding
        else
          emit << n.emit.chr(Encoding::BINARY) unless emit == EOS
        end
        n = @root
      end
      node.transitions[input] = Transition.new(emit, n)
      togo << n
      @states << n
    end
  end
  puts "#{@states.size} states"
  @root
end
generate_state_table() click to toggle source
# File lib/tasks/generate_huffman_table.rb, line 90
    def self.generate_state_table
      generate_machine
      state_id = {}
      id_state = {}
      state_id[@root] = 0
      id_state[0] = @root
      max_final = 0
      id = 1
      (@states - [@root]).sort_by { |s| s.final ? 0 : 1 }.each do |s|
        state_id[s] = id
        id_state[id] = s
        max_final = id if s.final
        id += 1
      end

      File.open(File.expand_path('../http/2/huffman_statemachine.rb', File.dirname(__FILE__)), 'w') do |f|
        f.print <<HEADER
# Machine generated Huffman decoder state machine.
# DO NOT EDIT THIS FILE.

# The following task generates this file.
#   rake generate_huffman_table

module HTTP2
  module Header
    class Huffman
      # :nodoc:
      MAX_FINAL_STATE = #{max_final}
      MACHINE = [
HEADER
        id.times do |i|
          n = id_state[i]
          f.print '        ['
          string = (1 << BITS_AT_ONCE).times.map do |t|
            transition = n.transitions.fetch(t)
            emit = transition.emit
            unless emit == EOS
              bytes = emit.bytes
              fail ArgumentError if bytes.size > 1
              emit = bytes.first
            end
            "[#{emit.inspect}, #{state_id.fetch(transition.node)}]"
          end.join(', ')
          f.print(string)
          f.print "],\n"
        end
        f.print <<TAILER
      ].each { |arr| arr.each { |subarr| subarr.each(&:freeze) }.freeze }.freeze
    end
  end
end
TAILER
      end
    end
generate_tree() click to toggle source
# File lib/tasks/generate_huffman_table.rb, line 45
def self.generate_tree
  @root = new(0)
  HTTP2::Header::Huffman::CODES.each_with_index do |c, chr|
    code, len = c
    @root.add(code, len, chr)
  end
  puts "#{@@id} nodes"
  @root
end
new(depth) click to toggle source
# File lib/tasks/generate_huffman_table.rb, line 18
def initialize(depth)
  @next = [nil, nil]
  @id = @@id
  @@id += 1 # rubocop:disable Style/ClassVars
  @final = false
  @depth = depth
end

Public Instance Methods

add(code, len, chr) click to toggle source
# File lib/tasks/generate_huffman_table.rb, line 26
def add(code, len, chr)
  self.final = true if chr == EOS && @depth <= 7
  if len.zero?
    @emit = chr
  else
    bit = (code & (1 << (len - 1))).zero? ? 0 : 1
    node = @next[bit] ||= Node.new(@depth + 1)
    node.add(code, len - 1, chr)
  end
end