Path: utzoo!attcan!uunet!seismo!sundc!pitstop!sun!decwrl!purdue!mailrus!tut.cis.ohio-state.edu!osu-cis!att!cbnews!lvc
From: lvc@cbnews.ATT.COM (Lawrence V. Cipriani)
Newsgroups: comp.lang.c
Subject: Re: hash algorithm
Summary: feed in the result of the previous call
Message-ID: <951@cbnews.ATT.COM>
Date: 24 Aug 88 19:34:20 GMT
References: <654@novavax.UUCP> <2550078@hpisod2.HP.COM> <4712@b-tech.UUCP>
Organization: AT&T Bell Laboratories, Columbus
Lines: 45

In article <4712@b-tech.UUCP>, zeeff@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@cbnews.ATT.COM