Realm

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}
164