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 41uint32_t SuperFastHash (const char * data, int len) { 42uint32_t hash = len, tmp; 43int 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