Class: Omnizip::Algorithms::LZMA::MatchFinder

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/algorithms/lzma/match_finder.rb

Overview

Match Finder using hash chain algorithm for LZ77 compression Ported from XZ Utils lz_encoder.c

Constant Summary collapse

HASH_SIZE =

Larger hash table for better distribution 16384 slots with 4-byte keys gives better collision resistance

16384
HASH_MASK = 
HASH_SIZE - 1
MAX_MATCHES = 
274
DEFAULT_CHAIN_DEPTH =

Maximum hash chain depth to prevent O(n) lookups XZ Utils uses different values based on compression level (4-256) Ruby needs much lower values due to slower string operations Testing shows depth 16 gives same compression ratio as 32-64 but 2-3x faster

16

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(dictionary, chain_depth: DEFAULT_CHAIN_DEPTH) ⇒ MatchFinder

Returns a new instance of MatchFinder.



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

def initialize(dictionary, chain_depth: DEFAULT_CHAIN_DEPTH)
  @dictionary = dictionary
  @buffer = String.new(encoding: Encoding::BINARY)
  @position = 0
  @chain_depth = chain_depth
  # Use nil as empty marker (not 0) to distinguish from position 0
  @hash_table = Array.new(HASH_SIZE, nil)
  @hash_chain = Array.new(0)
  @matches = Array.new(MAX_MATCHES)
  @matches_count = 0
end

Instance Attribute Details

#buffer ⇒ Object (readonly)

Returns the value of attribute buffer.



40
41
42
 
# File 'lib/omnizip/algorithms/lzma/match_finder.rb', line 40

def buffer
  @buffer
end

#dictionary ⇒ Object (readonly)

Returns the value of attribute dictionary.



40
41
42
 
# File 'lib/omnizip/algorithms/lzma/match_finder.rb', line 40

def dictionary
  @dictionary
end

#position ⇒ Object (readonly)

Returns the value of attribute position.



40
41
42
 
# File 'lib/omnizip/algorithms/lzma/match_finder.rb', line 40

def position
  @position
end

Instance Method Details

#feed(data) ⇒ void

This method returns an undefined value.

Add input data for processing

Parameters:

  • data (String) —

    Binary data to add



58
59
60
 
# File 'lib/omnizip/algorithms/lzma/match_finder.rb', line 58

def feed(data)
  @buffer << data
end

#find_longest_match(bytes, pos) ⇒ Match?

Legacy API: Find longest match at given position in external byte array This is a compatibility method for older code that passes bytes and position

Parameters:

  • bytes (Array<Integer>) —

    Byte array

  • pos (Integer) —

    Position to find match at

Returns:

  • (Match, nil) —

    Longest match found or nil



160
161
162
163
164
165
166
167
168
169
170
 
# File 'lib/omnizip/algorithms/lzma/match_finder.rb', line 160

def find_longest_match(bytes, pos)
  # If position is beyond current buffer, feed more data
  if pos >= @buffer.bytesize
    bytes_to_feed = bytes[pos..]
    @buffer << bytes_to_feed.pack("C*")
  end

  # Find matches at the given position
  matches = find_matches(pos)
  matches.first
end

#find_matches(current_pos = @buffer.bytesize - 273) ⇒ Array<Match>

Find matches for current position

Parameters:

  • current_pos (Integer) (defaults to: @buffer.bytesize - 273) —

    Position to find matches at (defaults to end)

Returns:

  • (Array<Match>) —

    Array of matches sorted by length (descending)



94
95
96
97
98
99
100
101
102
103
104
105
106
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
144
145
 
# File 'lib/omnizip/algorithms/lzma/match_finder.rb', line 94

def find_matches(current_pos = @buffer.bytesize - 273)
  # Calculate hash for current position
  # Note: Using 4-byte hash now (calc_hash checks pos + 4)
  hash = nil
  if current_pos >= 0 && current_pos + 4 <= @buffer.bytesize
    hash = calc_hash(@buffer, current_pos)
  end

  # Skip hash table update here - skip() already built the table for all positions
  # Adding current_pos to the chain is redundant since skip processed all positions

  # Can't find matches if no hash or insufficient data
  # Note: We CAN find matches at early positions (e.g., position 2 can match position 0)
  # The only requirement is that there's enough data for hash calculation (current_pos + 4 <= buffer size)
  # and that there's at least 2 bytes of history (for MIN_MATCH_LENGTH=2)
  # CRITICAL: Don't produce matches until position >= 2 to ensure decoder has enough dict_full
  # The decoder validates: dict_full > distance, where dict_full starts at 0 after 1st byte
  # For distance=1 match to be valid, decoder needs dict_full >= 2 (at least 2 bytes decoded)
  # This happens after processing position 1 (first byte was literal at position 0)
  # So we can only produce matches starting at position 2
  return [] if hash.nil? || @buffer.bytesize < 4 || current_pos + 4 > @buffer.bytesize || current_pos < 2

  @matches_count = 0
  chain_pos = @hash_chain[current_pos]
  chain_depth = 0

  while chain_pos && @matches_count < MAX_MATCHES && chain_depth < @chain_depth
    chain_depth += 1
    # CRITICAL: Skip invalid chain_pos values (beyond buffer or negative)
    next if chain_pos >= @buffer.bytesize || chain_pos.negative?

    distance = current_pos - chain_pos
    # CRITICAL: Break if distance is negative (chain_pos > current_pos)
    # This can happen when skip() links positions within the same chunk
    # where a later position has the same hash as an earlier position
    break if distance.negative? || distance > @dictionary.size || distance.zero?

    length = verify_match(current_pos, chain_pos)

    if length >= 2
      @matches[@matches_count] = Match.new(distance, length)
      @matches_count += 1
    end

    # Safely get next chain position
    chain_pos = if chain_pos < @hash_chain.size
                  @hash_chain[chain_pos]
                end
  end

  @matches.first(@matches_count).sort_by { |m| -m.length }
end

#longest_match ⇒ Match?

Get the longest match at current position

Returns:

  • (Match, nil) —

    Longest match found or nil



150
151
152
 
# File 'lib/omnizip/algorithms/lzma/match_finder.rb', line 150

def longest_match
  find_matches.first
end

#reset ⇒ Object

Reset the match finder state for a new encoding session Clears the buffer, hash table, and hash chain



64
65
66
67
68
69
70
 
# File 'lib/omnizip/algorithms/lzma/match_finder.rb', line 64

def reset
  @buffer.clear
  @position = 0
  @hash_table = Array.new(HASH_SIZE, nil)
  @hash_chain.clear
  @matches_count = 0
end

#skip(end_pos) ⇒ void

This method returns an undefined value.

Initialize hash table for all positions up to end_pos This is called before encoding starts to ensure the hash table is populated for all positions. Matches XZ Utils "skip" behavior.

Parameters:

  • end_pos (Integer) —

    Last position to initialize (inclusive)



78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/omnizip/algorithms/lzma/match_finder.rb', line 78

def skip(end_pos)
  pos = 0
  while pos + 3 <= @buffer.bytesize && pos <= end_pos
    hash = calc_hash(@buffer, pos)
    if hash
      @hash_chain[pos] = @hash_table[hash]
      @hash_table[hash] = pos
    end
    pos += 1
  end
end