Find file
Fetching contributors…
Cannot retrieve contributors at this time
440 lines (293 sloc) 10.4 KB
//-----------------------------------------------------------------------------
// Keyset tests generate various sorts of difficult-to-hash keysets and compare
// the distribution and collision frequency of the hash results against an
// ideal random distribution
// The sanity checks are also in this cpp/h
#pragma once
#include "Types.h"
#include "Stats.h"
#include "Random.h" // for rand_p
#include <algorithm> // for std::swap
#include <assert.h>
//-----------------------------------------------------------------------------
// Sanity tests
bool VerificationTest ( pfHash hash, const int hashbits, uint32_t expected, bool verbose );
bool SanityTest ( pfHash hash, const int hashbits );
void AppendedZeroesTest ( pfHash hash, const int hashbits );
//-----------------------------------------------------------------------------
// Keyset 'Combination' - all possible combinations of input blocks
template< typename hashtype >
void CombinationKeygenRecurse ( uint32_t * key, int len, int maxlen,
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);
}
}
}
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);
//----------
std::vector<hashtype> hashes;
uint32_t * key = new uint32_t[maxlen];
CombinationKeygenRecurse<hashtype>(key,0,maxlen,blocks,blockcount,hash,hashes);
delete [] key;
printf("%d keys\n",(int)hashes.size());
//----------
bool result = true;
result &= TestHashList<hashtype>(hashes,testColl,testDist,drawDiagram);
printf("\n");
return result;
}
//----------------------------------------------------------------------------
// Keyset 'Permutation' - given a set of 32-bit blocks, generate keys
// consisting of all possible permutations of those 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;
hash(blocks,blockcount * sizeof(uint32_t),0,&h);
hashes.push_back(h);
return;
}
for(int i = k; i < blockcount; i++)
{
std::swap(blocks[k],blocks[i]);
PermutationKeygenRecurse(hash,blocks,blockcount,k+1,hashes);
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);
//----------
std::vector<hashtype> hashes;
PermutationKeygenRecurse<hashtype>(hash,blocks,blockcount,0,hashes);
printf("%d keys\n",(int)hashes.size());
//----------
bool result = true;
result &= TestHashList<hashtype>(hashes,testColl,testDist,drawDiagram);
printf("\n");
return result;
}
//-----------------------------------------------------------------------------
// Keyset 'Sparse' - generate all possible N-bit keys with up to K bits set
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;
hashtype h;
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(bitsleft > 1)
{
SparseKeygenRecurse(hash,i+1,bitsleft-1,inclusive,k,hashes);
}
flipbit(&k,nbytes,i);
}
}
//----------
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);
typedef Blob<keybits> keytype;
std::vector<hashtype> hashes;
keytype k;
memset(&k,0,sizeof(k));
if(inclusive)
{
hashtype h;
hash(&k,sizeof(keytype),0,&h);
hashes.push_back(h);
}
SparseKeygenRecurse(hash,0,setbits,inclusive,k,hashes);
printf("%d keys\n",(int)hashes.size());
bool result = true;
result &= TestHashList<hashtype>(hashes,testColl,testDist,drawDiagram);
printf("\n");
return result;
}
//-----------------------------------------------------------------------------
// Keyset 'Windows' - for all possible N-bit windows of a K-bit key, generate
// all possible keys with bits set in that window
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;
std::vector<hashtype> hashes;
hashes.resize(keycount);
bool result = true;
int testcount = keybits;
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;
keytype key;
for(int i = 0; i < keycount; i++)
{
key = i;
//key = key << minbit;
lrot(&key,sizeof(keytype),minbit);
hash(&key,sizeof(keytype),0,&hashes[i]);
}
printf("Window at %3d - ",j);
result &= TestHashList(hashes,testCollision,testDistribution,drawDiagram);
//printf("\n");
}
return result;
}
//-----------------------------------------------------------------------------
// Keyset 'Cyclic' - generate keys that consist solely of N repetitions of M
// bytes.
// (This keyset type is designed to make MurmurHash2 fail)
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);
Rand r(483723);
std::vector<hashtype> hashes;
hashes.resize(keycount);
int keyLen = cycleLen * cycleReps;
uint8_t * cycle = new uint8_t[cycleLen + 16];
uint8_t * key = new uint8_t[keyLen];
//----------
for(int i = 0; i < keycount; i++)
{
r.rand_p(cycle,cycleLen);
*(uint32_t*)cycle = f3mix(i ^ 0x746a94f1);
for(int j = 0; j < keyLen; j++)
{
key[j] = cycle[j % cycleLen];
}
hash(key,keyLen,0,&hashes[i]);
}
//----------
bool result = true;
result &= TestHashList(hashes,true,true,drawDiagram);
printf("\n");
delete [] cycle;
delete [] key;
return result;
}
//-----------------------------------------------------------------------------
// Keyset 'TwoBytes' - generate all keys up to length N with two non-zero bytes
void TwoBytesKeygen ( int maxlen, KeyCallback & c );
template < typename hashtype >
bool TwoBytesTest2 ( pfHash hash, int maxlen, bool drawDiagram )
{
std::vector<hashtype> hashes;
HashCallback<hashtype> c(hash,hashes);
TwoBytesKeygen(maxlen,c);
bool result = true;
result &= TestHashList(hashes,true,true,drawDiagram);
printf("\n");
return result;
}
//-----------------------------------------------------------------------------
// Keyset 'Text' - generate all keys of the form "prefix"+"core"+"suffix",
// where "core" consists of all possible combinations of the given character
// set of length N.
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 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);
uint8_t * key = new uint8_t[keybytes+1];
key[keybytes] = 0;
memcpy(key,prefix,prefixlen);
memcpy(key+prefixlen+corelen,suffix,suffixlen);
//----------
std::vector<hashtype> hashes;
hashes.resize(keycount);
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;
}
hash(key,keybytes,0,&hashes[i]);
}
//----------
bool result = true;
result &= TestHashList(hashes,true,true,drawDiagram);
printf("\n");
delete [] key;
return result;
}
//-----------------------------------------------------------------------------
// Keyset 'Zeroes' - keys consisting of all zeroes, differing only in length
// We reuse one block of empty bytes, otherwise the RAM cost is enormous.
template < typename hashtype >
bool ZeroKeyTest ( pfHash hash, bool drawDiagram )
{
int keycount = 64*1024;
printf("Keyset 'Zeroes' - %d keys\n",keycount);
unsigned char * nullblock = new unsigned char[keycount];
memset(nullblock,0,keycount);
//----------
std::vector<hashtype> hashes;
hashes.resize(keycount);
for(int i = 0; i < keycount; i++)
{
hash(nullblock,i,0,&hashes[i]);
}
bool result = true;
result &= TestHashList(hashes,true,true,drawDiagram);
printf("\n");
delete [] nullblock;
return result;
}
//-----------------------------------------------------------------------------
// Keyset 'Seed' - hash "the quick brown fox..." using different seeds
template < typename hashtype >
bool SeedTest ( pfHash hash, int keycount, bool drawDiagram )
{
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);
//----------
std::vector<hashtype> hashes;
hashes.resize(keycount);
for(int i = 0; i < keycount; i++)
{
hash(text,len,i,&hashes[i]);
}
bool result = true;
result &= TestHashList(hashes,true,true,drawDiagram);
printf("\n");
return result;
}
//-----------------------------------------------------------------------------