superfasthash.c (3200B)
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 = (uint32_t)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 = (uint32_t)(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 ^= 64 (uint32_t)(((signed char)data[sizeof (uint16_t)]) << 18); 65 hash += hash >> 11; 66 break; 67 case 2: hash += get16bits (data); 68 hash ^= hash << 11; 69 hash += hash >> 17; 70 break; 71 case 1: hash += (uint32_t)((signed char)*data); 72 hash ^= hash << 10; 73 hash += hash >> 1; 74 } 75 76 /* Force "avalanching" of final 127 bits */ 77 hash ^= hash << 3; 78 hash += hash >> 5; 79 hash ^= hash << 4; 80 hash += hash >> 17; 81 hash ^= hash << 25; 82 hash += hash >> 6; 83 84 return hash; 85 }