Class: Omnizip::Algorithms::Zstandard::FSE::Encoder

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

Overview

FSE Encoder (RFC 8878 Section 4.1)

Encodes symbols using Finite State Entropy coding. FSE is a variant of arithmetic coding that uses table-based state transitions.

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(distribution, accuracy_log) ⇒ Encoder

Initialize FSE encoder

Parameters:

  • distribution (Array<Integer>) —

    Normalized symbol distribution

  • accuracy_log (Integer) —

    Accuracy log



144
145
146
147
148
149
150
151
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 144

def initialize(distribution, accuracy_log)
  @distribution = distribution
  @accuracy_log = accuracy_log
  @table_size = 1 << accuracy_log

  # Build encoding tables
  build_encoding_tables
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)



38
39
40
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 38

def accuracy_log
  @accuracy_log
end

#distribution ⇒ Array<Integer> (readonly)

Returns Symbol distribution (normalized frequencies).

Returns:

  • (Array<Integer>) —

    Symbol distribution (normalized frequencies)



35
36
37
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 35

def distribution
  @distribution
end

#table_size ⇒ Integer (readonly)

Returns Table size.

Returns:

  • (Integer) —

    Table size



41
42
43
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 41

def table_size
  @table_size
end

Class Method Details

.adjust_distribution(distribution, delta) ⇒ Object

Adjust distribution to sum to exactly table_size



120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 120

def self.adjust_distribution(distribution, delta)
  return if delta.zero?

  if delta.positive?
    # Need to add: increment largest probabilities
    delta.times do
      max_idx = distribution.each_with_index.max_by { |v, _| v }&.last
      distribution[max_idx] += 1 if max_idx
    end
  else
    # Need to subtract: decrement smallest non-zero probabilities
    (-delta).times do
      min_idx = distribution.each_with_index.select do |v, _|
        v > 1
      end.min_by { |v, _| v }&.last
      distribution[min_idx] -= 1 if min_idx
    end
  end
end

.build_from_frequencies(frequencies, max_accuracy_log = FSE_MAX_ACCURACY_LOG) ⇒ Encoder

Build FSE encoder from symbol frequencies

Parameters:

  • frequencies (Array<Integer>) —

    Raw symbol frequencies

  • max_accuracy_log (Integer) (defaults to: FSE_MAX_ACCURACY_LOG) —

    Maximum accuracy log (default 9)

Returns:



48
49
50
51
52
53
54
55
56
57
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 48

def self.build_from_frequencies(frequencies,
max_accuracy_log = FSE_MAX_ACCURACY_LOG)
  return nil if frequencies.nil? || frequencies.empty?

  # Normalize frequencies to table size
  distribution, accuracy_log = normalize_distribution(frequencies,
                                                      max_accuracy_log)

  new(distribution, accuracy_log)
end

.calculate_min_accuracy_log(num_symbols) ⇒ Object

Calculate minimum accuracy log for given number of symbols



93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 93

def self.calculate_min_accuracy_log(num_symbols)
  return 0 if num_symbols <= 1

  log = 0
  temp = num_symbols - 1
  while temp.positive?
    log += 1
    temp >>= 1
  end
  log
end

.normalize_distribution(frequencies, max_accuracy_log) ⇒ Array<Array<Integer>, Integer>

Normalize frequency distribution

Converts raw frequencies to normalized distribution that sums to 2^accuracy_log.

Parameters:

  • frequencies (Array<Integer>) —

    Raw frequencies

  • max_accuracy_log (Integer) —

    Maximum accuracy log

Returns:

  • (Array<Array<Integer>, Integer>) —

    Normalized distribution and accuracy log



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
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 66

def self.normalize_distribution(frequencies, max_accuracy_log)
  # Count non-zero symbols
  total_freq = frequencies.sum
  return [[], 0] if total_freq.zero?

  # Find minimum accuracy log that fits the distribution
  num_symbols = frequencies.count { |f| f&.positive? }
  accuracy_log = [calculate_min_accuracy_log(num_symbols),
                  FSE_MIN_ACCURACY_LOG].max
  accuracy_log = [accuracy_log, max_accuracy_log].min

  table_size = 1 << accuracy_log

  # Normalize frequencies to table size
  distribution = normalize_frequencies(frequencies, table_size)

  # Verify distribution sums to table size
  sum = distribution.sum
  if sum != table_size
    # Adjust to make it sum correctly
    adjust_distribution(distribution, table_size - sum)
  end

  [distribution, accuracy_log]
end

.normalize_frequencies(frequencies, table_size) ⇒ Object

Normalize frequencies to fit table size



106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 106

def self.normalize_frequencies(frequencies, table_size)
  total = frequencies.sum
  return Array.new(frequencies.length, 0) if total.zero?

  # Scale frequencies
  frequencies.map do |freq|
    next 0 if freq.nil? || freq <= 0

    normalized = ((freq * table_size) + (total / 2)) / total
    [normalized, 1].max # Minimum 1 for non-zero symbols
  end
end

Instance Method Details

#encode(symbols) ⇒ String

Encode symbols to bitstream

Parameters:

  • symbols (Array<Integer>) —

    Symbols to encode

Returns:

  • (String) —

    Encoded bitstream



157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 157

def encode(symbols)
  return "" if symbols.nil? || symbols.empty?

  # Initialize state from last symbol (reverse order encoding)
  bitstream = []

  # Encode in reverse order
  state = @table_size - 1 # Initial state

  symbols.reverse_each.with_index do |symbol, _idx|
    entry = @symbol_to_state[symbol]
    next unless entry

    # Find state for this symbol
    state = find_state_for_symbol(symbol, state)

    # Output bits for state transition
    num_bits = entry[:num_bits]
    if num_bits.positive?
      # Write lower num_bits of state
      mask = (1 << num_bits) - 1
      bits_to_write = state & mask
      write_bits(bitstream, bits_to_write, num_bits)
      state >>= num_bits
    end
  end

  # Write final state
  write_bits(bitstream, state, @accuracy_log)

  # Convert bit array to bytes (in reverse for FSE)
  bits_to_bytes(bitstream.reverse)
end

#symbol_count ⇒ Integer

Get number of symbols in distribution

Returns:

  • (Integer) 


194
195
196
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 194

def symbol_count
  @distribution.length
end