Class: Omnizip::Algorithms::Zstandard::Huffman

Inherits:
Object
  • Object
show all
Includes:
Constants
Defined in:
lib/omnizip/algorithms/zstandard/huffman.rb

Overview

Huffman decoding for Zstandard (RFC 8878 Section 4.2)

Zstandard uses FSE-compressed Huffman weights followed by canonical Huffman decoding.

Constant Summary

Constants included from Constants

Constants::BLOCK_HEADER_SIZE, Constants::BLOCK_MAX_SIZE, Constants::BLOCK_TYPE_COMPRESSED, Constants::BLOCK_TYPE_RAW, Constants::BLOCK_TYPE_RESERVED, Constants::BLOCK_TYPE_RLE, Constants::BUFFER_SIZE, Constants::DEFAULT_LEVEL, Constants::DEFAULT_REPEAT_OFFSETS, Constants::FSE_MAX_ACCURACY_LOG, Constants::FSE_MIN_ACCURACY_LOG, Constants::HUFFMAN_MAX_BITS, Constants::HUFFMAN_MAX_CODE_LENGTH, Constants::HUFFMAN_MAX_LOG, Constants::HUFFMAN_STANDARD_TABLE_SIZE, Constants::LITERALS_BLOCK_COMPRESSED, Constants::LITERALS_BLOCK_RAW, Constants::LITERALS_BLOCK_RLE, Constants::LITERALS_BLOCK_TREELESS, Constants::LITERALS_LENGTH_ACCURACY_LOG, Constants::LITERAL_LENGTH_TABLE, Constants::MAGIC_BYTES, Constants::MAGIC_NUMBER, Constants::MATCH_LENGTH_ACCURACY_LOG, Constants::MATCH_LENGTH_TABLE, Constants::MAX_LEVEL, Constants::MIN_LEVEL, Constants::MODE_FSE, Constants::MODE_PREDEFINED, Constants::MODE_REPEAT, Constants::MODE_RLE, Constants::OFFSET_ACCURACY_LOG, Constants::PREDEFINED_LL_DISTRIBUTION, Constants::PREDEFINED_ML_DISTRIBUTION, Constants::PREDEFINED_OFFSET_DISTRIBUTION, Constants::REPEAT_OFFSET_1, Constants::REPEAT_OFFSET_2, Constants::REPEAT_OFFSET_3, Constants::SKIPPABLE_MAGIC_BASE, Constants::SKIPPABLE_MAGIC_MASK, Constants::WINDOW_LOG_MAX, Constants::WINDOW_LOG_MIN

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(decode_table, max_bits) ⇒ Huffman

Initialize Huffman decoder

Parameters:

  • decode_table (Hash) —

    Code to [symbol, length] mapping

  • max_bits (Integer) —

    Maximum code length



127
128
129
130
131
132
133
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 127

def initialize(decode_table, max_bits)
  @decode_table = decode_table
  @max_bits = max_bits

  # Build lookup table for faster decoding
  build_lookup_table
end

Instance Attribute Details

#decode_table ⇒ Hash<Integer, Array<Integer>> (readonly)

Returns Code to symbol mapping.

Returns:

  • (Hash<Integer, Array<Integer>>) —

    Code to symbol mapping



34
35
36
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 34

def decode_table
  @decode_table
end

#max_bits ⇒ Integer (readonly)

Returns Maximum code length.

Returns:

  • (Integer) —

    Maximum code length



37
38
39
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 37

def max_bits
  @max_bits
end

Class Method Details

.build_canonical_codes(code_lengths) ⇒ Hash<Integer, Integer>

Build canonical Huffman codes from lengths

Parameters:

  • code_lengths (Array<Integer>) —

    Code lengths for each symbol

Returns:

  • (Hash<Integer, Integer>) —

    Symbol to code mapping



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
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 92

def self.build_canonical_codes(code_lengths)
  codes = {}
  return codes if code_lengths.nil? || code_lengths.empty?

  max_length = code_lengths.compact.max || 0

  # Count symbols at each length
  bl_count = Array.new(max_length + 1, 0)
  code_lengths.each do |length|
    bl_count[length] += 1 if length&.positive?
  end

  # Calculate starting code for each length
  code = 0
  next_code = Array.new(max_length + 1, 0)
  (1..max_length).each do |bits|
    code = ((code + bl_count[bits - 1]) << 1)
    next_code[bits] = code
  end

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

    codes[symbol] = next_code[length]
    next_code[length] += 1
  end

  codes
end

.build_from_weights(weights, max_bits = HUFFMAN_MAX_BITS) ⇒ Huffman

Build Huffman table from weights

Parameters:

  • weights (Array<Integer>) —

    Symbol weights (0 means not present)

  • max_bits (Integer) (defaults to: HUFFMAN_MAX_BITS) —

    Maximum code length

Returns:

  • (Huffman) —

    Built Huffman decoder



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 44

def self.build_from_weights(weights, max_bits = HUFFMAN_MAX_BITS)
  # Convert weights to code lengths
  code_lengths = calculate_code_lengths(weights, max_bits)

  # Build canonical Huffman codes
  codes = build_canonical_codes(code_lengths)

  # Build decode table: code -> [symbol, length]
  decode_table = {}
  code_lengths.each_with_index do |length, symbol|
    next if length.nil? || length.zero?

    code = codes[symbol]
    decode_table[code] = [symbol, length]
  end

  new(decode_table, max_bits)
end

.calculate_code_lengths(weights, max_bits) ⇒ Array<Integer>

Calculate code lengths from weights

Weight 0 means symbol is not present. Higher weights mean shorter codes.

Parameters:

  • weights (Array<Integer>) —

    Symbol weights

  • max_bits (Integer) —

    Maximum code length

Returns:

  • (Array<Integer>) —

    Code lengths



71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 71

def self.calculate_code_lengths(weights, max_bits)
  return [] if weights.nil? || weights.empty?

  # Find max weight
  max_weight = weights.max || 0
  return Array.new(weights.length, 0) if max_weight.zero?

  # Convert weights to code lengths
  # Higher weight = shorter code length
  weights.map do |weight|
    next 0 if weight.nil? || weight.zero?

    # Code length = max_weight - weight + 1
    [max_weight - weight + 1, max_bits].min
  end
end

Instance Method Details

#decode(bitstream) ⇒ Integer

Decode a symbol from bitstream

Parameters:

Returns:

  • (Integer) —

    Decoded symbol



139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 139

def decode(bitstream)
  return 0 if @lookup_table.nil? || @lookup_table.empty?

  # Peek max_bits bits
  code = 0
  bits_read = 0

  (@max_bits || 1).times do
    bit = read_single_bit_forward(bitstream)
    code = (code << 1) | bit
    bits_read += 1

    # Check if this code exists in our table
    if @decode_table.key?(code)
      expected_length = @decode_table[code][1]
      if bits_read == expected_length
        return @decode_table[code][0]
      end
    end
  end

  # Fallback: try lookup table
  symbol = @lookup_table[code]
  return symbol if symbol

  0
end