src/libsystemd/bus-bloom.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2013 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include "util.h"
  23 #include "siphash24.h"
  24 #include "bus-bloom.h"
  25
  26 static inline void set_bit(uint64_t filter[], unsigned b) {
  27         filter[b >> 6] |= 1ULL << (b & 63);
  28 }
  29
  30 #define HASH_KEY1 SD_ID128_MAKE(b9,66,0b,f0,46,70,47,c1,88,75,c4,9c,54,b9,bd,15)
  31 #define HASH_KEY2 SD_ID128_MAKE(aa,a1,54,a2,e0,71,4b,39,bf,e1,dd,2e,9f,c5,4a,3b)
  32
  33 static void bloom_add_data(uint64_t filter[BLOOM_SIZE/8], const void *data, size_t n) {
  34         uint8_t a[8], b[8];
  35         unsigned k = 0;
  36
  37         /*
  38          * Our bloom filter has the following parameters:
  39          *
  40          * m=512   (bits in the filter)
  41          * k=8     (hash functions)
  42          *
  43          * We calculate a two 64bit SipHash values (for two fixed but
  44          * randomly generated hash keys) of which we use 8 parts of 9 bits
  45          * as individual hash functions.
  46          *
  47          */
  48
  49         siphash24(a, data, n, HASH_KEY1.bytes);
  50         siphash24(b, data, n, HASH_KEY2.bytes);
  51
  52         assert_cc(BLOOM_SIZE*8 == 512);
  53
  54         for (k = 0; k < 8; k++)
  55                 set_bit(filter, ((uint16_t) a[k] << 1) ^ (uint16_t) b[k]);
  56
  57         /* log_debug("bloom: adding <%.*s>", (int) n, (char*) data); */
  58 }
  59
  60 void bloom_add_pair(uint64_t filter[BLOOM_SIZE/8], const char *a, const char *b) {
  61         size_t n;
  62         char *c;
  63
  64         assert(filter);
  65         assert(a);
  66         assert(b);
  67
  68         n = strlen(a) + 1 + strlen(b);
  69         c = alloca(n + 1);
  70         strcpy(stpcpy(stpcpy(c, a), ":"), b);
  71
  72         bloom_add_data(filter, c, n);
  73 }
  74
  75 void bloom_add_prefixes(uint64_t filter[BLOOM_SIZE/8], const char *a, const char *b, char sep) {
  76         size_t n;
  77         char *c, *p;
  78
  79         assert(filter);
  80         assert(a);
  81         assert(b);
  82
  83         n = strlen(a) + 1 + strlen(b);
  84         c = alloca(n + 1);
  85
  86         p = stpcpy(stpcpy(c, a), ":");
  87         strcpy(p, b);
  88
  89         for (;;) {
  90                 char *e;
  91
  92                 e = strrchr(p, sep);
  93                 if (!e || e == p)
  94                         break;
  95
  96                 *e = 0;
  97                 bloom_add_data(filter, c, e - c);
  98         }
  99 }