8000 Convert all parameters integers to 64 bit by adewes · Pull Request #8 · DCSO/bloom · GitHub
[go: up one dir, main page]

Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions .travis.yml
Original file line number Diff line number Diff line change
@@ -1,6 +1,7 @@
language: go
sudo: false
before_script:
- go get ./...
- go vet ./...
script: make release
deploy:
Expand Down
139 changes: 78 additions & 61 deletions bloom.go
Original file line number Diff line number Diff line change
Expand Up @@ -15,8 +15,6 @@ import (
"math"
)

const magicSeed = "this-is-magical"

// SetError represents an error with a given message related to set operations.
type SetError struct {
msg string
Expand All @@ -29,61 +27,70 @@ type BloomFilter struct {
//bit array
v []uint64
//desired maximum number of elements
n uint32
n uint64
//desired false positive probability
p float64
//number of hash functions
k uint32
k uint64
//number of bits
m uint32
m uint64
//number of elements in the filter
N uint32
N uint64
//number of 64-bit integers (generated automatically)
M uint32
M uint64
//arbitrary data that we can attach to the filter
Data []byte
}

// Read loads a filter from a reader object.
func (s *BloomFilter) Read(input io.Reader) error {
bs4 := make([]byte, 4)
bs8 := make([]byte, 8)

if _, err := io.ReadFull(input, bs4); err != nil {
if _, err := io.ReadFull(input, bs8); err != nil {
return err
}

s.n = binary.LittleEndian.Uint32(bs4)
flags := binary.LittleEndian.Uint64(bs8)

if flags & 0xFF != 1 {
return fmt.Errorf("Invalid version bit (should be 1)")
}

if _, err := io.ReadFull(input, bs8); err != nil {
return err
}

s.n = binary.LittleEndian.Uint64(bs8)

if _, err := io.ReadFull(input, bs8); err != nil {
return err
}

s.p = math.Float64frombits(binary.LittleEndian.Uint64(bs8))

if _, err := io.ReadFull(input, bs4); err != nil {
if _, err := io.ReadFull(input, bs8); err != nil {
return err
}

s.k = binary.LittleEndian.Uint32(bs4)
s.k = binary.LittleEndian.Uint64(bs8)

if _, err := io.ReadFull(input, bs4); err != nil {
if _, err := io.ReadFull(input, bs8); err != nil {
return err
}

s.m = binary.LittleEndian.Uint32(bs4)
s.m = binary.LittleEndian.Uint64(bs8)

if _, err := io.ReadFull(input, bs4); err != nil {
if _, err := io.ReadFull(input, bs8); err != nil {
return err
}

s.N = binary.LittleEndian.Uint32(bs4)
s.N = binary.LittleEndian.Uint64(bs8)

s.M = uint32(math.Ceil(float64(s.m) / 64.0))
s.M = uint64(math.Ceil(float64(s.m) / 64.0))

s.v = make([]uint64, s.M)

for i := uint32(0); i < s.M; i++ {
for i := uint64(0); i < s.M; i++ {
n, err := io.ReadFull(input, bs8)
if err != nil {
return err
Expand All @@ -107,18 +114,18 @@ func (s *BloomFilter) Read(input io.Reader) error {
}

// NumHashFuncs returns the number of hash functions used in the Bloom filter.
func (s *BloomFilter) NumHashFuncs() uint32 {
func (s *BloomFilter) NumHashFuncs() uint64 {
return s.k
}

// MaxNumElements returns the maximal supported number of elements in the Bloom
// filter (capacity).
func (s *BloomFilter) MaxNumElements() uint32 {
func (s *BloomFilter) MaxNumElements() uint64 {
return s.n
}

// NumBits returns the number of bits used in the Bloom filter.
func (s *BloomFilter) NumBits() uint32 {
func (s *BloomFilter) NumBits() uint64 {
return s.m
}

Expand All @@ -130,21 +137,24 @@ func (s *BloomFilter) FalsePositiveProb() float64 {

// Write writes the binary representation of a Bloom filter to an io.Writer.
func (s *BloomFilter) Write(output io.Writer) error {
bs4 := make([]byte, 4)
bs8 := make([]byte, 8)

binary.LittleEndian.PutUint32(bs4, s.n)
output.Write(bs4)
// we write the version bit
binary.LittleEndian.PutUint64(bs8, 1)
output.Write(bs8)

binary.LittleEndian.PutUint64(bs8, s.n)
output.Write(bs8)
binary.LittleEndian.PutUint64(bs8, math.Float64bits(s.p))
output.Write(bs8)
binary.LittleEndian.PutUint32(bs4, s.k)
output.Write(bs4)
binary.LittleEndian.PutUint32(bs4, s.m)
output.Write(bs4)
binary.LittleEndian.PutUint32(bs4, s.N)
output.Write(bs4)

for i := uint32(0); i < s.M; i++ {
binary.LittleEndian.PutUint64(bs8, s.k)
output.Write(bs8)
binary.LittleEndian.PutUint64(bs8, s.m)
output.Write(bs8)
binary.LittleEndian.PutUint64(bs8, s.N)
output.Write(bs8)

for i := uint64(0); i < s.M; i++ {
binary.LittleEndian.PutUint64(bs8, s.v[i])
n, err := output.Write(bs8)
if n != 8 {
Expand All @@ -162,40 +172,47 @@ func (s *BloomFilter) Write(output io.Writer) error {

// Reset clears the Bloom filter of all elements.
func (s *BloomFilter) Reset() {
for i := uint32(0); i < s.M; i++ {
for i := uint64(0); i < s.M; i++ {
s.v[i] = 0
}
s.N = 0
}

// this is the largest prime number < 2^64. As we will probably never encounter
// a Bloom filter with a number of bits > m (if yes sorry to you people from,
// the future, I envy your available RAM though) we can use the pseudorandom
// sequence generated by repeatedly multiplying the initial hash value h
// with g and taking the modulo over m to generate a sequence of hash values
// that has a uniform distribution.
const m uint64 = 18446744073709551557
// this is our multiplier. It has a very large primitive root
// so that it will not repeat a given cycle for any practically meaningful
// value of k.
const g uint64 = 18446744073709550147

// Fingerprint returns the fingerprint of a given value, as an array of index
// values.
func (s *BloomFilter) Fingerprint(value []byte, fingerprint []uint32) {

hashValue1 := fnv.New64()
hashValue2 := fnv.New64()

hashValue1.Write(value)
hashValue2.Write(value)
hashValue2.Write([]byte(magicSeed))
func (s *BloomFilter) Fingerprint(value []byte, fingerprint []uint64) {

h1 := hashValue1.Sum64()
h2 := hashValue2.Sum64()
hv := fnv.New64()
hv.Write(value)
hn := hv.Sum64() % m

for i := uint32(0); i < s.k; i++ {
fingerprint[i] = uint32((h1 + (uint64(i)+1)*h2) % uint64(s.m))
for i := uint64(0); i < s.k; i++ {
hn = (hn*g) % m
fingerprint[i] = uint64(hn % s.m)
}
}

// Add adds a byte array element to the Bloom filter.
func (s *BloomFilter) Add(value []byte) {
var k, l uint32
var k, l uint64
newValue := false
fingerprint := make([]uint32, s.k)
fingerprint := make([]uint64, s.k)
s.Fingerprint(value, fing 7438 erprint)
for i := uint32(0); i < s.k; i++ {
k = uint32(fingerprint[i] / 64)
l = uint32(fingerprint[i] % 64)
for i := uint64(0); i < s.k; i++ {
k = uint64(fingerprint[i] / 64)
l = uint64(fingerprint[i] % 64)
v := uint64(1 << l)
if (s.v[k] & v) == 0 {
newValue = true
Expand All @@ -218,7 +235,7 @@ func (s *BloomFilter) Add(value []byte) {
// hence is not allowed. An error will be returned in this case, and the
// receiver will be left unaltered.
func (s *BloomFilter) Join(s2 *BloomFilter) error {
var i uint32
var i uint64
if s.n != s2.n {
return fmt.Errorf("filters have different dimensions (n = %d vs. %d))",
s.n, s2.n)
Expand Down Expand Up @@ -253,18 +270,18 @@ func (s *BloomFilter) Join(s2 *BloomFilter) error {
// Check returns true if the given value may be in the Bloom filter, false if it
// is definitely not in it.
func (s *BloomFilter) Check(value []byte) bool {
fingerprint := make([]uint32, s.k)
fingerprint := make([]uint64, s.k)
s.Fingerprint(value, fingerprint)
return s.CheckFingerprint(fingerprint)
}

// CheckFingerprint returns true if the given fingerprint occurs in the Bloom
// filter, false if it does not.
func (s *BloomFilter) CheckFingerprint(fingerprint []uint32) bool {
var k, l uint32
for i := uint32(0); i < s.k; i++ {
k = uint32(fingerprint[i] / 64)
l = uint32(fingerprint[i] % 64)
func (s *BloomFilter) CheckFingerprint(fingerprint []uint64) bool {
var k, l uint64
for i := uint64(0); i < s.k; i++ {
k = uint64(fingerprint[i] / 64)
l = uint64(fingerprint[i] % 64)
if (s.v[k] & (1 << l)) == 0 {
return false
}
Expand All @@ -274,13 +291,13 @@ func (s *BloomFilter) CheckFingerprint(fingerprint []uint32) bool {

// Initialize returns a new, empty Bloom filter with the given capacity (n)
// and FP probability (p).
func Initialize(n uint32, p float64) BloomFilter {
func Initialize(n uint64, p float64) BloomFilter {
var bf BloomFilter
bf.n = n
bf.p = p
bf.m = uint32(math.Abs(math.Ceil(float64(n) * math.Log(float64(p)) / (math.Pow(math.Log(2.0), 2.0)))))
bf.M = uint32(math.Ceil(float64(bf.m) / 64.0))
bf.k = uint32(math.Ceil(math.Log(2) * float64(bf.m) / float64(n)))
bf.m = uint64(math.Abs(math.Ceil(float64(n) * math.Log(float64(p)) / (math.Pow(math.Log(2.0), 2.0)))))
bf.M = uint64(math.Ceil(float64(bf.m) / 64.0))
bf.k = uint64(math.Ceil(math.Log(2) * float64(bf.m) / float64(n)))
bf.v = make([]uint64, bf.M)
return bf
}
10 changes: 5 additions & 5 deletions bloom/manage.go
Original file line number Diff line number Diff line change
Expand Up @@ -208,7 +208,7 @@ func printStats(path string, bloomParams BloomParams) {
fmt.Printf("Hash functions:\t\t%d\n", filter.NumHashFuncs())
}

func createFilter(path string, n uint32, p float64, bloomParams BloomParams) {
func createFilter(path string, n uint64, p float64, bloomParams BloomParams) {
filter := bloom.Initialize(n, p)
readValuesIntoFilter(&filter, bloomParams)
err := bloom.WriteFilter(&filter, path, bloomParams.gzip)
Expand Down Expand Up @@ -320,7 +320,7 @@ func main() {
Aliases: []string{"cr"},
Flags: []cli.Flag{
cli.Float64Flag{Name: "p", Value: 0.01, Usage: "The desired false positive probability."},
cli.IntFlag{Name: "n", Value: 10000, Usage: "The desired capacity."},
cli.Uint64Flag{Name: "n", Value: 10000, Usage: "The desired capacity."},
},
Usage: "Create a new Bloom filter and store it in the given filename.",
Action: func(c *cli.Context) error {
Expand All @@ -333,15 +333,15 @@ func main() {
if err != nil {
return err
}
n := c.Int("n")
n := c.Uint64("n")
p := c.Float64("p")
if n < 0 {
exitWithError("n cannot be negative.")
}
if p < 0 || p > 1 {
exitWithError("p must be between 0 and 1.")
}
createFilter(path, uint32(n), p, bloomParams)
createFilter(path, n, p, bloomParams)
return nil
},
},
Expand Down Expand Up @@ -471,7 +471,7 @@ func main() {
},
},
}
app.Version = "0.1.1"
app.Version = "0.2.2"

app.Run(os.Args)
}
Loading
0