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 (RFC 8878 Section 4.1)

Builds a decoding table from a probability distribution according to RFC 8878.

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_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::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::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

Constructor Details

#initialize(states, accuracy_log, symbol_count) ⇒ Table

Initialize with pre-built table

Parameters:

  • states (Array<State>) —

    Decoding states

  • accuracy_log (Integer)
  • symbol_count (Integer) 


82
83
84
85
86
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 82

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 Accuracy log (table size = 2^accuracy_log).

Returns:

  • (Integer) —

    Accuracy log (table size = 2^accuracy_log)



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

def accuracy_log
  @accuracy_log
end

#states ⇒ Array<State> (readonly)

Returns Decoding table entries.

Returns:

  • (Array<State>) —

    Decoding table entries



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

def states
  @states
end

#symbol_count ⇒ Integer (readonly)

Returns Number of symbols in the table.

Returns:

  • (Integer) —

    Number of symbols in the table



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

def symbol_count
  @symbol_count
end

Class Method Details

.allocate_cells(distribution, table_size) ⇒ Object

Allocate cells using FSE spread pattern

The spread pattern distributes symbols across the table using a step that ensures good distribution.



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 107

def self.allocate_cells(distribution, table_size)
  cells = Array.new(table_size, nil)

  # Validate distribution sum
  total = distribution.compact.sum
  if total > table_size
    raise ArgumentError,
          "Distribution sum (#{total}) exceeds table size (#{table_size})"
  end

  # Step = (table_size >> 1) + (table_size >> 3) + 3
  step = (table_size >> 1) + (table_size >> 3) + 3
  mask = table_size - 1

  position = 0

  distribution.each_with_index do |prob, symbol|
    next if prob.nil? || prob <= 0

    prob.times do
      # Find empty position (with safety limit)
      attempts = 0
      while cells[position]
        position = (position + step) & mask
        attempts += 1
        if attempts > table_size
          raise "FSE table allocation failed: no empty cell found"
        end
      end

      cells[position] = symbol
      position = (position + step) & mask
    end
  end

  cells
end

.build(distribution, accuracy_log) ⇒ Table

Build FSE table from normalized distribution

Parameters:

  • distribution (Array<Integer>) —

    Normalized symbol frequencies

  • accuracy_log (Integer) —

    Log2 of table size

Returns:

  • (Table) —

    Built FSE table



56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 56

def self.build(distribution, accuracy_log)
  table_size = 1 << accuracy_log

  # Allocate cells using spread pattern
  cells = allocate_cells(distribution, table_size)

  # Calculate num_bits and baseline for each state
  states = calculate_state_values(cells, distribution, table_size)

  new(states, accuracy_log, distribution.length)
end

.build_predefined(distribution, accuracy_log) ⇒ Table

Build from predefined distribution

Parameters:

  • distribution (Array<Integer>) —

    Predefined distribution

  • accuracy_log (Integer) —

    Accuracy log

Returns:



73
74
75
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 73

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

.calculate_num_bits(prob, table_size) ⇒ Object

Calculate number of bits needed for a symbol with given probability



178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 178

def self.calculate_num_bits(prob, table_size)
  return 0 if prob <= 0

  # num_bits = accuracy_log - log2(prob)
  # This is the number of extra bits needed
  log_prob = 0
  temp = prob
  while temp > 1
    log_prob += 1
    temp >>= 1
  end

  log_table = 0
  temp = table_size
  while temp > 1
    log_table += 1
    temp >>= 1
  end

  [0, log_table - log_prob].max
end

.calculate_state_values(cells, distribution, table_size) ⇒ Object

Calculate num_bits and baseline for each state



146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 146

def self.calculate_state_values(cells, distribution, table_size)
  states = Array.new(table_size)

  # Group positions by symbol
  symbol_positions = {}
  cells.each_with_index do |symbol, pos|
    next if symbol.nil?

    symbol_positions[symbol] ||= []
    symbol_positions[symbol] << pos
  end

  # Calculate state values for each symbol
  symbol_positions.each do |symbol, positions|
    prob = distribution[symbol]
    next if prob.nil? || prob <= 0

    positions.each_with_index do |pos, idx|
      # Calculate num_bits: -log2(prob/table_size)
      num_bits = calculate_num_bits(prob, table_size)

      # Calculate baseline
      baseline = idx

      states[pos] = State.new(symbol, num_bits, baseline)
    end
  end

  states
end

Instance Method Details

#[](index) ⇒ State

Get state at index

Parameters:

  • index (Integer) —

    State index

Returns:

  • (State) —

    State at index



92
93
94
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 92

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

#size ⇒ Integer

Get table size

Returns:

  • (Integer) —

    Number of entries in table



99
100
101
 
# File 'lib/omnizip/algorithms/zstandard/fse/table.rb', line 99

def size
  @states.length
end