Revision: 947
http://dcplusplus.svn.sourceforge.net/dcplusplus/?rev=947&view=rev
Author: arnetheduck
Date: 2007-12-20 02:02:19 -0800 (Thu, 20 Dec 2007)
Log Message:
-----------
Bloom fixes
Modified Paths:
--------------
dcplusplus/trunk/dcpp/HashBloom.cpp
Modified: dcplusplus/trunk/dcpp/HashBloom.cpp
===================================================================
--- dcplusplus/trunk/dcpp/HashBloom.cpp 2007-12-17 23:14:47 UTC (rev 946)
+++ dcplusplus/trunk/dcpp/HashBloom.cpp 2007-12-20 10:02:19 UTC (rev 947)
@@ -6,14 +6,10 @@
namespace dcpp {
size_t HashBloom::get_k(size_t n) {
- const size_t bits = TTHValue::SIZE * 8;
- for(size_t k = static_cast<size_t>(sqrt(bits)); k > 1; --k) {
- // We only want the k's where the bits will end up on a byte boundary to ease hash implementation
- if((bits % k) == 0 && (bits / k) % 8 == 0) {
- uint64_t m = get_m(n, k);
- if(m >> (TTHValue::SIZE * 8 / k) == 0) {
- return k;
- }
+ for(size_t k = TTHValue::SIZE/3; k > 1; --k) {
+ uint64_t m = get_m(n, k);
+ if(m >> 24 == 0) {
+ return k;
}
}
return 1;
@@ -32,7 +28,7 @@
bool HashBloom::match(const TTHValue& tth) const {
if(bloom.empty()) {
- return true;
+ return false;
}
for(size_t i = 0; i < k; ++i) {
if(!bloom[pos(tth, i)]) {
@@ -52,17 +48,21 @@
}
size_t HashBloom::pos(const TTHValue& tth, size_t n) const {
- return (*(size_t*)(tth.data + (TTHValue::SIZE / k) * n )) % bloom.size();
+ uint32_t x = 0;
+ for(size_t i = n*3; i < TTHValue::SIZE; i += 3*k) {
+ x ^= static_cast<uint32_t>(tth.data[i]) << 2*8;
+ x ^= static_cast<uint32_t>(tth.data[i+1]) << 8;
+ x ^= static_cast<uint32_t>(tth.data[i+2]);
+ }
+
+ return x % bloom.size();
}
void HashBloom::copy_to(ByteVector& v) const {
- size_t ones = 0;
v.resize(bloom.size() / 8);
for(size_t i = 0; i < bloom.size(); ++i) {
- ones += bloom[i];
- v[i/8] |= bloom[i] << i % 8;
+ v[i/8] |= bloom[i] << (i % 8);
}
- dcdebug("Bloom fill: %u/%u = %lf\n", ones, bloom.size(), static_cast<double>(ones)/bloom.size());
}
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
