Home | History | Annotate | Download | only in superfasthash 
      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 }
     85