Annotation of libaitcrc/src/hash.c, revision 1.1.2.2
1.1.2.1 misho 1: /*************************************************************************
2: * (C) 2009 AITNET ltd - Sofia/Bulgaria - <misho@aitbg.com>
3: * by Michael Pounov <misho@openbsd-bg.org>
4: *
5: * $Author: misho $
1.1.2.2 ! misho 6: * $Id: hash.c,v 1.1.2.1 2010/06/13 16:29:03 misho Exp $
1.1.2.1 misho 7: *
8: *************************************************************************/
9: #include "global.h"
10:
11:
12: /*
13: * hash_varchar() Compute index hash by variable length string
14: * @csStr = Input data buffer
15: * @nStrLen = Length of data buffer
16: * @nVer = Version of algorythm; 0 - original, 1 - AITNET variant
17: * return: Hash value
18: */
19: inline u_int
20: hash_varchar(const char *csStr, int nStrLen, int nVer)
21: {
22: register u_int n, hash = 0;
23: register int i;
24:
25: assert(csStr);
26:
27: for (i = 0; i < nStrLen; i++) {
28: n = 2 * hash + csStr[i];
29: if (!nVer) {
30: if (hash & 0x80000000)
31: n ^= 0xC0A0A0D5; // Polynom CRC-32 aviation
32: } else {
33: if (n & 1) // Misho ;) patch for better avalanche!!!
34: n ^= 0xC0A0A0D5; // Polynom CRC-32 aviation
35: }
36: hash = n;
37: }
38:
39: return hash;
40: }
41:
42: /*
43: * hash_bernstein() Compute index hash by Bernstein
44: * @csStr = Input data buffer
45: * @nStrLen = Length of data buffer
46: * @nVer = Version of algorythm; 0 - Bernstein, 1 - DJBX33A variant
47: * return: Hash value
48: */
49: inline u_int
50: hash_bernstein(const char *csStr, int nStrLen, int nVer)
51: {
52: register u_int hash = 5381;
53: register int i;
54:
55: assert(csStr);
56:
57: for (i = 0; i < nStrLen; i++)
58: if (!nVer)
59: hash = ((hash << 5) + hash) + csStr[i];
60: else
61: hash = hash * 33 + csStr[i]; // DJBX33A
62:
63: return hash;
64: }
65:
66: /*
67: * hash_fnv1() Compute index hash by FNV-1
68: * @csStr = Input data buffer
69: * @nStrLen = Length of data buffer
70: * @nVer = Version of algorythm; 0 - FNV-1, 1 - FNV-1a (best avalanche)
71: * return: Hash value
72: */
73: inline u_int
74: hash_fnv1(const char *csStr, int nStrLen, int nVer)
75: {
76: register u_int hash = 0x811c9dc5; // 2166136261
77: register int i;
78:
79: assert(csStr);
80:
81: for (i = 0; i < nStrLen; i++)
82: if (!nVer) { // FNV-1
83: hash *= 16777619;
84: hash ^= csStr[i];
85: } else { // FNV-1a
86: hash ^= csStr[i];
87: hash *= 16777619;
88: }
89:
90: return hash;
91: }
92:
93: /*
94: * hash_jenkins() Compute index hash by Jenkins (one-at-a-time)
95: * @csStr = Input data buffer
96: * @nStrLen = Length of data buffer
97: * return: Hash value
98: */
99: inline u_int
100: hash_jenkins(const char *csStr, int nStrLen)
101: {
102: register u_int hash = 0;
103: register int i;
104:
105: assert(csStr);
106:
107: for (i = 0; i < nStrLen; i++) {
108: hash += csStr[i];
109: hash += (hash << 10);
110: hash ^= (hash >> 6);
111: }
112: hash += (hash << 3);
113: hash ^= (hash >> 11);
114: hash += (hash << 15);
115:
116: return hash;
117: }
1.1.2.2 ! misho 118:
! 119: /*
! 120: * hash_reddragon() Compute index hash by Red Dragon
! 121: * @csStr = Input data buffer
! 122: * @nStrLen = Length of data buffer
! 123: * return: Hash value
! 124: */
! 125: inline u_int
! 126: hash_reddragon(const char *csStr, int nStrLen)
! 127: {
! 128: register u_int g, hash;
! 129: register int i;
! 130:
! 131: assert(csStr);
! 132:
! 133: for (hash = 0, i = 0; i < nStrLen; i++) {
! 134: hash = (hash << 4) + csStr[i];
! 135: if ((g = hash & 0xF0000000)) {
! 136: hash ^= g >> 24;
! 137: hash ^= g;
! 138: }
! 139: }
! 140:
! 141: return hash;
! 142: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>