Class: Omnizip::Algorithms::Zstandard::SequencesDecoder

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

Overview

Sequences section decoder (RFC 8878 §3.1.1.3.2) and the LZ77 executor (§3.1.2).

Decoding follows the C reference ZSTD_decodeSequence:

  • State initialization order: LL, OF, ML.
  • Per sequence: resolve the offset first (reading its extra bits and updating the repeat-offset slots), then read the ML extra bits, then the LL extra bits.
  • State updates (non-last sequences) in order LL, ML, OF.

Defined Under Namespace

Classes: Sequence

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(input, previous_tables, executor) ⇒ SequencesDecoder

Returns a new instance of SequencesDecoder.



59
60
61
62
63
64
65
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 59

def initialize(input, previous_tables, executor)
  @input = input
  @previous_tables = previous_tables
  @executor = executor
  @sequences = []
  @fse_tables = {}
end

Instance Attribute Details

#fse_tables ⇒ Hash (readonly)

Returns FSE tables for the next block's Repeat mode.

Returns:

  • (Hash) —

    FSE tables for the next block's Repeat mode



45
46
47
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 45

def fse_tables
  @fse_tables
end

#sequences ⇒ Array<Sequence> (readonly)

Returns:



42
43
44
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 42

def sequences
  @sequences
end

Class Method Details

.decode(input, previous_tables = {}, executor = nil) ⇒ SequencesDecoder

Decode the sequences section at the head of input.

Parameters:

  • input (String)
  • previous_tables (Hash) (defaults to: {}) —

    tables carried from the previous compressed block (:ll, :ml, :of entries)

  • executor (SequenceExecutor) (defaults to: nil) —

    repeat-offset state, updated in place while decoding

Returns:



55
56
57
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 55

def self.decode(input, previous_tables = {}, executor = nil)
  new(input, previous_tables, executor || SequenceExecutor.new).decode_section
end

Instance Method Details

#decode_section ⇒ Object

rubocop:disable Metrics/MethodLength rubocop:disable Metrics/AbcSize



69
70
71
72
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
 
# File 'lib/omnizip/algorithms/zstandard/sequences.rb', line 69

def decode_section
  num_sequences, offset = read_sequence_count
  return self if num_sequences.zero?

  if @input.bytesize <= offset
    raise Omnizip::DecompressionError,
          "truncated sequences section: missing modes byte"
  end
  # rubocop:enable Metrics/AbcSize

  modes = @input.getbyte(offset)
  ll_mode = (modes >> 6) & 0x03
  of_mode = (modes >> 4) & 0x03
  ml_mode = (modes >> 2) & 0x03

  cursor = offset + 1
  @ll_table, cursor = build_table(ll_mode, :ll,
                                  PREDEFINED_LL_DISTRIBUTION,
                                  LITERALS_LENGTH_ACCURACY_LOG, cursor)
  @of_table, cursor = build_table(of_mode, :of,
                                  PREDEFINED_OFFSET_DISTRIBUTION,
                                  OFFSET_ACCURACY_LOG, cursor)
  @ml_table, cursor = build_table(ml_mode, :ml,
                                  PREDEFINED_ML_DISTRIBUTION,
                                  MATCH_LENGTH_ACCURACY_LOG, cursor)

  decode_sequences(num_sequences, @input.byteslice(cursor..))
  self
end