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) ⇒ Tree

Initialize a new Huffman tree

Parameters:

  • lengths (Array<Integer>) —

    Code lengths for each symbol

  • num_symbols (Integer) —

    Number of symbols



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

def initialize(lengths, num_symbols)
  @lengths = lengths
  @num_symbols = num_symbols
  @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



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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
89
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
 
# File 'lib/cabriolet/huffman/tree.rb', line 32

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

  # Fill entries for codes short enough for direct mapping (LSB ordering)
  (1..table_bits).each do |bit_num|
    (0...num_symbols).each do |sym|
      next unless lengths[sym] == bit_num

      # Reverse the significant bits for LSB ordering
      fill = lengths[sym]
      reverse = pos >> (table_bits - fill)
      leaf = 0
      fill.times do
        leaf <<= 1
        leaf |= reverse & 1
        reverse >>= 1
      end

      pos += bit_mask
      return false if pos > table_mask

      # Fill all possible lookups of this symbol
      fill = bit_mask
      next_symbol = 1 << bit_num
      while fill.positive?
        @table[leaf] = sym
        leaf += next_symbol
        fill -= 1
      end
    end
    bit_mask >>= 1
  end

  # Exit with success if table is complete
  return true if pos == table_mask

  # Mark remaining entries as unused
  (pos...table_mask).each do |sym_idx|
    reverse = sym_idx
    leaf = 0
    fill = table_bits
    fill.times do
      leaf <<= 1
      leaf |= reverse & 1
      reverse >>= 1
    end
    @table[leaf] = 0xFFFF
  end

  # next_symbol = base of allocation for long codes
  next_symbol = [(table_mask >> 1), num_symbols].max

  # Process longer codes (table_bits + 1 to MAX_BITS)
  pos <<= 16
  table_mask <<= 16
  bit_mask = 1 << 15

  ((table_bits + 1)..MAX_BITS).each do |bit_num|
    (0...num_symbols).each do |sym|
      next unless lengths[sym] == bit_num

      return false if pos >= table_mask

      # leaf = the first table_bits of the code, reversed (LSB)
      reverse = pos >> 16
      leaf = 0
      fill = table_bits
      fill.times do
        leaf <<= 1
        leaf |= reverse & 1
        reverse >>= 1
      end

      # Build the tree path for this long code
      (0...(bit_num - table_bits)).each do |fill_idx|
        # If this path hasn't been taken yet, allocate two entries
        if @table[leaf] == 0xFFFF
          @table[next_symbol << 1] = 0xFFFF
          @table[(next_symbol << 1) + 1] = 0xFFFF
          @table[leaf] = next_symbol
          next_symbol += 1
        end

        # Follow the path and select either left or right for next bit
        leaf = @table[leaf] << 1
        leaf += 1 if (pos >> (15 - fill_idx)).anybits?(1)
      end

      @table[leaf] = sym
      pos += bit_mask
    end
    bit_mask >>= 1
  end

  # Full table?
  pos == table_mask
end