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

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

Overview

Huffman coding for Zstandard literals (RFC 8878 ยง4.2).

Zstandard does NOT use symbol-ordered canonical Huffman. The decode table groups symbols by weight: all weight-1 symbols occupy the first DTable entries, then weight-2, and so on, with ascending symbol order inside each group. A symbol with weight w has code length (tableLog + 1 - w) and occupies (1 << w) >> 1 consecutive DTable entries.

Defined Under Namespace

Classes: DecodeEntry

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_DEFAULT_TABLELOG, 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::HUF_SYMBOLVALUE_MAX, Constants::LDM_MIN_LEVEL, 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::OF_BASE, Constants::OF_BITS, 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

Methods included from Constants

highbit32

Constructor Details

#initialize(weights, table_log) ⇒ Huffman

Returns a new instance of Huffman.



54
55
56
57
58
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 54

def initialize(weights, table_log)
  @weights = weights
  @table_log = table_log
  @lookup = nil
end

Instance Attribute Details

#table_log ⇒ Integer (readonly)

Returns table log (max code length in this tree).

Returns:

  • (Integer) —

    table log (max code length in this tree)



43
44
45
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 43

def table_log
  @table_log
end

#weights ⇒ Array<Integer> (readonly)

Returns per-symbol weights (0 = absent).

Returns:

  • (Array<Integer>) —

    per-symbol weights (0 = absent)



40
41
42
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 40

def weights
  @weights
end

Class Method Details

.compute_table_log(weights) ⇒ Integer

Derive tableLog from the Kraft sum of the weights (C reference HUF_readStats).

Returns:

  • (Integer) 


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 143

def self.compute_table_log(weights)
  if weights.empty? || weights.all?(0)
    raise Omnizip::DecompressionError,
          "Huffman weights: no present symbols"
  end

  weight_total = weights.sum { |w| w.positive? ? (1 << w) >> 1 : 0 }
  if weight_total.zero?
    raise Omnizip::DecompressionError, "Huffman weight total is 0"
  end

  table_log = if weight_total.nobits?(weight_total - 1)
                Constants.highbit32(weight_total)
              else
                Constants.highbit32(weight_total) + 1
              end
  if table_log > HUFFMAN_MAX_BITS
    raise Omnizip::DecompressionError,
          "Huffman tableLog #{table_log} exceeds max #{HUFFMAN_MAX_BITS}"
  end

  table_log
end

.from_weights(weights) ⇒ Huffman

Build a decode table from per-symbol weights.

Parameters:

  • weights (Array<Integer>) —

    one entry per symbol

Returns:



49
50
51
52
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 49

def self.from_weights(weights)
  table_log = compute_table_log(weights)
  new(weights, table_log)
end

Instance Method Details

#decode(bitstream) ⇒ Integer

Decode one symbol from a reverse bitstream (peek max_bits, look up, consume the code's length).

Parameters:

Returns:

  • (Integer) —

    decoded symbol byte



65
66
67
68
69
70
71
72
73
74
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 65

def decode(bitstream)
  entry = lookup[bitstream.peek_bits(HUFFMAN_MAX_BITS)]
  if entry.nil? || entry.nb_bits.zero?
    raise Omnizip::DecompressionError,
          "Huffman lookup miss: no code for the next bits"
  end

  bitstream.read_bits(entry.nb_bits)
  entry.symbol
end

#encode_table ⇒ Array<Array(Integer, Integer)>

Per-symbol (code, length) table for encoding, indexed by symbol value. Absent symbols map to (0, 0).

Returns:

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


118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 118

def encode_table
  @encode_table ||= begin
    codes = Array.new(@weights.length) { [0, 0] }
    max_weight = @weights.max || 0
    dtable_pos = 0
    (1..max_weight).each do |w|
      length = @table_log + 1 - w
      entries_per_symbol = (1 << w) >> 1
      @weights.each_with_index do |sw, sym|
        next unless sw == w

        code = dtable_pos >> (@table_log - length)
        codes[sym] = [code, length]
        dtable_pos += entries_per_symbol
      end
    end
    codes.fill([0, 0], codes.length..255)
    codes
  end
end

#lookup ⇒ Array<DecodeEntry>

Build the flat 1 << HUFFMAN_MAX_BITS lookup table.

Returns:



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

def lookup
  @lookup ||= begin
    table_size = 1 << @table_log
    dtable = Array.new(table_size) { DecodeEntry.new(0, 0) }
    max_weight = @weights.max || 0

    pos = 0
    (1..max_weight).each do |w|
      length = @table_log + 1 - w
      entries_per_symbol = (1 << w) >> 1
      @weights.each_with_index do |sw, sym|
        next unless sw == w

        entry = DecodeEntry.new(sym, length)
        entries_per_symbol.times do
          if pos < table_size
            dtable[pos] = entry
            pos += 1
          end
        end
      end
    end

    expand = 1 << (HUFFMAN_MAX_BITS - @table_log)
    lookup = []
    table_size.times do |i|
      expand.times { lookup << dtable[i] }
    end
    while lookup.length < (1 << HUFFMAN_MAX_BITS)
      lookup << DecodeEntry.new(0, 0)
    end
    lookup
  end
end