Return to jhash.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / lib

Annotation of embedaddon/quagga/lib/jhash.c, revision 1.1

1.1     ! misho       1: /* jhash.h: Jenkins hash support.
        !             2:  *
        !             3:  * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
        !             4:  *
        !             5:  * http://burtleburtle.net/bob/hash/
        !             6:  *
        !             7:  * These are the credits from Bob's sources:
        !             8:  *
        !             9:  * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
        !            10:  * hash(), hash2(), hash3, and mix() are externally useful functions.
        !            11:  * Routines to test the hash are included if SELF_TEST is defined.
        !            12:  * You can use this free for any purpose.  It has no warranty.
        !            13:  *
        !            14:  * Copyright (C) 2003 David S. Miller (davem@redhat.com)
        !            15:  *
        !            16:  * I've modified Bob's hash to be useful in the Linux kernel, and
        !            17:  * any bugs present are surely my fault.  -DaveM
        !            18:  */
        !            19: 
        !            20: #include "zebra.h"
        !            21: #include "jhash.h"
        !            22: 
        !            23: /* The golden ration: an arbitrary value */
        !            24: #define JHASH_GOLDEN_RATIO  0x9e3779b9
        !            25: 
        !            26: /* NOTE: Arguments are modified. */
        !            27: #define __jhash_mix(a, b, c) \
        !            28: { \
        !            29:   a -= b; a -= c; a ^= (c>>13); \
        !            30:   b -= c; b -= a; b ^= (a<<8); \
        !            31:   c -= a; c -= b; c ^= (b>>13); \
        !            32:   a -= b; a -= c; a ^= (c>>12);  \
        !            33:   b -= c; b -= a; b ^= (a<<16); \
        !            34:   c -= a; c -= b; c ^= (b>>5); \
        !            35:   a -= b; a -= c; a ^= (c>>3);  \
        !            36:   b -= c; b -= a; b ^= (a<<10); \
        !            37:   c -= a; c -= b; c ^= (b>>15); \
        !            38: }
        !            39: 
        !            40: /* The most generic version, hashes an arbitrary sequence
        !            41:  * of bytes.  No alignment or length assumptions are made about
        !            42:  * the input key.
        !            43:  */
        !            44: u_int32_t
        !            45: jhash (void *key, u_int32_t length, u_int32_t initval)
        !            46: {
        !            47:   u_int32_t a, b, c, len;
        !            48:   u_int8_t *k = key;
        !            49: 
        !            50:   len = length;
        !            51:   a = b = JHASH_GOLDEN_RATIO;
        !            52:   c = initval;
        !            53: 
        !            54:   while (len >= 12)
        !            55:     {
        !            56:       a +=
        !            57:         (k[0] + ((u_int32_t) k[1] << 8) + ((u_int32_t) k[2] << 16) +
        !            58:          ((u_int32_t) k[3] << 24));
        !            59:       b +=
        !            60:         (k[4] + ((u_int32_t) k[5] << 8) + ((u_int32_t) k[6] << 16) +
        !            61:          ((u_int32_t) k[7] << 24));
        !            62:       c +=
        !            63:         (k[8] + ((u_int32_t) k[9] << 8) + ((u_int32_t) k[10] << 16) +
        !            64:          ((u_int32_t) k[11] << 24));
        !            65: 
        !            66:       __jhash_mix (a, b, c);
        !            67: 
        !            68:       k += 12;
        !            69:       len -= 12;
        !            70:     }
        !            71: 
        !            72:   c += length;
        !            73:   switch (len)
        !            74:     {
        !            75:     case 11:
        !            76:       c += ((u_int32_t) k[10] << 24);
        !            77:     case 10:
        !            78:       c += ((u_int32_t) k[9] << 16);
        !            79:     case 9:
        !            80:       c += ((u_int32_t) k[8] << 8);
        !            81:     case 8:
        !            82:       b += ((u_int32_t) k[7] << 24);
        !            83:     case 7:
        !            84:       b += ((u_int32_t) k[6] << 16);
        !            85:     case 6:
        !            86:       b += ((u_int32_t) k[5] << 8);
        !            87:     case 5:
        !            88:       b += k[4];
        !            89:     case 4:
        !            90:       a += ((u_int32_t) k[3] << 24);
        !            91:     case 3:
        !            92:       a += ((u_int32_t) k[2] << 16);
        !            93:     case 2:
        !            94:       a += ((u_int32_t) k[1] << 8);
        !            95:     case 1:
        !            96:       a += k[0];
        !            97:     };
        !            98: 
        !            99:   __jhash_mix (a, b, c);
        !           100: 
        !           101:   return c;
        !           102: }
        !           103: 
        !           104: /* A special optimized version that handles 1 or more of u_int32_ts.
        !           105:  * The length parameter here is the number of u_int32_ts in the key.
        !           106:  */
        !           107: u_int32_t
        !           108: jhash2 (u_int32_t * k, u_int32_t length, u_int32_t initval)
        !           109: {
        !           110:   u_int32_t a, b, c, len;
        !           111: 
        !           112:   a = b = JHASH_GOLDEN_RATIO;
        !           113:   c = initval;
        !           114:   len = length;
        !           115: 
        !           116:   while (len >= 3)
        !           117:     {
        !           118:       a += k[0];
        !           119:       b += k[1];
        !           120:       c += k[2];
        !           121:       __jhash_mix (a, b, c);
        !           122:       k += 3;
        !           123:       len -= 3;
        !           124:     }
        !           125: 
        !           126:   c += length * 4;
        !           127: 
        !           128:   switch (len)
        !           129:     {
        !           130:     case 2:
        !           131:       b += k[1];
        !           132:     case 1:
        !           133:       a += k[0];
        !           134:     };
        !           135: 
        !           136:   __jhash_mix (a, b, c);
        !           137: 
        !           138:   return c;
        !           139: }
        !           140: 
        !           141: 
        !           142: /* A special ultra-optimized versions that knows they are hashing exactly
        !           143:  * 3, 2 or 1 word(s).
        !           144:  *
        !           145:  * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
        !           146:  *       done at the end is not done here.
        !           147:  */
        !           148: u_int32_t
        !           149: jhash_3words (u_int32_t a, u_int32_t b, u_int32_t c, u_int32_t initval)
        !           150: {
        !           151:   a += JHASH_GOLDEN_RATIO;
        !           152:   b += JHASH_GOLDEN_RATIO;
        !           153:   c += initval;
        !           154: 
        !           155:   __jhash_mix (a, b, c);
        !           156: 
        !           157:   return c;
        !           158: }
        !           159: 
        !           160: u_int32_t
        !           161: jhash_2words (u_int32_t a, u_int32_t b, u_int32_t initval)
        !           162: {
        !           163:   return jhash_3words (a, b, 0, initval);
        !           164: }
        !           165: 
        !           166: u_int32_t
        !           167: jhash_1word (u_int32_t a, u_int32_t initval)
        !           168: {
        !           169:   return jhash_3words (a, 0, 0, initval);
        !           170: }