Bloom filter.

const MAX_BITS = 2 ** 31;

// Two 32-bit hashes of the value's UTF-8 bytes: FNV-1a from two different starting
// values, each finished with MurmurHash3's final mix. Alone, FNV-1a's low bits depend
// only on the low bits of each byte, and a position mod a small size reads mostly low bits.
export function hashPair(value: string): [number, number] {
	const bytes = new TextEncoder().encode(value);
	return [finish(fnv1a(bytes, 0x811c9dc5)), finish(fnv1a(bytes, 0x050c5d1f))];
}

function fnv1a(bytes: Uint8Array, basis: number): number {
	let hash = basis;
	for (const byte of bytes) {
		hash ^= byte;
		hash = Math.imul(hash, 16777619) >>> 0;
	}
	return hash;
}

function finish(hash: number): number {
	hash ^= hash >>> 16;
	hash = Math.imul(hash, 0x85ebca6b);
	hash ^= hash >>> 13;
	hash = Math.imul(hash, 0xc2b2ae35);
	hash ^= hash >>> 16;
	return hash >>> 0;
}

export type Size = { bits: number; hashes: number };

// Size a filter for about `expectedItems` values at a target false positive rate.
export function sizeFor(expectedItems: number, falsePositiveRate: number): Size {
	if (!Number.isInteger(expectedItems) || expectedItems < 1 || expectedItems > MAX_BITS)
		throw new RangeError('expected items must be an integer from 1 to 2147483648');
	if (!(falsePositiveRate > 0 && falsePositiveRate < 1))
		throw new RangeError('false positive rate must be greater than 0 and less than 1');
	// m = −n ln p / (ln 2)², then k = (m / n) ln 2, the hash count that makes the rate smallest.
	const bits = Math.ceil((-expectedItems * Math.log(falsePositiveRate)) / (Math.LN2 * Math.LN2));
	if (bits > MAX_BITS) throw new RangeError('the filter would need more than 2147483648 bits');
	const hashes = Math.round((bits / expectedItems) * Math.LN2);
	return { bits, hashes: Math.min(32, Math.max(1, hashes)) };
}

export type Step = {
	kind: 'hash' | 'set' | 'test';
	value: string;
	/** hash: the first 32-bit hash. set and test: the bit's position. */
	a: number;
	/** hash: the second hash. set: 1 if the bit was already on. test: 1 if the bit is on. */
	b: number;
};

// A row of bits, all off to start. Adding a value turns on the bits at its positions.
// A value whose positions are all on might have been added; one with any bit off never was.
// Bits are never turned off, because another value may need the same bit.
export class BloomFilter {
	readonly bits: number;
	readonly hashes: number;
	#bytes: Uint8Array;
	#bitsOn = 0;
	#steps: Step[] = [];
	#capture: boolean;

	constructor(bits: number, hashes: number, trace = false) {
		if (!Number.isInteger(bits) || bits < 1 || bits > MAX_BITS)
			throw new RangeError('bits must be an integer from 1 to 2147483648');
		if (!Number.isInteger(hashes) || hashes < 1 || hashes > 32)
			throw new RangeError('hashes must be an integer from 1 to 32');
		this.bits = bits;
		this.hashes = hashes;
		this.#bytes = new Uint8Array(Math.ceil(bits / 8));
		this.#capture = trace;
	}

	// Rebuild a filter from toBytes(), for example one built on a server and shipped to a browser.
	static fromBytes(bits: number, hashes: number, bytes: Uint8Array, trace = false): BloomFilter {
		const filter = new BloomFilter(bits, hashes, trace);
		if (bytes.length !== filter.#bytes.length)
			throw new RangeError('bytes must be exactly ceil(bits / 8) long');
		if (bits % 8 && bytes[bytes.length - 1] >> (bits % 8))
			throw new RangeError('a bit past the last one is set');
		filter.#bytes.set(bytes);
		for (let bit = 0; bit < bits; bit++) if (filter.#isOn(bit)) filter.#bitsOn++;
		return filter;
	}

	get bitsOn(): number {
		return this.#bitsOn;
	}

	// The chance that a value never added finds all its bits on: the fraction on, per hash.
	estimatedFalsePositiveRate(): number {
		return (this.#bitsOn / this.bits) ** this.hashes;
	}

	// Double hashing: the i-th position is (h1 + i × h2) mod bits, so two hashes stand in for k.
	positions(value: string): number[] {
		const [first, second] = hashPair(value);
		return Array.from({ length: this.hashes }, (_, i) => (first + i * second) % this.bits);
	}

	// Turn on every one of the value's bits. True if any was off, so the filter changed.
	add(value: string): boolean {
		let changed = false;
		for (const bit of this.#start(value)) {
			const on = this.#isOn(bit);
			this.#record('set', value, bit, on ? 1 : 0);
			if (on) continue;
			this.#bytes[bit >>> 3] |= 1 << (bit & 7);
			this.#bitsOn++;
			changed = true;
		}
		return changed;
	}

	// False: definitely never added. True: maybe, because other values may have set these bits.
	mightContain(value: string): boolean {
		for (const bit of this.#start(value)) {
			const on = this.#isOn(bit);
			this.#record('test', value, bit, on ? 1 : 0);
			if (!on) return false;
		}
		return true;
	}

	toBytes(): Uint8Array {
		return this.#bytes.slice();
	}

	trace(): Step[] {
		return this.#steps.map((step) => ({ ...step }));
	}

	#start(value: string): number[] {
		this.#steps = [];
		const [first, second] = hashPair(value);
		this.#record('hash', value, first, second);
		return this.positions(value);
	}

	#isOn(bit: number): boolean {
		return (this.#bytes[bit >>> 3] & (1 << (bit & 7))) !== 0;
	}

	#record(kind: Step['kind'], value: string, a: number, b: number): void {
		if (this.#capture) this.#steps.push({ kind, value, a, b });
	}
}

const maxBits = 1 << 31

// HashPair returns two 32-bit hashes of the value's UTF-8 bytes: FNV-1a from two
// different starting values, each finished with MurmurHash3's final mix. Alone,
// FNV-1a's low bits depend only on the low bits of each byte, and a position mod a
// small size reads mostly low bits.
func HashPair(value string) (uint32, uint32) {
	return finish(fnv1a(value, 0x811c9dc5)), finish(fnv1a(value, 0x050c5d1f))
}

func fnv1a(value string, basis uint32) uint32 {
	hash := basis
	for i := 0; i < len(value); i++ {
		hash ^= uint32(value[i])
		hash *= 16777619
	}
	return hash
}

func finish(hash uint32) uint32 {
	hash ^= hash >> 16
	hash *= 0x85ebca6b
	hash ^= hash >> 13
	hash *= 0xc2b2ae35
	hash ^= hash >> 16
	return hash
}

// Size is a filter's bit count and hash count.
type Size struct{ Bits, Hashes int }

// SizeFor sizes a filter for about expectedItems values at a target false positive rate.
func SizeFor(expectedItems int, falsePositiveRate float64) (Size, error) {
	if expectedItems < 1 || expectedItems > maxBits {
		return Size{}, errors.New("expected items must be an integer from 1 to 2147483648")
	}
	if !(falsePositiveRate > 0 && falsePositiveRate < 1) {
		return Size{}, errors.New("false positive rate must be greater than 0 and less than 1")
	}
	// m = −n ln p / (ln 2)², then k = (m / n) ln 2, the hash count that makes the rate smallest.
	ln2 := math.Ln2
	bits := math.Ceil(-float64(expectedItems) * math.Log(falsePositiveRate) / (ln2 * ln2))
	if bits > maxBits {
		return Size{}, errors.New("the filter would need more than 2147483648 bits")
	}
	hashes := int(math.Round(bits / float64(expectedItems) * ln2))
	return Size{int(bits), min(32, max(1, hashes))}, nil
}

type Step struct {
	Kind  string `json:"kind"`
	Value string `json:"value"`
	// hash: the first 32-bit hash. set and test: the bit's position.
	A int64 `json:"a"`
	// hash: the second hash. set: 1 if the bit was already on. test: 1 if the bit is on.
	B int64 `json:"b"`
}

// BloomFilter is a row of bits, all off to start. Adding a value turns on the bits
// at its positions. A value whose positions are all on might have been added; one
// with any bit off never was. Bits are never turned off, because another value may
// need the same bit.
type BloomFilter struct {
	bits    int
	hashes  int
	data    []byte
	bitsOn  int
	steps   []Step
	capture bool
}

func NewBloomFilter(bits, hashes int, trace bool) (*BloomFilter, error) {
	if bits < 1 || bits > maxBits {
		return nil, errors.New("bits must be an integer from 1 to 2147483648")
	}
	if hashes < 1 || hashes > 32 {
		return nil, errors.New("hashes must be an integer from 1 to 32")
	}
	return &BloomFilter{bits: bits, hashes: hashes, data: make([]byte, (bits+7)/8), capture: trace}, nil
}

// FromBytes rebuilds a filter from Bytes(), for example one built on a server and
// shipped to a client.
func FromBytes(bits, hashes int, data []byte, trace bool) (*BloomFilter, error) {
	f, err := NewBloomFilter(bits, hashes, trace)
	if err != nil {
		return nil, err
	}
	if len(data) != len(f.data) {
		return nil, errors.New("bytes must be exactly ceil(bits / 8) long")
	}
	if bits%8 != 0 && data[len(data)-1]>>(bits%8) != 0 {
		return nil, errors.New("a bit past the last one is set")
	}
	copy(f.data, data)
	for bit := range bits {
		if f.isOn(bit) {
			f.bitsOn++
		}
	}
	return f, nil
}

func (f *BloomFilter) Bits() int   { return f.bits }
func (f *BloomFilter) Hashes() int { return f.hashes }
func (f *BloomFilter) BitsOn() int { return f.bitsOn }

// EstimatedFalsePositiveRate is the chance that a value never added finds all its
// bits on: the fraction on, per hash.
func (f *BloomFilter) EstimatedFalsePositiveRate() float64 {
	return math.Pow(float64(f.bitsOn)/float64(f.bits), float64(f.hashes))
}

// Positions uses double hashing: the i-th position is (h1 + i × h2) mod bits, so
// two hashes stand in for k.
func (f *BloomFilter) Positions(value string) []int {
	first, second := HashPair(value)
	positions := make([]int, f.hashes)
	for i := range positions {
		positions[i] = int((uint64(first) + uint64(i)*uint64(second)) % uint64(f.bits))
	}
	return positions
}

// Add turns on every one of the value's bits. It reports whether any was off, so
// the filter changed.
func (f *BloomFilter) Add(value string) bool {
	changed := false
	for _, bit := range f.start(value) {
		on := f.isOn(bit)
		f.record("set", value, int64(bit), flag(on))
		if on {
			continue
		}
		f.data[bit>>3] |= 1 << (bit & 7)
		f.bitsOn++
		changed = true
	}
	return changed
}

// MightContain returns false when the value was definitely never added, and true
// for maybe, because other values may have set these bits.
func (f *BloomFilter) MightContain(value string) bool {
	for _, bit := range f.start(value) {
		on := f.isOn(bit)
		f.record("test", value, int64(bit), flag(on))
		if !on {
			return false
		}
	}
	return true
}

func (f *BloomFilter) Bytes() []byte { return append([]byte{}, f.data...) }
func (f *BloomFilter) Trace() []Step { return append([]Step{}, f.steps...) }

func (f *BloomFilter) start(value string) []int {
	f.steps = nil
	first, second := HashPair(value)
	f.record("hash", value, int64(first), int64(second))
	return f.Positions(value)
}

func (f *BloomFilter) isOn(bit int) bool { return f.data[bit>>3]&(1<<(bit&7)) != 0 }

func (f *BloomFilter) record(kind, value string, a, b int64) {
	if f.capture {
		f.steps = append(f.steps, Step{kind, value, a, b})
	}
}

func flag(on bool) int64 {
	if on {
		return 1
	}
	return 0
}