]>
git.ipfire.org Git - thirdparty/systemd.git/blob - src/libsystemd/sd-bus/bus-bloom.c
2 This file is part of systemd.
4 Copyright 2013 Lennart Poettering
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.
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.
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/>.
20 #include "bus-bloom.h"
21 #include "siphash24.h"
24 static inline void set_bit(uint64_t filter
[], unsigned long b
) {
25 filter
[b
>> 6] |= 1ULL << (b
& 63);
28 static 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),
39 static 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 */
54 /* Determine bits in filter */
57 /* Determine how many bytes we need to generate a bit index 0..m for this filter */
58 w
= (u64log2(m
) + 7) / 8;
60 assert(w
<= sizeof(uint64_t));
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);
67 for (i
= 0, hash_index
= 0; i
< k
; i
++) {
71 for (d
= 0; d
< w
; d
++) {
73 h
= siphash24(data
, n
, hash_keys
[hash_index
++].bytes
);
77 p
= (p
<< 8ULL) | (uint64_t) ((uint8_t *)&h
)[8 - c
];
85 /* log_debug("bloom: adding <%.*s>", (int) n, (char*) data); */
88 void bloom_add_pair(uint64_t filter
[], size_t size
, unsigned k
, const char *a
, const char *b
) {
96 n
= strlen(a
) + 1 + strlen(b
);
98 strcpy(stpcpy(stpcpy(c
, a
), ":"), b
);
100 bloom_add_data(filter
, size
, k
, c
, n
);
103 void bloom_add_prefixes(uint64_t filter
[], size_t size
, unsigned k
, const char *a
, const char *b
, char sep
) {
111 n
= strlen(a
) + 1 + strlen(b
);
114 p
= stpcpy(stpcpy(c
, a
), ":");
117 bloom_add_data(filter
, size
, k
, c
, n
);
127 bloom_add_data(filter
, size
, k
, c
, e
- c
+ 1);
133 bloom_add_data(filter
, size
, k
, c
, e
- c
);
137 bool bloom_validate_parameters(size_t size
, unsigned k
) {
148 w
= (u64log2(m
) + 7) / 8;
149 if (w
> sizeof(uint64_t))
152 if (k
* w
> ELEMENTSOF(hash_keys
) * 8)