1f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 2f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Flipping a single bit of a key should cause an "avalanche" of changes in 3f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// the hash function's output. Ideally, each output bits should flip 50% of 4f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// the time - if the probability of an output bit flipping is not 50%, that bit 5f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// is "biased". Too much bias means that patterns applied to the input will 6f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// cause "echoes" of the patterns in the output, which in turn can cause the 7f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// hash function to fail to create an even, random distribution of hash values. 8f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 9f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 10f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#pragma once 11f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 12f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include "Types.h" 13f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include "Random.h" 14f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 15f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include <vector> 16f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include <stdio.h> 17f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include <math.h> 18f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 19f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Avalanche fails if a bit is biased by more than 1% 20f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 21f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define AVALANCHE_FAIL 0.01 22f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 23f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comdouble maxBias ( std::vector<int> & counts, int reps ); 24f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 25f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 26f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 27f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtemplate < typename keytype, typename hashtype > 28f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid calcBias ( pfHash hash, std::vector<int> & counts, int reps, Rand & r ) 29f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 30f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybytes = sizeof(keytype); 31f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbytes = sizeof(hashtype); 32f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 33f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybits = keybytes * 8; 34f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbits = hashbytes * 8; 35f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 36f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com keytype K; 37f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hashtype A,B; 38f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 39f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int irep = 0; irep < reps; irep++) 40f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 41f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(irep % (reps/10) == 0) printf("."); 42f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 43f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com r.rand_p(&K,keybytes); 44f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 45f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(&K,keybytes,0,&A); 46f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 47f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int * cursor = &counts[0]; 48f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 49f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int iBit = 0; iBit < keybits; iBit++) 50f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 51f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com flipbit(&K,keybytes,iBit); 52f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(&K,keybytes,0,&B); 53f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com flipbit(&K,keybytes,iBit); 54f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 55f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int iOut = 0; iOut < hashbits; iOut++) 56f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 57f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int bitA = getbit(&A,hashbytes,iOut); 58f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int bitB = getbit(&B,hashbytes,iOut); 59f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 60f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com (*cursor++) += (bitA ^ bitB); 61f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 62f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 63f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 64f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 65f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 66f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 67f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 68f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtemplate < typename keytype, typename hashtype > 69f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.combool AvalancheTest ( pfHash hash, const int reps ) 70f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 71f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com Rand r(48273); 72f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 73f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybytes = sizeof(keytype); 74f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbytes = sizeof(hashtype); 75f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 76f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybits = keybytes * 8; 77f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbits = hashbytes * 8; 78f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 79f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Testing %3d-bit keys -> %3d-bit hashes, %8d reps",keybits,hashbits,reps); 80f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 81f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 82f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 83f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com std::vector<int> bins(keybits*hashbits,0); 84f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 85f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com calcBias<keytype,hashtype>(hash,bins,reps,r); 86f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 87f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 88f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 89f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com bool result = true; 90f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 91f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double b = maxBias(bins,reps); 92f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 93f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf(" worst bias is %f%%",b * 100.0); 94f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 95f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(b > AVALANCHE_FAIL) 96f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 97f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf(" !!!!! "); 98f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com result = false; 99f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 100f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 101f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("\n"); 102f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 103f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return result; 104f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 105f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 106f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//---------------------------------------------------------------------------- 107f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Tests the Bit Independence Criteron. Stricter than Avalanche, but slow and 108f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// not really all that useful. 109f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 110f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtemplate< typename keytype, typename hashtype > 111f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid BicTest ( pfHash hash, const int keybit, const int reps, double & maxBias, int & maxA, int & maxB, bool verbose ) 112f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 113f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com Rand r(11938); 114f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 115f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybytes = sizeof(keytype); 116f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbytes = sizeof(hashtype); 117f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbits = hashbytes * 8; 118f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 119f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com std::vector<int> bins(hashbits*hashbits*4,0); 120f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 121f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com keytype key; 122f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hashtype h1,h2; 123f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 124f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int irep = 0; irep < reps; irep++) 125f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 126f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) 127f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 128f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(irep % (reps/10) == 0) printf("."); 129f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 130f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 131f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com r.rand_p(&key,keybytes); 132f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(&key,keybytes,0,&h1); 133f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 134f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com flipbit(key,keybit); 135f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(&key,keybytes,0,&h2); 136f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 137f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hashtype d = h1 ^ h2; 138f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 139f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out1 = 0; out1 < hashbits; out1++) 140f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out2 = 0; out2 < hashbits; out2++) 141f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 142f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(out1 == out2) continue; 143f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 144f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t b = getbit(d,out1) | (getbit(d,out2) << 1); 145f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 146f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com bins[(out1 * hashbits + out2) * 4 + b]++; 147f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 148f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 149f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 150f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) printf("\n"); 151f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 152f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxBias = 0; 153f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 154f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out1 = 0; out1 < hashbits; out1++) 155f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 156f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out2 = 0; out2 < hashbits; out2++) 157f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 158f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(out1 == out2) 159f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 160f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) printf("\\"); 161f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com continue; 162f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 163f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 164f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double bias = 0; 165f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 166f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int b = 0; b < 4; b++) 167f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 168f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double b2 = double(bins[(out1 * hashbits + out2) * 4 + b]) / double(reps / 2); 169f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com b2 = fabs(b2 * 2 - 1); 170f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 171f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(b2 > bias) bias = b2; 172f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 173f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 174f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(bias > maxBias) 175f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 176f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxBias = bias; 177f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxA = out1; 178f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxB = out2; 179f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 180f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 181f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) 182f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 183f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if (bias < 0.01) printf("."); 184f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else if(bias < 0.05) printf("o"); 185f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else if(bias < 0.33) printf("O"); 186f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else printf("X"); 187f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 188f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 189f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 190f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) printf("\n"); 191f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 192f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 193f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 194f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//---------- 195f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 196f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtemplate< typename keytype, typename hashtype > 197f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.combool BicTest ( pfHash hash, const int reps ) 198f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 199f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybytes = sizeof(keytype); 200f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybits = keybytes * 8; 201f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 202f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double maxBias = 0; 203f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int maxK = 0; 204f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int maxA = 0; 205f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int maxB = 0; 206f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 207f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 0; i < keybits; i++) 208f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 209f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(i % (keybits/10) == 0) printf("."); 210f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 211f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double bias; 212f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int a,b; 213f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 214f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com BicTest<keytype,hashtype>(hash,i,reps,bias,a,b,true); 215f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 216f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(bias > maxBias) 217f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 218f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxBias = bias; 219f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxK = i; 220f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxA = a; 221f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxB = b; 222f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 223f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 224f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 225f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Max bias %f - (%3d : %3d,%3d)\n",maxBias,maxK,maxA,maxB); 226f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 227f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Bit independence is harder to pass than avalanche, so we're a bit more lax here. 228f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 229f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com bool result = (maxBias < 0.05); 230f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 231f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return result; 232f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 233f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 234f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 235f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// BIC test variant - store all intermediate data in a table, draw diagram 236f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// afterwards (much faster) 237f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 238f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtemplate< typename keytype, typename hashtype > 239f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid BicTest3 ( pfHash hash, const int reps, bool verbose = true ) 240f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 241f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybytes = sizeof(keytype); 242f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybits = keybytes * 8; 243f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbytes = sizeof(hashtype); 244f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbits = hashbytes * 8; 245f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int pagesize = hashbits*hashbits*4; 246f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 247f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com Rand r(11938); 248f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 249f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double maxBias = 0; 250f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int maxK = 0; 251f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int maxA = 0; 252f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int maxB = 0; 253f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 254f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com keytype key; 255f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hashtype h1,h2; 256f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 257f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com std::vector<int> bins(keybits*pagesize,0); 258f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 259f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int keybit = 0; keybit < keybits; keybit++) 260f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 261f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(keybit % (keybits/10) == 0) printf("."); 262f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 263f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int * page = &bins[keybit*pagesize]; 264f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 265f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int irep = 0; irep < reps; irep++) 266f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 267f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com r.rand_p(&key,keybytes); 268f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(&key,keybytes,0,&h1); 269f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com flipbit(key,keybit); 270f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(&key,keybytes,0,&h2); 271f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 272f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hashtype d = h1 ^ h2; 273f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 274f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out1 = 0; out1 < hashbits-1; out1++) 275f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out2 = out1+1; out2 < hashbits; out2++) 276f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 277f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int * b = &page[(out1*hashbits+out2)*4]; 278f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 279f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t x = getbit(d,out1) | (getbit(d,out2) << 1); 280f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 281f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com b[x]++; 282f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 283f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 284f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 285f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 286f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("\n"); 287f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 288f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out1 = 0; out1 < hashbits-1; out1++) 289f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 290f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out2 = out1+1; out2 < hashbits; out2++) 291f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 292f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) printf("(%3d,%3d) - ",out1,out2); 293f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 294f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int keybit = 0; keybit < keybits; keybit++) 295f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 296f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int * page = &bins[keybit*pagesize]; 297f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int * bins = &page[(out1*hashbits+out2)*4]; 298f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 299f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double bias = 0; 300f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 301f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int b = 0; b < 4; b++) 302f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 303f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double b2 = double(bins[b]) / double(reps / 2); 304f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com b2 = fabs(b2 * 2 - 1); 305f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 306f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(b2 > bias) bias = b2; 307f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 308f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 309f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(bias > maxBias) 310f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 311f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxBias = bias; 312f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxK = keybit; 313f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxA = out1; 314f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxB = out2; 315f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 316f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 317f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) 318f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 319f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if (bias < 0.01) printf("."); 320f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else if(bias < 0.05) printf("o"); 321f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else if(bias < 0.33) printf("O"); 322f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else printf("X"); 323f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 324f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 325f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 326f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Finished keybit 327f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 328f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) printf("\n"); 329f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 330f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 331f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) 332f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 333f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 0; i < keybits+12; i++) printf("-"); 334f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("\n"); 335f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 336f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 337f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 338f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Max bias %f - (%3d : %3d,%3d)\n",maxBias,maxK,maxA,maxB); 339f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 340f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 341f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 342f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 343f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// BIC test variant - iterate over output bits, then key bits. No temp storage, 344f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// but slooooow 345f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 346f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtemplate< typename keytype, typename hashtype > 347f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid BicTest2 ( pfHash hash, const int reps, bool verbose = true ) 348f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 349f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybytes = sizeof(keytype); 350f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int keybits = keybytes * 8; 351f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbytes = sizeof(hashtype); 352f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbits = hashbytes * 8; 353f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 354f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com Rand r(11938); 355f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 356f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double maxBias = 0; 357f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int maxK = 0; 358f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int maxA = 0; 359f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int maxB = 0; 360f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 361f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com keytype key; 362f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hashtype h1,h2; 363f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 364f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out1 = 0; out1 < hashbits-1; out1++) 365f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int out2 = out1+1; out2 < hashbits; out2++) 366f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 367f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) printf("(%3d,%3d) - ",out1,out2); 368f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 369f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int keybit = 0; keybit < keybits; keybit++) 370f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 371f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int bins[4] = { 0, 0, 0, 0 }; 372f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 373f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int irep = 0; irep < reps; irep++) 374f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 375f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com r.rand_p(&key,keybytes); 376f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(&key,keybytes,0,&h1); 377f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com flipbit(key,keybit); 378f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hash(&key,keybytes,0,&h2); 379f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 380f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com hashtype d = h1 ^ h2; 381f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 382f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t b = getbit(d,out1) | (getbit(d,out2) << 1); 383f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 384f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com bins[b]++; 385f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 386f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 387f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double bias = 0; 388f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 389f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int b = 0; b < 4; b++) 390f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 391f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com double b2 = double(bins[b]) / double(reps / 2); 392f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com b2 = fabs(b2 * 2 - 1); 393f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 394f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(b2 > bias) bias = b2; 395f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 396f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 397f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(bias > maxBias) 398f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 399f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxBias = bias; 400f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxK = keybit; 401f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxA = out1; 402f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com maxB = out2; 403f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 404f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 405f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) 406f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 407f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if (bias < 0.05) printf("."); 408f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else if(bias < 0.10) printf("o"); 409f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else if(bias < 0.50) printf("O"); 410f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else printf("X"); 411f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 412f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 413f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 414f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Finished keybit 415f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 416f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(verbose) printf("\n"); 417f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 418f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 419f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com printf("Max bias %f - (%3d : %3d,%3d)\n",maxBias,maxK,maxA,maxB); 420f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 421f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 422f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 423