Class: Omnizip::Implementations::SevenZip::LZMA::MatchFinder

Inherits:
Object
  • Object
show all
Includes:
Algorithms::LZMA::Constants
Defined in:
lib/omnizip/implementations/seven_zip/lzma/match_finder.rb

Overview

7-Zip LZMA SDK match finder implementation.

This is the original SdkMatchFinder moved from algorithms/lzma/sdk_match_finder.rb to the new namespace structure.

Ported from 7-Zip LZMA SDK by Igor Pavlov.

Defined Under Namespace

Classes: Match

Constant Summary

Constants included from Algorithms::LZMA::Constants

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(config) ⇒ MatchFinder

Initialize the SDK-compatible match finder

Parameters:

  • config (MatchFinderConfig) —

    Configuration object



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/omnizip/implementations/seven_zip/lzma/match_finder.rb', line 51

def initialize(config)
  @config = config
  @window_size = config.window_size
  @max_match_length = config.max_match_length
  @chain_length = config.chain_length
  @lazy_matching = config.lazy_matching

  # Hash table: maps hash value to position
  # SDK uses separate hash2 and hash3 tables, but we simplify
  # to single hash table with chaining
  @hash_table = {}

  # Hash chain: stores previous positions for each hash value
  @hash_chain = {}

  # CRC table for hash computation (SDK uses CRC)
  init_crc_table
end

Instance Attribute Details

#config ⇒ Object (readonly)

Returns the value of attribute config.



46
47
48
 
# File 'lib/omnizip/implementations/seven_zip/lzma/match_finder.rb', line 46

def config
  @config
end

Instance Method Details

#find_longest_match(data, pos) ⇒ Match?

Find the longest match at the given position

Implements SDK's GetMatches() function from LzFind.c

Parameters:

  • data (String, Array<Integer>) —

    Input data

  • pos (Integer) —

    Current position in data

Returns:

  • (Match, nil) —

    Best match or nil if no match found



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
 
# File 'lib/omnizip/implementations/seven_zip/lzma/match_finder.rb', line 77

def find_longest_match(data, pos)
  return nil if pos >= data.size
  return nil if data.size - pos < MATCH_LEN_MIN

  if @lazy_matching && @lazy_match
    # Return lazy match from previous position
    match = @lazy_match
    @lazy_match = nil
    # Don't update hash - current position was already added when lazy match was created
    return match
  end

  best_match = find_best_match(data, pos)

  if @lazy_matching && best_match && pos + 1 < data.size
    # Try next position for potentially better match
    next_match = find_best_match(data, pos + 1)
    if next_match && next_match.length > best_match.length
      # Save better match for next call
      @lazy_match = next_match
      # Don't update hash - we'll add it when lazy match is consumed
      return nil
    end
  end

  # CRITICAL: Update hash AFTER finding matches
  # This ensures the current position is available for future matches
  update_hash(data, pos)
  best_match
end

#reset ⇒ void

This method returns an undefined value.

Reset the match finder state



111
112
113
114
115
 
# File 'lib/omnizip/implementations/seven_zip/lzma/match_finder.rb', line 111

def reset
  @hash_table.clear
  @hash_chain.clear
  @lazy_match = nil
end