/*
** $Id: hash.c,v 1.2 2008/12/18 04:03:43 dredd Exp $
**
** $Source: /cvsroot/swlpc/swlpc/lpvm/hash.c,v $
** $Revision: 1.2 $
** $Date: 2008/12/18 04:03:43 $
** $State: Exp $
**
** Authors: Mike McGaughey & Geoff Wong, 1993-1998
** geoff.wong@gmail.com
** mmcgus@yahoo.com
**
** See the file "Copying" distributed with this file.
*/
#include "rhash.h"
int nhash = 0;
/* s - string, maxn - maximum # of chars, hashs - htable size */
int hashstr(char *s, int maxn, int hashs)
{
register unsigned int h = 0;
register unsigned char *p;
/*
* What's faster - table memory access (with 1 cycle delays)
* and 2 passes through the string, or a few adds? I'm betting on the adds.
*
* The following loop is carefully juggled so that the compiler
* can fill the memory load delay slot with a multiply (multiply
* is 1 cycle on mips, apparently) and doesn't need a temp for the
* pointer increment (hence it's a pre-increment; saves 1 load and
* brings the loop pipeline below 8 instructions). Mips compiler (-O2)
* isn't very clever about detecting this - hence the obtuse code.
* Also: Removing the tests on maxn makes the inner loop 30% faster
* (from 7 to 5 instructions), so it's out. Note that the hash
* value computed is a multiple of 3 - rectified in the return statement.
* NB: gcc chooses to use a shift and add instead of *3, but produces
* worse code for the rest of the loop!
*/
p = ((unsigned char *) s) - 1;
do
{
h = h * 3 + (*++p);
}
while (*p);
return (h / 3) % hashs; /* nb: h is unsigned, so this is positive */
#if 0
for (h = 0, i = 0, p = (unsigned char *) s; *p && i < maxn; i++, p++)
h = T[h ^ *p];
if (hashs > 256 && *s)
{
int oh = h;
for (i = 1, p = (unsigned char *) s, h = (*p++ + 1) & 0xff; *p && i < maxn; i++, p++)
h = T[h ^ *p];
h += (oh << 8);
}
return h % hashs; /* nb: h is unsigned, so this is positive */
#endif
}