class Bitcoin::BloomFilter

Constants

LN2
LN2_SQUARED
MAX_BLOOM_FILTER_SIZE
MAX_HASH_FUNCS

Attributes

filter[R]
hash_funcs[R]
tweak[R]

Public Class Methods

create_filter(elements_length, fp_rate, tweak = 0) click to toggle source

Create a new bloom filter. @param [Integer] elements_length the number of elements @param [Float] fp_rate the false positive rate chosen by the client @param [Integer] tweak A random value to add to the seed value in the hash function used by the bloom filter

# File lib/bitcoin/bloom_filter.rb, line 22
def self.create_filter(elements_length, fp_rate, tweak = 0)
  # The size S of the filter in bytes is given by (-1 / pow(log(2), 2) * N * log(P)) / 8
  len = [[(-elements_length * Math.log(fp_rate) / (LN2_SQUARED * 8)).to_i, MAX_BLOOM_FILTER_SIZE].min, 1].max
  filter = Array.new(len, 0)
  # The number of hash functions required is given by S * 8 / N * log(2)
  hash_funcs = [[(filter.size * 8 * LN2 / elements_length).to_i, MAX_HASH_FUNCS].min, 1].max
  BloomFilter.new(filter, hash_funcs, tweak)
end
new(filter, hash_funcs, tweak) click to toggle source
# File lib/bitcoin/bloom_filter.rb, line 12
def initialize(filter, hash_funcs, tweak)
  @filter = filter
  @hash_funcs = hash_funcs
  @tweak = tweak
end

Public Instance Methods

add(data) click to toggle source

@param [String] data The data element to add to the current filter.

# File lib/bitcoin/bloom_filter.rb, line 32
def add(data)
  return if full?
  hash_funcs.times do |i|
    hash = to_hash(data, i)
    set_bit(hash)
  end
end
clear() click to toggle source
# File lib/bitcoin/bloom_filter.rb, line 52
def clear
  filter.fill(0)
  @full = false
end
contains?(data) click to toggle source

Returns true if the given data matches the filter @param [String] data The data to check the current filter @return [Boolean] true if the given data matches the filter

# File lib/bitcoin/bloom_filter.rb, line 43
def contains?(data)
  return true if full?
  hash_funcs.times do |i|
    hash = to_hash(data, i)
    return false unless check_bit(hash)
  end
  true
end
to_a() click to toggle source
# File lib/bitcoin/bloom_filter.rb, line 57
def to_a
  filter
end

Private Instance Methods

check_bit(data) click to toggle source
# File lib/bitcoin/bloom_filter.rb, line 70
def check_bit(data)
  filter[data >> 3] & (1 << (7 & data)) != 0
end
full?() click to toggle source
# File lib/bitcoin/bloom_filter.rb, line 74
def full?
  @full |= filter.all? {|byte| byte == 0xff}
end
set_bit(data) click to toggle source
# File lib/bitcoin/bloom_filter.rb, line 66
def set_bit(data)
  filter[data >> 3] |= (1 << (7 & data))
end
to_hash(data, i) click to toggle source
# File lib/bitcoin/bloom_filter.rb, line 62
def to_hash(data, i)
  MurmurHash3::V32.str_hash(data, (i * 0xfba4c795 + tweak) & 0xffffffff)  % (filter.length * 8)
end