[Dcplusplus-commit] SF.net SVN: dcplusplus: [947] dcplusplus/trunk/dcpp/HashBloom.cpp

[<arn...@us...>]

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.