diff --git a/src/dht/key.cpp b/src/dht/key.cpp --- a/src/dht/key.cpp +++ b/src/dht/key.cpp @@ -22,6 +22,7 @@ #include #include #include +#include using namespace bt; @@ -35,14 +36,13 @@ { } - Key::Key(const Uint8* d) : bt::SHA1Hash(d) + Key::Key(const bt::Uint8* d) : bt::SHA1Hash(d) { } Key::Key(const QByteArray & ba) { - for (int i = 0;i < 20 && i < ba.size();i++) - hash[i] = ba[i]; + memcpy(hash, ba.data(), std::min(20, ba.size())); } Key::~Key() @@ -60,83 +60,64 @@ bool Key::operator < (const Key & other) const { - for (int i = 0;i < 20;i++) - { - if (hash[i] < other.hash[i]) - return true; - else if (hash[i] > other.hash[i]) - return false; - } - return false; + return memcmp(hash, other.hash, 20) < 0; } bool Key::operator <= (const Key & other) const { - return operator < (other) || operator == (other); + return memcmp(hash, other.hash, 20) <= 0; } bool Key::operator > (const Key & other) const { - for (int i = 0;i < 20;i++) - { - if (hash[i] < other.hash[i]) - return false; - else if (hash[i] > other.hash[i]) - return true; - } - return false; + return memcmp(hash, other.hash, 20) > 0; } bool Key::operator >= (const Key & other) const { - return operator > (other) || operator == (other); + return memcmp(hash, other.hash, 20) >= 0; } Key operator + (const dht::Key& a, const dht::Key& b) { - bt::Uint8 result[20]; - bool carry = false; - const bt::Uint8* ad = a.getData(); - const bt::Uint8* bd = b.getData(); - for (int i = 19;i >= 0;i--) - { - unsigned int r = ad[i] + bd[i] + (carry ? 1 : 0); - if (r > 255) - { - result[i] = r & 0xFF; - carry = true; - } - else - { - result[i] = r; - carry = false; - } + dht::Key result; + bt::Uint64 sum = 0; + + for (int i = 4; i >= 0; i--) { + sum += (bt::Uint64) htobe32(a.hash[i]) + htobe32(b.hash[i]); + result.hash[i] = htobe32(sum & 0xFFFFFFFF); + sum = sum >> 32; } - return dht::Key(result); + return result; } Key operator + (const Key & a, bt::Uint8 value) { - bt::Uint8 b[20]; - memset(b, 0, 20); - b[19] = value; - return a + Key(b); + dht::Key result(a); + + bt::Uint64 sum = value; + for (int i = 4; i >= 0 && sum != 0; i--) { + sum += htobe32(result.hash[i]); + result.hash[i] = htobe32(sum & 0xFFFFFFFF); + sum = sum >> 32; + } + + return result; } Key Key::operator / (int value) const { - bt::Uint8 result[20]; - bt::Uint8 remainder = 0; - - for (int i = 0; i < 20; i++) - { - bt::Uint8 d = (hash[i] + (remainder << 8)) / value; - remainder = (hash[i] + (remainder << 8)) % value; - result[i] = d; + dht::Key result; + bt::Uint64 remainder = 0; + + for (int i = 0; i < 5; i++) { + const bt::Uint32 h = htobe32(hash[i]); + result.hash[i] = htobe32( ( h + remainder) / value ); + remainder = ((h + remainder) % value) << 32; } - - return dht::Key(result); + + return result; } @@ -149,48 +130,34 @@ { srand(time(0)); Key k; - for (int i = 0;i < 20;i++) + Uint16* h = (Uint16*) k.hash; + for (int i = 0; i < 10; i++) { - k.hash[i] = (Uint8)rand() % 0xFF; + h[i] = std::rand() & 0xFFFF; // rand() between 0 and only 2^31 } return k; } Key operator - (const Key & a, const Key & b) { - bt::Uint8 result[20]; - bool carry = false; - const bt::Uint8* ad = a.getData(); - const bt::Uint8* bd = b.getData(); - for (int i = 19;i >= 0;i--) + dht::Key result; + bt::Uint32 carry = 0; + for (int i = 4; i >= 0; i--) { - if (ad[i] >= bd[i]) + const bt::Uint32 a32 = htobe32(a.hash[i]); + const bt::Uint32 b32 = htobe32(b.hash[i]); + if (a32 >= (( bt::Uint64)b32 + carry) ) { - result[i] = ad[i] - bd[i]; - if (carry) - { - if (result[i] == 0) - { - result[i] = 0xFF; - carry = true; - } - else - { - result[i] -= 1; - carry = false; - } - } - } - else - { - result[i] = 256 - (bd[i] - ad[i]); - if (carry) - result[i] -= 1; - carry = true; + result.hash[i] = htobe32(a32 - b32 - carry); + carry = 0; + } else { + const bt::Uint64 max = 0xFFFFFFFF + 1; + result.hash[i] = htobe32( (bt::Uint32) (max - (b32 - a32) - carry) ); + carry = 1; } } - return dht::Key(result); + return result; } Key Key::mid(const dht::Key& a, const dht::Key& b) @@ -200,19 +167,20 @@ else return b + (a - b) / 2; } + +#define rep4(v) v, v, v, v +#define rep20(v) rep4(v), rep4(v), rep4(v), rep4(v), rep4(v) +const bt::Uint8 val_max[20] = {rep20(0xFF)}; +const bt::Uint8 val_min[20] = {rep20(0x00)}; Key Key::max() { - bt::Uint8 result[20]; - std::fill(result, result + 20, 0xFF); - return Key(result); + return Key(val_max); } Key Key::min() { - bt::Uint8 result[20]; - std::fill(result, result + 20, 0x0); - return Key(result); + return Key(val_min); } diff --git a/src/dht/tests/keytest.cpp b/src/dht/tests/keytest.cpp --- a/src/dht/tests/keytest.cpp +++ b/src/dht/tests/keytest.cpp @@ -43,20 +43,20 @@ { bt::Uint8 result[20]; std::fill(result, result + 20, 0); - + QString s = str.toLower(); if (s.size() % 2 != 0) s.prepend('0'); - + int j = 19; - + for (int i = s.size() - 1; i >= 0; i -= 2) { char left = s[i - 1].toLatin1(); char right = s[i].toLatin1(); result[j--] = (HexCharToUint8(left) << 4) | HexCharToUint8(right); } - + return dht::Key(result); } @@ -68,43 +68,65 @@ { bt::InitLog("keytest.log", false, true); } - + void cleanupTestCase() { } - + void testAddition() { dht::Key a = KeyFromHexString("14455"); - dht::Key b = KeyFromHexString("FFEEDD"); + dht::Key b = KeyFromHexString("FFEEDD"); dht::Key c = a + b; QVERIFY(c == KeyFromHexString("1013332")); - + dht::Key d = a + 1; QVERIFY(d == KeyFromHexString("14456")); - + dht::Key e = KeyFromHexString("FFFF") + 1; QVERIFY(e == KeyFromHexString("10000")); + + dht::Key f = KeyFromHexString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF") + 1; + QVERIFY(f == KeyFromHexString("0000000000000000000000000000000000000000")); + + dht::Key h = KeyFromHexString("FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF"); + dht::Key j = KeyFromHexString("0000000100000000000000010000000000000001"); + dht::Key g = j + h; + QVERIFY(g == KeyFromHexString("0000000000000001000000000000000100000000")); } - + void testSubtraction() { dht::Key a = KeyFromHexString("556677"); dht::Key b = KeyFromHexString("3384E6"); dht::Key c = a - b; QVERIFY(c == KeyFromHexString("21E191")); - + dht::Key d = KeyFromHexString("550077"); dht::Key e = KeyFromHexString("3384E6"); dht::Key f = d - e; QVERIFY(f == KeyFromHexString("217B91")); + + f = e - d; + QVERIFY(f == KeyFromHexString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDE846F")); + + dht::Key g = KeyFromHexString("0000000000000001000000000000000100000000"); + dht::Key j = KeyFromHexString("0000000100000000000000010000000000000001"); + dht::Key h = g - j; + QVERIFY(h == KeyFromHexString("FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF")); + } - + void testDivision() { dht::Key a = KeyFromHexString("550078"); dht::Key b = a / 2; QVERIFY(b == KeyFromHexString("2A803C")); + + dht::Key c = KeyFromHexString("0000000100000000000000010000000000000001"); + dht::Key d = c / 32; + QVERIFY(d == KeyFromHexString("0000000008000000000000000800000000000000")); + } }; diff --git a/src/util/sha1hash.h b/src/util/sha1hash.h --- a/src/util/sha1hash.h +++ b/src/util/sha1hash.h @@ -40,7 +40,7 @@ class KTORRENT_EXPORT SHA1Hash { protected: - Uint8 hash[20]; + Uint32 hash[5]; public: /** * Constructor, sets every byte in the hash to 0. @@ -111,7 +111,7 @@ * Directly get pointer to the data. * @return The data */ - const Uint8* getData() const {return hash;} + const Uint8* getData() const {return (Uint8*) hash;} /** * Function to print a SHA1Hash to the Log. diff --git a/src/util/sha1hash.cpp b/src/util/sha1hash.cpp --- a/src/util/sha1hash.cpp +++ b/src/util/sha1hash.cpp @@ -31,18 +31,17 @@ { SHA1Hash::SHA1Hash() { - std::fill(hash,hash+20,0); + memset(hash, 0, 20); } SHA1Hash::SHA1Hash(const SHA1Hash & other) { - for (int i = 0;i < 20;i++) - hash[i] = other.hash[i]; + memcpy(hash, other.hash, 20); } SHA1Hash::SHA1Hash(const Uint8* h) { - memcpy(hash,h,20); + memcpy(hash, h, 20); } @@ -51,18 +50,13 @@ SHA1Hash & SHA1Hash::operator = (const SHA1Hash & other) { - for (int i = 0;i < 20;i++) - hash[i] = other.hash[i]; + memcpy(hash, other.hash, 20); return *this; } bool SHA1Hash::operator == (const SHA1Hash & other) const { - for (int i = 0;i < 20;i++) - if (hash[i] != other.hash[i]) - return false; - - return true; + return memcmp(hash, other.hash, 20) == 0; } SHA1Hash SHA1Hash::generate(const Uint8* data,Uint32 len) @@ -72,20 +66,20 @@ return hg.generate(data,len); } +#define hex_str '%','0','2','x' +#define hex_str4 hex_str, hex_str, hex_str, hex_str +#define hex_str20 hex_str4, hex_str4, hex_str4, hex_str4, hex_str4 QString SHA1Hash::toString() const { char tmp[41]; - char fmt[81]; - for (int i = 0;i < 20;i++) - strncpy(fmt + 4*i,"%02x",4); - fmt[80] = '\0'; - tmp[40] = '\0'; - snprintf(tmp,41,fmt, - hash[0],hash[1],hash[2],hash[3],hash[4], - hash[5],hash[6],hash[7],hash[8],hash[9], - hash[10],hash[11],hash[12],hash[13],hash[14], - hash[15],hash[16],hash[17],hash[18],hash[19]); - return QString::fromUtf8(tmp); + char fmt[81] = {hex_str20, '\0'}; + const Uint8* h = getData(); + snprintf(tmp, 40, fmt, + h[0], h[1], h[2], h[3], h[4], + h[5], h[6], h[7], h[8], h[9], + h[10], h[11], h[12], h[13], h[14], + h[15], h[16], h[17], h[18], h[19]); + return QString::fromLatin1(tmp, 40); } QByteArray SHA1Hash::toByteArray() const @@ -107,24 +101,18 @@ SHA1Hash operator ^ (const SHA1Hash & a,const SHA1Hash & b) { SHA1Hash k; - for (int i = 0;i < 20;i++) - { - k.hash[i] = a.hash[i] ^ b.hash[i]; - } + Uint64* k64 = (Uint64*) k.hash; + const Uint64* a64 = (Uint64*) a.hash; + const Uint64* b64 = (Uint64*) b.hash; + k64[0] = a64[0] ^ b64[0]; + k64[1] = a64[1] ^ b64[1]; + k.hash[4] = a.hash[4] ^ b.hash[4]; return k; } bool operator < (const SHA1Hash & a,const SHA1Hash & b) { - for (int i = 0;i < 20;i++) - { - if (a.hash[i] < b.hash[i]) - return true; - else if (a.hash[i] > b.hash[i]) - return false; - } - - return false; + return memcmp(a.hash, b.hash, 20) < 0; } uint qHash(const SHA1Hash &key)