Module: Omnizip::Algorithms::Zstandard::HuffmanEncoder

Includes:
Constants
Defined in:
lib/omnizip/algorithms/zstandard/huffman_encoder.rb

Overview

Huffman encoder for Zstandard literals (RFC 8878 §4.2).

Builds a length-limited Huffman code from per-byte frequencies, emits the weight table (direct or FSE-compressed), and codes the literals into 1 or 4 reverse bitstreams.

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

Class Method Summary collapse

Methods included from Constants

highbit32

Class Method Details

.build_weights(literals) ⇒ Array<Integer>

Build 256 weights (0 for absent symbols) from the literal bytes, with code lengths capped at HUFFMAN_MAX_BITS.

Parameters:

  • literals (String)

Returns:

  • (Array<Integer>) 


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

def build_weights(literals)
  counts = Array.new(256, 0)
  literals.each_byte { |b| counts[b] += 1 }

  present = (0..255).select { |b| counts[b].positive? }
  if present.length < 2
    # A Huffman table needs at least 2 symbols; pad with
    # symbol 0 (or 1) so the real symbol keeps a real code.
    weights = Array.new(256, 0)
    sym = present.first || 0
    weights[sym] = 1
    other = sym.zero? ? 1 : 0
    weights[other] = 1
    return weights
  end

  freqs = present.map { |b| counts[b] }
  lengths = huffman_lengths(freqs)
  lengths = limit_lengths(lengths, HUFFMAN_MAX_BITS, freqs)

  max_len = lengths.max
  weights = Array.new(256, 0)
  present.each_with_index do |byte, i|
    weights[byte] = max_len - lengths[i] + 1
  end
  weights
end

.encode_huffman_stream(encode_table, literals) ⇒ String

Code literals into one reverse bitstream (C BIT_CStream direction): the encoder writes the last symbol first so the reverse reader recovers symbols in order.

Parameters:

  • encode_table (Array<Array(Integer, Integer)>)
  • literals (String)

Returns:

  • (String) 


313
314
315
316
317
318
319
320
321
322
323
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 313

def encode_huffman_stream(encode_table, literals)
  bitc = FSE::Encoder::BitCStream.new
  (literals.bytesize - 1).downto(0) do |i|
    code, len = encode_table[literals.getbyte(i)]
    next if len.zero?

    bitc.add_bits(code, len)
    bitc.flush
  end
  bitc.close
end

.encode_literals(literals) ⇒ String

Encode literals as a Compressed_Literals_Block section: header + weights + coded stream(s).

rubocop:disable Metrics/MethodLength rubocop:disable-next Metrics/AbcSize

Parameters:

  • literals (String)

Returns:

  • (String) 


246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 246

def encode_literals(literals)
  weights = build_weights(literals)
  # The wire format drops the last present weight (it is implied
  # by the Kraft inequality on decode), so the coding table must
  # be rebuilt exactly the way the decoder rebuilds it.
  max_symbol = weights.rindex(&:positive?)
  wire_weights = weights.first(max_symbol)
  full_weights = wire_weights +
    [HuffmanTableReader.implied_last_weight(wire_weights)]
  table = Huffman.from_weights(full_weights)
  encode_table = table.encode_table

  weights_wire = encode_weights(weights)
  lit_size = literals.bytesize

  # Single stream (3-byte header) when both sizes fit 10 bits.
  if lit_size < 1024
    coded = encode_huffman_stream(encode_table, literals)
    lit_c_size = weights_wire.bytesize + coded.bytesize
    if lit_c_size < 1024
      header = LITERALS_BLOCK_COMPRESSED |
        (lit_size << 4) | (lit_c_size << 14)
      return [header].pack("V")[0, 3] + weights_wire + coded
    end
  end

  # 4 streams with a jump table.
  segment_size = (lit_size + 3) / 4
  segments = Array.new(4) do |i|
    encode_huffman_stream(
      encode_table,
      literals.byteslice(segment_size * i, segment_size),
    )
  end

  lit_c_size = weights_wire.bytesize + 6 + segments.sum(&:bytesize)

  out = if lit_size < 1024 && lit_c_size < 1024
          header = LITERALS_BLOCK_COMPRESSED | (0b01 << 2) |
            (lit_size << 4) | (lit_c_size << 14)
          [header].pack("V")[0, 3]
        elsif lit_size < 16_384 && lit_c_size < 16_384
          header = LITERALS_BLOCK_COMPRESSED | (0b10 << 2) |
            (lit_size << 4) | (lit_c_size << 18)
          [header].pack("V")[0, 4]
        elsif lit_size < 262_144 && lit_c_size < 262_144
          low = LITERALS_BLOCK_COMPRESSED | (0b11 << 2) |
            (lit_size << 4) | ((lit_c_size & 0x3FF) << 22)
          [low].pack("V") + [(lit_c_size >> 10) & 0xFF].pack("C")
        else
          raise Omnizip::CompressionError,
                "literals section exceeds the 18-bit header limits"
        end

  out + weights_wire +
    segments.first(3).map { |s| [s.bytesize].pack("v") }.join +
    segments.join
end

.encode_weights(weights) ⇒ String

Serialize the weight table. Direct 4-bit weights when the alphabet fits, FSE-compressed otherwise.

Parameters:

  • weights (Array<Integer>)

Returns:

  • (String)

Raises:



184
185
186
187
188
189
190
191
192
193
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 184

def encode_weights(weights)
  max_symbol = weights.rindex(&:positive?)
  raise Omnizip::CompressionError, "no present Huffman weights" if max_symbol.nil?

  if max_symbol <= 128
    encode_weights_direct(weights, max_symbol)
  else
    encode_weights_fse(weights, max_symbol)
  end
end

.encode_weights_direct(weights, max_symbol) ⇒ Object

Direct encoding: header byte 127 + o_size, then two 4-bit weights per byte. The last present weight is implied on decode and is dropped here.



198
199
200
201
202
203
204
205
206
207
208
209
210
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 198

def encode_weights_direct(weights, max_symbol)
  o_size = max_symbol
  i_size = 127 + o_size
  out = [i_size].pack("C")

  (0...o_size).step(2) do |n|
    high = weights[n] & 0x0F
    low = n + 1 < o_size ? weights[n + 1] & 0x0F : 0
    out << ((high << 4) | low).chr
  end

  out
end

.encode_weights_fse(weights, max_symbol) ⇒ Object

FSE-compressed weights (RFC 8878 §4.2.1.2): payload-size header byte, NCount, then the 2-state bitstream.



214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 214

def encode_weights_fse(weights, max_symbol)
  o_size = max_symbol
  symbols = weights.first(o_size)

  distinct = symbols.uniq.length
  if distinct <= 1
    raise Omnizip::CompressionError,
          "uniform Huffman weights give no compression"
  end

  encoder = FSE::Encoder.build_from_symbols(symbols, 11, 6)
  if encoder.nil?
    raise Omnizip::CompressionError,
          "uniform Huffman weights give no compression"
  end

  payload = encoder.compress(symbols)
  if payload.bytesize >= 128
    raise Omnizip::CompressionError,
          "FSE weight payload exceeds the 127-byte header limit"
  end

  [payload.bytesize].pack("C") + payload
end

.huffman_lengths(freqs) ⇒ Array<Integer>

Standard Huffman code lengths via smallest-pair merging.

Parameters:

  • freqs (Array<Integer>)

Returns:

  • (Array<Integer>) —

    code length per symbol



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

def huffman_lengths(freqs)
  nodes = freqs.map { |f| { freq: f, parent: -1 } }

  while nodes.count { |n| n[:parent] == -1 } > 1
    a = -1
    b = -1
    nodes.each_with_index do |n, i|
      next unless n[:parent] == -1

      if a == -1 || n[:freq] < nodes[a][:freq]
        b = a
        a = i
      elsif b == -1 || n[:freq] < nodes[b][:freq]
        b = i
      end
    end

    nodes[a][:parent] = nodes.length
    nodes[b][:parent] = nodes.length
    nodes << { freq: nodes[a][:freq] + nodes[b][:freq], parent: -1 }
  end

  lengths = Array.new(freqs.length, 0)
  freqs.each_index do |i|
    len = 0
    cur = i
    while nodes[cur][:parent] != -1
      cur = nodes[cur][:parent]
      len += 1
    end
    lengths[i] = [len, 255].min
  end
  lengths
end

.kraft_adjust_index(lengths, freqs) ⇒ Object

Index of the least-frequent symbol matching the block.



168
169
170
171
172
173
174
175
176
177
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 168

def kraft_adjust_index(lengths, freqs)
  best = nil
  lengths.each_with_index do |l, i|
    next unless yield(l)
    next if best && freqs[i] >= freqs[best]

    best = i
  end
  best
end

.limit_lengths(lengths, max_len, freqs) ⇒ Array<Integer>

Cap code lengths at max_len and repair the Kraft sum to be EXACTLY 2^max_len, in integer arithmetic. An exact sum is what lets the decoder re-derive the dropped last weight as a clean power of two — a float-tolerance repair can leave the remainder non-power-of-two and the frame undecodable.

rubocop:disable Metrics/MethodLength rubocop:disable-next Metrics/AbcSize

Parameters:

  • lengths (Array<Integer>) —

    mutated in place

  • max_len (Integer)
  • freqs (Array<Integer>)

Returns:

  • (Array<Integer>) 


120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
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
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 120

def limit_lengths(lengths, max_len, freqs)
  lengths.map! { |l| [l, max_len].min }

  target = 1 << max_len
  kraft = lengths.sum { |l| l.positive? ? 1 << (max_len - l) : 0 }

  # Over-subscribed: lengthen the least-frequent shortest
  # codes until the sum fits.
  while kraft > target
    idx = kraft_adjust_index(lengths, freqs) do |l|
      l.positive? && l < max_len
    end
    lengths[idx] += 1
    kraft -= 1 << (max_len - lengths[idx])
  end

  # Under-subscribed: shorten the most-frequent code that fits
  # without overshooting; if none fits, lengthen one and let
  # the first loop re-fit.
  while kraft < target
    best = nil
    lengths.each_with_index do |l, i|
      next unless l > 1

      contribution = 1 << (max_len - l)
      next if kraft + contribution > target
      next if best && freqs[i] <= freqs[best]

      best = i
    end
    if best.nil?
      idx = kraft_adjust_index(lengths, freqs) do |l|
        l.positive? && l < max_len
      end
      lengths[idx] += 1
      kraft -= 1 << (max_len - lengths[idx])
    else
      delta = 1 << (max_len - lengths[best])
      lengths[best] -= 1
      kraft += delta
    end
  end

  lengths
end