1#include "dthdr.h"
2
3/* Hashing a string into an unsigned integer.
4** The basic method is to continuingly accumulate bytes and multiply
5** with some given prime. The length n of the string is added last.
6** The recurrent equation is like this:
7** h[k] = (h[k-1] + bytes)*prime for 0 <= k < n
8** h[n] = (h[n-1] + n)*prime
9** The prime is chosen to have a good distribution of 1-bits so that
10** the multiplication will distribute the bits in the accumulator well.
11** The below code accumulates 2 bytes at a time for speed.
12**
13** Written by Kiem-Phong Vo (02/28/03)
14*/
15
16uint dtstrhash(reg uint h, void* args, reg int n)
17{
18 reg unsigned char* s = (unsigned char*)args;
19
20 if(n <= 0)
21 { for(; *s != 0; s += s[1] ? 2 : 1)
22 h = (h + (s[0]<<8) + s[1])*DT_PRIME;
23 n = s - (unsigned char*)args;
24 }
25 else
26 { reg unsigned char* ends;
27 for(ends = s+n-1; s < ends; s += 2)
28 h = (h + (s[0]<<8) + s[1])*DT_PRIME;
29 if(s <= ends)
30 h = (h + (s[0]<<8))*DT_PRIME;
31 }
32 return (h+n)*DT_PRIME;
33}
34