main.c
2.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
* Copyright (C) 2013 Freie Universität Berlin
*
* This file is subject to the terms and conditions of the GNU Lesser
* General Public License v2.1. See the file LICENSE in the top level
* directory for more details.
*/
/**
* @ingroup tests
* @{
*
* @file
* @brief Bloom filter test application
*
* @author Christian Mehlis <mehlis@inf.fu-berlin.de>
*
* @}
*/
#include <stdio.h>
#include <string.h>
#include <inttypes.h>
#include "xtimer.h"
#include "hashes.h"
#include "bloom.h"
#include "random.h"
#include "bitfield.h"
#define BLOOM_BITS (1UL << 12)
#define BLOOM_HASHF (8)
#define lenB 512
#define lenA (10 * 1000)
#define MAGIC_A 0xafafafaf
#define MAGIC_B 0x0c0c0c0c
#define myseed 0x83d385c0 /* random number */
#define BUF_SIZE 50
static uint32_t buf[BUF_SIZE];
static bloom_t bloom;
BITFIELD(bf, BLOOM_BITS);
hashfp_t hashes[BLOOM_HASHF] = {
(hashfp_t) fnv_hash, (hashfp_t) sax_hash, (hashfp_t) sdbm_hash,
(hashfp_t) djb2_hash, (hashfp_t) kr_hash, (hashfp_t) dek_hash,
(hashfp_t) rotating_hash, (hashfp_t) one_at_a_time_hash,
};
static void buf_fill(uint32_t *buf, int len)
{
for (int k = 0; k < len; k++) {
buf[k] = random_uint32();
}
}
int main(void)
{
xtimer_init();
bloom_init(&bloom, BLOOM_BITS, bf, hashes, BLOOM_HASHF);
printf("Testing Bloom filter.\n\n");
printf("m: %" PRIu32 " k: %" PRIu32 "\n\n", (uint32_t) bloom.m,
(uint32_t) bloom.k);
random_init(myseed);
unsigned long t1 = xtimer_now_usec();
for (int i = 0; i < lenB; i++) {
buf_fill(buf, BUF_SIZE);
buf[0] = MAGIC_B;
bloom_add(&bloom,
(uint8_t *) buf,
BUF_SIZE * sizeof(uint32_t) / sizeof(uint8_t));
}
unsigned long t2 = xtimer_now_usec();
printf("adding %d elements took %" PRIu32 "ms\n", lenB,
(uint32_t) (t2 - t1) / 1000);
int in = 0;
int not_in = 0;
unsigned long t3 = xtimer_now_usec();
for (int i = 0; i < lenA; i++) {
buf_fill(buf, BUF_SIZE);
buf[0] = MAGIC_A;
if (bloom_check(&bloom,
(uint8_t *) buf,
BUF_SIZE * sizeof(uint32_t) / sizeof(uint8_t))) {
in++;
}
else {
not_in++;
}
}
unsigned long t4 = xtimer_now_usec();
printf("checking %d elements took %" PRIu32 "ms\n", lenA,
(uint32_t) (t4 - t3) / 1000);
printf("\n");
printf("%d elements probably in the filter.\n", in);
printf("%d elements not in the filter.\n", not_in);
double false_positive_rate = (double) in / (double) lenA;
printf("%f false positive rate.\n", false_positive_rate);
bloom_del(&bloom);
printf("\nAll done!\n");
return 0;
}