bslh_wyhashincrementalalgorithm.h

Go to the documentation of this file.

/// @file bslh_wyhashincrementalalgorithm.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslh_wyhashincrementalalgorithm.h                                  -*-C++-*-
#ifndef INCLUDED_BSLH_WYHASHINCREMENTALALGORITHM
#define INCLUDED_BSLH_WYHASHINCREMENTALALGORITHM
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslh_wyhashincrementalalgorithm bslh_wyhashincrementalalgorithm
/// @brief  Provide an implementation of the WyHash algorithm final v3.
/// @addtogroup bsl
/// @{
/// @addtogroup bslh
/// @{
/// @addtogroup bslh_wyhashincrementalalgorithm
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslh_wyhashincrementalalgorithm-purpose"> Purpose</a>
/// * <a href="#bslh_wyhashincrementalalgorithm-classes"> Classes </a>
/// * <a href="#bslh_wyhashincrementalalgorithm-description"> Description </a>
///   * <a href="#bslh_wyhashincrementalalgorithm-security"> Security </a>
///     * <a href="#bslh_wyhashincrementalalgorithm-denial-of-service-protection"> Denial of Service (DoS) Protection </a>
///   * <a href="#bslh_wyhashincrementalalgorithm-hash-distribution"> Hash Distribution </a>
///   * <a href="#bslh_wyhashincrementalalgorithm-alignment-independence"> Alignment-Independence </a>
///   * <a href="#bslh_wyhashincrementalalgorithm-subdivision-invariance"> Subdivision-Invariance </a>
///   * <a href="#bslh_wyhashincrementalalgorithm-speed"> Speed </a>
///   * <a href="#bslh_wyhashincrementalalgorithm-usage"> Usage </a>
///     * <a href="#bslh_wyhashincrementalalgorithm-example-creating-and-using-a-hash-table"> Example: Creating and Using a Hash Table </a>
///
/// # Purpose {#bslh_wyhashincrementalalgorithm-purpose}
/// Provide an implementation of the WyHash algorithm final v3.
///
/// # Classes {#bslh_wyhashincrementalalgorithm-classes}
///
/// -  bslh::WyHashIncrementalAlgorithm: functor implementing the WyHash algorithm
///
/// @see  bslh_hash
///
/// # Description {#bslh_wyhashincrementalalgorithm-description}
/// `bslh::WyHashIncrementalAlgorithm` implements the WyHash
/// algorithm by Wang Yi et al (see implementation file for full list of
/// authors) with modifications.  This algorithm is known to be very fast yet
/// have good avalanche behavior.
///
/// The original algorithm was downloaded from
/// https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h which had been
/// updated on September 14, 2021, last commit 166f352, and modified to conform
/// to BDE coding conventions with no change in the binary results produced.
///
/// The modifications are:
/// * A property is added that hashing a segment in one pass will yeild the
///   same result as hashing it in pieces.
/// * Byte-swapping is eliminated for speed, and therefore the algorithm yields
///   different results depending on the byte-order of the host.
///
/// ## Security {#bslh_wyhashincrementalalgorithm-security}
///
///
/// WyHash is *not* a "Cryptographically Secure" hash.  It is "Cryptographically
/// Strong", but not "Cryptographically Secure".  In order to be
/// cryptographically secure, an algorithm must, among other things, provide
/// "Collision Resistance", described in
/// https://en.wikipedia.org/wiki/Collision_resistance , meaning that it should
/// be difficult to find two different messages `m1` and `m2` such that
/// `hash(m1) == hash(m2)`.  Because of the limited sized output (only 2**64
/// possibilities) and the fast execution time of the algorithm, it is probable
/// to find two such values searching only about `sqrt(2**64) == 2**32` inputs,
/// which wont take long.
///
/// WyHash *is*, however, a cryptographically strong PRF (pseudo-random
/// function).  This means, assuming a cryptographically secure random seed is
/// given, the output of this algorithm will be indistinguishable from a uniform
/// random distribution.  This property is enough for the algorithm to be able
/// to protect a hash table from malicious Denial of Service (DoS) attacks.
///
/// ### Denial of Service (DoS) Protection {#bslh_wyhashincrementalalgorithm-denial-of-service-protection}
///
///
/// Given a cryptographically secure seed, this algorithm will produce hashes
/// with a distribution that is indistinguishable from random.  This
/// distribution means that there is no way for an attacker to predict which
/// keys will cause collisions, meaning that this algorithm can help mitigate
/// Denial of Service (DoS) attacks on a hash table.  DoS attacks occur when an
/// attacker deliberately degrades the performance of the hash table by
/// inserting data that will collide to the same bucket, causing an average
/// constant time lookup to become a linear search.  This protection is only
/// effective if the seed provided is a cryptographically secure random number
/// that is not available to the attacker.
///
/// ## Hash Distribution {#bslh_wyhashincrementalalgorithm-hash-distribution}
///
///
/// Output hashes will be well distributed and will avalanche, which means
/// changing one bit of the input will change approximately 50% of the output
/// bits.  This will prevent similar values from funneling to the same hash or
/// bucket.
///
/// ## Alignment-Independence {#bslh_wyhashincrementalalgorithm-alignment-independence}
///
///
/// The value obtained by hashing a segment of memory is independent of the
/// alignment of the segment of memory.
///
/// ## Subdivision-Invariance {#bslh_wyhashincrementalalgorithm-subdivision-invariance}
///
///
/// Note that this algorithm is *subdivision-invariant* (see
/// {@ref bslh_hash |Subdivision-Invariance}).
///
/// ## Speed {#bslh_wyhashincrementalalgorithm-speed}
///
///
/// This algorithm is at least 2X faster than Spooky on all sizes of objects on
/// Linux, Windows, and Solaris.  On Aix it is about twice as fast as Spooky on
/// small objects and about 50% slower on large objects.
///
/// ## Usage {#bslh_wyhashincrementalalgorithm-usage}
///
///
/// This section illustrates intended usage of this component.
///
/// ### Example: Creating and Using a Hash Table {#bslh_wyhashincrementalalgorithm-example-creating-and-using-a-hash-table}
///
///
/// Suppose we have any array of types that define `operator==`, and we want a
/// fast way to find out if values are contained in the array.  We can create a
/// `HashTable` data structure that is capable of looking up values in O(1)
/// time.
///
/// Further suppose that we will be storing futures (the financial instruments)
/// in this table.  Since futures have standardized names, we don't have to
/// worry about any malicious values causing collisions.  We will want to use a
/// general purpose hashing algorithm with a good hash distribution and good
/// speed.  This algorithm will need to be in the form of a hash functor -- an
/// object that will take objects stored in our array as input, and yield a
/// 64-bit int value.  The functor can pass the attributes of the `TYPE` that
/// are salient to hashing into the hashing algorithm, and then return the hash
/// that is produced.
///
/// We can use the result of the hash function to index into our array of
/// `buckets`.  Each `bucket` is simply a pointer to a value in our original
/// array of `TYPE` objects.
///
/// First, we define our `HashTable` template class, with the two type
/// parameters: `TYPE` (the type being referenced) and `HASHER` (a functor that
/// produces the hash).
/// @code
/// template <class TYPE, class HASHER>
/// class HashTable {
/// @endcode
/// This `class template` implements a hash table providing fast lookup of an
/// external, non-owned, array of values of (template parameter) `TYPE`.
///
/// The (template parameter) `TYPE` shall have a transitive, symmetric
/// `operator==` function.  There is no requirement that it have any kind of
/// creator defined.
///
/// The `HASHER` template parameter type must be a functor with a method having
/// the following signature:
/// @code
/// size_t operator()(TYPE)  const;
///                  -OR-
/// size_t operator()(const TYPE&) const;
/// @endcode
/// and `HASHER` shall have a publicly accessible default constructor and
/// destructor.
///
/// Note that this hash table has numerous simplifications because we know the
/// size of the array and never have to resize the table.
/// @code
///     // DATA
///     const TYPE       *d_values;          // Array of values table is to
///                                          // hold
///     size_t            d_numValues;       // Length of 'd_values'.
///     const TYPE      **d_bucketArray;     // Contains ptrs into 'd_values'
///     size_t            d_bucketArrayMask; // Will always be '2^N - 1'.
///     HASHER            d_hasher;          // User supplied hashing algorithm
///
///   private:
///     // PRIVATE ACCESSORS
///     bool lookup(size_t      *idx,
///                 const TYPE&  value,
///                 size_t       hashValue) const;
///         // Look up the specified 'value', having the specified 'hashValue',
///         // and load its index in 'd_bucketArray' into the specified 'idx'.
///         // If not found, return the vacant entry in 'd_bucketArray' where
///         // it should be inserted.  Return 'true' if 'value' is found and
///         // 'false' otherwise.
///
///   public:
///     // CREATORS
///     HashTable(const TYPE *valuesArray,
///               size_t      numValues);
///         // Create a hash table referring to the specified 'valuesArray'
///         // having length of the specified 'numValues'.  No value in
///         // 'valuesArray' shall have the same value as any of the other
///         // values in 'valuesArray'
///
///     ~HashTable();
///         // Free up memory used by this hash table.
///
///     // ACCESSORS
///     bool contains(const TYPE& value) const;
///         // Return true if the specified 'value' is found in the table and
///         // false otherwise.
/// };
///
/// // PRIVATE ACCESSORS
/// template <class TYPE, class HASHER>
/// bool HashTable<TYPE, HASHER>::lookup(size_t      *idx,
///                                      const TYPE&  value,
///                                      size_t       hashValue) const
/// {
///     const TYPE *ptr;
///     for (*idx = hashValue & d_bucketArrayMask; (ptr = d_bucketArray[*idx]);
///                                    *idx = (*idx + 1) & d_bucketArrayMask) {
///         if (value == *ptr) {
///             return true;                                          // RETURN
///         }
///     }
///
///     // value was not found in table
///
///     return false;
/// }
///
/// // CREATORS
/// template <class TYPE, class HASHER>
/// HashTable<TYPE, HASHER>::HashTable(const TYPE *valuesArray,
///                                    size_t      numValues)
/// : d_values(valuesArray)
/// , d_numValues(numValues)
/// , d_hasher()
/// {
///     size_t bucketArrayLength = 4;
///     while (bucketArrayLength < numValues * 4) {
///         bucketArrayLength *= 2;
///
///     }
///     d_bucketArrayMask = bucketArrayLength - 1;
///     d_bucketArray = new const TYPE *[bucketArrayLength];
///     memset(d_bucketArray,  0, bucketArrayLength * sizeof(TYPE *));
///
///     for (unsigned i = 0; i < numValues; ++i) {
///         const TYPE& value = d_values[i];
///         size_t idx;
///         const bool found = lookup(&idx, value, d_hasher(value));
///         BSLS_ASSERT_OPT(!found);    (void) found;
///         d_bucketArray[idx] = &d_values[i];
///     }
/// }
///
/// template <class TYPE, class HASHER>
/// HashTable<TYPE, HASHER>::~HashTable()
/// {
///     delete [] d_bucketArray;
/// }
///
/// // ACCESSORS
/// template <class TYPE, class HASHER>
/// bool HashTable<TYPE, HASHER>::contains(const TYPE& value) const
/// {
///     size_t idx;
///     return lookup(&idx, value, d_hasher(value));
/// }
/// @endcode
/// Then, we define a `Future` class, which holds a c-string `name`, char
/// `callMonth`, and short `callYear`.
/// @code
/// class Future {
/// @endcode
/// This `class` identifies a future contract.  It tracks the name, call month
/// and year of the contract it represents, and allows equality comparison.
/// @code
///     // DATA
///     const char *d_name;    // held, not owned
///     const char  d_callMonth;
///     const short d_callYear;
///
///   public:
///     // CREATORS
///     Future(const char *name, const char callMonth, const short callYear)
///     : d_name(name), d_callMonth(callMonth), d_callYear(callYear)
///         // Create a 'Future' object out of the specified 'name',
///         // 'callMonth', and 'callYear'.
///     {}
///
///     Future() : d_name(""), d_callMonth('\0'), d_callYear(0)
///         // Create a 'Future' with default values.
///     {}
///
///     // ACCESSORS
///     const char * getMonth() const
///         // Return the month that this future expires.
///     {
///         return &d_callMonth;
///     }
///
///     const char * getName() const
///         // Return the name of this future
///     {
///         return d_name;
///     }
///
///     const short * getYear() const
///         // Return the year that this future expires
///     {
///         return &d_callYear;
///     }
///
///     bool operator==(const Future& rhs) const
///         // Compare this to the specified 'other' object and return true if
///         // they are equal
///     {
///         return (!strcmp(d_name, rhs.d_name)) &&
///                                           d_callMonth == rhs.d_callMonth &&
///                                           d_callYear  == rhs.d_callYear;
///     }
/// };
///
/// bool operator!=(const Future& lhs, const Future& rhs)
///     // Compare compare the specified 'lhs' and 'rhs' objects and return
///     // true if they are not equal
/// {
///     return !(lhs == rhs);
/// }
/// @endcode
/// Next, we need a hash functor for `Future`.  We are going to use the
/// `SpookyHashAlgorithm` because it is a fast, general purpose hashing
/// algorithm that will provide an easy way to combine the attributes of
/// `Future` objects that are salient to hashing into one reasonable hash that
/// will distribute the items evenly throughout the hash table.
/// @code
/// struct HashFuture {
///     // This struct is a functor that will apply the 'SpookyHashAlgorithm'
///     // to objects of type 'Future'.
///
///     bsls::Types::Uint64 d_seed;
///
///     HashFuture()
///     {
///         // Generate random bits in 'd_seed' based on the time of day in
///         // nanoseconds.
///
///         bsls::Types::Uint64 nano =
///                   bsls::SystemTime::nowMonotonicClock().totalNanoseconds();
///         const int iterations = static_cast<int>(nano & 7) + 1;
///         for (int ii = 0; ii < iterations; ++ii) {
///             nano *= bsls::SystemTime::nowMonotonicClock().
///                                                         totalNanoseconds();
///             nano += nano >> 32;
///         }
///
///         BSLMF_ASSERT(sizeof(d_seed) <= sizeof(nano));
///
///         memcpy(&d_seed, &nano, sizeof(d_seed));
///     }
///
///     // MANIPULATOR
///     size_t operator()(const Future& future) const
///         // Return the hash of the of the specified 'future'.  Note that
///         // this uses the 'SpookyHashAlgorithm' to quickly combine the
///         // attributes of 'Future' objects that are salient to hashing into
///         // a hash suitable for a hash table.
///     {
///         bslh::WyHashIncrementalAlgorithm hash(d_seed);
///
///         hash(future.getName(),  strlen(future.getName()));
///         hash(future.getMonth(), sizeof(char));
///         hash(future.getYear(),  sizeof(short));
///
///         return static_cast<size_t>(hash.computeHash());
///     }
/// };
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslh
 * @{
 */
/** @addtogroup bslh_wyhashincrementalalgorithm
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bslmf_assert.h>
#include <bslmf_isbitwisecopyable.h>
 
#include <bsls_assert.h>
#include <bsls_byteorder.h>
#include <bsls_keyword.h>
#include <bsls_performancehint.h>
#include <bsls_types.h>
 
#include <algorithm>
 
#include <stddef.h>  // for 'size_t'
#include <stdint.h>  // for 'uint64_t'
#include <string.h>  // for 'memcpy'
 
#if defined(_MSC_VER) && defined(_M_X64)
#include <intrin.h>
#pragma intrinsic(_umul128)
#endif
 
// protections that produce different results:
 
//: 0 normal valid behavior
//:
//: 1 extra protection against entropy loss (probability=2^-63), aka.  "blind
//:   multiplication"
 
#undef  BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_XOR
#define BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_XOR 0
 
//: 0 normal, real version of 64x64 -> 128 multiply, slow on 32 bit systems
//:
//: 1 not real multiply, faster on 32 bit systems but produces different
//:   results
 
#undef  BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_PSEUDO_MULTIPLY
#define BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_PSEUDO_MULTIPLY 0
 
 
namespace bslh {
 
                    // ======================================
                    // class bslh::WyHashIncrementalAlgorithm
                    // ======================================
 
/// This class wraps an implementation of the "WyHash" hash algorithm in an
/// interface that is usable in the modular hashing system in `bslh`.
///
/// See @ref bslh_wyhashincrementalalgorithm 
class WyHashIncrementalAlgorithm {
 
  private:
    // PRIVATE TYPES
    enum { k_PREPAD_LENGTH = 16,                       // See implementation
           k_PREPAD_LENGTH_RAW = k_PREPAD_LENGTH - 1,  // notes in the imp file
           k_REPEAT_LENGTH = 48 };
 
  public:
    // TYPES
 
    /// Typedef indicating the value type returned by this algorithm.
    typedef bsls::Types::Uint64 result_type;
 
    enum { k_SEED_LENGTH = sizeof(uint64_t) };
 
  private:
    // DATA
    uint64_t d_initialSeed, d_seed, d_see1, d_see2; // seeds, state of the hash
                                                    // computation
 
    bool     d_last16AtEnd;                         // indicates that the last
                                                    // 16 bytes at the end of
                                                    // the repeat buf are valid
 
    uint8_t  d_buffer[k_PREPAD_LENGTH_RAW + k_REPEAT_LENGTH];
                                                    // prePad + repeat buffer,
                                                    // not including the first
                                                    // (never used) byte.  See
                                                    // the implementation notes
                                                    // in the imp file
 
    size_t   d_totalLen;                            // total length of input so
                                                    // far
 
    // CLASS DATA
 
    // These values for 's_secret*' were copied directly from the original
    // github source.
 
    static const uint64_t s_secret0 = 0xa0761d6478bd642full;
    static const uint64_t s_secret1 = 0xe7037ed1a0b428dbull;
    static const uint64_t s_secret2 = 0x8ebc6af09c88c6e3ull;
    static const uint64_t s_secret3 = 0x589965cc75374cc3ull;
 
  private:
    // NOT IMPLEMENTED
    WyHashIncrementalAlgorithm(const WyHashIncrementalAlgorithm&)
                                                          BSLS_KEYWORD_DELETED;
    WyHashIncrementalAlgorithm& operator=(const WyHashIncrementalAlgorithm&)
                                                          BSLS_KEYWORD_DELETED;
 
  private:
    // PRIVATE CLASS METHODS
#if BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_PSEUDO_MULTIPLY
    static uint64_t _wyrot(uint64_t x);
        // Return the specified 'x' with the high- and low-order 32 bits
        // swapped.
#endif
 
    /// Multiply the specified `*a_p` and `*b_p`, yielding a 128 bit result,
    /// when `*b_p` will contain the high 64 bits and `*a_p` will contain
    /// the low 64 bits of the result.  This may be configured through
    /// conditional switches to perform a faster function other than
    /// multiply.
    static void _wymum(uint64_t *a_p, uint64_t *b_p);
 
    /// Do a 64x64 -> 128 bit multiply of the specified `a` and `b`, then
    /// then return the bitwise-xor of the high and low 64-bits.
    static uint64_t _wymix(uint64_t a, uint64_t b);
 
    /// Read 8 bytes, native-endian.  Note that `p` might not be aligned.
    static uint64_t _wyr8(const uint8_t *p);
 
    /// Read 4 bytes, native-endian,  Note that `p` might not be aligned.
    static uint64_t _wyr4(const uint8_t *p);
 
    /// Read a mix of the specified `k` bytes beginning at the specified
    /// `p`, where `k` is in the range `[ 1 .. 3 ]`.
    static uint64_t _wyr3(const uint8_t *p, size_t k);
 
    // PRIVATE MANIPULATORS
 
    /// Return a ptr to the address at the specified `offset` after the
    /// beginning of the `prepad` area of the buffer.  The behavior is
    /// undefined unless `1 <= offset`.
    uint8_t *prePadAt(ptrdiff_t offset);
 
    /// Process the specified `k_REPEAT_LENGTH`-byte `buffer`.  Note that
    /// this function is called only when there is additional input beyond
    /// the buffer.
    void process48ByteSection(const uint8_t *buffer);
 
    /// Return a pointer to the beginning of the repeated buffer area.
    uint8_t *repeatBufferBegin();
 
    /// Return a pointer past the end of the buffer.
    uint8_t *repeatBufferEnd();
 
  public:
    // CREATORS
 
    /// Create a `WyHashIncrementalAlgorithm` using a default initial seed.
    WyHashIncrementalAlgorithm();
 
    /// Create a `bslh::WyHashIncrementalAlgorithm`, seeded with the
    /// specified `seed`.
    explicit WyHashIncrementalAlgorithm(uint64_t seed);
 
    /// Create a `bslh::WyHashIncrementalAlgorithm`, seeded with
    /// `k_SEED_LENGTH` bytes of data starting at the specified `seed`.
    explicit WyHashIncrementalAlgorithm(const char *seed);
 
     ~WyHashIncrementalAlgorithm() = default;
        // Destroy this object.
 
    // MANIPULATORS
 
    /// Incorporate the specified `data`, of at least the specified
    /// `numBytes`, into the internal state of the hashing algorithm.  Every
    /// bit of data incorporated into the internal state of the algorithm
    /// will contribute to the final hash produced by `computeHash()`.  The
    /// same hash value will be produced regardless of whether a sequence of
    /// bytes is passed in all at once or through multiple calls to this
    /// member function.  Input where `numBytes` is 0 will have no effect on
    /// the internal state of the algorithm.  The behaviour is undefined
    /// unless `data` points to a valid memory location with at least
    /// `numBytes` bytes of initialized memory or `numBytes` is zero.
    void operator()(const void *data, size_t numBytes);
 
    /// Return the finalized version of the hash that has been accumulated.
    /// Note that this changes the internal state of the object, so calling
    /// `computeHash()` multiple times in a row will return different
    /// results, and only the first result returned will match the expected
    /// result of the algorithm.  Also note that a value will be returned,
    /// even if data has not been passed into `operator()`
    result_type computeHash();
};
 
// ============================================================================
//                            INLINE DEFINITIONS
// ============================================================================
 
                        // --------------------------
                        // WyHashIncrementalAlgorithm
                        // --------------------------
 
// PRIVATE CLASS METHODS
#if BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_PSEUDO_MULTIPLY
inline
uint64_t WyHashIncrementalAlgorithm::_wyrot(uint64_t x)
{
    return (x >> 32) | (x << 32);
}
#endif
 
inline
void WyHashIncrementalAlgorithm::_wymum(uint64_t *a_p, uint64_t *b_p)
{
#if BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_PSEUDO_MULTIPLY
    const uint64_t hh = (*a_p >> 32) * (*b_p >> 32);
    const uint64_t hl = (*a_p >> 32) * static_cast<uint32_t>(*b_p);
    const uint64_t lh = static_cast<uint32_t>(*a_p) * (*b_p >> 32);
    const uint64_t ll = static_cast<uint64_t>(static_cast<uint32_t>(*a_p)) *
                                                   static_cast<uint32_t>(*b_p);
 
#if BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_XOR
    // pseudo munge (not real multiply) -> xor
 
    *a_p ^= _wyrot(hl) ^ hh;
    *b_p ^= _wyrot(lh) ^ ll;
#else
    // pseudo munge (not real multiply)
 
    *a_p = _wyrot(hl) ^ hh;
    *b_p = _wyrot(lh) ^ ll;
#endif
#elif defined(__SIZEOF_INT128__)
    __uint128_t r = *a_p;
    r *= *b_p;
 
#if BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_XOR
    // multiply -> xor
 
    *a_p ^= static_cast<uint64_t>(r);
    *b_p ^= static_cast<uint64_t>(r >> 64);
#else
    // multiply
 
    *a_p = static_cast<uint64_t>(r);
    *b_p = static_cast<uint64_t>(r >> 64);
#endif
#elif defined(_MSC_VER) && defined(_M_X64)
#if BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_XOR
    // multiply -> xor
 
    uint64_t a, b;
    a = _umul128(*a_p, *b_p, &b);
    *a_p ^= a;
    *b_p ^= b;
#else
    // multiply
 
    *a_p = _umul128(*a_p, *b_p, b_p);
#endif
#else
    const uint64_t ha = *a_p >> 32, hb = *b_p >> 32;
    const uint64_t la = static_cast<uint32_t>(*a_p);
    const uint64_t lb = static_cast<uint32_t>(*b_p);
 
    const uint64_t rh = ha * hb, rl = la * lb;
    const uint64_t rm0 = ha * lb, rm1 = hb * la;
    const uint64_t t = rl + (rm0 << 32);
 
    const uint64_t lo = t + (rm1 << 32);
    const uint64_t hi = rh + (rm0 >> 32) + (rm1 >> 32) + (t < rl) + (lo < t);
 
#if BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_XOR
    // multiply -> xor
 
    *a_p ^= lo;
    *b_p ^= hi;
#else
    // multiply
 
    *a_p = lo;
    *b_p = hi;
#endif
#endif
}
 
//multiply and xor mix function, aka MUM
inline
uint64_t WyHashIncrementalAlgorithm::_wymix(uint64_t a, uint64_t b)
{
    _wymum(&a, &b);
    return a ^ b;
}
 
//read functions
inline
uint64_t WyHashIncrementalAlgorithm::_wyr8(const uint8_t *p)
{
    uint64_t v;
    memcpy(&v, p, 8);
    return v;
}
 
inline
uint64_t WyHashIncrementalAlgorithm::_wyr4(const uint8_t *p)
{
    uint32_t v;
    memcpy(&v, p, 4);
    return v;
}
 
/// Read a mix of the `k` bytes beginning at `p`, where `k` is in the range
/// `[ 1 .. 3 ]`.
inline
uint64_t WyHashIncrementalAlgorithm::_wyr3(const uint8_t *p, size_t k)
{
    BSLS_ASSERT_SAFE(1 <= k && k <= 3);
 
    return (static_cast<uint64_t>(p[0]) << 16) |
           (static_cast<uint64_t>(p[k >> 1]) << 8) |
           p[k - 1];
}
 
// PRIVATE MANIPULATORS
inline
uint8_t *WyHashIncrementalAlgorithm::prePadAt(ptrdiff_t offset)
{
    BSLMF_ASSERT(sizeof(d_last16AtEnd) == 1);    // see implementation doc
    BSLS_ASSERT_SAFE(1 <= offset);
 
    return d_buffer + offset - 1;
}
 
inline
void WyHashIncrementalAlgorithm::process48ByteSection(const uint8_t *buffer)
{
    d_seed = _wymix(_wyr8(buffer)      ^ s_secret1,
                    _wyr8(buffer +  8) ^ d_seed);
    d_see1 = _wymix(_wyr8(buffer + 16) ^ s_secret2,
                    _wyr8(buffer + 24) ^ d_see1);
    d_see2 = _wymix(_wyr8(buffer + 32) ^ s_secret3,
                    _wyr8(buffer + 40) ^ d_see2);
}
 
inline
uint8_t *WyHashIncrementalAlgorithm::repeatBufferBegin()
{
    return d_buffer + k_PREPAD_LENGTH_RAW;
}
 
inline
uint8_t *WyHashIncrementalAlgorithm::repeatBufferEnd()
{
    return d_buffer + sizeof(d_buffer);
}
 
// CREATORS
inline
WyHashIncrementalAlgorithm::WyHashIncrementalAlgorithm()
: d_initialSeed(0x50defacedfacade5ULL)
, d_last16AtEnd(false)
, d_totalLen(0)
{
    BSLMF_ASSERT(sizeof(*this) == 13 * sizeof(uint64_t) ||
                 sizeof(*this) == 12 * sizeof(uint64_t) + sizeof(size_t));
 
    d_seed = d_initialSeed ^ s_secret0;
}
 
inline
WyHashIncrementalAlgorithm::WyHashIncrementalAlgorithm(uint64_t seed)
: d_initialSeed(seed)
, d_last16AtEnd(false)
, d_totalLen(0)
{
    BSLMF_ASSERT(sizeof(d_initialSeed) == sizeof(seed));
    d_seed = d_initialSeed ^ s_secret0;
}
 
inline
WyHashIncrementalAlgorithm::WyHashIncrementalAlgorithm(const char *seed)
: d_last16AtEnd(false)
, d_totalLen(0)
{
    BSLMF_ASSERT(sizeof(d_initialSeed) == k_SEED_LENGTH);
 
    memcpy(&d_initialSeed, seed, sizeof(d_initialSeed));
 
    d_seed = d_initialSeed ^ s_secret0;
}
 
// MANIPULATORS
inline
void WyHashIncrementalAlgorithm::operator()(const void *data, size_t numBytes)
{
    if (0 == numBytes) {
        // In all cases when '0 == numBytes', all we do is a 'memcpy' of 0
        // length, which is a no-op.  In the cases where '0 == data' (for
        // example, hashing a default-constructed 'bsl::string_view') this
        // 'memcpy' gets 'p' (0) passed to the second arg, which is technically
        // UB.  To avoid this UB, just return.
 
        return;                                                       // RETURN
    }
    else {
        BSLS_ASSERT_SAFE(0 != data);
    }
 
    const uint8_t *p   = static_cast<const uint8_t *>(data);
    const uint8_t *end = p + numBytes;
 
    const size_t   origLen = d_totalLen;
    size_t         repeatBufNumBytes = origLen % k_REPEAT_LENGTH;
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(!repeatBufNumBytes && origLen)) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        repeatBufNumBytes = k_REPEAT_LENGTH;
    }
 
    d_totalLen = origLen + numBytes;
 
    if (0 != repeatBufNumBytes) {
        const ptrdiff_t remainingSpaceInBuf = k_REPEAT_LENGTH -
                                                             repeatBufNumBytes;
        if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(end - p <=
                                                        remainingSpaceInBuf)) {
            memcpy(repeatBufferBegin() + repeatBufNumBytes, p, end - p);
 
            // Leave 'd_last16AtEnd' alone.
 
            return;                                                   // RETURN
        }
        else {
            BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
            if (origLen <= k_REPEAT_LENGTH) {
                d_see1 = d_see2 = d_seed;
            }
 
            memcpy(repeatBufferBegin() + repeatBufNumBytes,
                   p,
                   remainingSpaceInBuf);
 
            p += remainingSpaceInBuf;
            process48ByteSection(repeatBufferBegin());
 
            d_last16AtEnd = true;
        }
    }
 
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(k_REPEAT_LENGTH < end - p)) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        if (0 == origLen) {
            d_see1 = d_see2 = d_seed;
        }
 
        do {
            process48ByteSection(p);
            p += k_REPEAT_LENGTH;
        } while (k_REPEAT_LENGTH < end - p);
 
        d_last16AtEnd = false;
 
        const ptrdiff_t remOffset = end - p;
        if (remOffset < 16) {
            BSLS_ASSERT_SAFE(0 < remOffset);
 
            // We say 'p + remOffset - 16' rather than 'end - 16' below because
            // the latter caused an inaccurate warning which could not be
            // silenced via pragmas.
 
            memcpy(prePadAt(remOffset), p + remOffset - 16, 16);
 
            return;                                                   // RETURN
        }
    }
 
    memcpy(repeatBufferBegin(), p, end - p);
}
 
inline
WyHashIncrementalAlgorithm::result_type
WyHashIncrementalAlgorithm::computeHash()
{
    BSLMF_ASSERT(sizeof(result_type) == sizeof(d_seed));
 
    uint8_t *p = repeatBufferBegin();
 
    uint64_t a, b, seed = d_seed;
 
    const size_t len = d_totalLen;
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(len <= 16)) {
        if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(len >= 4)) {
            const size_t subLen = (len >> 3) << 2;
 
            a = (_wyr4(p) << 32) | _wyr4(p + subLen);
            b = (_wyr4(p + len - 4) << 32) | _wyr4(p + len - 4 - subLen);
        }
        else if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(len > 0)) {
            a = _wyr3(p, len);
            b = 0;
        }
        else {
            BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
            a = b = 0;
        }
    }
    else {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        size_t totalLenRemainder = len % k_REPEAT_LENGTH;
        if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(0 == totalLenRemainder)) {
            BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
            totalLenRemainder = k_REPEAT_LENGTH;
        }
        uint8_t *end = p + totalLenRemainder;
 
        if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(k_REPEAT_LENGTH < len)) {
            BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
            seed ^= d_see1 ^ d_see2;
        }
 
        while (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(end - p > 16)) {
            BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
            seed = _wymix(_wyr8(p) ^ s_secret1, _wyr8(p + 8) ^ seed);
            p += 16;
        }
 
        const ptrdiff_t offset = end - repeatBufferBegin() - k_PREPAD_LENGTH;
        if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(offset < 0 &&
                                                              d_last16AtEnd)) {
            BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
            BSLS_ASSERT_SAFE(k_REPEAT_LENGTH < len);
            memcpy(repeatBufferBegin() + offset,
                   repeatBufferEnd() + offset,
                   -offset);
        }
 
        a = _wyr8(end - 16);
        b = _wyr8(end - 8);
    }
 
    return d_initialSeed ^ _wymix(s_secret1 ^ len,
                                              _wymix(a ^ s_secret1, b ^ seed));
}
 
}  // close package namespace
 
 
// ============================================================================
//                                TYPE TRAITS
// ============================================================================
 
 
namespace bslmf {
template <>
struct IsBitwiseCopyable<
                BloombergLP::bslh::WyHashIncrementalAlgorithm> : bsl::true_type
{};
}  // close namespace bslmf
 
 
#undef BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_PSEUDO_MULTIPLY
#undef BSLH_WYHASHINCREMENTALALGORITHM_WYMUM_XOR
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2022 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */