gcs_test.go raw
1 package filter
2
3 import (
4 "bytes"
5 "errors"
6 "fmt"
7 "math/bits"
8 "math/rand"
9 "slices"
10 "testing"
11 )
12
13 // golombBits is a test helper that encodes values with the given P and returns
14 // the raw bit string, so bit ordering can be asserted explicitly.
15 func golombBits(values []uint64, p uint) string {
16 var w bitWriter
17 for _, v := range values {
18 w.writeGolomb(v, p)
19 }
20 w.flush()
21 var s string
22 for _, b := range w.buf {
23 s += fmt.Sprintf("%08b", b)
24 }
25 return s
26 }
27
28 // bitsToBytes converts a string of '0' and '1' characters into packed bytes.
29 func bitsToBytes(t *testing.T, s string) []byte {
30 t.Helper()
31 if len(s)%8 != 0 {
32 t.Fatalf("bit string length %d is not a whole number of bytes", len(s))
33 }
34 out := make([]byte, len(s)/8)
35 for i := range s {
36 bit := byte(0)
37 switch s[i] {
38 case '0':
39 case '1':
40 bit = 1
41 default:
42 t.Fatalf("invalid bit %q at %d", s[i], i)
43 }
44 out[i/8] = out[i/8]<<1 | bit
45 }
46 return out
47 }
48
49 func TestGolombEncoding(t *testing.T) {
50 // BIP158's P=2 table: 0..9 encode as q unary bits followed by the
51 // big-endian remainder.
52 // The 38 bits above are zero-padded to 40 bits (5 bytes).
53 want := "000" + "001" + "010" + "011" +
54 "1000" + "1001" + "1010" + "1011" +
55 "11000" + "11001" + "00"
56 values := make([]uint64, 10)
57 for i := range values {
58 values[i] = uint64(i)
59 }
60 if got := golombBits(values, 2); got != want {
61 t.Fatalf("P=2 encoding = %s, want %s", got, want)
62 }
63
64 for _, p := range []uint{2, 4, 19} {
65 values := []uint64{0, 1, 2, 3, 7, 8, 15, 1 << p, 1<<p - 1, 1<<p + 12345}
66 encoded := golombBits(values, p)
67 encodedBytes := bitsToBytes(t, encoded)
68
69 r := bitReader{data: encodedBytes}
70 for i, want := range values {
71 got, err := r.readGolomb(p)
72 if err != nil {
73 t.Fatalf("P=%d read %d: %v", p, i, err)
74 }
75 if got != want {
76 t.Fatalf("P=%d read %d = %d, want %d", p, i, got, want)
77 }
78 }
79 if err := r.checkPadding(); err != nil {
80 t.Fatalf("P=%d padding: %v", p, err)
81 }
82 }
83 }
84
85 func TestBuildDecodeRoundTrip(t *testing.T) {
86 blockHash := [32]byte{}
87 blockHash[0] = 0xaa
88
89 tests := []struct {
90 name string
91 items [][]byte
92 }{
93 {"single", [][]byte{[]byte("hello")}},
94 {"duplicates", [][]byte{[]byte("a"), []byte("b"), []byte("a"), []byte("a")}},
95 {"empty item", [][]byte{{}, []byte("x")}},
96 {"many", func() [][]byte {
97 items := make([][]byte, 0, 300)
98 for i := 0; i < 300; i++ {
99 items = append(items, []byte(fmt.Sprintf("item-%d", i)))
100 }
101 return items
102 }()},
103 }
104
105 for _, tc := range tests {
106 t.Run(tc.name, func(t *testing.T) {
107 f := Build(tc.items, blockHash)
108 values, n, err := Decode(f)
109 if err != nil {
110 t.Fatalf("Decode: %v", err)
111 }
112 if n != uint64(len(tc.items)) {
113 t.Fatalf("N = %d, want %d", n, len(tc.items))
114 }
115 if len(values) != len(tc.items) {
116 t.Fatalf("decoded %d values, want %d", len(values), len(tc.items))
117 }
118 if !slices.IsSorted(values) {
119 t.Fatal("decoded values are not sorted")
120 }
121
122 for _, item := range tc.items {
123 ok, err := Match(f, blockHash, [][]byte{item})
124 if err != nil {
125 t.Fatalf("Match(%q): %v", item, err)
126 }
127 if !ok {
128 t.Fatalf("Match(%q) = false, want true", item)
129 }
130 }
131
132 // A different key must not (generally) interpret the same set.
133 other := blockHash
134 other[0] ^= 0xff
135 ok, err := Match(f, other, [][]byte{[]byte("definitely-not-present")})
136 if err != nil {
137 t.Fatalf("Match other key: %v", err)
138 }
139 if ok {
140 t.Fatal("query unexpectedly matched under a different key")
141 }
142 })
143 }
144
145 // Duplicate items map to the same value, so at least one decoded delta is
146 // zero. N still counts the raw items.
147 f := Build([][]byte{[]byte("dup"), []byte("dup"), []byte("dup")}, blockHash)
148 values, n, err := Decode(f)
149 if err != nil {
150 t.Fatal(err)
151 }
152 if n != 3 || len(values) != 3 {
153 t.Fatalf("N=%d len(values)=%d, want 3,3", n, len(values))
154 }
155 if values[0] != values[1] || values[1] != values[2] {
156 t.Fatalf("duplicate values not equal: %v", values)
157 }
158 }
159
160 func TestEmptyFilter(t *testing.T) {
161 var hash [32]byte
162 f := Build(nil, hash)
163 if !bytes.Equal(f, []byte{0x00}) {
164 t.Fatalf("Build(nil) = %x, want 00", f)
165 }
166 if f := Build([][]byte{}, hash); !bytes.Equal(f, []byte{0x00}) {
167 t.Fatalf("Build(empty) = %x, want 00", f)
168 }
169
170 ok, err := Match([]byte{0x00}, hash, [][]byte{[]byte("anything")})
171 if err != nil || ok {
172 t.Fatalf("Match(empty, query) = %v, %v; want false, nil", ok, err)
173 }
174 ok, err = MatchScript([]byte{0x00}, hash, [][]byte{[]byte("anything")})
175 if err != nil || ok {
176 t.Fatalf("MatchScript(empty, query) = %v, %v; want false, nil", ok, err)
177 }
178 ok, err = MatchAny([]byte{0x00}, hash, [][]byte{[]byte("anything")})
179 if err != nil || ok {
180 t.Fatalf("MatchAny(empty, query) = %v, %v; want false, nil", ok, err)
181 }
182
183 // Per the package contract, an empty query against an empty filter matches.
184 ok, err = Match([]byte{0x00}, hash, nil)
185 if err != nil || !ok {
186 t.Fatalf("Match(empty, nil query) = %v, %v; want true, nil", ok, err)
187 }
188
189 values, n, err := Decode([]byte{0x00})
190 if err != nil || n != 0 || values != nil {
191 t.Fatalf("Decode(empty) = %v, %d, %v; want nil, 0, nil", values, n, err)
192 }
193 }
194
195 func TestMatchMultipleQueries(t *testing.T) {
196 var hash [32]byte
197 items := [][]byte{[]byte("alpha"), []byte("beta"), []byte("gamma")}
198 f := Build(items, hash)
199
200 ok, err := Match(f, hash, [][]byte{[]byte("nope"), []byte("beta")})
201 if err != nil || !ok {
202 t.Fatalf("multi query = %v, %v; want true, nil", ok, err)
203 }
204 ok, err = Match(f, hash, [][]byte{[]byte("nope"), []byte("also-nope")})
205 if err != nil || ok {
206 t.Fatalf("negative multi query = %v, %v; want false, nil", ok, err)
207 }
208 }
209
210 func TestMalformedFilters(t *testing.T) {
211 var hash [32]byte
212
213 // A valid one-element filter for the value 0 (delta 0, P=19): 20 bits.
214 validZero := []byte{0x01, 0x00, 0x00, 0x00}
215 if _, _, err := Decode(validZero); err != nil {
216 t.Fatalf("valid zero filter: %v", err)
217 }
218
219 tests := []struct {
220 name string
221 filter []byte
222 target error
223 }{
224 {"empty input", nil, ErrInvalidFilter},
225 {"truncated CompactSize", []byte{0xfd, 0x01}, ErrInvalidFilter},
226 {"non-canonical CompactSize", []byte{0xfd, 0x01, 0x00}, ErrInvalidFilter},
227 {"absurd N", []byte{0xfe, 0x00, 0x00, 0x20, 0x00}, ErrTooManyElements},
228 {"missing payload", []byte{0x01}, ErrInvalidFilter},
229 {"truncated payload", []byte{0x01, 0x00}, ErrInvalidFilter},
230 {"non-zero padding", []byte{0x01, 0x00, 0x00, 0x01}, ErrInvalidFilter},
231 {"trailing zero byte", []byte{0x01, 0x00, 0x00, 0x00, 0x00}, ErrInvalidFilter},
232 {"empty filter trailing byte", []byte{0x00, 0x00}, ErrInvalidFilter},
233 {"zero element with payload", []byte{0x00, 0x01}, ErrInvalidFilter},
234 }
235 for _, tc := range tests {
236 t.Run(tc.name, func(t *testing.T) {
237 if _, _, err := Decode(tc.filter); !errors.Is(err, tc.target) {
238 t.Fatalf("Decode = %v, want %v", err, tc.target)
239 }
240 if _, err := Match(tc.filter, hash, [][]byte{[]byte("x")}); !errors.Is(err, tc.target) {
241 t.Fatalf("Match = %v, want %v", err, tc.target)
242 }
243 if _, err := Match(tc.filter, hash, nil); !errors.Is(err, tc.target) {
244 t.Fatalf("Match(nil query) = %v, want %v", err, tc.target)
245 }
246 })
247 }
248 }
249
250 // TestRandomInputsNeverPanic exercises Match and Decode with arbitrary short
251 // byte strings to ensure malformed filters cannot panic.
252 func TestRandomInputsNeverPanic(t *testing.T) {
253 rng := rand.New(rand.NewSource(0x158))
254 var hash [32]byte
255 for i := 0; i < 5000; i++ {
256 data := make([]byte, rng.Intn(64))
257 if _, err := rng.Read(data); err != nil {
258 t.Fatal(err)
259 }
260 query := make([][]byte, rng.Intn(4))
261 for j := range query {
262 query[j] = make([]byte, rng.Intn(8))
263 if _, err := rng.Read(query[j]); err != nil {
264 t.Fatal(err)
265 }
266 }
267 _, _ = Match(data, hash, query)
268 _, _ = Match(data, hash, nil)
269 _, _, _ = Decode(data)
270 }
271 }
272
273 func FuzzMatch(f *testing.F) {
274 f.Add([]byte{0x00}, []byte("x"))
275 f.Add([]byte{0x01, 0x00, 0x00, 0x00}, []byte("x"))
276 f.Add([]byte{0xfd, 0x01, 0x00, 0x00}, []byte(""))
277 f.Fuzz(func(t *testing.T, filter, query []byte) {
278 var hash [32]byte
279 _, _ = Match(filter, hash, [][]byte{query})
280 _, _, _ = Decode(filter)
281 })
282 }
283
284 // TestHashMapping checks the (hash * F) >> 64 mapping against a big.Int
285 // reference for a few values.
286 func TestHashMapping(t *testing.T) {
287 var hash [32]byte
288 hash[0] = 1
289 var key [16]byte
290 copy(key[:], hash[:16])
291 items := [][]byte{[]byte("a"), []byte("b"), []byte("c"), []byte("d")}
292 f := uint64(len(items)) * M
293 for _, item := range items {
294 h := siphash24(key, item)
295 // Compute the top 64 bits of h*F with math/bits, then compare with a
296 // shift/add decomposition that does not use Mul64.
297 hi, lo := bits.Mul64(h, f)
298 if hi != mulHiRef(h, f) || lo != mulLoRef(h, f) {
299 t.Fatalf("mapping for %q mismatch", item)
300 }
301 }
302 }
303
304 func mulHiRef(a, b uint64) uint64 {
305 // 32-bit limb decomposition of the high 64 bits of a*b.
306 a0, a1 := a&0xffffffff, a>>32
307 b0, b1 := b&0xffffffff, b>>32
308 p00 := a0 * b0
309 p01 := a0 * b1
310 p10 := a1 * b0
311 p11 := a1 * b1
312 mid := (p00 >> 32) + (p01 & 0xffffffff) + (p10 & 0xffffffff)
313 return p11 + (p01 >> 32) + (p10 >> 32) + (mid >> 32)
314 }
315
316 func mulLoRef(a, b uint64) uint64 {
317 a0, a1 := a&0xffffffff, a>>32
318 b0, b1 := b&0xffffffff, b>>32
319 return a0*b0 + ((a0*b1 + a1*b0) << 32)
320 }
321