folly/SpookyHashV2.cpp

   1 /*
   2  * Copyright 2015 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 // Spooky Hash
  18 // A 128-bit noncryptographic hash, for checksums and table lookup
  19 // By Bob Jenkins.  Public domain.
  20 //   Oct 31 2010: published framework, disclaimer ShortHash isn't right
  21 //   Nov 7 2010: disabled ShortHash
  22 //   Oct 31 2011: replace End, ShortMix, ShortEnd, enable ShortHash again
  23 //   April 10 2012: buffer overflow on platforms without unaligned reads
  24 //   July 12 2012: was passing out variables in final to in/out in short
  25 //   July 30 2012: I reintroduced the buffer overflow
  26 //   August 5 2012: SpookyV2: d = should be d += in short hash, and remove
  27 //                  extra mix from long hash
  28
  29 #include <folly/SpookyHashV2.h>
  30
  31 #include <cstring>
  32
  33 #define ALLOW_UNALIGNED_READS 1
  34
  35 namespace folly {
  36 namespace hash {
  37
  38 //
  39 // short hash ... it could be used on any message,
  40 // but it's used by Spooky just for short messages.
  41 //
  42 void SpookyHashV2::Short(
  43     const void *message,
  44     size_t length,
  45     uint64_t *hash1,
  46     uint64_t *hash2)
  47 {
  48     uint64_t buf[2*sc_numVars];
  49     union
  50     {
  51         const uint8_t *p8;
  52         uint32_t *p32;
  53         uint64_t *p64;
  54         size_t i;
  55     } u;
  56
  57     u.p8 = (const uint8_t *)message;
  58
  59     if (!ALLOW_UNALIGNED_READS && (u.i & 0x7))
  60     {
  61         memcpy(buf, message, length);
  62         u.p64 = buf;
  63     }
  64
  65     size_t remainder = length%32;
  66     uint64_t a=*hash1;
  67     uint64_t b=*hash2;
  68     uint64_t c=sc_const;
  69     uint64_t d=sc_const;
  70
  71     if (length > 15)
  72     {
  73         const uint64_t *end = u.p64 + (length/32)*4;
  74
  75         // handle all complete sets of 32 bytes
  76         for (; u.p64 < end; u.p64 += 4)
  77         {
  78             c += u.p64[0];
  79             d += u.p64[1];
  80             ShortMix(a,b,c,d);
  81             a += u.p64[2];
  82             b += u.p64[3];
  83         }
  84
  85         //Handle the case of 16+ remaining bytes.
  86         if (remainder >= 16)
  87         {
  88             c += u.p64[0];
  89             d += u.p64[1];
  90             ShortMix(a,b,c,d);
  91             u.p64 += 2;
  92             remainder -= 16;
  93         }
  94     }
  95
  96     // Handle the last 0..15 bytes, and its length
  97     d += ((uint64_t)length) << 56;
  98     switch (remainder)
  99     {
 100     case 15:
 101     d += ((uint64_t)u.p8[14]) << 48;
 102     case 14:
 103         d += ((uint64_t)u.p8[13]) << 40;
 104     case 13:
 105         d += ((uint64_t)u.p8[12]) << 32;
 106     case 12:
 107         d += u.p32[2];
 108         c += u.p64[0];
 109         break;
 110     case 11:
 111         d += ((uint64_t)u.p8[10]) << 16;
 112     case 10:
 113         d += ((uint64_t)u.p8[9]) << 8;
 114     case 9:
 115         d += (uint64_t)u.p8[8];
 116     case 8:
 117         c += u.p64[0];
 118         break;
 119     case 7:
 120         c += ((uint64_t)u.p8[6]) << 48;
 121     case 6:
 122         c += ((uint64_t)u.p8[5]) << 40;
 123     case 5:
 124         c += ((uint64_t)u.p8[4]) << 32;
 125     case 4:
 126         c += u.p32[0];
 127         break;
 128     case 3:
 129         c += ((uint64_t)u.p8[2]) << 16;
 130     case 2:
 131         c += ((uint64_t)u.p8[1]) << 8;
 132     case 1:
 133         c += (uint64_t)u.p8[0];
 134         break;
 135     case 0:
 136         c += sc_const;
 137         d += sc_const;
 138     }
 139     ShortEnd(a,b,c,d);
 140     *hash1 = a;
 141     *hash2 = b;
 142 }
 143
 144
 145
 146
 147 // do the whole hash in one call
 148 void SpookyHashV2::Hash128(
 149     const void *message,
 150     size_t length,
 151     uint64_t *hash1,
 152     uint64_t *hash2)
 153 {
 154     if (length < sc_bufSize)
 155     {
 156         Short(message, length, hash1, hash2);
 157         return;
 158     }
 159
 160     uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
 161     uint64_t buf[sc_numVars];
 162     uint64_t *end;
 163     union
 164     {
 165         const uint8_t *p8;
 166         uint64_t *p64;
 167         size_t i;
 168     } u;
 169     size_t remainder;
 170
 171     h0=h3=h6=h9  = *hash1;
 172     h1=h4=h7=h10 = *hash2;
 173     h2=h5=h8=h11 = sc_const;
 174
 175     u.p8 = (const uint8_t *)message;
 176     end = u.p64 + (length/sc_blockSize)*sc_numVars;
 177
 178     // handle all whole sc_blockSize blocks of bytes
 179     if (ALLOW_UNALIGNED_READS || ((u.i & 0x7) == 0))
 180     {
 181         while (u.p64 < end)
 182         {
 183             Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
 184             u.p64 += sc_numVars;
 185         }
 186     }
 187     else
 188     {
 189         while (u.p64 < end)
 190         {
 191             memcpy(buf, u.p64, sc_blockSize);
 192             Mix(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
 193             u.p64 += sc_numVars;
 194         }
 195     }
 196
 197     // handle the last partial block of sc_blockSize bytes
 198     remainder = (length - ((const uint8_t *)end-(const uint8_t *)message));
 199     memcpy(buf, end, remainder);
 200     memset(((uint8_t *)buf)+remainder, 0, sc_blockSize-remainder);
 201     ((uint8_t *)buf)[sc_blockSize-1] = remainder;
 202
 203     // do some final mixing
 204     End(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
 205     *hash1 = h0;
 206     *hash2 = h1;
 207 }
 208
 209
 210
 211 // init spooky state
 212 void SpookyHashV2::Init(uint64_t seed1, uint64_t seed2)
 213 {
 214     m_length = 0;
 215     m_remainder = 0;
 216     m_state[0] = seed1;
 217     m_state[1] = seed2;
 218 }
 219
 220
 221 // add a message fragment to the state
 222 void SpookyHashV2::Update(const void *message, size_t length)
 223 {
 224     uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
 225     size_t newLength = length + m_remainder;
 226     uint8_t  remainder;
 227     union
 228     {
 229         const uint8_t *p8;
 230         uint64_t *p64;
 231         size_t i;
 232     } u;
 233     const uint64_t *end;
 234
 235     // Is this message fragment too short?  If it is, stuff it away.
 236     if (newLength < sc_bufSize)
 237     {
 238         memcpy(&((uint8_t *)m_data)[m_remainder], message, length);
 239         m_length = length + m_length;
 240         m_remainder = (uint8_t)newLength;
 241         return;
 242     }
 243
 244     // init the variables
 245     if (m_length < sc_bufSize)
 246     {
 247         h0=h3=h6=h9  = m_state[0];
 248         h1=h4=h7=h10 = m_state[1];
 249         h2=h5=h8=h11 = sc_const;
 250     }
 251     else
 252     {
 253         h0 = m_state[0];
 254         h1 = m_state[1];
 255         h2 = m_state[2];
 256         h3 = m_state[3];
 257         h4 = m_state[4];
 258         h5 = m_state[5];
 259         h6 = m_state[6];
 260         h7 = m_state[7];
 261         h8 = m_state[8];
 262         h9 = m_state[9];
 263         h10 = m_state[10];
 264         h11 = m_state[11];
 265     }
 266     m_length = length + m_length;
 267
 268     // if we've got anything stuffed away, use it now
 269     if (m_remainder)
 270     {
 271         uint8_t prefix = sc_bufSize-m_remainder;
 272         memcpy(&(((uint8_t *)m_data)[m_remainder]), message, prefix);
 273         u.p64 = m_data;
 274         Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
 275         Mix(&u.p64[sc_numVars], h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
 276         u.p8 = ((const uint8_t *)message) + prefix;
 277         length -= prefix;
 278     }
 279     else
 280     {
 281         u.p8 = (const uint8_t *)message;
 282     }
 283
 284     // handle all whole blocks of sc_blockSize bytes
 285     end = u.p64 + (length/sc_blockSize)*sc_numVars;
 286     remainder = (uint8_t)(length-((const uint8_t *)end-u.p8));
 287     if (ALLOW_UNALIGNED_READS || (u.i & 0x7) == 0)
 288     {
 289         while (u.p64 < end)
 290         {
 291             Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
 292             u.p64 += sc_numVars;
 293         }
 294     }
 295     else
 296     {
 297         while (u.p64 < end)
 298         {
 299             memcpy(m_data, u.p8, sc_blockSize);
 300             Mix(m_data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
 301             u.p64 += sc_numVars;
 302         }
 303     }
 304
 305     // stuff away the last few bytes
 306     m_remainder = remainder;
 307     memcpy(m_data, end, remainder);
 308
 309     // stuff away the variables
 310     m_state[0] = h0;
 311     m_state[1] = h1;
 312     m_state[2] = h2;
 313     m_state[3] = h3;
 314     m_state[4] = h4;
 315     m_state[5] = h5;
 316     m_state[6] = h6;
 317     m_state[7] = h7;
 318     m_state[8] = h8;
 319     m_state[9] = h9;
 320     m_state[10] = h10;
 321     m_state[11] = h11;
 322 }
 323
 324
 325 // report the hash for the concatenation of all message fragments so far
 326 void SpookyHashV2::Final(uint64_t *hash1, uint64_t *hash2)
 327 {
 328     // init the variables
 329     if (m_length < sc_bufSize)
 330     {
 331         *hash1 = m_state[0];
 332         *hash2 = m_state[1];
 333         Short( m_data, m_length, hash1, hash2);
 334         return;
 335     }
 336
 337     const uint64_t *data = (const uint64_t *)m_data;
 338     uint8_t remainder = m_remainder;
 339
 340     uint64_t h0 = m_state[0];
 341     uint64_t h1 = m_state[1];
 342     uint64_t h2 = m_state[2];
 343     uint64_t h3 = m_state[3];
 344     uint64_t h4 = m_state[4];
 345     uint64_t h5 = m_state[5];
 346     uint64_t h6 = m_state[6];
 347     uint64_t h7 = m_state[7];
 348     uint64_t h8 = m_state[8];
 349     uint64_t h9 = m_state[9];
 350     uint64_t h10 = m_state[10];
 351     uint64_t h11 = m_state[11];
 352
 353     if (remainder >= sc_blockSize)
 354     {
 355         // m_data can contain two blocks; handle any whole first block
 356         Mix(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
 357         data += sc_numVars;
 358         remainder -= sc_blockSize;
 359     }
 360
 361     // mix in the last partial block, and the length mod sc_blockSize
 362     memset(&((uint8_t *)data)[remainder], 0, (sc_blockSize-remainder));
 363
 364     ((uint8_t *)data)[sc_blockSize-1] = remainder;
 365
 366     // do some final mixing
 367     End(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
 368
 369     *hash1 = h0;
 370     *hash2 = h1;
 371 }
 372
 373 }  // namespace hash
 374 }  // namespace folly