From owner-freebsd-hackers@FreeBSD.ORG Sat Dec 29 02:32:19 2007 Return-Path: Delivered-To: hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id BD87316A41A; Sat, 29 Dec 2007 02:32:19 +0000 (UTC) (envelope-from youshi10@u.washington.edu) Received: from mxout5.cac.washington.edu (mxout5.cac.washington.edu [140.142.32.135]) by mx1.freebsd.org (Postfix) with ESMTP id 9ED7313C459; Sat, 29 Dec 2007 02:32:19 +0000 (UTC) (envelope-from youshi10@u.washington.edu) Received: from smtp.washington.edu (smtp.washington.edu [140.142.33.9] (may be forged)) by mxout5.cac.washington.edu (8.13.7+UW06.06/8.13.7+UW07.09) with ESMTP id lBT2WI4C027331 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Fri, 28 Dec 2007 18:32:19 -0800 X-Auth-Received: from [192.168.1.105] (c-76-22-52-184.hsd1.wa.comcast.net [76.22.52.184]) (authenticated authid=youshi10) by smtp.washington.edu (8.13.7+UW06.06/8.13.7+UW07.09) with ESMTP id lBT2WIPQ024687 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT); Fri, 28 Dec 2007 18:32:18 -0800 In-Reply-To: References: <5950EE0C-383D-4D6B-9991-A0DEABD2ADE4@u.washington.edu> <20071228003716.GB48997@lor.one-eyed-alien.net> Mime-Version: 1.0 (Apple Message framework v753) X-Gpgmail-State: !signed Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <1896C9EB-E6B3-4B7D-B354-7DE0774D685C@u.washington.edu> Content-Transfer-Encoding: 7bit From: Garrett Cooper Date: Fri, 28 Dec 2007 18:32:21 -0800 To: Ivan Voras X-Mailer: Apple Mail (2.753) X-PMX-Version: 5.4.1.325704, Antispam-Engine: 2.6.0.325393, Antispam-Data: 2007.12.28.181639 X-Uwash-Spam: Gauge=IIIIIII, Probability=7%, Report='__CT 0, __CTE 0, __CT_TEXT_PLAIN 0, __HAS_MSGID 0, __HAS_X_MAILER 0, __MIME_TEXT_ONLY 0, __MIME_VERSION 0, __SANE_MSGID 0' Cc: hackers@freebsd.org Subject: Re: BSD license compatible hash algorithm? X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 29 Dec 2007 02:32:19 -0000 On Dec 28, 2007, at 4:35 AM, Ivan Voras wrote: > Garrett Cooper wrote: > >> Looks promising, but how difficult would it be to port the >> code to other platforms (Win32 for instance?). > > The hash algorithm itself as implemented in hash.h is pretty much a > text-book hash algorithm (D.J.Bernstein's): > > #ifndef HASHINIT > #define HASHINIT 5381 > #define HASHSTEP(x,c) (((x << 5) + x) + (c)) > #endif > > /* > * Return a 32-bit hash of the given buffer. The init > * value should be 0, or the previous hash value to extend > * the previous hash. > */ > static __inline uint32_t > hash32_buf(const void *buf, size_t len, uint32_t hash) > { > const unsigned char *p = buf; > > while (len--) > hash = HASHSTEP(hash, *p++); > > return hash; > } > > It apparently has some weaknesses if used on binary (non-text) data > but I don't see why it wouldn't work on Windows. Well, when I mentioned 'difficulty to port to Windows', I was referring to the number of references that the API may have to This algorithm would be used for storage, but I could see potential for needing improved security, as someone changing the pkg db in memory could yield unwanted pkg installations or deletions, and just unwanted pkg behavior in general from occurring thanks to some malicious users.. Anyhow, thanks for the ideas I really do appreciate it. Overall, I think I will stick with BDB's hash(3) (seems less data collision prone, as was pointed out earlier, and less of a security risk) as I wasn't aware of the NULL argument, no filename 'clause' with dbopen(3). -Garrett