Return to hash.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / libelwix / src

version 3.7

    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 2015/06/25 17:53:50 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 - 2015
   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: 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: 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: 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: 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: 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: }