Class: Omnizip::Formats::Rar::Compression::LZ77Huffman::MatchFinder

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/formats/rar/compression/lz77_huffman/match_finder.rb

Overview

LZ77 Match Finder for RAR compression

Defined Under Namespace

Classes: Match

Constant Summary collapse

MAX_MATCH_LENGTH = 
257
MIN_MATCH_LENGTH = 
3
WINDOW_SIZE = 
32768
MAX_CHAIN_LENGTH = 
1024

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(window_size = WINDOW_SIZE, max_match_length = MAX_MATCH_LENGTH) ⇒ MatchFinder

Returns a new instance of MatchFinder.



30
31
32
33
34
35
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/match_finder.rb', line 30

def initialize(window_size = WINDOW_SIZE,
max_match_length = MAX_MATCH_LENGTH)
  @window_size = window_size
  @max_match_length = [max_match_length, MAX_MATCH_LENGTH].min
  @hash_table = {}
end

Instance Attribute Details

#max_match_length ⇒ Object (readonly)

Returns the value of attribute max_match_length.



28
29
30
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/match_finder.rb', line 28

def max_match_length
  @max_match_length
end

#window_size ⇒ Object (readonly)

Returns the value of attribute window_size.



28
29
30
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/match_finder.rb', line 28

def window_size
  @window_size
end

Instance Method Details

#find_match(data, position) ⇒ Object 



37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/match_finder.rb', line 37

def find_match(data, position)
  return nil if position >= data.size
  return nil if data.size - position < MIN_MATCH_LENGTH

  # Index all positions up to current if not done yet
  ensure_indexed(data, position)

  hash_val = hash_bytes(data, position)
  candidates = @hash_table[hash_val] || []
  best_match = find_best_among_candidates(data, position,
                                          candidates)
  update_hash(hash_val, position)
  best_match
end

#hash_chain_count ⇒ Object 



64
65
66
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/match_finder.rb', line 64

def hash_chain_count
  @hash_table.size
end

#reset ⇒ Object 



59
60
61
62
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/match_finder.rb', line 59

def reset
  @hash_table.clear
  @last_indexed = -1
end

#update(data, position) ⇒ Object 



52
53
54
55
56
57
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/match_finder.rb', line 52

def update(data, position)
  return if position >= data.size

  hash_val = hash_bytes(data, position)
  update_hash(hash_val, position)
end