Class: HuffmanTable::Node
- Inherits:
-
Object
- Object
- HuffmanTable::Node
- Defined in:
- lib/tasks/generate_huffman_table.rb
Defined Under Namespace
Classes: Transition
Constant Summary collapse
- @@id =
rubocop:disable Style/ClassVars
0
Class Attribute Summary collapse
-
.root ⇒ Object
readonly
Returns the value of attribute root.
Instance Attribute Summary collapse
-
#depth ⇒ Object
Returns the value of attribute depth.
-
#emit ⇒ Object
Returns the value of attribute emit.
-
#final ⇒ Object
Returns the value of attribute final.
-
#id ⇒ Object
Returns the value of attribute id.
-
#next ⇒ Object
Returns the value of attribute next.
-
#transitions ⇒ Object
Returns the value of attribute transitions.
Class Method Summary collapse
-
.decode(input) ⇒ Object
Test decoder.
- .generate_machine ⇒ Object
- .generate_state_table ⇒ Object
- .generate_tree ⇒ Object
Instance Method Summary collapse
- #add(code, len, chr) ⇒ Object
-
#initialize(depth) ⇒ Node
constructor
A new instance of Node.
Constructor Details
#initialize(depth) ⇒ Node
Returns a new instance of Node.
18 19 20 21 22 23 24 |
# 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 |
Class Attribute Details
.root ⇒ Object (readonly)
Returns the value of attribute root.
146 147 148 |
# File 'lib/tasks/generate_huffman_table.rb', line 146 def root @root end |
Instance Attribute Details
#depth ⇒ Object
Returns the value of attribute depth.
14 15 16 |
# File 'lib/tasks/generate_huffman_table.rb', line 14 def depth @depth end |
#emit ⇒ Object
Returns the value of attribute emit.
14 15 16 |
# File 'lib/tasks/generate_huffman_table.rb', line 14 def emit @emit end |
#final ⇒ Object
Returns the value of attribute final.
14 15 16 |
# File 'lib/tasks/generate_huffman_table.rb', line 14 def final @final end |
#id ⇒ Object
Returns the value of attribute id.
16 17 18 |
# File 'lib/tasks/generate_huffman_table.rb', line 16 def id @id end |
#next ⇒ Object
Returns the value of attribute next.
14 15 16 |
# File 'lib/tasks/generate_huffman_table.rb', line 14 def next @next end |
#transitions ⇒ Object
Returns the value of attribute transitions.
15 16 17 |
# File 'lib/tasks/generate_huffman_table.rb', line 15 def transitions @transitions end |
Class Method Details
.decode(input) ⇒ Object
Test decoder
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 |
# 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 ⇒ Object
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
# 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 ⇒ Object
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
# 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.('../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 |
Instance Method Details
#add(code, len, chr) ⇒ Object
26 27 28 29 30 31 32 33 34 35 |
# 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 |