xref: /titanic_50/usr/src/lib/libast/common/cdt/dtstrhash.c (revision 3e14f97f673e8a630f076077de35afdd43dc1587)
1da2e3ebdSchin /***********************************************************************
2da2e3ebdSchin *                                                                      *
3da2e3ebdSchin *               This software is part of the ast package               *
4*3e14f97fSRoger A. Faulkner *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
5da2e3ebdSchin *                      and is licensed under the                       *
6da2e3ebdSchin *                  Common Public License, Version 1.0                  *
77c2fbfb3SApril Chin *                    by AT&T Intellectual Property                     *
8da2e3ebdSchin *                                                                      *
9da2e3ebdSchin *                A copy of the License is available at                 *
10da2e3ebdSchin *            http://www.opensource.org/licenses/cpl1.0.txt             *
11da2e3ebdSchin *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
12da2e3ebdSchin *                                                                      *
13da2e3ebdSchin *              Information and Software Systems Research               *
14da2e3ebdSchin *                            AT&T Research                             *
15da2e3ebdSchin *                           Florham Park NJ                            *
16da2e3ebdSchin *                                                                      *
17da2e3ebdSchin *                 Glenn Fowler <gsf@research.att.com>                  *
18da2e3ebdSchin *                  David Korn <dgk@research.att.com>                   *
19da2e3ebdSchin *                   Phong Vo <kpv@research.att.com>                    *
20da2e3ebdSchin *                                                                      *
21da2e3ebdSchin ***********************************************************************/
22da2e3ebdSchin #include	"dthdr.h"
23da2e3ebdSchin 
24da2e3ebdSchin /* Hashing a string into an unsigned integer.
25da2e3ebdSchin ** The basic method is to continuingly accumulate bytes and multiply
26da2e3ebdSchin ** with some given prime. The length n of the string is added last.
27da2e3ebdSchin ** The recurrent equation is like this:
28da2e3ebdSchin **	h[k] = (h[k-1] + bytes)*prime	for 0 <= k < n
29da2e3ebdSchin **	h[n] = (h[n-1] + n)*prime
30da2e3ebdSchin ** The prime is chosen to have a good distribution of 1-bits so that
31da2e3ebdSchin ** the multiplication will distribute the bits in the accumulator well.
32da2e3ebdSchin ** The below code accumulates 2 bytes at a time for speed.
33da2e3ebdSchin **
34da2e3ebdSchin ** Written by Kiem-Phong Vo (02/28/03)
35da2e3ebdSchin */
36da2e3ebdSchin 
37da2e3ebdSchin #if __STD_C
dtstrhash(reg uint h,Void_t * args,reg int n)38da2e3ebdSchin uint dtstrhash(reg uint h, Void_t* args, reg int n)
39da2e3ebdSchin #else
40da2e3ebdSchin uint dtstrhash(h,args,n)
41da2e3ebdSchin reg uint	h;
42da2e3ebdSchin Void_t*		args;
43da2e3ebdSchin reg int		n;
44da2e3ebdSchin #endif
45da2e3ebdSchin {
46da2e3ebdSchin 	reg unsigned char*	s = (unsigned char*)args;
47da2e3ebdSchin 
48da2e3ebdSchin 	if(n <= 0)
49da2e3ebdSchin 	{	for(; *s != 0; s += s[1] ? 2 : 1)
50da2e3ebdSchin 			h = (h + (s[0]<<8) + s[1])*DT_PRIME;
51da2e3ebdSchin 		n = s - (unsigned char*)args;
52da2e3ebdSchin 	}
53da2e3ebdSchin 	else
54da2e3ebdSchin 	{	reg unsigned char*	ends;
55da2e3ebdSchin 		for(ends = s+n-1; s < ends; s += 2)
56da2e3ebdSchin 			h = (h + (s[0]<<8) + s[1])*DT_PRIME;
57da2e3ebdSchin 		if(s <= ends)
58da2e3ebdSchin 			h = (h + (s[0]<<8))*DT_PRIME;
59da2e3ebdSchin 	}
60da2e3ebdSchin 	return (h+n)*DT_PRIME;
61da2e3ebdSchin }
62