Return to hash.c CVS log

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

Annotation of libaitcrc/src/hash.c, revision 1.1.2.1

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 $
        !             6: * $Id: libaithash.c,v 1.2 2009/10/01 09:26:33 misho Exp $
        !             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: }