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