#pragma once | |
#include "Platform.h" | |
#include "Bitvec.h" | |
#include <memory.h> | |
#include <vector> | |
#include <map> | |
#include <set> | |
//----------------------------------------------------------------------------- | |
// If the optimizer detects that a value in a speed test is constant or unused, | |
// the optimizer may remove references to it or otherwise create code that | |
// would not occur in a real-world application. To prevent the optimizer from | |
// doing this we declare two trivial functions that either sink or source data, | |
// and bar the compiler from optimizing them. | |
void blackhole ( uint32_t x ); | |
uint32_t whitehole ( void ); | |
//----------------------------------------------------------------------------- | |
// We want to verify that every test produces the same result on every platform | |
// To do this, we hash the results of every test to produce an overall | |
// verification value for the whole test suite. If two runs produce the same | |
// verification value, then every test in both run produced the same results | |
extern uint32_t g_verify; | |
// Mix the given blob of data into the verification code | |
void MixVCode ( const void * blob, int len ); | |
//----------------------------------------------------------------------------- | |
typedef void (*pfHash) ( const void * blob, const int len, const uint32_t seed, void * out ); | |
struct ByteVec : public std::vector<uint8_t> | |
{ | |
ByteVec ( const void * key, int len ) | |
{ | |
resize(len); | |
memcpy(&front(),key,len); | |
} | |
}; | |
template< typename hashtype, typename keytype > | |
struct CollisionMap : public std::map< hashtype, std::vector<keytype> > | |
{ | |
}; | |
template< typename hashtype > | |
struct HashSet : public std::set<hashtype> | |
{ | |
}; | |
//----------------------------------------------------------------------------- | |
template < class T > | |
class hashfunc | |
{ | |
public: | |
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 operator pfHash ( void ) const | |
{ | |
return m_hash; | |
} | |
inline T operator () ( const void * key, const int len, const uint32_t seed ) | |
{ | |
T result; | |
m_hash(key,len,seed,(uint32_t*)&result); | |
return result; | |
} | |
pfHash m_hash; | |
}; | |
//----------------------------------------------------------------------------- | |
// Key-processing callback objects. Simplifies keyset testing a bit. | |
struct KeyCallback | |
{ | |
KeyCallback() : m_count(0) | |
{ | |
} | |
virtual ~KeyCallback() | |
{ | |
} | |
virtual void operator() ( const void * key, int len ) | |
{ | |
m_count++; | |
} | |
virtual void reserve ( int keycount ) | |
{ | |
}; | |
int m_count; | |
}; | |
//---------- | |
template<typename hashtype> | |
struct HashCallback : public KeyCallback | |
{ | |
typedef std::vector<hashtype> hashvec; | |
HashCallback ( pfHash hash, hashvec & hashes ) : m_hashes(hashes), m_pfHash(hash) | |
{ | |
m_hashes.clear(); | |
} | |
virtual void operator () ( const void * key, int len ) | |
{ | |
size_t newsize = m_hashes.size() + 1; | |
m_hashes.resize(newsize); | |
m_pfHash(key,len,0,&m_hashes.back()); | |
} | |
virtual void reserve ( int keycount ) | |
{ | |
m_hashes.reserve(keycount); | |
} | |
hashvec & m_hashes; | |
pfHash m_pfHash; | |
//---------- | |
private: | |
HashCallback & operator = ( const HashCallback & ); | |
}; | |
//---------- | |
template<typename hashtype> | |
struct CollisionCallback : public KeyCallback | |
{ | |
typedef HashSet<hashtype> hashset; | |
typedef CollisionMap<hashtype,ByteVec> collmap; | |
CollisionCallback ( pfHash hash, hashset & collisions, collmap & cmap ) | |
: m_pfHash(hash), | |
m_collisions(collisions), | |
m_collmap(cmap) | |
{ | |
} | |
virtual void operator () ( const void * key, int len ) | |
{ | |
hashtype h; | |
m_pfHash(key,len,0,&h); | |
if(m_collisions.count(h)) | |
{ | |
m_collmap[h].push_back( ByteVec(key,len) ); | |
} | |
} | |
//---------- | |
pfHash m_pfHash; | |
hashset & m_collisions; | |
collmap & m_collmap; | |
private: | |
CollisionCallback & operator = ( const CollisionCallback & c ); | |
}; | |
//----------------------------------------------------------------------------- | |
template < int _bits > | |
class Blob | |
{ | |
public: | |
Blob() | |
{ | |
for(size_t i = 0; i < sizeof(bytes); i++) | |
{ | |
bytes[i] = 0; | |
} | |
} | |
Blob ( int x ) | |
{ | |
for(size_t i = 0; i < sizeof(bytes); i++) | |
{ | |
bytes[i] = 0; | |
} | |
*(int*)bytes = x; | |
} | |
Blob ( const Blob & k ) | |
{ | |
for(size_t i = 0; i < sizeof(bytes); i++) | |
{ | |
bytes[i] = k.bytes[i]; | |
} | |
} | |
Blob & operator = ( const Blob & k ) | |
{ | |
for(size_t i = 0; i < sizeof(bytes); i++) | |
{ | |
bytes[i] = k.bytes[i]; | |
} | |
return *this; | |
} | |
Blob ( uint64_t a, uint64_t b ) | |
{ | |
uint64_t t[2] = {a,b}; | |
set(&t,16); | |
} | |
void set ( const void * blob, size_t len ) | |
{ | |
const uint8_t * k = (const uint8_t*)blob; | |
len = len > sizeof(bytes) ? sizeof(bytes) : len; | |
for(size_t i = 0; i < len; i++) | |
{ | |
bytes[i] = k[i]; | |
} | |
for(size_t i = len; i < sizeof(bytes); 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(size_t i = 0; i < sizeof(bytes); 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(size_t i = 0; i < sizeof(bytes); 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(size_t i = 0; i < sizeof(bytes); i++) | |
{ | |
t.bytes[i] = bytes[i] ^ k.bytes[i]; | |
} | |
return t; | |
} | |
Blob & operator ^= ( const Blob & k ) | |
{ | |
for(size_t i = 0; i < sizeof(bytes); i++) | |
{ | |
bytes[i] ^= k.bytes[i]; | |
} | |
return *this; | |
} | |
int operator & ( int x ) | |
{ | |
return (*(int*)bytes) & x; | |
} | |
Blob & operator &= ( const Blob & k ) | |
{ | |
for(size_t i = 0; i < sizeof(bytes); i++) | |
{ | |
bytes[i] &= k.bytes[i]; | |
} | |
} | |
Blob operator << ( int c ) | |
{ | |
Blob t = *this; | |
lshift(&t.bytes[0],sizeof(bytes),c); | |
return t; | |
} | |
Blob operator >> ( int c ) | |
{ | |
Blob t = *this; | |
rshift(&t.bytes[0],sizeof(bytes),c); | |
return t; | |
} | |
Blob & operator <<= ( int c ) | |
{ | |
lshift(&bytes[0],sizeof(bytes),c); | |
return *this; | |
} | |
Blob & operator >>= ( int c ) | |
{ | |
rshift(&bytes[0],sizeof(bytes),c); | |
return *this; | |
} | |
//---------- | |
private: | |
uint8_t bytes[(_bits+7)/8]; | |
}; | |
typedef Blob<128> uint128_t; | |
typedef Blob<256> uint256_t; | |
//----------------------------------------------------------------------------- |