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 29 #include <stddef.h> 30 #include <stdint.h> 31 32 #undef get16bits 33 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ 34 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) 35 #define get16bits(d) (*((const uint16_t *) (d))) 36 #endif 37 38 #if !defined (get16bits) 39 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\ 40 +(uint32_t)(((const uint8_t *)(d))[0]) ) 41 #endif 42 43 uint32_t SuperFastHash (const char * data, int len, uint32_t hash) { 44 uint32_t tmp; 45 int rem; 46 47 if (len <= 0 || data == NULL) return 0; 48 49 rem = len & 3; 50 len >>= 2; 51 52 /* Main loop */ 53 for (;len > 0; len--) { 54 hash += get16bits (data); 55 tmp = (get16bits (data+2) << 11) ^ hash; 56 hash = (hash << 16) ^ tmp; 57 data += 2*sizeof (uint16_t); 58 hash += hash >> 11; 59 } 60 61 /* Handle end cases */ 62 switch (rem) { 63 case 3: hash += get16bits (data); 64 hash ^= hash << 16; 65 hash ^= ((signed char)data[sizeof (uint16_t)]) << 18; 66 hash += hash >> 11; 67 break; 68 case 2: hash += get16bits (data); 69 hash ^= hash << 11; 70 hash += hash >> 17; 71 break; 72 case 1: hash += (signed char)*data; 73 hash ^= hash << 10; 74 hash += hash >> 1; 75 } 76 77 /* Force "avalanching" of final 127 bits */ 78 hash ^= hash << 3; 79 hash += hash >> 5; 80 hash ^= hash << 4; 81 hash += hash >> 17; 82 hash ^= hash << 25; 83 hash += hash >> 6; 84 85 return hash; 86 } 87
