Class: Omnizip::Algorithms::Zstandard::SequenceExecutor

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

Overview

Stateful LZ77 sequence executor (RFC 8878 ยง3.1.2). Tracks the three repeat-offset slots across the frame; the slots are updated while decoding each sequence's offset.

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

Instance Method Summary collapse

Methods included from Constants

highbit32

Constructor Details

#initialize ⇒ SequenceExecutor

Returns a new instance of SequenceExecutor.



252
253
254
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 252

def initialize
  @repeat_offsets = DEFAULT_REPEAT_OFFSETS.dup
end

Instance Attribute Details

#repeat_offsets ⇒ Array<Integer> (readonly)

Returns repeat offsets, most recent first.

Returns:

  • (Array<Integer>) —

    repeat offsets, most recent first



250
251
252
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 250

def repeat_offsets
  @repeat_offsets
end

Instance Method Details

#execute(literals, sequences, output) ⇒ String

Execute decoded sequences against the literal buffer, appending to output and returning the produced bytes.

rubocop:disable Metrics/AbcSize

Parameters:

Returns:

  • (String) —

    the block's output



319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 319

def execute(literals, sequences, output)
  lit_pos = 0
  block_start = output.bytesize

  sequences.each do |seq|
    ll = seq.literal_length
    if ll.positive?
      take = [ll, literals.bytesize - lit_pos].min
      output << literals.byteslice(lit_pos, take)
      lit_pos += take
    end
    # rubocop:enable Metrics/AbcSize

    distance = seq.offset
    if distance.zero? || distance > output.bytesize
      raise Omnizip::DecompressionError,
            "match distance #{distance} exceeds decoded output " \
            "length #{output.bytesize}"
    end

    ml = seq.match_length
    src_start = output.bytesize - distance
    ml.times { |i| output << output.getbyte(src_start + (i % distance)) }
  end

  output << literals.byteslice(lit_pos..) if lit_pos < literals.bytesize
  output.byteslice(block_start..)
end

#reset ⇒ Object

Reset to the frame defaults [1, 4, 8].



257
258
259
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 257

def reset
  @repeat_offsets = DEFAULT_REPEAT_OFFSETS.dup
end

#resolve_offset(of_e, ll0, bs) ⇒ Integer

Resolve a sequence offset (C reference semantics).

Offset codes 0 and 1 address the repeat slots; the exact behaviour depends on ll0 (whether the sequence emits no literals). Codes >= 2 carry a real distance: distance = OF_BASE + read(code bits).

rubocop:disable Metrics/AbcSize

Parameters:

  • of_e (FSE::State) —

    offset table entry for this sequence

  • ll0 (Boolean) —

    literal length is zero

  • bs (FSE::BitStream)

Returns:

  • (Integer) —

    resolved byte distance



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
304
305
306
307
308
309
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 273

def resolve_offset(of_e, ll0, bs)
  of_bits = of_e.nb_add_bits
  prev = @repeat_offsets

  if of_bits > 1
    offset = of_e.base_val + bs.read_bits(of_bits)
    prev[2] = prev[1]
    prev[1] = prev[0]
    prev[0] = offset
    offset
  elsif of_bits.zero?
    offset = prev[ll0 ? 1 : 0]
    if ll0
      prev[1] = prev[0]
      prev[0] = offset
    end
    # rubocop:enable Metrics/AbcSize
    offset
  else
    # of_bits == 1: the "rep3-1" special family.
    selector = of_e.base_val + (ll0 ? 1 : 0) + bs.read_bits(1)
    temp = case selector
           when 1 then prev[1]
           when 3 then prev[0] - 1
           else prev[2]
           end
    if temp.zero?
      raise Omnizip::DecompressionError,
            "repeat offset 1 - 1 evaluated to 0 (corrupt stream)"
    end

    prev[2] = prev[1] unless selector == 1
    prev[1] = prev[0]
    prev[0] = temp
    temp
  end
end