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
|
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this file,
* You can obtain one at http://mozilla.org/MPL/2.0/. */
extern "C" {
#include "sslbloom.h"
}
#include "gtest_utils.h"
namespace nss_test {
// Some random-ish inputs to test with. These don't result in collisions in any
// of the configurations that are tested below.
static const uint8_t kHashes1[] = {
0x79, 0x53, 0xb8, 0xdd, 0x6b, 0x98, 0xce, 0x00, 0xb7, 0xdc, 0xe8,
0x03, 0x70, 0x8c, 0xe3, 0xac, 0x06, 0x8b, 0x22, 0xfd, 0x0e, 0x34,
0x48, 0xe6, 0xe5, 0xe0, 0x8a, 0xd6, 0x16, 0x18, 0xe5, 0x48};
static const uint8_t kHashes2[] = {
0xc6, 0xdd, 0x6e, 0xc4, 0x76, 0xb8, 0x55, 0xf2, 0xa4, 0xfc, 0x59,
0x04, 0xa4, 0x90, 0xdc, 0xa7, 0xa7, 0x0d, 0x94, 0x8f, 0xc2, 0xdc,
0x15, 0x6d, 0x48, 0x93, 0x9d, 0x05, 0xbb, 0x9a, 0xbc, 0xc1};
typedef struct {
unsigned int k;
unsigned int bits;
} BloomFilterConfig;
class BloomFilterTest
: public ::testing::Test,
public ::testing::WithParamInterface<BloomFilterConfig> {
public:
BloomFilterTest() : filter_() {}
void SetUp() { Init(); }
void TearDown() { sslBloom_Destroy(&filter_); }
protected:
void Init() {
if (filter_.filter) {
sslBloom_Destroy(&filter_);
}
ASSERT_EQ(SECSuccess,
sslBloom_Init(&filter_, GetParam().k, GetParam().bits));
}
bool Check(const uint8_t* hashes) {
return sslBloom_Check(&filter_, hashes) ? true : false;
}
void Add(const uint8_t* hashes, bool expect_collision = false) {
EXPECT_EQ(expect_collision, sslBloom_Add(&filter_, hashes) ? true : false);
EXPECT_TRUE(Check(hashes));
}
sslBloomFilter filter_;
};
TEST_P(BloomFilterTest, InitOnly) {}
TEST_P(BloomFilterTest, AddToEmpty) {
EXPECT_FALSE(Check(kHashes1));
Add(kHashes1);
}
TEST_P(BloomFilterTest, AddTwo) {
Add(kHashes1);
Add(kHashes2);
}
TEST_P(BloomFilterTest, AddOneTwice) {
Add(kHashes1);
Add(kHashes1, true);
}
TEST_P(BloomFilterTest, Zero) {
Add(kHashes1);
sslBloom_Zero(&filter_);
EXPECT_FALSE(Check(kHashes1));
EXPECT_FALSE(Check(kHashes2));
}
TEST_P(BloomFilterTest, Fill) {
sslBloom_Fill(&filter_);
EXPECT_TRUE(Check(kHashes1));
EXPECT_TRUE(Check(kHashes2));
}
static const BloomFilterConfig kBloomFilterConfigurations[] = {
{1, 1}, // 1 hash, 1 bit input - high chance of collision.
{1, 2}, // 1 hash, 2 bits - smaller than the basic unit size.
{1, 3}, // 1 hash, 3 bits - same as basic unit size.
{1, 4}, // 1 hash, 4 bits - 2 octets each.
{3, 10}, // 3 hashes over a reasonable number of bits.
{3, 3}, // Test that we can read multiple bits.
{4, 15}, // A credible filter.
{2, 18}, // A moderately large allocation.
{16, 16}, // Insane, use all of the bits from the hashes.
{16, 9}, // This also uses all of the bits from the hashes.
};
INSTANTIATE_TEST_SUITE_P(BloomFilterConfigurations, BloomFilterTest,
::testing::ValuesIn(kBloomFilterConfigurations));
} // namespace nss_test
|
