Skip to content

Commit

Permalink
WIP wyhash update
Browse files Browse the repository at this point in the history 
which does not fix its bad static seeds
  • Loading branch information
@rurban
rurban committed Apr 2, 2022
1 parent 2be674e commit cff7c6b
Show file tree
Hide file tree
Showing 2 changed files with 12 additions and 48 deletions.
20 changes: 6 additions & 14 deletions main.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -809,16 +809,8 @@ void Seed_init (HashInfo* info, size_t seed) {
// Needed for hashed with a few bad seeds, to reject this seed and generate a new one.
// (GH #99)
void Bad_Seed_init (pfHash hash, uint32_t &seed) {
if(hash ==
#ifdef HAVE_BIT32
wyhash32_test
#else
wyhash32low
#endif
)
wyhash32_seed_init(seed);
// zero-seed hashes:
else if (!seed && (hash == BadHash || hash == sumhash || hash == fletcher2_test ||
if (!seed && (hash == BadHash || hash == sumhash || hash == fletcher2_test ||
hash == fletcher4_test || hash == Bernstein_test || hash == sdbm_test ||
hash == JenkinsOOAT_test || hash == JenkinsOOAT_perl_test ||
hash == SuperFastHash_test || hash == MurmurOAAT_test ||
Expand All @@ -837,11 +829,11 @@ void Bad_Seed_init (pfHash hash, uint32_t &seed) {
else if (hash == MurmurHash3_x86_128 && seed == 0x239b961b)
seed++;
#ifdef HAVE_INT64
else if(hash == wyhash_test) {
size_t seedl = seed;
wyhash_seed_init(seedl);
seed = seedl;
}
//else if(hash == wyhash_test) {
// size_t seedl = seed;
// wyhash_seed_init(seedl);
// seed = seedl;
//}
else if(hash == mirhash_test)
mirhash_seed_init(seed);
else if(hash == mirhash32low)
Expand Down
40 changes: 6 additions & 34 deletions wyhash.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -15,10 +15,6 @@
//protections that produce different results:
//1: normal valid behavior
//2: extra protection against entropy loss (probability=2^-63), aka. "blind multiplication"
// There are 2 known bad seeds for the 32bit and many for the 64bit variants.
// Recommended is just to skip or inc those known bad seeds, if you dont want to set WYHASH_CONDOM 2
// 32bit: 429dacdd, d637dbf3
// 64bit: *14cc886e, *1bf4ed84
#define WYHASH_CONDOM 1
#endif

Expand Down Expand Up @@ -118,19 +114,6 @@ static inline uint64_t _wyr4(const uint8_t *p) {
}
#endif
static inline uint64_t _wyr3(const uint8_t *p, size_t k) { return (((uint64_t)p[0])<<16)|(((uint64_t)p[k>>1])<<8)|p[k-1];}

#ifdef __cplusplus
// skip bad seeds with WYHASH_CONDOM 1
static void wyhash_seed_init(size_t &seed) {
if ((seed & 0x14cc886e) || (seed & 0xd637dbf3))
seed++;
}
static void wyhash32_seed_init(uint32_t &seed) {
if ((seed == 0x429dacdd) || (seed & 0xd637dbf3))
seed++;
}
#endif

//wyhash main function
static inline uint64_t wyhash(const void *key, size_t len, uint64_t seed, const uint64_t *secret){
const uint8_t *p=(const uint8_t *)key; seed^=*secret; uint64_t a, b;
Expand All @@ -156,14 +139,15 @@ static inline uint64_t wyhash(const void *key, size_t len, uint64_t seed, const
}
return _wymix(secret[1]^len,_wymix(a^secret[1],b^seed));
}

//the default secret parameters
static const uint64_t _wyp[4] = {0xa0761d6478bd642full, 0xe7037ed1a0b428dbull, 0x8ebc6af09c88c6e3ull, 0x589965cc75374cc3ull};

//a useful 64bit-64bit mix function to produce deterministic pseudo random numbers that can pass BigCrush and PractRand
static inline uint64_t wyhash64(uint64_t A, uint64_t B){ A^=_wyp[0]; B^=_wyp[1]; _wymum(&A,&B); return _wymix(A^_wyp[0],B^_wyp[1]);}
static inline uint64_t wyhash64(uint64_t A, uint64_t B){ A^=0xa0761d6478bd642full; B^=0xe7037ed1a0b428dbull; _wymum(&A,&B); return _wymix(A^0xa0761d6478bd642full,B^0xe7037ed1a0b428dbull);}

//The wyrand PRNG that pass BigCrush and PractRand
static inline uint64_t wyrand(uint64_t *seed){ *seed+=_wyp[0]; return _wymix(*seed,*seed^_wyp[1]);}
static inline uint64_t wyrand(uint64_t *seed){ *seed+=0xa0761d6478bd642full; return _wymix(*seed,*seed^0xe7037ed1a0b428dbull);}

//convert any 64 bit pseudo random numbers to uniform distribution [0,1). It can be combined with wyrand, wyhash64 or wyhash.
static inline double wy2u01(uint64_t r){ const double _wynorm=1.0/(1ull<<52); return (r>>12)*_wynorm;}
Expand Down Expand Up @@ -200,8 +184,6 @@ static inline void make_secret(uint64_t seed, uint64_t *secret){
if(x!=32){ ok=0; break; }
#endif
}
if(!ok)continue;
for(uint64_t j=3;j<0x100000000ull;j+=2) if(secret[i]%j==0){ ok=0; break; }
}while(!ok);
}
}
Expand Down Expand Up @@ -235,13 +217,13 @@ typedef uint32_t wyhashmap_t;
typedef uint64_t wyhashmap_t;
#endif

static inline size_t wyhashmap(wyhashmap_t *idx, size_t idx_size, const void *key, size_t key_size, uint8_t insert){
static inline size_t wyhashmap(wyhashmap_t *idx, size_t idx_size, const void *key, size_t key_size, uint8_t insert, uint64_t *secret){
size_t i=1; uint64_t h2; wyhashmap_t sig;
do{ sig=h2=wyhash(key,key_size,i,_wyp); i++; }while(_unlikely_(!sig));
do{ sig=h2=wyhash(key,key_size,i,secret); i++; }while(_unlikely_(!sig));
#ifdef WYHASHMAP_WEAK_SMALL_FAST
size_t i0=wy2u0k(h2,idx_size);
#else
size_t i0=wy2u0k(wyhash(key,key_size,0,_wyp),idx_size);
size_t i0=wy2u0k(wyhash(key,key_size,0,secret),idx_size);
#endif
for(i=i0; i<idx_size&&idx[i]&&idx[i]!=sig; i++);
if(_unlikely_(i==idx_size)){
Expand All @@ -256,16 +238,6 @@ static inline size_t wyhashmap(wyhashmap_t *idx, size_t idx_size, const void *ke
}
#endif

/* test vectors for portability test
wyhash("",0)=42bc986dc5eec4d3
wyhash("a",1)=84508dc903c31551
wyhash("abc",2)=bc54887cfc9ecb1
wyhash("message digest",3)=6e2ff3298208a67c
wyhash("abcdefghijklmnopqrstuvwxyz",4)=9a64e42e897195b9
wyhash("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",5)=9199383239c32554
wyhash("12345678901234567890123456789012345678901234567890123456789012345678901234567890",6)=7c1ccf6bba30f5a5
*/

/* The Unlicense
This is free and unencumbered software released into the public domain.
Expand Down

0 comments on commit cff7c6b

Please sign in to comment.