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