Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

375 lines (280 sloc) 6.865 kb
#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;
//-----------------------------------------------------------------------------
Jump to Line
Something went wrong with that request. Please try again.