Class: Omnizip::Algorithms::Zstandard::FSE::Table

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

Overview

FSE decoding table built from a normalized distribution (RFC 8878 §4.1, "From normalized distribution to decoding tables"; mirrors the C reference FSE_buildDTable).

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(states, accuracy_log, symbol_count) ⇒ Table

Returns a new instance of Table.



131
132
133
134
135
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 131

def initialize(states, accuracy_log, symbol_count)
  @states = states
  @accuracy_log = accuracy_log
  @symbol_count = symbol_count
end

Instance Attribute Details

#accuracy_log ⇒ Integer (readonly)

Returns log2 of the table size.

Returns:

  • (Integer) —

    log2 of the table size



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

def accuracy_log
  @accuracy_log
end

#states ⇒ Array<State> (readonly)

Returns:



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

def states
  @states
end

#symbol_count ⇒ Integer (readonly)

Returns number of symbols in the source alphabet.

Returns:

  • (Integer) —

    number of symbols in the source alphabet



48
49
50
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 48

def symbol_count
  @symbol_count
end

Class Method Details

.build(distribution, accuracy_log) ⇒ Table

Build a table from a distribution.

Parameters:

  • distribution (Array<Integer>) —

    normalized counts; positive = cell count, -1 = "less than 1" low-probability symbol (one cell at the top of the table), 0 = absent

  • accuracy_log (Integer)

Returns:



57
58
59
60
61
62
63
64
65
66
67
68
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 57

def self.build(distribution, accuracy_log)
  table_size = 1 << accuracy_log
  step = (table_size >> 1) + (table_size >> 3) + 3
  mask = table_size - 1

  # Phase 1a: low-probability (-1) symbols occupy single cells
  # from the top of the table downward.
  table_symbol = Array.new(table_size, 0xFFFF)
  high_threshold = table_size - 1
  distribution.each_with_index do |freq, symbol|
    next unless freq == -1

    table_symbol[high_threshold] = symbol
    if high_threshold.zero?
      raise Omnizip::DecompressionError,
            "FSE table overflow placing low-probability symbol"
    end

    high_threshold -= 1
  end

  # Phase 1b: spread positive-count symbols from position 0,
  # skipping the reserved low-probability area.
  position = 0
  distribution.each_with_index do |freq, symbol|
    next unless freq.positive?

    freq.times do
      table_symbol[position] = symbol
      position = (position + step) & mask
      position = (position + step) & mask while position > high_threshold
    end
  end

  # Phase 2: symbolNext starts at 1 for -1/1 counts, at the
  # count itself otherwise.
  symbol_next = Array.new(distribution.length, 0)
  singular = [-1, 1].freeze
  distribution.each_with_index do |freq, symbol|
    next if freq.zero?

    symbol_next[symbol] = singular.include?(freq) ? 1 : freq
  end

  # Phase 3: per-cell transition rules.
  states = table_symbol.map do |symbol|
    next_state = symbol_next[symbol]
    symbol_next[symbol] += 1
    nb_bits = accuracy_log - Constants.highbit32(next_state)
    baseline = (next_state << nb_bits) - table_size
    State.new(symbol, nb_bits, baseline)
  end

  new(states, accuracy_log, distribution.length)
end

.build_predefined(distribution, accuracy_log) ⇒ Table

Build from an RFC 8878 §4.1.3 predefined distribution.

Parameters:

  • distribution (Array<Integer>)
  • accuracy_log (Integer)

Returns:



118
119
120
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 118

def self.build_predefined(distribution, accuracy_log)
  build(distribution, accuracy_log)
end

.build_rle(symbol, accuracy_log) ⇒ Table

Single-symbol RLE table: every state decodes symbol with a full state reset.

Returns:



126
127
128
129
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 126

def self.build_rle(symbol, accuracy_log)
  new(Array.new(1 << accuracy_log) { State.new(symbol, 0, 0) },
      accuracy_log, 1)
end

Instance Method Details

#[](index) ⇒ State

Returns:



138
139
140
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 138

def [](index)
  @states[index]
end

#size ⇒ Integer

Returns:

  • (Integer) 


143
144
145
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 143

def size
  @states.length
end