bslh_spookyhashalgorithmimp.h

Go to the documentation of this file.

/// @file bslh_spookyhashalgorithmimp.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslh_spookyhashalgorithmimp.h                                      -*-C++-*-
#ifndef INCLUDED_BSLH_SPOOKYHASHALGORITHMIMP
#define INCLUDED_BSLH_SPOOKYHASHALGORITHMIMP
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslh_spookyhashalgorithmimp bslh_spookyhashalgorithmimp
/// @brief  Provide BDE style encapsulation of 3rd party SpookyHash code.
/// @addtogroup bsl
/// @{
/// @addtogroup bslh
/// @{
/// @addtogroup bslh_spookyhashalgorithmimp
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslh_spookyhashalgorithmimp-purpose"> Purpose</a>
/// * <a href="#bslh_spookyhashalgorithmimp-classes"> Classes </a>
/// * <a href="#bslh_spookyhashalgorithmimp-description"> Description </a>
///   * <a href="#bslh_spookyhashalgorithmimp-usage"> Usage </a>
///     * <a href="#bslh_spookyhashalgorithmimp-example-creating-128-bit-checksums"> Example: Creating 128-bit checksums </a>
///   * <a href="#bslh_spookyhashalgorithmimp-changes"> Changes </a>
///   * <a href="#bslh_spookyhashalgorithmimp-third-party-documentation"> Third-Party Documentation </a>
///
/// # Purpose {#bslh_spookyhashalgorithmimp-purpose}
/// Provide BDE style encapsulation of 3rd party SpookyHash code.
///
/// # Classes {#bslh_spookyhashalgorithmimp-classes}
///
/// -  bslh::SpookyHashAlgorithmImp: encapsulation of 3rd party SpookyHash code
///
/// @see  bslh_hash, bslh_spookyhashalgorithm
///
/// # Description {#bslh_spookyhashalgorithmimp-description}
/// `bslh::SpookyHashAlgorithmImp` provides BDE style encapsulation
/// around Bob Jenkins' canonical SpookyHash implementation.  SpookyHash
/// provides a way to hash contiguous data all at once, or discontiguous data in
/// pieces.  More information is available at:
/// http://burtleburtle.net/bob/hash/spooky.html
///
/// ## Usage {#bslh_spookyhashalgorithmimp-usage}
///
///
/// This section illustrates intended usage of this component.
///
/// ### Example: Creating 128-bit checksums {#bslh_spookyhashalgorithmimp-example-creating-128-bit-checksums}
///
///
/// Suppose we have a library of 4 billion pieces of data and we want to store
/// checksums for this data.  For a 64-bit hash, there is a 35% chance of two of
/// these checksums colliding (according to the approximation found here:
/// http://en.wikipedia.org/wiki/Birthday_problem).  We want to avoid checksum
/// collision, so we will use the 128-bit hashing functionality provided by
/// `SpookyHashAlgorithmImp`.
///
/// First, we will declare a class `CheckedData` which will store some data as
/// well as the checksum associated with it.
/// @code
///
///   class CheckedData {
///       // This class holds a pointer to data and provides a way of verifying
///       // that the data has not changed.
///
///       // TYPES
///       typedef bsls::Types::Uint64 Uint64;
///
///       // DATA
///       size_t      d_length;
///       const char *d_data;
///       Uint64      d_checksum1;
///       Uint64      d_checksum2;
///
///     public:
///       CheckedData(const char *data, size_t length);
///           // Creates an instance of this class having the specified 'length'
///           // bytes of 'data'.  The behavior is undefined unless 'data' is
///           // initialized with at least 'length' bytes or 'length' is zero,
///           // and remains valid for the lifetime of this object.  Note that
///           // only a pointer to the data will be maintained, it will not be
///           // copied.
///
///       const char *getData();
///           // Return a pointer to the data being tracked by this class.
///
///       bool isDataValid();
///           // Return 'true' if the data stored in this class matches the
///           // stored checksum, and 'false' otherwise.
///   };
///
/// @endcode
/// Then, we define the `CheckedData` constructor.  Here we will use
/// `SpookyHashImp` to calculate a 128-bit checksum.
/// @code
///
///   CheckedData::CheckedData(const char *data, size_t length)
///   : d_length(length)
///   , d_data(data)
///   , d_checksum1(0)
///   , d_checksum2(0)
///   {
///       BSLS_ASSERT(0 != data || 0 == length);
///
///       SpookyHashAlgorithmImp hashAlg(1, 2);
///
///       hashAlg.hash128(d_data, d_length, &d_checksum1, &d_checksum2);
///   }
///
///   const char *CheckedData::getData() {
///       return d_data;
///   }
///
/// @endcode
/// Next, we define `isDataValid`.  We will generate a checksum from the
/// contained data and then compare it to the checksum we generated when the
/// class was created.  If the two hashes match, then we can be reasonably
/// certain that the data is still in a valid state (the chance of an accidental
/// collision is very low).  If the checksums do not match, we know that the
/// data has been corrupted.  We will not be able to restore it, but we will
/// know not to trust it.
/// @code
///
///   bool CheckedData::isDataValid() {
///       SpookyHashAlgorithmImp hashAlg(1, 2);
///       Uint64 checksum1 = 0;
///       Uint64 checksum2 = 0;
///
///       hashAlg.hash128(d_data, d_length, &checksum1, &checksum2);
///
///       return (d_checksum1 == checksum1) && (d_checksum2 == checksum2);
///   }
/// @endcode
/// Then, we store some data in our `CheckedData` class for safekeeping.
/// @code
///
///       char data[] = "To be, or not to be--that is the question:"
///                     "Whether 'tis nobler in the mind to suffer"
///                     "The slings and arrows of outrageous fortune"
///                     "Or to take arms against a sea of troubles"
///                     "And by opposing end them.  To die, to sleep--"
///                     "No more--and by a sleep to say we end"
///                     "The heartache, and the thousand natural shocks"
///                     "That flesh is heir to.  'Tis a consummation"
///                     "Devoutly to be wished.  To die, to sleep--"
///                     "To sleep--perchance to dream: ay, there's the rub,"
///                     "For in that sleep of death what dreams may come"
///                     "When we have shuffled off this mortal coil,"
///                     "Must give us pause.  There's the respect"
///                     "That makes calamity of so long life."
///                     "For who would bear the whips and scorns of time,"
///                     "Th' oppressor's wrong, the proud man's contumely"
///                     "The pangs of despised love, the law's delay,"
///                     "The insolence of office, and the spurns"
///                     "That patient merit of th' unworthy takes,"
///                     "When he himself might his quietus make"
///                     "With a bare bodkin? Who would fardels bear,"
///                     "To grunt and sweat under a weary life,"
///                     "But that the dread of something after death,"
///                     "The undiscovered country, from whose bourn"
///                     "No traveller returns, puzzles the will,"
///                     "And makes us rather bear those ills we have"
///                     "Than fly to others that we know not of?"
///                     "Thus conscience does make cowards of us all,"
///                     "And thus the native hue of resolution"
///                     "Is sicklied o'er with the pale cast of thought,"
///                     "And enterprise of great pitch and moment"
///                     "With this regard their currents turn awry"
///                     "And lose the name of action. -- Soft you now,"
///                     "The fair Ophelia! -- Nymph, in thy orisons"
///                     "Be all my sins remembered.";
///       CheckedData checkedData(data, strlen(data));
///
/// @endcode
/// Now, we check that the `CheckedData` recognizes that it is still valid.
/// @code
///
///       ASSERT(checkedData.isDataValid());
///
/// @endcode
/// Finally, we tamper with the data and check that our `CheckedData` class can
/// detect this.
/// @code
///     data[34] = 'z';
///     ASSERT(!checkedData.isDataValid());
/// @endcode
///
/// ## Changes {#bslh_spookyhashalgorithmimp-changes}
///
///
/// The third party code begins with the "SpookyHash" header below, and
/// continues until the BloombergLP copyright notice.  Changes made to the
/// original code include:
///
/// 1. Added `BloombergLP` and `bslh` namespaces
/// 2. Renamed `SpookyHash` to `SpookyHashAlgorithmImp`
/// 3. Removed usage of `stdint.h` (which might not be available on all
///    platforms) and updated associated `typedef`s
/// 4. Added `include` guards
/// 5. Made some methods private
/// 6. Reformatted comments and added comments
/// 7. Updated indenting to BDE style
/// 8. Moved `typedef`s within class
/// 9. Changed C-style casts to @ref static_cast s
/// 10. Reordered methods according to BDE style
/// 11. Added inline to `Hash32` and `Hash64`
/// 12. Changed static constants to `enum`s to avoid storage overhead
/// 13. Added constructor in place of `init`
/// 14. Made function names lower case (had to change `Final` to `finalize` and
///     `Short` to `shortHash` to avoid using a keyword)
/// 15. Reformatted comments
/// 16. Replaced some uses of 'inline' with the new
///     `BSLH_SPOOKYHASHALGORITHMIMP_INLINE` macro, which forces inlining on GCC
///
/// ## Third-Party Documentation {#bslh_spookyhashalgorithmimp-third-party-documentation}
///
///
/// @code
/// SpookyHash: a 128-bit non cryptographic hash function
///
/// By Bob Jenkins, public domain
///   Oct 31 2010: alpha, framework + SpookyHash::Mix appears right
///   Oct 31 2011: alpha again, Mix only good to 2^^69 but rest appears right
///   Dec 31 2011: beta, improved Mix, tested it for 2-bit deltas
///   Feb  2 2012: production, same bits as beta
///   Feb  5 2012: adjusted definitions of uint* to be more portable
///   Mar 30 2012: 3 bytes/cycle, not 4. Alpha was 4 but wasn't thorough enough.
///   August 5 2012: SpookyV2 (different results)
///
/// Up to 3 bytes/cycle for long messages.  Reasonably fast for short messages.
/// All 1 or 2 bit deltas achieve avalanche within 1% bias per output bit.
///
/// This was developed for and tested on 64-bit x86-compatible processors.  It
/// assumes the processor is little-endian.  There is a macro controlling
/// whether unaligned reads are allowed (by default they are).  This should be
/// an equally good hash on big-endian machines, but it will compute different
/// results on them than on little-endian machines.
///
/// Google's CityHash has similar specs to SpookyHash, and CityHash is faster on
/// new Intel boxes.  MD4 and MD5 also have similar specs, but they are orders
/// of magnitude slower.  CRCs are two or more times slower, but unlike
/// SpookyHash, they have nice math for combining the CRCs of pieces to form the
/// CRCs of wholes.  There are also cryptographic hashes, but those are even
/// slower than MD5.
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslh
 * @{
 */
/** @addtogroup bslh_spookyhashalgorithmimp
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bsls_assert.h>
#include <bsls_platform.h>
#include <bsls_types.h>
 
#include <stddef.h>    // 'size_t'
 
/// See implementation notes for the explanation of this macro.
#if defined(BSLS_PLATFORM_CMP_GNU)
#define BSLH_SPOOKYHASHALGORITHMIMP_INLINE \
    inline __attribute__((always_inline))
#else
#define BSLH_SPOOKYHASHALGORITHMIMP_INLINE inline
#endif
 
 
 
namespace bslh {
 
 
/// This class wraps an implementation of Bob Jenkin's "SpookyHash" in a
/// BDE-style component.  For more information, see
/// http://burtleburtle.net/bob/hash/spooky.html .
///
/// See @ref bslh_spookyhashalgorithmimp 
class SpookyHashAlgorithmImp {
 
  public:
    typedef  bsls::Types::Uint64  Uint64;
    typedef  unsigned int         Uint32;
    typedef  unsigned short       Uint16;
    typedef  unsigned char        Uint8;
 
  private:
    // DATA
 
    /// Number of 64-bit integers used in the internal state.
    enum { k_NUM_VARS = 12 };
 
    /// Size of the internal state, in bytes.
    enum { k_BLOCK_SIZE = k_NUM_VARS * 8 };
 
    /// Size of buffer of unhashed data, in bytes.
    enum { k_BUFFER_SIZE = k_BLOCK_SIZE * 2 };
 
    // A non-zero, odd, constant that has an irregular distribution of 1's
    // and 0's to be used in hashing calculations.
    static const Uint64 sc_const = 0xdeadbeefdeadbeefULL;
 
    Uint64 m_data[2 * k_NUM_VARS]; // unhashed data, for partial messages
    Uint64 m_state[k_NUM_VARS];    // internal state of the hash
    size_t m_length;               // total length of the input so far
    Uint8  m_remainder;            // length of unhashed data stashed in m_data
 
    // PRIVATE CLASS METHODS
 
    /// Incorporate the first 12 bytes of the specified `data` into `h0`,
    /// `h1`, `h2`, `h3`, `h4`, `h5`, `h6`, `h7`, `h8`, `h9`, `h10`, and
    /// `h11`, and then mix the inputs together so that `h0` and `h1` are a hash of all the inputs.  
    /// 
    /// \note Note that   non-BDE-standard passing by
    /// non-`const` reference is used here to remain consistent with the cannonical implementation.  
    /// 
    /// \pre The behavior is undefined   unless `data`
    /// points at least 8 bytes of initialized memory.
    static void end(const Uint64 *data,
                    Uint64 &h0, Uint64 &h1, Uint64 &h2, Uint64 &h3,
                    Uint64 &h4, Uint64 &h5, Uint64 &h6, Uint64 &h7,
                    Uint64 &h8, Uint64 &h9, Uint64 &h10,Uint64 &h11);
 
    /// Combine the specified `h0`, `h1`, `h2`, `h3`, `h4`, `h5`, `h6`,
    /// `h7`, `h8`, `h9`, `h10`, and `h11` together so that `h0` and `h1` will be a hash of all the inputs.  
    /// 
    /// \note Note that   non-BDE-standard
    /// passing by non-`const` reference is used here to remain consistent
    /// with the cannonical implementation.  
    /// 
    /// \pre The behavior is undefined   unless `data` points at least 8 bytes of initialized memory.
    static void endPartial(Uint64 &h0, Uint64 &h1, Uint64 &h2, Uint64 &h3,
                           Uint64 &h4, Uint64 &h5, Uint64 &h6, Uint64 &h7,
                           Uint64 &h8, Uint64 &h9, Uint64 &h10,Uint64 &h11);
 
    /// Thoroughly mix the first 12 bytes of the specified `data` into `s0`,
    /// `s1`, `s2`, `s3`, `s4`, `s5`, `s6`, `s7`, `s8`, `s9`, `s10`, and
    /// `s11`.  This method should be used when the input is 96 bytes or
    /// longer to prevent the loss of entropy, because the internal state of
    /// `SpookyHashAlgorithmImp` is overwritten every 96 bytes.  
    /// 
    /// \note Note that   non-BDE-standard passing by non-`const` reference is used here to
    /// remain consistent with the cannonical implementation.  
    /// 
    /// \pre The behavior is undefined   unless `data` points at least 8 bytes of initialized
    /// memory.
    static void mix(const Uint64 *data,
                    Uint64 &s0, Uint64 &s1, Uint64 &s2,  Uint64 &s3,
                    Uint64 &s4, Uint64 &s5, Uint64 &s6,  Uint64 &s7,
                    Uint64 &s8, Uint64 &s9, Uint64 &s10, Uint64 &s11);
 
    /// Return the specified `x` left rotated by `k` bits.
    static Uint64 rot64(Uint64 x, int k);
 
    /// Hash the specified `length` bytes of `message` using `hash1` and
    /// `hash2` as seeds.  Load the higher order bits of the resulting
    /// 128-bit hash value into `hash1` and the lower order bits in `hash2`.
    /// This method is meant to be used for messages less than 192 bytes in
    /// length because of its lower startup cost.  
    /// 
    /// \pre The behavior is undefined   unless `message` points at least `length` bytes of initialized
    /// memory or `length` is zero, and both `hash1` and `hash2` point to
    /// at least 8 bytes of initialized, modifiable, memory.
    static void shortHash(const void *message,
                          size_t      length,
                          Uint64     *hash1,
                          Uint64     *hash2);
 
    /// Combine the specified `h0`, `h1`, `h2`, and `h3` together so that
    /// `h0` and `h1` will be a hash of all the inputs.  
    /// 
    /// \note Note that   non-BDE-standard passing by non-`const` reference is used here to
    /// remain consistent with the cannonical implementation.
    static void shortEnd(Uint64 &h0, Uint64 &h1, Uint64 &h2, Uint64 &h3);
 
    /// Thoroughly mix the specified `h0`, `h1`, `h2`, and `h3` so that each
    /// bit of input contributes entropy to every bit of the final states of `h0`, `h1`, `h2`, and `h3`.  
    /// 
    /// \note Note that   non-BDE-standard passing by
    /// non-`const` reference is used here to remain consistent with the
    /// cannonical implementation.
    static void shortMix(Uint64 &h0, Uint64 &h1, Uint64 &h2, Uint64 &h3);
 
  private:
    // NOT IMPLEMENTED
 
    /// Do not allow copy construction
    SpookyHashAlgorithmImp(const SpookyHashAlgorithmImp& original);// = delete;
 
    SpookyHashAlgorithmImp& operator=(const SpookyHashAlgorithmImp& rhs);
                                                                   // = delete;
        // Do not allow assignment
 
  public:
    // PUBLIC CLASS METHODS
 
    /// Hash the specified `length` bytes of `message` using `seed` as a
    /// seed.  Return the resulting 32-bit hash.  
    /// 
    /// \pre The behavior is undefined   unless `message` points at least `length` bytes of initialized
    /// memory or `length` is zero.
    static Uint32 hash32(const void *message,
                         size_t      length,
                         Uint32      seed);
 
    /// Hash the specified `length` bytes of `message` using `seed` as a
    /// seed.  Return the resulting 64-bit hash.  
    /// 
    /// \pre The behavior is undefined   unless `message` points at least `length` bytes of initialized
    /// memory or `length` is zero.
    static Uint64 hash64(const void *message,
                         size_t      length,
                         Uint64      seed);
 
    /// Hash the specified `length` bytes of `message` using `hash1` and
    /// `hash2` as seeds.  Load the higher order bits of the resulting
    /// 128-bit hash value into `hash1` and the lower order bits in `hash2`. 
    /// 
    /// \pre The behavior is undefined   unless `message` points at least `length`
    /// bytes of initialized memory or `length` is zero, and both `hash1`
    /// and `hash2` point to at least 8 bytes of initialized, modifiable,
    /// memory.
    static void hash128(const void *message,
                        size_t      length,
                        Uint64     *hash1,
                        Uint64     *hash2);
 
    // CREATORS
 
    /// Create a `bslh::SpookyHashAlgorithmImp`, initializing the internal
    /// state of the object using the specified `seed1` and `seed2` as seeds
    /// for the algorithm.
    SpookyHashAlgorithmImp(Uint64 seed1, Uint64 seed2);
 
     ~SpookyHashAlgorithmImp() = default;
        // Destroy this object.
 
    // MANIPULATORS
 
    /// Accumulate the specified `length` bytes of `message` into the
    /// internal state of the algorithm.  Accumulating bytes through
    /// `Update` will produce the same result as hashing them all at once
    /// through the `HashXX` static methods.  
    /// 
    /// \pre The behavior is undefined   unless `message` points at least `length` bytes of initialized
    /// memory or `length` is zero.
    void update(const void *message, size_t length);
 
    /// Load the finalized hash into the specified `hash1` and `hash2`.
    /// `hash1` will contain the higher order bits of the hash and `hash2`
    /// will contain the lower order bits.  The internal state of the
    /// algorithm will be modified, meaning that calling final multiple
    /// times will result in different hash values being returned.  The
    /// returned hash will be the same as if `Hash128` had been called will
    /// all of the accumulated data in one block.  
    /// 
    /// \pre The behavior is undefined   unless both `hash1` and `hash2` point to 8 bytes of modifiable memory.  
    /// 
    /// \note Note that   a value will be returned even if `update` has not
    /// been called.
    void finalize(Uint64 *hash1, Uint64 *hash2);
};
 
// ============================================================================
//                            INLINE DEFINITIONS
// ============================================================================
 
// PUBLIC CLASS METHODS
inline
SpookyHashAlgorithmImp::Uint32 SpookyHashAlgorithmImp::hash32(
                                                           const void *message,
                                                           size_t      length,
                                                           Uint32      seed)
{
    BSLS_ASSERT(0 != message || 0 == length);
    Uint64 hash1 = seed, hash2 = seed;
    hash128(message, length, &hash1, &hash2);
    return static_cast<Uint32>(hash1);
}
 
inline
SpookyHashAlgorithmImp::Uint64 SpookyHashAlgorithmImp::hash64(
                                                           const void *message,
                                                           size_t      length,
                                                           Uint64      seed)
{
    BSLS_ASSERT(0 != message || 0 == length);
    Uint64 hash1 = seed;
    hash128(message, length, &hash1, &seed);
    return hash1;
}
 
// CREATORS
inline
SpookyHashAlgorithmImp::SpookyHashAlgorithmImp(Uint64 seed1, Uint64 seed2)
: m_length(0)
, m_remainder(0)
{
    m_state[0] = seed1;
    m_state[1] = seed2;
}
 
// PRIVATE CLASS METHODS
BSLH_SPOOKYHASHALGORITHMIMP_INLINE
void SpookyHashAlgorithmImp::end(
    const Uint64 *data,
    Uint64 &h0, Uint64 &h1, Uint64 &h2, Uint64 &h3,
    Uint64 &h4, Uint64 &h5, Uint64 &h6, Uint64 &h7,
    Uint64 &h8, Uint64 &h9, Uint64 &h10,Uint64 &h11)
{
    BSLS_ASSERT(data);
    h0 += data[0];   h1 += data[1];   h2 += data[2];   h3 += data[3];
    h4 += data[4];   h5 += data[5];   h6 += data[6];   h7 += data[7];
    h8 += data[8];   h9 += data[9];   h10 += data[10]; h11 += data[11];
    endPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
    endPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
    endPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
}
 
BSLH_SPOOKYHASHALGORITHMIMP_INLINE
void SpookyHashAlgorithmImp::endPartial(
    Uint64 &h0, Uint64 &h1, Uint64 &h2, Uint64 &h3,
    Uint64 &h4, Uint64 &h5, Uint64 &h6, Uint64 &h7,
    Uint64 &h8, Uint64 &h9, Uint64 &h10,Uint64 &h11)
{
    h11+= h1;    h2 ^= h11;   h1 = rot64(h1,44);
    h0 += h2;    h3 ^= h0;    h2 = rot64(h2,15);
    h1 += h3;    h4 ^= h1;    h3 = rot64(h3,34);
    h2 += h4;    h5 ^= h2;    h4 = rot64(h4,21);
    h3 += h5;    h6 ^= h3;    h5 = rot64(h5,38);
    h4 += h6;    h7 ^= h4;    h6 = rot64(h6,33);
    h5 += h7;    h8 ^= h5;    h7 = rot64(h7,10);
    h6 += h8;    h9 ^= h6;    h8 = rot64(h8,13);
    h7 += h9;    h10^= h7;    h9 = rot64(h9,38);
    h8 += h10;   h11^= h8;    h10= rot64(h10,53);
    h9 += h11;   h0 ^= h9;    h11= rot64(h11,42);
    h10+= h0;    h1 ^= h10;   h0 = rot64(h0,54);
}
 
BSLH_SPOOKYHASHALGORITHMIMP_INLINE
void SpookyHashAlgorithmImp::mix(
    const Uint64 *data,
    Uint64 &s0, Uint64 &s1, Uint64 &s2, Uint64 &s3,
    Uint64 &s4, Uint64 &s5, Uint64 &s6, Uint64 &s7,
    Uint64 &s8, Uint64 &s9, Uint64 &s10,Uint64 &s11)
{
    BSLS_ASSERT(data);
    s0 += data[0];   s2  ^= s10; s11 ^= s0;  s0  = rot64(s0,11);  s11 += s1;
    s1 += data[1];   s3  ^= s11; s0  ^= s1;  s1  = rot64(s1,32);  s0  += s2;
    s2 += data[2];   s4  ^= s0;  s1  ^= s2;  s2  = rot64(s2,43);  s1  += s3;
    s3 += data[3];   s5  ^= s1;  s2  ^= s3;  s3  = rot64(s3,31);  s2  += s4;
    s4 += data[4];   s6  ^= s2;  s3  ^= s4;  s4  = rot64(s4,17);  s3  += s5;
    s5 += data[5];   s7  ^= s3;  s4  ^= s5;  s5  = rot64(s5,28);  s4  += s6;
    s6 += data[6];   s8  ^= s4;  s5  ^= s6;  s6  = rot64(s6,39);  s5  += s7;
    s7 += data[7];   s9  ^= s5;  s6  ^= s7;  s7  = rot64(s7,57);  s6  += s8;
    s8 += data[8];   s10 ^= s6;  s7  ^= s8;  s8  = rot64(s8,55);  s7  += s9;
    s9 += data[9];   s11 ^= s7;  s8  ^= s9;  s9  = rot64(s9,54);  s8  += s10;
    s10 += data[10]; s0  ^= s8;  s9  ^= s10; s10 = rot64(s10,22); s9  += s11;
    s11 += data[11]; s1  ^= s9;  s10 ^= s11; s11 = rot64(s11,46); s10 += s0;
}
 
BSLH_SPOOKYHASHALGORITHMIMP_INLINE
SpookyHashAlgorithmImp::Uint64 SpookyHashAlgorithmImp::rot64(Uint64 x, int k)
{
    return (x << k) | (x >> (64 - k));
}
 
BSLH_SPOOKYHASHALGORITHMIMP_INLINE
void SpookyHashAlgorithmImp::shortEnd(Uint64 &h0,
                                      Uint64 &h1,
                                      Uint64 &h2,
                                      Uint64 &h3)
{
    h3 ^= h2;  h2 = rot64(h2,15);  h3 += h2;
    h0 ^= h3;  h3 = rot64(h3,52);  h0 += h3;
    h1 ^= h0;  h0 = rot64(h0,26);  h1 += h0;
    h2 ^= h1;  h1 = rot64(h1,51);  h2 += h1;
    h3 ^= h2;  h2 = rot64(h2,28);  h3 += h2;
    h0 ^= h3;  h3 = rot64(h3,9);   h0 += h3;
    h1 ^= h0;  h0 = rot64(h0,47);  h1 += h0;
    h2 ^= h1;  h1 = rot64(h1,54);  h2 += h1;
    h3 ^= h2;  h2 = rot64(h2,32);  h3 += h2;
    h0 ^= h3;  h3 = rot64(h3,25);  h0 += h3;
    h1 ^= h0;  h0 = rot64(h0,63);  h1 += h0;
}
 
BSLH_SPOOKYHASHALGORITHMIMP_INLINE
void SpookyHashAlgorithmImp::shortMix(Uint64 &h0,
                                      Uint64 &h1,
                                      Uint64 &h2,
                                      Uint64 &h3)
{
    h2 = rot64(h2,50);  h2 += h3;  h0 ^= h2;
    h3 = rot64(h3,52);  h3 += h0;  h1 ^= h3;
    h0 = rot64(h0,30);  h0 += h1;  h2 ^= h0;
    h1 = rot64(h1,41);  h1 += h2;  h3 ^= h1;
    h2 = rot64(h2,54);  h2 += h3;  h0 ^= h2;
    h3 = rot64(h3,48);  h3 += h0;  h1 ^= h3;
    h0 = rot64(h0,38);  h0 += h1;  h2 ^= h0;
    h1 = rot64(h1,37);  h1 += h2;  h3 ^= h1;
    h2 = rot64(h2,62);  h2 += h3;  h0 ^= h2;
    h3 = rot64(h3,34);  h3 += h0;  h1 ^= h3;
    h0 = rot64(h0,5);   h0 += h1;  h2 ^= h0;
    h1 = rot64(h1,36);  h1 += h2;  h3 ^= h1;
}
 
}  // close package namespace
 
 
 
#undef BSLH_SPOOKYHASHALGORITHMIMP_INLINE
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2017 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 ----------------------------------
 
/** @} */
/** @} */
/** @} */