1f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include "KeysetTest.h" 2f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 3f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include "Platform.h" 4f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include "Random.h" 5f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 6f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include <map> 7f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include <set> 8f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 9f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 10f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// This should hopefully be a thorough and uambiguous test of whether a hash 11f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// is correctly implemented on a given platform 12f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 13f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.combool VerificationTest ( pfHash hash, const int hashbits, uint32_t expected, bool verbose ) 14f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 15f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbytes = hashbits / 8; 16f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 17f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t * key = new uint8_t[256]; 18f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t * hashes = new uint8_t[hashbytes * 256]; 19f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t * final = new uint8_t[hashbytes]; 20f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 21f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com memset(key,0,256); 22f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com memset(hashes,0,hashbytes*256); 23f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com memset(final,0,hashbytes); 24f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 25f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Hash keys of the form {0}, {0,1}, {0,1,2}... up to N=255,using 256-N as 26f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // the seed 27f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 28f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 0; i < 256; i++) 29f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 30f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com key[i] = (uint8_t)i; 31f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 32f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(key,i,256-i,&hashes[i*hashbytes]); 33f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 34f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 35f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Then hash the result array 36f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 37f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(hashes,hashbytes*256,0,final); 38f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 39f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // The first four bytes of that hash, interpreted as a little-endian integer, is our 40f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // verification value 41f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 42f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t verification = (final[0] << 0) | (final[1] << 8) | (final[2] << 16) | (final[3] << 24); 43f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 44f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com delete [] key; 45f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com delete [] hashes; 46f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com delete [] final; 47f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 48f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 49f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 50f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(expected != verification) 51f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 52f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) printf("Verification value 0x%08X : Failed! (Expected 0x%08x)\n",verification,expected); 53f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return false; 54f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 55f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else 56f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 57f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) printf("Verification value 0x%08X : Passed!\n",verification); 58f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return true; 59f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 60f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 61f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 62f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//---------------------------------------------------------------------------- 63f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Basic sanity checks - 64f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 65f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// A hash function should not be reading outside the bounds of the key. 66f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 67f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Flipping a bit of a key should, with overwhelmingly high probability, 68f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// result in a different hash. 69f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 70f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Hashing the same key twice should always produce the same result. 71f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 72f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// The memory alignment of the key should not affect the hash result. 73f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 74f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.combool SanityTest ( pfHash hash, const int hashbits ) 75f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 76f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Running sanity check 1"); 77f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 78f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com Rand r(883741); 79f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 80f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com bool result = true; 81f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 82f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbytes = hashbits/8; 83f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int reps = 10; 84dd462f2c6817d4e09a6ecd99f35e3a04c342afb2tanjent@gmail.com const int keymax = 256; 85f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int pad = 16; 86f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int buflen = keymax + pad*3; 87f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 88f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t * buffer1 = new uint8_t[buflen]; 89f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t * buffer2 = new uint8_t[buflen]; 90f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 91f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t * hash1 = new uint8_t[hashbytes]; 92f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t * hash2 = new uint8_t[hashbytes]; 93f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 94f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 95f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 96f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int irep = 0; irep < reps; irep++) 97f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 98f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(irep % (reps/10) == 0) printf("."); 99f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 100f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int len = 4; len <= keymax; len++) 101f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 102f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int offset = pad; offset < pad*2; offset++) 103f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 104f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t * key1 = &buffer1[pad]; 105f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t * key2 = &buffer2[pad+offset]; 106f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 107f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com r.rand_p(buffer1,buflen); 108f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com r.rand_p(buffer2,buflen); 109f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 110f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com memcpy(key2,key1,len); 111f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 112f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(key1,len,0,hash1); 113f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 114f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int bit = 0; bit < (len * 8); bit++) 115f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 116f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Flip a bit, hash the key -> we should get a different result. 117f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 118f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com flipbit(key2,len,bit); 119f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(key2,len,0,hash2); 120f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 121f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(memcmp(hash1,hash2,hashbytes) == 0) 122f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 123f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com result = false; 124f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 125f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 126f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Flip it back, hash again -> we should get the original result. 127f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 128f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com flipbit(key2,len,bit); 129f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(key2,len,0,hash2); 130f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 131f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(memcmp(hash1,hash2,hashbytes) != 0) 132f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 133f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com result = false; 134f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 135f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 136f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 137f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 138f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 139f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 140f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(result == false) 141f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 142f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("*********FAIL*********\n"); 143f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 144f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else 145f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 146f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("PASS\n"); 147f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 148f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 149e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com delete [] buffer1; 150e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com delete [] buffer2; 151e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com 152f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com delete [] hash1; 153f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com delete [] hash2; 154f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 155f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return result; 156f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 157f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 158f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//---------------------------------------------------------------------------- 159f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Appending zero bytes to a key should always cause it to produce a different 160f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// hash value 161f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 162f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid AppendedZeroesTest ( pfHash hash, const int hashbits ) 163f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 164f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Running sanity check 2"); 165f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 166f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com Rand r(173994); 167f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 168f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbytes = hashbits/8; 169f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 170f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int rep = 0; rep < 100; rep++) 171f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 172f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(rep % 10 == 0) printf("."); 173f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 174f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com unsigned char key[256]; 175f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 176f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com memset(key,0,sizeof(key)); 177f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 178f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com r.rand_p(key,32); 179f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 180f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h1[16]; 181f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h2[16]; 182f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 183f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com memset(h1,0,hashbytes); 184f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com memset(h2,0,hashbytes); 185f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 186f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 0; i < 32; i++) 187f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 188f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(key,32+i,0,h1); 189f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 190f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(memcmp(h1,h2,hashbytes) == 0) 191f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 192f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("\n*********FAIL*********\n"); 193f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return; 194f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 195f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 196f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com memcpy(h2,h1,hashbytes); 197f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 198f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 199f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 200f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("PASS\n"); 201f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 202f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 203f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 204f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Generate all keys of up to N bytes containing two non-zero bytes 205f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 206f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid TwoBytesKeygen ( int maxlen, KeyCallback & c ) 207f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 208f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 209f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Compute # of keys 210f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 211f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int keycount = 0; 212f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 213f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 2; i <= maxlen; i++) keycount += (int)chooseK(i,2); 214f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 215f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com keycount *= 255*255; 216f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 217f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 2; i <= maxlen; i++) keycount += i*255; 218f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 219f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Keyset 'TwoBytes' - up-to-%d-byte keys, %d total keys\n",maxlen, keycount); 220f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 221f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com c.reserve(keycount); 222f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 223f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 224f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Add all keys with one non-zero byte 225f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 226f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint8_t key[256]; 227f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 228f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com memset(key,0,256); 229f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 230f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int keylen = 2; keylen <= maxlen; keylen++) 231f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int byteA = 0; byteA < keylen; byteA++) 232f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 233f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int valA = 1; valA <= 255; valA++) 234f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 235f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com key[byteA] = (uint8_t)valA; 236f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 237f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com c(key,keylen); 238f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 239f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 240f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com key[byteA] = 0; 241f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 242f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 243f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 244f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Add all keys with two non-zero bytes 245f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 246f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int keylen = 2; keylen <= maxlen; keylen++) 247f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int byteA = 0; byteA < keylen-1; byteA++) 248f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int byteB = byteA+1; byteB < keylen; byteB++) 249f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 250f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int valA = 1; valA <= 255; valA++) 251f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 252f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com key[byteA] = (uint8_t)valA; 253f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 254f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int valB = 1; valB <= 255; valB++) 255f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 256f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com key[byteB] = (uint8_t)valB; 257f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com c(key,keylen); 258f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 259f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 260f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com key[byteB] = 0; 261f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 262f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 263f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com key[byteA] = 0; 264f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 265f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 266f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 267f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 268f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 269f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtemplate< typename hashtype > 270f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid DumpCollisionMap ( CollisionMap<hashtype,ByteVec> & cmap ) 271f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 272f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com typedef CollisionMap<hashtype,ByteVec> cmap_t; 273f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 274f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(typename cmap_t::iterator it = cmap.begin(); it != cmap.end(); ++it) 275f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 276f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const hashtype & hash = (*it).first; 277f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 278f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Hash - "); 279f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printbytes(&hash,sizeof(hashtype)); 280f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("\n"); 281f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 282f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com std::vector<ByteVec> & keys = (*it).second; 283f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 284f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 0; i < (int)keys.size(); i++) 285f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 286f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com ByteVec & key = keys[i]; 287f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 288f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Key - "); 289f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printbytes(&key[0],(int)key.size()); 290f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("\n"); 291f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 292f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("\n"); 293f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 294f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 295f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 296f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 297f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// test code 298f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 299f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid ReportCollisions ( pfHash hash ) 300f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 301f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Hashing keyset\n"); 302f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 303f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com std::vector<uint128_t> hashes; 304f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 305f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com HashCallback<uint128_t> c(hash,hashes); 306f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 307f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com TwoBytesKeygen(20,c); 308f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 309f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("%d hashes\n",(int)hashes.size()); 310f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 311f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Finding collisions\n"); 312f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 313f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com HashSet<uint128_t> collisions; 314f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 315f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com FindCollisions(hashes,collisions,1000); 316f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 317f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("%d collisions\n",(int)collisions.size()); 318f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 319f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Mapping collisions\n"); 320f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 321f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com CollisionMap<uint128_t,ByteVec> cmap; 322f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 323f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com CollisionCallback<uint128_t> c2(hash,collisions,cmap); 324f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 325f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com TwoBytesKeygen(20,c2); 326f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 327f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Dumping collisions\n"); 328f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 329f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com DumpCollisionMap(cmap); 330f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 331