base/third_party/superfasthash/superfasthash.c

   1 // Copyright (c) 2010, Paul Hsieh
   2 // All rights reserved.
   3 //
   4 // Redistribution and use in source and binary forms, with or without
   5 // modification, are permitted provided that the following conditions are met:
   6 //
   7 // * Redistributions of source code must retain the above copyright notice, this
   8 //   list of conditions and the following disclaimer.
   9 // * Redistributions in binary form must reproduce the above copyright notice,
  10 //   this list of conditions and the following disclaimer in the documentation
  11 //   and/or other materials provided with the distribution.
  12 // * Neither my name, Paul Hsieh, nor the names of any other contributors to the
  13 //   code use may not be used to endorse or promote products derived from this
  14 //   software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  20 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26 // POSSIBILITY OF SUCH DAMAGE.
  27
  28 #include <stdint.h>
  29 #include <stdlib.h>
  30 #undef get16bits
  31 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
  32   || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
  33 #define get16bits(d) (*((const uint16_t *) (d)))
  34 #endif
  35
  36 #if !defined (get16bits)
  37 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
  38                        +(uint32_t)(((const uint8_t *)(d))[0]) )
  39 #endif
  40
  41 uint32_t SuperFastHash (const char * data, int len) {
  42 uint32_t hash = len, tmp;
  43 int rem;
  44
  45     if (len <= 0 || data == NULL) return 0;
  46
  47     rem = len & 3;
  48     len >>= 2;
  49
  50     /* Main loop */
  51     for (;len > 0; len--) {
  52         hash  += get16bits (data);
  53         tmp    = (get16bits (data+2) << 11) ^ hash;
  54         hash   = (hash << 16) ^ tmp;
  55         data  += 2*sizeof (uint16_t);
  56         hash  += hash >> 11;
  57     }
  58
  59     /* Handle end cases */
  60     switch (rem) {
  61         case 3: hash += get16bits (data);
  62                 hash ^= hash << 16;
  63                 hash ^= ((signed char)data[sizeof (uint16_t)]) << 18;
  64                 hash += hash >> 11;
  65                 break;
  66         case 2: hash += get16bits (data);
  67                 hash ^= hash << 11;
  68                 hash += hash >> 17;
  69                 break;
  70         case 1: hash += (signed char)*data;
  71                 hash ^= hash << 10;
  72                 hash += hash >> 1;
  73     }
  74
  75     /* Force "avalanching" of final 127 bits */
  76     hash ^= hash << 3;
  77     hash += hash >> 5;
  78     hash ^= hash << 4;
  79     hash += hash >> 17;
  80     hash ^= hash << 25;
  81     hash += hash >> 6;
  82
  83     return hash;
  84 }