<commit_before>// a2filter.go - A2 bloom filter
//
// To the extent possible under law, the Yawning Angel waived all copyright
// and related or neighboring rights to a2filter, using the creative
// commons "cc0" public domain dedication. See LICENSE or
// <http://creativecommons.org/publicdomain/zero/1.0/> for full details.

// Package a2filter implements a SipHash-2-4 based Active-Active Bloom Filter.
// It is designed to be stable over time even when filled to max capacity by
// implementing the active-active buffering (A2 buffering) scheme presented in
// "Aging Bloom Filter with Two Active Buffers for Dynamic Sets" (MyungKeun
// Yoon).
//
// Note that none of the operations on the filter are constant time, and the
// the max backing Bloom Filter size is limited to 2^31 bytes.  This package is
// threadsafe.
package a2filter

import (
	"crypto/rand"
	"encoding/binary"
	"fmt"
	"math"
	"sync"

	"github.com/dchest/siphash"
)

const (
	ln2         = 0.69314718055994529
	ln2Sq       = 0.48045301391820139
	maxMln2     = 31
	maxNrHashes = 32
)

// A2Filter is an Active-Active Bloom Filter.
type A2Filter struct {
	sync.Mutex
	k1, k2 uint64

	nrEntries    int
	nrEntriesMax int

	nrHashes int
	hashMask uint32
	active1  []byte
	active2  []byte
}

// New constructs a new A2Filter with a filter set size 2^mLn2, and false
// postive rate p.  The actual in memory footprint of the datastructure will be
// approximately 2^(mLn2+1) bits due to the double buffered nature of the
// filter.
func New(mLn2 int, p float64) (*A2Filter, error) {
	var key [16]byte
	_, err := rand.Read(key[:])
	if err != nil {
		return nil, err
	}

	if mLn2 > maxMln2 {
		return nil, fmt.Errorf("requested filter too large: %d", mLn2)
	}

	m := 1 << uint32(mLn2)
	n := -1.0 * float64(m) * ln2Sq / math.Log(p)
	k := int((float64(m) * ln2 / n) + 0.5)

	f := new(A2Filter)
	f.k1 = binary.BigEndian.Uint64(key[0:8])
	f.k2 = binary.BigEndian.Uint64(key[8:16])
	f.nrEntriesMax = int(n)
	f.nrHashes = k
	f.hashMask = uint32(m - 1)
	if f.nrHashes < 2 {
		f.nrHashes = 2
	}
	if f.nrHashes > maxNrHashes {
		return nil, fmt.Errorf("requested parameters need too many hashes")
	}
	f.active1 = make([]byte, m/8)<commit_msg>Take an io.Reader as the entropy source.<commit_after>// a2filter.go - A2 bloom filter
//
// To the extent possible under law, the Yawning Angel waived all copyright
// and related or neighboring rights to a2filter, using the creative
// commons "cc0" public domain dedication. See LICENSE or
// <http://creativecommons.org/publicdomain/zero/1.0/> for full details.

// Package a2filter implements a SipHash-2-4 based Active-Active Bloom Filter.
// It is designed to be stable over time even when filled to max capacity by
// implementing the active-active buffering (A2 buffering) scheme presented in
// "Aging Bloom Filter with Two Active Buffers for Dynamic Sets" (MyungKeun
// Yoon).
//
// Note that none of the operations on the filter are constant time, and the
// the max backing Bloom Filter size is limited to 2^31 bytes.  This package is
// threadsafe.
package a2filter

import (
	"encoding/binary"
	"fmt"
	"io"
	"math"
	"sync"

	"github.com/dchest/siphash"
)

const (
	ln2         = 0.69314718055994529
	ln2Sq       = 0.48045301391820139
	maxMln2     = 31
	maxNrHashes = 32
)

// A2Filter is an Active-Active Bloom Filter.
type A2Filter struct {
	sync.Mutex
	k1, k2 uint64

	nrEntries    int
	nrEntriesMax int

	nrHashes int
	hashMask uint32
	active1  []byte
	active2  []byte
}

// New constructs a new A2Filter with a filter set size 2^mLn2, and false
// postive rate p.  The actual in memory footprint of the datastructure will be
// approximately 2^(mLn2+1) bits due to the double buffered nature of the
// filter.
func New(rand io.Reader, mLn2 int, p float64) (*A2Filter, error) {
	var key [16]byte
	if _, err := io.ReadFull(rand, key[:]); err != nil {
		return nil, err
	}

	if mLn2 > maxMln2 {
		return nil, fmt.Errorf("requested filter too large: %d", mLn2)
	}

	m := 1 << uint32(mLn2)
	n := -1.0 * float64(m) * ln2Sq / math.Log(p)
	k := int((float64(m) * ln2 / n) + 0.5)

	f := new(A2Filter)
	f.k1 = binary.BigEndian.Uint64(key[0:8])
	f.k2 = binary.BigEndian.Uint64(key[8:16])
	f.nrEntriesMax = int(n)
	f.nrHashes = k
	f.hashMask = uint32(m - 1)
	if f.nrHashes < 2 {
		f.nrHashes = 2
	}
	if f.nrHashes > maxNrHashes {
		return nil, fmt.Errorf("requested parameters need too many hashes")
	}
	f.active1 = make([]byte, m/8)
{'fraction_non_alphanumeric': 0.11198738170347003, 'fraction_numerical': 0.051825146462370436, 'mean_word_length': 3.313896987366375, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '444098', 'n_tokens_mistral': 1741, 'n_tokens_neox': 1593, 'n_words': 544}