Module: Omnizip::Algorithms::Zstandard::MatchFinder

Includes:
Constants
Defined in:
lib/omnizip/algorithms/zstandard/match_finder.rb

Overview

LZ77 match finder for Zstandard (port of the omnizip-rs encoder/match_finder.rs, itself from zstd_compress_lazy / zstd_fast in the C reference).

Uses a 4-byte multiplicative hash table with optional hash-chain walking, over ABSOLUTE positions of the whole input so matches can reference earlier blocks (window permitting). Parsers: greedy (no look-ahead), lazy (1-step), lazy2 (2-step).

Defined Under Namespace

Classes: MatchState, RawSequence, SeqStore

Constant Summary collapse

PRIME4_BYTES = 
2_654_435_761
MIN_MATCH = 
4
MIN_MATCH_ECONOMICAL =

Matches shorter than this cost more to encode than the literals they replace under a greedy/lazy parse (measured in the Rust port: min_match 3 regressed ~20% vs 5).

5
REP_NUM = 
3

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

Class Method Summary collapse

Methods included from Constants

highbit32

Class Method Details

.backward_extension(src, ip, anchor, candidate) ⇒ Object

Bytes before ip (and before the match candidate) that extend the match backward, bounded by the pending literal run so the previous sequence is never overlapped.



326
327
328
329
330
331
332
333
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 326

def backward_extension(src, ip, anchor, candidate)
  back = 0
  while ip > anchor + back && candidate > back &&
      src.getbyte(ip - 1 - back) == src.getbyte(candidate - 1 - back)
    back += 1
  end
  back
end

.compress_range(src, block_start, block_end, seq_store, ms, min_match, lazy, ldm = nil, max_distance = BLOCK_MAX_SIZE) ⇒ void

This method returns an undefined value.

Run the parser over src. Positions are absolute; the hash table persists across calls so cross-block references are found.

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

Parameters:

  • lazy (Integer) —

    0 = greedy, 1 or 2 = look-ahead steps



195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 195

def compress_range(src, block_start, block_end, seq_store, ms,
                   min_match, lazy, ldm = nil,
                   max_distance = BLOCK_MAX_SIZE)
  mm = [min_match, MIN_MATCH_ECONOMICAL].max
  span = block_end - block_start
  if span < mm + 1
    seq_store.literals << src.byteslice(block_start, span)
    return
  end

  ms.hash_log
  anchor = block_start
  ip = block_start.positive? ? block_start : 1
  limit = block_end - mm

  while ip < limit
    match = if ldm || lazy.positive?
              # Lazy levels share the LDM loop's rep0 fast-path
              # (with backward extension): without it, levels
              # 6+ measured worse than the greedy default level
              # because every rep-offset match paid full offset
              # coding.
              find_match_ldm(src, ip, ms, mm, limit, anchor,
                             seq_store.rep_offsets[0], ldm,
                             max_distance)
            else
              find_greedy_match(src, ip, ms, mm, limit, anchor,
                                seq_store.rep_offsets[0])
            end
    if match
      dist, len = match
      defer = false
      if lazy.positive?
        (1..lazy).each do |k|
          next unless ip + k < limit

          m2 = if ldm
                 probe_match(src, ip + k, ms, mm, limit, ldm,
                             max_distance)
               else
                 probe_match(src, ip + k, ms, mm, limit)
               end
          if m2 && m2[1] > len + k
            defer = true
            break
          end
        end
      end

      if defer
        ip += 1
        next
      end

      ip = match[2] if match.length == 3
      seq_store.literals << src.byteslice(anchor, ip - anchor)
      seq_store.sequences <<
        RawSequence.new(ip - anchor, len, dist)
      rotate_reps(seq_store.rep_offsets, dist)
      insert_range(ms, src, ip, len)
      ip += len
      anchor = ip
    else
      ip += 1
    end
  end

  return unless anchor < block_end

  seq_store.literals << src.byteslice(anchor, block_end - anchor)
end

.count_match(a, a_pos, b, b_pos, limit) ⇒ Object

Count matching bytes between two positions, 8 bytes at a time (C ZSTD_count).



163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 163

def count_match(a, a_pos, b, b_pos, limit)
  len = 0
  a_size = a.bytesize
  b_size = b.bytesize
  while len + 8 <= limit && a_pos + len + 8 <= a_size &&
      b_pos + len + 8 <= b_size
    wa = read8(a, a_pos + len)
    wb = read8(b, b_pos + len)
    if wa == wb
      len += 8
    else
      diff = wa ^ wb
      return len + (((diff & -diff).bit_length - 1) / 8)
    end
  end
  while len < limit && a_pos + len < a_size && b_pos + len < b_size &&
      a.getbyte(a_pos + len) == b.getbyte(b_pos + len)
    len += 1
  end
  len
end

.find_best_match(src, ip, ms, min_match, limit, ldm = nil, max_distance = BLOCK_MAX_SIZE) ⇒ Object

Find the best match at ip (single probe, or a chain walk when enabled). Updates the hash table. Returns [distance, length] or nil.

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



342
343
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
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 342

def find_best_match(src, ip, ms, min_match, limit, ldm = nil,
                    max_distance = BLOCK_MAX_SIZE)
  size = src.bytesize
  return nil if ip + MIN_MATCH > size

  h = hash4(src, ip, ms.hash_log)
  candidate = ms.hash_table[h]
  if ms.max_chain.positive? && !ms.chain.empty? && (ip < ms.chain.length)
    ms.chain[ip] = candidate
  end
  ms.hash_table[h] = ip

  max_extend = limit + MIN_MATCH_ECONOMICAL - ip
  best_len = 0
  best_dist = 0
  walks = [ms.max_chain, 1].max

  walks.times do
    break if candidate.zero? || candidate >= ip

    dist = ip - candidate
    break if dist >= max_distance
    break if candidate + MIN_MATCH > size

    if read4(src, ip) == read4(src, candidate)
      m_len = MIN_MATCH + count_match(src, ip + MIN_MATCH,
                                      src, candidate + MIN_MATCH,
                                      [max_extend - MIN_MATCH, 0].max)
      if m_len > best_len
        best_len = m_len
        best_dist = dist
        break if best_len >= max_extend
      end
    end

    break if ms.max_chain.zero? || ms.chain.empty? || candidate >= ms.chain.length

    candidate = ms.chain[candidate]
  end

  if ldm
    lm = ldm.find_match(src, ip, max_distance, min_match,
                        limit + min_match)
    if lm && lm[1] > best_len
      best_len = lm[1]
      best_dist = lm[0]
    end
  end

  return nil if best_len < min_match

  [best_dist, best_len]
end

.find_greedy_match(src, ip, ms, min_match, limit, anchor, rep0) ⇒ Object

Greedy-path match search (port of the Rust compress_block_with_min_match): the rep0 fast-path first (cheapest offset to encode), then the hash table — both with backward extension into the pending literals. Returns [offset, length, start] or nil.



292
293
294
295
296
297
298
299
300
301
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 292

def find_greedy_match(src, ip, ms, min_match, limit, anchor, rep0)
  m = rep0_match(src, ip, rep0, min_match, limit, anchor)
  return m if m

  dist, len = find_best_match(src, ip, ms, min_match, limit)
  return nil unless dist

  back = backward_extension(src, ip, anchor, ip - dist)
  [dist, len + back, ip - back]
end

.find_match_ldm(src, ip, ms, min_match, limit, anchor, rep0, ldm, max_distance) ⇒ Object

LDM-mode match search (port of the Rust compress_block_lazy2_with_ldm loop body): rep0 fast-path first, then the normal hash probe merged with the LDM table. Returns [offset, length, start] or nil.



274
275
276
277
278
279
280
281
282
283
284
285
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 274

def find_match_ldm(src, ip, ms, min_match, limit, anchor, rep0,
                   ldm, max_distance)
  m = rep0_match(src, ip, rep0, min_match, limit, anchor)
  return m if m

  dist, len = find_best_match(src, ip, ms, min_match, limit,
                              ldm, max_distance)
  return nil unless dist

  back = backward_extension(src, ip, anchor, ip - dist)
  [dist, len + back, ip - back]
end

.hash4(src, pos, h_bits) ⇒ Object 



155
156
157
158
159
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 155

def hash4(src, pos, h_bits)
  v = read4(src, pos)
  # 32-bit wrapping multiply (C/uint32_t), then the high bits.
  ((v * PRIME4_BYTES) & 0xFFFFFFFF) >> (32 - h_bits)
end

.insert_range(ms, src, start, len) ⇒ Object

Insert hash entries for the start and the second-to-last position of an emitted match (C ZSTD_insertAndFindFirstIndex lazy-insert subset).

rubocop:disable-next Metrics/AbcSize



447
448
449
450
451
452
453
454
455
456
457
458
459
460
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 447

def insert_range(ms, src, start, len)
  size = src.bytesize
  if start + MIN_MATCH <= size
    h = hash4(src, start, ms.hash_log)
    ms.chain[start] = ms.hash_table[h] if start < ms.chain.length
    ms.hash_table[h] = start
  end
  pos = start + len - 2
  if pos.positive? && pos + MIN_MATCH <= size
    h = hash4(src, pos, ms.hash_log)
    ms.chain[pos] = ms.hash_table[h] if pos < ms.chain.length
    ms.hash_table[h] = pos
  end
end

.params_for_level(level, input_len) ⇒ Hash

Parameters for a compression level (a Ruby-sized adaptation of the C ZSTD_defaultCParameters table): the hash log is additionally capped by the input size so small inputs do not pay for a huge table.

Returns:

  • (Hash) —

    with :hash_log, :chain, :lazy, :min_match



113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 113

def params_for_level(level, input_len)
  level = level.clamp(1, 22)
  input_log = input_len.positive? ? input_len.bit_length - 1 : 6
  hash_log = { 1 => 12, 2 => 13, 3 => 14, 4 => 14, 5 => 14,
               6 => 14, 7 => 15, 8 => 15, 9 => 16, 10 => 16,
               11 => 16, 12 => 17 }.fetch(level, 17)
  hash_log = input_log if input_log < hash_log
  hash_log = 6 if hash_log < 6

  lazy, chain = if level <= 5
                  [0, 0]
                elsif level <= 7
                  [1, 4]
                else
                  [2, [1 << [(level - 4) / 2, 4].min, 32].min]
                end

  { hash_log: hash_log, chain: chain, lazy: lazy,
    min_match: MIN_MATCH_ECONOMICAL }
end

.probe_match(src, ip, ms, min_match, limit, ldm = nil, max_distance = BLOCK_MAX_SIZE) ⇒ Object

Read-only probe at ip without updating the hash table (used by the lazy look-ahead so deferred positions do not pollute the table early).

rubocop:disable Metrics/AbcSize rubocop:disable Metrics/CyclomaticComplexity



405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 405

def probe_match(src, ip, ms, min_match, limit, ldm = nil,
                max_distance = BLOCK_MAX_SIZE)
  size = src.bytesize
  return nil if ip + MIN_MATCH > size

  candidate = ms.hash_table[hash4(src, ip, ms.hash_log)]

  best_len = 0
  best_dist = 0
  if candidate.positive? && candidate < ip
    dist = ip - candidate
    if dist < max_distance && candidate + MIN_MATCH <= size &&
        read4(src, ip) == read4(src, candidate)
      best_len = MIN_MATCH + count_match(
        src, ip + MIN_MATCH, src, candidate + MIN_MATCH,
        [limit + MIN_MATCH_ECONOMICAL - ip - MIN_MATCH, 0].max
      )
      best_dist = dist
    end
  end

  if ldm
    lm = ldm.find_match(src, ip, max_distance, min_match,
                        limit + min_match)
    if lm && lm[1] > best_len
      best_len = lm[1]
      best_dist = lm[0]
    end
  end

  return nil if best_len < min_match

  [best_dist, best_len]
end

.read4(src, pos) ⇒ Object

Allocation-free little-endian reads; the hot loops call these millions of times, and String#byteslice + unpack1 showed up as half the encoder's time via GC pressure.



137
138
139
140
141
142
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 137

def read4(src, pos)
  src.getbyte(pos) |
    (src.getbyte(pos + 1) << 8) |
    (src.getbyte(pos + 2) << 16) |
    (src.getbyte(pos + 3) << 24)
end

.read8(src, pos) ⇒ Object 



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

def read8(src, pos)
  src.getbyte(pos) |
    (src.getbyte(pos + 1) << 8) |
    (src.getbyte(pos + 2) << 16) |
    (src.getbyte(pos + 3) << 24) |
    (src.getbyte(pos + 4) << 32) |
    (src.getbyte(pos + 5) << 40) |
    (src.getbyte(pos + 6) << 48) |
    (src.getbyte(pos + 7) << 56)
end

.rep0_match(src, ip, rep0, min_match, limit, anchor) ⇒ Object

Match at distance rep0 (the decoder's most recent offset) with forward and backward extension. [rep0, length, start] or nil.

rubocop:disable-next Metrics/AbcSize



308
309
310
311
312
313
314
315
316
317
318
319
320
321
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 308

def rep0_match(src, ip, rep0, min_match, limit, anchor)
  return nil if rep0 <= 0 || ip <= rep0
  return nil if read4(src, ip) != read4(src, ip - rep0)

  m_len = MIN_MATCH + count_match(
    src, ip + MIN_MATCH, src, ip + MIN_MATCH - rep0,
    [limit + MIN_MATCH_ECONOMICAL - ip - MIN_MATCH, 0].max
  )
  back = backward_extension(src, ip, anchor, ip - rep0)
  m_len += back
  return nil if m_len < min_match

  [rep0, m_len, ip - back]
end

.rotate_reps(reps, new_offset) ⇒ Object

Rotate the finder-side repeat offsets (C ZSTD_updateRep).

rubocop:disable-next Metrics/AbcSize



465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
 
# File 'lib/omnizip/algorithms/zstandard/match_finder.rb', line 465

def rotate_reps(reps, new_offset)
  if reps[0] == new_offset
    nil # already most recent
  elsif reps[1] == new_offset
    reps[0], reps[1] = reps[1], reps[0]
  elsif reps[2] == new_offset
    reps[2] = reps[1]
    reps[1] = reps[0]
    reps[0] = new_offset
  else
    reps[2] = reps[1]
    reps[1] = reps[0]
    reps[0] = new_offset
  end
end