From 5922eaf61adf6cdec7cb9e5d942a19102f969ec6 Mon Sep 17 00:00:00 2001 From: Simo Sorce Date: Wed, 24 Apr 2002 11:57:00 +0000 Subject: 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) --- source3/smbd/mangle.c | 1 + source3/smbd/mangle_hash2.c | 18 ++++++++++++++---- 2 files changed, 15 insertions(+), 4 deletions(-) (limited to 'source3/smbd') 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; } /* -- cgit