Class: Cabriolet::Huffman::Tree

Inherits:
Object
  • Object
show all
Defined in:
lib/cabriolet/huffman/tree.rb

Overview

Tree builds Huffman decoding trees from code lengths

Constant Summary collapse

MAX_BITS =

Maximum code length supported

16

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(lengths, num_symbols, bit_order: :lsb) ⇒ Tree

Initialize a new Huffman tree

Parameters:

  • lengths (Array<Integer>) —

    Code lengths for each symbol

  • num_symbols (Integer) —

    Number of symbols

  • bit_order (Symbol) (defaults to: :lsb) —

    Bit ordering (:lsb or :msb), defaults to :lsb



17
18
19
20
21
22
 
# File 'lib/cabriolet/huffman/tree.rb', line 17

def initialize(lengths, num_symbols, bit_order: :lsb)
  @lengths = lengths
  @num_symbols = num_symbols
  @bit_order = bit_order
  @table = nil
end

Instance Attribute Details

#lengths ⇒ Object (readonly)

Returns the value of attribute lengths.



7
8
9
 
# File 'lib/cabriolet/huffman/tree.rb', line 7

def lengths
  @lengths
end

#num_symbols ⇒ Object (readonly)

Returns the value of attribute num_symbols.



7
8
9
 
# File 'lib/cabriolet/huffman/tree.rb', line 7

def num_symbols
  @num_symbols
end

#table ⇒ Object (readonly)

Returns the value of attribute table.



7
8
9
 
# File 'lib/cabriolet/huffman/tree.rb', line 7

def table
  @table
end

Instance Method Details

#build_table(table_bits) ⇒ Boolean

Build the fast decode table from code lengths

This implements a canonical Huffman decoding table based on the algorithm from libmspack (readhuff.h make_decode_table). The table has two levels:

  1. Direct lookup for codes <= table_bits length

  2. Linked entries for longer codes

Parameters:

  • table_bits (Integer) —

    Number of bits for table lookup (typically 6-12)

Returns:

  • (Boolean) —

    true if successful, false on error



34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/cabriolet/huffman/tree.rb', line 34

def build_table(table_bits)
  # Allocate table: (1 << table_bits) entries for direct lookup
  # Plus space for longer codes (up to num_symbols * 2)
  table_size = (1 << table_bits) + (num_symbols * 2)
  @table = Array.new(table_size, 0xFFFF)

  pos = 0
  table_mask = 1 << table_bits
  bit_mask = table_mask >> 1

  if @bit_order == :msb
    build_table_msb(table_bits, pos, table_mask, bit_mask)
  else
    build_table_lsb(table_bits, pos, table_mask, bit_mask)
  end
end