]>
Commit | Line | Data |
---|---|---|
53e1b683 | 1 | /* SPDX-License-Identifier: LGPL-2.1+ */ |
a56f19c4 LP |
2 | /*** |
3 | This file is part of systemd. | |
4 | ||
5 | Copyright 2013 Lennart Poettering | |
6 | ||
7 | systemd is free software; you can redistribute it and/or modify it | |
8 | under the terms of the GNU Lesser General Public License as published by | |
9 | the Free Software Foundation; either version 2.1 of the License, or | |
10 | (at your option) any later version. | |
11 | ||
12 | systemd is distributed in the hope that it will be useful, but | |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | Lesser General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU Lesser General Public License | |
18 | along with systemd; If not, see <http://www.gnu.org/licenses/>. | |
19 | ***/ | |
20 | ||
a56f19c4 | 21 | #include "bus-bloom.h" |
cf0fbc49 TA |
22 | #include "siphash24.h" |
23 | #include "util.h" | |
a56f19c4 | 24 | |
b28ff39f | 25 | static inline void set_bit(uint64_t filter[], unsigned long b) { |
a56f19c4 LP |
26 | filter[b >> 6] |= 1ULL << (b & 63); |
27 | } | |
28 | ||
b28ff39f LP |
29 | static const sd_id128_t hash_keys[] = { |
30 | SD_ID128_ARRAY(b9,66,0b,f0,46,70,47,c1,88,75,c4,9c,54,b9,bd,15), | |
31 | SD_ID128_ARRAY(aa,a1,54,a2,e0,71,4b,39,bf,e1,dd,2e,9f,c5,4a,3b), | |
32 | SD_ID128_ARRAY(63,fd,ae,be,cd,82,48,12,a1,6e,41,26,cb,fa,a0,c8), | |
33 | SD_ID128_ARRAY(23,be,45,29,32,d2,46,2d,82,03,52,28,fe,37,17,f5), | |
34 | SD_ID128_ARRAY(56,3b,bf,ee,5a,4f,43,39,af,aa,94,08,df,f0,fc,10), | |
35 | SD_ID128_ARRAY(31,80,c8,73,c7,ea,46,d3,aa,25,75,0f,9e,4c,09,29), | |
36 | SD_ID128_ARRAY(7d,f7,18,4b,7b,a4,44,d5,85,3c,06,e0,65,53,96,6d), | |
37 | SD_ID128_ARRAY(f2,77,e9,6f,93,b5,4e,71,9a,0c,34,88,39,25,bf,35), | |
38 | }; | |
39 | ||
40 | static void bloom_add_data( | |
41 | uint64_t filter[], /* The filter bits */ | |
42 | size_t size, /* Size of the filter in bytes */ | |
43 | unsigned k, /* Number of hash functions */ | |
44 | const void *data, /* Data to hash */ | |
45 | size_t n) { /* Size of data to hash in bytes */ | |
46 | ||
dbe81cbd | 47 | uint64_t h; |
b28ff39f LP |
48 | uint64_t m; |
49 | unsigned w, i, c = 0; | |
587f21d8 | 50 | unsigned hash_index; |
b28ff39f LP |
51 | |
52 | assert(size > 0); | |
53 | assert(k > 0); | |
54 | ||
55 | /* Determine bits in filter */ | |
56 | m = size * 8; | |
57 | ||
58 | /* Determine how many bytes we need to generate a bit index 0..m for this filter */ | |
59 | w = (u64log2(m) + 7) / 8; | |
60 | ||
61 | assert(w <= sizeof(uint64_t)); | |
62 | ||
63 | /* Make sure we have enough hash keys to generate m * k bits | |
64 | * of hash value. Note that SipHash24 generates 64 bits of | |
65 | * hash value for each 128 bits of hash key. */ | |
66 | assert(k * w <= ELEMENTSOF(hash_keys) * 8); | |
67 | ||
587f21d8 | 68 | for (i = 0, hash_index = 0; i < k; i++) { |
b28ff39f LP |
69 | uint64_t p = 0; |
70 | unsigned d; | |
71 | ||
72 | for (d = 0; d < w; d++) { | |
73 | if (c <= 0) { | |
933f9cae | 74 | h = siphash24(data, n, hash_keys[hash_index++].bytes); |
b28ff39f LP |
75 | c += 8; |
76 | } | |
77 | ||
dbe81cbd | 78 | p = (p << 8ULL) | (uint64_t) ((uint8_t *)&h)[8 - c]; |
b28ff39f LP |
79 | c--; |
80 | } | |
81 | ||
82 | p &= m - 1; | |
83 | set_bit(filter, p); | |
84 | } | |
f11e11e3 LP |
85 | |
86 | /* log_debug("bloom: adding <%.*s>", (int) n, (char*) data); */ | |
a56f19c4 LP |
87 | } |
88 | ||
b28ff39f | 89 | void bloom_add_pair(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b) { |
a56f19c4 LP |
90 | size_t n; |
91 | char *c; | |
92 | ||
93 | assert(filter); | |
94 | assert(a); | |
95 | assert(b); | |
96 | ||
97 | n = strlen(a) + 1 + strlen(b); | |
98 | c = alloca(n + 1); | |
99 | strcpy(stpcpy(stpcpy(c, a), ":"), b); | |
100 | ||
b28ff39f | 101 | bloom_add_data(filter, size, k, c, n); |
a56f19c4 LP |
102 | } |
103 | ||
b28ff39f | 104 | void bloom_add_prefixes(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b, char sep) { |
a56f19c4 LP |
105 | size_t n; |
106 | char *c, *p; | |
107 | ||
108 | assert(filter); | |
109 | assert(a); | |
110 | assert(b); | |
111 | ||
112 | n = strlen(a) + 1 + strlen(b); | |
113 | c = alloca(n + 1); | |
114 | ||
115 | p = stpcpy(stpcpy(c, a), ":"); | |
116 | strcpy(p, b); | |
117 | ||
7cd4dbe9 DH |
118 | bloom_add_data(filter, size, k, c, n); |
119 | ||
a56f19c4 LP |
120 | for (;;) { |
121 | char *e; | |
122 | ||
123 | e = strrchr(p, sep); | |
7cd4dbe9 DH |
124 | if (!e) |
125 | break; | |
126 | ||
127 | *(e + 1) = 0; | |
128 | bloom_add_data(filter, size, k, c, e - c + 1); | |
129 | ||
130 | if (e == p) | |
a56f19c4 LP |
131 | break; |
132 | ||
133 | *e = 0; | |
b28ff39f | 134 | bloom_add_data(filter, size, k, c, e - c); |
a56f19c4 LP |
135 | } |
136 | } | |
b28ff39f LP |
137 | |
138 | bool bloom_validate_parameters(size_t size, unsigned k) { | |
139 | uint64_t m; | |
140 | unsigned w; | |
141 | ||
142 | if (size <= 0) | |
143 | return false; | |
144 | ||
145 | if (k <= 0) | |
146 | return false; | |
147 | ||
148 | m = size * 8; | |
149 | w = (u64log2(m) + 7) / 8; | |
150 | if (w > sizeof(uint64_t)) | |
151 | return false; | |
152 | ||
153 | if (k * w > ELEMENTSOF(hash_keys) * 8) | |
154 | return false; | |
155 | ||
156 | return true; | |
157 | } |