[comp.sources.wanted] bit-scrambling hashing functions...

oz@yunexus.UUCP (Ozan Yigit) (05/22/89)

What I am looking for is a hash function (returning "long") that scrambles
bits very well: a small variation in the string should cause a large
variation in the bits.  I thought a hash function like the following
should be able to do this.  I am not familiar with CRC polynomials, nor
hash functions based on them.  Would someone knowledgeable on the topic
either provide a 32-bit version of this, or send me the appropriate
references on similar, or other bit-scrambling hash functions ??

Please mail. many thnx... oz
----
/* [from decus diff]
 * Return the CRC16 hash code for the buffer (but never 0).
 * Algorithm from Stu Wecker (Digital memo 130-959-002-00).
 * Since the value 0 is used as a flag, the hash will be
 * 1 if the CRC is 0.
 */

u_long crc16a[] = {
	0000000, 0140301, 0140601, 0000500, 
	0141401, 0001700, 0001200, 0141101,
	0143001, 0003300, 0003600, 0143501, 
	0002400, 0142701, 0142201, 0002100,
};
u_long crc16b[] = {
	0000000, 0146001, 0154001, 0012000, 
	0170001, 0036000, 0024000, 0162001,
	0120001, 0066000, 0074000, 0132001, 
	0050000, 0116001, 0104001, 0043000,
};

u_long
hash(str)
register char *str;
{
	register u_long crc;
	register u_long tmp;

	crc = 0;
	while (*str)
		tmp = *str++ ^ crc;    /* XOR crc with new char  */
		crc = (crc >> 8)
			^ crc16a[(tmp & 0017)]
			^ crc16b[(tmp & 0360) >> 4];
	}
	return ((crc == 0) ? (u_long) 1 : crc);
}



-- 
DEC-SI Suit: If Ford or GM had		Usenet:    oz@nexus.yorku.ca
patents on the way a tire is mounted    ......!uunet!utai!yunexus!oz
on an axle, we'd all be a lot poorer	Bitnet: oz@[yulibra|yuyetti]
right now.             [Mike Vizard]	Phonet: +1 416 736-5257x3976