Line data Source code
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 4008 : static inline void set_bit(uint64_t filter[], unsigned long b) {
27 4008 : filter[b >> 6] |= 1ULL << (b & 63);
28 4008 : }
29 :
30 : static const sd_id128_t hash_keys[] = {
31 : SD_ID128_ARRAY(b9,66,0b,f0,46,70,47,c1,88,75,c4,9c,54,b9,bd,15),
32 : SD_ID128_ARRAY(aa,a1,54,a2,e0,71,4b,39,bf,e1,dd,2e,9f,c5,4a,3b),
33 : SD_ID128_ARRAY(63,fd,ae,be,cd,82,48,12,a1,6e,41,26,cb,fa,a0,c8),
34 : SD_ID128_ARRAY(23,be,45,29,32,d2,46,2d,82,03,52,28,fe,37,17,f5),
35 : SD_ID128_ARRAY(56,3b,bf,ee,5a,4f,43,39,af,aa,94,08,df,f0,fc,10),
36 : SD_ID128_ARRAY(31,80,c8,73,c7,ea,46,d3,aa,25,75,0f,9e,4c,09,29),
37 : SD_ID128_ARRAY(7d,f7,18,4b,7b,a4,44,d5,85,3c,06,e0,65,53,96,6d),
38 : SD_ID128_ARRAY(f2,77,e9,6f,93,b5,4e,71,9a,0c,34,88,39,25,bf,35),
39 : };
40 :
41 501 : static void bloom_add_data(
42 : uint64_t filter[], /* The filter bits */
43 : size_t size, /* Size of the filter in bytes */
44 : unsigned k, /* Number of hash functions */
45 : const void *data, /* Data to hash */
46 : size_t n) { /* Size of data to hash in bytes */
47 :
48 : uint8_t h[8];
49 : uint64_t m;
50 501 : unsigned w, i, c = 0;
51 : unsigned hash_index;
52 :
53 501 : assert(size > 0);
54 501 : assert(k > 0);
55 :
56 : /* Determine bits in filter */
57 501 : m = size * 8;
58 :
59 : /* Determine how many bytes we need to generate a bit index 0..m for this filter */
60 501 : w = (u64log2(m) + 7) / 8;
61 :
62 501 : assert(w <= sizeof(uint64_t));
63 :
64 : /* Make sure we have enough hash keys to generate m * k bits
65 : * of hash value. Note that SipHash24 generates 64 bits of
66 : * hash value for each 128 bits of hash key. */
67 501 : assert(k * w <= ELEMENTSOF(hash_keys) * 8);
68 :
69 4509 : for (i = 0, hash_index = 0; i < k; i++) {
70 4008 : uint64_t p = 0;
71 : unsigned d;
72 :
73 12024 : for (d = 0; d < w; d++) {
74 8016 : if (c <= 0) {
75 1002 : siphash24(h, data, n, hash_keys[hash_index++].bytes);
76 1002 : c += 8;
77 : }
78 :
79 8016 : p = (p << 8ULL) | (uint64_t) h[8 - c];
80 8016 : c--;
81 : }
82 :
83 4008 : p &= m - 1;
84 4008 : set_bit(filter, p);
85 : }
86 :
87 : /* log_debug("bloom: adding <%.*s>", (int) n, (char*) data); */
88 501 : }
89 :
90 237 : void bloom_add_pair(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b) {
91 : size_t n;
92 : char *c;
93 :
94 237 : assert(filter);
95 237 : assert(a);
96 237 : assert(b);
97 :
98 237 : n = strlen(a) + 1 + strlen(b);
99 237 : c = alloca(n + 1);
100 237 : strcpy(stpcpy(stpcpy(c, a), ":"), b);
101 :
102 237 : bloom_add_data(filter, size, k, c, n);
103 237 : }
104 :
105 97 : void bloom_add_prefixes(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b, char sep) {
106 : size_t n;
107 : char *c, *p;
108 :
109 97 : assert(filter);
110 97 : assert(a);
111 97 : assert(b);
112 :
113 97 : n = strlen(a) + 1 + strlen(b);
114 97 : c = alloca(n + 1);
115 :
116 97 : p = stpcpy(stpcpy(c, a), ":");
117 97 : strcpy(p, b);
118 :
119 97 : bloom_add_data(filter, size, k, c, n);
120 :
121 : for (;;) {
122 : char *e;
123 :
124 162 : e = strrchr(p, sep);
125 162 : if (!e)
126 60 : break;
127 :
128 102 : *(e + 1) = 0;
129 102 : bloom_add_data(filter, size, k, c, e - c + 1);
130 :
131 102 : if (e == p)
132 37 : break;
133 :
134 65 : *e = 0;
135 65 : bloom_add_data(filter, size, k, c, e - c);
136 65 : }
137 97 : }
138 :
139 76 : bool bloom_validate_parameters(size_t size, unsigned k) {
140 : uint64_t m;
141 : unsigned w;
142 :
143 76 : if (size <= 0)
144 0 : return false;
145 :
146 76 : if (k <= 0)
147 0 : return false;
148 :
149 76 : m = size * 8;
150 76 : w = (u64log2(m) + 7) / 8;
151 76 : if (w > sizeof(uint64_t))
152 0 : return false;
153 :
154 76 : if (k * w > ELEMENTSOF(hash_keys) * 8)
155 0 : return false;
156 :
157 76 : return true;
158 : }
|
