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)) == 0 ? 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 == 0 @emit = chr else bit = (code & (1 << (len - 1))) == 0 ? 0 : 1 node = @next[bit] ||= Node.new(@depth + 1) node.add(code, len - 1, chr) end end