folly::hash::SpookyHashV2 Class Reference

#include <SpookyHashV2.h>

Public Member Functions
void	Init (uint64_t seed1, uint64_t seed2)
void	Update (const void *message, size_t length)
void	Final (uint64_t *hash1, uint64_t *hash2) const

Static Public Member Functions
static void	Hash128 (const void *message, size_t length, uint64_t *hash1, uint64_t *hash2)
static uint64_t	Hash64 (const void *message, size_t length, uint64_t seed)
static uint32_t	Hash32 (const void *message, size_t length, uint32_t seed)
static uint64_t	Rot64 (uint64_t x, int k)
static void	Mix (const uint64_t *data, uint64_t &s0, uint64_t &s1, uint64_t &s2, uint64_t &s3, uint64_t &s4, uint64_t &s5, uint64_t &s6, uint64_t &s7, uint64_t &s8, uint64_t &s9, uint64_t &s10, uint64_t &s11)
static void	EndPartial (uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3, uint64_t &h4, uint64_t &h5, uint64_t &h6, uint64_t &h7, uint64_t &h8, uint64_t &h9, uint64_t &h10, uint64_t &h11)
static void	End (const uint64_t *data, uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3, uint64_t &h4, uint64_t &h5, uint64_t &h6, uint64_t &h7, uint64_t &h8, uint64_t &h9, uint64_t &h10, uint64_t &h11)
static void	ShortMix (uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3)
static void	ShortEnd (uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3)

Static Private Member Functions
static void	Short (const void *message, size_t length, uint64_t *hash1, uint64_t *hash2)

Private Attributes
uint64_t	m_data [2 *sc_numVars]
uint64_t	m_state [sc_numVars]
size_t	m_length
uint8_t	m_remainder

Static Private Attributes
static constexpr size_t	sc_numVars = 12
static constexpr size_t	sc_blockSize = sc_numVars*8
static constexpr size_t	sc_bufSize = 2*sc_blockSize
static constexpr uint64_t	sc_const = 0xdeadbeefdeadbeefULL

Detailed Description

Definition at line 56 of file SpookyHashV2.h.

Member Function Documentation

static void folly::hash::SpookyHashV2::End ( const uint64_t *  data, uint64_t &  h0, uint64_t &  h1, uint64_t &  h2, uint64_t &  h3, uint64_t &  h4, uint64_t &  h5, uint64_t &  h6, uint64_t &  h7, uint64_t &  h8, uint64_t &  h9, uint64_t &  h10, uint64_t &  h11  )

inlinestatic

Definition at line 197 of file SpookyHashV2.h.

References EndPartial().

Referenced by Final(), and Hash128().

    {
        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);
    }

static void folly::hash::SpookyHashV2::EndPartial ( uint64_t &  h0, uint64_t &  h1, uint64_t &  h2, uint64_t &  h3, uint64_t &  h4, uint64_t &  h5, uint64_t &  h6, uint64_t &  h7, uint64_t &  h8, uint64_t &  h9, uint64_t &  h10, uint64_t &  h11  )

inlinestatic

Definition at line 178 of file SpookyHashV2.h.

References Rot64().

Referenced by End().

    {
        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);
    }

void folly::hash::SpookyHashV2::Final	(	uint64_t *	hash1,
		uint64_t *	hash2
	)		const

Definition at line 340 of file SpookyHashV2.cpp.

References folly::data(), End(), m_data, m_length, m_remainder, m_state, Mix(), sc_blockSize, sc_bufSize, sc_numVars, Short(), uint64_t, and uint8_t.

Referenced by folly::RecordIOReader::Iterator::advanceToValid(), Hash32(), and folly::IOBufHash::operator()().

{
    // init the variables
    if (m_length < sc_bufSize)
    {
        *hash1 = m_state[0];
        *hash2 = m_state[1];
        Short( m_data, m_length, hash1, hash2);
        return;
    }

    uint64_t buf[2*sc_numVars];
    memcpy(buf, m_data, sizeof(buf));
    uint64_t *data = buf;
    uint8_t remainder = m_remainder;

    uint64_t h0 = m_state[0];
    uint64_t h1 = m_state[1];
    uint64_t h2 = m_state[2];
    uint64_t h3 = m_state[3];
    uint64_t h4 = m_state[4];
    uint64_t h5 = m_state[5];
    uint64_t h6 = m_state[6];
    uint64_t h7 = m_state[7];
    uint64_t h8 = m_state[8];
    uint64_t h9 = m_state[9];
    uint64_t h10 = m_state[10];
    uint64_t h11 = m_state[11];

    if (remainder >= sc_blockSize)
    {
        // m_data can contain two blocks; handle any whole first block
        Mix(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
        data += sc_numVars;
        remainder -= sc_blockSize;
    }

    // mix in the last partial block, and the length mod sc_blockSize
    memset(&((uint8_t *)data)[remainder], 0, (sc_blockSize-remainder));

    ((uint8_t *)data)[sc_blockSize-1] = remainder;

    // do some final mixing
    End(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);

    *hash1 = h0;
    *hash2 = h1;
}

void folly::hash::SpookyHashV2::Hash128 ( const void *  message, size_t  length, uint64_t *  hash1, uint64_t *  hash2  )

static

Definition at line 162 of file SpookyHashV2.cpp.

References folly::test::end(), End(), i, folly::kHasUnalignedAccess, message, Mix(), sc_blockSize, sc_bufSize, sc_const, sc_numVars, Short(), uint64_t, and uint8_t.

Referenced by folly::IPAddressV6::hash(), Hash32(), and Hash64().

{
    if (length < sc_bufSize)
    {
        Short(message, length, hash1, hash2);
        return;
    }

    uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
    uint64_t buf[sc_numVars];
    uint64_t *end;
    union
    {
        const uint8_t *p8;
        uint64_t *p64;
        size_t i;
    } u;
    size_t remainder;

    h0=h3=h6=h9  = *hash1;
    h1=h4=h7=h10 = *hash2;
    h2=h5=h8=h11 = sc_const;

    u.p8 = (const uint8_t *)message;
    end = u.p64 + (length/sc_blockSize)*sc_numVars;

    // handle all whole sc_blockSize blocks of bytes
    if (kHasUnalignedAccess || ((u.i & 0x7) == 0))
    {
        while (u.p64 < end)
        {
            Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
            u.p64 += sc_numVars;
        }
    }
    else
    {
        while (u.p64 < end)
        {
            memcpy(buf, u.p64, sc_blockSize);
            Mix(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
            u.p64 += sc_numVars;
        }
    }

    // handle the last partial block of sc_blockSize bytes
    remainder = (length - ((const uint8_t *)end-(const uint8_t *)message));
    memcpy(buf, end, remainder);
    memset(((uint8_t *)buf)+remainder, 0, sc_blockSize-remainder);
    ((uint8_t*)buf)[sc_blockSize - 1] = uint8_t(remainder);

    // do some final mixing
    End(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
    *hash1 = h0;
    *hash2 = h1;
}

static uint32_t folly::hash::SpookyHashV2::Hash32 ( const void *  message, size_t  length, uint32_t  seed  )

inlinestatic

Definition at line 84 of file SpookyHashV2.h.

References Final(), Hash128(), Init(), seed, uint32_t, uint64_t, and Update().

Referenced by folly::RecordIOReader::Iterator::advanceToValid().

    {
        uint64_t hash1 = seed, hash2 = seed;
        Hash128(message, length, &hash1, &hash2);
        return (uint32_t)hash1;
    }

static uint64_t folly::hash::SpookyHashV2::Hash64 ( const void *  message, size_t  length, uint64_t  seed  )

inlinestatic

Definition at line 71 of file SpookyHashV2.h.

References Hash128(), seed, and uint64_t.

Referenced by folly::RecordIOReader::Iterator::advanceToValid(), detail::SpookyHashV2::operator()(), folly::hasher< std::string >::operator()(), and folly::exception_tracer::operator<<().

    {
        uint64_t hash1 = seed;
        Hash128(message, length, &hash1, &seed);
        return hash1;
    }

void folly::hash::SpookyHashV2::Init	(	uint64_t	seed1,
		uint64_t	seed2
	)

Definition at line 226 of file SpookyHashV2.cpp.

References m_length, m_remainder, and m_state.

Referenced by folly::RecordIOReader::Iterator::advanceToValid(), Hash32(), and folly::IOBufHash::operator()().

{
    m_length = 0;
    m_remainder = 0;
    m_state[0] = seed1;
    m_state[1] = seed2;
}

static void folly::hash::SpookyHashV2::Mix ( const uint64_t *  data, uint64_t &  s0, uint64_t &  s1, uint64_t &  s2, uint64_t &  s3, uint64_t &  s4, uint64_t &  s5, uint64_t &  s6, uint64_t &  s7, uint64_t &  s8, uint64_t &  s9, uint64_t &  s10, uint64_t &  s11  )

inlinestatic

Definition at line 142 of file SpookyHashV2.h.

References Rot64().

Referenced by Final(), Hash128(), and Update().

    {
      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;
    }

static uint64_t folly::hash::SpookyHashV2::Rot64 ( uint64_t  x, int  k  )

inlinestatic

Definition at line 124 of file SpookyHashV2.h.

References k.

Referenced by EndPartial(), Mix(), ShortEnd(), and ShortMix().

    {
        return (x << k) | (x >> (64 - k));
    }

void folly::hash::SpookyHashV2::Short ( const void *  message, size_t  length, uint64_t *  hash1, uint64_t *  hash2  )

staticprivate

Definition at line 45 of file SpookyHashV2.cpp.

References a, b, c, folly::test::end(), FOLLY_FALLTHROUGH, i, folly::kHasUnalignedAccess, sc_const, sc_numVars, ShortEnd(), ShortMix(), uint32_t, uint64_t, and uint8_t.

Referenced by Final(), Hash128(), and ShortEnd().

{
    uint64_t buf[2*sc_numVars];
    union
    {
        const uint8_t *p8;
        uint32_t *p32;
        uint64_t *p64;
        size_t i;
    } u;

    u.p8 = (const uint8_t *)message;

    if (!kHasUnalignedAccess && (u.i & 0x7))
    {
        memcpy(buf, message, length);
        u.p64 = buf;
    }

    size_t remainder = length%32;
    uint64_t a=*hash1;
    uint64_t b=*hash2;
    uint64_t c=sc_const;
    uint64_t d=sc_const;

    if (length > 15)
    {
        const uint64_t *end = u.p64 + (length/32)*4;

        // handle all complete sets of 32 bytes
        for (; u.p64 < end; u.p64 += 4)
        {
            c += u.p64[0];
            d += u.p64[1];
            ShortMix(a,b,c,d);
            a += u.p64[2];
            b += u.p64[3];
        }

        //Handle the case of 16+ remaining bytes.
        if (remainder >= 16)
        {
            c += u.p64[0];
            d += u.p64[1];
            ShortMix(a,b,c,d);
            u.p64 += 2;
            remainder -= 16;
        }
    }

    // Handle the last 0..15 bytes, and its length
    d += ((uint64_t)length) << 56;
    switch (remainder)
    {
    case 15:
        d += ((uint64_t)u.p8[14]) << 48;
        FOLLY_FALLTHROUGH;
    case 14:
        d += ((uint64_t)u.p8[13]) << 40;
        FOLLY_FALLTHROUGH;
    case 13:
        d += ((uint64_t)u.p8[12]) << 32;
        FOLLY_FALLTHROUGH;
    case 12:
        d += u.p32[2];
        c += u.p64[0];
        break;
    case 11:
        d += ((uint64_t)u.p8[10]) << 16;
        FOLLY_FALLTHROUGH;
    case 10:
        d += ((uint64_t)u.p8[9]) << 8;
        FOLLY_FALLTHROUGH;
    case 9:
        d += (uint64_t)u.p8[8];
        FOLLY_FALLTHROUGH;
    case 8:
        c += u.p64[0];
        break;
    case 7:
        c += ((uint64_t)u.p8[6]) << 48;
        FOLLY_FALLTHROUGH;
    case 6:
        c += ((uint64_t)u.p8[5]) << 40;
        FOLLY_FALLTHROUGH;
    case 5:
        c += ((uint64_t)u.p8[4]) << 32;
        FOLLY_FALLTHROUGH;
    case 4:
        c += u.p32[0];
        break;
    case 3:
        c += ((uint64_t)u.p8[2]) << 16;
        FOLLY_FALLTHROUGH;
    case 2:
        c += ((uint64_t)u.p8[1]) << 8;
        FOLLY_FALLTHROUGH;
    case 1:
        c += (uint64_t)u.p8[0];
        break;
    case 0:
        c += sc_const;
        d += sc_const;
    }
    ShortEnd(a,b,c,d);
    *hash1 = a;
    *hash2 = b;
}

static void folly::hash::SpookyHashV2::ShortEnd ( uint64_t &  h0, uint64_t &  h1, uint64_t &  h2, uint64_t &  h3  )

inlinestatic

Definition at line 255 of file SpookyHashV2.h.

References Rot64(), Short(), and uint64_t.

Referenced by Short().

    {
        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;
    }

static void folly::hash::SpookyHashV2::ShortMix ( uint64_t &  h0, uint64_t &  h1, uint64_t &  h2, uint64_t &  h3  )

inlinestatic

Definition at line 226 of file SpookyHashV2.h.

References Rot64().

Referenced by Short().

    {
        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;
    }

void folly::hash::SpookyHashV2::Update	(	const void *	message,
		size_t	length
	)

Definition at line 236 of file SpookyHashV2.cpp.

References folly::test::end(), i, folly::kHasUnalignedAccess, m_data, m_length, m_remainder, m_state, Mix(), prefix(), sc_blockSize, sc_bufSize, sc_const, sc_numVars, uint64_t, and uint8_t.

Referenced by folly::RecordIOReader::Iterator::advanceToValid(), Hash32(), and folly::IOBufHash::operator()().

{
    uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
    size_t newLength = length + m_remainder;
    uint8_t  remainder;
    union
    {
        const uint8_t *p8;
        uint64_t *p64;
        size_t i;
    } u;
    const uint64_t *end;

    // Is this message fragment too short?  If it is, stuff it away.
    if (newLength < sc_bufSize)
    {
        memcpy(&((uint8_t *)m_data)[m_remainder], message, length);
        m_length = length + m_length;
        m_remainder = (uint8_t)newLength;
        return;
    }

    // init the variables
    if (m_length < sc_bufSize)
    {
        h0=h3=h6=h9  = m_state[0];
        h1=h4=h7=h10 = m_state[1];
        h2=h5=h8=h11 = sc_const;
    }
    else
    {
        h0 = m_state[0];
        h1 = m_state[1];
        h2 = m_state[2];
        h3 = m_state[3];
        h4 = m_state[4];
        h5 = m_state[5];
        h6 = m_state[6];
        h7 = m_state[7];
        h8 = m_state[8];
        h9 = m_state[9];
        h10 = m_state[10];
        h11 = m_state[11];
    }
    m_length = length + m_length;

    // if we've got anything stuffed away, use it now
    if (m_remainder)
    {
        uint8_t prefix = sc_bufSize-m_remainder;
        memcpy(&(((uint8_t *)m_data)[m_remainder]), message, prefix);
        u.p64 = m_data;
        Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
        Mix(&u.p64[sc_numVars], h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
        u.p8 = ((const uint8_t *)message) + prefix;
        length -= prefix;
    }
    else
    {
        u.p8 = (const uint8_t *)message;
    }

    // handle all whole blocks of sc_blockSize bytes
    end = u.p64 + (length/sc_blockSize)*sc_numVars;
    remainder = (uint8_t)(length-((const uint8_t *)end-u.p8));
    if (kHasUnalignedAccess || (u.i & 0x7) == 0)
    {
        while (u.p64 < end)
        {
            Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
            u.p64 += sc_numVars;
        }
    }
    else
    {
        while (u.p64 < end)
        {
            memcpy(m_data, u.p8, sc_blockSize);
            Mix(m_data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
            u.p64 += sc_numVars;
        }
    }

    // stuff away the last few bytes
    m_remainder = remainder;
    memcpy(m_data, end, remainder);

    // stuff away the variables
    m_state[0] = h0;
    m_state[1] = h1;
    m_state[2] = h2;
    m_state[3] = h3;
    m_state[4] = h4;
    m_state[5] = h5;
    m_state[6] = h6;
    m_state[7] = h7;
    m_state[8] = h8;
    m_state[9] = h9;
    m_state[10] = h10;
    m_state[11] = h11;
}

Member Data Documentation

uint64_t folly::hash::SpookyHashV2::m_data[2 *sc_numVars]

private

Definition at line 303 of file SpookyHashV2.h.

Referenced by Final(), and Update().

size_t folly::hash::SpookyHashV2::m_length

private

Definition at line 305 of file SpookyHashV2.h.

Referenced by Final(), Init(), and Update().

uint8_t folly::hash::SpookyHashV2::m_remainder

private

Definition at line 306 of file SpookyHashV2.h.

Referenced by Final(), Init(), and Update().

uint64_t folly::hash::SpookyHashV2::m_state[sc_numVars]

private

Definition at line 304 of file SpookyHashV2.h.

Referenced by Final(), Init(), and Update().

constexpr size_t folly::hash::SpookyHashV2::sc_blockSize = sc_numVars*8

staticprivate

Definition at line 289 of file SpookyHashV2.h.

Referenced by Final(), Hash128(), and Update().

constexpr size_t folly::hash::SpookyHashV2::sc_bufSize = 2*sc_blockSize

staticprivate

Definition at line 292 of file SpookyHashV2.h.

Referenced by Final(), Hash128(), and Update().

constexpr uint64_t folly::hash::SpookyHashV2::sc_const = 0xdeadbeefdeadbeefULL

staticprivate

Definition at line 301 of file SpookyHashV2.h.

Referenced by Hash128(), Short(), and Update().

constexpr size_t folly::hash::SpookyHashV2::sc_numVars = 12

staticprivate

Definition at line 286 of file SpookyHashV2.h.

Referenced by Final(), Hash128(), Short(), and Update().

---

The documentation for this class was generated from the following files:

• proxygen/folly/folly/hash/SpookyHashV2.h
• proxygen/folly/folly/hash/SpookyHashV2.cpp