Annotation of libelwix/src/hash.c, revision 1.1.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>