Class: Omnizip::Algorithms::LZMA::XzMatchFinderAdapter

Inherits:
Object
  • Object
show all
Includes:
Constants
Defined in:
lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb

Overview

XZ Utils-compatible match finder adapter

Wraps existing MatchFinder to provide XZ Utils interface with:

  • Cursor-based position tracking
  • Multiple match finding (not just longest)
  • Skip and lookahead operations

Based on: xz/src/liblzma/lz/lz_encoder_mf.c

Defined Under Namespace

Classes: Match

Constant Summary

Constants included from Constants

Constants::BIT_MODEL_TOTAL, Constants::COMPRESSION_LEVEL_DEFAULT, Constants::COMPRESSION_LEVEL_MAX, Constants::COMPRESSION_LEVEL_MIN, Constants::DICT_SIZE_MAX, Constants::DICT_SIZE_MIN, Constants::DIST_ALIGN_BITS, Constants::DIST_ALIGN_SIZE, Constants::DIST_SLOT_FAST_LIMIT, Constants::END_POS_MODEL_INDEX, Constants::EOS_MARKER, Constants::INIT_PROBS, Constants::LEN_HIGH_SYMBOLS, Constants::LEN_LOW_SYMBOLS, Constants::LEN_MID_SYMBOLS, Constants::LIT_SIZE_MAX, Constants::MATCH_LEN_MAX, Constants::MATCH_LEN_MIN, Constants::MOVE_BITS, Constants::NUM_DIRECT_BITS, Constants::NUM_DIST_SLOTS, Constants::NUM_DIST_SLOT_BITS, Constants::NUM_FULL_DISTANCES, Constants::NUM_LEN_HIGH_BITS, Constants::NUM_LEN_LOW_BITS, Constants::NUM_LEN_MID_BITS, Constants::NUM_LEN_TO_POS_STATES, Constants::NUM_LIT_CONTEXT_BITS_MAX, Constants::NUM_LIT_POS_BITS_MAX, Constants::NUM_POS_BITS_MAX, Constants::NUM_STATES, Constants::POS_STATES_MAX, Constants::START_POS_MODEL_INDEX, Constants::TOP

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(data, dict_size: 1 << 23, nice_len: 32) ⇒ XzMatchFinderAdapter

Initialize match finder adapter

Parameters:

  • data (String, Array<Integer>) —

    Input data

  • dict_size (Integer) (defaults to: 1 << 23) —

    Dictionary size (default 8MB for XZ)

  • nice_len (Integer) (defaults to: 32) —

    Nice match length (default 32)



51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 51

def initialize(data, dict_size: 1 << 23, nice_len: 32)
  @data = data.is_a?(String) ? data.bytes : data
  @pos = 0
  @dict_size = dict_size
  @nice_len = nice_len

  # Internal state
  @matches = []
  @longest_len = 0

  # Hash table for match finding
  @hash_table = {}
end

Instance Attribute Details

#longest_len ⇒ Object (readonly)

Returns the value of attribute longest_len.



44
45
46
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 44

def longest_len
  @longest_len
end

#matches ⇒ Object (readonly)

Returns the value of attribute matches.



44
45
46
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 44

def matches
  @matches
end

#pos ⇒ Object (readonly)

Returns the value of attribute pos.



44
45
46
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 44

def pos
  @pos
end

Instance Method Details

#available ⇒ Integer

Bytes available from current position

Returns:

  • (Integer) —

    Number of bytes remaining



152
153
154
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 152

def available
  @data.size - @pos
end

#current_byte ⇒ Integer?

Get current byte at position

Returns:

  • (Integer, nil) —

    Byte value or nil if at end



159
160
161
162
163
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 159

def current_byte
  return nil if @pos >= @data.size

  @data[@pos]
end

#find_matches ⇒ Integer

Find all matches at current position

Finds multiple matches of different lengths, not just the longest. Results stored in @matches array, longest length in @longest_len.

Returns:

  • (Integer) —

    Longest match length (0 if no matches)



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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 71

def find_matches
  @matches.clear
  @longest_len = 0

  return 0 if @pos >= @data.size
  return 0 if available < MATCH_LEN_MIN

  # CRITICAL: Don't produce matches until there's enough data for decoder
  # The decoder validates: dict_full > distance
  # Where dict_full = decoded_byte_count (starting from 0)
  # So for distance=N to be valid, we need at least N+1 bytes decoded
  # We're at position @pos (0-based), so @pos bytes have been processed
  # For distance=1 match: need @pos >= 2 (so decoder has dict_full=2)
  # For distance=N match: need @pos >= N+1
  # Simple check: Don't produce matches until @pos >= 2
  return 0 if @pos < 2

  # Find matches using hash chains
  hash_val = compute_hash
  positions = @hash_table[hash_val] || []

  # Track best matches at each length
  best_distances = {}

  positions.reverse_each do |prev_pos|
    distance = @pos - prev_pos
    break if distance > @dict_size

    # Skip self-matching (can happen when lookahead searches same position twice)
    next if distance.zero?

    match_len = calculate_match_length(prev_pos)
    next if match_len < MATCH_LEN_MIN

    # Keep best (shortest) distance for each length
    if !best_distances[match_len] || distance < best_distances[match_len]
      best_distances[match_len] = distance
    end

    # Update longest
    @longest_len = match_len if match_len > @longest_len

    # Stop if we found nice length
    break if match_len >= @nice_len
  end

  # Convert to matches array (sorted by length)
  best_distances.keys.sort.each do |len|
    @matches << Match.new(len: len, dist: best_distances[len])
  end

  # Update hash table
  update_hash(hash_val, @pos)

  @longest_len
end

#get_byte(offset) ⇒ Integer

Get byte at offset from current position

Parameters:

  • offset (Integer) —

    Offset from current position (can be negative)

Returns:

  • (Integer) —

    Byte value (0 if out of bounds)



169
170
171
172
173
174
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 169

def get_byte(offset)
  pos = @pos + offset
  return 0 if pos.negative? || pos >= @data.size

  @data[pos]
end

#move_pos ⇒ Object

Move position forward by one byte



145
146
147
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 145

def move_pos
  @pos += 1
end

#reset ⇒ Object

Reset match finder to beginning



177
178
179
180
181
182
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 177

def reset
  @pos = 0
  @matches.clear
  @longest_len = 0
  @hash_table.clear
end

#skip(n) ⇒ Object

Skip n bytes without finding matches

Advances position and updates hash tables but doesn't search for matches. Used for rep matches where we already know what to encode.

Parameters:

  • n (Integer) —

    Number of bytes to skip



134
135
136
137
138
139
140
141
142
 
# File 'lib/omnizip/algorithms/lzma/xz_match_finder_adapter.rb', line 134

def skip(n)
  n.times do
    return if @pos >= @data.size

    hash_val = compute_hash
    update_hash(hash_val, @pos)
    @pos += 1
  end
end