summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--libglusterfs/src/hashfn.c103
-rw-r--r--libglusterfs/src/hashfn.h2
-rw-r--r--xlators/cluster/dht/src/Makefile.am2
-rw-r--r--xlators/cluster/dht/src/dht-hashfn-tea.c141
-rw-r--r--xlators/cluster/dht/src/dht-hashfn.c10
5 files changed, 110 insertions, 148 deletions
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 <http://www.azillionmonkeys.com/qed/hash.html>
@@ -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. <http://www.zresearch.com>
- 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
- <http://www.gnu.org/licenses/>.
-*/
-
-
-#include <stdint.h>
-#include <stdio.h>
-#include <string.h>
-
-
-#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;
generated by cgit (git 2.34.1) at 2024-11-06 03:21:12 +0000