Class: Omnizip::Formats::Rar::Compression::LZ77Huffman::HuffmanCoder

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/formats/rar/compression/lz77_huffman/huffman_coder.rb

Overview

Huffman coding for RAR LZ77+Huffman compression

Implements canonical Huffman tree decoding for RAR archives. RAR uses multiple Huffman tables:

  • MC (Main Code): Literals and length codes
  • LD (Length-Distance): Distance codes
  • RC (Repeat Count): Run-length encoding
  • LDD (Low Distance): Low distance values

Responsibilities:

  • ONE responsibility: Huffman tree operations
  • Build canonical Huffman trees from code lengths
  • Decode symbols using Huffman trees
  • Parse tree structure from bit stream

Canonical Huffman Code Properties:

  • Codes of same length are sequential
  • Shorter codes have lower values
  • Deterministic tree construction from lengths

Constant Summary collapse

MAX_CODE_LENGTH =

Maximum code length for RAR

15

Instance Method Summary collapse

Constructor Details

#initialize ⇒ HuffmanCoder

Initialize Huffman coder



52
53
54
55
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_coder.rb', line 52

def initialize
  @decode_table = {}
  @code_lengths = []
end

Instance Method Details

#build_tree(code_lengths) ⇒ void

This method returns an undefined value.

Build Huffman tree from code lengths

Constructs a canonical Huffman tree given the code lengths for each symbol. This is how RAR transmits Huffman tables.

Parameters:

  • code_lengths (Array<Integer>) —

    Code length for each symbol



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
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_coder.rb', line 64

def build_tree(code_lengths)
  @code_lengths = code_lengths
  @decode_table = {}

  # Count codes of each length
  length_counts = Array.new(MAX_CODE_LENGTH + 1, 0)
  code_lengths.each do |len|
    length_counts[len] += 1 if len.positive?
  end

  # Calculate first code for each length
  first_codes = Array.new(MAX_CODE_LENGTH + 1, 0)
  code = 0
  (1..MAX_CODE_LENGTH).each do |len|
    first_codes[len] = code
    code = (code + length_counts[len]) << 1
  end

  # Assign codes to symbols
  code_lengths.each_with_index do |len, symbol|
    next if len.zero?

    code = first_codes[len]
    first_codes[len] += 1

    # Store in decode table: [code, length] => symbol
    key = (code << 8) | len
    @decode_table[key] = symbol
  end
end

#decode_symbol(bit_stream) ⇒ Integer?

Decode a single symbol from bit stream

Reads bits one at a time until a valid Huffman code is found, then returns the corresponding symbol.

Parameters:

  • bit_stream (BitStream) —

    Input bit stream

Returns:

  • (Integer, nil) —

    Decoded symbol or nil if end



102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_coder.rb', line 102

def decode_symbol(bit_stream)
  code = 0
  length = 0

  # Read bits until we find a valid code
  (1..MAX_CODE_LENGTH).each do |len|
    bit = bit_stream.read_bit
    code = (code << 1) | bit
    length = len

    # Check if this code exists in decode table
    key = (code << 8) | length
    return @decode_table[key] if @decode_table.key?(key)
  end

  # No valid code found
  nil
end

#empty? ⇒ Boolean

Check if tree is empty

Returns:

  • (Boolean) —

    True if no codes defined



149
150
151
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_coder.rb', line 149

def empty?
  @decode_table.empty?
end

#encode_symbol(symbol) ⇒ Array<Integer, Integer>

Encode a symbol (for future encoder implementation)

Parameters:

  • symbol (Integer) —

    Symbol to encode

Returns:

  • (Array<Integer, Integer>) —

    [code, length]



172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_coder.rb', line 172

def encode_symbol(symbol)
  # Find code for symbol
  @decode_table.each do |key, sym|
    next unless sym == symbol

    code = key >> 8
    length = key & 0xFF
    return [code, length]
  end

  nil
end

#parse_tree(bit_stream, num_symbols) ⇒ void

This method returns an undefined value.

Parse Huffman tree from RAR bit stream

RAR encodes Huffman trees in a compact format:

  1. Number of code lengths
  2. Code lengths (potentially compressed)
  3. Tree structure

This is a simplified implementation for MVP.

Parameters:

  • bit_stream (BitStream) —

    Input bit stream

  • num_symbols (Integer) —

    Number of symbols in alphabet



133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_coder.rb', line 133

def parse_tree(bit_stream, num_symbols)
  code_lengths = Array.new(num_symbols, 0)

  # Read code lengths (simplified - real RAR uses RLE)
  num_symbols.times do |i|
    # Read length as 4-bit value
    len = bit_stream.read_bits(4)
    code_lengths[i] = len
  end

  build_tree(code_lengths)
end

#reset ⇒ void

This method returns an undefined value.

Reset the coder



163
164
165
166
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_coder.rb', line 163

def reset
  @decode_table = {}
  @code_lengths = []
end

#symbol_count ⇒ Integer

Get number of symbols in tree

Returns:

  • (Integer) —

    Number of symbols



156
157
158
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_coder.rb', line 156

def symbol_count
  @decode_table.size
end