Annotation of libelwix/src/hash.c, revision 1.1
1.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 $
! 6: * $Id: hash.c,v 1.4 2012/08/29 09:00:44 misho Exp $
! 7: *
! 8: **************************************************************************
! 9: The ELWIX and AITNET software is distributed under the following
! 10: terms:
! 11:
! 12: All of the documentation and software included in the ELWIX and AITNET
! 13: Releases is copyrighted by ELWIX - Sofia/Bulgaria <info@elwix.org>
! 14:
! 15: Copyright 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013
! 16: by Michael Pounov <misho@elwix.org>. All rights reserved.
! 17:
! 18: Redistribution and use in source and binary forms, with or without
! 19: modification, are permitted provided that the following conditions
! 20: are met:
! 21: 1. Redistributions of source code must retain the above copyright
! 22: notice, this list of conditions and the following disclaimer.
! 23: 2. Redistributions in binary form must reproduce the above copyright
! 24: notice, this list of conditions and the following disclaimer in the
! 25: documentation and/or other materials provided with the distribution.
! 26: 3. All advertising materials mentioning features or use of this software
! 27: must display the following acknowledgement:
! 28: This product includes software developed by Michael Pounov <misho@elwix.org>
! 29: ELWIX - Embedded LightWeight unIX and its contributors.
! 30: 4. Neither the name of AITNET nor the names of its contributors
! 31: may be used to endorse or promote products derived from this software
! 32: without specific prior written permission.
! 33:
! 34: THIS SOFTWARE IS PROVIDED BY AITNET AND CONTRIBUTORS ``AS IS'' AND
! 35: ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 36: IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 37: ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
! 38: FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
! 39: DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
! 40: OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
! 41: HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
! 42: LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
! 43: OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
! 44: SUCH DAMAGE.
! 45: */
! 46: #include "global.h"
! 47:
! 48:
! 49: /*
! 50: * hash_varchar() - Compute index hash by variable length string
! 51: *
! 52: * @csStr = Input data buffer
! 53: * @nStrLen = Length of data buffer
! 54: * @nVer = Version of algorythm; 0 - original, 1 - AITNET variant
! 55: * return: Hash value
! 56: */
! 57: inline u_int
! 58: hash_varchar(const char *csStr, int nStrLen, int nVer)
! 59: {
! 60: register u_int n, hash = 0;
! 61: register int i;
! 62:
! 63: assert(csStr);
! 64:
! 65: for (i = 0; i < nStrLen; i++) {
! 66: n = 2 * hash + csStr[i];
! 67: if (!nVer) {
! 68: if (hash & 0x80000000)
! 69: n ^= POLY_CRC32; /* Polynom CRC-32 aviation */
! 70: } else {
! 71: if (n & 1) /* Misho ;) patch for better avalanche!!! */
! 72: n ^= POLY_CRC32; /* Polynom CRC-32 aviation */
! 73: }
! 74: hash = n;
! 75: }
! 76:
! 77: return hash;
! 78: }
! 79:
! 80: /*
! 81: * hash_bernstein() - Compute index hash by Bernstein
! 82: *
! 83: * @csStr = Input data buffer
! 84: * @nStrLen = Length of data buffer
! 85: * @nVer = Version of algorythm; 0 - Bernstein, 1 - DJBX33A variant
! 86: * return: Hash value
! 87: */
! 88: inline u_int
! 89: hash_bernstein(const char *csStr, int nStrLen, int nVer)
! 90: {
! 91: register u_int hash = INIT_BERNSTEIN;
! 92: register int i;
! 93:
! 94: assert(csStr);
! 95:
! 96: for (i = 0; i < nStrLen; i++)
! 97: if (!nVer)
! 98: hash = ((hash << 5) + hash) + csStr[i];
! 99: else
! 100: hash = hash * 33 + csStr[i]; /* DJBX33A */
! 101:
! 102: return hash;
! 103: }
! 104:
! 105: /*
! 106: * hash_fnv1() - Compute index hash by FNV-1
! 107: *
! 108: * @csStr = Input data buffer
! 109: * @nStrLen = Length of data buffer
! 110: * @nVer = Version of algorythm; 0 - FNV-1, 1 - FNV-1a (best avalanche)
! 111: * return: Hash value
! 112: */
! 113: inline u_int
! 114: hash_fnv1(const char *csStr, int nStrLen, int nVer)
! 115: {
! 116: register u_int hash = INIT_FNV1;
! 117: register int i;
! 118:
! 119: assert(csStr);
! 120:
! 121: for (i = 0; i < nStrLen; i++)
! 122: if (!nVer) { /* FNV-1 */
! 123: hash *= POLY_FNV1;
! 124: hash ^= csStr[i];
! 125: } else { /* FNV-1a */
! 126: hash ^= csStr[i];
! 127: hash *= POLY_FNV1;
! 128: }
! 129:
! 130: return hash;
! 131: }
! 132:
! 133: /*
! 134: * hash_jenkins() - Compute index hash by Jenkins (one-at-a-time)
! 135: *
! 136: * @csStr = Input data buffer
! 137: * @nStrLen = Length of data buffer
! 138: * return: Hash value
! 139: */
! 140: inline u_int
! 141: hash_jenkins(const char *csStr, int nStrLen)
! 142: {
! 143: register u_int hash = 0;
! 144: register int i;
! 145:
! 146: assert(csStr);
! 147:
! 148: for (i = 0; i < nStrLen; i++) {
! 149: hash += csStr[i];
! 150: hash += (hash << 10);
! 151: hash ^= (hash >> 6);
! 152: }
! 153: hash += (hash << 3);
! 154: hash ^= (hash >> 11);
! 155: hash += (hash << 15);
! 156:
! 157: return hash;
! 158: }
! 159:
! 160: /*
! 161: * hash_reddragon() - Compute index hash by Red Dragon
! 162: *
! 163: * @csStr = Input data buffer
! 164: * @nStrLen = Length of data buffer
! 165: * return: Hash value
! 166: */
! 167: inline u_int
! 168: hash_reddragon(const char *csStr, int nStrLen)
! 169: {
! 170: register u_int g, hash;
! 171: register int i;
! 172:
! 173: assert(csStr);
! 174:
! 175: for (hash = 0, i = 0; i < nStrLen; i++) {
! 176: hash = (hash << 4) + csStr[i];
! 177: if ((g = hash & 0xF0000000)) {
! 178: hash ^= g >> 24;
! 179: hash ^= g;
! 180: }
! 181: }
! 182:
! 183: return hash;
! 184: }
! 185:
! 186: /*
! 187: * hash_jenkins32() - Fast Jenkins hash function
! 188: *
! 189: * @buf = Input buffer
! 190: * @len = Length of buffer
! 191: * @prevhash = Previous hash, if participate in continuing hash
! 192: * return: Hash value
! 193: */
! 194: u_int
! 195: hash_jenkins32(const u_int *buf, int len, u_int prevhash)
! 196: {
! 197: register u_int a, b, c;
! 198:
! 199: assert(buf);
! 200:
! 201: a = b = c = INIT_JENKINS32 + (((u_int) len) << 2) + prevhash;
! 202:
! 203: while (len > 3) {
! 204: a += buf[0];
! 205: b += buf[1];
! 206: c += buf[2];
! 207: MIX32(a, b, c);
! 208: len -= 3;
! 209: buf += 3;
! 210: }
! 211:
! 212: switch (len) {
! 213: case 3:
! 214: c += buf[2];
! 215: case 2:
! 216: b += buf[1];
! 217: case 1:
! 218: a += buf[0];
! 219: FINAL32(a, b, c);
! 220: case 0:
! 221: break;
! 222: }
! 223:
! 224: return c;
! 225: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / libelwix / src