1 /* vim:expandtab:shiftwidth=2:tabstop=2:smarttab: 2 * 3 * HashKit library 4 * 5 * Copyright (C) 2011-2012 Data Differential, http://datadifferential.com/ 6 * Copyright (C) 2006-2009 Brian Aker All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions are 10 * met: 11 * 12 * * Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * * Redistributions in binary form must reproduce the above 16 * copyright notice, this list of conditions and the following disclaimer 17 * in the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * * The names of its contributors may not be used to endorse or 21 * promote products derived from this software without specific prior 22 * written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 25 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 27 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 28 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 29 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 30 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 31 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 32 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 33 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 34 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 35 * 36 */ 37 38 /* By Paul Hsieh (C) 2004, 2005. Covered under the Paul Hsieh 39 * derivative license. 40 * See: http://www.azillionmonkeys.com/qed/weblicense.html for license 41 * details. 42 * http://www.azillionmonkeys.com/qed/hash.html 43 */ 44 45 #include <libhashkit/common.h> 46 47 #undef get16bits 48 #if (defined(__GNUC__) && defined(__i386__)) 49 #define get16bits(d) (*((const uint16_t *) (d))) 50 #endif 51 52 #if !defined (get16bits) 53 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\ 54 +(uint32_t)(((const uint8_t *)(d))[0]) ) 55 #endif 56 57 #ifdef HAVE_HSIEH_HASH 58 uint32_t hashkit_hsieh(const char *key, size_t key_length, void *) 59 { 60 uint32_t hash = 0, tmp; 61 int rem; 62 63 if (key_length <= 0 || key == NULL) 64 return 0; 65 66 rem = key_length & 3; 67 key_length >>= 2; 68 69 /* Main loop */ 70 for (;key_length > 0; key_length--) 71 { 72 hash += get16bits (key); 73 tmp = (get16bits (key+2) << 11) ^ hash; 74 hash = (hash << 16) ^ tmp; 75 key += 2*sizeof (uint16_t); 76 hash += hash >> 11; 77 } 78 79 /* Handle end cases */ 80 switch (rem) 81 { 82 case 3: hash += get16bits (key); 83 hash ^= hash << 16; 84 hash ^= (uint32_t)key[sizeof (uint16_t)] << 18; 85 hash += hash >> 11; 86 break; 87 case 2: hash += get16bits (key); 88 hash ^= hash << 11; 89 hash += hash >> 17; 90 break; 91 case 1: hash += (unsigned char)(*key); 92 hash ^= hash << 10; 93 hash += hash >> 1; 94 default: 95 break; 96 } 97 98 /* Force "avalanching" of final 127 bits */ 99 hash ^= hash << 3; 100 hash += hash >> 5; 101 hash ^= hash << 4; 102 hash += hash >> 17; 103 hash ^= hash << 25; 104 hash += hash >> 6; 105 106 return hash; 107 } 108 #else 109 uint32_t hashkit_hsieh(const char *, size_t , void *) 110 { 111 return 0; 112 } 113 #endif 114