[beast: 1/20] SFI: add randomhash.hh, randomhash.cc from Rapicorn
- From: Tim Janik <timj src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [beast: 1/20] SFI: add randomhash.hh, randomhash.cc from Rapicorn
- Date: Sun, 24 Sep 2017 00:19:43 +0000 (UTC)
commit 6521240f8dce3adbef7b1aac87c0e787fa67fb93
Author: Tim Janik <timj gnu org>
Date: Sun Sep 17 01:50:20 2017 +0200
SFI: add randomhash.hh, randomhash.cc from Rapicorn
Import is based on Rapicorn commit id:
bf228016cba3f6d252ee2cc38e1ed32607f37bf0
Signed-off-by: Tim Janik <timj gnu org>
sfi/randomhash.cc | 687 +++++++++++++++++++++++++++++++++++++++++++++++++++++
sfi/randomhash.hh | 559 +++++++++++++++++++++++++++++++++++++++++++
2 files changed, 1246 insertions(+), 0 deletions(-)
---
diff --git a/sfi/randomhash.cc b/sfi/randomhash.cc
new file mode 100644
index 0000000..5cffe16
--- /dev/null
+++ b/sfi/randomhash.cc
@@ -0,0 +1,687 @@
+// This Source Code Form is licensed MPL-2.0: http://mozilla.org/MPL/2.0
+// Author: 2014, Tim Janik, see http://testbit.org/keccak
+#include "randomhash.hh"
+#include "entropy.hh"
+
+namespace Bse {
+
+// == Lib::KeccakF1600 ==
+Lib::KeccakF1600::KeccakF1600()
+{
+ reset();
+}
+
+void
+Lib::KeccakF1600::reset ()
+{
+ memset4 ((uint32*) bytes, 0, sizeof (bytes) / 4);
+}
+
+static constexpr const uint8_t KECCAK_RHO_OFFSETS[25] = { 0, 1, 62, 28, 27, 36, 44, 6, 55, 20, 3, 10, 43,
+ 25, 39, 41, 45, 15, 21, 8, 18, 2, 61, 56, 14 };
+static constexpr const uint64_t KECCAK_ROUND_CONSTANTS[255] = {
+ 1, 32898, 0x800000000000808a, 0x8000000080008000, 32907, 0x80000001, 0x8000000080008081,
0x8000000000008009, 138, 136, 0x80008009,
+ 0x8000000a, 0x8000808b, 0x800000000000008b, 0x8000000000008089, 0x8000000000008003, 0x8000000000008002,
0x8000000000000080, 32778,
+ 0x800000008000000a, 0x8000000080008081, 0x8000000000008080, 0x80000001, 0x8000000080008008,
0x8000000080008082, 0x800000008000800a,
+ 0x8000000000000003, 0x8000000080000009, 0x8000000000008082, 32777, 0x8000000000000080, 32899,
0x8000000000000081, 1, 32779,
+ 0x8000000080008001, 128, 0x8000000000008000, 0x8000000080008001, 9, 0x800000008000808b, 129,
0x8000000000000082, 0x8000008b,
+ 0x8000000080008009, 0x8000000080000000, 0x80000080, 0x80008003, 0x8000000080008082, 0x8000000080008083,
0x8000000080000088, 32905,
+ 32777, 0x8000000000000009, 0x80008008, 0x80008001, 0x800000000000008a, 0x800000000000000b, 137,
0x80000002, 0x800000000000800b,
+ 0x8000800b, 32907, 0x80000088, 0x800000000000800a, 0x80000089, 0x8000000000000001, 0x8000000000008088,
0x8000000000000081, 136,
+ 0x80008080, 129, 0x800000000000000b, 0, 137, 0x8000008b, 0x8000000080008080, 0x800000000000008b,
0x8000000000008000,
+ 0x8000000080008088, 0x80000082, 11, 0x800000000000000a, 32898, 0x8000000000008003, 0x800000000000808b,
0x800000008000000b,
+ 0x800000008000008a, 0x80000081, 0x80000081, 0x80000008, 131, 0x8000000080008003, 0x80008088,
0x8000000080000088, 32768, 0x80008082,
+ 0x80008089, 0x8000000080008083, 0x8000000080000001, 0x80008002, 0x8000000080000089, 130,
0x8000000080000008, 0x8000000000000089,
+ 0x8000000080000008, 0x8000000000000000, 0x8000000000000083, 0x80008080, 8, 0x8000000080000080,
0x8000000080008080,
+ 0x8000000000000002, 0x800000008000808b, 8, 0x8000000080000009, 0x800000000000800b, 0x80008082, 0x80008000,
0x8000000000008008, 32897,
+ 0x8000000080008089, 0x80008089, 0x800000008000800a, 0x800000000000008a, 0x8000000000000082, 0x80000002,
0x8000000000008082, 32896,
+ 0x800000008000000b, 0x8000000080000003, 10, 0x8000000000008001, 0x8000000080000083, 0x8000000000008083,
139, 32778,
+ 0x8000000080000083, 0x800000000000800a, 0x80000000, 0x800000008000008a, 0x80000008, 10,
0x8000000000008088, 0x8000000000000008,
+ 0x80000003, 0x8000000000000000, 0x800000000000000a, 32779, 0x8000000080008088, 0x8000000b, 0x80000080,
0x8000808a,
+ 0x8000000000008009, 3, 0x80000003, 0x8000000000000089, 0x8000000080000081, 0x800000008000008b, 0x80008003,
0x800000008000800b,
+ 0x8000000000008008, 32776, 0x8000000000008002, 0x8000000000000009, 0x80008081, 32906, 0x8000800a, 128,
0x8000000000008089,
+ 0x800000000000808a, 0x8000000080008089, 0x80008000, 0x8000000000008081, 0x8000800a, 9, 0x8000000080008002,
0x8000000a, 0x80008002,
+ 0x8000000080000000, 0x80000009, 32904, 2, 0x80008008, 0x80008088, 0x8000000080000001, 0x8000808b,
0x8000000000000002,
+ 0x8000000080008002, 0x80000083, 32905, 32896, 0x8000000080000082, 0x8000000000000088, 0x800000008000808a,
32906, 0x80008083,
+ 0x8000000b, 0x80000009, 32769, 0x80000089, 0x8000000000000088, 0x8000000080008003, 0x80008001,
0x8000000000000003,
+ 0x8000000080000080, 0x8000000080008009, 0x8000000080000089, 11, 0x8000000000000083, 0x80008009,
0x80000083, 32768, 0x8000800b, 32770,
+ 3, 0x8000008a, 0x8000000080000002, 32769, 0x80000000, 0x8000000080000003, 131, 0x800000008000808a, 32771,
32776, 0x800000000000808b,
+ 0x8000000080000082, 0x8000000000000001, 0x8000000000008001, 0x800000008000000a, 0x8000000080008008,
0x800000008000800b,
+ 0x8000000000008081, 0x80008083, 0x80000082, 130, 0x8000000080000081, 0x8000000080000002, 32904, 139,
32899, 0x8000000000000008,
+ 0x8000008a, 0x800000008000008b, 0x8000808a, 0x8000000000008080, 0x80000088, 0x8000000000008083, 2,
0x80008081, 32771, 32897,
+ 0x8000000080008000, 32770, 138,
+};
+
+/// Rotate left for uint64_t.
+static inline constexpr uint64_t
+bit_rotate64 (uint64_t bits, unsigned int offset)
+{
+ // bitwise rotate-left pattern recognized by gcc & clang iff 64==sizeof (bits)
+ return (bits << offset) | (bits >> (64 - offset));
+}
+
+/// The Keccak-f[1600] permutation for up to 254 rounds, see Keccak11 @cite Keccak11 .
+void
+Lib::KeccakF1600::permute (const uint32_t n_rounds)
+{
+ BSE_ASSERT_RETURN (n_rounds < 255); // adjust the KECCAK_ROUND_CONSTANTS access to lift this assertion
+ // Keccak forward rounds
+ for (size_t round_index = 0; round_index < n_rounds; round_index++)
+ {
+ // theta
+ uint64_t C[5];
+ for (size_t x = 0; x < 5; x++)
+ {
+ C[x] = A[x];
+ for (size_t y = 1; y < 5; y++)
+ C[x] ^= A[x + 5 * y];
+ }
+ for (size_t x = 0; x < 5; x++)
+ {
+ const uint64_t D = C[(5 + x - 1) % 5] ^ bit_rotate64 (C[(x + 1) % 5], 1);
+ for (size_t y = 0; y < 5; y++)
+ A[x + 5 * y] ^= D;
+ }
+ // rho
+ for (size_t y = 0; y < 25; y += 5)
+ {
+ uint64_t *const plane = &A[y];
+ for (size_t x = 0; x < 5; x++)
+ plane[x] = bit_rotate64 (plane[x], KECCAK_RHO_OFFSETS[x + y]);
+ }
+ // pi
+ const uint64_t a[25] = { A[0], A[1], A[2], A[3], A[4], A[5], A[6], A[7], A[8], A[9], A[10], A[11],
A[12],
+ A[13], A[14], A[15], A[16], A[17], A[18], A[19], A[20], A[21], A[22], A[23],
A[24] };
+ for (size_t y = 0; y < 5; y++)
+ for (size_t x = 0; x < 5; x++)
+ {
+ const size_t X = (0 * x + 1 * y) % 5;
+ const size_t Y = (2 * x + 3 * y) % 5;
+ A[X + 5 * Y] = a[x + 5 * y];
+ }
+ // chi
+ for (size_t y = 0; y < 25; y += 5)
+ {
+ uint64_t *const plane = &A[y];
+ for (size_t x = 0; x < 5; x++)
+ C[x] = plane[x] ^ (~plane[(x + 1) % 5] & plane[(x + 2) % 5]);
+ for (size_t x = 0; x < 5; x++)
+ plane[x] = C[x];
+ }
+ // iota
+ A[0 + 5 * 0] ^= KECCAK_ROUND_CONSTANTS[round_index]; // round_index needs %255 for n_rounds>=255
+ }
+}
+
+// == KeccakRng ==
+/// Keccak permutation for 1600 bits, see Keccak11 @cite Keccak11 .
+void
+KeccakRng::permute1600()
+{
+ state_.permute (n_rounds_);
+ opos_ = 0; // fresh outputs available
+}
+
+/** Discard 2^256 bits of the current generator state.
+ * This makes it practically infeasible to guess previous generator states or
+ * deduce generated values from the past.
+ * Use this for forward security @cite Security03 of generated security tokens like session keys.
+ */
+void
+KeccakRng::forget()
+{
+ std::fill (&state_[0], &state_[256 / 64], 0);
+ permute1600();
+}
+
+/** Discard @a count consecutive random values.
+ * This function is slightly faster than calling operator()() exactly @a count times.
+ */
+void
+KeccakRng::discard (unsigned long long count)
+{
+ while (count)
+ {
+ if (opos_ >= n_nums())
+ permute1600();
+ const unsigned long long ull = std::min ((unsigned long long) n_nums() - opos_, count);
+ opos_ += ull;
+ count -= ull;
+ }
+}
+
+/** Incorporate @a seed_values into the current generator state.
+ * A block permutation to advance the generator state is carried out per n_nums() seed values.
+ * After calling this function, generating the next n_nums() random values will not need to
+ * block for a new permutation.
+ */
+void
+KeccakRng::xor_seed (const uint64_t *seeds, size_t n_seeds)
+{
+ // printerr ("xor_seed(%p): %s\n", this, String ((const char*) seeds, n_seeds * 8));
+ size_t i = 0;
+ while (n_seeds)
+ {
+ if (i > 0) // not first seed block
+ permute1600(); // prepare for next seed block
+ const size_t count = std::min (n_nums(), n_seeds);
+ for (i = 0; i < count; i++)
+ state_[i] ^= seeds[i];
+ seeds += count;
+ n_seeds -= count;
+ }
+ if (i < 25) // apply Simple padding: pad10*
+ state_[i] ^= 0x1; // 1: payload boundary bit for Keccak Sponge compliant padding
+ permute1600(); // integrate seed
+}
+
+void
+KeccakRng::auto_seed()
+{
+ AutoSeeder seeder;
+ seed (seeder);
+}
+
+/// The destructor resets the generator state to avoid leaving memory trails.
+KeccakRng::~KeccakRng()
+{
+ // forget all state and leave no trails
+ std::fill (&state_[0], &state_[25], 0xaffeaffeaffeaffe);
+ forget();
+ opos_ = n_nums();
+}
+
+// == SHAKE_Base - primitive for SHA3 hashing ==
+template<size_t HASHBITS, uint8_t DOMAINBITS>
+class SHAKE_Base {
+ Lib::KeccakF1600 state_;
+ const size_t rate_;
+ size_t iopos_;
+ bool feeding_mode_;
+protected:
+ /// Add stream data up to block size into Keccak state via XOR.
+ size_t
+ xor_state (size_t offset, const uint8_t *input, size_t n_in)
+ {
+ BSE_ASSERT_RETURN (offset + n_in <= byte_rate(), 0);
+ size_t i;
+ for (i = offset; i < offset + n_in; i++)
+ state_.byte (i) ^= input[i - offset];
+ return i - offset;
+ }
+ /** Pad stream from offset to block boundary into Keccak state via XOR.
+ * The @a trail argument must contain the termination bit, optionally preceeded by
+ * additional (LSB) bits for domain separation. A permutation is carried out if the
+ * trailing padding bits do not fit into the remaining block length.
+ */
+ void
+ absorb_padding (size_t offset, uint8_t trail = 0x01)
+ {
+ BSE_ASSERT_RETURN (offset < byte_rate()); // offset is first byte following payload
+ BSE_ASSERT_RETURN (trail != 0x00);
+ // MultiRatePadding
+ state_.byte (offset) ^= trail; // 1: payload boundary bit for MultiRatePadding (and
SimplePadding)
+ // state_.bits[i..last] ^= 0x0; // 0*: bitrate filler for MultiRatePadding (and
SimplePadding)
+ const size_t lastbyte = byte_rate() - 1; // last bitrate byte, may coincide with offset
+ if (offset == lastbyte && trail >= 0x80)
+ state_.permute (24); // prepare new block to append last bit
+ state_.byte (lastbyte) ^= 0x80; // 1: last bitrate bit; required by MultiRatePadding
+ }
+ SHAKE_Base (size_t rate) :
+ rate_ (rate), iopos_ (0), feeding_mode_ (true)
+ {}
+public:
+ size_t
+ byte_rate() const
+ {
+ return rate_ / 8;
+ }
+ void
+ reset()
+ {
+ state_.reset();
+ iopos_ = 0;
+ feeding_mode_ = true;
+ }
+ void
+ update (const uint8_t *data, size_t length)
+ {
+ BSE_ASSERT_RETURN (feeding_mode_ == true);
+ while (length)
+ {
+ const size_t count = std::min (byte_rate() - iopos_, length);
+ xor_state (iopos_, data, count);
+ iopos_ += count;
+ data += count;
+ length -= count;
+ if (iopos_ >= byte_rate())
+ {
+ state_.permute (24);
+ iopos_ = 0;
+ }
+ }
+ }
+ /// Switch from absorbing into squeezing mode and return digest.
+ size_t
+ get_hash (uint8_t hashvalue[HASHBITS / 8])
+ {
+ if (feeding_mode_)
+ {
+ const uint8_t shake_delimiter = DOMAINBITS;
+ absorb_padding (iopos_, shake_delimiter);
+ feeding_mode_ = false;
+ state_.permute (24);
+ iopos_ = 0;
+ }
+ const size_t count = HASHBITS / 8;
+ for (size_t i = 0; i < count; i++)
+ hashvalue[i] = state_.byte (i);
+ return count;
+ }
+ /// Read out the current Keccak state and permute as needed.
+ void
+ squeeze_digest (uint8_t *output, size_t n_out)
+ {
+ BSE_ASSERT_RETURN (HASHBITS == 0);
+ get_hash (output); // absorb_padding and leave feeding_mode_
+ BSE_ASSERT_RETURN (feeding_mode_ == false);
+ while (n_out)
+ {
+ const size_t count = std::min (n_out, byte_rate() - iopos_);
+ for (size_t i = 0; i < count; i++)
+ output[i] = state_.byte (iopos_ + i);
+ iopos_ += count;
+ output += count;
+ n_out -= count;
+ if (iopos_ >= byte_rate())
+ {
+ state_.permute (24);
+ iopos_ = 0;
+ }
+ }
+ }
+};
+
+// == SHA3_224 ==
+struct SHA3_224::State : SHAKE_Base<224, 0x06> {
+ State() : SHAKE_Base (1152) {}
+};
+
+SHA3_224::SHA3_224 () :
+ state_ (new (&mem_) State())
+{
+ static_assert (sizeof (mem_) >= sizeof (*state_), "");
+}
+
+SHA3_224::~SHA3_224 ()
+{
+ state_->~State();
+}
+
+void
+SHA3_224::update (const uint8_t *data, size_t length)
+{
+ state_->update (data, length);
+}
+
+void
+SHA3_224::digest (uint8_t hashvalue[28])
+{
+ state_->get_hash (hashvalue);
+}
+
+void
+SHA3_224::reset ()
+{
+ state_->reset();
+}
+
+void
+sha3_224_hash (const void *data, size_t data_length, uint8_t hashvalue[28])
+{
+ SHA3_224 context;
+ context.update ((const uint8_t*) data, data_length);
+ context.digest (hashvalue);
+}
+
+// == SHA3_256 ==
+struct SHA3_256::State : SHAKE_Base<256, 0x06> {
+ State() : SHAKE_Base (1088) {}
+};
+
+SHA3_256::SHA3_256 () :
+ state_ (new (&mem_) State())
+{
+ static_assert (sizeof (mem_) >= sizeof (*state_), "");
+}
+
+SHA3_256::~SHA3_256 ()
+{
+ state_->~State();
+}
+
+void
+SHA3_256::update (const uint8_t *data, size_t length)
+{
+ state_->update (data, length);
+}
+
+void
+SHA3_256::digest (uint8_t hashvalue[32])
+{
+ state_->get_hash (hashvalue);
+}
+
+void
+SHA3_256::reset ()
+{
+ state_->reset();
+}
+
+void
+sha3_256_hash (const void *data, size_t data_length, uint8_t hashvalue[32])
+{
+ SHA3_256 context;
+ context.update ((const uint8_t*) data, data_length);
+ context.digest (hashvalue);
+}
+
+// == SHA3_384 ==
+struct SHA3_384::State : SHAKE_Base<384, 0x06> {
+ State() : SHAKE_Base (832) {}
+};
+
+SHA3_384::SHA3_384 () :
+ state_ (new (&mem_) State())
+{
+ static_assert (sizeof (mem_) >= sizeof (*state_), "");
+}
+
+SHA3_384::~SHA3_384 ()
+{
+ state_->~State();
+}
+
+void
+SHA3_384::update (const uint8_t *data, size_t length)
+{
+ state_->update (data, length);
+}
+
+void
+SHA3_384::digest (uint8_t hashvalue[48])
+{
+ state_->get_hash (hashvalue);
+}
+
+void
+SHA3_384::reset ()
+{
+ state_->reset();
+}
+
+void
+sha3_384_hash (const void *data, size_t data_length, uint8_t hashvalue[48])
+{
+ SHA3_384 context;
+ context.update ((const uint8_t*) data, data_length);
+ context.digest (hashvalue);
+}
+
+// == SHA3_512 ==
+struct SHA3_512::State : SHAKE_Base<512, 0x06> {
+ State() : SHAKE_Base (576) {}
+};
+
+SHA3_512::SHA3_512 () :
+ state_ (new (&mem_) State())
+{
+ static_assert (sizeof (mem_) >= sizeof (*state_), "");
+}
+
+SHA3_512::~SHA3_512 ()
+{
+ state_->~State();
+}
+
+void
+SHA3_512::update (const uint8_t *data, size_t length)
+{
+ state_->update (data, length);
+}
+
+void
+SHA3_512::digest (uint8_t hashvalue[64])
+{
+ state_->get_hash (hashvalue);
+}
+
+void
+SHA3_512::reset ()
+{
+ state_->reset();
+}
+
+void
+sha3_512_hash (const void *data, size_t data_length, uint8_t hashvalue[64])
+{
+ SHA3_512 context;
+ context.update ((const uint8_t*) data, data_length);
+ context.digest (hashvalue);
+}
+
+// == SHAKE128 ==
+struct SHAKE128::State : SHAKE_Base<0, 0x1f> {
+ State() : SHAKE_Base (1344) {}
+};
+
+SHAKE128::SHAKE128 () :
+ state_ (new (&mem_) State())
+{
+ static_assert (sizeof (mem_) >= sizeof (*state_), "");
+}
+
+SHAKE128::~SHAKE128 ()
+{
+ state_->~State();
+}
+
+void
+SHAKE128::update (const uint8_t *data, size_t length)
+{
+ state_->update (data, length);
+}
+
+void
+SHAKE128::squeeze_digest (uint8_t *hashvalues, size_t n)
+{
+ state_->squeeze_digest (hashvalues, n);
+}
+
+void
+SHAKE128::reset ()
+{
+ state_->reset();
+}
+
+void
+shake128_hash (const void *data, size_t data_length, uint8_t *hashvalues, size_t n)
+{
+ SHAKE128 context;
+ context.update ((const uint8_t*) data, data_length);
+ context.squeeze_digest (hashvalues, n);
+}
+
+// == SHAKE256 ==
+struct SHAKE256::State : SHAKE_Base<0, 0x1f> {
+ State() : SHAKE_Base (1088) {}
+};
+
+SHAKE256::SHAKE256 () :
+ state_ (new (&mem_) State())
+{
+ static_assert (sizeof (mem_) >= sizeof (*state_), "");
+}
+
+SHAKE256::~SHAKE256 ()
+{
+ state_->~State();
+}
+
+void
+SHAKE256::update (const uint8_t *data, size_t length)
+{
+ state_->update (data, length);
+}
+
+void
+SHAKE256::squeeze_digest (uint8_t *hashvalues, size_t n)
+{
+ state_->squeeze_digest (hashvalues, n);
+}
+
+void
+SHAKE256::reset ()
+{
+ state_->reset();
+}
+
+void
+shake256_hash (const void *data, size_t data_length, uint8_t *hashvalues, size_t n)
+{
+ SHAKE256 context;
+ context.update ((const uint8_t*) data, data_length);
+ context.squeeze_digest (hashvalues, n);
+}
+
+// == Pcg32Rng ==
+Pcg32Rng::Pcg32Rng () :
+ increment_ (0), accu_ (0)
+{
+ auto_seed();
+}
+
+Pcg32Rng::Pcg32Rng (uint64_t offset, uint64_t sequence) :
+ increment_ (0), accu_ (0)
+{
+ seed (offset, sequence);
+}
+
+void
+Pcg32Rng::auto_seed ()
+{
+ AutoSeeder seeder;
+ seed (seeder);
+}
+
+void
+Pcg32Rng::seed (uint64_t offset, uint64_t sequence)
+{
+ accu_ = sequence;
+ increment_ = (sequence << 1) | 1; // force increment_ to be odd
+ accu_ += offset;
+ accu_ = A * accu_ + increment_;
+}
+
+// == Random Numbers ==
+static uint64_t
+global_random64()
+{
+ static KeccakRng *global_rng = NULL;
+ static std::mutex mtx;
+ std::unique_lock<std::mutex> lock (mtx);
+ if (UNLIKELY (!global_rng))
+ {
+ uint64 entropy[32];
+ collect_runtime_entropy (entropy, ARRAY_SIZE (entropy));
+ static std::aligned_storage<sizeof (KeccakRng), alignof (KeccakRng)>::type mem;
+ // 8 rounds provide good statistical shuffling, and
+ // 256 hidden bits make the generator state unguessable
+ global_rng = new (&mem) KeccakRng (256, 8);
+ global_rng->seed (entropy, ARRAY_SIZE (entropy));
+ }
+ return global_rng->random();
+}
+
+/** Generate a non-deterministic, uniformly distributed 64 bit pseudo-random number.
+ * This function generates pseudo-random numbers using the system state as entropy
+ * and class KeccakRng for the mixing. No seeding is required.
+ */
+uint64_t
+random_int64 ()
+{
+ return global_random64();
+}
+
+/** Generate uniformly distributed pseudo-random integer within range.
+ * This function generates a pseudo-random number like random_int64(),
+ * constrained to the range: @a begin <= number < @a end.
+ */
+int64_t
+random_irange (int64_t begin, int64_t end)
+{
+ return_unless (begin < end, begin);
+ const uint64_t range = end - begin;
+ const uint64_t quotient = 0xffffffffffffffffULL / range;
+ const uint64_t bound = quotient * range;
+ uint64_t r = global_random64();
+ while (BSE_UNLIKELY (r >= bound)) // repeats with <50% probability
+ r = global_random64();
+ return begin + r / quotient;
+}
+
+/** Generate uniformly distributed pseudo-random floating point number.
+ * This function generates a pseudo-random number like random_int64(),
+ * constrained to the range: 0.0 <= number < 1.0.
+ */
+double
+random_float ()
+{
+ double r01;
+ do
+ r01 = global_random64() * 5.42101086242752217003726400434970855712890625e-20; // 1.0 / 2^64
+ while (BSE_UNLIKELY (r01 >= 1.0)); // retry if arithmetic exceeds boundary
+ return r01;
+}
+
+/** Generate uniformly distributed pseudo-random floating point number within a range.
+ * This function generates a pseudo-random number like random_float(),
+ * constrained to the range: @a begin <= number < @a end.
+ */
+double
+random_frange (double begin, double end)
+{
+ return_unless (begin < end, begin + 0 * end); // catch and propagate NaNs
+ const double r01 = global_random64() * 5.42101086242752217003726400434970855712890625e-20; // 1.0 / 2^64
+ return end * r01 + (1.0 - r01) * begin;
+}
+
+/// Provide a unique 64 bit identifier that is not 0, see also random_int64().
+uint64_t
+random_nonce ()
+{
+ static uint64_t cached_nonce = 0;
+ if (BSE_UNLIKELY (cached_nonce == 0))
+ random_secret (&cached_nonce);
+ return cached_nonce;
+}
+
+/// Generate a secret non-zero nonce in secret_var, unless it has already been assigned.
+void
+random_secret (uint64_t *secret_var)
+{
+ static std::mutex mtx;
+ std::unique_lock<std::mutex> lock (mtx);
+ if (!*secret_var)
+ {
+ uint64_t d;
+ do
+ d = global_random64();
+ while (d == 0); // very unlikely
+ *secret_var = d;
+ }
+}
+
+uint64_t cached_hash_secret = 0;
+
+} // Bse
diff --git a/sfi/randomhash.hh b/sfi/randomhash.hh
new file mode 100644
index 0000000..0877f69
--- /dev/null
+++ b/sfi/randomhash.hh
@@ -0,0 +1,559 @@
+// This Source Code Form is licensed MPL-2.0: http://mozilla.org/MPL/2.0
+// Author: 2014, Tim Janik, see http://testbit.org/keccak
+#ifndef __BSE_RANDOMHASH_HH__
+#define __BSE_RANDOMHASH_HH__
+
+#include <sfi/bcore.hh>
+
+namespace Bse {
+
+/** Helper to provide memory for placement new
+ * AlignedPOD<SIZE> is aligned like max_align_t or like malloc()-ed memory and
+ * provides SIZE bytes. Idiomatic use is:
+ * \code{.cc}
+ * static AlignedPOD<sizeof (std::string)> pod_mem;
+ * std::string *str = new (&pod_mem) std::string();
+ * \endcode
+ */
+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);
+
+
+// == Hashing ==
+/** SHA3_224 - 224 Bit digest generation.
+ * This class implements the SHA3 hash funtion to create 224 Bit digests, see FIPS 202 @cite Fips202 .
+ */
+struct SHA3_224 {
+ /*dtor*/ ~SHA3_224 ();
+ /*ctor*/ SHA3_224 (); ///< Create context to calculate a 224 bit SHA3 hash digest.
+ void reset (); ///< Reset state to feed and retrieve a new hash value.
+ void update (const uint8_t *data, size_t length); ///< Feed data to be hashed.
+ void digest (uint8_t hashvalue[28]); ///< Retrieve the resulting hash value.
+private:
+ AlignedPOD<232> mem_;
+ class State;
+ State *state_;
+};
+/// Calculate 224 bit SHA3 digest from @a data, see also class SHA3_224.
+void sha3_224_hash (const void *data, size_t data_length, uint8_t hashvalue[28]);
+
+/** SHA3_256 - 256 Bit digest generation.
+ * This class implements the SHA3 hash funtion to create 256 Bit digests, see FIPS 202 @cite Fips202 .
+ */
+struct SHA3_256 {
+ /*dtor*/ ~SHA3_256 ();
+ /*ctor*/ SHA3_256 (); ///< Create context to calculate a 256 bit SHA3 hash digest.
+ void reset (); ///< Reset state to feed and retrieve a new hash value.
+ void update (const uint8_t *data, size_t length); ///< Feed data to be hashed.
+ void digest (uint8_t hashvalue[32]); ///< Retrieve the resulting hash value.
+private:
+ AlignedPOD<232> mem_;
+ class State;
+ State *state_;
+};
+/// Calculate 256 bit SHA3 digest from @a data, see also class SHA3_256.
+void sha3_256_hash (const void *data, size_t data_length, uint8_t hashvalue[32]);
+
+/** SHA3_384 - 384 Bit digest generation.
+ * This class implements the SHA3 hash funtion to create 384 Bit digests, see FIPS 202 @cite Fips202 .
+ */
+struct SHA3_384 {
+ /*dtor*/ ~SHA3_384 ();
+ /*ctor*/ SHA3_384 (); ///< Create context to calculate a 384 bit SHA3 hash digest.
+ void reset (); ///< Reset state to feed and retrieve a new hash value.
+ void update (const uint8_t *data, size_t length); ///< Feed data to be hashed.
+ void digest (uint8_t hashvalue[48]); ///< Retrieve the resulting hash value.
+private:
+ AlignedPOD<232> mem_;
+ class State;
+ State *state_;
+};
+/// Calculate 384 bit SHA3 digest from @a data, see also class SHA3_384.
+void sha3_384_hash (const void *data, size_t data_length, uint8_t hashvalue[48]);
+
+/** SHA3_512 - 512 Bit digest generation.
+ * This class implements the SHA3 hash funtion to create 512 Bit digests, see FIPS 202 @cite Fips202 .
+ */
+struct SHA3_512 {
+ /*dtor*/ ~SHA3_512 ();
+ /*ctor*/ SHA3_512 (); ///< Create context to calculate a 512 bit SHA3 hash digest.
+ void reset (); ///< Reset state to feed and retrieve a new hash value.
+ void update (const uint8_t *data, size_t length); ///< Feed data to be hashed.
+ void digest (uint8_t hashvalue[64]); ///< Retrieve the resulting hash value.
+private:
+ AlignedPOD<232> mem_;
+ class State;
+ State *state_;
+};
+/// Calculate 512 bit SHA3 digest from @a data, see also class SHA3_512.
+void sha3_512_hash (const void *data, size_t data_length, uint8_t hashvalue[64]);
+
+/** SHAKE128 - 128 Bit extendable output digest generation.
+ * This class implements the SHA3 extendable output hash funtion with 128 bit security strength, see FIPS
202 @cite Fips202 .
+ */
+struct SHAKE128 {
+ /*dtor*/ ~SHAKE128 ();
+ /*ctor*/ SHAKE128 (); ///< Create context to calculate an unbounded SHAKE128 hash digest.
+ void reset (); ///< Reset state to feed and retrieve a new hash value.
+ void update (const uint8_t *data, size_t length); ///< Feed data to be hashed.
+ void squeeze_digest (uint8_t *hashvalues, size_t n); ///< Retrieve an arbitrary number of
hash value bytes.
+private:
+ AlignedPOD<232> mem_;
+ class State;
+ State *state_;
+};
+/// Calculate SHA3 extendable output digest for 128 bit security strength, see also class SHAKE128.
+void shake128_hash (const void *data, size_t data_length, uint8_t *hashvalues, size_t n);
+
+/** SHAKE256 - 256 Bit extendable output digest generation.
+ * This class implements the SHA3 extendable output hash funtion with 256 bit security strength, see FIPS
202 @cite Fips202 .
+ */
+struct SHAKE256 {
+ /*dtor*/ ~SHAKE256 ();
+ /*ctor*/ SHAKE256 (); ///< Create context to calculate an unbounded SHAKE256 hash digest.
+ void reset (); ///< Reset state to feed and retrieve a new hash value.
+ void update (const uint8_t *data, size_t length); ///< Feed data to be hashed.
+ void squeeze_digest (uint8_t *hashvalues, size_t n); ///< Retrieve an arbitrary number of
hash value bytes.
+private:
+ AlignedPOD<232> mem_;
+ class State;
+ State *state_;
+};
+/// Calculate SHA3 extendable output digest for 256 bit security strength, see also class SHAKE256.
+void shake256_hash (const void *data, size_t data_length, uint8_t *hashvalues, size_t n);
+
+namespace Lib { // Namespace for implementation internals
+
+/// The Keccak-f[1600] Permutation, see the Keccak specification @cite Keccak11 .
+class KeccakF1600 {
+ union alignas (2 * sizeof (uint64_t))
+ {
+ uint64_t A[25];
+ uint8_t bytes[200];
+ // __MMX__: __m64 V[25];
+ };
+public:
+ explicit KeccakF1600 (); ///< Zero the state.
+ void reset (); ///< Zero the state.
+ uint64_t& operator[] (int index) { return A[index]; }
+ uint64_t operator[] (int index) const { return A[index]; }
+ void permute (uint32_t n_rounds); ///< Apply Keccak permutation with @a n_rounds.
+ inline uint8_t&
+ byte (size_t state_index) ///< Access byte 0..199 of the state.
+ {
+#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
+
+/// AutoSeeder provides non-deterministic seeding entropy.
+class AutoSeeder {
+public:
+ /// Generate non-deterministic 64bit random value.
+ static uint64 random () { return random_int64(); }
+ /// Generate non-deterministic 64bit random value.
+ uint64 operator() () const { return this->random(); }
+ /// Fill the range [begin, end) with random unsigned integer values.
+ 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);
+ }
+ }
+};
+
+/** KeccakRng - A KeccakF1600 based pseudo-random number generator.
+ * The permutation steps are derived from the Keccak specification @cite Keccak11 .
+ * For further details about this implementation, see also: http://testbit.org/keccak
+ * This class is primarily used to implement more fine tuned generators, such as:
+ * KeccakCryptoRng, KeccakGoodRng and KeccakFastRng.
+ */
+class KeccakRng {
+ const uint16_t bit_rate_, n_rounds_;
+ uint32_t opos_;
+ Lib::KeccakF1600 state_;
+ void permute1600();
+public:
+ /// Integral type of the KeccakRng generator results.
+ typedef uint64_t result_type;
+ /// Amount of 64 bit random numbers per generated block.
+ inline size_t n_nums() const { return bit_rate_ / 64; }
+ /// Amount of bits used to store hidden random number generator state.
+ inline size_t bit_capacity() const { return 1600 - bit_rate_; }
+ /*dtor*/ ~KeccakRng ();
+ /// Create an unseeded Keccak PRNG with specific capacity and number of rounds, for experts only.
+ explicit
+ KeccakRng (uint16_t hidden_state_capacity, uint16_t n_rounds) :
+ bit_rate_ (1600 - hidden_state_capacity), n_rounds_ (n_rounds), opos_ (n_nums())
+ {
+ BSE_ASSERT_RETURN (hidden_state_capacity > 0 && hidden_state_capacity <= 1600 - 64);
+ BSE_ASSERT_RETURN (64 * (hidden_state_capacity / 64) == hidden_state_capacity); // capacity must be
64bit aligned
+ BSE_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);
+ /// Reinitialize the generator state using a 64 bit @a seed_value.
+ void seed (uint64_t seed_value = 1) { seed (&seed_value, 1); }
+ /// Reinitialize the generator state using a nuber of 64 bit @a seeds.
+ void
+ seed (const uint64_t *seeds, size_t n_seeds)
+ {
+ state_.reset();
+ xor_seed (seeds, n_seeds);
+ }
+ /// Seed the generator state from a @a seed_sequence.
+ 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);
+ }
+ /// Seed the generator from a system specific nondeterministic random source.
+ void auto_seed ();
+ /// Generate uniformly distributed 64 bit pseudo random number.
+ /// A new block permutation is carried out every n_nums() calls, see also xor_seed().
+ uint64_t
+ random ()
+ {
+ if (opos_ >= n_nums())
+ permute1600();
+ return state_[opos_++];
+ }
+ /// Generate uniformly distributed 32 bit pseudo random number.
+ result_type operator() () { return random(); }
+ /// Fill the range [begin, end) with random unsigned integer values.
+ 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);
+ }
+ }
+ /// Compare two generators for state equality.
+ 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_;
+ }
+ /// Compare two generators for state inequality.
+ friend bool
+ operator!= (const KeccakRng &lhs, const KeccakRng &rhs)
+ {
+ return !(lhs == rhs);
+ }
+ /// Minimum of the result type, for uint64_t that is 0.
+ result_type
+ min() const
+ {
+ return std::numeric_limits<result_type>::min(); // 0
+ }
+ /// Maximum of the result type, for uint64_t that is 18446744073709551615.
+ result_type
+ max() const
+ {
+ return std::numeric_limits<result_type>::max(); // 18446744073709551615
+ }
+ /// Serialize generator state into an OStream.
+ 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;
+ }
+ /// Deserialize generator state from an IStream.
+ 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;
+ }
+};
+
+/** KeccakCryptoRng - A KeccakF1600 based cryptographic quality pseudo-random number generator.
+ * The quality of the generated pseudo random numbers is comaparable to the hash output of SHAKE128.
+ */
+class KeccakCryptoRng : public KeccakRng {
+public:
+ /// Initialize and seed the generator from a system specific nondeterministic random source.
+ explicit KeccakCryptoRng () : KeccakRng (256, 24) { auto_seed(); }
+ /// Initialize and seed the generator from @a seed_sequence.
+ template<class SeedSeq>
+ explicit KeccakCryptoRng (SeedSeq &seed_sequence) : KeccakRng (256, 24) { seed (seed_sequence); }
+};
+
+/** KeccakGoodRng - A KeccakF1600 based good quality pseudo-random number generator.
+ * This class provides very good random numbers, using the KeccakF1600 algorithm without
+ * the extra security margins applied for SHA3 hash generation. This improves performance
+ * significantly without noticably trading random number quality.
+ * For cryptography grade number generation KeccakCryptoRng should be used instead.
+ */
+class KeccakGoodRng : public KeccakRng {
+public:
+ /// Initialize and seed the generator from a system specific nondeterministic random source.
+ explicit KeccakGoodRng () : KeccakRng (192, 13) { auto_seed(); }
+ /// Initialize and seed the generator from @a seed_sequence.
+ template<class SeedSeq>
+ explicit KeccakGoodRng (SeedSeq &seed_sequence) : KeccakRng (192, 13) { seed (seed_sequence); }
+};
+
+/** KeccakFastRng - A KeccakF1600 based fast pseudo-random number generator.
+ * This class tunes the KeccakF1600 algorithm for best performance in pseudo random
+ * number generation. Performance is improved while still retaining quality random
+ * number generation, according to the findings in seciton "4.1.1 Statistical tests"
+ * from http://keccak.noekeon.org/Keccak-reference-3.0.pdf.
+ */
+class KeccakFastRng : public KeccakRng {
+public:
+ /// Initialize and seed the generator from a system specific nondeterministic random source.
+ explicit KeccakFastRng () : KeccakRng (128, 8) { auto_seed(); }
+ /// Initialize and seed the generator from @a seed_sequence.
+ template<class SeedSeq>
+ explicit KeccakFastRng (SeedSeq &seed_sequence) : KeccakRng (128, 8) { seed (seed_sequence); }
+};
+
+/** Pcg32Rng is a permutating linear congruential PRNG.
+ * At the core, this pseudo random number generator uses the well known
+ * linear congruential generator:
+ * 6364136223846793005 * accumulator + 1442695040888963407 mod 2^64.
+ * See also TAOCP by D. E. Knuth, section 3.3.4, table 1, line 26.
+ * For good statistical performance, the output function of the permuted congruential
+ * generator family is used as described on http://www.pcg-random.org/.
+ * Period length for this generator is 2^64, the specified seed @a offset
+ * chooses the position of the genrator and the seed @a sequence parameter
+ * can be used to choose from 2^63 distinct random sequences.
+ */
+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));
+ }
+ 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:
+ /// Initialize and seed from @a seed_sequence.
+ template<class SeedSeq>
+ explicit Pcg32Rng (SeedSeq &seed_sequence) : increment_ (0), accu_ (0) { seed (seed_sequence); }
+ /// Initialize and seed by seeking to position @a offset within stream @a sequence.
+ explicit Pcg32Rng (uint64_t offset, uint64_t sequence);
+ /// Initialize and seed the generator from a system specific nondeterministic random source.
+ explicit Pcg32Rng ();
+ /// Seed the generator from a system specific nondeterministic random source.
+ void auto_seed ();
+ /// Seed by seeking to position @a offset within stream @a sequence.
+ void seed (uint64_t offset, uint64_t sequence);
+ /// Seed the generator state from a @a seed_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]);
+ }
+ /// Generate uniformly distributed 32 bit pseudo random number.
+ 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 ==
+/** Simple, very fast and well known hash function as constexpr with good dispersion.
+ * This is the 64bit version of the well known
+ * [FNV-1a](https://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function)
+ * hash function, implemented as a C++11 constexpr for zero-terminated
+ * strings, so the hashes can be used e.g. as case labels in switch statements.
+ */
+template<class Num> static inline constexpr uint64_t
+fnv1a_consthash64 (const Num *const ztdata, uint64_t hash = 0xcbf29ce484222325)
+{
+ static_assert (sizeof (Num) <= 1, "");
+ return BSE_ISLIKELY (ztdata[0] != 0) ? fnv1a_consthash64 (ztdata + 1, 0x100000001b3 * (hash ^ uint8_t
(ztdata[0]))) : hash;
+}
+
+/** Hash function based on the PCG family of random number generators (RNG).
+ * This function is based on the paper [PCG: A Family of Simple Fast
+ * Space-Efficient Statistically Good Algorithms for Random Number
+ * Generation](http://www.pcg-random.org/paper.html),
+ * because of its excellent avalange and distribution properties.
+ * The hash data is integrated as octets in the inner LCG RNG loop.
+ * Hash generation is very fast, because the inner loop consists only of a
+ * multiplication and subtraction, while the ouput bit mixing consists of
+ * just 5 simple operations (xor, shift and rotation).
+ */
+template<class Num> static BSE_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; BSE_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;
+}
+
+/** Hash function based on the PCG family of random number generators (RNG).
+ * This function is similar to pcg_hash32() at its core, but because the
+ * output is 64bit, the accumulated 64bit LCG state does not need to be
+ * bit reduced. A fast but statistially good mixing function with
+ * 5 xor/shifts and one multiplication is applied as output stage.
+ * This function is allmost as fast as fnv1a_consthash64 due to the similar
+ * structures of the inner loops, but it tends to score much better in
+ * [Avalanche effect](https://en.wikipedia.org/wiki/Avalanche_effect)
+ * tests, usch as [SMHasher](https://code.google.com/p/smhasher/).
+ */
+template<class Num> static BSE_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; BSE_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;
+}
+
+/// pcg_hash64() variant for zero-terminated strings.
+static BSE_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; BSE_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; ///< Use hash_secret() for access.
+
+/// Provide hashing nonce for reseeding hashes at program start to avoid collision attacks.
+static BSE_PURE inline uint64_t
+hash_secret ()
+{
+ if (BSE_UNLIKELY (cached_hash_secret == 0))
+ random_secret (&cached_hash_secret);
+ return cached_hash_secret;
+}
+
+/// Fast byte hashing with good dispersion and runtime randomization.
+template<class Num> static BSE_CONST inline uint64_t
+byte_hash64 (const Num *data, size_t length)
+{
+ static_assert (sizeof (Num) <= 1, "");
+ return pcg_hash64 (data, length, hash_secret());
+}
+
+/// Fast string hashing with good dispersion for std::string and runtime randomization.
+static BSE_CONST inline uint64_t
+string_hash64 (const std::string &string)
+{
+ return pcg_hash64 (string.data(), string.size(), hash_secret());
+}
+
+/// pcg_hash64() variant for zero-terminated strings.
+static BSE_CONST inline uint64_t
+string_hash64 (const char *ztdata)
+{
+ return pcg_hash64 (ztdata, hash_secret());
+}
+
+} // Bse
+
+#endif // __BSE_RANDOMHASH_HH__
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
