Class: Cabriolet::Huffman::Decoder

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

Overview

Decoder decodes Huffman-encoded symbols from a bitstream

Constant Summary collapse

MAX_BITS =

Maximum code length supported

16

Class Method Summary collapse

Class Method Details

.decode_symbol(bitstream, table, table_bits, lengths, num_symbols = nil) ⇒ Integer

Decode a symbol from the bitstream using the decode table

This implements fast Huffman decoding based on the libmspack algorithm (readhuff.h READ_HUFFSYM macro). It uses a two-level table:

  1. Direct lookup for codes <= table_bits length

  2. Tree traversal for longer codes

Parameters:

  • Bitstream to read from

  • Huffman decode table

  • Number of bits for table lookup

  • Code lengths for each symbol

  • (defaults to: nil)

    Number of symbols in the table

Returns:

  • Decoded symbol

Raises:

  • if decoding fails



24
25
26
27
28
29
30
31
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
 
# File 'lib/cabriolet/huffman/decoder.rb', line 24

def self.decode_symbol(bitstream, table, table_bits, lengths,
num_symbols = nil)
  # If num_symbols not provided, infer it from lengths
  num_symbols ||= lengths.size

  # Peek at table_bits from the bitstream
  bits = bitstream.peek_bits(table_bits)

  # Look up in the decode table
  sym = table[bits]

  # If symbol is directly in table (< num_symbols)
  if sym < num_symbols
    # Get code length for this symbol and consume the bits
    code_len = lengths[sym]
    bitstream.skip_bits(code_len)
    return sym
  end

  # Symbol is a pointer to second level tree
  # We need to traverse the tree for longer codes (> table_bits)
  # Start from table_bits - 1 and increment
  idx = table_bits - 1

  loop do
    idx += 1
    if idx > MAX_BITS
      raise Cabriolet::DecompressionError,
            "Huffman decode error: code too long"
    end

    # Get the next bit from bit buffer at position idx
    bit = (bitstream.peek_bits(idx + 1) >> idx) & 1

    # Follow the tree path: (current_entry << 1) | bit
    next_idx = (sym << 1) | bit
    sym = table[next_idx]

    # Check for nil (invalid table entry)
    if sym.nil? || sym == 0xFFFF
      raise Cabriolet::DecompressionError,
            "Huffman decode error: invalid code"
    end

    # Found a valid symbol?
    break if sym < num_symbols
  end

  # Consume idx + 1 bits (the full code length)
  bitstream.skip_bits(idx + 1)

  sym
end