randomhash.hh

Go to the documentation of this file.

 // This Source Code Form is licensed MPL-2.0: http://mozilla.org/MPL/2.0
// Author: 2014, Tim Janik, see http://testbit.eu/
#ifndef __ASE_RANDOMHASH_HH__
#define __ASE_RANDOMHASH_HH__
 
#include <ase/cxxaux.hh>
 
namespace Ase {
 
template<size_t SIZE>
struct alignas (16) AlignedPOD {
  typename std::aligned_storage<SIZE, 16>::type mem;
  /* malloc() aligns to 2 * sizeof (size_t), i.e. 16 on 64bit, max_align_t is
   * usually aligned to long double, i.e. 16, and most SIMD code also needs at
   * least 16 byte alignment.
   */
};
 
// == Random Numbers ==
uint64_t        random_nonce    ();
uint64_t        random_int64    ();
int64_t         random_irange   (int64_t begin, int64_t end);
double          random_float    ();
double          random_frange   (double begin, double end);
void            random_secret   (uint64_t *secret_var);
 
// == FastRNG ==
class Mwc256 {
  // Based on https://prng.di.unimi.it/MWC256.c
  uint64_t state alignas (64) [4];
public:
  static constexpr uint64_t MWC_A3 = 0xff377e26f82da74a;
  Mwc256   clone192  ();
  Mwc256   clone128  ();
  uint64_t next      ();
  void     seed      ();
  void     seed      (uint64_t x, uint64_t y = 0, uint64_t z = 0, uint64_t c = 1);
  explicit Mwc256    (uint64_t x, uint64_t y = 0, uint64_t z = 0, uint64_t c = 1);
  explicit Mwc256    ();
  /*copy*/ Mwc256    (const Mwc256&) = default;
  Mwc256&  operator= (const Mwc256&) = default;
};
 
inline uint64_t
Mwc256::next()
{
  const __uint128_t t = MWC_A3 * __uint128_t (state[0]) + state[3];
  state[0] = state[1];
  state[1] = state[2];
  state[3] = t >> 64;
  return state[2] = t;
}
 
using FastRng = Mwc256;
 
// == Hashing ==
struct SHA3_224 {
  /*dtor*/ ~SHA3_224    ();
  /*ctor*/  SHA3_224    ();         
  void      reset       ();         
  void      update      (const uint8_t *data, size_t length);   
  void      digest      (uint8_t hashvalue[28]);                
  void      update      (const String &s) { update ((const uint8_t*) &s[0], s.size()); }
private:
  AlignedPOD<232> mem_;
  struct    State;
  State    *state_;
};
void    sha3_224_hash   (const void *data, size_t data_length, uint8_t hashvalue[28]);
 
struct SHA3_256 {
  /*dtor*/ ~SHA3_256    ();
  /*ctor*/  SHA3_256    ();         
  void      reset       ();         
  void      update      (const uint8_t *data, size_t length);   
  void      digest      (uint8_t hashvalue[32]);                
  void      update      (const String &s) { update ((const uint8_t*) &s[0], s.size()); }
private:
  AlignedPOD<232> mem_;
  struct    State;
  State    *state_;
};
void    sha3_256_hash   (const void *data, size_t data_length, uint8_t hashvalue[32]);
 
struct SHA3_384 {
  /*dtor*/ ~SHA3_384    ();
  /*ctor*/  SHA3_384    ();         
  void      reset       ();         
  void      update      (const uint8_t *data, size_t length);   
  void      digest      (uint8_t hashvalue[48]);                
  void      update      (const String &s) { update ((const uint8_t*) &s[0], s.size()); }
private:
  AlignedPOD<232> mem_;
  struct    State;
  State    *state_;
};
void    sha3_384_hash   (const void *data, size_t data_length, uint8_t hashvalue[48]);
 
struct SHA3_512 {
  /*dtor*/ ~SHA3_512    ();
  /*ctor*/  SHA3_512    ();         
  void      reset       ();         
  void      update      (const uint8_t *data, size_t length);   
  void      digest      (uint8_t hashvalue[64]);                
  void      update      (const String &s) { update ((const uint8_t*) &s[0], s.size()); }
private:
  AlignedPOD<232> mem_;
  struct    State;
  State    *state_;
};
void    sha3_512_hash   (const void *data, size_t data_length, uint8_t hashvalue[64]);
 
struct SHAKE128 {
  /*dtor*/ ~SHAKE128        ();
  /*ctor*/  SHAKE128        ();         
  void      reset           ();         
  void      update          (const uint8_t *data, size_t length);   
  void      squeeze_digest  (uint8_t *hashvalues, size_t n);        
  void      update          (const String &s) { update ((const uint8_t*) &s[0], s.size()); }
private:
  AlignedPOD<232> mem_;
  struct    State;
  State    *state_;
};
void    shake128_hash   (const void *data, size_t data_length, uint8_t *hashvalues, size_t n);
 
struct SHAKE256 {
  /*dtor*/ ~SHAKE256        ();
  /*ctor*/  SHAKE256        ();         
  void      reset           ();         
  void      update          (const uint8_t *data, size_t length);   
  void      squeeze_digest  (uint8_t *hashvalues, size_t n);        
  void      update          (const String &s) { update ((const uint8_t*) &s[0], s.size()); }
private:
  AlignedPOD<232> mem_;
  struct    State;
  State    *state_;
};
void    shake256_hash   (const void *data, size_t data_length, uint8_t *hashvalues, size_t n);
 
namespace Lib { // Namespace for implementation internals
 
class KeccakF1600 {
  union alignas (2 * sizeof (uint64_t))
  {
    uint64_t            A[25];
    uint8_t             bytes[200];
    // __MMX__: __m64   V[25];
  };
public:
  explicit      KeccakF1600 ();                         
  void          reset       ();                         
  uint64_t&     operator[]  (int      index)       { return A[index]; }
  uint64_t      operator[]  (int      index) const { return A[index]; }
  void          permute     (uint32_t n_rounds);        
  inline uint8_t&
  byte (size_t state_index)                             
  {
#if   __BYTE_ORDER == __LITTLE_ENDIAN
    return bytes[(state_index / 8) * 8 + (state_index % 8)];            // 8 == sizeof (uint64_t)
#elif __BYTE_ORDER == __BIG_ENDIAN
    return bytes[(state_index / 8) * 8 + (8 - 1 - (state_index % 8))];  // 8 == sizeof (uint64_t)
#else
#   error "Unknown __BYTE_ORDER"
#endif
  }
};
 
} // Lib
 
class AutoSeeder {
public:
  static uint64   random     ()       { return random_int64(); }
  uint64          operator() () const { return this->random(); }
  template<typename RandomAccessIterator> void
  generate (RandomAccessIterator begin, RandomAccessIterator end)
  {
    typedef typename std::iterator_traits<RandomAccessIterator>::value_type Value;
    while (begin != end)
      {
        const uint64_t rbits = operator()();
        *begin++ = Value (rbits);
        if (sizeof (Value) <= 4 && begin != end)
          *begin++ = Value (rbits >> 32);
      }
  }
};
 
class KeccakRng {
  const uint16_t      bit_rate_, n_rounds_;
  uint32_t            opos_;
  Lib::KeccakF1600    state_;
  void                permute1600();
public:
  /*copy*/            KeccakRng  (const KeccakRng&) = default;
  typedef uint64_t    result_type;
  inline size_t       n_nums() const            { return bit_rate_ / 64; }
  inline size_t       bit_capacity() const      { return 1600 - bit_rate_; }
  /*dtor*/           ~KeccakRng  ();
  explicit
  KeccakRng (uint16_t hidden_state_capacity, uint16_t n_rounds) :
    bit_rate_ (1600 - hidden_state_capacity), n_rounds_ (n_rounds), opos_ (n_nums())
  {
    ASE_ASSERT_RETURN (hidden_state_capacity > 0 && hidden_state_capacity <= 1600 - 64);
    ASE_ASSERT_RETURN (64 * (hidden_state_capacity / 64) == hidden_state_capacity); // capacity must be 64bit aligned
    ASE_ASSERT_RETURN (n_rounds > 0 && n_rounds < 255);                             // see KECCAK_ROUND_CONSTANTS access
  }
  void forget   ();
  void discard  (unsigned long long count);
  void xor_seed (const uint64_t *seeds, size_t n_seeds);
  void seed     (uint64_t seed_value = 1)               { seed (&seed_value, 1); }
  void
  seed (const uint64_t *seeds, size_t n_seeds)
  {
    state_.reset();
    xor_seed (seeds, n_seeds);
  }
  template<class SeedSeq> void
  seed (SeedSeq &seed_sequence)
  {
    uint32_t u32[50];                   // fill 50 * 32 = 1600 state bits
    seed_sequence.generate (&u32[0], &u32[50]);
    uint64_t u64[25];
    for (size_t i = 0; i < 25; i++)     // Keccak bit order: 1) LSB 2) MSB
      u64[i] = u32[i * 2] | (uint64_t (u32[i * 2 + 1]) << 32);
    seed (u64, 25);
  }
  void auto_seed ();
  uint64_t
  random ()
  {
    if (opos_ >= n_nums())
      permute1600();
    return state_[opos_++];
  }
  result_type   operator() ()   { return random(); }
  template<typename RandomAccessIterator> void
  generate (RandomAccessIterator begin, RandomAccessIterator end)
  {
    typedef typename std::iterator_traits<RandomAccessIterator>::value_type Value;
    while (begin != end)
      {
        const uint64_t rbits = operator()();
        *begin++ = Value (rbits);
        if (sizeof (Value) <= 4 && begin != end)
          *begin++ = Value (rbits >> 32);
      }
  }
  friend bool
  operator== (const KeccakRng &lhs, const KeccakRng &rhs)
  {
    for (size_t i = 0; i < 25; i++)
      if (lhs.state_[i] != rhs.state_[i])
        return false;
    return lhs.opos_ == rhs.opos_ && lhs.bit_rate_ == rhs.bit_rate_;
  }
  friend bool
  operator!= (const KeccakRng &lhs, const KeccakRng &rhs)
  {
    return !(lhs == rhs);
  }
  result_type
  min() const
  {
    return std::numeric_limits<result_type>::min(); // 0
  }
  result_type
  max() const
  {
    return std::numeric_limits<result_type>::max(); // 18446744073709551615
  }
  template<typename CharT, typename Traits>
  friend std::basic_ostream<CharT, Traits>&
  operator<< (std::basic_ostream<CharT, Traits> &os, const KeccakRng &self)
  {
    typedef typename std::basic_ostream<CharT, Traits>::ios_base IOS;
    const typename IOS::fmtflags saved_flags = os.flags();
    os.flags (IOS::dec | IOS::fixed | IOS::left);
    const CharT space = os.widen (' ');
    const CharT saved_fill = os.fill();
    os.fill (space);
    os << self.opos_;
    for (size_t i = 0; i < 25; i++)
      os << space << self.state_[i];
    os.flags (saved_flags);
    os.fill (saved_fill);
    return os;
  }
  template<typename CharT, typename Traits>
  friend std::basic_istream<CharT, Traits>&
  operator>> (std::basic_istream<CharT, Traits> &is, KeccakRng &self)
  {
    typedef typename std::basic_istream<CharT, Traits>::ios_base IOS;
    const typename IOS::fmtflags saved_flags = is.flags();
    is.flags (IOS::dec | IOS::skipws);
    is >> self.opos_;
    self.opos_ = std::min (self.n_nums(), size_t (self.opos_));
    for (size_t i = 0; i < 25; i++)
      is >> self.state_[i];
    is.flags (saved_flags);
    return is;
  }
};
 
class KeccakCryptoRng : public KeccakRng {
public:
  explicit      KeccakCryptoRng ()                       : KeccakRng (256, 24)   { auto_seed(); }
  template<class SeedSeq>
  explicit      KeccakCryptoRng (SeedSeq &seed_sequence) : KeccakRng (256, 24)   { seed (seed_sequence); }
};
 
class KeccakGoodRng : public KeccakRng {
public:
  explicit      KeccakGoodRng   ()                       : KeccakRng (192, 13)   { auto_seed(); }
  template<class SeedSeq>
  explicit      KeccakGoodRng   (SeedSeq &seed_sequence) : KeccakRng (192, 13)   { seed (seed_sequence); }
};
 
class KeccakFastRng : public KeccakRng {
public:
  explicit      KeccakFastRng   ()                       : KeccakRng (128, 8)    { auto_seed(); }
  template<class SeedSeq>
  explicit      KeccakFastRng   (SeedSeq &seed_sequence) : KeccakRng (128, 8)    { seed (seed_sequence); }
};
 
class Pcg32Rng {
  uint64_t increment_;          // must be odd, allows for 2^63 distinct random sequences
  uint64_t accu_;               // can contain all 2^64 possible values
  static constexpr const uint64_t A = 6364136223846793005ULL; // from C. E. Hayness, see TAOCP by D. E. Knuth, 3.3.4, table 1, line 26.
  static inline constexpr uint32_t
  ror32 (const uint32_t bits, const uint32_t offset)
  {
    // bitwise rotate-right pattern recognized by gcc & clang iff 32==sizeof (bits)
    return (bits >> offset) | (bits << ((32 - offset) & 31));
  }
  static inline constexpr uint32_t
  pcg_xsh_rr (const uint64_t input)
  {
    // Section 6.3.1. 32-bit Output, 64-bit State: PCG-XSH-RR
    // http://www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.pdf
    return ror32 ((input ^ (input >> 18)) >> 27, input >> 59);
  }
public:
  template<class SeedSeq>
  explicit Pcg32Rng  (SeedSeq &seed_sequence) : increment_ (0), accu_ (0) { seed (seed_sequence); }
  explicit Pcg32Rng  (uint64_t offset, uint64_t sequence);
  explicit Pcg32Rng  ();
  void     auto_seed ();
  void     seed      (uint64_t offset, uint64_t sequence);
  template<class SeedSeq> void
  seed (SeedSeq &seed_sequence)
  {
    uint64_t seeds[2];
    seed_sequence.generate (&seeds[0], &seeds[2]);
    seed (seeds[0], seeds[1]);
  }
  uint32_t
  random ()
  {
    const uint64_t lcgout = accu_;      // using the *last* state as ouput helps with CPU pipelining
    accu_ = A * accu_ + increment_;
    return pcg_xsh_rr (lcgout);         // PCG XOR-shift + random rotation
  }
};
 
// == Hashing ==
template<class Num> static inline constexpr uint64_t
fnv1a_consthash64 (const Num *ztdata)
{
  static_assert (sizeof (Num) <= 1, "");
  uint64_t hash = 0xcbf29ce484222325;
  while (ASE_ISLIKELY (*ztdata != 0))
    hash = 0x100000001b3 * (uint8_t (*ztdata++) ^ hash);
  return hash;
}
 
template<class Num> static inline constexpr uint64_t
fnv1a_consthash64 (const Num *const data, size_t length)
{
  static_assert (sizeof (Num) <= 1, "");
  uint64_t hash = 0xcbf29ce484222325;
  for (size_t j = 0; j < length; j++)
    hash = 0x100000001b3 * (uint8_t (data[j]) ^ hash);
  return hash;
}
 
template<class Num> static ASE_CONST inline uint32_t
pcg_hash32 (const Num *data, size_t length, uint64_t seed)
{
  static_assert (sizeof (Num) <= 1, "");
  uint64_t h = seed;
  // Knuth LCG
  h ^= 0x14057b7ef767814fULL;
  for (size_t i = 0; ASE_ISLIKELY (i < length); i++)
    {
      h -= uint8_t (data[i]);
      h *= 6364136223846793005ULL;
    }
  // based on pcg_detail::xsh_rr_mixin
  const size_t   rsh = h >> 59;
  const uint32_t xsh = (h ^ (h >> 18)) >> 27;
  const uint32_t rot = (xsh >> rsh) | (xsh << (32 - rsh));
  return rot;
}
 
template<class Num> static ASE_CONST inline uint64_t
pcg_hash64 (const Num *data, size_t length, uint64_t seed)
{
  static_assert (sizeof (Num) <= 1, "");
  uint64_t h = seed;
  // Knuth LCG
  h ^= 0x14057b7ef767814fULL;
  for (size_t i = 0; ASE_ISLIKELY (i < length); i++)
    {
      h -= uint8_t (data[i]);
      h *= 6364136223846793005ULL;
    }
  // based on pcg_detail::rxs_m_xs_mixin
  const size_t   rsh = h >> 59;
  const uint64_t rxs = h ^ (h >> (5 + rsh));
  const uint64_t m = rxs * 12605985483714917081ULL;
  const uint64_t xs = m ^ (m >> 43);
  return xs;
}
 
static ASE_CONST inline uint64_t
pcg_hash64 (const char *ztdata, uint64_t seed)
{
  uint64_t h = seed;
  // Knuth LCG
  h ^= 0x14057b7ef767814fULL;
  for (size_t i = 0; ASE_ISLIKELY (ztdata[i] != 0); i++)
    {
      h -= uint8_t (ztdata[i]);
      h *= 6364136223846793005ULL;
    }
  // based on pcg_detail::rxs_m_xs_mixin
  const size_t   rsh = h >> 59;
  const uint64_t rxs = h ^ (h >> (5 + rsh));
  const uint64_t m = rxs * 12605985483714917081ULL;
  const uint64_t xs = m ^ (m >> 43);
  return xs;
}
 
extern uint64_t cached_hash_secret; 
 
static ASE_PURE inline uint64_t
hash_secret ()
{
  if (ASE_UNLIKELY (cached_hash_secret == 0))
    random_secret (&cached_hash_secret);
  return cached_hash_secret;
}
 
template<class Num> static ASE_CONST inline uint64_t
byte_hash64 (const Num *data, size_t length)
{
  static_assert (sizeof (Num) <= 1, "");
  return pcg_hash64 (data, length, hash_secret());
}
 
static ASE_CONST inline uint64_t
string_hash64 (const std::string &string)
{
  return pcg_hash64 (string.data(), string.size(), hash_secret());
}
 
static ASE_CONST inline uint64_t
string_hash64 (const char *ztdata)
{
  return pcg_hash64 (ztdata, hash_secret());
}
 
} // Ase
 
#endif // __ASE_RANDOMHASH_HH__