Class: Omnizip::Algorithms::Zstandard::HuffmanTableReader

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

Overview

Reads a Huffman tree description from the wire (RFC 8878 §4.2.1) and builds a Huffman decode table.

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

.implied_last_weight(weights) ⇒ Object

Compute the implied last weight via the Kraft inequality: sum(2^(w-1)) over all symbols equals 1 << tableLog.



235
236
237
238
239
240
241
242
243
244
245
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
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 235

def self.implied_last_weight(weights)
  weight_total = 0
  weights.each do |w|
    if w > HUFFMAN_MAX_LOG
      raise Omnizip::DecompressionError,
            "Huffman weight #{w} exceeds tableLog max"
    end

    weight_total += (1 << w) >> 1
  end
  if weight_total.zero?
    raise Omnizip::DecompressionError, "Huffman weights sum to 0"
  end

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

  rest = (1 << table_log) - weight_total
  if rest.zero?
    raise Omnizip::DecompressionError,
          "Huffman weights already complete; no implied weight"
  end
  unless rest.nobits?(rest - 1)
    raise Omnizip::DecompressionError,
          "Huffman implied weight remainder #{rest} is not a power of 2"
  end

  last_weight = Constants.highbit32(rest) + 1
  if last_weight > HUFFMAN_MAX_LOG
    raise Omnizip::DecompressionError,
          "Huffman implied weight #{last_weight} exceeds max"
  end

  last_weight
end

.read(src) ⇒ Array(Huffman, Integer)

Read the table from the head of src.

Parameters:

  • src (String)

Returns:

  • (Array(Huffman, Integer)) —

    table and bytes consumed

Raises:



177
178
179
180
181
182
183
184
185
186
187
188
189
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 177

def self.read(src)
  raise Omnizip::DecompressionError, "empty Huffman header" if src.empty?

  i_size = src.getbyte(0)
  weights, consumed =
    if i_size >= 128
      read_direct_weights(src)
    else
      read_fse_compressed_weights(src)
    end

  [Huffman.from_weights(weights), consumed]
end

.read_direct_weights(src) ⇒ Object

Direct 4-bit weights: byte 0 is 127 + o_size, then (o_size + 1) / 2 bytes holding two nibbles each.



193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 193

def self.read_direct_weights(src)
  i_size = src.getbyte(0)
  o_size = i_size - 127
  packed_bytes = (o_size + 1) / 2
  needed = 1 + packed_bytes
  if src.bytesize < needed
    raise Omnizip::DecompressionError,
          "truncated direct Huffman weights: need #{needed} bytes"
  end

  weights = []
  (0...o_size).step(2) do |n|
    byte = src.getbyte(1 + (n / 2))
    weights << (byte >> 4)
    weights << (byte & 0x0F) if n + 1 < o_size
  end

  weights << implied_last_weight(weights)
  [weights, needed]
end

.read_fse_compressed_weights(src) ⇒ Object

FSE-compressed weights: byte 0 is the payload size, followed by an FSE table description and a 2-state interleaved bitstream (RFC 8878 §4.2.1.2).



217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/omnizip/algorithms/zstandard/huffman.rb', line 217

def self.read_fse_compressed_weights(src)
  i_size = src.getbyte(0)
  if 1 + i_size > src.bytesize
    raise Omnizip::DecompressionError,
          "truncated FSE Huffman weights: need #{1 + i_size} bytes"
  end

  payload = src.byteslice(1, i_size)
  table, consumed = FSE.read_table(payload)
  bitstream = payload.byteslice(consumed..)

  weights = FSE.decode_stream(table, bitstream, HUF_SYMBOLVALUE_MAX)
  weights << implied_last_weight(weights)
  [weights, 1 + i_size]
end