[systemd-devel] [PATCH] bus-bloom: Fix bloom filter calculation

[Lennart Poettering]

On Sat, 09.08.14 02:06, Denis Kenzior (denkenz at gmail.com) wrote:

Indeed!

Applied!

Thanks!

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


Lennart

-- 
Lennart Poettering, Red Hat