hash algorithm

[Lawrence V. Cipriani]

In article <4712 at b-tech.UUCP>, zeeff at b-tech.UUCP (Jon Zeeff) writes:
> /* This is a simplified version of the pathalias hashing function.
>  * Thanks to Steve Belovin and Peter Honeyman

> static long
> hash(name, size)
> register char *name;
> register int size;
> {
> 	register long sum = 0L;
> 
> 	while (size--) {
> 		sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
> 	}
> 	DEBUG("hash: returns (%ld)\n", sum % INDEX_SIZE);
> 	return(sum % INDEX_SIZE);
> }

If you change the routine to this:

static long
hash(name, size, sum)
register char *name;
register int size, sum;
{
	while (size--) {
		sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
	}
	DEBUG("hash: returns (%ld)\n", sum % INDEX_SIZE);
	return(sum % INDEX_SIZE);
}

where the initial value of sum is 0.  With the change you can
use hash() with data objects that won't fit in memory.  That is:

	int sum = 0; char iobuf[BUFSUZ];
	while ((nbytes = read(fd, iobuf, sizeof iobuf)) > 0)
		sum = hash(iobuf, nbytes, sum);

After the last call to hash, the value of sum is the sum for the
whole file.  This is not an original idea of mine.  I saw it in
a piece of 10 year old code.

-- 
Larry Cipriani, AT&T Network Systems, Columbus OH, cbnews!lvc lvc at cbnews.ATT.COM