bloomfilter.gno

  1// Package bloomfilter ports the classic Bloom filter data structure to
  2// gno.land: a fixed-size bit array plus k independent hash functions that
  3// let you test set membership with zero false negatives and a small, bounded
  4// false-positive rate — without ever storing the actual items.
  5//
  6// Membership is checked via double hashing (Kirsch–Mitzenmacher): two base
  7// hashes h1, h2 are combined as h1 + i*h2 to derive k bit positions per item,
  8// avoiding the cost of k independent hash functions.
  9//
 10// Add is a crossing function per the gno 0.9 interrealm convention (it takes
 11// `cur realm` as its first parameter); MightContain and Stats are read-only.
 12package bloomfilter
 13
 14import (
 15	"chain"
 16	"strconv"
 17	"strings"
 18)
 19
 20const (
 21	numBits    = 2048 // m: total bits in the filter
 22	numBytes   = numBits / 8
 23	numHashes  = 5 // k: hash functions per item (double-hashed from 2 bases)
 24	maxHistory = 20 // most recent additions kept for Render display only
 25)
 26
 27var (
 28	bits    [numBytes]byte // the bit array itself
 29	setBits int            // running count of bits currently set to 1
 30	added   int            // total Add calls (may double-count re-adds)
 31	history []string       // last few added items, for the Render view
 32)
 33
 34// fnv1a is a minimal FNV-1a 32-bit hash over a string, parameterized by an
 35// offset basis so two calls with different seeds behave as independent
 36// hash functions for the double-hashing scheme below.
 37func fnv1a(s string, seed uint32) uint32 {
 38	h := seed
 39	for i := 0; i < len(s); i++ {
 40		h ^= uint32(s[i])
 41		h *= 16777619 // FNV prime
 42	}
 43	return h
 44}
 45
 46// positions returns the k bit positions an item hashes to.
 47func positions(item string) [numHashes]uint32 {
 48	h1 := fnv1a(item, 2166136261)
 49	h2 := fnv1a(item, 84696351)
 50	if h2 == 0 {
 51		h2 = 1 // keep the second hash non-degenerate
 52	}
 53	var pos [numHashes]uint32
 54	for i := 0; i < numHashes; i++ {
 55		pos[i] = (h1 + uint32(i)*h2) % numBits
 56	}
 57	return pos
 58}
 59
 60// setBit sets bit `pos` and reports whether it was previously unset.
 61func setBit(pos uint32) bool {
 62	byteIdx := pos / 8
 63	mask := byte(1 << (pos % 8))
 64	if bits[byteIdx]&mask != 0 {
 65		return false
 66	}
 67	bits[byteIdx] |= mask
 68	return true
 69}
 70
 71// testBit reports whether bit `pos` is set.
 72func testBit(pos uint32) bool {
 73	byteIdx := pos / 8
 74	mask := byte(1 << (pos % 8))
 75	return bits[byteIdx]&mask != 0
 76}
 77
 78// Add inserts `item` into the filter. Crossing function: any caller (user or
 79// realm) may add, matching this demo's open-membership model.
 80func Add(cur realm, item string) {
 81	if item == "" {
 82		panic("bloomfilter: empty item")
 83	}
 84	for _, pos := range positions(item) {
 85		if setBit(pos) {
 86			setBits++
 87		}
 88	}
 89	added++
 90	history = append(history, item)
 91	if len(history) > maxHistory {
 92		history = history[len(history)-maxHistory:]
 93	}
 94	chain.Emit("Add", "item", item, "totalAdded", strconv.Itoa(added))
 95}
 96
 97// MightContain reports whether `item` was possibly added before. A false
 98// (definitely-not-a-member) answer is always correct; a true answer can
 99// occasionally be a false positive, never a false negative.
100func MightContain(item string) bool {
101	if item == "" {
102		return false
103	}
104	for _, pos := range positions(item) {
105		if !testBit(pos) {
106			return false
107		}
108	}
109	return true
110}
111
112// FalsePositiveRatePercent estimates the current false-positive rate, in
113// percent, as (bitsSet/m)^k — the standard Bloom filter approximation once
114// bits are randomly distributed. Computed with plain integer/float math to
115// avoid depending on math.Exp/Pow availability.
116func FalsePositiveRatePercent() float64 {
117	fillRatio := float64(setBits) / float64(numBits)
118	rate := 1.0
119	for i := 0; i < numHashes; i++ {
120		rate *= fillRatio
121	}
122	return rate * 100
123}
124
125// Stats returns the raw counters backing the Render view and
126// FalsePositiveRatePercent: (itemsAdded, bitsSet, totalBits, hashCount).
127func Stats() (int, int, int, int) {
128	return added, setBits, numBits, numHashes
129}
130
131// Render draws the filter's current stats and recently-added items as
132// Markdown for gnoweb.
133func Render(path string) string {
134	var b strings.Builder
135
136	b.WriteString("# Bloom Filter\n\n")
137	b.WriteString("A probabilistic set membership test: `Add` an item, then " +
138		"`MightContain` it back. False positives are possible; false " +
139		"negatives never happen. The filter never stores the items " +
140		"themselves — only " + strconv.Itoa(numBits) + " bits.\n\n")
141
142	fillRatio := float64(setBits) / float64(numBits) * 100
143
144	b.WriteString("## Stats\n\n")
145	b.WriteString("- **Bits (m):** " + strconv.Itoa(numBits) + "\n")
146	b.WriteString("- **Hash functions (k):** " + strconv.Itoa(numHashes) + "\n")
147	b.WriteString("- **Items added:** " + strconv.Itoa(added) + "\n")
148	b.WriteString("- **Bits set:** " + strconv.Itoa(setBits) + " (" +
149		strconv.FormatFloat(fillRatio, 'f', 1, 64) + "% full)\n")
150	b.WriteString("- **Estimated false-positive rate:** " +
151		strconv.FormatFloat(FalsePositiveRatePercent(), 'f', 3, 64) + "%\n\n")
152
153	b.WriteString("## Recently added\n\n")
154	if len(history) == 0 {
155		b.WriteString("_Nothing added yet — call `Add` with an item string._\n")
156		return b.String()
157	}
158	for i := len(history) - 1; i >= 0; i-- {
159		b.WriteString("- `" + history[i] + "`\n")
160	}
161
162	return b.String()
163}