// This is free and unencumbered software released into the public domain under The Unlicense (http://unlicense.org/)

// main repo: https://github.com/wangyi-fudan/wyhash

// author: 王一 Wang Yi <godspeed_china@yeah.net>

// contributors: Reini Urban, Dietrich Epp, Joshua Haberman, Tommy Ettinger, Daniel Lemire, Otmar Ertl, cocowalla, leo-yuriev, Diego Barrios Romero, paulie-g, dumblob, Yann Collet, ivte-ms, hyb, James Z.M. Gao, easyaspi314 (Devin), TheOneric

/* quick example:

   string s="fjsakfdsjkf";

   uint64_t hash=wyhash(s.c_str(), s.size(), 0, _wyp);

*/

#ifndef wyhash_final_version_3

#define wyhash_final_version_3

#ifndef WYHASH_CONDOM

//protections that produce different results:

//1: normal valid behavior

//2: extra protection against entropy loss (probability=2^-63), aka. "blind multiplication"

#define WYHASH_CONDOM 1

#endif

#ifndef WYHASH_32BIT_MUM

//0: normal version, slow on 32 bit systems

//1: faster on 32 bit systems but produces different results, incompatible with wy2u0k function

#define WYHASH_32BIT_MUM 0  

#endif

//includes

#include <stdint.h>

#include <string.h>

#if defined(_MSC_VER) && defined(_M_X64)

  #include <intrin.h>

  #pragma intrinsic(_umul128)

#endif

//likely and unlikely macros

#if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)

  #define _likely_(x)  __builtin_expect(x,1)

  #define _unlikely_(x)  __builtin_expect(x,0)

#else

  #define _likely_(x) (x)

  #define _unlikely_(x) (x)

#endif

//128bit multiply function

static inline uint64_t _wyrot(uint64_t x) { return (x>>32)|(x<<32); }

static inline void _wymum(uint64_t *A, uint64_t *B){

#if(WYHASH_32BIT_MUM)

  uint64_t hh=(*A>>32)*(*B>>32), hl=(*A>>32)*(uint32_t)*B, lh=(uint32_t)*A*(*B>>32), ll=(uint64_t)(uint32_t)*A*(uint32_t)*B;

  #if(WYHASH_CONDOM>1)

  *A^=_wyrot(hl)^hh; *B^=_wyrot(lh)^ll;

  #else

  *A=_wyrot(hl)^hh; *B=_wyrot(lh)^ll;

  #endif

#elif defined(__SIZEOF_INT128__)

  __uint128_t r=*A; r*=*B; 

  #if(WYHASH_CONDOM>1)

  *A^=(uint64_t)r; *B^=(uint64_t)(r>>64);

  #else

  *A=(uint64_t)r; *B=(uint64_t)(r>>64);

  #endif

#elif defined(_MSC_VER) && defined(_M_X64)

  #if(WYHASH_CONDOM>1)

  uint64_t  a,  b;

  a=_umul128(*A,*B,&b);

  *A^=a;  *B^=b;

  #else

  *A=_umul128(*A,*B,B);

  #endif

#else

  uint64_t ha=*A>>32, hb=*B>>32, la=(uint32_t)*A, lb=(uint32_t)*B, hi, lo;

  uint64_t rh=ha*hb, rm0=ha*lb, rm1=hb*la, rl=la*lb, t=rl+(rm0<<32), c=t<rl;

  lo=t+(rm1<<32); c+=lo<t; hi=rh+(rm0>>32)+(rm1>>32)+c;

  #if(WYHASH_CONDOM>1)

  *A^=lo;  *B^=hi;

  #else

  *A=lo;  *B=hi;

  #endif

#endif

}

//multiply and xor mix function, aka MUM

static inline uint64_t _wymix(uint64_t A, uint64_t B){ _wymum(&A,&B); return A^B; }

//endian macros

#ifndef WYHASH_LITTLE_ENDIAN

  #if defined(_WIN32) || defined(__LITTLE_ENDIAN__) || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)

    #define WYHASH_LITTLE_ENDIAN 1

  #elif defined(__BIG_ENDIAN__) || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)

    #define WYHASH_LITTLE_ENDIAN 0

  #else

    #warning could not determine endianness! Falling back to little endian.

    #define WYHASH_LITTLE_ENDIAN 1

  #endif

#endif

//read functions

#if (WYHASH_LITTLE_ENDIAN)

static inline uint64_t _wyr8(const uint8_t *p) { uint64_t v; memcpy(&v, p, 8); return v;}

static inline uint64_t _wyr4(const uint8_t *p) { uint32_t v; memcpy(&v, p, 4); return v;}

#elif defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)

static inline uint64_t _wyr8(const uint8_t *p) { uint64_t v; memcpy(&v, p, 8); return __builtin_bswap64(v);}

static inline uint64_t _wyr4(const uint8_t *p) { uint32_t v; memcpy(&v, p, 4); return __builtin_bswap32(v);}

#elif defined(_MSC_VER)

static inline uint64_t _wyr8(const uint8_t *p) { uint64_t v; memcpy(&v, p, 8); return _byteswap_uint64(v);}

static inline uint64_t _wyr4(const uint8_t *p) { uint32_t v; memcpy(&v, p, 4); return _byteswap_ulong(v);}

#else

static inline uint64_t _wyr8(const uint8_t *p) {

  uint64_t v; memcpy(&v, p, 8);

  return (((v >> 56) & 0xff)| ((v >> 40) & 0xff00)| ((v >> 24) & 0xff0000)| ((v >>  8) & 0xff000000)| ((v <<  8) & 0xff00000000)| ((v << 24) & 0xff0000000000)| ((v << 40) & 0xff000000000000)| ((v << 56) & 0xff00000000000000));

}

static inline uint64_t _wyr4(const uint8_t *p) {

  uint32_t v; memcpy(&v, p, 4);

  return (((v >> 24) & 0xff)| ((v >>  8) & 0xff00)| ((v <<  8) & 0xff0000)| ((v << 24) & 0xff000000));

}

#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];}

//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;

  if(_likely_(len<=16)){

    if(_likely_(len>=4)){ a=(_wyr4(p)<<32)|_wyr4(p+((len>>3)<<2)); b=(_wyr4(p+len-4)<<32)|_wyr4(p+len-4-((len>>3)<<2)); }

    else if(_likely_(len>0)){ a=_wyr3(p,len); b=0;}

    else a=b=0;

  }

  else{

    size_t i=len; 

    if(_unlikely_(i>48)){

      uint64_t see1=seed, see2=seed;

      do{

        seed=_wymix(_wyr8(p)^secret[1],_wyr8(p+8)^seed);

        see1=_wymix(_wyr8(p+16)^secret[2],_wyr8(p+24)^see1);

        see2=_wymix(_wyr8(p+32)^secret[3],_wyr8(p+40)^see2);

        p+=48; i-=48;

      }while(_likely_(i>48));

      seed^=see1^see2;

    }

    while(_unlikely_(i>16)){  seed=_wymix(_wyr8(p)^secret[1],_wyr8(p+8)^seed);  i-=16; p+=16;  }

    a=_wyr8(p+i-16);  b=_wyr8(p+i-8);

  }

  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^=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+=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;}

//convert any 64 bit pseudo random numbers to APPROXIMATE Gaussian distribution. It can be combined with wyrand, wyhash64 or wyhash.

static inline double wy2gau(uint64_t r){ const double _wynorm=1.0/(1ull<<20); return ((r&0x1fffff)+((r>>21)&0x1fffff)+((r>>42)&0x1fffff))*_wynorm-3.0;}

#if(!WYHASH_32BIT_MUM)

//fast range integer random number generation on [0,k) credit to Daniel Lemire. May not work when WYHASH_32BIT_MUM=1. It can be combined with wyrand, wyhash64 or wyhash.

static inline uint64_t wy2u0k(uint64_t r, uint64_t k){ _wymum(&r,&k); return k; }

#endif

//make your own secret

static inline void make_secret(uint64_t seed, uint64_t *secret){

  uint8_t c[] = {15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240 };

  for(size_t i=0;i<4;i++){

    uint8_t ok;

    do{

      ok=1; secret[i]=0;

      for(size_t j=0;j<64;j+=8) secret[i]|=((uint64_t)c[wyrand(&seed)%sizeof(c)])<<j;

      if(secret[i]%2==0){ ok=0; continue; }

      for(size_t j=0;j<i;j++) {

#if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)

        if(__builtin_popcountll(secret[j]^secret[i])!=32){ ok=0; break; }

#elif defined(_MSC_VER) && defined(_M_X64)

        if(_mm_popcnt_u64(secret[j]^secret[i])!=32){ ok=0; break; }

#else

        //manual popcount

        uint64_t x = secret[j]^secret[i];

        x -= (x >> 1) & 0x5555555555555555;

        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;

        x = (x * 0x0101010101010101) >> 56;

        if(x!=32){ ok=0; break; }

#endif

      }

    }while(!ok);

  }

}

/*  This is world's fastest hash map: 2x faster than bytell_hash_map.

    It does not store the keys, but only the hash/signature of keys.

    First we use pos=hash1(key) to approximately locate the bucket.

    Then we search signature=hash2(key) from pos linearly.

    If we find a bucket with matched signature we report the bucket

    Or if we meet a bucket whose signature=0, we report a new position to insert

    The signature collision probability is very low as we usually searched N~10 buckets.

    By combining hash1 and hash2, we acturally have 128 bit anti-collision strength.

    hash1 and hash2 can be the same function, resulting lower collision resistance but faster.

    The signature is 64 bit, but can be modified to 32 bit if necessary for save space.

    The above two can be activated by define WYHASHMAP_WEAK_SMALL_FAST

    simple examples:

    const size_t  size=213432;

    vector<wyhashmap_t> idx(size);  //  allocate the index of fixed size. idx MUST be zeroed.

    vector<value_class> value(size);  //  we only care about the index, user should maintain his own value vectors.

    string  key="dhskfhdsj" //  the object to be inserted into idx

    size_t  pos=wyhashmap(idx.data(), idx.size(), key.c_str(), key.size(), 1);  //  get the position and insert

    if(pos<size)  value[pos]++; //  we process the vallue

    else  cerr<<"map is full\n";

    pos=wyhashmap(idx.data(), idx.size(), key.c_str(), key.size(), 0);  // just lookup by setting insert=0

    if(pos<size)  value[pos]++; //  we process the vallue

    else  cerr<<"the key does not exist\n";

*/

/*

#ifdef  WYHASHMAP_WEAK_SMALL_FAST // for small hashmaps whose size < 2^24 and acceptable collision

typedef uint32_t  wyhashmap_t;

#else

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, uint64_t *secret){

  size_t  i=1;  uint64_t  h2; wyhashmap_t 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,secret),idx_size);

#endif

  for(i=i0; i<idx_size&&idx[i]&&idx[i]!=sig;  i++);

  if(_unlikely_(i==idx_size)){

    for(i=0;  i<i0&&idx[i]&&idx[i]!=sig;  i++);

    if(i==i0) return  idx_size;

  }

  if(!idx[i]){

    if(insert)  idx[i]=sig;

    else  return  idx_size;

  }

  return  i;

}

*/

#endif

/* The Unlicense

This is free and unencumbered software released into the public domain.

Anyone is free to copy, modify, publish, use, compile, sell, or

distribute this software, either in source code form or as a compiled

binary, for any purpose, commercial or non-commercial, and by any

means.

In jurisdictions that recognize copyright laws, the author or authors

of this software dedicate any and all copyright interest in the

software to the public domain. We make this dedication for the benefit

of the public at large and to the detriment of our heirs and

successors. We intend this dedication to be an overt act of

relinquishment in perpetuity of all present and future rights to this

software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF

MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.

IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR

OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,

ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

OTHER DEALINGS IN THE SOFTWARE.

For more information, please refer to <http://unlicense.org/>

*/