From 5d4981688b335b52f18e25c4c42c1314ed7e17df Mon Sep 17 00:00:00 2001 From: Brian Aker Date: Wed, 20 Jan 2010 18:51:52 -0800 Subject: [PATCH] Cleanup dead files in libmemcached. --- libhashkit/algorithm.c | 6 + libhashkit/algorithm.h | 3 + libmemcached/common.h | 16 -- libmemcached/crc.c | 86 --------- libmemcached/get.c | 4 +- libmemcached/hosts.c | 7 +- libmemcached/hsieh_hash.c | 68 ------- libmemcached/include.am | 8 - libmemcached/jenkins_hash.c | 213 ---------------------- libmemcached/md5.c | 354 ------------------------------------ libmemcached/murmur_hash.c | 76 -------- 11 files changed, 15 insertions(+), 826 deletions(-) delete mode 100644 libmemcached/crc.c delete mode 100644 libmemcached/hsieh_hash.c delete mode 100644 libmemcached/jenkins_hash.c delete mode 100644 libmemcached/md5.c delete mode 100644 libmemcached/murmur_hash.c diff --git a/libhashkit/algorithm.c b/libhashkit/algorithm.c index 3c486c77..380950e9 100644 --- a/libhashkit/algorithm.c +++ b/libhashkit/algorithm.c @@ -59,3 +59,9 @@ uint32_t libhashkit_md5(const char *key, size_t key_length) { return hashkit_md5(key, key_length, NULL); } + +void libhashkit_md5_signature(const unsigned char *key, uint32_t length, unsigned char *result) +{ + md5_signature(key, length, result); +} + diff --git a/libhashkit/algorithm.h b/libhashkit/algorithm.h index 465d0b5d..9e005eaf 100644 --- a/libhashkit/algorithm.h +++ b/libhashkit/algorithm.h @@ -82,6 +82,9 @@ uint32_t hashkit_jenkins(const char *key, size_t key_length, void *context); HASHKIT_LOCAL uint32_t hashkit_md5(const char *key, size_t key_length, void *context); +HASHKIT_API +void libhashkit_md5_signature(const unsigned char *key, uint32_t length, unsigned char *result); + #ifdef __cplusplus } #endif diff --git a/libmemcached/common.h b/libmemcached/common.h index 66dd43bc..1e1db2f5 100644 --- a/libmemcached/common.h +++ b/libmemcached/common.h @@ -95,22 +95,6 @@ typedef enum { #define SMALL_STRING_LEN 1024 #define HUGE_STRING_LEN 8196 -/* Hashing algo */ - -LIBMEMCACHED_LOCAL -void md5_signature(const unsigned char *key, unsigned int length, unsigned char *result); -LIBMEMCACHED_LOCAL -uint32_t hash_crc32(const char *data, - size_t data_len); -#ifdef HAVE_HSIEH_HASH -LIBMEMCACHED_LOCAL -uint32_t hsieh_hash(const char *key, size_t key_length); -#endif -LIBMEMCACHED_LOCAL -uint32_t murmur_hash(const char *key, size_t key_length); -LIBMEMCACHED_LOCAL -uint32_t jenkins_hash(const void *key, size_t length, uint32_t initval); - LIBMEMCACHED_LOCAL memcached_return_t memcached_connect(memcached_server_instance_st *ptr); LIBMEMCACHED_LOCAL diff --git a/libmemcached/crc.c b/libmemcached/crc.c deleted file mode 100644 index 90d3041c..00000000 --- a/libmemcached/crc.c +++ /dev/null @@ -1,86 +0,0 @@ -/* The crc32 functions and data was originally written by Spencer - * Garrett and was gleaned from the PostgreSQL source - * tree via the files contrib/ltree/crc32.[ch] and from FreeBSD at - * src/usr.bin/cksum/crc32.c. - */ - -#include "common.h" - -static const uint32_t crc32tab[256] = { - 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, - 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, - 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, - 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, - 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, - 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, - 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, - 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, - 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, - 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, - 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, - 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, - 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, - 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, - 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, - 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, - 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, - 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, - 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, - 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, - 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, - 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, - 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, - 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, - 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, - 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, - 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, - 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, - 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, - 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, - 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, - 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, - 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, - 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, - 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, - 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, - 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, - 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, - 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, - 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, - 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, - 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, - 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, - 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, - 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, - 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, - 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, - 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, - 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, - 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, - 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, - 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, - 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, - 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, - 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, - 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, - 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, - 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, - 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, - 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, - 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, - 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, - 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, - 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d, -}; - - -uint32_t hash_crc32(const char *key, size_t key_length) -{ - uint64_t x; - uint32_t crc= UINT32_MAX; - - for (x= 0; x < key_length; x++) - crc= (crc >> 8) ^ crc32tab[(crc ^ (uint64_t)key[x]) & 0xff]; - - return ~crc; -} diff --git a/libmemcached/get.c b/libmemcached/get.c index a7d0ebc6..1261d690 100644 --- a/libmemcached/get.c +++ b/libmemcached/get.c @@ -588,10 +588,10 @@ static memcached_return_t binary_mget_by_key(memcached_st *ptr, } if (is_master_key_set) - for (unsigned int x= 0; x < number_of_keys; x++) + for (size_t x= 0; x < number_of_keys; x++) hash[x]= master_server_key; else - for (unsigned int x= 0; x < number_of_keys; x++) + for (size_t x= 0; x < number_of_keys; x++) hash[x]= memcached_generate_hash(ptr, keys[x], key_length[x]); rc= replication_binary_mget(ptr, hash, dead_servers, keys, diff --git a/libmemcached/hosts.c b/libmemcached/hosts.c index ea02e7d4..9d8870dc 100644 --- a/libmemcached/hosts.c +++ b/libmemcached/hosts.c @@ -63,11 +63,12 @@ memcached_return_t run_distribution(memcached_st *ptr) return MEMCACHED_SUCCESS; } -static uint32_t ketama_server_hash(const char *key, unsigned int key_length, int alignment) +static uint32_t ketama_server_hash(const char *key, unsigned int key_length, uint32_t alignment) { unsigned char results[16]; - md5_signature((unsigned char*)key, key_length, results); + libhashkit_md5_signature((unsigned char*)key, key_length, results); + return ((uint32_t) (results[3 + alignment * 4] & 0xFF) << 24) | ((uint32_t) (results[2 + alignment * 4] & 0xFF) << 16) | ((uint32_t) (results[1 + alignment * 4] & 0xFF) << 8) @@ -215,7 +216,7 @@ static memcached_return_t update_continuum(memcached_st *ptr) { for (uint32_t x = 0; x < pointer_per_hash; x++) { - value= ketama_server_hash(sort_host, (uint32_t) sort_host_length, (int) x); + value= ketama_server_hash(sort_host, (uint32_t) sort_host_length, x); ptr->continuum[continuum_index].index= host_index; ptr->continuum[continuum_index++].value= value; } diff --git a/libmemcached/hsieh_hash.c b/libmemcached/hsieh_hash.c deleted file mode 100644 index 91d515f2..00000000 --- a/libmemcached/hsieh_hash.c +++ /dev/null @@ -1,68 +0,0 @@ -/* By Paul Hsieh (C) 2004, 2005. Covered under the Paul Hsieh - * derivative license. - * See: http://www.azillionmonkeys.com/qed/weblicense.html for license - * details. - * http://www.azillionmonkeys.com/qed/hash.html -*/ - -#include "common.h" - -#undef get16bits -#if (defined(__GNUC__) && defined(__i386__)) -#define get16bits(d) (*((const uint16_t *) (d))) -#endif - -#if !defined (get16bits) -#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\ - +(uint32_t)(((const uint8_t *)(d))[0]) ) -#endif - -uint32_t hsieh_hash(const char *key, size_t key_length) -{ - uint32_t hash = 0, tmp; - int rem; - - if (key_length <= 0 || key == NULL) - return 0; - - rem = key_length & 3; - key_length >>= 2; - - /* Main loop */ - for (;key_length > 0; key_length--) - { - hash += get16bits (key); - tmp = (get16bits (key+2) << 11) ^ hash; - hash = (hash << 16) ^ tmp; - key += 2*sizeof (uint16_t); - hash += hash >> 11; - } - - /* Handle end cases */ - switch (rem) - { - case 3: hash += get16bits (key); - hash ^= hash << 16; - hash ^= key[sizeof (uint16_t)] << 18; - hash += hash >> 11; - break; - case 2: hash += get16bits (key); - hash ^= hash << 11; - hash += hash >> 17; - break; - case 1: hash += *key; - hash ^= hash << 10; - hash += hash >> 1; - } - - /* Force "avalanching" of final 127 bits */ - hash ^= hash << 3; - hash += hash >> 5; - hash ^= hash << 4; - hash += hash >> 17; - hash ^= hash << 25; - hash += hash >> 6; - - return hash; -} - diff --git a/libmemcached/include.am b/libmemcached/include.am index a786b222..88c3a5ca 100644 --- a/libmemcached/include.am +++ b/libmemcached/include.am @@ -85,7 +85,6 @@ libmemcached_libmemcached_la_SOURCES = \ libmemcached/auto.c \ libmemcached/behavior.c \ libmemcached/connect.c \ - libmemcached/crc.c \ libmemcached/delete.c \ libmemcached/do.c \ libmemcached/dump.c \ @@ -96,11 +95,8 @@ libmemcached_libmemcached_la_SOURCES = \ libmemcached/hash.c \ libmemcached/hosts.c \ libmemcached/io.c \ - libmemcached/jenkins_hash.c \ libmemcached/key.c \ - libmemcached/md5.c \ libmemcached/memcached.c \ - libmemcached/murmur_hash.c \ libmemcached/parse.c \ libmemcached/purge.c \ libmemcached/quit.c \ @@ -114,10 +110,6 @@ libmemcached_libmemcached_la_SOURCES = \ libmemcached/version.c -if INCLUDE_HSIEH_SRC -libmemcached_libmemcached_la_SOURCES += libmemcached/hsieh_hash.c -endif - libmemcached_libmemcached_la_DEPENDENCIES= libmemcached/libmemcachedcallbacks.la libmemcached/libmemcachedinternal.la libhashkit/libhashkit.la libmemcached_libmemcached_la_LIBADD= $(LIBM) libmemcached/libmemcachedcallbacks.la libmemcached/libmemcachedinternal.la libhashkit/libhashkit.la libmemcached_libmemcached_la_LDFLAGS= ${AM_LDFLAGS} -version-info ${MEMCACHED_LIBRARY_VERSION} diff --git a/libmemcached/jenkins_hash.c b/libmemcached/jenkins_hash.c deleted file mode 100644 index e4aa4f19..00000000 --- a/libmemcached/jenkins_hash.c +++ /dev/null @@ -1,213 +0,0 @@ -/* -* -* By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this -* code any way you wish, private, educational, or commercial. It's free. -* Use for hash table lookup, or anything where one collision in 2^^32 is -* acceptable. Do NOT use for cryptographic purposes. -* http://burtleburtle.net/bob/hash/index.html -* -* Modified by Brian Pontz for libmemcached -* TODO: -* Add big endian support -*/ - -#include "common.h" - -#define hashsize(n) ((uint32_t)1<<(n)) -#define hashmask(n) (hashsize(n)-1) -#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) - -#define mix(a,b,c) \ -{ \ - a -= c; a ^= rot(c, 4); c += b; \ - b -= a; b ^= rot(a, 6); a += c; \ - c -= b; c ^= rot(b, 8); b += a; \ - a -= c; a ^= rot(c,16); c += b; \ - b -= a; b ^= rot(a,19); a += c; \ - c -= b; c ^= rot(b, 4); b += a; \ -} - -#define final(a,b,c) \ -{ \ - c ^= b; c -= rot(b,14); \ - a ^= c; a -= rot(c,11); \ - b ^= a; b -= rot(a,25); \ - c ^= b; c -= rot(b,16); \ - a ^= c; a -= rot(c,4); \ - b ^= a; b -= rot(a,14); \ - c ^= b; c -= rot(b,24); \ -} - -/* -jenkins_hash() -- hash a variable-length key into a 32-bit value - k : the key (the unaligned variable-length array of bytes) - length : the length of the key, counting by bytes - initval : can be any 4-byte value -Returns a 32-bit value. Every bit of the key affects every bit of -the return value. Two keys differing by one or two bits will have -totally different hash values. - -The best hash table sizes are powers of 2. There is no need to do -mod a prime (mod is sooo slow!). If you need less than 32 bits, -use a bitmask. For example, if you need only 10 bits, do - h = (h & hashmask(10)); -In which case, the hash table should have hashsize(10) elements. -*/ - -uint32_t jenkins_hash(const void *key, size_t length, uint32_t initval) -{ - uint32_t a,b,c; /* internal state */ - union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ - - /* Set up the internal state */ - a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; - - u.ptr = key; -#ifndef WORDS_BIGENDIAN - if ((u.i & 0x3) == 0) - { - const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ - - /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ - while (length > 12) - { - a += k[0]; - b += k[1]; - c += k[2]; - mix(a,b,c); - length -= 12; - k += 3; - } - - /*----------------------------- handle the last (probably partial) block */ - /* - * "k[2]&0xffffff" actually reads beyond the end of the string, but - * then masks off the part it's not allowed to read. Because the - * string is aligned, the masked-off tail is in the same word as the - * rest of the string. Every machine with memory protection I've seen - * does it on word boundaries, so is OK with this. But VALGRIND will - * still catch it and complain. The masking trick does make the hash - * noticably faster for short strings (like English words). - */ - switch(length) - { - case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; - case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; - case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; - case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; - case 8 : b+=k[1]; a+=k[0]; break; - case 7 : b+=k[1]&0xffffff; a+=k[0]; break; - case 6 : b+=k[1]&0xffff; a+=k[0]; break; - case 5 : b+=k[1]&0xff; a+=k[0]; break; - case 4 : a+=k[0]; break; - case 3 : a+=k[0]&0xffffff; break; - case 2 : a+=k[0]&0xffff; break; - case 1 : a+=k[0]&0xff; break; - case 0 : return c; /* zero length strings require no mixing */ - default: return c; - } - - } - else if ((u.i & 0x1) == 0) - { - const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ - const uint8_t *k8; - - /*--------------- all but last block: aligned reads and different mixing */ - while (length > 12) - { - a += k[0] + (((uint32_t)k[1])<<16); - b += k[2] + (((uint32_t)k[3])<<16); - c += k[4] + (((uint32_t)k[5])<<16); - mix(a,b,c); - length -= 12; - k += 6; - } - - /*----------------------------- handle the last (probably partial) block */ - k8 = (const uint8_t *)k; - switch(length) - { - case 12: c+=k[4]+(((uint32_t)k[5])<<16); - b+=k[2]+(((uint32_t)k[3])<<16); - a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ - case 10: c+=k[4]; - b+=k[2]+(((uint32_t)k[3])<<16); - a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 9 : c+=k8[8]; /* fall through */ - case 8 : b+=k[2]+(((uint32_t)k[3])<<16); - a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ - case 6 : b+=k[2]; - a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 5 : b+=k8[4]; /* fall through */ - case 4 : a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ - case 2 : a+=k[0]; - break; - case 1 : a+=k8[0]; - break; - case 0 : return c; /* zero length requires no mixing */ - default: return c; - } - - } - else - { /* need to read the key one byte at a time */ -#endif /* little endian */ - const uint8_t *k = (const uint8_t *)key; - - /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ - while (length > 12) - { - a += k[0]; - a += ((uint32_t)k[1])<<8; - a += ((uint32_t)k[2])<<16; - a += ((uint32_t)k[3])<<24; - b += k[4]; - b += ((uint32_t)k[5])<<8; - b += ((uint32_t)k[6])<<16; - b += ((uint32_t)k[7])<<24; - c += k[8]; - c += ((uint32_t)k[9])<<8; - c += ((uint32_t)k[10])<<16; - c += ((uint32_t)k[11])<<24; - mix(a,b,c); - length -= 12; - k += 12; - } - - /*-------------------------------- last block: affect all 32 bits of (c) */ - switch(length) /* all the case statements fall through */ - { - case 12: c+=((uint32_t)k[11])<<24; - case 11: c+=((uint32_t)k[10])<<16; - case 10: c+=((uint32_t)k[9])<<8; - case 9 : c+=k[8]; - case 8 : b+=((uint32_t)k[7])<<24; - case 7 : b+=((uint32_t)k[6])<<16; - case 6 : b+=((uint32_t)k[5])<<8; - case 5 : b+=k[4]; - case 4 : a+=((uint32_t)k[3])<<24; - case 3 : a+=((uint32_t)k[2])<<16; - case 2 : a+=((uint32_t)k[1])<<8; - case 1 : a+=k[0]; - break; - case 0 : return c; - default : return c; - } -#ifndef WORDS_BIGENDIAN - } -#endif - - final(a,b,c); - return c; -} - - diff --git a/libmemcached/md5.c b/libmemcached/md5.c deleted file mode 100644 index 6558d5c8..00000000 --- a/libmemcached/md5.c +++ /dev/null @@ -1,354 +0,0 @@ -/* - This Library has been modified from its original form by - Brian Aker (brian@tangent.org) - - See below for original Copyright. -*/ -/* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm - */ - -/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All -rights reserved. - -License to copy and use this software is granted provided that it -is identified as the "RSA Data Security, Inc. MD5 Message-Digest -Algorithm" in all material mentioning or referencing this software -or this function. - -License is also granted to make and use derivative works provided -that such works are identified as "derived from the RSA Data -Security, Inc. MD5 Message-Digest Algorithm" in all material -mentioning or referencing the derived work. - -RSA Data Security, Inc. makes no representations concerning either -the merchantability of this software or the suitability of this -software for any particular purpose. It is provided "as is" -without express or implied warranty of any kind. - -These notices must be retained in any copies of any part of this -documentation and/or software. -*/ - - -#include "common.h" - -#include -#include - -/* POINTER defines a generic pointer type */ -typedef unsigned char *POINTER; - - -/* UINT4 defines a four byte word */ -typedef unsigned int UINT4; - - -/* MD5 context. */ -typedef struct { - UINT4 state[4]; /* state (ABCD) */ - UINT4 count[2]; /* number of bits, modulo 2^64 (lsb first) */ - unsigned char buffer[64]; /* input buffer */ -} MD5_CTX; - -static void MD5Init (MD5_CTX *context); /* context */ -static void MD5Update ( MD5_CTX *context, /* context */ - const unsigned char *input, /* input block */ - unsigned int inputLen); /* length of input block */ -static void MD5Final ( unsigned char digest[16], /* message digest */ - MD5_CTX *context); /* context */ - -/* Constants for MD5Transform routine. */ - -#define S11 7 -#define S12 12 -#define S13 17 -#define S14 22 -#define S21 5 -#define S22 9 -#define S23 14 -#define S24 20 -#define S31 4 -#define S32 11 -#define S33 16 -#define S34 23 -#define S41 6 -#define S42 10 -#define S43 15 -#define S44 21 - - -static void MD5Transform (UINT4 state[4], - unsigned char block[64]); -static void Encode (unsigned char *output, - UINT4 *input, - unsigned int len); -static void Decode(UINT4 *output, unsigned char *input, unsigned int len); - -static unsigned char PADDING[64] = { - 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 -}; - -/* F, G, H and I are basic MD5 functions. - */ -#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) -#define G(x, y, z) (((x) & (z)) | ((y) & (~z))) -#define H(x, y, z) ((x) ^ (y) ^ (z)) -#define I(x, y, z) ((y) ^ ((x) | (~z))) - -/* ROTATE_LEFT rotates x left n bits. - */ -#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) - -/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4. -Rotation is separate from addition to prevent recomputation. - */ -#define FF(a, b, c, d, x, s, ac) { \ - (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \ - (a) = ROTATE_LEFT ((a), (s)); \ - (a) += (b); \ - } -#define GG(a, b, c, d, x, s, ac) { \ - (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \ - (a) = ROTATE_LEFT ((a), (s)); \ - (a) += (b); \ - } -#define HH(a, b, c, d, x, s, ac) { \ - (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \ - (a) = ROTATE_LEFT ((a), (s)); \ - (a) += (b); \ - } -#define II(a, b, c, d, x, s, ac) { \ - (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \ - (a) = ROTATE_LEFT ((a), (s)); \ - (a) += (b); \ - } - - -/* - Just a simple method for getting the signature - result must be == 16 -*/ -void md5_signature(const unsigned char *key, unsigned int length, unsigned char *result) -{ - MD5_CTX my_md5; - - MD5Init(&my_md5); - (void)MD5Update(&my_md5, key, length); - MD5Final(result, &my_md5); -} - -/* MD5 initialization. Begins an MD5 operation, writing a new context. - */ -static void MD5Init (MD5_CTX *context) /* context */ -{ - context->count[0] = context->count[1] = 0; - /* Load magic initialization constants. -*/ - context->state[0] = 0x67452301; - context->state[1] = 0xefcdab89; - context->state[2] = 0x98badcfe; - context->state[3] = 0x10325476; -} - -/* MD5 block update operation. Continues an MD5 message-digest - operation, processing another message block, and updating the - context. - */ - -static void MD5Update ( - MD5_CTX *context, /* context */ - const unsigned char *input, /* input block */ - unsigned int inputLen) /* length of input block */ -{ - unsigned int i, idx, partLen; - - /* Compute number of bytes mod 64 */ - idx = (unsigned int)((context->count[0] >> 3) & 0x3F); - - - /* Update number of bits */ - if ((context->count[0] += ((UINT4)inputLen << 3)) - < ((UINT4)inputLen << 3)) - context->count[1]++; - context->count[1] += ((UINT4)inputLen >> 29); - - partLen = 64 - idx; - - /* Transform as many times as possible. -*/ - if (inputLen >= partLen) { - memcpy((POINTER)&context->buffer[idx], (POINTER)input, partLen); - MD5Transform(context->state, context->buffer); - - for (i = partLen; i + 63 < inputLen; i += 64) - MD5Transform (context->state, (unsigned char *)&input[i]); - - idx = 0; - } - else - i = 0; - - /* Buffer remaining input */ - memcpy((POINTER)&context->buffer[idx], (POINTER)&input[i], - inputLen-i); -} - -/* MD5 finalization. Ends an MD5 message-digest operation, writing the - the message digest and zeroizing the context. - */ - -static void MD5Final ( - unsigned char digest[16], /* message digest */ - MD5_CTX *context) /* context */ -{ - unsigned char bits[8]; - unsigned int idx, padLen; - - /* Save number of bits */ - Encode (bits, context->count, 8); - - /* Pad out to 56 mod 64. -*/ - idx = (unsigned int)((context->count[0] >> 3) & 0x3f); - padLen = (idx < 56) ? (56 - idx) : (120 - idx); - MD5Update (context, PADDING, padLen); - - /* Append length (before padding) */ - MD5Update (context, bits, 8); - - /* Store state in digest */ - Encode (digest, context->state, 16); - - /* Zeroize sensitive information. -*/ - memset((POINTER)context, 0, sizeof (*context)); -} - -/* MD5 basic transformation. Transforms state based on block. - */ -static void MD5Transform ( - UINT4 state[4], - unsigned char block[64]) -{ - UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16]; - - Decode (x, block, 64); - - /* Round 1 */ - FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */ - FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */ - FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */ - FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */ - FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */ - FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */ - FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */ - FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */ - FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */ - FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */ - FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */ - FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */ - FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */ - FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */ - FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */ - FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */ - - /* Round 2 */ - GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */ - GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */ - GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */ - GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */ - GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */ - GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */ - GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */ - GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */ - GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */ - GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */ - GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */ - GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */ - GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */ - GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */ - GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */ - GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */ - - /* Round 3 */ - HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */ - HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */ - HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */ - HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */ - HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */ - HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */ - HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */ - HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */ - HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */ - HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */ - HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */ - HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */ - HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */ - HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */ - HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */ - HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */ - - /* Round 4 */ - II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */ - II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */ - II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */ - II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */ - II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */ - II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */ - II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */ - II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */ - II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */ - II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */ - II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */ - II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */ - II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */ - II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */ - II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */ - II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */ - - - state[0] += a; - state[1] += b; - state[2] += c; - state[3] += d; - - /* Zeroize sensitive information. -*/ - memset((POINTER)x, 0, sizeof (x)); -} - -/* Encodes input (UINT4) into output (unsigned char). Assumes len is - a multiple of 4. - */ -static void Encode ( -unsigned char *output, -UINT4 *input, -unsigned int len) -{ - unsigned int i, j; - - for (i = 0, j = 0; j < len; i++, j += 4) { - output[j] = (unsigned char)(input[i] & 0xff); - output[j+1] = (unsigned char)((input[i] >> 8) & 0xff); - output[j+2] = (unsigned char)((input[i] >> 16) & 0xff); - output[j+3] = (unsigned char)((input[i] >> 24) & 0xff); - } -} - - -/* Decodes input (unsigned char) into output (UINT4). Assumes len is - a multiple of 4. - */ -static void Decode ( -UINT4 *output, -unsigned char *input, -unsigned int len) -{ - unsigned int i, j; - - for (i = 0, j = 0; j < len; i++, j += 4) - output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) | - (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24); -} diff --git a/libmemcached/murmur_hash.c b/libmemcached/murmur_hash.c deleted file mode 100644 index f1c3267c..00000000 --- a/libmemcached/murmur_hash.c +++ /dev/null @@ -1,76 +0,0 @@ -/* - "Murmur" hash provided by Austin, tanjent@gmail.com - http://murmurhash.googlepages.com/ - - Note - This code makes a few assumptions about how your machine behaves - - - 1. We can read a 4-byte value from any address without crashing - 2. sizeof(int) == 4 - - And it has a few limitations - - 1. It will not work incrementally. - 2. It will not produce the same results on little-endian and big-endian - machines. - - Updated to murmur2 hash - BP -*/ - -#include "common.h" - -uint32_t murmur_hash(const char *key, size_t length) -{ - /* - 'm' and 'r' are mixing constants generated offline. They're not - really 'magic', they just happen to work well. - */ - - const unsigned int m= 0x5bd1e995; - const uint32_t seed= (0xdeadbeef * (uint32_t)length); - const int r= 24; - - - // Initialize the hash to a 'random' value - - uint32_t h= seed ^ (uint32_t)length; - - // Mix 4 bytes at a time into the hash - - const unsigned char * data= (const unsigned char *)key; - - while(length >= 4) - { - unsigned int k = *(unsigned int *)data; - - k *= m; - k ^= k >> r; - k *= m; - - h *= m; - h ^= k; - - data += 4; - length -= 4; - } - - // Handle the last few bytes of the input array - - switch(length) - { - case 3: h ^= ((uint32_t)data[2]) << 16; - case 2: h ^= ((uint32_t)data[1]) << 8; - case 1: h ^= data[0]; - h *= m; - default: break; - }; - - /* - Do a few final mixes of the hash to ensure the last few bytes are - well-incorporated. - */ - - h ^= h >> 13; - h *= m; - h ^= h >> 15; - - return (uint32_t) h; -} -- 2.30.2