From f097e77ffb386dc73e3639af4a9cd57df0d3d40d Mon Sep 17 00:00:00 2001 From: Basavanagowda Kanur Date: Fri, 27 Feb 2009 00:36:23 +0530 Subject: moved dht_hashfn_tea() to libglusterfs/hashfn.c as gf_dm_hashfn() (dm - davies-meyer). moved dht_hashfn_tea() to libglusterfs/src/hashfn.c as gf_dm_hashfn(). Signed-off-by: Anand V. Avati --- libglusterfs/src/hashfn.c | 103 ++++++++++++++++++++++ libglusterfs/src/hashfn.h | 2 + xlators/cluster/dht/src/Makefile.am | 2 +- xlators/cluster/dht/src/dht-hashfn-tea.c | 141 ------------------------------- xlators/cluster/dht/src/dht-hashfn.c | 10 +-- 5 files changed, 110 insertions(+), 148 deletions(-) delete mode 100644 xlators/cluster/dht/src/dht-hashfn-tea.c diff --git a/libglusterfs/src/hashfn.c b/libglusterfs/src/hashfn.c index 810cc92495e..9ef8955a87d 100644 --- a/libglusterfs/src/hashfn.c +++ b/libglusterfs/src/hashfn.c @@ -29,6 +29,10 @@ #define get16bits(d) (*((const uint16_t *) (d))) +#define DM_DELTA 0x9E3779B9 +#define DM_FULLROUNDS 10 /* 32 is overkill, 16 is strong crypto */ +#define DM_PARTROUNDS 6 /* 6 gets complete mixing */ + /* This is apparently the "fastest hash function for strings". Written by Paul Hsieh @@ -87,3 +91,102 @@ uint32_t SuperFastHash (const char * data, int32_t len) { return hash; } + + +/* Davies-Meyer hashing function implementation + */ +static int +dm_round (int rounds, uint32_t *array, uint32_t *h0, uint32_t *h1) +{ + uint32_t sum = 0; + int n = 0; + uint32_t b0 = 0; + uint32_t b1 = 0; + + b0 = *h0; + b1 = *h1; + + n = rounds; + + do { + sum += DM_DELTA; + b0 += ((b1 << 4) + array[0]) + ^ (b1 + sum) + ^ ((b1 >> 5) + array[1]); + b1 += ((b0 << 4) + array[2]) + ^ (b0 + sum) + ^ ((b0 >> 5) + array[3]); + } while (--n); + + *h0 += b0; + *h1 += b1; + + return 0; +} + + +uint32_t +__pad (int len) +{ + uint32_t pad = 0; + + pad = (uint32_t) len | ((uint32_t) len << 8); + pad |= pad << 16; + + return pad; +} + +uint32_t +gf_dm_hashfn (const char *msg, int len) +{ + uint32_t h0 = 0x9464a485; + uint32_t h1 = 0x542e1a94; + uint32_t array[4]; + uint32_t pad = 0; + int i = 0; + int j = 0; + int full_quads = 0; + int full_words = 0; + int full_bytes = 0; + uint32_t *intmsg = NULL; + int word = 0; + + + intmsg = (uint32_t *) msg; + pad = __pad (len); + + full_bytes = len; + full_words = len / 4; + full_quads = len / 16; + + for (i = 0; i < full_quads; i++) { + for (j = 0; j < 4; j++) { + word = *intmsg; + array[j] = word; + intmsg++; + full_words--; + full_bytes -= 4; + } + dm_round (DM_PARTROUNDS, &array[0], &h0, &h1); + } + + for (j = 0; j < 4; j++) { + if (full_words) { + word = *intmsg; + array[j] = word; + intmsg++; + full_words--; + full_bytes -= 4; + } else { + array[j] = pad; + while (full_bytes) { + array[j] <<= 8; + array[j] |= msg[len - full_bytes]; + full_bytes--; + } + } + } + dm_round (DM_FULLROUNDS, &array[0], &h0, &h1); + + return h0 ^ h1; +} diff --git a/libglusterfs/src/hashfn.h b/libglusterfs/src/hashfn.h index 1eea181f2a4..92481126d2d 100644 --- a/libglusterfs/src/hashfn.h +++ b/libglusterfs/src/hashfn.h @@ -30,4 +30,6 @@ uint32_t SuperFastHash (const char * data, int32_t len); +uint32_t gf_dm_hashfn (const char *msg, int len); + #endif /* __HASHFN_H__ */ diff --git a/xlators/cluster/dht/src/Makefile.am b/xlators/cluster/dht/src/Makefile.am index b7d07d137a6..d4e0752a585 100644 --- a/xlators/cluster/dht/src/Makefile.am +++ b/xlators/cluster/dht/src/Makefile.am @@ -4,7 +4,7 @@ xlatordir = $(libdir)/glusterfs/$(PACKAGE_VERSION)/xlator/cluster dht_common_source = dht-layout.c dht-helper.c dht-linkfile.c \ - dht-selfheal.c dht-rename.c dht-hashfn.c dht-hashfn-tea.c + dht-selfheal.c dht-rename.c dht-hashfn.c dht_la_SOURCES = $(dht_common_source) dht.c diff --git a/xlators/cluster/dht/src/dht-hashfn-tea.c b/xlators/cluster/dht/src/dht-hashfn-tea.c deleted file mode 100644 index 3eca35dd4ad..00000000000 --- a/xlators/cluster/dht/src/dht-hashfn-tea.c +++ /dev/null @@ -1,141 +0,0 @@ -/* - Copyright (c) 2008-2009 Z RESEARCH, Inc. - This file is part of GlusterFS. - - GlusterFS is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published - by the Free Software Foundation; either version 3 of the License, - or (at your option) any later version. - - GlusterFS is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see - . -*/ - - -#include -#include -#include - - -#define DELTA 0x9E3779B9 -#define FULLROUNDS 10 /* 32 is overkill, 16 is strong crypto */ -#define PARTROUNDS 6 /* 6 gets complete mixing */ - - -static int -tearound (int rounds, uint32_t *array, uint32_t *h0, uint32_t *h1) -{ - uint32_t sum = 0; - int n = 0; - uint32_t b0 = 0; - uint32_t b1 = 0; - - b0 = *h0; - b1 = *h1; - - n = rounds; - - do { - sum += DELTA; - b0 += ((b1 << 4) + array[0]) - ^ (b1 + sum) - ^ ((b1 >> 5) + array[1]); - b1 += ((b0 << 4) + array[2]) - ^ (b0 + sum) - ^ ((b0 >> 5) + array[3]); - } while (--n); - - *h0 += b0; - *h1 += b1; - - return 0; -} - - -uint32_t -__pad (int len) -{ - uint32_t pad = 0; - - pad = (uint32_t) len | ((uint32_t) len << 8); - pad |= pad << 16; - - return pad; -} - - -uint32_t -dht_hashfn_tea (const char *msg, int len) -{ - uint32_t h0 = 0x9464a485; - uint32_t h1 = 0x542e1a94; - uint32_t array[4]; - uint32_t pad = 0; - int i = 0; - int j = 0; - int full_quads = 0; - int full_words = 0; - int full_bytes = 0; - uint32_t *intmsg = NULL; - int word = 0; - - - intmsg = (uint32_t *) msg; - pad = __pad (len); - - full_bytes = len; - full_words = len / 4; - full_quads = len / 16; - - for (i = 0; i < full_quads; i++) { - for (j = 0; j < 4; j++) { - word = *intmsg; - array[j] = word; - intmsg++; - full_words--; - full_bytes -= 4; - } - tearound (PARTROUNDS, &array[0], &h0, &h1); - } - - for (j = 0; j < 4; j++) { - if (full_words) { - word = *intmsg; - array[j] = word; - intmsg++; - full_words--; - full_bytes -= 4; - } else { - array[j] = pad; - while (full_bytes) { - array[j] <<= 8; - array[j] |= msg[len - full_bytes]; - full_bytes--; - } - } - } - tearound (FULLROUNDS, &array[0], &h0, &h1); - - return h0 ^ h1; -} - - -#if 0 -int -main (int argc, char *argv[]) -{ - int i = 0; - int hashval = 0; - - for (i = 1; i < argc; i++) { - hashval = tea (argv[i], strlen (argv[i])); - printf ("%s: %x\n", argv[i], hashval); - } -} -#endif diff --git a/xlators/cluster/dht/src/dht-hashfn.c b/xlators/cluster/dht/src/dht-hashfn.c index ee89eb61afd..31cb828a483 100644 --- a/xlators/cluster/dht/src/dht-hashfn.c +++ b/xlators/cluster/dht/src/dht-hashfn.c @@ -26,13 +26,11 @@ #include "glusterfs.h" #include "xlator.h" #include "dht-common.h" - - -uint32_t dht_hashfn_tea (const char *name, int len); +#include "hashfn.h" typedef enum { - DHT_HASH_TYPE_TEA, + DHT_HASH_TYPE_DM, } dht_hashfn_type_t; @@ -43,8 +41,8 @@ dht_hash_compute_internal (int type, const char *name, uint32_t *hash_p) uint32_t hash = 0; switch (type) { - case DHT_HASH_TYPE_TEA: - hash = dht_hashfn_tea (name, strlen (name)); + case DHT_HASH_TYPE_DM: + hash = gf_dm_hashfn (name, strlen (name)); break; default: ret = -1; -- cgit