diff options
| author | tanjent@gmail.com <tanjent@gmail.com@77a7d1d3-4c08-bdc2-d393-d5859734b01a> | 2011-03-19 21:28:26 +0000 |
|---|---|---|
| committer | tanjent@gmail.com <tanjent@gmail.com@77a7d1d3-4c08-bdc2-d393-d5859734b01a> | 2011-03-19 21:28:26 +0000 |
| commit | 6ffe01004546290235d45b2d8c436180947395a7 (patch) | |
| tree | 650c57ab98a96b1f1d15453c777866597bdd1a57 | |
| parent | 3ef87613ed6bd520128d5ba169f1cb99b86b4018 (diff) | |
| download | src-6ffe01004546290235d45b2d8c436180947395a7.tar.gz | |
Add startup self-test
Remove randhash (will fail self-test)
Remove QuickBrownFox (replaced by VerificationTest)
De-tabulate all files
git-svn-id: http://smhasher.googlecode.com/svn/trunk@90 77a7d1d3-4c08-bdc2-d393-d5859734b01a
| -rw-r--r-- | AvalancheTest.cpp | 60 | ||||
| -rw-r--r-- | AvalancheTest.h | 294 | ||||
| -rw-r--r-- | Bitslice.cpp | 152 | ||||
| -rw-r--r-- | Bitvec.cpp | 850 | ||||
| -rw-r--r-- | Bitvec.h | 170 | ||||
| -rw-r--r-- | DifferentialTest.h | 276 | ||||
| -rw-r--r-- | Hashes.cpp | 120 | ||||
| -rw-r--r-- | Hashes.h | 10 | ||||
| -rw-r--r-- | KeysetTest.cpp | 250 | ||||
| -rw-r--r-- | KeysetTest.h | 401 | ||||
| -rw-r--r-- | MurmurHash1.cpp | 272 | ||||
| -rw-r--r-- | MurmurHash2.cpp | 704 | ||||
| -rw-r--r-- | MurmurHash3.cpp | 63 | ||||
| -rw-r--r-- | Platform.cpp | 2 | ||||
| -rw-r--r-- | Platform.h | 8 | ||||
| -rw-r--r-- | Random.h | 178 | ||||
| -rw-r--r-- | SpeedTest.cpp | 118 | ||||
| -rw-r--r-- | Stats.cpp | 78 | ||||
| -rw-r--r-- | Stats.h | 368 | ||||
| -rw-r--r-- | SuperFastHash.cpp | 70 | ||||
| -rw-r--r-- | Types.cpp | 2 | ||||
| -rw-r--r-- | Types.h | 376 | ||||
| -rw-r--r-- | crc.cpp | 26 | ||||
| -rw-r--r-- | lookup3.cpp | 64 | ||||
| -rw-r--r-- | main.cpp | 800 | ||||
| -rw-r--r-- | md5.cpp | 14 | ||||
| -rw-r--r-- | pstdint.h | 80 | ||||
| -rw-r--r-- | sha1.cpp | 24 |
28 files changed, 2857 insertions, 2973 deletions
diff --git a/AvalancheTest.cpp b/AvalancheTest.cpp index 5cdebd8..38aa452 100644 --- a/AvalancheTest.cpp +++ b/AvalancheTest.cpp @@ -4,53 +4,53 @@ void PrintAvalancheDiagram ( int x, int y, int reps, double scale, int * bins )
{
- const char * symbols = ".123456789X";
+ const char * symbols = ".123456789X";
- for(int i = 0; i < y; i++)
- {
- printf("[");
- for(int j = 0; j < x; j++)
- {
- int k = (y - i) -1;
+ for(int i = 0; i < y; i++)
+ {
+ printf("[");
+ for(int j = 0; j < x; j++)
+ {
+ int k = (y - i) -1;
- int bin = bins[k + (j*y)];
+ int bin = bins[k + (j*y)];
- double b = double(bin) / double(reps);
- b = fabs(b*2 - 1);
+ double b = double(bin) / double(reps);
+ b = fabs(b*2 - 1);
- b *= scale;
+ b *= scale;
- int s = (int)floor(b*10);
+ int s = (int)floor(b*10);
- if(s > 10) s = 10;
- if(s < 0) s = 0;
+ if(s > 10) s = 10;
+ if(s < 0) s = 0;
- printf("%c",symbols[s]);
- }
+ printf("%c",symbols[s]);
+ }
- printf("]\n");
- }
+ printf("]\n");
+ }
}
//----------------------------------------------------------------------------
double maxBias ( std::vector<int> & counts, int reps )
{
- double worst = 0;
+ double worst = 0;
- for(int i = 0; i < (int)counts.size(); i++)
- {
- double c = double(counts[i]) / double(reps);
+ for(int i = 0; i < (int)counts.size(); i++)
+ {
+ double c = double(counts[i]) / double(reps);
- double d = fabs(c * 2 - 1);
-
- if(d > worst)
- {
- worst = d;
- }
- }
+ double d = fabs(c * 2 - 1);
+
+ if(d > worst)
+ {
+ worst = d;
+ }
+ }
- return worst;
+ return worst;
}
//-----------------------------------------------------------------------------
diff --git a/AvalancheTest.h b/AvalancheTest.h index 1fbf095..966f8b0 100644 --- a/AvalancheTest.h +++ b/AvalancheTest.h @@ -27,40 +27,40 @@ double maxBias ( std::vector<int> & counts, int reps ); template < typename keytype, typename hashtype >
void calcBias ( pfHash hash, std::vector<int> & counts, int reps )
{
- const int keybytes = sizeof(keytype);
- const int hashbytes = sizeof(hashtype);
+ const int keybytes = sizeof(keytype);
+ const int hashbytes = sizeof(hashtype);
- const int keybits = keybytes * 8;
- const int hashbits = hashbytes * 8;
+ const int keybits = keybytes * 8;
+ const int hashbits = hashbytes * 8;
- keytype K;
- hashtype A,B;
+ keytype K;
+ hashtype A,B;
- for(int irep = 0; irep < reps; irep++)
- {
- if(irep % (reps/10) == 0) printf(".");
+ for(int irep = 0; irep < reps; irep++)
+ {
+ if(irep % (reps/10) == 0) printf(".");
- rand_p(&K,keybytes);
+ rand_p(&K,keybytes);
- hash(&K,keybytes,0,&A);
+ hash(&K,keybytes,0,&A);
- int * cursor = &counts[0];
+ int * cursor = &counts[0];
- for(int iBit = 0; iBit < keybits; iBit++)
- {
- flipbit(&K,keybytes,iBit);
- hash(&K,keybytes,0,&B);
- flipbit(&K,keybytes,iBit);
+ for(int iBit = 0; iBit < keybits; iBit++)
+ {
+ flipbit(&K,keybytes,iBit);
+ hash(&K,keybytes,0,&B);
+ flipbit(&K,keybytes,iBit);
- for(int iOut = 0; iOut < hashbits; iOut++)
- {
- int bitA = getbit(&A,hashbytes,iOut);
- int bitB = getbit(&B,hashbytes,iOut);
+ for(int iOut = 0; iOut < hashbits; iOut++)
+ {
+ int bitA = getbit(&A,hashbytes,iOut);
+ int bitB = getbit(&B,hashbytes,iOut);
- (*cursor++) += (bitA ^ bitB);
- }
- }
- }
+ (*cursor++) += (bitA ^ bitB);
+ }
+ }
+ }
}
//-----------------------------------------------------------------------------
@@ -68,37 +68,37 @@ void calcBias ( pfHash hash, std::vector<int> & counts, int reps ) template < typename keytype, typename hashtype >
bool AvalancheTest ( pfHash hash, const int reps )
{
- const int keybytes = sizeof(keytype);
- const int hashbytes = sizeof(hashtype);
+ const int keybytes = sizeof(keytype);
+ const int hashbytes = sizeof(hashtype);
- const int keybits = keybytes * 8;
- const int hashbits = hashbytes * 8;
+ const int keybits = keybytes * 8;
+ const int hashbits = hashbytes * 8;
- printf("Testing %3d-bit keys -> %3d-bit hashes, %8d reps",keybits,hashbits,reps);
+ printf("Testing %3d-bit keys -> %3d-bit hashes, %8d reps",keybits,hashbits,reps);
- //----------
+ //----------
- std::vector<int> bins(keybits*hashbits,0);
+ std::vector<int> bins(keybits*hashbits,0);
- calcBias<keytype,hashtype>(hash,bins,reps);
-
- //----------
+ calcBias<keytype,hashtype>(hash,bins,reps);
+
+ //----------
- bool result = true;
+ bool result = true;
- double b = maxBias(bins,reps);
+ double b = maxBias(bins,reps);
- printf(" worst bias is %f%%",b * 100.0);
+ printf(" worst bias is %f%%",b * 100.0);
- if(b > AVALANCHE_FAIL)
- {
- printf(" !!!!! ");
- result = false;
- }
+ if(b > AVALANCHE_FAIL)
+ {
+ printf(" !!!!! ");
+ result = false;
+ }
- printf("\n");
+ printf("\n");
- return result;
+ return result;
}
//----------------------------------------------------------------------------
@@ -108,83 +108,83 @@ bool AvalancheTest ( pfHash hash, const int reps ) template< typename keytype, typename hashtype >
void BicTest ( pfHash hash, const int keybit, const int reps, double & maxBias, int & maxA, int & maxB, bool verbose )
{
- const int keybytes = sizeof(keytype);
- const int hashbytes = sizeof(hashtype);
- const int hashbits = hashbytes * 8;
-
- std::vector<int> bins(hashbits*hashbits*4,0);
-
- keytype key;
- hashtype h1,h2;
-
- for(int irep = 0; irep < reps; irep++)
- {
- if(verbose)
- {
- if(irep % (reps/10) == 0) printf(".");
- }
-
- rand_p(&key,keybytes);
- hash(&key,keybytes,0,&h1);
-
- flipbit(key,keybit);
- hash(&key,keybytes,0,&h2);
-
- keytype d = h1 ^ h2;
-
- for(int out1 = 0; out1 < hashbits; out1++)
- for(int out2 = 0; out2 < hashbits; out2++)
- {
- if(out1 == out2) continue;
-
- uint32_t b = getbit(d,out1) | (getbit(d,out2) << 1);
-
- bins[(out1 * hashbits + out2) * 4 + b]++;
- }
- }
-
- if(verbose) printf("\n");
-
- maxBias = 0;
-
- for(int out1 = 0; out1 < hashbits; out1++)
- {
- for(int out2 = 0; out2 < hashbits; out2++)
- {
- if(out1 == out2)
- {
- if(verbose) printf("\\");
- continue;
- }
-
- double bias = 0;
-
- for(int b = 0; b < 4; b++)
- {
- double b2 = double(bins[(out1 * hashbits + out2) * 4 + b]) / double(reps / 2);
- b2 = fabs(b2 * 2 - 1);
-
- if(b2 > bias) bias = b2;
- }
-
- if(bias > maxBias)
- {
- maxBias = bias;
- maxA = out1;
- maxB = out2;
- }
-
- if(verbose)
- {
- if (bias < 0.01) printf(".");
- else if(bias < 0.05) printf("o");
- else if(bias < 0.33) printf("O");
- else printf("X");
- }
- }
-
- if(verbose) printf("\n");
- }
+ const int keybytes = sizeof(keytype);
+ const int hashbytes = sizeof(hashtype);
+ const int hashbits = hashbytes * 8;
+
+ std::vector<int> bins(hashbits*hashbits*4,0);
+
+ keytype key;
+ hashtype h1,h2;
+
+ for(int irep = 0; irep < reps; irep++)
+ {
+ if(verbose)
+ {
+ if(irep % (reps/10) == 0) printf(".");
+ }
+
+ rand_p(&key,keybytes);
+ hash(&key,keybytes,0,&h1);
+
+ flipbit(key,keybit);
+ hash(&key,keybytes,0,&h2);
+
+ keytype d = h1 ^ h2;
+
+ for(int out1 = 0; out1 < hashbits; out1++)
+ for(int out2 = 0; out2 < hashbits; out2++)
+ {
+ if(out1 == out2) continue;
+
+ uint32_t b = getbit(d,out1) | (getbit(d,out2) << 1);
+
+ bins[(out1 * hashbits + out2) * 4 + b]++;
+ }
+ }
+
+ if(verbose) printf("\n");
+
+ maxBias = 0;
+
+ for(int out1 = 0; out1 < hashbits; out1++)
+ {
+ for(int out2 = 0; out2 < hashbits; out2++)
+ {
+ if(out1 == out2)
+ {
+ if(verbose) printf("\\");
+ continue;
+ }
+
+ double bias = 0;
+
+ for(int b = 0; b < 4; b++)
+ {
+ double b2 = double(bins[(out1 * hashbits + out2) * 4 + b]) / double(reps / 2);
+ b2 = fabs(b2 * 2 - 1);
+
+ if(b2 > bias) bias = b2;
+ }
+
+ if(bias > maxBias)
+ {
+ maxBias = bias;
+ maxA = out1;
+ maxB = out2;
+ }
+
+ if(verbose)
+ {
+ if (bias < 0.01) printf(".");
+ else if(bias < 0.05) printf("o");
+ else if(bias < 0.33) printf("O");
+ else printf("X");
+ }
+ }
+
+ if(verbose) printf("\n");
+ }
}
//----------
@@ -192,39 +192,39 @@ void BicTest ( pfHash hash, const int keybit, const int reps, double & maxBias, template< typename keytype, typename hashtype >
bool BicTest ( pfHash hash, const int reps )
{
- const int keybytes = sizeof(keytype);
- const int keybits = keybytes * 8;
+ const int keybytes = sizeof(keytype);
+ const int keybits = keybytes * 8;
- double maxBias = 0;
- int maxK = 0;
- int maxA = 0;
- int maxB = 0;
+ double maxBias = 0;
+ int maxK = 0;
+ int maxA = 0;
+ int maxB = 0;
- for(int i = 0; i < keybits; i++)
- {
- if(i % (keybits/10) == 0) printf(".");
+ for(int i = 0; i < keybits; i++)
+ {
+ if(i % (keybits/10) == 0) printf(".");
- double bias;
- int a,b;
-
- BicTest<keytype,hashtype>(hash,i,reps,bias,a,b,false);
+ double bias;
+ int a,b;
+
+ BicTest<keytype,hashtype>(hash,i,reps,bias,a,b,false);
- if(bias > maxBias)
- {
- maxBias = bias;
- maxK = i;
- maxA = a;
- maxB = b;
- }
- }
+ if(bias > maxBias)
+ {
+ maxBias = bias;
+ maxK = i;
+ maxA = a;
+ maxB = b;
+ }
+ }
- printf("Max bias %f - (%3d : %3d,%3d)\n",maxBias,maxK,maxA,maxB);
+ printf("Max bias %f - (%3d : %3d,%3d)\n",maxBias,maxK,maxA,maxB);
- // Bit independence is harder to pass than avalanche, so we're a bit more lax here.
+ // Bit independence is harder to pass than avalanche, so we're a bit more lax here.
- bool result = (maxBias < 0.05);
+ bool result = (maxBias < 0.05);
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
diff --git a/Bitslice.cpp b/Bitslice.cpp index 7e9edd3..428e355 100644 --- a/Bitslice.cpp +++ b/Bitslice.cpp @@ -9,42 +9,42 @@ typedef std::vector<slice> slice_vec; int countbits ( slice & v )
{
- int c = 0;
+ int c = 0;
- for(size_t i = 0; i < v.size(); i++)
- {
- int d = countbits(v[i]);
+ for(size_t i = 0; i < v.size(); i++)
+ {
+ int d = countbits(v[i]);
- c += d;
- }
+ c += d;
+ }
- return c;
+ return c;
}
int countxor ( slice & a, slice & b )
{
- assert(a.size() == b.size());
+ assert(a.size() == b.size());
- int c = 0;
+ int c = 0;
- for(size_t i = 0; i < a.size(); i++)
- {
- int d = countbits(a[i] ^ b[i]);
+ for(size_t i = 0; i < a.size(); i++)
+ {
+ int d = countbits(a[i] ^ b[i]);
- c += d;
- }
+ c += d;
+ }
- return c;
+ return c;
}
void xoreq ( slice & a, slice & b )
{
- assert(a.size() == b.size());
+ assert(a.size() == b.size());
- for(size_t i = 0; i < a.size(); i++)
- {
- a[i] ^= b[i];
- }
+ for(size_t i = 0; i < a.size(); i++)
+ {
+ a[i] ^= b[i];
+ }
}
//-----------------------------------------------------------------------------
@@ -53,75 +53,75 @@ void xoreq ( slice & a, slice & b ) template< typename hashtype >
void Bitslice ( std::vector<hashtype> & hashes, slice_vec & slices )
{
- const int hashbytes = sizeof(hashtype);
- const int hashbits = hashbytes * 8;
- const int slicelen = ((int)hashes.size() + 31) / 32;
+ const int hashbytes = sizeof(hashtype);
+ const int hashbits = hashbytes * 8;
+ const int slicelen = ((int)hashes.size() + 31) / 32;
- slices.clear();
- slices.resize(hashbits);
+ slices.clear();
+ slices.resize(hashbits);
- for(int i = 0; i < (int)slices.size(); i++)
- {
- slices[i].resize(slicelen,0);
- }
+ for(int i = 0; i < (int)slices.size(); i++)
+ {
+ slices[i].resize(slicelen,0);
+ }
- for(int j = 0; j < hashbits; j++)
- {
- void * sliceblob = &(slices[j][0]);
+ for(int j = 0; j < hashbits; j++)
+ {
+ void * sliceblob = &(slices[j][0]);
- for(int i = 0; i < (int)hashes.size(); i++)
- {
- int b = getbit(hashes[i],j);
+ for(int i = 0; i < (int)hashes.size(); i++)
+ {
+ int b = getbit(hashes[i],j);
- setbit(sliceblob,slicelen*4,i,b);
- }
- }
+ setbit(sliceblob,slicelen*4,i,b);
+ }
+ }
}
void FactorSlices ( slice_vec & slices )
{
- std::vector<int> counts(slices.size(),0);
-
- for(size_t i = 0; i < slices.size(); i++)
- {
- counts[i] = countbits(slices[i]);
- }
-
- bool changed = true;
-
- while(changed)
- {
- int bestA = -1;
- int bestB = -1;
-
- for(int j = 0; j < (int)slices.size()-1; j++)
- {
- for(int i = j+1; i < (int)slices.size(); i++)
- {
- int d = countxor(slices[i],slices[j]);
-
- if((d < counts[i]) && (d < counts[j]))
- {
- if(counts[i] < counts[j])
- {
- bestA = j;
- bestB = i;
- }
- }
- else if(d < counts[i])
- {
- //bestA =
- }
- }
- }
- }
+ std::vector<int> counts(slices.size(),0);
+
+ for(size_t i = 0; i < slices.size(); i++)
+ {
+ counts[i] = countbits(slices[i]);
+ }
+
+ bool changed = true;
+
+ while(changed)
+ {
+ int bestA = -1;
+ int bestB = -1;
+
+ for(int j = 0; j < (int)slices.size()-1; j++)
+ {
+ for(int i = j+1; i < (int)slices.size(); i++)
+ {
+ int d = countxor(slices[i],slices[j]);
+
+ if((d < counts[i]) && (d < counts[j]))
+ {
+ if(counts[i] < counts[j])
+ {
+ bestA = j;
+ bestB = i;
+ }
+ }
+ else if(d < counts[i])
+ {
+ //bestA =
+ }
+ }
+ }
+ }
}
void foo ( void )
{
- slice a;
- slice_vec b;
+ slice a;
+ slice_vec b;
- Bitslice(a,b);
+ Bitslice(a,b);
}
\ No newline at end of file @@ -16,617 +16,617 @@ void assert ( bool ) void printbits ( void * blob, int len )
{
- uint8_t * data = (uint8_t*)blob;
+ uint8_t * data = (uint8_t*)blob;
- printf("[");
- for(int i = 0; i < len; i++)
- {
- unsigned char byte = data[i];
+ printf("[");
+ for(int i = 0; i < len; i++)
+ {
+ unsigned char byte = data[i];
- int hi = (byte >> 4);
- int lo = (byte & 0xF);
+ int hi = (byte >> 4);
+ int lo = (byte & 0xF);
- if(hi) printf("%01x",hi);
- else printf(".");
+ if(hi) printf("%01x",hi);
+ else printf(".");
- if(lo) printf("%01x",lo);
- else printf(".");
+ if(lo) printf("%01x",lo);
+ else printf(".");
- if(i != len-1) printf(" ");
- }
- printf("]");
+ if(i != len-1) printf(" ");
+ }
+ printf("]");
}
void printbits2 ( uint8_t * k, int nbytes )
{
- printf("[");
+ printf("[");
- for(int i = nbytes-1; i >= 0; i--)
- {
- uint8_t b = k[i];
+ for(int i = nbytes-1; i >= 0; i--)
+ {
+ uint8_t b = k[i];
- for(int j = 7; j >= 0; j--)
- {
- uint8_t c = (b & (1 << j)) ? '#' : ' ';
+ for(int j = 7; j >= 0; j--)
+ {
+ uint8_t c = (b & (1 << j)) ? '#' : ' ';
- putc(c,stdout);
- }
- }
- printf("]");
+ putc(c,stdout);
+ }
+ }
+ printf("]");
}
void printhex32 ( void * blob, int len )
{
- assert((len & 3) == 0);
+ assert((len & 3) == 0);
- uint32_t * d = (uint32_t*)blob;
+ uint32_t * d = (uint32_t*)blob;
- printf("{ ");
+ printf("{ ");
- for(int i = 0; i < len/4; i++)
- {
- printf("0x%08x, ",d[i]);
- }
+ for(int i = 0; i < len/4; i++)
+ {
+ printf("0x%08x, ",d[i]);
+ }
- printf("}");
+ printf("}");
}
void printbytes ( void * blob, int len )
{
- uint8_t * d = (uint8_t*)blob;
+ uint8_t * d = (uint8_t*)blob;
- printf("{ ");
+ printf("{ ");
- for(int i = 0; i < len; i++)
- {
- printf("0x%02x, ",d[i]);
- }
+ for(int i = 0; i < len; i++)
+ {
+ printf("0x%02x, ",d[i]);
+ }
- printf(" };");
+ printf(" };");
}
//-----------------------------------------------------------------------------
uint32_t getbit ( void * block, int len, uint32_t bit )
{
- uint8_t * b = (uint8_t*)block;
+ uint8_t * b = (uint8_t*)block;
- int byte = bit >> 3;
- bit = bit & 0x7;
-
- if(byte < len) return (b[byte] >> bit) & 1;
+ int byte = bit >> 3;
+ bit = bit & 0x7;
+
+ if(byte < len) return (b[byte] >> bit) & 1;
- return 0;
+ return 0;
}
uint32_t getbit_wrap ( void * block, int len, uint32_t bit )
{
- uint8_t * b = (uint8_t*)block;
-
- int byte = bit >> 3;
- bit = bit & 0x7;
-
- byte %= len;
-
- return (b[byte] >> bit) & 1;
+ uint8_t * b = (uint8_t*)block;
+
+ int byte = bit >> 3;
+ bit = bit & 0x7;
+
+ byte %= len;
+
+ return (b[byte] >> bit) & 1;
}
void setbit ( void * block, int len, uint32_t bit )
{
- uint8_t * b = (uint8_t*)block;
+ uint8_t * b = (uint8_t*)block;
- int byte = bit >> 3;
- bit = bit & 0x7;
-
- if(byte < len) b[byte] |= (1 << bit);
+ int byte = bit >> 3;
+ bit = bit & 0x7;
+
+ if(byte < len) b[byte] |= (1 << bit);
}
void setbit ( void * block, int len, uint32_t bit, uint32_t val )
{
- val ? setbit(block,len,bit) : clearbit(block,len,bit);
+ val ? setbit(block,len,bit) : clearbit(block,len,bit);
}
void clearbit ( void * block, int len, uint32_t bit )
{
- uint8_t * b = (uint8_t*)block;
+ uint8_t * b = (uint8_t*)block;
- int byte = bit >> 3;
- bit = bit & 0x7;
-
- if(byte < len) b[byte] &= ~(1 << bit);
+ int byte = bit >> 3;
+ bit = bit & 0x7;
+
+ if(byte < len) b[byte] &= ~(1 << bit);
}
void flipbit ( void * block, int len, uint32_t bit )
{
- uint8_t * b = (uint8_t*)block;
+ uint8_t * b = (uint8_t*)block;
- int byte = bit >> 3;
- bit = bit & 0x7;
-
- if(byte < len) b[byte] ^= (1 << bit);
+ int byte = bit >> 3;
+ bit = bit & 0x7;
+
+ if(byte < len) b[byte] ^= (1 << bit);
}
// from the "Bit Twiddling Hacks" webpage
int countbits ( uint32_t v )
{
- v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
- v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
- int c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
+ v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
+ v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
+ int c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
- return c;
+ return c;
}
//-----------------------------------------------------------------------------
void lshift1 ( void * blob, int len, int c )
{
- int nbits = len*8;
+ int nbits = len*8;
- for(int i = nbits-1; i >= 0; i--)
- {
- setbit(blob,len,i,getbit(blob,len,i-c));
- }
+ for(int i = nbits-1; i >= 0; i--)
+ {
+ setbit(blob,len,i,getbit(blob,len,i-c));
+ }
}
void lshift8 ( void * blob, int nbytes, int c )
{
- uint8_t * k = (uint8_t*)blob;
+ uint8_t * k = (uint8_t*)blob;
- if(c == 0) return;
+ if(c == 0) return;
- int b = c >> 3;
- c &= 7;
+ int b = c >> 3;
+ c &= 7;
- for(int i = nbytes-1; i >= b; i--)
- {
- k[i] = k[i-b];
- }
+ for(int i = nbytes-1; i >= b; i--)
+ {
+ k[i] = k[i-b];
+ }
- for(int i = b-1; i >= 0; i--)
- {
- k[i] = 0;
- }
+ for(int i = b-1; i >= 0; i--)
+ {
+ k[i] = 0;
+ }
- if(c == 0) return;
+ if(c == 0) return;
- for(int i = nbytes-1; i >= 0; i--)
- {
- uint8_t a = k[i];
- uint8_t b = (i == 0) ? 0 : k[i-1];
+ for(int i = nbytes-1; i >= 0; i--)
+ {
+ uint8_t a = k[i];
+ uint8_t b = (i == 0) ? 0 : k[i-1];
- k[i] = (a << c) | (b >> (8-c));
- }
+ k[i] = (a << c) | (b >> (8-c));
+ }
}
void lshift32 ( void * blob, int len, int c )
{
- assert((len & 3) == 0);
+ assert((len & 3) == 0);
- int nbytes = len;
- int ndwords = nbytes / 4;
+ int nbytes = len;
+ int ndwords = nbytes / 4;
- uint32_t * k = (uint32_t*)blob;
+ uint32_t * k = (uint32_t*)blob;
- if(c == 0) return;
+ if(c == 0) return;
- //----------
+ //----------
- int b = c / 32;
- c &= (32-1);
+ int b = c / 32;
+ c &= (32-1);
- for(int i = ndwords-1; i >= b; i--)
- {
- k[i] = k[i-b];
- }
+ for(int i = ndwords-1; i >= b; i--)
+ {
+ k[i] = k[i-b];
+ }
- for(int i = b-1; i >= 0; i--)
- {
- k[i] = 0;
- }
+ for(int i = b-1; i >= 0; i--)
+ {
+ k[i] = 0;
+ }
- if(c == 0) return;
+ if(c == 0) return;
- for(int i = ndwords-1; i >= 0; i--)
- {
- uint32_t a = k[i];
- uint32_t b = (i == 0) ? 0 : k[i-1];
+ for(int i = ndwords-1; i >= 0; i--)
+ {
+ uint32_t a = k[i];
+ uint32_t b = (i == 0) ? 0 : k[i-1];
- k[i] = (a << c) | (b >> (32-c));
- }
+ k[i] = (a << c) | (b >> (32-c));
+ }
}
//-----------------------------------------------------------------------------
void rshift1 ( void * blob, int len, int c )
{
- int nbits = len*8;
+ int nbits = len*8;
- for(int i = 0; i < nbits; i++)
- {
- setbit(blob,len,i,getbit(blob,len,i+c));
- }
+ for(int i = 0; i < nbits; i++)
+ {
+ setbit(blob,len,i,getbit(blob,len,i+c));
+ }
}
void rshift8 ( void * blob, int nbytes, int c )
{
- uint8_t * k = (uint8_t*)blob;
+ uint8_t * k = (uint8_t*)blob;
- if(c == 0) return;
+ if(c == 0) return;
- int b = c >> 3;
- c &= 7;
+ int b = c >> 3;
+ c &= 7;
- for(int i = 0; i < nbytes-b; i++)
- {
- k[i] = k[i+b];
- }
+ for(int i = 0; i < nbytes-b; i++)
+ {
+ k[i] = k[i+b];
+ }
- for(int i = nbytes-b; i < nbytes; i++)
- {
- k[i] = 0;
- }
+ for(int i = nbytes-b; i < nbytes; i++)
+ {
+ k[i] = 0;
+ }
- if(c == 0) return;
+ if(c == 0) return;
- for(int i = 0; i < nbytes; i++)
- {
- uint8_t a = (i == nbytes-1) ? 0 : k[i+1];
- uint8_t b = k[i];
+ for(int i = 0; i < nbytes; i++)
+ {
+ uint8_t a = (i == nbytes-1) ? 0 : k[i+1];
+ uint8_t b = k[i];
- k[i] = (a << (8-c) ) | (b >> c);
- }
+ k[i] = (a << (8-c) ) | (b >> c);
+ }
}
void rshift32 ( void * blob, int len, int c )
{
- assert((len & 3) == 0);
+ assert((len & 3) == 0);
- int nbytes = len;
- int ndwords = nbytes / 4;
+ int nbytes = len;
+ int ndwords = nbytes / 4;
- uint32_t * k = (uint32_t*)blob;
+ uint32_t * k = (uint32_t*)blob;
- //----------
+ //----------
- if(c == 0) return;
+ if(c == 0) return;
- int b = c / 32;
- c &= (32-1);
+ int b = c / 32;
+ c &= (32-1);
- for(int i = 0; i < ndwords-b; i++)
- {
- k[i] = k[i+b];
- }
+ for(int i = 0; i < ndwords-b; i++)
+ {
+ k[i] = k[i+b];
+ }
- for(int i = ndwords-b; i < ndwords; i++)
- {
- k[i] = 0;
- }
+ for(int i = ndwords-b; i < ndwords; i++)
+ {
+ k[i] = 0;
+ }
- if(c == 0) return;
+ if(c == 0) return;
- for(int i = 0; i < ndwords; i++)
- {
- uint32_t a = (i == ndwords-1) ? 0 : k[i+1];
- uint32_t b = k[i];
+ for(int i = 0; i < ndwords; i++)
+ {
+ uint32_t a = (i == ndwords-1) ? 0 : k[i+1];
+ uint32_t b = k[i];
- k[i] = (a << (32-c) ) | (b >> c);
- }
+ k[i] = (a << (32-c) ) | (b >> c);
+ }
}
//-----------------------------------------------------------------------------
void lrot1 ( void * blob, int len, int c )
{
- int nbits = len * 8;
+ int nbits = len * 8;
- for(int i = 0; i < c; i++)
- {
- uint32_t bit = getbit(blob,len,nbits-1);
+ for(int i = 0; i < c; i++)
+ {
+ uint32_t bit = getbit(blob,len,nbits-1);
- lshift1(blob,len,1);
+ lshift1(blob,len,1);
- setbit(blob,len,0,bit);
- }
+ setbit(blob,len,0,bit);
+ }
}
void lrot8 ( void * blob, int len, int c )
{
- int nbytes = len;
+ int nbytes = len;
- uint8_t * k = (uint8_t*)blob;
+ uint8_t * k = (uint8_t*)blob;
- if(c == 0) return;
+ if(c == 0) return;
- //----------
+ //----------
- int b = c / 8;
- c &= (8-1);
+ int b = c / 8;
+ c &= (8-1);
- for(int j = 0; j < b; j++)
- {
- uint8_t t = k[nbytes-1];
+ for(int j = 0; j < b; j++)
+ {
+ uint8_t t = k[nbytes-1];
- for(int i = nbytes-1; i > 0; i--)
- {
- k[i] = k[i-1];
- }
+ for(int i = nbytes-1; i > 0; i--)
+ {
+ k[i] = k[i-1];
+ }
- k[0] = t;
- }
+ k[0] = t;
+ }
- uint8_t t = k[nbytes-1];
+ uint8_t t = k[nbytes-1];
- if(c == 0) return;
+ if(c == 0) return;
- for(int i = nbytes-1; i >= 0; i--)
- {
- uint8_t a = k[i];
- uint8_t b = (i == 0) ? t : k[i-1];
+ for(int i = nbytes-1; i >= 0; i--)
+ {
+ uint8_t a = k[i];
+ uint8_t b = (i == 0) ? t : k[i-1];
- k[i] = (a << c) | (b >> (8-c));
- }
+ k[i] = (a << c) | (b >> (8-c));
+ }
}
void lrot32 ( void * blob, int len, int c )
{
- assert((len & 3) == 0);
+ assert((len & 3) == 0);
- int nbytes = len;
- int ndwords = nbytes/4;
+ int nbytes = len;
+ int ndwords = nbytes/4;
- uint32_t * k = (uint32_t*)blob;
+ uint32_t * k = (uint32_t*)blob;
- if(c == 0) return;
+ if(c == 0) return;
- //----------
+ //----------
- int b = c / 32;
- c &= (32-1);
+ int b = c / 32;
+ c &= (32-1);
- for(int j = 0; j < b; j++)
- {
- uint32_t t = k[ndwords-1];
+ for(int j = 0; j < b; j++)
+ {
+ uint32_t t = k[ndwords-1];
- for(int i = ndwords-1; i > 0; i--)
- {
- k[i] = k[i-1];
- }
+ for(int i = ndwords-1; i > 0; i--)
+ {
+ k[i] = k[i-1];
+ }
- k[0] = t;
- }
+ k[0] = t;
+ }
- uint32_t t = k[ndwords-1];
+ uint32_t t = k[ndwords-1];
- if(c == 0) return;
+ if(c == 0) return;
- for(int i = ndwords-1; i >= 0; i--)
- {
- uint32_t a = k[i];
- uint32_t b = (i == 0) ? t : k[i-1];
+ for(int i = ndwords-1; i >= 0; i--)
+ {
+ uint32_t a = k[i];
+ uint32_t b = (i == 0) ? t : k[i-1];
- k[i] = (a << c) | (b >> (32-c));
- }
+ k[i] = (a << c) | (b >> (32-c));
+ }
}
//-----------------------------------------------------------------------------
void rrot1 ( void * blob, int len, int c )
{
- int nbits = len * 8;
+ int nbits = len * 8;
- for(int i = 0; i < c; i++)
- {
- uint32_t bit = getbit(blob,len,0);
+ for(int i = 0; i < c; i++)
+ {
+ uint32_t bit = getbit(blob,len,0);
- rshift1(blob,len,1);
+ rshift1(blob,len,1);
- setbit(blob,len,nbits-1,bit);
- }
+ setbit(blob,len,nbits-1,bit);
+ }
}
void rrot8 ( void * blob, int len, int c )
{
- int nbytes = len;
+ int nbytes = len;
- uint8_t * k = (uint8_t*)blob;
+ uint8_t * k = (uint8_t*)blob;
- if(c == 0) return;
+ if(c == 0) return;
- //----------
+ //----------
- int b = c / 8;
- c &= (8-1);
+ int b = c / 8;
+ c &= (8-1);
- for(int j = 0; j < b; j++)
- {
- uint8_t t = k[0];
+ for(int j = 0; j < b; j++)
+ {
+ uint8_t t = k[0];
- for(int i = 0; i < nbytes-1; i++)
- {
- k[i] = k[i+1];
- }
+ for(int i = 0; i < nbytes-1; i++)
+ {
+ k[i] = k[i+1];
+ }
- k[nbytes-1] = t;
- }
+ k[nbytes-1] = t;
+ }
- if(c == 0) return;
+ if(c == 0) return;
- //----------
+ //----------
- uint8_t t = k[0];
+ uint8_t t = k[0];
- for(int i = 0; i < nbytes; i++)
- {
- uint8_t a = (i == nbytes-1) ? t : k[i+1];
- uint8_t b = k[i];
+ for(int i = 0; i < nbytes; i++)
+ {
+ uint8_t a = (i == nbytes-1) ? t : k[i+1];
+ uint8_t b = k[i];
- k[i] = (a << (8-c)) | (b >> c);
- }
+ k[i] = (a << (8-c)) | (b >> c);
+ }
}
void rrot32 ( void * blob, int len, int c )
{
- assert((len & 3) == 0);
+ assert((len & 3) == 0);
- int nbytes = len;
- int ndwords = nbytes/4;
+ int nbytes = len;
+ int ndwords = nbytes/4;
- uint32_t * k = (uint32_t*)blob;
+ uint32_t * k = (uint32_t*)blob;
- if(c == 0) return;
+ if(c == 0) return;
- //----------
+ //----------
- int b = c / 32;
- c &= (32-1);
+ int b = c / 32;
+ c &= (32-1);
- for(int j = 0; j < b; j++)
- {
- uint32_t t = k[0];
+ for(int j = 0; j < b; j++)
+ {
+ uint32_t t = k[0];
- for(int i = 0; i < ndwords-1; i++)
- {
- k[i] = k[i+1];
- }
+ for(int i = 0; i < ndwords-1; i++)
+ {
+ k[i] = k[i+1];
+ }
- k[ndwords-1] = t;
- }
+ k[ndwords-1] = t;
+ }
- if(c == 0) return;
+ if(c == 0) return;
- //----------
+ //----------
- uint32_t t = k[0];
+ uint32_t t = k[0];
- for(int i = 0; i < ndwords; i++)
- {
- uint32_t a = (i == ndwords-1) ? t : k[i+1];
- uint32_t b = k[i];
+ for(int i = 0; i < ndwords; i++)
+ {
+ uint32_t a = (i == ndwords-1) ? t : k[i+1];
+ uint32_t b = k[i];
- k[i] = (a << (32-c)) | (b >> c);
- }
+ k[i] = (a << (32-c)) | (b >> c);
+ }
}
//-----------------------------------------------------------------------------
uint32_t window1 ( void * blob, int len, int start, int count )
{
- int nbits = len*8;
- start %= nbits;
+ int nbits = len*8;
+ start %= nbits;
- uint32_t t = 0;
+ uint32_t t = 0;
- for(int i = 0; i < count; i++)
- {
- setbit(&t,sizeof(t),i, getbit_wrap(blob,len,start+i));
- }
+ for(int i = 0; i < count; i++)
+ {
+ setbit(&t,sizeof(t),i, getbit_wrap(blob,len,start+i));
+ }
- return t;
+ return t;
}
uint32_t window8 ( void * blob, int len, int start, int count )
{
- int nbits = len*8;
- start %= nbits;
+ int nbits = len*8;
+ start %= nbits;
- uint32_t t = 0;
- uint8_t * k = (uint8_t*)blob;
+ uint32_t t = 0;
+ uint8_t * k = (uint8_t*)blob;
- if(count == 0) return 0;
+ if(count == 0) return 0;
- int c = start & (8-1);
- int d = start / 8;
+ int c = start & (8-1);
+ int d = start / 8;
- for(int i = 0; i < 4; i++)
- {
- int ia = (i + d + 1) % len;
- int ib = (i + d + 0) % len;
+ for(int i = 0; i < 4; i++)
+ {
+ int ia = (i + d + 1) % len;
+ int ib = (i + d + 0) % len;
- uint32_t a = k[ia];
- uint32_t b = k[ib];
-
- uint32_t m = (a << (8-c)) | (b >> c);
+ uint32_t a = k[ia];
+ uint32_t b = k[ib];
+
+ uint32_t m = (a << (8-c)) | (b >> c);
- t |= (m << (8*i));
+ t |= (m << (8*i));
- }
+ }
- t &= ((1 << count)-1);
+ t &= ((1 << count)-1);
- return t;
+ return t;
}
uint32_t window32 ( void * blob, int len, int start, int count )
{
- int nbits = len*8;
- start %= nbits;
+ int nbits = len*8;
+ start %= nbits;
- assert((len & 3) == 0);
+ assert((len & 3) == 0);
- int ndwords = len / 4;
+ int ndwords = len / 4;
- uint32_t * k = (uint32_t*)blob;
+ uint32_t * k = (uint32_t*)blob;
- if(count == 0) return 0;
+ if(count == 0) return 0;
- int c = start & (32-1);
- int d = start / 32;
+ int c = start & (32-1);
+ int d = start / 32;
- if(c == 0) return (k[d] & ((1 << count) - 1));
+ if(c == 0) return (k[d] & ((1 << count) - 1));
- int ia = (d + 1) % ndwords;
- int ib = (d + 0) % ndwords;
+ int ia = (d + 1) % ndwords;
+ int ib = (d + 0) % ndwords;
- uint32_t a = k[ia];
- uint32_t b = k[ib];
-
- uint32_t t = (a << (32-c)) | (b >> c);
+ uint32_t a = k[ia];
+ uint32_t b = k[ib];
+
+ uint32_t t = (a << (32-c)) | (b >> c);
- t &= ((1 << count)-1);
+ t &= ((1 << count)-1);
- return t;
+ return t;
}
//-----------------------------------------------------------------------------
bool test_shift ( void )
{
- int nbits = 64;
- int nbytes = nbits / 8;
- int reps = 10000;
-
- for(int j = 0; j < reps; j++)
- {
- if(j % (reps/10) == 0) printf(".");
-
- uint64_t a = rand_u64();
- uint64_t b;
-
- for(int i = 0; i < nbits; i++)
- {
- b = a; lshift1 (&b,nbytes,i); assert(b == (a << i));
- b = a; lshift8 (&b,nbytes,i); assert(b == (a << i));
- b = a; lshift32 (&b,nbytes,i); assert(b == (a << i));
-
- b = a; rshift1 (&b,nbytes,i); assert(b == (a >> i));
- b = a; rshift8 (&b,nbytes,i); assert(b == (a >> i));
- b = a; rshift32 (&b,nbytes,i); assert(b == (a >> i));
-
- b = a; lrot1 (&b,nbytes,i); assert(b == ROTL64(a,i));
- b = a; lrot8 (&b,nbytes,i); assert(b == ROTL64(a,i));
- b = a; lrot32 (&b,nbytes,i); assert(b == ROTL64(a,i));
-
- b = a; rrot1 (&b,nbytes,i); assert(b == ROTR64(a,i));
- b = a; rrot8 (&b,nbytes,i); assert(b == ROTR64(a,i));
- b = a; rrot32 (&b,nbytes,i); assert(b == ROTR64(a,i));
- }
- }
-
- printf("PASS\n");
- return true;
+ int nbits = 64;
+ int nbytes = nbits / 8;
+ int reps = 10000;
+
+ for(int j = 0; j < reps; j++)
+ {
+ if(j % (reps/10) == 0) printf(".");
+
+ uint64_t a = rand_u64();
+ uint64_t b;
+
+ for(int i = 0; i < nbits; i++)
+ {
+ b = a; lshift1 (&b,nbytes,i); assert(b == (a << i));
+ b = a; lshift8 (&b,nbytes,i); assert(b == (a << i));
+ b = a; lshift32 (&b,nbytes,i); assert(b == (a << i));
+
+ b = a; rshift1 (&b,nbytes,i); assert(b == (a >> i));
+ b = a; rshift8 (&b,nbytes,i); assert(b == (a >> i));
+ b = a; rshift32 (&b,nbytes,i); assert(b == (a >> i));
+
+ b = a; lrot1 (&b,nbytes,i); assert(b == ROTL64(a,i));
+ b = a; lrot8 (&b,nbytes,i); assert(b == ROTL64(a,i));
+ b = a; lrot32 (&b,nbytes,i); assert(b == ROTL64(a,i));
+
+ b = a; rrot1 (&b,nbytes,i); assert(b == ROTR64(a,i));
+ b = a; rrot8 (&b,nbytes,i); assert(b == ROTR64(a,i));
+ b = a; rrot32 (&b,nbytes,i); assert(b == ROTR64(a,i));
+ }
+ }
+
+ printf("PASS\n");
+ return true;
}
//-----------------------------------------------------------------------------
@@ -634,86 +634,86 @@ bool test_shift ( void ) template < int nbits >
bool test_window2 ( void )
{
- struct keytype
- {
- uint8_t bytes[nbits/8];
- };
+ struct keytype
+ {
+ uint8_t bytes[nbits/8];
+ };
- int nbytes = nbits / 8;
- int reps = 10000;
+ int nbytes = nbits / 8;
+ int reps = 10000;
- for(int j = 0; j < reps; j++)
- {
- if(j % (reps/10) == 0) printf(".");
+ for(int j = 0; j < reps; j++)
+ {
+ if(j % (reps/10) == 0) printf(".");
- keytype k;
+ keytype k;
- rand_p(&k,nbytes);
+ rand_p(&k,nbytes);
- for(int start = 0; start < nbits; start++)
- {
- for(int count = 0; count < 32; count++)
- {
- uint32_t a = window1(&k,nbytes,start,count);
- uint32_t b = window8(&k,nbytes,start,count);
- uint32_t c = window(&k,nbytes,start,count);
+ for(int start = 0; start < nbits; start++)
+ {
+ for(int count = 0; count < 32; count++)
+ {
+ uint32_t a = window1(&k,nbytes,start,count);
+ uint32_t b = window8(&k,nbytes,start,count);
+ uint32_t c = window(&k,nbytes,start,count);
- assert(a == b);
- assert(a == c);
- }
- }
- }
+ assert(a == b);
+ assert(a == c);
+ }
+ }
+ }
- printf("PASS %d\n",nbits);
+ printf("PASS %d\n",nbits);
- return true;
+ return true;
}
bool test_window ( void )
{
- int reps = 10000;
-
- for(int j = 0; j < reps; j++)
- {
- if(j % (reps/10) == 0) printf(".");
-
- int nbits = 64;
- int nbytes = nbits / 8;
-
- uint64_t x = rand_u64();
-
- for(int start = 0; start < nbits; start++)
- {
- for(int count = 0; count < 32; count++)
- {
- uint32_t a = (uint32_t)ROTR64(x,start);
- a &= ((1 << count)-1);
-
- uint32_t b = window1 (&x,nbytes,start,count);
- uint32_t c = window8 (&x,nbytes,start,count);
- uint32_t d = window32(&x,nbytes,start,count);
- uint32_t e = window (x,start,count);
-
- assert(a == b);
- assert(a == c);
- assert(a == d);
- assert(a == e);
- }
- }
- }
-
- printf("PASS 64\n");
-
- test_window2<8>();
- test_window2<16>();
- test_window2<24>();
- test_window2<32>();
- test_window2<40>();
- test_window2<48>();
- test_window2<56>();
- test_window2<64>();
-
- return true;
+ int reps = 10000;
+
+ for(int j = 0; j < reps; j++)
+ {
+ if(j % (reps/10) == 0) printf(".");
+
+ int nbits = 64;
+ int nbytes = nbits / 8;
+
+ uint64_t x = rand_u64();
+
+ for(int start = 0; start < nbits; start++)
+ {
+ for(int count = 0; count < 32; count++)
+ {
+ uint32_t a = (uint32_t)ROTR64(x,start);
+ a &= ((1 << count)-1);
+
+ uint32_t b = window1 (&x,nbytes,start,count);
+ uint32_t c = window8 (&x,nbytes,start,count);
+ uint32_t d = window32(&x,nbytes,start,count);
+ uint32_t e = window (x,start,count);
+
+ assert(a == b);
+ assert(a == c);
+ assert(a == d);
+ assert(a == e);
+ }
+ }
+ }
+
+ printf("PASS 64\n");
+
+ test_window2<8>();
+ test_window2<16>();
+ test_window2<24>();
+ test_window2<32>();
+ test_window2<40>();
+ test_window2<48>();
+ test_window2<56>();
+ test_window2<64>();
+
+ return true;
}
//-----------------------------------------------------------------------------
@@ -32,7 +32,7 @@ void invert ( std::vector<uint32_t> & v ); template< typename T >
inline uint32_t getbit ( T & blob, uint32_t bit )
{
- return getbit(&blob,sizeof(blob),bit);
+ return getbit(&blob,sizeof(blob),bit);
}
template<> inline uint32_t getbit ( uint32_t & blob, uint32_t bit ) { return (blob >> (bit & 31)) & 1; }
@@ -43,7 +43,7 @@ template<> inline uint32_t getbit ( uint64_t & blob, uint32_t bit ) { return (bl template< typename T >
inline void setbit ( T & blob, uint32_t bit )
{
- return setbit(&blob,sizeof(blob),bit);
+ return setbit(&blob,sizeof(blob),bit);
}
template<> inline void setbit ( uint32_t & blob, uint32_t bit ) { blob |= uint32_t(1) << (bit & 31); }
@@ -54,7 +54,7 @@ template<> inline void setbit ( uint64_t & blob, uint32_t bit ) { blob |= uint64 template< typename T >
inline void flipbit ( T & blob, uint32_t bit )
{
- flipbit(&blob,sizeof(blob),bit);
+ flipbit(&blob,sizeof(blob),bit);
}
template<> inline void flipbit ( uint32_t & blob, uint32_t bit ) { bit &= 31; blob ^= (uint32_t(1) << bit); }
@@ -74,52 +74,52 @@ void rshift32 ( void * blob, int len, int c ); inline void lshift ( void * blob, int len, int c )
{
- if((len & 3) == 0)
- {
- lshift32(blob,len,c);
- }
- else
- {
- lshift8(blob,len,c);
- }
+ if((len & 3) == 0)
+ {
+ lshift32(blob,len,c);
+ }
+ else
+ {
+ lshift8(blob,len,c);
+ }
}
inline void rshift ( void * blob, int len, int c )
{
- if((len & 3) == 0)
- {
- rshift32(blob,len,c);
- }
- else
- {
- rshift8(blob,len,c);
- }
+ if((len & 3) == 0)
+ {
+ rshift32(blob,len,c);
+ }
+ else
+ {
+ rshift8(blob,len,c);
+ }
}
template < typename T >
inline void lshift ( T & blob, int c )
{
- if((sizeof(T) & 3) == 0)
- {
- lshift32(&blob,sizeof(T),c);
- }
- else
- {
- lshift8(&blob,sizeof(T),c);
- }
+ if((sizeof(T) & 3) == 0)
+ {
+ lshift32(&blob,sizeof(T),c);
+ }
+ else
+ {
+ lshift8(&blob,sizeof(T),c);
+ }
}
template < typename T >
inline void rshift ( T & blob, int c )
{
- if((sizeof(T) & 3) == 0)
- {
- lshift32(&blob,sizeof(T),c);
- }
- else
- {
- lshift8(&blob,sizeof(T),c);
- }
+ if((sizeof(T) & 3) == 0)
+ {
+ lshift32(&blob,sizeof(T),c);
+ }
+ else
+ {
+ lshift8(&blob,sizeof(T),c);
+ }
}
template<> inline void lshift ( uint32_t & blob, int c ) { blob <<= c; }
@@ -141,52 +141,52 @@ void rrot32 ( void * blob, int len, int c ); inline void lrot ( void * blob, int len, int c )
{
- if((len & 3) == 0)
- {
- return lrot32(blob,len,c);
- }
- else
- {
- return lrot8(blob,len,c);
- }
+ if((len & 3) == 0)
+ {
+ return lrot32(blob,len,c);
+ }
+ else
+ {
+ return lrot8(blob,len,c);
+ }
}
inline void rrot ( void * blob, int len, int c )
{
- if((len & 3) == 0)
- {
- return rrot32(blob,len,c);
- }
- else
- {
- return rrot8(blob,len,c);
- }
+ if((len & 3) == 0)
+ {
+ return rrot32(blob,len,c);
+ }
+ else
+ {
+ return rrot8(blob,len,c);
+ }
}
template < typename T >
inline void lrot ( T & blob, int c )
{
- if((sizeof(T) & 3) == 0)
- {
- return lrot32(&blob,sizeof(T),c);
- }
- else
- {
- return lrot8(&blob,sizeof(T),c);
- }
+ if((sizeof(T) & 3) == 0)
+ {
+ return lrot32(&blob,sizeof(T),c);
+ }
+ else
+ {
+ return lrot8(&blob,sizeof(T),c);
+ }
}
template < typename T >
inline void rrot ( T & blob, int c )
{
- if((sizeof(T) & 3) == 0)
- {
- return rrot32(&blob,sizeof(T),c);
- }
- else
- {
- return rrot8(&blob,sizeof(T),c);
- }
+ if((sizeof(T) & 3) == 0)
+ {
+ return rrot32(&blob,sizeof(T),c);
+ }
+ else
+ {
+ return rrot8(&blob,sizeof(T),c);
+ }
}
template<> inline void lrot ( uint32_t & blob, int c ) { blob = ROTL32(blob,c); }
@@ -203,39 +203,39 @@ uint32_t window32 ( void * blob, int len, int start, int count ); inline uint32_t window ( void * blob, int len, int start, int count )
{
- if(len & 3)
- {
- return window8(blob,len,start,count);
- }
- else
- {
- return window32(blob,len,start,count);
- }
+ if(len & 3)
+ {
+ return window8(blob,len,start,count);
+ }
+ else
+ {
+ return window32(blob,len,start,count);
+ }
}
template < typename T >
inline uint32_t window ( T & blob, int start, int count )
{
- if((sizeof(T) & 3) == 0)
- {
- return window32(&blob,sizeof(T),start,count);
- }
- else
- {
- return window8(&blob,sizeof(T),start,count);
- }
+ if((sizeof(T) & 3) == 0)
+ {
+ return window32(&blob,sizeof(T),start,count);
+ }
+ else
+ {
+ return window8(&blob,sizeof(T),start,count);
+ }
}
template<>
inline uint32_t window ( uint32_t & blob, int start, int count )
{
- return ROTR32(blob,start) & ((1<<count)-1);
+ return ROTR32(blob,start) & ((1<<count)-1);
}
template<>
inline uint32_t window ( uint64_t & blob, int start, int count )
{
- return (uint32_t)ROTR64(blob,start) & ((1<<count)-1);
+ return (uint32_t)ROTR64(blob,start) & ((1<<count)-1);
}
//-----------------------------------------------------------------------------
diff --git a/DifferentialTest.h b/DifferentialTest.h index 16d2049..0894c0a 100644 --- a/DifferentialTest.h +++ b/DifferentialTest.h @@ -20,75 +20,75 @@ template < class keytype >
bool ProcessDifferentials ( std::vector<keytype> & diffs, int reps, bool dumpCollisions )
{
- std::sort(diffs.begin(), diffs.end());
-
- int count = 1;
- int ignore = 0;
-
- bool result = true;
-
- if(diffs.size())
- {
- keytype kp = diffs[0];
-
- for(int i = 1; i < (int)diffs.size(); i++)
- {
- if(diffs[i] == kp)
- {
- count++;
- continue;
- }
- else
- {
- if(count > 1)
- {
- result = false;
-
- double pct = 100 * (double(count) / double(reps));
-
- if(dumpCollisions)
- {
- printbits((unsigned char*)&kp,sizeof(kp));
- printf(" - %4.2f%%\n", pct );
- }
- }
- else
- {
- ignore++;
- }
-
- kp = diffs[i];
- count = 1;
- }
- }
-
- if(count > 1)
- {
- double pct = 100 * (double(count) / double(reps));
-
- if(dumpCollisions)
- {
- printbits((unsigned char*)&kp,sizeof(kp));
- printf(" - %4.2f%%\n", pct );
- }
- }
- else
- {
- ignore++;
- }
- }
-
- printf("%d total collisions, of which %d single collisions were ignored",(int)diffs.size(),ignore);
-
- if(result == false)
- {
- printf(" !!!!! ");
- }
-
- printf("\n");
- printf("\n");
-
- return result;
+ std::sort(diffs.begin(), diffs.end());
+
+ int count = 1;
+ int ignore = 0;
+
+ bool result = true;
+
+ if(diffs.size())
+ {
+ keytype kp = diffs[0];
+
+ for(int i = 1; i < (int)diffs.size(); i++)
+ {
+ if(diffs[i] == kp)
+ {
+ count++;
+ continue;
+ }
+ else
+ {
+ if(count > 1)
+ {
+ result = false;
+
+ double pct = 100 * (double(count) / double(reps));
+
+ if(dumpCollisions)
+ {
+ printbits((unsigned char*)&kp,sizeof(kp));
+ printf(" - %4.2f%%\n", pct );
+ }
+ }
+ else
+ {
+ ignore++;
+ }
+
+ kp = diffs[i];
+ count = 1;
+ }
+ }
+
+ if(count > 1)
+ {
+ double pct = 100 * (double(count) / double(reps));
+
+ if(dumpCollisions)
+ {
+ printbits((unsigned char*)&kp,sizeof(kp));
+ printf(" - %4.2f%%\n", pct );
+ }
+ }
+ else
+ {
+ ignore++;
+ }
+ }
+
+ printf("%d total collisions, of which %d single collisions were ignored",(int)diffs.size(),ignore);
+
+ if(result == false)
+ {
+ printf(" !!!!! ");
+ }
+
+ printf("\n");
+ printf("\n");
+
+ return result;
}
//-----------------------------------------------------------------------------
@@ -102,28 +102,28 @@ bool ProcessDifferentials ( std::vector<keytype> & diffs, int reps, bool dumpCol template < typename keytype, typename hashtype >
void DiffTestRecurse ( pfHash hash, keytype & k1, keytype & k2, hashtype & h1, hashtype & h2, int start, int bitsleft, std::vector<keytype> & diffs )
{
- const int bits = sizeof(keytype)*8;
+ const int bits = sizeof(keytype)*8;
- for(int i = start; i < bits; i++)
- {
- flipbit(&k2,sizeof(k2),i);
- bitsleft--;
+ for(int i = start; i < bits; i++)
+ {
+ flipbit(&k2,sizeof(k2),i);
+ bitsleft--;
- hash(&k2,sizeof(k2),0,&h2);
+ hash(&k2,sizeof(k2),0,&h2);
- if(h1 == h2)
- {
- diffs.push_back(k1 ^ k2);
- }
+ if(h1 == h2)
+ {
+ diffs.push_back(k1 ^ k2);
+ }
- if(bitsleft)
- {
- DiffTestRecurse(hash,k1,k2,h1,h2,i+1,bitsleft,diffs);
- }
+ if(bitsleft)
+ {
+ DiffTestRecurse(hash,k1,k2,h1,h2,i+1,bitsleft,diffs);
+ }
- flipbit(&k2,sizeof(k2),i);
- bitsleft++;
- }
+ flipbit(&k2,sizeof(k2),i);
+ bitsleft++;
+ }
}
//----------
@@ -131,39 +131,39 @@ void DiffTestRecurse ( pfHash hash, keytype & k1, keytype & k2, hashtype & h1, h template < typename keytype, typename hashtype >
bool DiffTest ( pfHash hash, int diffbits, int reps, bool dumpCollisions )
{
- const int keybits = sizeof(keytype) * 8;
- const int hashbits = sizeof(hashtype) * 8;
+ const int keybits = sizeof(keytype) * 8;
+ const int hashbits = sizeof(hashtype) * 8;
- double diffcount = chooseUpToK(keybits,diffbits);
- double testcount = (diffcount * double(reps));
- double expected = testcount / pow(2.0,double(hashbits));
+ double diffcount = chooseUpToK(keybits,diffbits);
+ double testcount = (diffcount * double(reps));
+ double expected = testcount / pow(2.0,double(hashbits));
- std::vector<keytype> diffs;
+ std::vector<keytype> diffs;
- keytype k1,k2;
- hashtype h1,h2;
+ keytype k1,k2;
+ hashtype h1,h2;
- printf("Testing %0.f up-to-%d-bit differentials in %d-bit keys -> %d bit hashes.\n",diffcount,diffbits,keybits,hashbits);
- printf("%d reps, %0.f total tests, expecting %2.2f random collisions",reps,testcount,expected);
+ printf("Testing %0.f up-to-%d-bit differentials in %d-bit keys -> %d bit hashes.\n",diffcount,diffbits,keybits,hashbits);
+ printf("%d reps, %0.f total tests, expecting %2.2f random collisions",reps,testcount,expected);
- for(int i = 0; i < reps; i++)
- {
- if(i % (reps/10) == 0) printf(".");
+ for(int i = 0; i < reps; i++)
+ {
+ if(i % (reps/10) == 0) printf(".");
- rand_p(&k1,sizeof(k1));
- k2 = k1;
+ rand_p(&k1,sizeof(k1));
+ k2 = k1;
- hash(&k1,sizeof(k1),0,(uint32_t*)&h1);
+ hash(&k1,sizeof(k1),0,(uint32_t*)&h1);
- DiffTestRecurse<keytype,hashtype>(hash,k1,k2,h1,h2,0,diffbits,diffs);
- }
- printf("\n");
+ DiffTestRecurse<keytype,hashtype>(hash,k1,k2,h1,h2,0,diffbits,diffs);
+ }
+ printf("\n");
- bool result = true;
+ bool result = true;
- result &= ProcessDifferentials(diffs,reps,dumpCollisions);
+ result &= ProcessDifferentials(diffs,reps,dumpCollisions);
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -185,53 +185,53 @@ bool DiffTest ( pfHash hash, int diffbits, int reps, bool dumpCollisions ) template < typename keytype, typename hashtype >
void DiffDistTest ( pfHash hash, const int diffbits, int trials, double & worst, double & avg )
{
- std::vector<keytype> keys(trials);
- std::vector<hashtype> A(trials),B(trials);
+ std::vector<keytype> keys(trials);
+ std::vector<hashtype> A(trials),B(trials);
- for(int i = 0; i < trials; i++)
- {
- rand_p(&keys[i],sizeof(keytype));
+ for(int i = 0; i < trials; i++)
+ {
+ rand_p(&keys[i],sizeof(keytype));
- hash(&keys[i],sizeof(keytype),0,(uint32_t*)&A[i]);
- }
+ hash(&keys[i],sizeof(keytype),0,(uint32_t*)&A[i]);
+ }
- //----------
+ //----------
- std::vector<keytype> diffs;
+ std::vector<keytype> diffs;
- keytype temp(0);
+ keytype temp(0);
- SparseKeygenRecurse<keytype>(0,diffbits,true,temp,diffs);
+ SparseKeygenRecurse<keytype>(0,diffbits,true,temp,diffs);
- //----------
+ //----------
- worst = 0;
- avg = 0;
+ worst = 0;
+ avg = 0;
- hashtype h2;
+ hashtype h2;
- for(size_t j = 0; j < diffs.size(); j++)
- {
- keytype & d = diffs[j];
+ for(size_t j = 0; j < diffs.size(); j++)
+ {
+ keytype & d = diffs[j];
- for(int i = 0; i < trials; i++)
- {
- keytype k2 = keys[i] ^ d;
+ for(int i = 0; i < trials; i++)
+ {
+ keytype k2 = keys[i] ^ d;
- hash(&k2,sizeof(k2),0,&h2);
+ hash(&k2,sizeof(k2),0,&h2);
- B[i] = A[i] ^ h2;
- }
+ B[i] = A[i] ^ h2;
+ }
- double dworst,davg;
+ double dworst,davg;
- TestDistributionFast(B,dworst,davg);
+ TestDistributionFast(B,dworst,davg);
- avg += davg;
- worst = (dworst > worst) ? dworst : worst;
- }
+ avg += davg;
+ worst = (dworst > worst) ? dworst : worst;
+ }
- avg /= double(diffs.size());
+ avg /= double(diffs.size());
}
//----------------------------------------------------------------------------
@@ -12,72 +12,52 @@ //----------------------------------------------------------------------------
// fake / bad hashes
-void randhash_32 ( const void *, int, uint32_t, void * out )
-{
- ((uint32_t*)out)[0] = rand_u32();
-}
-
-void randhash_64 ( const void *, int, uint32_t, void * out )
-{
- ((uint32_t*)out)[0] = rand_u32();
- ((uint32_t*)out)[1] = rand_u32();
-}
-
-void randhash_128 ( const void *, int, uint32_t, void * out )
-{
- ((uint32_t*)out)[0] = rand_u32();
- ((uint32_t*)out)[1] = rand_u32();
- ((uint32_t*)out)[2] = rand_u32();
- ((uint32_t*)out)[3] = rand_u32();
-}
-
void BadHash ( const void * key, int len, uint32_t seed, void * out )
{
- uint32_t h = seed;
+ uint32_t h = seed;
- const uint8_t * data = (const uint8_t*)key;
+ const uint8_t * data = (const uint8_t*)key;
- for(int i = 0; i < len; i++)
- {
- h ^= h >> 3;
- h ^= h << 5;
- h ^= data[i];
- }
+ for(int i = 0; i < len; i++)
+ {
+ h ^= h >> 3;
+ h ^= h << 5;
+ h ^= data[i];
+ }
- *(uint32_t*)out = h;
+ *(uint32_t*)out = h;
}
void sumhash ( const void * key, int len, uint32_t seed, void * out )
{
- uint32_t h = seed;
+ uint32_t h = seed;
- const uint8_t * data = (const uint8_t*)key;
+ const uint8_t * data = (const uint8_t*)key;
- for(int i = 0; i < len; i++)
- {
- h += data[i];
- }
+ for(int i = 0; i < len; i++)
+ {
+ h += data[i];
+ }
- *(uint32_t*)out = h;
+ *(uint32_t*)out = h;
}
void sumhash32 ( const void * key, int len, uint32_t seed, void * out )
{
- uint32_t h = seed;
+ uint32_t h = seed;
- const uint32_t * data = (const uint32_t*)key;
+ const uint32_t * data = (const uint32_t*)key;
- for(int i = 0; i < len/4; i++)
- {
- h += data[i];
- }
+ for(int i = 0; i < len/4; i++)
+ {
+ h += data[i];
+ }
- *(uint32_t*)out = h;
+ *(uint32_t*)out = h;
}
void DoNothingHash ( const void *, int, uint32_t, void * )
{
- return;
}
//-----------------------------------------------------------------------------
@@ -85,50 +65,50 @@ void DoNothingHash ( const void *, int, uint32_t, void * ) void MurmurOAAT ( const void * key, int len, uint32_t seed, void * out )
{
- const uint8_t * data = (const uint8_t*)key;
+ const uint8_t * data = (const uint8_t*)key;
- uint32_t h = seed ^ len;
+ uint32_t h = seed ^ len;
- for(int i = 0; i < len; i++)
- {
- h ^= data[i];
- h *= 0x5bd1e995;
- h ^= h >> 15;
- }
+ for(int i = 0; i < len; i++)
+ {
+ h ^= data[i];
+ h *= 0x5bd1e995;
+ h ^= h >> 15;
+ }
- h *= 0x5bd1e995;
- h ^= h >> 15;
+ h *= 0x5bd1e995;
+ h ^= h >> 15;
- *(uint32_t*)out = h;
+ *(uint32_t*)out = h;
}
//----------------------------------------------------------------------------
void FNV ( const void * key, int len, uint32_t seed, void * out )
{
- unsigned int h = seed;
+ unsigned int h = seed;
- const uint8_t * data = (const uint8_t*)key;
+ const uint8_t * data = (const uint8_t*)key;
- h ^= BIG_CONSTANT(2166136261);
+ h ^= BIG_CONSTANT(2166136261);
- for(int i = 0; i < len; i++)
- {
- h ^= data[i];
- h *= 16777619;
- }
+ for(int i = 0; i < len; i++)
+ {
+ h ^= data[i];
+ h *= 16777619;
+ }
- *(uint32_t*)out = h;
+ *(uint32_t*)out = h;
}
//-----------------------------------------------------------------------------
uint32_t x17 ( const void * key, int len, uint32_t h )
{
- const uint8_t * data = (const uint8_t*)key;
+ const uint8_t * data = (const uint8_t*)key;
- for(int i = 0; i < len; ++i)
- {
+ for(int i = 0; i < len; ++i)
+ {
h = 17 * h + (data[i] - ' ');
}
@@ -139,14 +119,14 @@ uint32_t x17 ( const void * key, int len, uint32_t h ) uint32_t Bernstein ( const void * key, int len, uint32_t h )
{
- const uint8_t * data = (const uint8_t*)key;
+ const uint8_t * data = (const uint8_t*)key;
- for(int i = 0; i < len; ++i)
- {
+ for(int i = 0; i < len; ++i)
+ {
h = 33 * h + data[i];
}
- return h;
+ return h;
}
//-----------------------------------------------------------------------------
@@ -44,25 +44,25 @@ void MurmurHash2A_test ( const void * key, int len, uint32_t seed, void * ou inline void MurmurHash1_test ( const void * key, int len, uint32_t seed, void * out )
{
- *(uint32_t*)out = MurmurHash1(key,len,seed);
+ *(uint32_t*)out = MurmurHash1(key,len,seed);
}
inline void MurmurHash2_test ( const void * key, int len, uint32_t seed, void * out )
{
- *(uint32_t*)out = MurmurHash2(key,len,seed);
+ *(uint32_t*)out = MurmurHash2(key,len,seed);
}
inline void MurmurHash2A_test ( const void * key, int len, uint32_t seed, void * out )
{
- *(uint32_t*)out = MurmurHash2A(key,len,seed);
+ *(uint32_t*)out = MurmurHash2A(key,len,seed);
}
inline void MurmurHash64A_test ( const void * key, int len, uint32_t seed, void * out )
{
- *(uint64_t*)out = MurmurHash64A(key,len,seed);
+ *(uint64_t*)out = MurmurHash64A(key,len,seed);
}
inline void MurmurHash64B_test ( const void * key, int len, uint32_t seed, void * out )
{
- *(uint64_t*)out = MurmurHash64B(key,len,seed);
+ *(uint64_t*)out = MurmurHash64B(key,len,seed);
}
\ No newline at end of file diff --git a/KeysetTest.cpp b/KeysetTest.cpp index 6436826..a59fda4 100644 --- a/KeysetTest.cpp +++ b/KeysetTest.cpp @@ -3,29 +3,50 @@ #include "Random.h"
//-----------------------------------------------------------------------------
+// This should hopefully be a thorough and uambiguous test of whether a hash
+// is correctly implemented on a given platform
-void QuickBrownFox ( pfHash hash, const int hashbits )
+bool VerificationTest ( pfHash hash, const int hashbits, uint32_t expected, bool verbose )
{
- const int hashbytes = hashbits / 8;
+ const int hashbytes = hashbits / 8;
- const char * text1 = "The quick brown fox jumps over the lazy dog";
- const char * text2 = "The quick brown fox jumps over the lazy cog";
+ uint8_t * key = new uint8_t[256];
+ uint8_t * hashes = new uint8_t[hashbytes * 256];
+ uint8_t * final = new uint8_t[hashbytes];
- uint8_t h1[128];
- uint8_t h2[128];
+ memset(key,0,256);
+ memset(hashes,0,hashbytes*256);
+ memset(final,0,hashbytes);
- hash(text1,(int)strlen(text1),0,h1);
- hash(text2,(int)strlen(text2),0,h2);
+ for(int i = 0; i < 256; i++)
+ {
+ key[i] = (uint8_t)i;
+
+ hash(key,i,0,&hashes[i*hashbytes]);
+ }
- printf("\"%s\" => ",text1);
- printhex32(h1,hashbytes);
- printf("\n");
+ //----------
- printf("\"%s\" => ",text2);
- printhex32(h2,hashbytes);
- printf("\n");
+ hash(hashes,hashbytes*256,0,final);
- printf("\n");
+ uint32_t verification = (final[0] << 0) | (final[1] << 8) | (final[2] << 16) | (final[3] << 24);
+
+ delete [] key;
+ delete [] hashes;
+ delete [] final;
+
+ //----------
+
+ if(expected != verification)
+ {
+ if(verbose) printf("Verification value 0x%08X : Failed! (Expected 0x%08x)\n",verification,expected);
+ return false;
+ }
+ else
+ {
+ if(verbose) printf("Verification value 0x%08X : Passed!\n",verification);
+ return true;
+ }
}
//----------------------------------------------------------------------------
@@ -41,81 +62,82 @@ void QuickBrownFox ( pfHash hash, const int hashbits ) // The memory alignment of the key should not affect the hash result.
bool SanityTest ( pfHash hash, const int hashbits )
-{ printf("Testing bit twiddling");
-
- bool result = true;
-
- const int hashbytes = hashbits/8;
- const int reps = 10;
- const int keymax = 128;
- const int pad = 16;
- const int buflen = keymax + pad*3;
-
- uint8_t * buffer1 = new uint8_t[buflen];
- uint8_t * buffer2 = new uint8_t[buflen];
-
- uint8_t * hash1 = new uint8_t[hashbytes];
- uint8_t * hash2 = new uint8_t[hashbytes];
-
- //----------
-
- for(int irep = 0; irep < reps; irep++)
- {
- if(irep % (reps/10) == 0) printf(".");
-
- for(int len = 4; len <= keymax; len++)
- {
- for(int offset = pad; offset < pad*2; offset++)
- {
- uint8_t * key1 = &buffer1[pad];
- uint8_t * key2 = &buffer2[pad+offset];
-
- rand_p(buffer1,buflen);
- rand_p(buffer2,buflen);
-
- memcpy(key2,key1,len);
-
- hash(key1,len,0,hash1);
-
- for(int bit = 0; bit < (len * 8); bit++)
- {
- // Flip a bit, hash the key -> we should get a different result.
-
- flipbit(key2,len,bit);
- hash(key2,len,0,hash2);
-
- if(memcmp(hash1,hash2,hashbytes) == 0)
- {
- result = false;
- }
-
- // Flip it back, hash again -> we should get the original result.
-
- flipbit(key2,len,bit);
- hash(key2,len,0,hash2);
-
- if(memcmp(hash1,hash2,hashbytes) != 0)
- {
- result = false;
- }
- }
- }
- }
- }
-
- if(result == false)
- {
- printf("*********FAIL*********\n");
- }
- else
- {
- printf("PASS\n");
- }
-
- delete [] hash1;
- delete [] hash2;
-
- return result;
+{
+ printf("Running sanity check 1");
+
+ bool result = true;
+
+ const int hashbytes = hashbits/8;
+ const int reps = 10;
+ const int keymax = 128;
+ const int pad = 16;
+ const int buflen = keymax + pad*3;
+
+ uint8_t * buffer1 = new uint8_t[buflen];
+ uint8_t * buffer2 = new uint8_t[buflen];
+
+ uint8_t * hash1 = new uint8_t[hashbytes];
+ uint8_t * hash2 = new uint8_t[hashbytes];
+
+ //----------
+
+ for(int irep = 0; irep < reps; irep++)
+ {
+ if(irep % (reps/10) == 0) printf(".");
+
+ for(int len = 4; len <= keymax; len++)
+ {
+ for(int offset = pad; offset < pad*2; offset++)
+ {
+ uint8_t * key1 = &buffer1[pad];
+ uint8_t * key2 = &buffer2[pad+offset];
+
+ rand_p(buffer1,buflen);
+ rand_p(buffer2,buflen);
+
+ memcpy(key2,key1,len);
+
+ hash(key1,len,0,hash1);
+
+ for(int bit = 0; bit < (len * 8); bit++)
+ {
+ // Flip a bit, hash the key -> we should get a different result.
+
+ flipbit(key2,len,bit);
+ hash(key2,len,0,hash2);
+
+ if(memcmp(hash1,hash2,hashbytes) == 0)
+ {
+ result = false;
+ }
+
+ // Flip it back, hash again -> we should get the original result.
+
+ flipbit(key2,len,bit);
+ hash(key2,len,0,hash2);
+
+ if(memcmp(hash1,hash2,hashbytes) != 0)
+ {
+ result = false;
+ }
+ }
+ }
+ }
+ }
+
+ if(result == false)
+ {
+ printf("*********FAIL*********\n");
+ }
+ else
+ {
+ printf("PASS\n");
+ }
+
+ delete [] hash1;
+ delete [] hash2;
+
+ return result;
}
//----------------------------------------------------------------------------
@@ -124,41 +146,41 @@ bool SanityTest ( pfHash hash, const int hashbits ) void AppendedZeroesTest ( pfHash hash, const int hashbits )
{
- const int hashbytes = hashbits/8;
+ printf("Running sanity check 2");
- printf("Testing zero-appending");
+ const int hashbytes = hashbits/8;
- for(int rep = 0; rep < 100; rep++)
- {
- if(rep % 10 == 0) printf(".");
+ for(int rep = 0; rep < 100; rep++)
+ {
+ if(rep % 10 == 0) printf(".");
- unsigned char key[256];
+ unsigned char key[256];
- memset(key,0,sizeof(key));
+ memset(key,0,sizeof(key));
- rand_p(key,32);
+ rand_p(key,32);
- uint32_t h1[16];
- uint32_t h2[16];
+ uint32_t h1[16];
+ uint32_t h2[16];
- memset(h1,0,hashbytes);
- memset(h2,0,hashbytes);
+ memset(h1,0,hashbytes);
+ memset(h2,0,hashbytes);
- for(int i = 0; i < 32; i++)
- {
- hash(key,32+i,0,h1);
+ for(int i = 0; i < 32; i++)
+ {
+ hash(key,32+i,0,h1);
- if(memcmp(h1,h2,hashbytes) == 0)
- {
- printf("\n*********FAIL*********\n");
- return;
- }
+ if(memcmp(h1,h2,hashbytes) == 0)
+ {
+ printf("\n*********FAIL*********\n");
+ return;
+ }
- memcpy(h2,h1,hashbytes);
- }
- }
+ memcpy(h2,h1,hashbytes);
+ }
+ }
- printf("PASS\n");
+ printf("PASS\n");
}
//-----------------------------------------------------------------------------
diff --git a/KeysetTest.h b/KeysetTest.h index 17ded7b..c2a5c33 100644 --- a/KeysetTest.h +++ b/KeysetTest.h @@ -16,9 +16,8 @@ //-----------------------------------------------------------------------------
// Sanity tests
+bool VerificationTest ( pfHash hash, const int hashbits, uint32_t expected, bool verbose );
bool SanityTest ( pfHash hash, const int hashbits );
-void QuickBrownFox ( pfHash hash, const int hashbits );
-void AlignmentTest ( pfHash hash, const int hashbits );
void AppendedZeroesTest ( pfHash hash, const int hashbits );
//-----------------------------------------------------------------------------
@@ -26,55 +25,55 @@ void AppendedZeroesTest ( pfHash hash, const int hashbits ); template< typename hashtype >
void CombinationKeygenRecurse ( uint32_t * key, int len, int maxlen,
- uint32_t * blocks, int blockcount,
- pfHash hash, std::vector<hashtype> & hashes )
+ uint32_t * blocks, int blockcount,
+ pfHash hash, std::vector<hashtype> & hashes )
{
- if(len == maxlen) return;
-
- for(int i = 0; i < blockcount; i++)
- {
- key[len] = blocks[i];
-
- //if(len == maxlen-1)
- {
- hashtype h;
- hash(key,(len+1) * sizeof(uint32_t),0,&h);
- hashes.push_back(h);
- }
-
- //else
- {
- CombinationKeygenRecurse(key,len+1,maxlen,blocks,blockcount,hash,hashes);
- }
- }
+ if(len == maxlen) return;
+
+ for(int i = 0; i < blockcount; i++)
+ {
+ key[len] = blocks[i];
+
+ //if(len == maxlen-1)
+ {
+ hashtype h;
+ hash(key,(len+1) * sizeof(uint32_t),0,&h);
+ hashes.push_back(h);
+ }
+
+ //else
+ {
+ CombinationKeygenRecurse(key,len+1,maxlen,blocks,blockcount,hash,hashes);
+ }
+ }
}
template< typename hashtype >
bool CombinationKeyTest ( hashfunc<hashtype> hash, int maxlen, uint32_t * blocks, int blockcount, bool testColl, bool testDist, bool drawDiagram )
{
- printf("Keyset 'Combination' - up to %d blocks from a set of %d - ",maxlen,blockcount);
+ printf("Keyset 'Combination' - up to %d blocks from a set of %d - ",maxlen,blockcount);
- //----------
+ //----------
- std::vector<hashtype> hashes;
+ std::vector<hashtype> hashes;
- uint32_t * key = new uint32_t[maxlen];
+ uint32_t * key = new uint32_t[maxlen];
- CombinationKeygenRecurse<hashtype>(key,0,maxlen,blocks,blockcount,hash,hashes);
+ CombinationKeygenRecurse<hashtype>(key,0,maxlen,blocks,blockcount,hash,hashes);
- delete [] key;
+ delete [] key;
- printf("%d keys\n",(int)hashes.size());
+ printf("%d keys\n",(int)hashes.size());
- //----------
+ //----------
- bool result = true;
+ bool result = true;
- result &= TestHashList<hashtype>(hashes,testColl,testDist,drawDiagram);
-
- printf("\n");
+ result &= TestHashList<hashtype>(hashes,testColl,testDist,drawDiagram);
+
+ printf("\n");
- return result;
+ return result;
}
//----------------------------------------------------------------------------
@@ -84,49 +83,49 @@ bool CombinationKeyTest ( hashfunc<hashtype> hash, int maxlen, uint32_t * blocks template< typename hashtype >
void PermutationKeygenRecurse ( pfHash hash, uint32_t * blocks, int blockcount, int k, std::vector<hashtype> & hashes )
{
- if(k == blockcount-1)
- {
- hashtype h;
+ if(k == blockcount-1)
+ {
+ hashtype h;
- hash(blocks,blockcount * sizeof(uint32_t),0,&h);
+ hash(blocks,blockcount * sizeof(uint32_t),0,&h);
- hashes.push_back(h);
+ hashes.push_back(h);
- return;
- }
+ return;
+ }
- for(int i = k; i < blockcount; i++)
- {
- std::swap(blocks[k],blocks[i]);
+ for(int i = k; i < blockcount; i++)
+ {
+ std::swap(blocks[k],blocks[i]);
- PermutationKeygenRecurse(hash,blocks,blockcount,k+1,hashes);
+ PermutationKeygenRecurse(hash,blocks,blockcount,k+1,hashes);
- std::swap(blocks[k],blocks[i]);
- }
+ std::swap(blocks[k],blocks[i]);
+ }
}
template< typename hashtype >
bool PermutationKeyTest ( hashfunc<hashtype> hash, uint32_t * blocks, int blockcount, bool testColl, bool testDist, bool drawDiagram )
{
- printf("Keyset 'Permutation' - %d blocks - ",blockcount);
+ printf("Keyset 'Permutation' - %d blocks - ",blockcount);
- //----------
+ //----------
- std::vector<hashtype> hashes;
+ std::vector<hashtype> hashes;
- PermutationKeygenRecurse<hashtype>(hash,blocks,blockcount,0,hashes);
+ PermutationKeygenRecurse<hashtype>(hash,blocks,blockcount,0,hashes);
- printf("%d keys\n",(int)hashes.size());
+ printf("%d keys\n",(int)hashes.size());
- //----------
+ //----------
- bool result = true;
+ bool result = true;
- result &= TestHashList<hashtype>(hashes,testColl,testDist,drawDiagram);
-
- printf("\n");
+ result &= TestHashList<hashtype>(hashes,testColl,testDist,drawDiagram);
+
+ printf("\n");
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -135,28 +134,28 @@ bool PermutationKeyTest ( hashfunc<hashtype> hash, uint32_t * blocks, int blockc template < typename keytype, typename hashtype >
void SparseKeygenRecurse ( pfHash hash, int start, int bitsleft, bool inclusive, keytype & k, std::vector<hashtype> & hashes )
{
- const int nbytes = sizeof(keytype);
- const int nbits = nbytes * 8;
+ const int nbytes = sizeof(keytype);
+ const int nbits = nbytes * 8;
- hashtype h;
+ hashtype h;
- for(int i = start; i < nbits; i++)
- {
- flipbit(&k,nbytes,i);
+ for(int i = start; i < nbits; i++)
+ {
+ flipbit(&k,nbytes,i);
- if(inclusive || (bitsleft == 1))
- {
- hash(&k,sizeof(keytype),0,&h);
- hashes.push_back(h);
- }
+ if(inclusive || (bitsleft == 1))
+ {
+ hash(&k,sizeof(keytype),0,&h);
+ hashes.push_back(h);
+ }
- if(bitsleft > 1)
- {
- SparseKeygenRecurse(hash,i+1,bitsleft-1,inclusive,k,hashes);
- }
+ if(bitsleft > 1)
+ {
+ SparseKeygenRecurse(hash,i+1,bitsleft-1,inclusive,k,hashes);
+ }
- flipbit(&k,nbytes,i);
- }
+ flipbit(&k,nbytes,i);
+ }
}
//----------
@@ -164,35 +163,35 @@ void SparseKeygenRecurse ( pfHash hash, int start, int bitsleft, bool inclusive, template < int keybits, typename hashtype >
bool SparseKeyTest ( hashfunc<hashtype> hash, const int setbits, bool inclusive, bool testColl, bool testDist, bool drawDiagram )
{
- printf("Keyset 'Sparse' - %d-bit keys with %s %d bits set - ",keybits, inclusive ? "up to" : "exactly", setbits);
+ printf("Keyset 'Sparse' - %d-bit keys with %s %d bits set - ",keybits, inclusive ? "up to" : "exactly", setbits);
- typedef Blob<keybits> keytype;
+ typedef Blob<keybits> keytype;
- std::vector<hashtype> hashes;
+ std::vector<hashtype> hashes;
- keytype k;
- memset(&k,0,sizeof(k));
+ keytype k;
+ memset(&k,0,sizeof(k));
- if(inclusive)
- {
- hashtype h;
+ if(inclusive)
+ {
+ hashtype h;
- hash(&k,sizeof(keytype),0,&h);
+ hash(&k,sizeof(keytype),0,&h);
- hashes.push_back(h);
- }
+ hashes.push_back(h);
+ }
- SparseKeygenRecurse(hash,0,setbits,inclusive,k,hashes);
+ SparseKeygenRecurse(hash,0,setbits,inclusive,k,hashes);
- printf("%d keys\n",(int)hashes.size());
+ printf("%d keys\n",(int)hashes.size());
- bool result = true;
-
- result &= TestHashList<hashtype>(hashes,testColl,testDist,drawDiagram);
+ bool result = true;
+
+ result &= TestHashList<hashtype>(hashes,testColl,testDist,drawDiagram);
- printf("\n");
+ printf("\n");
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -202,40 +201,40 @@ bool SparseKeyTest ( hashfunc<hashtype> hash, const int setbits, bool inclusive, template < typename keytype, typename hashtype >
bool WindowedKeyTest ( hashfunc<hashtype> hash, const int windowbits, bool testCollision, bool testDistribution, bool drawDiagram )
{
- const int keybits = sizeof(keytype) * 8;
- const int keycount = 1 << windowbits;
+ const int keybits = sizeof(keytype) * 8;
+ const int keycount = 1 << windowbits;
- std::vector<hashtype> hashes;
- hashes.resize(keycount);
+ std::vector<hashtype> hashes;
+ hashes.resize(keycount);
- bool result = true;
+ bool result = true;
- int testcount = (keybits-windowbits);
+ int testcount = (keybits-windowbits);
- printf("Keyset 'Windowed' - %3d-bit key, %3d-bit window - %d tests, %d keys per test\n",keybits,windowbits,testcount,keycount);
+ printf("Keyset 'Windowed' - %3d-bit key, %3d-bit window - %d tests, %d keys per test\n",keybits,windowbits,testcount,keycount);
- for(int j = 0; j <= testcount; j++)
- {
- int minbit = j;
+ for(int j = 0; j <= testcount; j++)
+ {
+ int minbit = j;
- keytype key;
+ keytype key;
- for(int i = 0; i < keycount; i++)
- {
- key = i;
- key = key << minbit;
+ for(int i = 0; i < keycount; i++)
+ {
+ key = i;
+ key = key << minbit;
- hash(&key,sizeof(keytype),0,&hashes[i]);
- }
+ hash(&key,sizeof(keytype),0,&hashes[i]);
+ }
- printf("Window at %3d - ",j);
+ printf("Window at %3d - ",j);
- result &= TestHashList(hashes,testCollision,testDistribution,drawDiagram);
+ result &= TestHashList(hashes,testCollision,testDistribution,drawDiagram);
- //printf("\n");
- }
+ //printf("\n");
+ }
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -247,43 +246,43 @@ bool WindowedKeyTest ( hashfunc<hashtype> hash, const int windowbits, bool testC template < typename hashtype >
bool CyclicKeyTest ( pfHash hash, int cycleLen, int cycleReps, const int keycount, bool drawDiagram )
{
- printf("Keyset 'Cyclic' - %d cycles of %d bytes - %d keys\n",cycleReps,cycleLen,keycount);
+ printf("Keyset 'Cyclic' - %d cycles of %d bytes - %d keys\n",cycleReps,cycleLen,keycount);
- std::vector<hashtype> hashes;
- hashes.resize(keycount);
+ std::vector<hashtype> hashes;
+ hashes.resize(keycount);
- int keyLen = cycleLen * cycleReps;
+ int keyLen = cycleLen * cycleReps;
- uint8_t * cycle = new uint8_t[cycleLen + 16];
- uint8_t * key = new uint8_t[keyLen];
+ uint8_t * cycle = new uint8_t[cycleLen + 16];
+ uint8_t * key = new uint8_t[keyLen];
- //----------
+ //----------
- for(int i = 0; i < keycount; i++)
- {
- rand_p(cycle,cycleLen);
+ for(int i = 0; i < keycount; i++)
+ {
+ rand_p(cycle,cycleLen);
- *(uint32_t*)cycle = f3mix(i ^ 0x746a94f1);
+ *(uint32_t*)cycle = f3mix(i ^ 0x746a94f1);
- for(int j = 0; j < keyLen; j++)
- {
- key[j] = cycle[j % cycleLen];
- }
+ for(int j = 0; j < keyLen; j++)
+ {
+ key[j] = cycle[j % cycleLen];
+ }
- hash(key,keyLen,0,&hashes[i]);
- }
+ hash(key,keyLen,0,&hashes[i]);
+ }
- //----------
-
- bool result = true;
+ //----------
+
+ bool result = true;
- result &= TestHashList(hashes,true,true,drawDiagram);
- printf("\n");
+ result &= TestHashList(hashes,true,true,drawDiagram);
+ printf("\n");
- delete [] cycle;
- delete [] key;
+ delete [] cycle;
+ delete [] key;
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -294,52 +293,52 @@ bool CyclicKeyTest ( pfHash hash, int cycleLen, int cycleReps, const int keycoun template < typename hashtype >
bool TextKeyTest ( hashfunc<hashtype> hash, const char * prefix, const char * coreset, const int corelen, const char * suffix, bool drawDiagram )
{
- const int prefixlen = (int)strlen(prefix);
- const int suffixlen = (int)strlen(suffix);
- const int corecount = (int)strlen(coreset);
+ const int prefixlen = (int)strlen(prefix);
+ const int suffixlen = (int)strlen(suffix);
+ const int corecount = (int)strlen(coreset);
- const int keybytes = prefixlen + corelen + suffixlen;
- const int keycount = (int)pow(double(corecount),double(corelen));
+ const int keybytes = prefixlen + corelen + suffixlen;
+ const int keycount = (int)pow(double(corecount),double(corelen));
- printf("Keyset 'Text' - keys of form \"%s[",prefix);
- for(int i = 0; i < corelen; i++) printf("X");
- printf("]%s\" - %d keys\n",suffix,keycount);
+ printf("Keyset 'Text' - keys of form \"%s[",prefix);
+ for(int i = 0; i < corelen; i++) printf("X");
+ printf("]%s\" - %d keys\n",suffix,keycount);
- uint8_t * key = new uint8_t[keybytes+1];
+ uint8_t * key = new uint8_t[keybytes+1];
- key[keybytes] = 0;
+ key[keybytes] = 0;
- memcpy(key,prefix,prefixlen);
- memcpy(key+prefixlen+corelen,suffix,suffixlen);
+ memcpy(key,prefix,prefixlen);
+ memcpy(key+prefixlen+corelen,suffix,suffixlen);
- //----------
+ //----------
- std::vector<hashtype> hashes;
- hashes.resize(keycount);
+ std::vector<hashtype> hashes;
+ hashes.resize(keycount);
- for(int i = 0; i < keycount; i++)
- {
- int t = i;
+ for(int i = 0; i < keycount; i++)
+ {
+ int t = i;
- for(int j = 0; j < corelen; j++)
- {
- key[prefixlen+j] = coreset[t % corecount]; t /= corecount;
- }
+ for(int j = 0; j < corelen; j++)
+ {
+ key[prefixlen+j] = coreset[t % corecount]; t /= corecount;
+ }
- hash(key,keybytes,0,&hashes[i]);
- }
+ hash(key,keybytes,0,&hashes[i]);
+ }
- //----------
+ //----------
- bool result = true;
+ bool result = true;
- result &= TestHashList(hashes,true,true,drawDiagram);
+ result &= TestHashList(hashes,true,true,drawDiagram);
- printf("\n");
+ printf("\n");
- delete [] key;
+ delete [] key;
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -350,33 +349,33 @@ bool TextKeyTest ( hashfunc<hashtype> hash, const char * prefix, const char * co template < typename hashtype >
bool ZeroKeyTest ( pfHash hash, bool drawDiagram )
{
- int keycount = 64*1024;
+ int keycount = 64*1024;
- printf("Keyset 'Zeroes' - %d keys\n",keycount);
+ printf("Keyset 'Zeroes' - %d keys\n",keycount);
- unsigned char * nullblock = new unsigned char[keycount];
- memset(nullblock,0,keycount);
+ unsigned char * nullblock = new unsigned char[keycount];
+ memset(nullblock,0,keycount);
- //----------
+ //----------
- std::vector<hashtype> hashes;
+ std::vector<hashtype> hashes;
- hashes.resize(keycount);
+ hashes.resize(keycount);
- for(int i = 0; i < keycount; i++)
- {
- hash(nullblock,i,0,&hashes[i]);
- }
+ for(int i = 0; i < keycount; i++)
+ {
+ hash(nullblock,i,0,&hashes[i]);
+ }
- bool result = true;
+ bool result = true;
- result &= TestHashList(hashes,true,true,drawDiagram);
+ result &= TestHashList(hashes,true,true,drawDiagram);
- printf("\n");
+ printf("\n");
- delete [] nullblock;
+ delete [] nullblock;
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -385,29 +384,29 @@ bool ZeroKeyTest ( pfHash hash, bool drawDiagram ) template < typename hashtype >
bool SeedTest ( pfHash hash, int keycount, bool drawDiagram )
{
- printf("Keyset 'Seed' - %d keys\n",keycount);
+ printf("Keyset 'Seed' - %d keys\n",keycount);
- const char * text = "The quick brown fox jumps over the lazy dog";
- const int len = (int)strlen(text);
+ const char * text = "The quick brown fox jumps over the lazy dog";
+ const int len = (int)strlen(text);
- //----------
+ //----------
- std::vector<hashtype> hashes;
+ std::vector<hashtype> hashes;
- hashes.resize(keycount);
+ hashes.resize(keycount);
- for(int i = 0; i < keycount; i++)
- {
- hash(text,len,i,&hashes[i]);
- }
+ for(int i = 0; i < keycount; i++)
+ {
+ hash(text,len,i,&hashes[i]);
+ }
- bool result = true;
+ bool result = true;
- result &= TestHashList(hashes,true,true,drawDiagram);
+ result &= TestHashList(hashes,true,true,drawDiagram);
- printf("\n");
+ printf("\n");
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
diff --git a/MurmurHash1.cpp b/MurmurHash1.cpp index 6499a3d..ed23e6f 100644 --- a/MurmurHash1.cpp +++ b/MurmurHash1.cpp @@ -16,50 +16,50 @@ uint32_t MurmurHash1 ( const void * key, int len, uint32_t seed )
{
- const unsigned int m = 0xc6a4a793;
-
- const int r = 16;
-
- unsigned int h = seed ^ (len * m);
-
- //----------
-
- const unsigned char * data = (const unsigned char *)key;
-
- while(len >= 4)
- {
- unsigned int k = *(unsigned int *)data;
-
- h += k;
- h *= m;
- h ^= h >> 16;
-
- data += 4;
- len -= 4;
- }
-
- //----------
-
- switch(len)
- {
- case 3:
- h += data[2] << 16;
- case 2:
- h += data[1] << 8;
- case 1:
- h += data[0];
- h *= m;
- h ^= h >> r;
- };
+ const unsigned int m = 0xc6a4a793;
+
+ const int r = 16;
+
+ unsigned int h = seed ^ (len * m);
+
+ //----------
+
+ const unsigned char * data = (const unsigned char *)key;
+
+ while(len >= 4)
+ {
+ unsigned int k = *(unsigned int *)data;
+
+ h += k;
+ h *= m;
+ h ^= h >> 16;
+
+ data += 4;
+ len -= 4;
+ }
+
+ //----------
+
+ switch(len)
+ {
+ case 3:
+ h += data[2] << 16;
+ case 2:
+ h += data[1] << 8;
+ case 1:
+ h += data[0];
+ h *= m;
+ h ^= h >> r;
+ };
- //----------
+ //----------
- h *= m;
- h ^= h >> 10;
- h *= m;
- h ^= h >> 17;
+ h *= m;
+ h ^= h >> 10;
+ h *= m;
+ h ^= h >> 17;
- return h;
+ return h;
}
//-----------------------------------------------------------------------------
@@ -72,100 +72,100 @@ uint32_t MurmurHash1 ( const void * key, int len, uint32_t seed ) unsigned int MurmurHash1Aligned ( const void * key, int len, unsigned int seed )
{
- const unsigned int m = 0xc6a4a793;
- const int r = 16;
-
- const unsigned char * data = (const unsigned char *)key;
-
- unsigned int h = seed ^ (len * m);
-
- int align = (uint64_t)data & 3;
-
- if(align && (len >= 4))
- {
- // Pre-load the temp registers
-
- unsigned int t = 0, d = 0;
-
- switch(align)
- {
- case 1: t |= data[2] << 16;
- case 2: t |= data[1] << 8;
- case 3: t |= data[0];
- }
-
- t <<= (8 * align);
-
- data += 4-align;
- len -= 4-align;
-
- int sl = 8 * (4-align);
- int sr = 8 * align;
-
- // Mix
-
- while(len >= 4)
- {
- d = *(unsigned int *)data;
- t = (t >> sr) | (d << sl);
- h += t;
- h *= m;
- h ^= h >> r;
- t = d;
-
- data += 4;
- len -= 4;
- }
-
- // Handle leftover data in temp registers
-
- int pack = len < align ? len : align;
-
- d = 0;
-
- switch(pack)
- {
- case 3: d |= data[2] << 16;
- case 2: d |= data[1] << 8;
- case 1: d |= data[0];
- case 0: h += (t >> sr) | (d << sl);
- h *= m;
- h ^= h >> r;
- }
-
- data += pack;
- len -= pack;
- }
- else
- {
- while(len >= 4)
- {
- h += *(unsigned int *)data;
- h *= m;
- h ^= h >> r;
-
- data += 4;
- len -= 4;
- }
- }
-
- //----------
- // Handle tail bytes
-
- switch(len)
- {
- case 3: h += data[2] << 16;
- case 2: h += data[1] << 8;
- case 1: h += data[0];
- h *= m;
- h ^= h >> r;
- };
-
- h *= m;
- h ^= h >> 10;
- h *= m;
- h ^= h >> 17;
-
- return h;
+ const unsigned int m = 0xc6a4a793;
+ const int r = 16;
+
+ const unsigned char * data = (const unsigned char *)key;
+
+ unsigned int h = seed ^ (len * m);
+
+ int align = (uint64_t)data & 3;
+
+ if(align && (len >= 4))
+ {
+ // Pre-load the temp registers
+
+ unsigned int t = 0, d = 0;
+
+ switch(align)
+ {
+ case 1: t |= data[2] << 16;
+ case 2: t |= data[1] << 8;
+ case 3: t |= data[0];
+ }
+
+ t <<= (8 * align);
+
+ data += 4-align;
+ len -= 4-align;
+
+ int sl = 8 * (4-align);
+ int sr = 8 * align;
+
+ // Mix
+
+ while(len >= 4)
+ {
+ d = *(unsigned int *)data;
+ t = (t >> sr) | (d << sl);
+ h += t;
+ h *= m;
+ h ^= h >> r;
+ t = d;
+
+ data += 4;
+ len -= 4;
+ }
+
+ // Handle leftover data in temp registers
+
+ int pack = len < align ? len : align;
+
+ d = 0;
+
+ switch(pack)
+ {
+ case 3: d |= data[2] << 16;
+ case 2: d |= data[1] << 8;
+ case 1: d |= data[0];
+ case 0: h += (t >> sr) | (d << sl);
+ h *= m;
+ h ^= h >> r;
+ }
+
+ data += pack;
+ len -= pack;
+ }
+ else
+ {
+ while(len >= 4)
+ {
+ h += *(unsigned int *)data;
+ h *= m;
+ h ^= h >> r;
+
+ data += 4;
+ len -= 4;
+ }
+ }
+
+ //----------
+ // Handle tail bytes
+
+ switch(len)
+ {
+ case 3: h += data[2] << 16;
+ case 2: h += data[1] << 8;
+ case 1: h += data[0];
+ h *= m;
+ h ^= h >> r;
+ };
+
+ h *= m;
+ h ^= h >> 10;
+ h *= m;
+ h ^= h >> 17;
+
+ return h;
}
diff --git a/MurmurHash2.cpp b/MurmurHash2.cpp index e020628..cc94f79 100644 --- a/MurmurHash2.cpp +++ b/MurmurHash2.cpp @@ -16,53 +16,53 @@ uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed )
{
- // 'm' and 'r' are mixing constants generated offline.
- // They're not really 'magic', they just happen to work well.
+ // 'm' and 'r' are mixing constants generated offline.
+ // They're not really 'magic', they just happen to work well.
- const uint32_t m = 0x5bd1e995;
- const int r = 24;
+ const uint32_t m = 0x5bd1e995;
+ const int r = 24;
- // Initialize the hash to a 'random' value
+ // Initialize the hash to a 'random' value
- uint32_t h = seed ^ len;
+ uint32_t h = seed ^ len;
- // Mix 4 bytes at a time into the hash
+ // Mix 4 bytes at a time into the hash
- const unsigned char * data = (const unsigned char *)key;
+ const unsigned char * data = (const unsigned char *)key;
- while(len >= 4)
- {
- uint32_t k = *(uint32_t*)data;
+ while(len >= 4)
+ {
+ uint32_t k = *(uint32_t*)data;
- k *= m;
- k ^= k >> r;
- k *= m;
+ k *= m;
+ k ^= k >> r;
+ k *= m;
- h *= m;
- h ^= k;
+ h *= m;
+ h ^= k;
- data += 4;
- len -= 4;
- }
+ data += 4;
+ len -= 4;
+ }
- // Handle the last few bytes of the input array
+ // Handle the last few bytes of the input array
- switch(len)
- {
- case 3: h ^= data[2] << 16;
- case 2: h ^= data[1] << 8;
- case 1: h ^= data[0];
- h *= m;
- };
+ switch(len)
+ {
+ case 3: h ^= data[2] << 16;
+ case 2: h ^= data[1] << 8;
+ case 1: h ^= data[0];
+ h *= m;
+ };
- // Do a few final mixes of the hash to ensure the last few
- // bytes are well-incorporated.
+ // Do a few final mixes of the hash to ensure the last few
+ // bytes are well-incorporated.
- h ^= h >> 13;
- h *= m;
- h ^= h >> 15;
+ h ^= h >> 13;
+ h *= m;
+ h ^= h >> 15;
- return h;
+ return h;
}
//-----------------------------------------------------------------------------
@@ -75,45 +75,45 @@ uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed ) uint64_t MurmurHash64A ( const void * key, int len, uint64_t seed )
{
- const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995);
- const int r = 47;
-
- uint64_t h = seed ^ (len * m);
-
- const uint64_t * data = (const uint64_t *)key;
- const uint64_t * end = data + (len/8);
-
- while(data != end)
- {
- uint64_t k = *data++;
-
- k *= m;
- k ^= k >> r;
- k *= m;
-
- h ^= k;
- h *= m;
- }
-
- const unsigned char * data2 = (const unsigned char*)data;
-
- switch(len & 7)
- {
- case 7: h ^= uint64_t(data2[6]) << 48;
- case 6: h ^= uint64_t(data2[5]) << 40;
- case 5: h ^= uint64_t(data2[4]) << 32;
- case 4: h ^= uint64_t(data2[3]) << 24;
- case 3: h ^= uint64_t(data2[2]) << 16;
- case 2: h ^= uint64_t(data2[1]) << 8;
- case 1: h ^= uint64_t(data2[0]);
- h *= m;
- };
+ const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995);
+ const int r = 47;
+
+ uint64_t h = seed ^ (len * m);
+
+ const uint64_t * data = (const uint64_t *)key;
+ const uint64_t * end = data + (len/8);
+
+ while(data != end)
+ {
+ uint64_t k = *data++;
+
+ k *= m;
+ k ^= k >> r;
+ k *= m;
+
+ h ^= k;
+ h *= m;
+ }
+
+ const unsigned char * data2 = (const unsigned char*)data;
+
+ switch(len & 7)
+ {
+ case 7: h ^= uint64_t(data2[6]) << 48;
+ case 6: h ^= uint64_t(data2[5]) << 40;
+ case 5: h ^= uint64_t(data2[4]) << 32;
+ case 4: h ^= uint64_t(data2[3]) << 24;
+ case 3: h ^= uint64_t(data2[2]) << 16;
+ case 2: h ^= uint64_t(data2[1]) << 8;
+ case 1: h ^= uint64_t(data2[0]);
+ h *= m;
+ };
- h ^= h >> r;
- h *= m;
- h ^= h >> r;
+ h ^= h >> r;
+ h *= m;
+ h ^= h >> r;
- return h;
+ return h;
}
@@ -121,53 +121,53 @@ uint64_t MurmurHash64A ( const void * key, int len, uint64_t seed ) uint64_t MurmurHash64B ( const void * key, int len, uint64_t seed )
{
- const uint32_t m = 0x5bd1e995;
- const int r = 24;
-
- uint32_t h1 = uint32_t(seed) ^ len;
- uint32_t h2 = uint32_t(seed >> 32);
-
- const uint32_t * data = (const uint32_t *)key;
-
- while(len >= 8)
- {
- uint32_t k1 = *data++;
- k1 *= m; k1 ^= k1 >> r; k1 *= m;
- h1 *= m; h1 ^= k1;
- len -= 4;
-
- uint32_t k2 = *data++;
- k2 *= m; k2 ^= k2 >> r; k2 *= m;
- h2 *= m; h2 ^= k2;
- len -= 4;
- }
-
- if(len >= 4)
- {
- uint32_t k1 = *data++;
- k1 *= m; k1 ^= k1 >> r; k1 *= m;
- h1 *= m; h1 ^= k1;
- len -= 4;
- }
-
- switch(len)
- {
- case 3: h2 ^= ((unsigned char*)data)[2] << 16;
- case 2: h2 ^= ((unsigned char*)data)[1] << 8;
- case 1: h2 ^= ((unsigned char*)data)[0];
- h2 *= m;
- };
-
- h1 ^= h2 >> 18; h1 *= m;
- h2 ^= h1 >> 22; h2 *= m;
- h1 ^= h2 >> 17; h1 *= m;
- h2 ^= h1 >> 19; h2 *= m;
-
- uint64_t h = h1;
-
- h = (h << 32) | h2;
-
- return h;
+ const uint32_t m = 0x5bd1e995;
+ const int r = 24;
+
+ uint32_t h1 = uint32_t(seed) ^ len;
+ uint32_t h2 = uint32_t(seed >> 32);
+
+ const uint32_t * data = (const uint32_t *)key;
+
+ while(len >= 8)
+ {
+ uint32_t k1 = *data++;
+ k1 *= m; k1 ^= k1 >> r; k1 *= m;
+ h1 *= m; h1 ^= k1;
+ len -= 4;
+
+ uint32_t k2 = *data++;
+ k2 *= m; k2 ^= k2 >> r; k2 *= m;
+ h2 *= m; h2 ^= k2;
+ len -= 4;
+ }
+
+ if(len >= 4)
+ {
+ uint32_t k1 = *data++;
+ k1 *= m; k1 ^= k1 >> r; k1 *= m;
+ h1 *= m; h1 ^= k1;
+ len -= 4;
+ }
+
+ switch(len)
+ {
+ case 3: h2 ^= ((unsigned char*)data)[2] << 16;
+ case 2: h2 ^= ((unsigned char*)data)[1] << 8;
+ case 1: h2 ^= ((unsigned char*)data)[0];
+ h2 *= m;
+ };
+
+ h1 ^= h2 >> 18; h1 *= m;
+ h2 ^= h1 >> 22; h2 *= m;
+ h1 ^= h2 >> 17; h1 *= m;
+ h2 ^= h1 >> 19; h2 *= m;
+
+ uint64_t h = h1;
+
+ h = (h << 32) | h2;
+
+ return h;
}
//-----------------------------------------------------------------------------
@@ -185,41 +185,41 @@ uint64_t MurmurHash64B ( const void * key, int len, uint64_t seed ) uint32_t MurmurHash2A ( const void * key, int len, uint32_t seed )
{
- const uint32_t m = 0x5bd1e995;
- const int r = 24;
- uint32_t l = len;
+ const uint32_t m = 0x5bd1e995;
+ const int r = 24;
+ uint32_t l = len;
- const unsigned char * data = (const unsigned char *)key;
+ const unsigned char * data = (const unsigned char *)key;
- uint32_t h = seed;
+ uint32_t h = seed;
- while(len >= 4)
- {
- uint32_t k = *(uint32_t*)data;
+ while(len >= 4)
+ {
+ uint32_t k = *(uint32_t*)data;
- mmix(h,k);
+ mmix(h,k);
- data += 4;
- len -= 4;
- }
+ data += 4;
+ len -= 4;
+ }
- uint32_t t = 0;
+ uint32_t t = 0;
- switch(len)
- {
- case 3: t ^= data[2] << 16;
- case 2: t ^= data[1] << 8;
- case 1: t ^= data[0];
- };
+ switch(len)
+ {
+ case 3: t ^= data[2] << 16;
+ case 2: t ^= data[1] << 8;
+ case 1: t ^= data[0];
+ };
- mmix(h,t);
- mmix(h,l);
+ mmix(h,t);
+ mmix(h,l);
- h ^= h >> 13;
- h *= m;
- h ^= h >> 15;
+ h ^= h >> 13;
+ h *= m;
+ h ^= h >> 15;
- return h;
+ return h;
}
//-----------------------------------------------------------------------------
@@ -242,72 +242,72 @@ class CMurmurHash2A {
public:
- void Begin ( uint32_t seed = 0 )
- {
- m_hash = seed;
- m_tail = 0;
- m_count = 0;
- m_size = 0;
- }
+ void Begin ( uint32_t seed = 0 )
+ {
+ m_hash = seed;
+ m_tail = 0;
+ m_count = 0;
+ m_size = 0;
+ }
- void Add ( const unsigned char * data, int len )
- {
- m_size += len;
+ void Add ( const unsigned char * data, int len )
+ {
+ m_size += len;
- MixTail(data,len);
+ MixTail(data,len);
- while(len >= 4)
- {
- uint32_t k = *(uint32_t*)data;
+ while(len >= 4)
+ {
+ uint32_t k = *(uint32_t*)data;
- mmix(m_hash,k);
+ mmix(m_hash,k);
- data += 4;
- len -= 4;
- }
+ data += 4;
+ len -= 4;
+ }
- MixTail(data,len);
- }
+ MixTail(data,len);
+ }
- uint32_t End ( void )
- {
- mmix(m_hash,m_tail);
- mmix(m_hash,m_size);
+ uint32_t End ( void )
+ {
+ mmix(m_hash,m_tail);
+ mmix(m_hash,m_size);
- m_hash ^= m_hash >> 13;
- m_hash *= m;
- m_hash ^= m_hash >> 15;
+ m_hash ^= m_hash >> 13;
+ m_hash *= m;
+ m_hash ^= m_hash >> 15;
- return m_hash;
- }
+ return m_hash;
+ }
private:
- static const uint32_t m = 0x5bd1e995;
- static const int r = 24;
-
- void MixTail ( const unsigned char * & data, int & len )
- {
- while( len && ((len<4) || m_count) )
- {
- m_tail |= (*data++) << (m_count * 8);
-
- m_count++;
- len--;
-
- if(m_count == 4)
- {
- mmix(m_hash,m_tail);
- m_tail = 0;
- m_count = 0;
- }
- }
- }
-
- uint32_t m_hash;
- uint32_t m_tail;
- uint32_t m_count;
- uint32_t m_size;
+ static const uint32_t m = 0x5bd1e995;
+ static const int r = 24;
+
+ void MixTail ( const unsigned char * & data, int & len )
+ {
+ while( len && ((len<4) || m_count) )
+ {
+ m_tail |= (*data++) << (m_count * 8);
+
+ m_count++;
+ len--;
+
+ if(m_count == 4)
+ {
+ mmix(m_hash,m_tail);
+ m_tail = 0;
+ m_count = 0;
+ }
+ }
+ }
+
+ uint32_t m_hash;
+ uint32_t m_tail;
+ uint32_t m_count;
+ uint32_t m_size;
};
//-----------------------------------------------------------------------------
@@ -318,46 +318,46 @@ private: uint32_t MurmurHashNeutral2 ( const void * key, int len, uint32_t seed )
{
- const uint32_t m = 0x5bd1e995;
- const int r = 24;
-
- uint32_t h = seed ^ len;
-
- const unsigned char * data = (const unsigned char *)key;
-
- while(len >= 4)
- {
- uint32_t k;
-
- k = data[0];
- k |= data[1] << 8;
- k |= data[2] << 16;
- k |= data[3] << 24;
-
- k *= m;
- k ^= k >> r;
- k *= m;
-
- h *= m;
- h ^= k;
-
- data += 4;
- len -= 4;
- }
-
- switch(len)
- {
- case 3: h ^= data[2] << 16;
- case 2: h ^= data[1] << 8;
- case 1: h ^= data[0];
- h *= m;
- };
-
- h ^= h >> 13;
- h *= m;
- h ^= h >> 15;
-
- return h;
+ const uint32_t m = 0x5bd1e995;
+ const int r = 24;
+
+ uint32_t h = seed ^ len;
+
+ const unsigned char * data = (const unsigned char *)key;
+
+ while(len >= 4)
+ {
+ uint32_t k;
+
+ k = data[0];
+ k |= data[1] << 8;
+ k |= data[2] << 16;
+ k |= data[3] << 24;
+
+ k *= m;
+ k ^= k >> r;
+ k *= m;
+
+ h *= m;
+ h ^= k;
+
+ data += 4;
+ len -= 4;
+ }
+
+ switch(len)
+ {
+ case 3: h ^= data[2] << 16;
+ case 2: h ^= data[1] << 8;
+ case 1: h ^= data[0];
+ h *= m;
+ };
+
+ h ^= h >> 13;
+ h *= m;
+ h ^= h >> 15;
+
+ return h;
}
//-----------------------------------------------------------------------------
@@ -372,130 +372,130 @@ uint32_t MurmurHashNeutral2 ( const void * key, int len, uint32_t seed ) uint32_t MurmurHashAligned2 ( const void * key, int len, uint32_t seed )
{
- const uint32_t m = 0x5bd1e995;
- const int r = 24;
+ const uint32_t m = 0x5bd1e995;
+ const int r = 24;
- const unsigned char * data = (const unsigned char *)key;
+ const unsigned char * data = (const unsigned char *)key;
- uint32_t h = seed ^ len;
+ uint32_t h = seed ^ len;
- int align = (uint64_t)data & 3;
+ int align = (uint64_t)data & 3;
- if(align && (len >= 4))
- {
- // Pre-load the temp registers
+ if(align && (len >= 4))
+ {
+ // Pre-load the temp registers
- uint32_t t = 0, d = 0;
+ uint32_t t = 0, d = 0;
- switch(align)
- {
- case 1: t |= data[2] << 16;
- case 2: t |= data[1] << 8;
- case 3: t |= data[0];
- }
+ switch(align)
+ {
+ case 1: t |= data[2] << 16;
+ case 2: t |= data[1] << 8;
+ case 3: t |= data[0];
+ }
- t <<= (8 * align);
-
- data += 4-align;
- len -= 4-align;
-
- int sl = 8 * (4-align);
- int sr = 8 * align;
-
- // Mix
-
- while(len >= 4)
- {
- d = *(uint32_t *)data;
- t = (t >> sr) | (d << sl);
-
- uint32_t k = t;
-
- MIX(h,k,m);
-
- t = d;
-
- data += 4;
- len -= 4;
- }
-
- // Handle leftover data in temp registers
-
- d = 0;
-
- if(len >= align)
- {
- switch(align)
- {
- case 3: d |= data[2] << 16;
- case 2: d |= data[1] << 8;
- case 1: d |= data[0];
- }
-
- uint32_t k = (t >> sr) | (d << sl);
- MIX(h,k,m);
-
- data += align;
- len -= align;
-
- //----------
- // Handle tail bytes
-
- switch(len)
- {
- case 3: h ^= data[2] << 16;
- case 2: h ^= data[1] << 8;
- case 1: h ^= data[0];
- h *= m;
- };
- }
- else
- {
- switch(len)
- {
- case 3: d |= data[2] << 16;
- case 2: d |= data[1] << 8;
- case 1: d |= data[0];
- case 0: h ^= (t >> sr) | (d << sl);
- h *= m;
- }
- }
-
- h ^= h >> 13;
- h *= m;
- h ^= h >> 15;
-
- return h;
- }
- else
- {
- while(len >= 4)
- {
- uint32_t k = *(uint32_t *)data;
-
- MIX(h,k,m);
+ t <<= (8 * align);
+
+ data += 4-align;
+ len -= 4-align;
+
+ int sl = 8 * (4-align);
+ int sr = 8 * align;
+
+ // Mix
+
+ while(len >= 4)
+ {
+ d = *(uint32_t *)data;
+ t = (t >> sr) | (d << sl);
+
+ uint32_t k = t;
+
+ MIX(h,k,m);
+
+ t = d;
+
+ data += 4;
+ len -= 4;
+ }
+
+ // Handle leftover data in temp registers
+
+ d = 0;
+
+ if(len >= align)
+ {
+ switch(align)
+ {
+ case 3: d |= data[2] << 16;
+ case 2: d |= data[1] << 8;
+ case 1: d |= data[0];
+ }
+
+ uint32_t k = (t >> sr) | (d << sl);
+ MIX(h,k,m);
+
+ data += align;
+ len -= align;
+
+ //----------
+ // Handle tail bytes
+
+ switch(len)
+ {
+ case 3: h ^= data[2] << 16;
+ case 2: h ^= data[1] << 8;
+ case 1: h ^= data[0];
+ h *= m;
+ };
+ }
+ else
+ {
+ switch(len)
+ {
+ case 3: d |= data[2] << 16;
+ case 2: d |= data[1] << 8;
+ case 1: d |= data[0];
+ case 0: h ^= (t >> sr) | (d << sl);
+ h *= m;
+ }
+ }
+
+ h ^= h >> 13;
+ h *= m;
+ h ^= h >> 15;
+
+ return h;
+ }
+ else
+ {
+ while(len >= 4)
+ {
+ uint32_t k = *(uint32_t *)data;
+
+ MIX(h,k,m);
- data += 4;
- len -= 4;
- }
-
- //----------
- // Handle tail bytes
-
- switch(len)
- {
- case 3: h ^= data[2] << 16;
- case 2: h ^= data[1] << 8;
- case 1: h ^= data[0];
- h *= m;
- };
-
- h ^= h >> 13;
- h *= m;
- h ^= h >> 15;
-
- return h;
- }
+ data += 4;
+ len -= 4;
+ }
+
+ //----------
+ // Handle tail bytes
+
+ switch(len)
+ {
+ case 3: h ^= data[2] << 16;
+ case 2: h ^= data[1] << 8;
+ case 1: h ^= data[0];
+ h *= m;
+ };
+
+ h ^= h >> 13;
+ h *= m;
+ h ^= h >> 15;
+
+ return h;
+ }
}
//-----------------------------------------------------------------------------
diff --git a/MurmurHash3.cpp b/MurmurHash3.cpp index fa2dafc..7a6e435 100644 --- a/MurmurHash3.cpp +++ b/MurmurHash3.cpp @@ -366,66 +366,3 @@ void MurmurHash3_x64_128 ( const void * key, const int len, }
//-----------------------------------------------------------------------------
-// Quick copy-pasted test code for GCC build
-
-// This should print -
-
-// "The quick brown fox jumps over the lazy dog" => { 0x38585ecf, 0x5f6d752a, 0x0157c98a, 0x8c686b9b, }
-// "The quick brown fox jumps over the lazy cog" => { 0x6d3fd6f0, 0xc86a98a0, 0x4d6fac1c, 0x8f3e52b4, }
-
-#ifndef _MSC_VER
-
-/*
-#include <assert.h>
-#include <stdio.h>
-#include <string.h>
-
-typedef void (*pfHash) ( const void * blob, const int len, const uint32_t seed, void * out );
-
-void printhex32 ( void * blob, int len )
-{
- assert((len & 3) == 0);
-
- uint32_t * d = (uint32_t*)blob;
-
- printf("{ ");
-
- for(int i = 0; i < len/4; i++)
- {
- printf("0x%08x, ",d[i]);
- }
-
- printf("}");
-}
-
-void QuickBrownFox ( pfHash hash, const int hashbits )
-{
- const int hashbytes = hashbits / 8;
-
- const char * text1 = "The quick brown fox jumps over the lazy dog";
- const char * text2 = "The quick brown fox jumps over the lazy cog";
-
- uint8_t h1[128];
- uint8_t h2[128];
-
- hash(text1,(int)strlen(text1),0,h1);
- hash(text2,(int)strlen(text2),0,h2);
-
- printf("\"%s\" => ",text1);
- printhex32(h1,hashbytes);
- printf("\n");
-
- printf("\"%s\" => ",text2);
- printhex32(h2,hashbytes);
- printf("\n");
-
- printf("\n");
-}
-
-int main ( int argc, char** argv )
-{
- QuickBrownFox(&MurmurHash3_x64_128,128);
-}
-*/
-
-#endif
diff --git a/Platform.cpp b/Platform.cpp index 5f38872..3561379 100644 --- a/Platform.cpp +++ b/Platform.cpp @@ -15,7 +15,7 @@ void testRDTSC ( void ) void SetAffinity ( int cpu )
{
- SetProcessAffinityMask(GetCurrentProcess(),cpu);
+ SetProcessAffinityMask(GetCurrentProcess(),cpu);
}
#else
@@ -43,22 +43,22 @@ void SetAffinity ( int cpu ); inline uint32_t rotl32 ( uint32_t x, int8_t r )
{
- return (x << r) | (x >> (32 - r));
+ return (x << r) | (x >> (32 - r));
}
inline uint64_t rotl64 ( uint64_t x, int8_t r )
{
- return (x << r) | (x >> (64 - r));
+ return (x << r) | (x >> (64 - r));
}
inline uint32_t rotr32 ( uint32_t x, int8_t r )
{
- return (x >> r) | (x << (32 - r));
+ return (x >> r) | (x << (32 - r));
}
inline uint64_t rotr64 ( uint64_t x, int8_t r )
{
- return (x >> r) | (x << (64 - r));
+ return (x >> r) | (x << (64 - r));
}
#define ROTL32(x,y) rotl32(x,y)
@@ -8,84 +8,84 @@ struct Rand
{
- uint32_t x;
- uint32_t y;
- uint32_t z;
- uint32_t w;
-
- Rand()
- {
- reseed(uint32_t(0));
- }
-
- Rand( uint32_t seed )
- {
- reseed(seed);
- }
-
- void reseed ( uint32_t seed )
- {
- x = 0x498b3bc5 ^ seed;
- y = 0;
- z = 0;
- w = 0;
-
- for(int i = 0; i < 10; i++) mix();
- }
-
- void reseed ( uint64_t seed )
- {
- x = 0x498b3bc5 ^ (uint32_t)(seed >> 0);
- y = 0x5a05089a ^ (uint32_t)(seed >> 32);
- z = 0;
- w = 0;
-
- for(int i = 0; i < 10; i++) mix();
- }
-
- //-----------------------------------------------------------------------------
-
- void mix ( void )
- {
- uint32_t t = x ^ (x << 11);
- x = y; y = z; z = w;
- w = w ^ (w >> 19) ^ t ^ (t >> 8);
- }
-
- uint32_t rand_u32 ( void )
- {
- mix();
-
- return x;
- }
-
- uint64_t rand_u64 ( void )
- {
- mix();
-
- uint64_t a = x;
- uint64_t b = y;
-
- return (a << 32) | b;
- }
-
- void rand_p ( void * blob, int bytes )
- {
- uint32_t * blocks = (uint32_t*)blob;
-
- while(bytes >= 4)
- {
- *blocks++ = rand_u32();
- bytes -= 4;
- }
-
- uint8_t * tail = (uint8_t*)blocks;
-
- for(int i = 0; i < bytes; i++)
- {
- tail[i] = (uint8_t)rand_u32();
- }
- }
+ uint32_t x;
+ uint32_t y;
+ uint32_t z;
+ uint32_t w;
+
+ Rand()
+ {
+ reseed(uint32_t(0));
+ }
+
+ Rand( uint32_t seed )
+ {
+ reseed(seed);
+ }
+
+ void reseed ( uint32_t seed )
+ {
+ x = 0x498b3bc5 ^ seed;
+ y = 0;
+ z = 0;
+ w = 0;
+
+ for(int i = 0; i < 10; i++) mix();
+ }
+
+ void reseed ( uint64_t seed )
+ {
+ x = 0x498b3bc5 ^ (uint32_t)(seed >> 0);
+ y = 0x5a05089a ^ (uint32_t)(seed >> 32);
+ z = 0;
+ w = 0;
+
+ for(int i = 0; i < 10; i++) mix();
+ }
+
+ //-----------------------------------------------------------------------------
+
+ void mix ( void )
+ {
+ uint32_t t = x ^ (x << 11);
+ x = y; y = z; z = w;
+ w = w ^ (w >> 19) ^ t ^ (t >> 8);
+ }
+
+ uint32_t rand_u32 ( void )
+ {
+ mix();
+
+ return x;
+ }
+
+ uint64_t rand_u64 ( void )
+ {
+ mix();
+
+ uint64_t a = x;
+ uint64_t b = y;
+
+ return (a << 32) | b;
+ }
+
+ void rand_p ( void * blob, int bytes )
+ {
+ uint32_t * blocks = (uint32_t*)blob;
+
+ while(bytes >= 4)
+ {
+ *blocks++ = rand_u32();
+ bytes -= 4;
+ }
+
+ uint8_t * tail = (uint8_t*)blocks;
+
+ for(int i = 0; i < bytes; i++)
+ {
+ tail[i] = (uint8_t)rand_u32();
+ }
+ }
};
//-----------------------------------------------------------------------------
@@ -97,20 +97,20 @@ inline uint64_t rand_u64 ( void ) { return g_rand1.rand_u64(); } inline void rand_p ( void * blob, int bytes )
{
- uint32_t * blocks = (uint32_t*)blob;
+ uint32_t * blocks = (uint32_t*)blob;
- while(bytes >= 4)
- {
- *blocks++ = rand_u32();
- bytes -= 4;
- }
+ while(bytes >= 4)
+ {
+ *blocks++ = rand_u32();
+ bytes -= 4;
+ }
- uint8_t * tail = (uint8_t*)blocks;
+ uint8_t * tail = (uint8_t*)blocks;
- for(int i = 0; i < bytes; i++)
- {
- tail[i] = (uint8_t)rand_u32();
- }
+ for(int i = 0; i < bytes; i++)
+ {
+ tail[i] = (uint8_t)rand_u32();
+ }
}
//-----------------------------------------------------------------------------
diff --git a/SpeedTest.cpp b/SpeedTest.cpp index c7c742b..a4ed8a7 100644 --- a/SpeedTest.cpp +++ b/SpeedTest.cpp @@ -9,98 +9,98 @@ void BulkSpeedTest ( pfHash hash )
{
- const int trials = 9999;
- const int blocksize = 256 * 1024;
+ const int trials = 9999;
+ const int blocksize = 256 * 1024;
- printf("Bulk speed test - %d-byte keys\n",blocksize);
+ printf("Bulk speed test - %d-byte keys\n",blocksize);
- char * block = new char[blocksize + 16];
+ char * block = new char[blocksize + 16];
- rand_p(block,blocksize+16);
+ rand_p(block,blocksize+16);
- uint32_t temp[16];
+ uint32_t temp[16];
- for(int align = 0; align < 8; align++)
- {
- double bestbpc = 0;
+ for(int align = 0; align < 8; align++)
+ {
+ double bestbpc = 0;
- for(int itrial = 0; itrial < trials; itrial++)
- {
- int64_t begin,end;
+ for(int itrial = 0; itrial < trials; itrial++)
+ {
+ int64_t begin,end;
- begin = rdtsc();
+ begin = rdtsc();
- hash(block + align,blocksize,itrial,temp);
+ hash(block + align,blocksize,itrial,temp);
- end = rdtsc();
+ end = rdtsc();
- blackhole(temp[0]);
+ blackhole(temp[0]);
- double cycles = double(end-begin);
- double bpc = double(blocksize) / cycles;
- if(bpc > bestbpc) bestbpc = bpc;
- }
+ double cycles = double(end-begin);
+ double bpc = double(blocksize) / cycles;
+ if(bpc > bestbpc) bestbpc = bpc;
+ }
- double bestbps = (bestbpc * 3000000000.0 / 1048576.0);
- printf("Alignment %2d - %6.3f bytes/cycle - %7.2f MiB/sec @ 3 ghz\n",align,bestbpc,bestbps);
- }
+ double bestbps = (bestbpc * 3000000000.0 / 1048576.0);
+ printf("Alignment %2d - %6.3f bytes/cycle - %7.2f MiB/sec @ 3 ghz\n",align,bestbpc,bestbps);
+ }
- delete [] block;
+ delete [] block;
}
//-----------------------------------------------------------------------------
void TinySpeedTest ( pfHash hash, int hashsize, int keysize, bool verbose, double & outCycles )
{
- const int trials = 100000;
+ const int trials = 100000;
- if(verbose) printf("Small key speed test - %4d-byte keys - ",keysize);
+ if(verbose) printf("Small key speed test - %4d-byte keys - ",keysize);
- uint8_t * h = new uint8_t[hashsize];
- uint8_t * k = new uint8_t[keysize];
+ uint8_t * h = new uint8_t[hashsize];
+ uint8_t * k = new uint8_t[keysize];
- double bestcycles = 1e9;
+ double bestcycles = 1e9;
- for(int itrial = 0; itrial < trials; itrial++)
- {
- int64_t begin,end;
+ for(int itrial = 0; itrial < trials; itrial++)
+ {
+ int64_t begin,end;
- rand_p(k,keysize);
+ rand_p(k,keysize);
- begin = rdtsc();
-
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ begin = rdtsc();
+
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
+ hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h); hash(k,keysize,itrial,h);
- end = rdtsc();
+ end = rdtsc();
- //blackhole(*(uint32_t*)(&h));
+ //blackhole(*(uint32_t*)(&h));
- double cycles = double(end-begin) / 64;
- if(cycles < bestcycles) bestcycles = cycles;
- }
+ double cycles = double(end-begin) / 64;
+ if(cycles < bestcycles) bestcycles = cycles;
+ }
- double bestbpc = double(keysize) / bestcycles;
- if(verbose) printf("%8.2f cycles/hash, %8.4f bytes/cycle\n",bestcycles,bestbpc);
+ double bestbpc = double(keysize) / bestcycles;
+ if(verbose) printf("%8.2f cycles/hash, %8.4f bytes/cycle\n",bestcycles,bestbpc);
- outCycles = bestcycles;
+ outCycles = bestcycles;
}
//-----------------------------------------------------------------------------
@@ -6,28 +6,28 @@ double chooseK ( int n, int k ) {
if(k > (n - k)) k = n - k;
- double c = 1;
+ double c = 1;
- for(int i = 0; i < k; i++)
- {
- double t = double(n-i) / double(i+1);
+ for(int i = 0; i < k; i++)
+ {
+ double t = double(n-i) / double(i+1);
- c *= t;
- }
+ c *= t;
+ }
return c;
}
double chooseUpToK ( int n, int k )
{
- double c = 0;
+ double c = 0;
- for(int i = 1; i <= k; i++)
- {
- c += chooseK(n,i);
- }
+ for(int i = 1; i <= k; i++)
+ {
+ c += chooseK(n,i);
+ }
- return c;
+ return c;
}
//-----------------------------------------------------------------------------
@@ -44,29 +44,29 @@ double chooseUpToK ( int n, int k ) double calcScore ( const int * bins, const int bincount, const int keycount )
{
- double n = bincount;
- double k = keycount;
+ double n = bincount;
+ double k = keycount;
- // compute rms value
+ // compute rms value
- double r = 0;
+ double r = 0;
- for(int i = 0; i < bincount; i++)
- {
- double b = bins[i];
+ for(int i = 0; i < bincount; i++)
+ {
+ double b = bins[i];
- r += b*b;
- }
+ r += b*b;
+ }
- r = sqrt(r / n);
+ r = sqrt(r / n);
- // compute fill factor
+ // compute fill factor
- double f = (k*k - 1) / (n*r*r - k);
+ double f = (k*k - 1) / (n*r*r - k);
- // rescale to (0,1) with 0 = good, 1 = bad
+ // rescale to (0,1) with 0 = good, 1 = bad
- return 1 - (f / n);
+ return 1 - (f / n);
}
@@ -74,26 +74,26 @@ double calcScore ( const int * bins, const int bincount, const int keycount ) void plot ( double n )
{
- double n2 = n * 1;
+ double n2 = n * 1;
- if(n2 < 0) n2 = 0;
+ if(n2 < 0) n2 = 0;
- n2 *= 100;
+ n2 *= 100;
- if(n2 > 64) n2 = 64;
+ if(n2 > 64) n2 = 64;
- int n3 = (int)n2;
+ int n3 = (int)n2;
- if(n3 == 0)
- printf(".");
- else
- {
- char x = '0' + char(n3);
+ if(n3 == 0)
+ printf(".");
+ else
+ {
+ char x = '0' + char(n3);
- if(x > '9') x = 'X';
+ if(x > '9') x = 'X';
- printf("%c",x);
- }
+ printf("%c",x);
+ }
}
//-----------------------------------------------------------------------------
@@ -15,7 +15,7 @@ void plot ( double n ); inline double ExpectedCollisions ( double balls, double bins )
{
- return balls - bins + bins * pow(1 - 1/bins,balls);
+ return balls - bins + bins * pow(1 - 1/bins,balls);
}
double chooseK ( int b, int k );
@@ -25,13 +25,13 @@ double chooseUpToK ( int n, int k ); inline uint32_t f3mix ( uint32_t k )
{
- k ^= k >> 16;
- k *= 0x85ebca6b;
- k ^= k >> 13;
- k *= 0xc2b2ae35;
- k ^= k >> 16;
+ k ^= k >> 16;
+ k *= 0x85ebca6b;
+ k ^= k >> 13;
+ k *= 0xc2b2ae35;
+ k ^= k >> 16;
- return k;
+ return k;
}
//-----------------------------------------------------------------------------
@@ -39,17 +39,17 @@ inline uint32_t f3mix ( uint32_t k ) template< typename hashtype >
int CountCollisions ( std::vector<hashtype> const & hashes )
{
- int collcount = 0;
+ int collcount = 0;
- std::vector<hashtype> temp = hashes;
- std::sort(temp.begin(),temp.end());
+ std::vector<hashtype> temp = hashes;
+ std::sort(temp.begin(),temp.end());
- for(size_t i = 1; i < hashes.size(); i++)
- {
- if(temp[i] == temp[i-1]) collcount++;
- }
+ for(size_t i = 1; i < hashes.size(); i++)
+ {
+ if(temp[i] == temp[i-1]) collcount++;
+ }
- return collcount;
+ return collcount;
}
//-----------------------------------------------------------------------------
@@ -57,35 +57,35 @@ int CountCollisions ( std::vector<hashtype> const & hashes ) template < class keytype, typename hashtype >
int PrintCollisions ( hashfunc<hashtype> hash, std::vector<keytype> & keys )
{
- int collcount = 0;
+ int collcount = 0;
- typedef std::map<hashtype,keytype> htab;
- htab tab;
+ typedef std::map<hashtype,keytype> htab;
+ htab tab;
- for(size_t i = 1; i < keys.size(); i++)
- {
- keytype & k1 = keys[i];
+ for(size_t i = 1; i < keys.size(); i++)
+ {
+ keytype & k1 = keys[i];
- hashtype h = hash(&k1,sizeof(keytype),0);
+ hashtype h = hash(&k1,sizeof(keytype),0);
- typename htab::iterator it = tab.find(h);
+ typename htab::iterator it = tab.find(h);
- if(it != tab.end())
- {
- keytype & k2 = (*it).second;
+ if(it != tab.end())
+ {
+ keytype & k2 = (*it).second;
- printf("A: ");
- printbits(&k1,sizeof(keytype));
- printf("B: ");
- printbits(&k2,sizeof(keytype));
- }
- else
- {
+ printf("A: ");
+ printbits(&k1,sizeof(keytype));
+ printf("B: ");
+ printbits(&k2,sizeof(keytype));
+ }
+ else
+ {
tab.insert( std::make_pair(h,k1) );
- }
- }
+ }
+ }
- return collcount;
+ return collcount;
}
//----------------------------------------------------------------------------
@@ -93,45 +93,45 @@ int PrintCollisions ( hashfunc<hashtype> hash, std::vector<keytype> & keys ) template < typename hashtype >
bool TestHashList ( std::vector<hashtype> & hashes, bool testColl, bool testDist, bool drawDiagram )
{
- bool result = true;
+ bool result = true;
- if(testColl)
- {
- size_t count = hashes.size();
+ if(testColl)
+ {
+ size_t count = hashes.size();
- double expected = (double(count) * double(count-1)) / pow(2.0,double(sizeof(hashtype) * 8 + 1));
+ double expected = (double(count) * double(count-1)) / pow(2.0,double(sizeof(hashtype) * 8 + 1));
- printf("Testing collisions - Expected %8.2f, ",expected);
+ printf("Testing collisions - Expected %8.2f, ",expected);
- double collcount = 0;
+ double collcount = 0;
- collcount = CountCollisions(hashes);
+ collcount = CountCollisions(hashes);
- printf("actual %8.2f (%5.2fx)",collcount, collcount / expected);
+ printf("actual %8.2f (%5.2fx)",collcount, collcount / expected);
- // 2x expected collisions = fail
+ // 2x expected collisions = fail
- // #TODO - collision failure cutoff needs to be expressed as a standard deviation instead
- // of a scale factor, otherwise we fail erroneously if there are a small expected number
- // of collisions
+ // #TODO - collision failure cutoff needs to be expressed as a standard deviation instead
+ // of a scale factor, otherwise we fail erroneously if there are a small expected number
+ // of collisions
- if(double(collcount) / double(expected) > 2.0)
- {
- printf(" !!!!! ");
- result = false;
- }
+ if(double(collcount) / double(expected) > 2.0)
+ {
+ printf(" !!!!! ");
+ result = false;
+ }
- printf("\n");
- }
+ printf("\n");
+ }
- //----------
+ //----------
- if(testDist)
- {
- TestDistribution(hashes,drawDiagram);
- }
+ if(testDist)
+ {
+ TestDistribution(hashes,drawDiagram);
+ }
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -139,30 +139,30 @@ bool TestHashList ( std::vector<hashtype> & hashes, bool testColl, bool testDist template < class keytype, typename hashtype >
bool TestKeyList ( hashfunc<hashtype> hash, std::vector<keytype> & keys, bool testColl, bool testDist, bool drawDiagram )
{
- int keycount = (int)keys.size();
+ int keycount = (int)keys.size();
- std::vector<hashtype> hashes;
+ std::vector<hashtype> hashes;
- hashes.resize(keycount);
+ hashes.resize(keycount);
- printf("Hashing");
+ printf("Hashing");
- for(int i = 0; i < keycount; i++)
- {
- if(i % (keycount / 10) == 0) printf(".");
+ for(int i = 0; i < keycount; i++)
+ {
+ if(i % (keycount / 10) == 0) printf(".");
- keytype & k = keys[i];
+ keytype & k = keys[i];
- hash(&k,sizeof(k),0,&hashes[i]);
- }
+ hash(&k,sizeof(k),0,&hashes[i]);
+ }
- printf("\n");
+ printf("\n");
- bool result = TestHashList(hashes,testColl,testDist,drawDiagram);
+ bool result = TestHashList(hashes,testColl,testDist,drawDiagram);
- printf("\n");
+ printf("\n");
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -178,52 +178,52 @@ bool TestKeyList ( hashfunc<hashtype> hash, std::vector<keytype> & keys, bool te template < typename hashtype >
double TestDistributionBytepairs ( std::vector<hashtype> & hashes, bool drawDiagram )
{
- const int nbytes = sizeof(hashtype);
- const int hashbits = nbytes * 8;
-
- const int nbins = 65536;
+ const int nbytes = sizeof(hashtype);
+ const int hashbits = nbytes * 8;
+
+ const int nbins = 65536;
- std::vector<int> bins(nbins,0);
+ std::vector<int> bins(nbins,0);
- double worst = 0;
+ double worst = 0;
- for(int a = 0; a < hashbits; a++)
- {
- if(drawDiagram) if((a % 8 == 0) && (a > 0)) printf("\n");
+ for(int a = 0; a < hashbits; a++)
+ {
+ if(drawDiagram) if((a % 8 == 0) && (a > 0)) printf("\n");
- if(drawDiagram) printf("[");
+ if(drawDiagram) printf("[");
- for(int b = 0; b < hashbits; b++)
- {
- if(drawDiagram) if((b % 8 == 0) && (b > 0)) printf(" ");
+ for(int b = 0; b < hashbits; b++)
+ {
+ if(drawDiagram) if((b % 8 == 0) && (b > 0)) printf(" ");
- bins.clear();
- bins.resize(nbins,0);
+ bins.clear();
+ bins.resize(nbins,0);
- for(size_t i = 0; i < hashes.size(); i++)
- {
- hashtype & hash = hashes[i];
+ for(size_t i = 0; i < hashes.size(); i++)
+ {
+ hashtype & hash = hashes[i];
- uint32_t pa = window(&hash,sizeof(hash),a,8);
- uint32_t pb = window(&hash,sizeof(hash),b,8);
+ uint32_t pa = window(&hash,sizeof(hash),a,8);
+ uint32_t pb = window(&hash,sizeof(hash),b,8);
- bins[pa | (pb << 8)]++;
- }
+ bins[pa | (pb << 8)]++;
+ }
- double s = calcScore(bins,bins.size(),hashes.size());
+ double s = calcScore(bins,bins.size(),hashes.size());
- if(drawDiagram) plot(s);
+ if(drawDiagram) plot(s);
- if(s > worst)
- {
- worst = s;
- }
- }
+ if(s > worst)
+ {
+ worst = s;
+ }
+ }
- if(drawDiagram) printf("]\n");
- }
+ if(drawDiagram) printf("]\n");
+ }
- return worst;
+ return worst;
}
@@ -233,84 +233,84 @@ double TestDistributionBytepairs ( std::vector<hashtype> & hashes, bool drawDiag template< typename hashtype >
double TestDistribution ( std::vector<hashtype> & hashes, bool drawDiagram )
{
- printf("Testing distribution - ");
+ printf("Testing distribution - ");
- if(drawDiagram) printf("\n");
+ if(drawDiagram) printf("\n");
- const int hashbits = sizeof(hashtype) * 8;
+ const int hashbits = sizeof(hashtype) * 8;
- int maxwidth = 20;
+ int maxwidth = 20;
- // We need at least 5 keys per bin to reliably test distribution biases
- // down to 1%, so don't bother to test sparser distributions than that
+ // We need at least 5 keys per bin to reliably test distribution biases
+ // down to 1%, so don't bother to test sparser distributions than that
- while(double(hashes.size()) / double(1 << maxwidth) < 5.0)
- {
- maxwidth--;
- }
+ while(double(hashes.size()) / double(1 << maxwidth) < 5.0)
+ {
+ maxwidth--;
+ }
- std::vector<int> bins;
- bins.resize(1 << maxwidth);
+ std::vector<int> bins;
+ bins.resize(1 << maxwidth);
- double worst = 0;
- int worstStart = -1;
- int worstWidth = -1;
+ double worst = 0;
+ int worstStart = -1;
+ int worstWidth = -1;
- for(int start = 0; start < hashbits; start++)
- {
- int width = maxwidth;
- int bincount = (1 << width);
+ for(int start = 0; start < hashbits; start++)
+ {
+ int width = maxwidth;
+ int bincount = (1 << width);
- memset(&bins[0],0,sizeof(int)*bincount);
+ memset(&bins[0],0,sizeof(int)*bincount);
- for(size_t j = 0; j < hashes.size(); j++)
- {
- hashtype & hash = hashes[j];
+ for(size_t j = 0; j < hashes.size(); j++)
+ {
+ hashtype & hash = hashes[j];
- uint32_t index = window(&hash,sizeof(hash),start,width);
+ uint32_t index = window(&hash,sizeof(hash),start,width);
- bins[index]++;
- }
+ bins[index]++;
+ }
- // Test the distribution, then fold the bins in half,
- // repeat until we're down to 256 bins
+ // Test the distribution, then fold the bins in half,
+ // repeat until we're down to 256 bins
- if(drawDiagram) printf("[");
+ if(drawDiagram) printf("[");
- while(bincount >= 256)
- {
- double n = calcScore(&bins[0],bincount,(int)hashes.size());
+ while(bincount >= 256)
+ {
+ double n = calcScore(&bins[0],bincount,(int)hashes.size());
- if(drawDiagram) plot(n);
+ if(drawDiagram) plot(n);
- if(n > worst)
- {
- worst = n;
- worstStart = start;
- worstWidth = width;
- }
+ if(n > worst)
+ {
+ worst = n;
+ worstStart = start;
+ worstWidth = width;
+ }
- width--;
- bincount /= 2;
+ width--;
+ bincount /= 2;
- if(width < 8) break;
+ if(width < 8) break;
- for(int i = 0; i < bincount; i++)
- {
- bins[i] += bins[i+bincount];
- }
- }
+ for(int i = 0; i < bincount; i++)
+ {
+ bins[i] += bins[i+bincount];
+ }
+ }
- if(drawDiagram) printf("]\n");
- }
+ if(drawDiagram) printf("]\n");
+ }
- double pct = worst * 100.0;
+ double pct = worst * 100.0;
- printf("Worst bias is the %3d-bit window at bit %3d - %5.3f%%",worstWidth,worstStart,pct);
- if(pct >= 1.0) printf(" !!!!! ");
- printf("\n");
+ printf("Worst bias is the %3d-bit window at bit %3d - %5.3f%%",worstWidth,worstStart,pct);
+ if(pct >= 1.0) printf(" !!!!! ");
+ printf("\n");
- return worst;
+ return worst;
}
//-----------------------------------------------------------------------------
@@ -319,36 +319,36 @@ double TestDistribution ( std::vector<hashtype> & hashes, bool drawDiagram ) template < typename hashtype >
void TestDistributionFast ( std::vector<hashtype> & hashes, double & dworst, double & davg )
{
- const int hashbits = sizeof(hashtype) * 8;
- const int nbins = 65536;
-
- std::vector<int> bins(nbins,0);
+ const int hashbits = sizeof(hashtype) * 8;
+ const int nbins = 65536;
+
+ std::vector<int> bins(nbins,0);
- dworst = -1.0e90;
- davg = 0;
+ dworst = -1.0e90;
+ davg = 0;
- for(int start = 0; start < hashbits; start += 8)
- {
- bins.clear();
- bins.resize(nbins,0);
+ for(int start = 0; start < hashbits; start += 8)
+ {
+ bins.clear();
+ bins.resize(nbins,0);
- for(size_t j = 0; j < hashes.size(); j++)
- {
- hashtype & hash = hashes[j];
+ for(size_t j = 0; j < hashes.size(); j++)
+ {
+ hashtype & hash = hashes[j];
- uint32_t index = window(&hash,sizeof(hash),start,16);
+ uint32_t index = window(&hash,sizeof(hash),start,16);
- bins[index]++;
- }
+ bins[index]++;
+ }
- double n = calcScore((int*)bins.begin(),(int)hashes.size(),(int)bins.size());
-
- davg += n;
+ double n = calcScore((int*)bins.begin(),(int)bins.size(),(int)hashes.size());
+
+ davg += n;
- if(n > dworst) dworst = n;
- }
+ if(n > dworst) dworst = n;
+ }
- davg /= double(hashbits/8);
+ davg /= double(hashbits/8);
}
//-----------------------------------------------------------------------------
diff --git a/SuperFastHash.cpp b/SuperFastHash.cpp index 3425634..b7094d3 100644 --- a/SuperFastHash.cpp +++ b/SuperFastHash.cpp @@ -21,48 +21,48 @@ uint32_t SuperFastHash (const char * data, int len) { uint32_t hash = 0, tmp;
int rem;
- if (len <= 0 || data == NULL) return 0;
+ if (len <= 0 || data == NULL) return 0;
- rem = len & 3;
- len >>= 2;
+ rem = len & 3;
+ len >>= 2;
- /* Main loop */
- for (;len > 0; len--) {
- hash += get16bits (data);
- tmp = (get16bits (data+2) << 11) ^ hash;
- hash = (hash << 16) ^ tmp;
- data += 2*sizeof (uint16_t);
- hash += hash >> 11;
- }
+ /* Main loop */
+ for (;len > 0; len--) {
+ hash += get16bits (data);
+ tmp = (get16bits (data+2) << 11) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ data += 2*sizeof (uint16_t);
+ hash += hash >> 11;
+ }
- /* Handle end cases */
- switch (rem) {
- case 3: hash += get16bits (data);
- hash ^= hash << 16;
- hash ^= data[sizeof (uint16_t)] << 18;
- hash += hash >> 11;
- break;
- case 2: hash += get16bits (data);
- hash ^= hash << 11;
- hash += hash >> 17;
- break;
- case 1: hash += *data;
- hash ^= hash << 10;
- hash += hash >> 1;
- }
+ /* Handle end cases */
+ switch (rem) {
+ case 3: hash += get16bits (data);
+ hash ^= hash << 16;
+ hash ^= data[sizeof (uint16_t)] << 18;
+ hash += hash >> 11;
+ break;
+ case 2: hash += get16bits (data);
+ hash ^= hash << 11;
+ hash += hash >> 17;
+ break;
+ case 1: hash += *data;
+ hash ^= hash << 10;
+ hash += hash >> 1;
+ }
- /* Force "avalanching" of final 127 bits */
- hash ^= hash << 3;
- hash += hash >> 5;
- hash ^= hash << 4;
- hash += hash >> 17;
- hash ^= hash << 25;
- hash += hash >> 6;
+ /* Force "avalanching" of final 127 bits */
+ hash ^= hash << 3;
+ hash += hash >> 5;
+ hash ^= hash << 4;
+ hash += hash >> 17;
+ hash ^= hash << 25;
+ hash += hash >> 6;
- return hash;
+ return hash;
}
void SuperFastHash ( const void * key, int len, uint32_t /*seed*/, void * out )
{
- *(uint32_t*)out = SuperFastHash((const char*)key,len);
+ *(uint32_t*)out = SuperFastHash((const char*)key,len);
}
\ No newline at end of file @@ -10,7 +10,7 @@ void blackhole ( uint32_t ) uint32_t whitehole ( void )
{
- return 0;
+ return 0;
}
#pragma optimize( "", on )
@@ -24,30 +24,30 @@ class hashfunc {
public:
- hashfunc ( pfHash h ) : m_hash(h)
- {
- }
+ hashfunc ( pfHash h ) : m_hash(h)
+ {
+ }
- inline void operator () ( const void * key, const int len, const uint32_t seed, uint32_t * out )
- {
- m_hash(key,len,seed,out);
- }
+ inline void operator () ( const void * key, const int len, const uint32_t seed, uint32_t * out )
+ {
+ m_hash(key,len,seed,out);
+ }
- inline operator pfHash ( void ) const
- {
- return m_hash;
- }
+ inline operator pfHash ( void ) const
+ {
+ return m_hash;
+ }
- inline T operator () ( const void * key, const int len, const uint32_t seed )
- {
- T result;
+ inline T operator () ( const void * key, const int len, const uint32_t seed )
+ {
+ T result;
- m_hash(key,len,seed,(uint32_t*)&result);
+ m_hash(key,len,seed,(uint32_t*)&result);
- return result;
- }
+ return result;
+ }
- pfHash m_hash;
+ pfHash m_hash;
};
//-----------------------------------------------------------------------------
@@ -57,179 +57,179 @@ class Blob {
public:
- Blob()
- {
- }
-
- Blob ( int x )
- {
- for(int i = 0; i < nbytes; i++)
- {
- bytes[i] = 0;
- }
-
- *(int*)bytes = x;
- }
-
- Blob ( const Blob & k )
- {
- for(int i = 0; i < nbytes; i++)
- {
- bytes[i] = k.bytes[i];
- }
- }
-
- Blob & operator = ( const Blob & k )
- {
- for(int i = 0; i < nbytes; i++)
- {
- bytes[i] = k.bytes[i];
- }
-
- return *this;
- }
-
- void set ( const void * blob, int len )
- {
- const uint8_t * k = (const uint8_t*)blob;
-
- len = len > nbytes ? nbytes : len;
-
- for(int i = 0; i < len; i++)
- {
- bytes[i] = k[i];
- }
-
- for(int i = len; i < nbytes; i++)
- {
- bytes[i] = 0;
- }
- }
-
- uint8_t & operator [] ( int i )
- {
- return bytes[i];
- }
-
- const uint8_t & operator [] ( int i ) const
- {
- return bytes[i];
- }
-
- //----------
- // boolean operations
-
- bool operator < ( const Blob & k ) const
- {
- for(int i = 0; i < nbytes; i++)
- {
- if(bytes[i] < k.bytes[i]) return true;
- if(bytes[i] > k.bytes[i]) return false;
- }
-
- return false;
- }
-
- bool operator == ( const Blob & k ) const
- {
- for(int i = 0; i < nbytes; i++)
- {
- if(bytes[i] != k.bytes[i]) return false;
- }
-
- return true;
- }
-
- bool operator != ( const Blob & k ) const
- {
- return !(*this == k);
- }
-
- //----------
- // bitwise operations
-
- Blob operator ^ ( const Blob & k ) const
- {
- Blob t;
-
- for(int i = 0; i < nbytes; i++)
- {
- t.bytes[i] = bytes[i] ^ k.bytes[i];
- }
-
- return t;
- }
-
- Blob & operator ^= ( const Blob & k )
- {
- for(int i = 0; i < nbytes; i++)
- {
- bytes[i] ^= k.bytes[i];
- }
-
- return *this;
- }
-
- int operator & ( int x )
- {
- return (*(int*)bytes) & x;
- }
-
- Blob & operator &= ( const Blob & k )
- {
- for(int i = 0; i < nbytes; i++)
- {
- bytes[i] &= k.bytes[i];
- }
- }
-
- Blob operator << ( int c )
- {
- Blob t = *this;
-
- lshift(&t.bytes[0],nbytes,c);
-
- return t;
- }
-
- Blob operator >> ( int c )
- {
- Blob t = *this;
-
- rshift(&t.bytes[0],nbytes,c);
-
- return t;
- }
-
- Blob & operator <<= ( int c )
- {
- lshift(&bytes[0],nbytes,c);
-
- return *this;
- }
-
- Blob & operator >>= ( int c )
- {
- rshift(&bytes[0],nbytes,c);
-
- return *this;
- }
-
- //----------
-
- enum
- {
- nbits = _bits,
- nbytes = (_bits+7)/8,
-
- align4 = (nbytes & 2) ? 0 : 1,
- align8 = (nbytes & 3) ? 0 : 1,
- align16 = (nbytes & 4) ? 0 : 1,
- };
+ Blob()
+ {
+ }
+
+ Blob ( int x )
+ {
+ for(int i = 0; i < nbytes; i++)
+ {
+ bytes[i] = 0;
+ }
+
+ *(int*)bytes = x;
+ }
+
+ Blob ( const Blob & k )
+ {
+ for(int i = 0; i < nbytes; i++)
+ {
+ bytes[i] = k.bytes[i];
+ }
+ }
+
+ Blob & operator = ( const Blob & k )
+ {
+ for(int i = 0; i < nbytes; i++)
+ {
+ bytes[i] = k.bytes[i];
+ }
+
+ return *this;
+ }
+
+ void set ( const void * blob, int len )
+ {
+ const uint8_t * k = (const uint8_t*)blob;
+
+ len = len > nbytes ? nbytes : len;
+
+ for(int i = 0; i < len; i++)
+ {
+ bytes[i] = k[i];
+ }
+
+ for(int i = len; i < nbytes; i++)
+ {
+ bytes[i] = 0;
+ }
+ }
+
+ uint8_t & operator [] ( int i )
+ {
+ return bytes[i];
+ }
+
+ const uint8_t & operator [] ( int i ) const
+ {
+ return bytes[i];
+ }
+
+ //----------
+ // boolean operations
+
+ bool operator < ( const Blob & k ) const
+ {
+ for(int i = 0; i < nbytes; i++)
+ {
+ if(bytes[i] < k.bytes[i]) return true;
+ if(bytes[i] > k.bytes[i]) return false;
+ }
+
+ return false;
+ }
+
+ bool operator == ( const Blob & k ) const
+ {
+ for(int i = 0; i < nbytes; i++)
+ {
+ if(bytes[i] != k.bytes[i]) return false;
+ }
+
+ return true;
+ }
+
+ bool operator != ( const Blob & k ) const
+ {
+ return !(*this == k);
+ }
+
+ //----------
+ // bitwise operations
+
+ Blob operator ^ ( const Blob & k ) const
+ {
+ Blob t;
+
+ for(int i = 0; i < nbytes; i++)
+ {
+ t.bytes[i] = bytes[i] ^ k.bytes[i];
+ }
+
+ return t;
+ }
+
+ Blob & operator ^= ( const Blob & k )
+ {
+ for(int i = 0; i < nbytes; i++)
+ {
+ bytes[i] ^= k.bytes[i];
+ }
+
+ return *this;
+ }
+
+ int operator & ( int x )
+ {
+ return (*(int*)bytes) & x;
+ }
+
+ Blob & operator &= ( const Blob & k )
+ {
+ for(int i = 0; i < nbytes; i++)
+ {
+ bytes[i] &= k.bytes[i];
+ }
+ }
+
+ Blob operator << ( int c )
+ {
+ Blob t = *this;
+
+ lshift(&t.bytes[0],nbytes,c);
+
+ return t;
+ }
+
+ Blob operator >> ( int c )
+ {
+ Blob t = *this;
+
+ rshift(&t.bytes[0],nbytes,c);
+
+ return t;
+ }
+
+ Blob & operator <<= ( int c )
+ {
+ lshift(&bytes[0],nbytes,c);
+
+ return *this;
+ }
+
+ Blob & operator >>= ( int c )
+ {
+ rshift(&bytes[0],nbytes,c);
+
+ return *this;
+ }
+
+ //----------
+
+ enum
+ {
+ nbits = _bits,
+ nbytes = (_bits+7)/8,
+
+ align4 = (nbytes & 2) ? 0 : 1,
+ align8 = (nbytes & 3) ? 0 : 1,
+ align16 = (nbytes & 4) ? 0 : 1,
+ };
private:
- uint8_t bytes[nbytes];
+ uint8_t bytes[nbytes];
};
typedef Blob<128> uint128_t;
@@ -80,21 +80,21 @@ static const uint32_t crc_table[256] = { void crc32 ( const void * key, int len, uint32_t seed, void * out )
{
- uint8_t * buf = (uint8_t*)key;
- uint32_t crc = seed ^ 0xffffffffL;
+ uint8_t * buf = (uint8_t*)key;
+ uint32_t crc = seed ^ 0xffffffffL;
- while (len >= 8)
- {
- DO8(buf);
- len -= 8;
- }
+ while (len >= 8)
+ {
+ DO8(buf);
+ len -= 8;
+ }
- while(len--)
- {
- DO1(buf);
- }
+ while(len--)
+ {
+ DO1(buf);
+ }
- crc ^= 0xffffffffL;
+ crc ^= 0xffffffffL;
- *(uint32_t*)out = crc;
+ *(uint32_t*)out = crc;
}
diff --git a/lookup3.cpp b/lookup3.cpp index 5dd3a42..edf1c9a 100644 --- a/lookup3.cpp +++ b/lookup3.cpp @@ -27,46 +27,46 @@ uint32_t lookup3 ( const void * key, int length, uint32_t initval )
{
- uint32_t a,b,c; /* internal state */
+ uint32_t a,b,c; /* internal state */
- a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
+ a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
- const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
+ const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
- /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
- while (length > 12)
- {
- a += k[0];
- b += k[1];
- c += k[2];
- mix(a,b,c);
- length -= 12;
- k += 3;
- }
+ /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
+ while (length > 12)
+ {
+ a += k[0];
+ b += k[1];
+ c += k[2];
+ mix(a,b,c);
+ length -= 12;
+ k += 3;
+ }
- switch(length)
- {
- case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
- case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
- case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
- case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
- case 8 : b+=k[1]; a+=k[0]; break;
- case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
- case 6 : b+=k[1]&0xffff; a+=k[0]; break;
- case 5 : b+=k[1]&0xff; a+=k[0]; break;
- case 4 : a+=k[0]; break;
- case 3 : a+=k[0]&0xffffff; break;
- case 2 : a+=k[0]&0xffff; break;
- case 1 : a+=k[0]&0xff; break;
- case 0 : { return c; } /* zero length strings require no mixing */
- }
+ switch(length)
+ {
+ case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
+ case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
+ case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
+ case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
+ case 8 : b+=k[1]; a+=k[0]; break;
+ case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
+ case 6 : b+=k[1]&0xffff; a+=k[0]; break;
+ case 5 : b+=k[1]&0xff; a+=k[0]; break;
+ case 4 : a+=k[0]; break;
+ case 3 : a+=k[0]&0xffffff; break;
+ case 2 : a+=k[0]&0xffff; break;
+ case 1 : a+=k[0]&0xff; break;
+ case 0 : { return c; } /* zero length strings require no mixing */
+ }
- final(a,b,c);
+ final(a,b,c);
- return c;
+ return c;
}
void lookup3_test ( const void * key, int len, uint32_t seed, void * out )
{
- *(uint32_t*)out = lookup3(key,len,seed);
+ *(uint32_t*)out = lookup3(key,len,seed);
}
@@ -8,6 +8,9 @@ #include <stdio.h>
#include <time.h>
+//-----------------------------------------------------------------------------
+// Configuration. TODO - move these to command-line flags
+
bool g_testAll = false;
bool g_testSanity = false;
@@ -23,524 +26,467 @@ bool g_testZeroes = false; bool g_testSeed = false;
//-----------------------------------------------------------------------------
-
-int64_t g_hashcount = 0;
-int64_t g_bytecount = 0;
-
-void counterhash ( const void * , const int len, const uint32_t , void * out )
-{
- g_hashcount++;
- g_bytecount += len;
-
- *(uint32_t*)out = rand_u32();
-}
-
-//-----------------------------------------------------------------------------
+// This is the list of all hashes that SMHasher can test.
struct HashInfo
{
- pfHash hash;
- int hashbits;
- const char * name;
- const char * desc;
+ pfHash hash;
+ int hashbits;
+ uint32_t verification;
+ const char * name;
+ const char * desc;
};
HashInfo g_hashes[] =
{
- { counterhash, 32, "count", "Counts how many times the hash function is called" },
- { randhash_32, 32, "rand32", "Random number generator, 32-bit" },
- { randhash_64, 64, "rand64", "Random number generator, 64-bit" },
- { randhash_128, 128, "rand128", "Random number generator, 128-bit" },
+ { DoNothingHash, 32, 0x00000000, "donothing32", "Do-Nothing function (only valid for measuring call overhead)" },
+ { DoNothingHash, 64, 0x00000000, "donothing64", "Do-Nothing function (only valid for measuring call overhead)" },
+ { DoNothingHash, 128, 0x00000000, "donothing128", "Do-Nothing function (only valid for measuring call overhead)" },
- { crc32, 32, "crc32", "CRC-32" },
- { DoNothingHash, 32, "donothing32", "Do-Nothing Function (only valid for speed test comparison)" },
+ { crc32, 32, 0x5C7DDD1F, "crc32", "CRC-32" },
- { md5_32, 32, "md5_32a", "MD5, first 32 bits of result" },
- { sha1_32a, 32, "sha1_32a", "SHA1, first 32 bits of result" },
+ { md5_32, 32, 0xC10C356B, "md5_32a", "MD5, first 32 bits of result" },
+ { sha1_32a, 32, 0xF9376EA7, "sha1_32a", "SHA1, first 32 bits of result" },
- { FNV, 32, "FNV", "Fowler-Noll-Vo hash, 32-bit" },
- { lookup3_test, 32, "lookup3", "Bob Jenkins' lookup3" },
- { SuperFastHash, 32, "superfast", "Paul Hsieh's SuperFastHash" },
- { MurmurOAAT, 32, "MurmurOAAT", "Murmur one-at-a-time" },
-
- // MurmurHash2
+ { FNV, 32, 0x2B377407, "FNV", "Fowler-Noll-Vo hash, 32-bit" },
+ { lookup3_test, 32, 0xDEC6FD2F, "lookup3", "Bob Jenkins' lookup3" },
+ { SuperFastHash, 32, 0x980ACD1D, "superfast", "Paul Hsieh's SuperFastHash" },
+ { MurmurOAAT, 32, 0x5F424541, "MurmurOAAT", "Murmur one-at-a-time" },
+
+ // MurmurHash2
- { MurmurHash2_test, 32, "Murmur2", "MurmurHash2 for x86, 32-bit" },
- { MurmurHash2A_test, 32, "Murmur2A", "MurmurHash2A for x86, 32-bit" },
- { MurmurHash64A_test, 64, "Murmur2B", "MurmurHash2 for x64, 64-bit" },
- { MurmurHash64B_test, 64, "Murmur2C", "MurmurHash2 for x86, 64-bit" },
+ { MurmurHash2_test, 32, 0xA6D95DE6, "Murmur2", "MurmurHash2 for x86, 32-bit" },
+ { MurmurHash2A_test, 32, 0xB79DC030, "Murmur2A", "MurmurHash2A for x86, 32-bit" },
+ { MurmurHash64A_test, 64, 0xDBD7FF4B, "Murmur2B", "MurmurHash2 for x64, 64-bit" },
+ { MurmurHash64B_test, 64, 0x3B861F71, "Murmur2C", "MurmurHash2 for x86, 64-bit" },
- // MurmurHash3
+ // MurmurHash3
- { MurmurHash3_x86_32, 32, "Murmur3A", "MurmurHash3 for x86, 32-bit" },
- { MurmurHash3_x86_128, 128, "Murmur3C", "MurmurHash3 for x86, 128-bit" },
- { MurmurHash3_x64_128, 128, "Murmur3F", "MurmurHash3 for x64, 128-bit" },
+ { MurmurHash3_x86_32, 32, 0x3B75AFFD, "Murmur3A", "MurmurHash3 for x86, 32-bit" },
+ { MurmurHash3_x86_128, 128, 0x78C7F0DB, "Murmur3C", "MurmurHash3 for x86, 128-bit" },
+ { MurmurHash3_x64_128, 128, 0x54667393, "Murmur3F", "MurmurHash3 for x64, 128-bit" },
};
HashInfo * findHash ( const char * name )
{
- for(int i = 0; i < sizeof(g_hashes) / sizeof(HashInfo); i++)
- {
- if(_stricmp(name,g_hashes[i].name) == 0) return &g_hashes[i];
- }
+ for(int i = 0; i < sizeof(g_hashes) / sizeof(HashInfo); i++)
+ {
+ if(_stricmp(name,g_hashes[i].name) == 0) return &g_hashes[i];
+ }
+
+ return NULL;
+}
+
+//-----------------------------------------------------------------------------
+// Self-test on startup - verify that all installed hashes work correctly.
+
+void SelfTest ( void )
+{
+ bool pass = true;
+
+ for(int i = 0; i < sizeof(g_hashes) / sizeof(HashInfo); i++)
+ {
+ HashInfo * info = & g_hashes[i];
+
+ pass &= VerificationTest(info->hash,info->hashbits,info->verification,false);
+ }
+
+ if(!pass)
+ {
+ printf("Self-test FAILED!\n");
+
+ for(int i = 0; i < sizeof(g_hashes) / sizeof(HashInfo); i++)
+ {
+ HashInfo * info = & g_hashes[i];
+
+ pass &= VerificationTest(info->hash,info->hashbits,info->verification,true);
+ }
- return NULL;
+ exit(1);
+ }
}
//----------------------------------------------------------------------------
template < typename hashtype >
-void test ( hashfunc<hashtype> hash, const char * hashname )
+void test ( hashfunc<hashtype> hash, HashInfo * info )
{
- const int hashbits = sizeof(hashtype) * 8;
-
- printf("-------------------------------------------------------------------------------\n");
- printf("--- Testing %s\n\n",hashname);
-
- //-----------------------------------------------------------------------------
- // Sanity tests
-
- if(g_testSanity || g_testAll)
- {
- printf("[[[ Sanity Tests ]]]\n\n");
-
- QuickBrownFox(hash,hashbits);
- SanityTest(hash,hashbits);
- AppendedZeroesTest(hash,hashbits);
- printf("\n");
- }
-
- //-----------------------------------------------------------------------------
- // Speed tests
-
- if(g_testSpeed || g_testAll)
- {
- printf("[[[ Speed Tests ]]]\n\n");
-
- BulkSpeedTest(hash);
- printf("\n");
-
- for(int i = 1; i < 32; i++)
- {
- double cycles;
-
- TinySpeedTest(hash,sizeof(hashtype),i,true,cycles);
- }
-
- /*
- for(int i = 32; i <= 2048; i += 32)
- {
- double cycles;
-
-
- TinySpeedTest(hash,sizeof(hashtype),i,true,cycles);
- }
- */
-
- printf("\n");
- }
-
- //-----------------------------------------------------------------------------
- // Differential tests
-
- if(g_testDiff || g_testAll)
- {
- printf("[[[ Differential Tests ]]]\n\n");
-
- bool result = true;
- bool dumpCollisions = false;
-
- result &= DiffTest< Blob<64>, hashtype >(hash,5,1000,dumpCollisions);
- result &= DiffTest< Blob<128>, hashtype >(hash,4,1000,dumpCollisions);
- result &= DiffTest< Blob<256>, hashtype >(hash,3,1000,dumpCollisions);
-
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
-
- //-----------------------------------------------------------------------------
- // Avalanche tests.
-
- // 2 million reps is enough to measure bias down to ~0.25%
-
- if(g_testAvalanche || g_testAll)
- {
- printf("[[[ Avalanche Tests ]]]\n\n");
-
- //const int hashbits = sizeof(hashtype) * 8;
- bool result = true;
-
- /*
- result &= AvalancheTest< Blob< 32>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob< 40>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob< 48>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob< 56>, hashtype > (hash,300000);
-
- result &= AvalancheTest< Blob< 64>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob< 72>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob< 80>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob< 88>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob< 96>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<104>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<112>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<120>, hashtype > (hash,300000);
- */
-
- result &= AvalancheTest< Blob<128>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<136>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<144>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<152>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<160>, hashtype > (hash,300000);
-
- /*
- result &= AvalancheTest< Blob<168>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<176>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<184>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<192>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<200>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<208>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<216>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<224>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<232>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<240>, hashtype > (hash,300000);
- result &= AvalancheTest< Blob<248>, hashtype > (hash,300000);
-
- result &= AvalancheTest< Blob<256>, hashtype > (hash,300000);
- */
-
- //result &= AvalancheTest< Blob<hashbits * 2>, hashtype > (hash,200000);
- //result &= AvalancheTest< Blob<768>, hashtype > (hash,2000000);
-
- // The bit independence test is slow and not particularly useful...
- //result &= BicTest < Blob<hashbits * 2>, hashtype > ( hash, 1000000 );
-
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
-
- //-----------------------------------------------------------------------------
- // Keyset 'Cyclic'
-
- if(g_testCyclic || g_testAll)
- {
- printf("[[[ Keyset 'Cyclic' Tests ]]]\n\n");
-
- bool result = true;
- bool drawDiagram = false;
-
- result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+0,8,10000000,drawDiagram);
- result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+1,8,10000000,drawDiagram);
- result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+2,8,10000000,drawDiagram);
- result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+3,8,10000000,drawDiagram);
- result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+4,8,10000000,drawDiagram);
-
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
-
- //-----------------------------------------------------------------------------
- // Keyset 'Sparse'
-
- if(g_testSparse || g_testAll)
- {
- printf("[[[ Keyset 'Sparse' Tests ]]]\n\n");
-
- bool result = true;
- bool drawDiagram = false;
-
- result &= SparseKeyTest< 32,hashtype>(hash,6,true,true,true,drawDiagram);
- result &= SparseKeyTest< 40,hashtype>(hash,6,true,true,true,drawDiagram);
- result &= SparseKeyTest< 48,hashtype>(hash,5,true,true,true,drawDiagram);
- result &= SparseKeyTest< 56,hashtype>(hash,5,true,true,true,drawDiagram);
- result &= SparseKeyTest< 64,hashtype>(hash,5,true,true,true,drawDiagram);
- result &= SparseKeyTest< 96,hashtype>(hash,4,true,true,true,drawDiagram);
- result &= SparseKeyTest< 256,hashtype>(hash,3,true,true,true,drawDiagram);
- result &= SparseKeyTest<2048,hashtype>(hash,2,true,true,true,drawDiagram);
-
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
-
- //-----------------------------------------------------------------------------
- // Keyset 'Permutation'
-
- if(g_testPermutation || g_testAll)
- {
- {
- // This one breaks lookup3, surprisingly
-
- printf("[[[ Keyset 'Combination Lowbits' Tests ]]]\n\n");
-
- bool result = true;
- bool drawDiagram = false;
-
- uint32_t blocks[] =
- {
- 0x00000000,
-
- 0x00000001, 0x00000002, 0x00000003, 0x00000004, 0x00000005, 0x00000006, 0x00000007,
- };
-
- result &= CombinationKeyTest<hashtype>(hash,8,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
-
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
-
- {
- printf("[[[ Keyset 'Combination Highbits' Tests ]]]\n\n");
-
- bool result = true;
- bool drawDiagram = false;
-
- uint32_t blocks[] =
- {
- 0x00000000,
-
- 0x20000000, 0x40000000, 0x60000000, 0x80000000, 0xA0000000, 0xC0000000, 0xE0000000
- };
-
- result &= CombinationKeyTest<hashtype>(hash,8,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
+ const int hashbits = sizeof(hashtype) * 8;
+
+ printf("-------------------------------------------------------------------------------\n");
+ printf("--- Testing %s\n\n",info->name);
+
+ //-----------------------------------------------------------------------------
+ // Sanity tests
+
+ if(g_testSanity || g_testAll)
+ {
+ printf("[[[ Sanity Tests ]]]\n\n");
+
+ VerificationTest(hash,hashbits,info->verification,true);
+ SanityTest(hash,hashbits);
+ AppendedZeroesTest(hash,hashbits);
+ printf("\n");
+ }
+
+ //-----------------------------------------------------------------------------
+ // Speed tests
+
+ if(g_testSpeed || g_testAll)
+ {
+ printf("[[[ Speed Tests ]]]\n\n");
+
+ BulkSpeedTest(hash);
+ printf("\n");
+
+ for(int i = 1; i < 32; i++)
+ {
+ double cycles;
+
+ TinySpeedTest(hash,sizeof(hashtype),i,true,cycles);
+ }
+
+ printf("\n");
+ }
+
+ //-----------------------------------------------------------------------------
+ // Differential tests
+
+ if(g_testDiff || g_testAll)
+ {
+ printf("[[[ Differential Tests ]]]\n\n");
+
+ bool result = true;
+ bool dumpCollisions = false;
+
+ result &= DiffTest< Blob<64>, hashtype >(hash,5,1000,dumpCollisions);
+ result &= DiffTest< Blob<128>, hashtype >(hash,4,1000,dumpCollisions);
+ result &= DiffTest< Blob<256>, hashtype >(hash,3,1000,dumpCollisions);
+
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
+
+ //-----------------------------------------------------------------------------
+ // Avalanche tests
+
+ if(g_testAvalanche || g_testAll)
+ {
+ printf("[[[ Avalanche Tests ]]]\n\n");
+
+ bool result = true;
+
+ result &= AvalancheTest< Blob< 32>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob< 40>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob< 48>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob< 56>, hashtype > (hash,300000);
+
+ result &= AvalancheTest< Blob< 64>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob< 72>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob< 80>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob< 88>, hashtype > (hash,300000);
+
+ result &= AvalancheTest< Blob< 96>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob<104>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob<112>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob<120>, hashtype > (hash,300000);
+
+ result &= AvalancheTest< Blob<128>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob<136>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob<144>, hashtype > (hash,300000);
+ result &= AvalancheTest< Blob<152>, hashtype > (hash,300000);
+
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
+
+ //-----------------------------------------------------------------------------
+ // Keyset 'Cyclic'
+
+ if(g_testCyclic || g_testAll)
+ {
+ printf("[[[ Keyset 'Cyclic' Tests ]]]\n\n");
+
+ bool result = true;
+ bool drawDiagram = false;
+
+ result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+0,8,10000000,drawDiagram);
+ result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+1,8,10000000,drawDiagram);
+ result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+2,8,10000000,drawDiagram);
+ result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+3,8,10000000,drawDiagram);
+ result &= CyclicKeyTest<hashtype>(hash,sizeof(hashtype)+4,8,10000000,drawDiagram);
+
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
+
+ //-----------------------------------------------------------------------------
+ // Keyset 'Sparse'
+
+ if(g_testSparse || g_testAll)
+ {
+ printf("[[[ Keyset 'Sparse' Tests ]]]\n\n");
+
+ bool result = true;
+ bool drawDiagram = false;
+
+ result &= SparseKeyTest< 32,hashtype>(hash,6,true,true,true,drawDiagram);
+ result &= SparseKeyTest< 40,hashtype>(hash,6,true,true,true,drawDiagram);
+ result &= SparseKeyTest< 48,hashtype>(hash,5,true,true,true,drawDiagram);
+ result &= SparseKeyTest< 56,hashtype>(hash,5,true,true,true,drawDiagram);
+ result &= SparseKeyTest< 64,hashtype>(hash,5,true,true,true,drawDiagram);
+ result &= SparseKeyTest< 96,hashtype>(hash,4,true,true,true,drawDiagram);
+ result &= SparseKeyTest< 256,hashtype>(hash,3,true,true,true,drawDiagram);
+ result &= SparseKeyTest<2048,hashtype>(hash,2,true,true,true,drawDiagram);
+
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
+
+ //-----------------------------------------------------------------------------
+ // Keyset 'Permutation'
+
+ if(g_testPermutation || g_testAll)
+ {
+ {
+ // This one breaks lookup3, surprisingly
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
+ printf("[[[ Keyset 'Combination Lowbits' Tests ]]]\n\n");
+
+ bool result = true;
+ bool drawDiagram = false;
- {
- printf("[[[ Keyset 'Combination 0x8000000' Tests ]]]\n\n");
+ uint32_t blocks[] =
+ {
+ 0x00000000,
+
+ 0x00000001, 0x00000002, 0x00000003, 0x00000004, 0x00000005, 0x00000006, 0x00000007,
+ };
- bool result = true;
- bool drawDiagram = false;
+ result &= CombinationKeyTest<hashtype>(hash,8,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
- uint32_t blocks[] =
- {
- 0x00000000,
-
- 0x80000000,
- };
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
- result &= CombinationKeyTest<hashtype>(hash,20,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
+ {
+ printf("[[[ Keyset 'Combination Highbits' Tests ]]]\n\n");
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
+ bool result = true;
+ bool drawDiagram = false;
- {
- printf("[[[ Keyset 'Combination 0x0000001' Tests ]]]\n\n");
+ uint32_t blocks[] =
+ {
+ 0x00000000,
+
+ 0x20000000, 0x40000000, 0x60000000, 0x80000000, 0xA0000000, 0xC0000000, 0xE0000000
+ };
- bool result = true;
- bool drawDiagram = false;
+ result &= CombinationKeyTest<hashtype>(hash,8,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
- uint32_t blocks[] =
- {
- 0x00000000,
-
- 0x00000001,
- };
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
- result &= CombinationKeyTest<hashtype>(hash,20,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
+ {
+ printf("[[[ Keyset 'Combination 0x8000000' Tests ]]]\n\n");
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
+ bool result = true;
+ bool drawDiagram = false;
- {
- printf("[[[ Keyset 'Combination Hi-Lo' Tests ]]]\n\n");
+ uint32_t blocks[] =
+ {
+ 0x00000000,
+
+ 0x80000000,
+ };
- bool result = true;
- bool drawDiagram = false;
+ result &= CombinationKeyTest<hashtype>(hash,20,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
- uint32_t blocks[] =
- {
- 0x00000000,
-
- 0x00000001, 0x00000002, 0x00000003, 0x00000004, 0x00000005, 0x00000006, 0x00000007,
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
- 0x80000000, 0x40000000, 0xC0000000, 0x20000000, 0xA0000000, 0x60000000, 0xE0000000
- };
+ {
+ printf("[[[ Keyset 'Combination 0x0000001' Tests ]]]\n\n");
- result &= CombinationKeyTest<hashtype>(hash,6,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
+ bool result = true;
+ bool drawDiagram = false;
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
+ uint32_t blocks[] =
+ {
+ 0x00000000,
+
+ 0x00000001,
+ };
- //----------
+ result &= CombinationKeyTest<hashtype>(hash,20,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
- /*
- {
- printf("[[[ Keyset 'Permutation' Tests ]]]\n\n");
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
- bool result = true;
- bool drawDiagram = false;
+ {
+ printf("[[[ Keyset 'Combination Hi-Lo' Tests ]]]\n\n");
- // This very sparse set of blocks is particularly hard for SuperFastHash
+ bool result = true;
+ bool drawDiagram = false;
- uint32_t blocks[] =
- {
- 0x00000000,
- 0x00000001,
- 0x00000002,
-
- 0x00000400,
- 0x00008000,
-
- 0x00080000,
- 0x00200000,
+ uint32_t blocks[] =
+ {
+ 0x00000000,
+
+ 0x00000001, 0x00000002, 0x00000003, 0x00000004, 0x00000005, 0x00000006, 0x00000007,
- 0x20000000,
- 0x40000000,
- 0x80000000,
- };
+ 0x80000000, 0x40000000, 0xC0000000, 0x20000000, 0xA0000000, 0x60000000, 0xE0000000
+ };
- result &= PermutationKeyTest<hashtype>(hash,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
+ result &= CombinationKeyTest<hashtype>(hash,6,blocks,sizeof(blocks) / sizeof(uint32_t),true,true,drawDiagram);
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
- */
- }
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
+ }
- //-----------------------------------------------------------------------------
- // Keyset 'Window'
+ //-----------------------------------------------------------------------------
+ // Keyset 'Window'
- // Skip distribution test for these - they're too easy to distribute well,
- // and it generates a _lot_ of testing
+ // Skip distribution test for these - they're too easy to distribute well,
+ // and it generates a _lot_ of testing
- if(g_testWindow || g_testAll)
- {
- printf("[[[ Keyset 'Window' Tests ]]]\n\n");
+ if(g_testWindow || g_testAll)
+ {
+ printf("[[[ Keyset 'Window' Tests ]]]\n\n");
- bool result = true;
- bool testCollision = true;
- bool testDistribution = false;
- bool drawDiagram = false;
+ bool result = true;
+ bool testCollision = true;
+ bool testDistribution = false;
+ bool drawDiagram = false;
- result &= WindowedKeyTest< Blob<hashbits*2>, hashtype > ( hash, 20, testCollision, testDistribution, drawDiagram );
+ result &= WindowedKeyTest< Blob<hashbits*2>, hashtype > ( hash, 20, testCollision, testDistribution, drawDiagram );
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
- //-----------------------------------------------------------------------------
- // Keyset 'Text'
+ //-----------------------------------------------------------------------------
+ // Keyset 'Text'
- if(g_testText || g_testAll)
- {
- printf("[[[ Keyset 'Text' Tests ]]]\n\n");
+ if(g_testText || g_testAll)
+ {
+ printf("[[[ Keyset 'Text' Tests ]]]\n\n");
- bool result = true;
- bool drawDiagram = false;
+ bool result = true;
+ bool drawDiagram = false;
- const char * alnum = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
+ const char * alnum = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
- result &= TextKeyTest( hash, "Foo", alnum,4, "Bar", drawDiagram );
- result &= TextKeyTest( hash, "FooBar", alnum,4, "", drawDiagram );
- result &= TextKeyTest( hash, "", alnum,4, "FooBar", drawDiagram );
+ result &= TextKeyTest( hash, "Foo", alnum,4, "Bar", drawDiagram );
+ result &= TextKeyTest( hash, "FooBar", alnum,4, "", drawDiagram );
+ result &= TextKeyTest( hash, "", alnum,4, "FooBar", drawDiagram );
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
- //-----------------------------------------------------------------------------
- // Keyset 'Zeroes'
+ //-----------------------------------------------------------------------------
+ // Keyset 'Zeroes'
- if(g_testZeroes || g_testAll)
- {
- printf("[[[ Keyset 'Zeroes' Tests ]]]\n\n");
+ if(g_testZeroes || g_testAll)
+ {
+ printf("[[[ Keyset 'Zeroes' Tests ]]]\n\n");
- bool result = true;
- bool drawDiagram = false;
+ bool result = true;
+ bool drawDiagram = false;
- result &= ZeroKeyTest<hashtype>( hash, drawDiagram );
+ result &= ZeroKeyTest<hashtype>( hash, drawDiagram );
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
- //-----------------------------------------------------------------------------
- // Keyset 'Seed'
+ //-----------------------------------------------------------------------------
+ // Keyset 'Seed'
- if(g_testSeed || g_testAll)
- {
- printf("[[[ Keyset 'Seed' Tests ]]]\n\n");
+ if(g_testSeed || g_testAll)
+ {
+ printf("[[[ Keyset 'Seed' Tests ]]]\n\n");
- bool result = true;
- bool drawDiagram = false;
+ bool result = true;
+ bool drawDiagram = false;
- result &= SeedTest<hashtype>( hash, 1000000, drawDiagram );
+ result &= SeedTest<hashtype>( hash, 1000000, drawDiagram );
- if(!result) printf("*********FAIL*********\n");
- printf("\n");
- }
+ if(!result) printf("*********FAIL*********\n");
+ printf("\n");
+ }
}
//-----------------------------------------------------------------------------
void testHash ( const char * name )
{
- HashInfo * pInfo = findHash(name);
-
- if(pInfo == NULL)
- {
- printf("Invalid hash '%s' specified\n",name);
- return;
- }
- else
- {
- if(pInfo->hashbits == 32)
- {
- test<uint32_t>( pInfo->hash, pInfo->desc );
- }
- else if(pInfo->hashbits == 64)
- {
- test<uint64_t>( pInfo->hash, pInfo->desc );
- }
- else if(pInfo->hashbits == 128)
- {
- test<uint128_t>( pInfo->hash, pInfo->desc );
- }
- else if(pInfo->hashbits == 256)
- {
- test<uint256_t>( pInfo->hash, pInfo->desc );
- }
- else
- {
- printf("Invalid hash bit width %d for hash '%s'",pInfo->hashbits,pInfo->name);
- }
- }
+ HashInfo * pInfo = findHash(name);
+
+ if(pInfo == NULL)
+ {
+ printf("Invalid hash '%s' specified\n",name);
+ return;
+ }
+ else
+ {
+ if(pInfo->hashbits == 32)
+ {
+ test<uint32_t>( pInfo->hash, pInfo );
+ }
+ else if(pInfo->hashbits == 64)
+ {
+ test<uint64_t>( pInfo->hash, pInfo );
+ }
+ else if(pInfo->hashbits == 128)
+ {
+ test<uint128_t>( pInfo->hash, pInfo );
+ }
+ else if(pInfo->hashbits == 256)
+ {
+ test<uint256_t>( pInfo->hash, pInfo );
+ }
+ else
+ {
+ printf("Invalid hash bit width %d for hash '%s'",pInfo->hashbits,pInfo->name);
+ }
+ }
}
//-----------------------------------------------------------------------------
int main ( int argc, char ** argv )
{
- SetAffinity(2);
+ SetAffinity(2);
- int timeBegin = clock();
+ SelfTest();
- g_testAll = true;
+ int timeBegin = clock();
- //g_testSanity = true;
- //g_testSpeed = true;
- //g_testAvalanche = true;
- //g_testCyclic = true;
- //g_testDiff = true;
- //g_testSparse = true;
- //g_testPermutation = true;
- //g_testZeroes = true;
+ g_testAll = true;
- //testHash("count");
- //printf("Called the hash function %I64d times, %I64d bytes hashed\n",g_hashcount,g_bytecount);
+ //g_testSanity = true;
+ //g_testSpeed = true;
+ //g_testAvalanche = true;
+ //g_testCyclic = true;
+ //g_testDiff = true;
+ //g_testSparse = true;
+ //g_testPermutation = true;
+ //g_testZeroes = true;
- testHash("murmur3a");
+ testHash("murmur3a");
- //----------
+ //----------
- int timeEnd = clock();
+ int timeEnd = clock();
printf("\n");
- printf("Testing took %f seconds\n",double(timeEnd-timeBegin)/double(CLOCKS_PER_SEC));
+ printf("Testing took %f seconds\n",double(timeEnd-timeBegin)/double(CLOCKS_PER_SEC));
printf("-------------------------------------------------------------------------------\n");
- return 0;
+ return 0;
}
@@ -363,20 +363,20 @@ void md5( unsigned char *input, int ilen, unsigned char output[16] ) unsigned int md5hash ( const void * input, int len, unsigned int /*seed*/ )
{
- unsigned int hash[4];
+ unsigned int hash[4];
- md5((unsigned char *)input,len,(unsigned char *)hash);
+ md5((unsigned char *)input,len,(unsigned char *)hash);
- //return hash[0] ^ hash[1] ^ hash[2] ^ hash[3];
+ //return hash[0] ^ hash[1] ^ hash[2] ^ hash[3];
- return hash[0];
+ return hash[0];
}
void md5_32 ( const void * key, int len, uint32_t /*seed*/, void * out )
{
- unsigned int hash[4];
+ unsigned int hash[4];
- md5((unsigned char*)key,len,(unsigned char*)hash);
+ md5((unsigned char*)key,len,(unsigned char*)hash);
- *(uint32_t*)out = hash[0];
+ *(uint32_t*)out = hash[0];
}
\ No newline at end of file @@ -749,51 +749,51 @@ typedef uint_least32_t uint_fast32_t; #define TESTUMAX(bits) glue3(u,bits,=) glue3(~,u,bits); if (glue3(UINT,bits,_MAX) glue3(!=,u,bits)) printf ("Something wrong with UINT%d_MAX\n", bits)
int main () {
- DECL(I,8)
- DECL(U,8)
- DECL(I,16)
- DECL(U,16)
- DECL(I,32)
- DECL(U,32)
+ DECL(I,8)
+ DECL(U,8)
+ DECL(I,16)
+ DECL(U,16)
+ DECL(I,32)
+ DECL(U,32)
#ifdef INT64_MAX
- DECL(I,64)
- DECL(U,64)
-#endif
- intmax_t imax = INTMAX_C(0);
- uintmax_t umax = UINTMAX_C(0);
- char str0[256], str1[256];
-
- sprintf (str0, "%d %x\n", 0, ~0);
-
- sprintf (str1, "%d %x\n", i8, ~0);
- if (0 != strcmp (str0, str1)) printf ("Something wrong with i8 : %s\n", str1);
- sprintf (str1, "%u %x\n", u8, ~0);
- if (0 != strcmp (str0, str1)) printf ("Something wrong with u8 : %s\n", str1);
- sprintf (str1, "%d %x\n", i16, ~0);
- if (0 != strcmp (str0, str1)) printf ("Something wrong with i16 : %s\n", str1);
- sprintf (str1, "%u %x\n", u16, ~0);
- if (0 != strcmp (str0, str1)) printf ("Something wrong with u16 : %s\n", str1);
- sprintf (str1, "%" PRINTF_INT32_MODIFIER "d %x\n", i32, ~0);
- if (0 != strcmp (str0, str1)) printf ("Something wrong with i32 : %s\n", str1);
- sprintf (str1, "%" PRINTF_INT32_MODIFIER "u %x\n", u32, ~0);
- if (0 != strcmp (str0, str1)) printf ("Something wrong with u32 : %s\n", str1);
+ DECL(I,64)
+ DECL(U,64)
+#endif
+ intmax_t imax = INTMAX_C(0);
+ uintmax_t umax = UINTMAX_C(0);
+ char str0[256], str1[256];
+
+ sprintf (str0, "%d %x\n", 0, ~0);
+
+ sprintf (str1, "%d %x\n", i8, ~0);
+ if (0 != strcmp (str0, str1)) printf ("Something wrong with i8 : %s\n", str1);
+ sprintf (str1, "%u %x\n", u8, ~0);
+ if (0 != strcmp (str0, str1)) printf ("Something wrong with u8 : %s\n", str1);
+ sprintf (str1, "%d %x\n", i16, ~0);
+ if (0 != strcmp (str0, str1)) printf ("Something wrong with i16 : %s\n", str1);
+ sprintf (str1, "%u %x\n", u16, ~0);
+ if (0 != strcmp (str0, str1)) printf ("Something wrong with u16 : %s\n", str1);
+ sprintf (str1, "%" PRINTF_INT32_MODIFIER "d %x\n", i32, ~0);
+ if (0 != strcmp (str0, str1)) printf ("Something wrong with i32 : %s\n", str1);
+ sprintf (str1, "%" PRINTF_INT32_MODIFIER "u %x\n", u32, ~0);
+ if (0 != strcmp (str0, str1)) printf ("Something wrong with u32 : %s\n", str1);
#ifdef INT64_MAX
- sprintf (str1, "%" PRINTF_INT64_MODIFIER "d %x\n", i64, ~0);
- if (0 != strcmp (str0, str1)) printf ("Something wrong with i64 : %s\n", str1);
-#endif
- sprintf (str1, "%" PRINTF_INTMAX_MODIFIER "d %x\n", imax, ~0);
- if (0 != strcmp (str0, str1)) printf ("Something wrong with imax : %s\n", str1);
- sprintf (str1, "%" PRINTF_INTMAX_MODIFIER "u %x\n", umax, ~0);
- if (0 != strcmp (str0, str1)) printf ("Something wrong with umax : %s\n", str1);
-
- TESTUMAX(8);
- TESTUMAX(16);
- TESTUMAX(32);
+ sprintf (str1, "%" PRINTF_INT64_MODIFIER "d %x\n", i64, ~0);
+ if (0 != strcmp (str0, str1)) printf ("Something wrong with i64 : %s\n", str1);
+#endif
+ sprintf (str1, "%" PRINTF_INTMAX_MODIFIER "d %x\n", imax, ~0);
+ if (0 != strcmp (str0, str1)) printf ("Something wrong with imax : %s\n", str1);
+ sprintf (str1, "%" PRINTF_INTMAX_MODIFIER "u %x\n", umax, ~0);
+ if (0 != strcmp (str0, str1)) printf ("Something wrong with umax : %s\n", str1);
+
+ TESTUMAX(8);
+ TESTUMAX(16);
+ TESTUMAX(32);
#ifdef INT64_MAX
- TESTUMAX(64);
+ TESTUMAX(64);
#endif
- return EXIT_SUCCESS;
+ return EXIT_SUCCESS;
}
#endif
@@ -10,10 +10,10 @@ Still 100% Public Domain Corrected a problem which generated improper hash values on 16 bit machines
Routine SHA1Update changed from
- void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned int
+ void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned int
len)
to
- void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned
+ void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned
long len)
The 'len' parameter was declared an int which works fine on 32 bit machines.
@@ -172,7 +172,7 @@ void SHA1_Init(SHA1_CTX* context) context->state[3] = 0x10325476;
context->state[4] = 0xC3D2E1F0;
context->count[0] = 0;
- context->count[1] = 0;
+ context->count[1] = 0;
}
@@ -187,12 +187,12 @@ void SHA1_Update(SHA1_CTX* context, const uint8_t* data, const size_t len) context->count[1] += (len >> 29);
if ((j + len) > 63)
- {
+ {
memcpy(&context->buffer[j], data, (i = 64-j));
SHA1_Transform(context->state, context->buffer);
for ( ; i + 63 < len; i += 64)
- {
+ {
SHA1_Transform(context->state, data + i);
}
@@ -235,15 +235,15 @@ void SHA1_Final(SHA1_CTX* context, uint8_t digest[SHA1_DIGEST_SIZE]) void sha1_32a ( const void * key, int len, uint32_t seed, void * out )
{
- SHA1_CTX context;
+ SHA1_CTX context;
- uint8_t digest[20];
+ uint8_t digest[20];
- SHA1_Init(&context);
- SHA1_Update(&context, (uint8_t*)key, len);
- SHA1_Final(&context, digest);
+ SHA1_Init(&context);
+ SHA1_Update(&context, (uint8_t*)key, len);
+ SHA1_Final(&context, digest);
- memcpy(out,&digest[0],4);
+ memcpy(out,&digest[0],4);
}
//-----------------------------------------------------------------------------
@@ -292,7 +292,7 @@ int main(int argc, char** argv) SHA1_Init(&context);
SHA1_Update(&context, (uint8_t*)test_data[k], strlen(test_data[k]));
SHA1_Final(&context, digest);
- digest_to_hex(digest, output);
+ digest_to_hex(digest, output);
if (strcmp(output, test_results[k])) {
fprintf(stdout, "FAIL\n");
|