1 | /*****************************************************************************/ |
2 | /* */ |
3 | /* hashfunc.c */ |
4 | /* */ |
5 | /* Hash functions */ |
6 | /* */ |
7 | /* */ |
8 | /* */ |
9 | /* (C) 1998-2011, Ullrich von Bassewitz */ |
10 | /* Roemerstrasse 52 */ |
11 | /* D-70794 Filderstadt */ |
12 | /* EMail: uz@cc65.org */ |
13 | /* */ |
14 | /* */ |
15 | /* This software is provided 'as-is', without any expressed or implied */ |
16 | /* warranty. In no event will the authors be held liable for any damages */ |
17 | /* arising from the use of this software. */ |
18 | /* */ |
19 | /* Permission is granted to anyone to use this software for any purpose, */ |
20 | /* including commercial applications, and to alter it and redistribute it */ |
21 | /* freely, subject to the following restrictions: */ |
22 | /* */ |
23 | /* 1. The origin of this software must not be misrepresented; you must not */ |
24 | /* claim that you wrote the original software. If you use this software */ |
25 | /* in a product, an acknowledgment in the product documentation would be */ |
26 | /* appreciated but is not required. */ |
27 | /* 2. Altered source versions must be plainly marked as such, and must not */ |
28 | /* be misrepresented as being the original software. */ |
29 | /* 3. This notice may not be removed or altered from any source */ |
30 | /* distribution. */ |
31 | /* */ |
32 | /*****************************************************************************/ |
33 | |
34 | |
35 | |
36 | /* common */ |
37 | #include "hashfunc.h" |
38 | |
39 | |
40 | |
41 | /*****************************************************************************/ |
42 | /* Code */ |
43 | /*****************************************************************************/ |
44 | |
45 | |
46 | |
47 | unsigned HashInt (unsigned V) |
48 | /* Return a hash value for the given integer. The function uses Robert |
49 | ** Jenkins' 32 bit integer hash function taken from |
50 | ** http://www.concentric.net/~ttwang/tech/inthash.htm |
51 | ** For 16 bit integers, the function may be suboptimal. |
52 | */ |
53 | { |
54 | V = (V + 0x7ed55d16) + (V << 12); |
55 | V = (V ^ 0xc761c23c) ^ (V >> 19); |
56 | V = (V + 0x165667b1) + (V << 5); |
57 | V = (V + 0xd3a2646c) ^ (V << 9); |
58 | V = (V + 0xfd7046c5) + (V << 3); |
59 | V = (V ^ 0xb55a4f09) ^ (V >> 16); |
60 | return V; |
61 | } |
62 | |
63 | |
64 | |
65 | unsigned HashStr (const char* S) |
66 | /* Return a hash value for the given string */ |
67 | { |
68 | unsigned L, H; |
69 | |
70 | /* Do the hash */ |
71 | H = L = 0; |
72 | while (*S) { |
73 | H = ((H << 3) ^ ((unsigned char) *S++)) + L++; |
74 | } |
75 | return H; |
76 | } |
77 | |
78 | |
79 | |
80 | unsigned HashBuf (const StrBuf* S) |
81 | /* Return a hash value for the given string buffer */ |
82 | { |
83 | unsigned I, L, H; |
84 | |
85 | /* Do the hash */ |
86 | H = L = 0; |
87 | for (I = 0; I < SB_GetLen (S); ++I) { |
88 | H = ((H << 3) ^ ((unsigned char) SB_AtUnchecked (S, I))) + L++; |
89 | } |
90 | return H; |
91 | } |
92 | |