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
|
/*
* Copyright (C) 2001-2019 Jacek Sieka, arnetheduck on gmail point com
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
#include "stdinc.h"
#include "HashBloom.h"
#include <cmath>
#include "MerkleTree.h"
namespace dcpp {
size_t HashBloom::get_k(size_t n, size_t h) {
for(size_t k = TTHValue::BITS/h; k > 1; --k) {
uint64_t m = get_m(n, k);
if(m >> 24 == 0) {
return k;
}
}
return 1;
}
uint64_t HashBloom::get_m(size_t n, size_t k) {
uint64_t m = (static_cast<uint64_t>(ceil(static_cast<double>(n) * k / log(2.))));
// 64-bit boundary as per spec
return ((m + 63ULL )/ 64ULL) * 64ULL;
}
void HashBloom::add(const TTHValue& tth) {
for(size_t i = 0; i < k; ++i) {
bloom[pos(tth, i)] = true;
}
}
bool HashBloom::match(const TTHValue& tth) const {
if(bloom.empty()) {
return false;
}
for(size_t i = 0; i < k; ++i) {
if(!bloom[pos(tth, i)]) {
return false;
}
}
return true;
}
void HashBloom::push_back(bool v) {
bloom.push_back(v);
}
void HashBloom::reset(size_t k_, size_t m, size_t h_) {
bloom.resize(m);
k = k_;
h = h_;
}
size_t HashBloom::pos(const TTHValue& tth, size_t n) const {
if((n+1)*h > TTHValue::BITS) {
return 0;
}
uint64_t x = 0;
size_t start = n * h;
for(size_t i = 0; i < h; ++i) {
size_t bit = start + i;
size_t byte = bit / 8;
size_t pos = bit % 8;
if(tth.data[byte] & (1 << pos)) {
x |= (1LL << i);
}
}
return x % bloom.size();
}
void HashBloom::copy_to(ByteVector& v) const {
v.resize(bloom.size() / 8);
for(size_t i = 0; i < bloom.size(); ++i) {
v[i/8] |= bloom[i] << (i % 8);
}
}
}
|
