]>
Commit | Line | Data |
---|---|---|
a56f19c4 LP |
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" | |
b67f541f | 23 | #include "siphash24.h" |
a56f19c4 LP |
24 | #include "bus-bloom.h" |
25 | ||
b28ff39f | 26 | static inline void set_bit(uint64_t filter[], unsigned long b) { |
a56f19c4 LP |
27 | filter[b >> 6] |= 1ULL << (b & 63); |
28 | } | |
29 | ||
b28ff39f LP |
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 | 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 | unsigned w, i, c = 0; | |
587f21d8 | 51 | unsigned hash_index; |
b28ff39f LP |
52 | |
53 | assert(size > 0); | |
54 | assert(k > 0); | |
55 | ||
56 | /* Determine bits in filter */ | |
57 | m = size * 8; | |
58 | ||
59 | /* Determine how many bytes we need to generate a bit index 0..m for this filter */ | |
60 | w = (u64log2(m) + 7) / 8; | |
61 | ||
62 | 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 | assert(k * w <= ELEMENTSOF(hash_keys) * 8); | |
68 | ||
587f21d8 | 69 | for (i = 0, hash_index = 0; i < k; i++) { |
b28ff39f LP |
70 | uint64_t p = 0; |
71 | unsigned d; | |
72 | ||
73 | for (d = 0; d < w; d++) { | |
74 | if (c <= 0) { | |
587f21d8 | 75 | siphash24(h, data, n, hash_keys[hash_index++].bytes); |
b28ff39f LP |
76 | c += 8; |
77 | } | |
78 | ||
79 | p = (p << 8ULL) | (uint64_t) h[8 - c]; | |
80 | c--; | |
81 | } | |
82 | ||
83 | p &= m - 1; | |
84 | set_bit(filter, p); | |
85 | } | |
f11e11e3 LP |
86 | |
87 | /* log_debug("bloom: adding <%.*s>", (int) n, (char*) data); */ | |
a56f19c4 LP |
88 | } |
89 | ||
b28ff39f | 90 | void bloom_add_pair(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b) { |
a56f19c4 LP |
91 | size_t n; |
92 | char *c; | |
93 | ||
94 | assert(filter); | |
95 | assert(a); | |
96 | assert(b); | |
97 | ||
98 | n = strlen(a) + 1 + strlen(b); | |
99 | c = alloca(n + 1); | |
100 | strcpy(stpcpy(stpcpy(c, a), ":"), b); | |
101 | ||
b28ff39f | 102 | bloom_add_data(filter, size, k, c, n); |
a56f19c4 LP |
103 | } |
104 | ||
b28ff39f | 105 | void bloom_add_prefixes(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b, char sep) { |
a56f19c4 LP |
106 | size_t n; |
107 | char *c, *p; | |
108 | ||
109 | assert(filter); | |
110 | assert(a); | |
111 | assert(b); | |
112 | ||
113 | n = strlen(a) + 1 + strlen(b); | |
114 | c = alloca(n + 1); | |
115 | ||
116 | p = stpcpy(stpcpy(c, a), ":"); | |
117 | strcpy(p, b); | |
118 | ||
119 | for (;;) { | |
120 | char *e; | |
121 | ||
122 | e = strrchr(p, sep); | |
123 | if (!e || e == p) | |
124 | break; | |
125 | ||
126 | *e = 0; | |
b28ff39f | 127 | bloom_add_data(filter, size, k, c, e - c); |
a56f19c4 LP |
128 | } |
129 | } | |
b28ff39f LP |
130 | |
131 | bool bloom_validate_parameters(size_t size, unsigned k) { | |
132 | uint64_t m; | |
133 | unsigned w; | |
134 | ||
135 | if (size <= 0) | |
136 | return false; | |
137 | ||
138 | if (k <= 0) | |
139 | return false; | |
140 | ||
141 | m = size * 8; | |
142 | w = (u64log2(m) + 7) / 8; | |
143 | if (w > sizeof(uint64_t)) | |
144 | return false; | |
145 | ||
146 | if (k * w > ELEMENTSOF(hash_keys) * 8) | |
147 | return false; | |
148 | ||
149 | return true; | |
150 | } |