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 §4.1): count normalization, NCount writing, CTable construction, and 2-state interleaved bitstream encoding. Mirrors the C reference FSE library.

Defined Under Namespace

Classes: BitCStream, CState, SymbolTT

Constant Summary collapse

RTB_TABLE = 
[0, 473_195, 504_333, 520_860, 550_000, 700_000,
750_000, 830_000].freeze
NOT_YET_ASSIGNED = 
-2

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

Returns a new instance of Encoder.



241
242
243
244
245
246
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 241

def initialize(distribution, table_log, max_symbol_value)
  @distribution = distribution
  @table_log = table_log
  @max_symbol_value = max_symbol_value
  build_encoding_tables
end

Instance Attribute Details

#distribution ⇒ Array<Integer> (readonly)

Returns normalized distribution.

Returns:

  • (Array<Integer>) —

    normalized distribution



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

def distribution
  @distribution
end

#max_symbol_value ⇒ Integer (readonly)

Returns:

  • (Integer) 


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

def max_symbol_value
  @max_symbol_value
end

#state_table ⇒ Array<Integer> (readonly)

Returns state transition table.

Returns:

  • (Array<Integer>) —

    state transition table



388
389
390
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 388

def state_table
  @state_table
end

#symbol_tt ⇒ Array<SymbolTT> (readonly)

Returns:



391
392
393
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 391

def symbol_tt
  @symbol_tt
end

#table_log ⇒ Integer (readonly)

Returns:

  • (Integer) 


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

def table_log
  @table_log
end

Class Method Details

.build_from_symbols(symbols, max_symbol_value, max_table_log = FSE_DEFAULT_TABLELOG) ⇒ Encoder?

Build from raw symbols: normalize + store.

Parameters:

  • symbols (Array<Integer>)
  • max_symbol_value (Integer)
  • max_table_log (Integer) (defaults to: FSE_DEFAULT_TABLELOG)

Returns:

  • (Encoder, nil) —

    nil for an RLE stream (single symbol)



224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 224

def self.build_from_symbols(symbols, max_symbol_value,
                            max_table_log = FSE_DEFAULT_TABLELOG)
  counts = Array.new(max_symbol_value + 1, 0)
  symbols.each { |s| counts[s] += 1 }
  total = symbols.length

  actual_max = max_symbol_value
  actual_max -= 1 while actual_max.positive? && counts[actual_max].zero?

  table_log = optimal_table_log(max_table_log, total, actual_max)
  norm = normalize_count(table_log, counts, total, actual_max,
                         use_low_prob: true)
  return nil if norm.empty?

  new(norm, table_log, actual_max)
end

.normalize_count(table_log, count, total, max_symbol_value, use_low_prob: true) ⇒ Array<Integer>

Normalize a raw histogram to sum to (1 << table_log).

Parameters:

  • table_log (Integer)
  • count (Array<Integer>) —

    raw frequencies

  • total (Integer) —

    sum(count)

  • max_symbol_value (Integer) —

    highest symbol index

  • use_low_prob (Boolean) (defaults to: true) —

    emit -1 sentinels for rare symbols (the zstd default)

Returns:

  • (Array<Integer>) —

    normalized distribution, or [] for an RLE stream



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

def self.normalize_count(table_log, count, total, max_symbol_value,
                         use_low_prob: true)
  table_log = FSE_DEFAULT_TABLELOG if table_log.zero?

  norm = Array.new(max_symbol_value + 1, 0)

  # RLE: a single symbol accounts for everything.
  (0..max_symbol_value).each do |s|
    return [] if count[s] == total
  end

  low_prob_count = use_low_prob ? -1 : 1
  scale = 62 - table_log
  step = (1 << 62) / total
  v_step = 1 << (scale - 20)
  still_to_distribute = 1 << table_log
  low_threshold = total >> table_log
  largest = 0
  largest_p = 0

  (0..max_symbol_value).each do |s|
    if count[s].zero?
      norm[s] = 0
      next
    end

    c64 = count[s]
    if c64 <= low_threshold
      norm[s] = low_prob_count
      still_to_distribute -= 1
    else
      proba = (c64 * step) >> scale
      if proba < 8
        rest_to_beat = v_step * RTB_TABLE[proba]
        diff = (c64 * step) - (proba << scale)
        proba += 1 if diff > rest_to_beat
      end
      if proba > largest_p
        largest_p = proba
        largest = s
      end
      norm[s] = proba
      still_to_distribute -= proba
    end
  end

  if -still_to_distribute >= norm[largest] / 2
    normalize_m2(norm, table_log, count, total, max_symbol_value,
                 low_prob_count)
  else
    norm[largest] += still_to_distribute
  end

  norm
end

.normalize_m2(norm, table_log, count, total, max_symbol_value, low_prob_count) ⇒ Object

Secondary normalization (C FSE_normalizeM2), used when the primary method's largest-symbol correction would be too big. rubocop:disable Metrics/MethodLength rubocop:disable-next Metrics/AbcSize



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
144
145
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 118

def self.normalize_m2(norm, table_log, count, total, max_symbol_value,
                      low_prob_count)
  table_size = 1 << table_log
  low_threshold = total >> table_log
  low_one = (total * 3) >> (table_log + 1)
  distributed = 0
  remaining = total

  (0..max_symbol_value).each do |s|
    if count[s].zero?
      norm[s] = 0
    elsif count[s] <= low_threshold
      norm[s] = low_prob_count
      distributed += 1
      remaining -= count[s]
    elsif count[s] <= low_one
      norm[s] = 1
      distributed += 1
      remaining -= count[s]
    else
      norm[s] = NOT_YET_ASSIGNED
    end
  end

  to_distribute = table_size - distributed
  return if to_distribute.zero?

  if remaining / to_distribute > low_one
    low_one = (remaining * 3) / (to_distribute * 2)
    (0..max_symbol_value).each do |s|
      if norm[s] == NOT_YET_ASSIGNED && count[s] <= low_one
        norm[s] = 1
        distributed += 1
        remaining -= count[s]
      end
    end
    to_distribute = table_size - distributed
  end

  if distributed == max_symbol_value + 1
    max_v = 0
    max_c = 0
    (0..max_symbol_value).each do |s|
      if count[s] > max_c
        max_v = s
        max_c = count[s]
      end
    end
    norm[max_v] += to_distribute
    return
  end

  if remaining.zero?
    idx = 0
    while to_distribute.positive? && idx <= max_symbol_value
      if norm[idx]&.positive?
        norm[idx] += 1
        to_distribute -= 1
      end
      idx = (idx + 1) % (max_symbol_value + 1)
    end
    return
  end

  v_step_log = 62 - table_log
  mid = (1 << (v_step_log - 1)) - 1
  r_step = (((1 << v_step_log) * to_distribute) + mid) / remaining
  tmp_total = mid
  (0..max_symbol_value).each do |s|
    next unless norm[s] == NOT_YET_ASSIGNED

    end_v = tmp_total + (count[s] * r_step)
    weight = (end_v >> v_step_log) - (tmp_total >> v_step_log)
    norm[s] = weight
    tmp_total = end_v
  end
end

.optimal_table_log(max_table_log, src_size, max_symbol_value) ⇒ Object

Choose an accuracy log for the given source size and alphabet.

Direct port of C FSE_optimalTableLog; the branch ladder is inherent to the algorithm. rubocop:disable-next Metrics/AbcSize



202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 202

def self.optimal_table_log(max_table_log, src_size, max_symbol_value)
  return FSE_MIN_ACCURACY_LOG if src_size <= 1

  max_bits_src = (src_size - 1).bit_length - 1 - 2
  max_bits_src = 0 if max_bits_src.negative?
  min_bits_src = src_size.bit_length + 1
  min_bits_sym = [max_symbol_value, 1].max.bit_length + 2
  min_bits = [min_bits_src, min_bits_sym].min

  table_log = max_table_log
  table_log = FSE_DEFAULT_TABLELOG if table_log.zero?
  table_log = max_bits_src if max_bits_src < table_log
  table_log = min_bits if min_bits > table_log
  table_log.clamp(FSE_MIN_ACCURACY_LOG, FSE_MAX_ACCURACY_LOG)
end

Instance Method Details

#compress(symbols) ⇒ String

Serialize table description + bitstream for symbols.

Returns:

  • (String) 


383
384
385
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 383

def compress(symbols)
  write_ncount + compress_symbols(symbols)
end

#compress_symbols(symbols) ⇒ String

Encode symbols into a 2-state interleaved reverse bitstream (C FSE_compress_usingCTable).

Direct port of C FSE_compress_usingCTable. rubocop:disable Metrics/AbcSize

Parameters:

  • symbols (Array<Integer>)

Returns:

  • (String) —

    bitstream bytes ending with the 1-bit mark



344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 344

def compress_symbols(symbols)
  return "" if symbols.length <= 2

  bitc = BitCStream.new
  ip = symbols.length

  ip -= 1
  if symbols.length.odd?
    s1 = CState.init2(self, symbols[ip])
    ip -= 1
    s2 = CState.init2(self, symbols[ip])
    ip -= 1
    s1.encode(bitc, self, symbols[ip])
    bitc.flush
  else
    s2 = CState.init2(self, symbols[ip])
    ip -= 1
    s1 = CState.init2(self, symbols[ip])
  end
  # rubocop:enable Metrics/AbcSize

  while ip.positive?
    ip -= 1
    s2.encode(bitc, self, symbols[ip])
    break if ip.zero?

    ip -= 1
    s1.encode(bitc, self, symbols[ip])
    bitc.flush
  end

  s2.flush(bitc)
  s1.flush(bitc)
  bitc.close
end

#write_ncount ⇒ String

Serialize the table description (NCount) per RFC 8878 §4.1.1.

rubocop:disable Metrics/MethodLength rubocop:disable-next Metrics/AbcSize

Returns:

  • (String) 


253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
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
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
 
# File 'lib/omnizip/algorithms/zstandard/fse/encoder.rb', line 253

def write_ncount
  out = []
  table_size = 1 << @table_log
  bit_stream = 0
  bit_count = 0
  symbol = 0
  alphabet_size = @max_symbol_value + 1
  previous_is_zero = false
  remaining = table_size + 1
  threshold = table_size
  nb_bits = @table_log + 1

  bit_stream |= (@table_log - FSE_MIN_ACCURACY_LOG) << bit_count
  bit_count += 4

  while symbol < alphabet_size && remaining > 1
    if previous_is_zero
      start = symbol
      symbol += 1 while symbol < alphabet_size &&
          @distribution[symbol].zero?
      if symbol == alphabet_size
        raise Omnizip::CompressionError, "bad FSE distribution"
      end

      while symbol >= start + 24
        start += 24
        bit_stream |= 0xFFFF << bit_count
        out.push(bit_stream & 0xFF, (bit_stream >> 8) & 0xFF)
        bit_stream >>= 16
      end
      while symbol >= start + 3
        start += 3
        bit_stream |= 3 << bit_count
        bit_count += 2
      end
      bit_stream |= (symbol - start) << bit_count
      bit_count += 2
      if bit_count > 16
        out.push(bit_stream & 0xFF, (bit_stream >> 8) & 0xFF)
        bit_stream >>= 16
        bit_count -= 16
      end
    end

    count = @distribution[symbol]
    symbol += 1
    max = ((2 * threshold) - 1) - remaining
    remaining -= count.negative? ? -count : count
    count_val = count + 1
    count_val += max if count_val >= threshold

    bit_stream |= count_val << bit_count
    bit_count += nb_bits
    bit_count -= 1 if count_val < max

    previous_is_zero = count_val == 1
    raise Omnizip::CompressionError, "FSE NCount remaining < 1" if remaining < 1

    while remaining < threshold
      nb_bits -= 1
      threshold >>= 1
    end

    if bit_count > 16
      out.push(bit_stream & 0xFF, (bit_stream >> 8) & 0xFF)
      bit_stream >>= 16
      bit_count -= 16
    end
  end

  unless remaining == 1
    raise Omnizip::CompressionError,
          "FSE NCount remaining != 1 (#{remaining})"
  end

  if bit_count.positive?
    n_bytes = (bit_count + 7) / 8
    out.push(*Array.new(n_bytes) { |i| (bit_stream >> (8 * i)) & 0xFF })
  end

  out.pack("C*")
end