Class: Omnizip::Algorithms::Zstandard::LdmHashTable

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/algorithms/zstandard/ldm.rb

Overview

Long-Distance Matching sparse hash table (port of the omnizip-rs encoder/ldm.rs).

Hashes every gap-th position into a head/chain table so the parser can find matches at distances far beyond the normal match-finder window — up to the full frame size. The table is pre-populated over the whole input before parsing starts, so entries may point forward of the current position; find_match skips those without spending its chain budget.

Constant Summary collapse

LDM_MAX_CHAIN =

Chain entries walked per find_match (Rust LDM_MAX_CHAIN).

32
MIN_MATCH = 
MatchFinder::MIN_MATCH

Instance Method Summary collapse

Constructor Details

#initialize(input_len, window_log, gap = 16) ⇒ LdmHashTable

Hash table and chain sizes are additionally capped by the number of sparse samples so small inputs do not pay for a window-sized table.



43
44
45
46
47
48
49
50
51
52
 
# File 'lib/omnizip/algorithms/zstandard/ldm.rb', line 43

def initialize(input_len, window_log, gap = 16)
  samples = (input_len / gap) + 1
  hash_log = [[window_log, 21].min, samples.bit_length + 2].min
  hash_log = 1 if hash_log < 1

  @gap = gap
  @hash_log = hash_log
  @head = Array.new(1 << hash_log)
  @chain = Array.new(samples)
end

Instance Method Details

#find_match(src, pos, max_distance, min_match, end_bound) ⇒ Object

Longest match at pos within max_distance, bounded by end_bound (the current block end). Walks up to MAX_CHAIN chain entries. Returns [distance, length] or nil.

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



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

def find_match(src, pos, max_distance, min_match, end_bound)
  return nil if pos + MIN_MATCH > src.bytesize

  candidate = @head[hash4(src, pos)]
  best_len = 0
  best_dist = 0
  chain_count = 0

  while candidate && chain_count < LDM_MAX_CHAIN
    if candidate >= pos
      candidate = @chain[candidate / @gap]
      next
    end

    dist = pos - candidate
    break if dist > max_distance

    len_cap = [end_bound - pos, pos - candidate].min
    len_cap = 0 if len_cap.negative?
    len = MatchFinder.count_match(src, pos, src, candidate, len_cap)
    if len > best_len && len >= min_match
      best_len = len
      best_dist = dist
    end

    candidate = @chain[candidate / @gap]
    chain_count += 1
  end

  return nil unless best_len >= min_match && best_dist.positive?

  [best_dist, best_len]
end

#insert(src, pos) ⇒ Object

Insert pos into the table (sparse sampling: every gap-th position only).



56
57
58
59
60
61
62
63
 
# File 'lib/omnizip/algorithms/zstandard/ldm.rb', line 56

def insert(src, pos)
  return unless (pos % @gap).zero?

  h = hash4(src, pos)
  idx = pos / @gap
  @chain[idx] = @head[h] if idx < @chain.length
  @head[h] = pos
end