-
Notifications
You must be signed in to change notification settings - Fork 2
/
gcs.go
541 lines (452 loc) · 15.1 KB
/
gcs.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
// Copyright (c) 2016-2017 The btcsuite developers
// Copyright (c) 2016-2017 The Lightning Network Developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.
package gcs
import (
"bytes"
"fmt"
"io"
"sort"
"github.com/aead/siphash"
"github.com/eager7/dogd/wire"
"github.com/kkdai/bstream"
)
// Inspired by https://github.com/rasky/gcs
var (
// ErrNTooBig signifies that the filter can't handle N items.
ErrNTooBig = fmt.Errorf("N is too big to fit in uint32")
// ErrPTooBig signifies that the filter can't handle `1/2**P`
// collision probability.
ErrPTooBig = fmt.Errorf("P is too big to fit in uint32")
)
const (
// KeySize is the size of the byte array required for key material for
// the SipHash keyed hash function.
KeySize = 16
// varIntProtoVer is the protocol version to use for serializing N as a
// VarInt.
varIntProtoVer uint32 = 0
)
// fastReduction calculates a mapping that's more ore less equivalent to: x mod
// N. However, instead of using a mod operation, which using a non-power of two
// will lead to slowness on many processors due to unnecessary division, we
// instead use a "multiply-and-shift" trick which eliminates all divisions,
// described in:
// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
//
// * v * N >> log_2(N)
//
// In our case, using 64-bit integers, log_2 is 64. As most processors don't
// support 128-bit arithmetic natively, we'll be super portable and unfold the
// operation into several operations with 64-bit arithmetic. As inputs, we the
// number to reduce, and our modulus N divided into its high 32-bits and lower
// 32-bits.
func fastReduction(v, nHi, nLo uint64) uint64 {
// First, we'll spit the item we need to reduce into its higher and
// lower bits.
vhi := v >> 32
vlo := uint64(uint32(v))
// Then, we distribute multiplication over each part.
vnphi := vhi * nHi
vnpmid := vhi * nLo
npvmid := nHi * vlo
vnplo := vlo * nLo
// We calculate the carry bit.
carry := (uint64(uint32(vnpmid)) + uint64(uint32(npvmid)) +
(vnplo >> 32)) >> 32
// Last, we add the high bits, the middle bits, and the carry.
v = vnphi + (vnpmid >> 32) + (npvmid >> 32) + carry
return v
}
// Filter describes an immutable filter that can be built from a set of data
// elements, serialized, deserialized, and queried in a thread-safe manner. The
// serialized form is compressed as a Golomb Coded Set (GCS), but does not
// include N or P to allow the user to encode the metadata separately if
// necessary. The hash function used is SipHash, a keyed function; the key used
// in building the filter is required in order to match filter values and is
// not included in the serialized form.
type Filter struct {
n uint32
p uint8
modulusNP uint64
filterData []byte
}
// BuildGCSFilter builds a new GCS filter with the collision probability of
// `1/(2**P)`, key `key`, and including every `[]byte` in `data` as a member of
// the set.
func BuildGCSFilter(P uint8, M uint64, key [KeySize]byte, data [][]byte) (*Filter, error) {
// Some initial parameter checks: make sure we have data from which to
// build the filter, and make sure our parameters will fit the hash
// function we're using.
if uint64(len(data)) >= (1 << 32) {
return nil, ErrNTooBig
}
if P > 32 {
return nil, ErrPTooBig
}
// Create the filter object and insert metadata.
f := Filter{
n: uint32(len(data)),
p: P,
}
// First we'll compute the value of m, which is the modulus we use
// within our finite field. We want to compute: mScalar * 2^P. We use
// math.Round in order to round the value up, rather than down.
f.modulusNP = uint64(f.n) * M
// Shortcut if the filter is empty.
if f.n == 0 {
return &f, nil
}
// Build the filter.
values := make([]uint64, 0, len(data))
b := bstream.NewBStreamWriter(0)
// Insert the hash (fast-ranged over a space of N*P) of each data
// element into a slice and sort the slice. This can be greatly
// optimized with native 128-bit multiplication, but we're going to be
// fully portable for now.
//
// First, we cache the high and low bits of modulusNP for the
// multiplication of 2 64-bit integers into a 128-bit integer.
nphi := f.modulusNP >> 32
nplo := uint64(uint32(f.modulusNP))
for _, d := range data {
// For each datum, we assign the initial hash to a uint64.
v := siphash.Sum64(d, &key)
v = fastReduction(v, nphi, nplo)
values = append(values, v)
}
sort.Slice(values, func(i, j int) bool { return values[i] < values[j] })
// Write the sorted list of values into the filter bitstream,
// compressing it using Golomb coding.
var value, lastValue, remainder uint64
for _, v := range values {
// Calculate the difference between this value and the last,
// modulo P.
remainder = (v - lastValue) & ((uint64(1) << f.p) - 1)
// Calculate the difference between this value and the last,
// divided by P.
value = (v - lastValue - remainder) >> f.p
lastValue = v
// Write the P multiple into the bitstream in unary; the
// average should be around 1 (2 bits - 0b10).
for value > 0 {
b.WriteBit(true)
value--
}
b.WriteBit(false)
// Write the remainder as a big-endian integer with enough bits
// to represent the appropriate collision probability.
b.WriteBits(remainder, int(f.p))
}
// Copy the bitstream into the filter object and return the object.
f.filterData = b.Bytes()
return &f, nil
}
// FromBytes deserializes a GCS filter from a known N, P, and serialized filter
// as returned by Bytes().
func FromBytes(N uint32, P uint8, M uint64, d []byte) (*Filter, error) {
// Basic sanity check.
if P > 32 {
return nil, ErrPTooBig
}
// Create the filter object and insert metadata.
f := &Filter{
n: N,
p: P,
}
// First we'll compute the value of m, which is the modulus we use
// within our finite field. We want to compute: mScalar * 2^P. We use
// math.Round in order to round the value up, rather than down.
f.modulusNP = uint64(f.n) * M
// Copy the filter.
f.filterData = make([]byte, len(d))
copy(f.filterData, d)
return f, nil
}
// FromNBytes deserializes a GCS filter from a known P, and serialized N and
// filter as returned by NBytes().
func FromNBytes(P uint8, M uint64, d []byte) (*Filter, error) {
buffer := bytes.NewBuffer(d)
N, err := wire.ReadVarInt(buffer, varIntProtoVer)
if err != nil {
return nil, err
}
if N >= (1 << 32) {
return nil, ErrNTooBig
}
return FromBytes(uint32(N), P, M, buffer.Bytes())
}
// Bytes returns the serialized format of the GCS filter, which does not
// include N or P (returned by separate methods) or the key used by SipHash.
func (f *Filter) Bytes() ([]byte, error) {
filterData := make([]byte, len(f.filterData))
copy(filterData, f.filterData)
return filterData, nil
}
// NBytes returns the serialized format of the GCS filter with N, which does
// not include P (returned by a separate method) or the key used by SipHash.
func (f *Filter) NBytes() ([]byte, error) {
var buffer bytes.Buffer
buffer.Grow(wire.VarIntSerializeSize(uint64(f.n)) + len(f.filterData))
err := wire.WriteVarInt(&buffer, varIntProtoVer, uint64(f.n))
if err != nil {
return nil, err
}
_, err = buffer.Write(f.filterData)
if err != nil {
return nil, err
}
return buffer.Bytes(), nil
}
// PBytes returns the serialized format of the GCS filter with P, which does
// not include N (returned by a separate method) or the key used by SipHash.
func (f *Filter) PBytes() ([]byte, error) {
filterData := make([]byte, len(f.filterData)+1)
filterData[0] = f.p
copy(filterData[1:], f.filterData)
return filterData, nil
}
// NPBytes returns the serialized format of the GCS filter with N and P, which
// does not include the key used by SipHash.
func (f *Filter) NPBytes() ([]byte, error) {
var buffer bytes.Buffer
buffer.Grow(wire.VarIntSerializeSize(uint64(f.n)) + 1 + len(f.filterData))
err := wire.WriteVarInt(&buffer, varIntProtoVer, uint64(f.n))
if err != nil {
return nil, err
}
err = buffer.WriteByte(f.p)
if err != nil {
return nil, err
}
_, err = buffer.Write(f.filterData)
if err != nil {
return nil, err
}
return buffer.Bytes(), nil
}
// P returns the filter's collision probability as a negative power of 2 (that
// is, a collision probability of `1/2**20` is represented as 20).
func (f *Filter) P() uint8 {
return f.p
}
// N returns the size of the data set used to build the filter.
func (f *Filter) N() uint32 {
return f.n
}
// Match checks whether a []byte value is likely (within collision probability)
// to be a member of the set represented by the filter.
func (f *Filter) Match(key [KeySize]byte, data []byte) (bool, error) {
// Create a filter bitstream.
filterData, err := f.Bytes()
if err != nil {
return false, err
}
b := bstream.NewBStreamReader(filterData)
// We take the high and low bits of modulusNP for the multiplication
// of 2 64-bit integers into a 128-bit integer.
nphi := f.modulusNP >> 32
nplo := uint64(uint32(f.modulusNP))
// Then we hash our search term with the same parameters as the filter.
term := siphash.Sum64(data, &key)
term = fastReduction(term, nphi, nplo)
// Go through the search filter and look for the desired value.
var value uint64
for i := uint32(0); i < f.N(); i++ {
// Read the difference between previous and new value from
// bitstream.
delta, err := f.readFullUint64(b)
if err != nil {
if err == io.EOF {
return false, nil
}
return false, err
}
// Add the delta to the previous value.
value += delta
switch {
// The current value matches our query term, success.
case value == term:
return true, nil
// The current value is greater than our query term, thus no
// future decoded value can match because the values
// monotonically increase.
case value > term:
return false, nil
}
}
// All values were decoded and none produced a successful match. This
// indicates that the items in the filter were all smaller than our
// target.
return false, nil
}
// MatchAny returns checks whether any []byte value is likely (within collision
// probability) to be a member of the set represented by the filter faster than
// calling Match() for each value individually.
func (f *Filter) MatchAny(key [KeySize]byte, data [][]byte) (bool, error) {
// TODO(conner): add real heuristics to query optimization
switch {
case len(data) >= int(f.N()/2):
return f.HashMatchAny(key, data)
default:
return f.ZipMatchAny(key, data)
}
}
// ZipMatchAny returns checks whether any []byte value is likely (within
// collision probability) to be a member of the set represented by the filter
// faster than calling Match() for each value individually.
//
// NOTE: This method should outperform HashMatchAny when the number of query
// entries is smaller than the number of filter entries.
func (f *Filter) ZipMatchAny(key [KeySize]byte, data [][]byte) (bool, error) {
// Basic anity check.
if len(data) == 0 {
return false, nil
}
// Create a filter bitstream.
filterData, err := f.Bytes()
if err != nil {
return false, err
}
b := bstream.NewBStreamReader(filterData)
// Create an uncompressed filter of the search values.
values := make([]uint64, 0, len(data))
// First, we cache the high and low bits of modulusNP for the
// multiplication of 2 64-bit integers into a 128-bit integer.
nphi := f.modulusNP >> 32
nplo := uint64(uint32(f.modulusNP))
for _, d := range data {
// For each datum, we assign the initial hash to a uint64.
v := siphash.Sum64(d, &key)
// We'll then reduce the value down to the range of our
// modulus.
v = fastReduction(v, nphi, nplo)
values = append(values, v)
}
sort.Slice(values, func(i, j int) bool { return values[i] < values[j] })
querySize := len(values)
// Zip down the filters, comparing values until we either run out of
// values to compare in one of the filters or we reach a matching
// value.
var (
value uint64
queryIndex int
)
out:
for i := uint32(0); i < f.N(); i++ {
// Advance filter we're searching or return false if we're at
// the end because nothing matched.
delta, err := f.readFullUint64(b)
if err != nil {
if err == io.EOF {
return false, nil
}
return false, err
}
value += delta
for {
switch {
// All query items have been exhausted and we haven't
// had a match, therefore there are no matches.
case queryIndex == querySize:
return false, nil
// The current item in the query matches the decoded
// value, success.
case values[queryIndex] == value:
return true, nil
// The current item in the query is greater than the
// current decoded value, continue to decode the next
// delta and try again.
case values[queryIndex] > value:
continue out
}
queryIndex++
}
}
// All items in the filter were decoded and none produced a successful
// match.
return false, nil
}
// HashMatchAny returns checks whether any []byte value is likely (within
// collision probability) to be a member of the set represented by the filter
// faster than calling Match() for each value individually.
//
// NOTE: This method should outperform MatchAny if the number of query entries
// approaches the number of filter entries, len(data) >= f.N().
func (f *Filter) HashMatchAny(key [KeySize]byte, data [][]byte) (bool, error) {
// Basic sanity check.
if len(data) == 0 {
return false, nil
}
// Create a filter bitstream.
filterData, err := f.Bytes()
if err != nil {
return false, err
}
b := bstream.NewBStreamReader(filterData)
var (
values = make(map[uint32]struct{}, f.N())
lastValue uint64
)
// First, decompress the filter and construct an index of the keys
// contained within the filter. Index construction terminates after all
// values have been read from the bitstream.
for {
// Read the next diff value from the filter, add it to the
// last value, and set the new value in the index.
value, err := f.readFullUint64(b)
if err == nil {
lastValue += value
values[uint32(lastValue)] = struct{}{}
continue
} else if err == io.EOF {
break
}
return false, err
}
// We cache the high and low bits of modulusNP for the multiplication of
// 2 64-bit integers into a 128-bit integer.
nphi := f.modulusNP >> 32
nplo := uint64(uint32(f.modulusNP))
// Finally, run through the provided data items, querying the index to
// determine if the filter contains any elements of interest.
for _, d := range data {
// For each datum, we assign the initial hash to
// a uint64.
v := siphash.Sum64(d, &key)
// We'll then reduce the value down to the range
// of our modulus.
v = fastReduction(v, nphi, nplo)
if _, ok := values[uint32(v)]; !ok {
continue
}
return true, nil
}
return false, nil
}
// readFullUint64 reads a value represented by the sum of a unary multiple of
// the filter's P modulus (`2**P`) and a big-endian P-bit remainder.
func (f *Filter) readFullUint64(b *bstream.BStream) (uint64, error) {
var quotient uint64
// Count the 1s until we reach a 0.
c, err := b.ReadBit()
if err != nil {
return 0, err
}
for c {
quotient++
c, err = b.ReadBit()
if err != nil {
return 0, err
}
}
// Read P bits.
remainder, err := b.ReadBits(int(f.p))
if err != nil {
return 0, err
}
// Add the multiple and the remainder.
v := (quotient << f.p) + remainder
return v, nil
}