summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSimo Sorce <idra@samba.org>2002-04-24 11:57:00 +0000
committerSimo Sorce <idra@samba.org>2002-04-24 11:57:00 +0000
commit5922eaf61adf6cdec7cb9e5d942a19102f969ec6 (patch)
tree937a9e58ba5d80a43d1d1fd1baba1e2e11a6dcb4
parent193225dd424c72209b54d867fac64b7415cff529 (diff)
downloadsamba-5922eaf61adf6cdec7cb9e5d942a19102f969ec6.tar.gz
samba-5922eaf61adf6cdec7cb9e5d942a19102f969ec6.tar.bz2
samba-5922eaf61adf6cdec7cb9e5d942a19102f969ec6.zip
move to the FNV1 hash alghorithm seem good
the test revealed 15 collision with 1 Million long file names :-) Simo. (This used to be commit 77dc498b6f0c435f082eb2d934920d3f3bef0b65)
-rw-r--r--source3/smbd/mangle.c1
-rw-r--r--source3/smbd/mangle_hash2.c18
2 files changed, 15 insertions, 4 deletions
diff --git a/source3/smbd/mangle.c b/source3/smbd/mangle.c
index 20b2b419cf..66dd2c00b7 100644
--- a/source3/smbd/mangle.c
+++ b/source3/smbd/mangle.c
@@ -29,6 +29,7 @@ static struct {
} mangle_backends[] = {
{ "hash", mangle_hash_init },
{ "hash2", mangle_hash2_init },
+ /*{ "tdb", mangle_tdb_init }, */
{ NULL, NULL }
};
diff --git a/source3/smbd/mangle_hash2.c b/source3/smbd/mangle_hash2.c
index a473de38d6..1c8b0689a1 100644
--- a/source3/smbd/mangle_hash2.c
+++ b/source3/smbd/mangle_hash2.c
@@ -2,6 +2,7 @@
Unix SMB/CIFS implementation.
new hash based name mangling implementation
Copyright (C) Andrew Tridgell 2002
+ Copyright (C) Simo Sorce 2002
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -30,6 +31,10 @@
for simplicity, we only allow ascii characters in 8.3 names
*/
+ /* hash alghorithm changed to FNV1 by idra@samba.org (Simo Sorce).
+ * see http://www.isthe.com/chongo/tech/comp/fnv/index.html for a
+ * discussion on Fowler / Noll / Vo (FNV) Hash by one of it's authors
+ */
/*
===============================================================================
@@ -73,6 +78,10 @@
#define MANGLE_CACHE_SIZE 4096
#endif
+#define FNV1_PRIME 0x01000193
+/*the following number is a fnv1 of the string: idra@samba.org 2002 */
+#define FNV1_INIT 0xa6b93095
+
/* these tables are used to provide fast tests for characters */
static unsigned char char_flags[256];
@@ -121,13 +130,14 @@ static u32 mangle_hash(const char *key, unsigned length)
length = strlen(str);
/* Set the initial value from the key size. */
- for (value = 0x238F13AF * length, i=0; i < length; i++) {
- value = (value + (((unsigned char)str[i]) << (i*5 % 24)));
- }
+ for (value = FNV1_INIT, i=0; i < length; i++) {
+ value *= (u32)FNV1_PRIME;
+ value ^= (u32)(str[i]);
+ }
/* note that we force it to a 31 bit hash, to keep within the limits
of the 36^6 mangle space */
- return (1103515243 * value + 12345) & ~0x80000000;
+ return value & ~0x80000000;
}
/*