[systemd-devel] [PATCH] bus-bloom: Fix bloom filter calculation
Denis Kenzior
denkenz at gmail.com
Sat Aug 9 00:06:21 PDT 2014
i is being used incorrectly. It is used to refer to the number of
indexes calculated so far (out of k). However, it is also incremented
when a new hash key is being used. This means that the results are
inconsistent with the desired behavior described in PORTING-DBUS1
document.
The expected result is that for the default values of m and k (512, 8)
the 1st hash key should produce 4 indexes. The second hash key is used
for the next 4 and overall 8 indexes into m are calculated.
The current behavior results in 6 indexes being calculated, 4 coming
from hash key 1 and 2 others from hash key 5.
---
src/libsystemd/sd-bus/bus-bloom.c | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)
diff --git a/src/libsystemd/sd-bus/bus-bloom.c b/src/libsystemd/sd-bus/bus-bloom.c
index e154296..3556774 100644
--- a/src/libsystemd/sd-bus/bus-bloom.c
+++ b/src/libsystemd/sd-bus/bus-bloom.c
@@ -48,6 +48,7 @@ static void bloom_add_data(
uint8_t h[8];
uint64_t m;
unsigned w, i, c = 0;
+ unsigned hash_index;
assert(size > 0);
assert(k > 0);
@@ -65,13 +66,13 @@ static void bloom_add_data(
* hash value for each 128 bits of hash key. */
assert(k * w <= ELEMENTSOF(hash_keys) * 8);
- for (i = 0; i < k; i++) {
+ for (i = 0, hash_index = 0; i < k; i++) {
uint64_t p = 0;
unsigned d;
for (d = 0; d < w; d++) {
if (c <= 0) {
- siphash24(h, data, n, hash_keys[i++].bytes);
+ siphash24(h, data, n, hash_keys[hash_index++].bytes);
c += 8;
}
--
1.8.5.5
More information about the systemd-devel
mailing list