1implement Bloomfilter; 2 3include "sys.m"; 4 sys: Sys; 5include "sets.m"; 6 sets: Sets; 7 Set: import sets; 8include "keyring.m"; 9 keyring: Keyring; 10include "bloomfilter.m"; 11 12init() 13{ 14 sys = load Sys Sys->PATH; 15 sets = load Sets Sets->PATH; 16 sets->init(); 17 keyring = load Keyring Keyring->PATH; 18} 19 20Bits: adt { 21 d: array of byte; 22 n: int; # bits used 23 get: fn(bits: self ref Bits, n: int): int; 24}; 25 26filter(d: array of byte, logm, k: int): Set 27{ 28 if(logm < 3 || logm > 30) 29 raise "invalid bloom filter size"; 30 nb := 1 << logm; 31 f := array[nb / 8 + 1] of {* => byte 0}; # one extra zero to make sure set's not inverted. 32 bits := hashbits(d, logm * k); 33 while(k--){ 34 v := bits.get(logm); 35 f[v >> 3] |= byte 1 << (v & 7); 36 } 37 return sets->bytes2set(f); 38} 39 40hashbits(data: array of byte, n: int): ref Bits 41{ 42 d := array[((n + 7) / 8)] of byte; 43 digest := array[Keyring->SHA1dlen] of byte; 44 state := keyring->sha1(data, len data, nil, nil); 45 extra := array[2] of byte; 46 e := 0; 47 for(i := 0; i < len d; i += Keyring->SHA1dlen){ 48 extra[0] = byte e; 49 extra[1] = byte (e>>8); 50 e++; 51 state = keyring->sha1(extra, len extra, digest, state); 52 if(i + Keyring->SHA1dlen > len d) 53 digest = digest[0:len d - i]; 54 d[i:] = digest; 55 } 56 return ref Bits(d, 0); 57} 58 59# XXX could be more efficient. 60Bits.get(bits: self ref Bits, n: int): int 61{ 62 d := bits.d; 63 v := 0; 64 nb := bits.n; 65 for(i := 0; i < n; i++){ 66 j := nb + i; 67 if(int d[j >> 3] & (1 << (j & 7))) 68 v |= (1 << i); 69 } 70 bits.n += n; 71 return v; 72} 73