Changeset 8575 in project


Ignore:
Timestamp:
02/20/08 03:08:27 (12 years ago)
Author:
Kon Lovett
Message:

Bug fixes for little & big endian not the same for trailing bytes (< sizeof uint32_t). Removed un-needed variables, re-used arguments where possible. Use of "scheme-object" for scheme function passing - I was dumb. Dropped use of "iset". Simplified RK Search.

Location:
release/3/hashes
Files:
58 edited
1 copied

Legend:

Unmodified
Added
Removed
  • release/3/hashes/tags/2.3/APHash.scm

    r8148 r8575  
    3333
    3434static uint32_t
    35 APHash (uint8_t *data, uint32_t len, uint32_t initval)
     35APHash( uint8_t *data, uint32_t length, uint32_t key )
    3636{
    37    uint32_t hash = initval;
    38    uint32_t i    = 0;
     37    if (data) {
     38        int i;
     39        for (i = 0; i < length; data++, i++) {
     40            key ^= ((i & 1) == 0) /* even? */
     41                      ? (  (key <<  7) ^ ((uint32_t) *data) ^ (key >> 3))
     42                      : (~((key << 11) ^ ((uint32_t) *data) ^ (key >> 5)));
     43        }
     44    }
    3945
    40    if (data == NULL) return 0;
    41 
    42    for (i = 0; i < len; data++, i++) {
    43       hash ^= ((i & 1) == 0) ? (  (hash <<  7) ^ (*data) ^ (hash >> 3)) :
    44                                (~((hash << 11) ^ (*data) ^ (hash >> 5)));
    45    }
    46 
    47    return hash;
     46    return key;
    4847}
    4948
  • release/3/hashes/tags/2.3/BKDRHash.scm

    r8148 r8575  
    2626
    2727static uint32_t
    28 BKDRHash (uint8_t *data, uint32_t len, uint32_t initval)
     28BKDRHash( uint8_t *data, uint32_t length, uint32_t key )
    2929{
    30    uint32_t seed = 131; /* 31 131 1313 13131 131313 etc.. */
    31    uint32_t hash = initval;
    32    uint32_t i;
     30    if (data) {
     31        uint32_t seed = 131; /* 31 131 1313 13131 131313 etc.. */
     32        for ( ; length; data++, length--) {
     33            key = (key * seed) + ((uint32_t) *data);
     34        }
     35    }
    3336
    34    if (data == NULL) return 0;
    35 
    36    for (i = 0; i < len; data++, i++) {
    37       hash = (hash * seed) + (*data);
    38    }
    39 
    40    return hash;
     37    return key;
    4138}
    4239
  • release/3/hashes/tags/2.3/BRPHash.scm

    r8148 r8575  
    2121
    2222static uint32_t
    23 BRPHash (uint8_t *data, uint32_t len, uint32_t initval)
     23BRPHash( uint8_t *data, uint32_t length, uint32_t key )
    2424{
    25 #  define SHIFT 6
    26 #  define MASK (((uint32_t) (~0)) << (bitsizeof(uint32_t) - SHIFT))
     25#   define MASK (((uint32_t) (~0)) << (bitsizeof( uint32_t ) - 6))
    2726
    28    uint32_t hash = initval;
    29    uint32_t i;
     27    if (data) {
     28        for ( ; length; data++, length--) {
     29            key = (key & MASK) ^ (key << 6) ^ ((uint32_t) *data);
     30        }
     31    }
    3032
    31    if (data == NULL) return 0;
     33    return key;
    3234
    33    for (i = 0; i < len; data++, i++) {
    34       hash = (hash & MASK) ^ (hash << SHIFT) ^ (*data);
    35    }
    36 
    37    return hash;
    38 
    39 #  undef SHIFT
    40 #  undef MASK
     35#   undef MASK
    4136}
    4237
  • release/3/hashes/tags/2.3/DEKHash.scm

    r8148 r8575  
    2525
    2626static uint32_t
    27 DEKHash (uint8_t *data, uint32_t len, uint32_t initval)
     27DEKHash( uint8_t *data, uint32_t length, uint32_t key )
    2828{
    29    uint32_t hash = initval ? initval : len;
    30    uint32_t i;
     29    if (! key) key = length;
    3130
    32    if (data == NULL) return 0;
     31    if (data) {
     32        for ( ; length; data++, length--) {
     33            key = ((key << 5) ^ (key >> 27)) ^ ((uint32_t) *data);
     34        }
     35    }
    3336
    34    for (i = 0; i < len; data++, i++) {
    35       hash = ((hash << 5) ^ (hash >> 27)) ^ (*data);
    36    }
    37 
    38    return hash;
     37    return key;
    3938}
    4039
  • release/3/hashes/tags/2.3/DJBHash.scm

    r8148 r8575  
    2525
    2626static uint32_t
    27 DJBHash (uint8_t *data, uint32_t len, uint32_t initval)
     27DJBHash( uint8_t *data, uint32_t length, uint32_t key )
    2828{
    29    uint32_t hash = initval ? initval : 5381;
    30    uint32_t i;
     29    if (! key) key = 5381;
    3130
    32    if (data == NULL) return 0;
     31    if (data) {
     32        for ( ; length; data++, length--) {
     33            key = ((key << 5) + key) + ((uint32_t) *data);
     34        }
     35    }
    3336
    34    for (i = 0; i < len; data++, i++) {
    35       hash = ((hash << 5) + hash) + (*data);
    36    }
    37 
    38    return hash;
     37    return key;
    3938}
    4039
  • release/3/hashes/tags/2.3/ELFHash.scm

    r8148 r8575  
    2424
    2525static uint32_t
    26 ELFHash (uint8_t *data, uint32_t len, uint32_t initval)
     26ELFHash( uint8_t *data, uint32_t length, uint32_t key )
    2727{
    28    uint32_t hash = initval;
    29    uint32_t x;
    30    uint32_t i;
     28    if (data) {
     29        for ( ; length; data++, length--) {
     30            uint32_t test;
     31            key = (key << 4) + ((uint32_t) *data);
     32            if ((test = (key & 0xF0000000L))) {
     33                key ^= (test >> 24);
     34                key &= ~test;
     35            }
     36        }
     37    }
    3138
    32    if (data == NULL) return 0;
    33 
    34    for (i = 0; i < len; data++, i++) {
    35       hash = (hash << 4) + (*data);
    36       if ((x = (hash & 0xF0000000L)) != 0) {
    37          hash ^= (x >> 24);
    38          hash &= ~x;
    39       }
    40    }
    41 
    42    return hash;
     39    return key;
    4340}
    4441
  • release/3/hashes/tags/2.3/FNVAHash.scm

    r8148 r8575  
    7272 */
    7373
    74 #define FNV1_32_INIT            ((uint32_t)0x811c9dc5)
    75 #define FNV1_32A_INIT           FNV1_32_INIT
    76 #define FNV_32_PRIME            ((uint32_t)0x01000193)
    77 
    7874/*
    7975        Useful with the gcc compiler with -O3 on many AMD & Intel CPUs.
    8076        Undefine if this is the case.
    8177*/
     78
    8279#define NO_FNV_GCC_OPTIMIZATION
    8380
    8481static uint32_t
    85 FNVAHash (uint8_t *data, uint32_t len, uint32_t initval)
     82FNVAHash( uint8_t *data, uint32_t length, uint32_t key )
    8683{
    87         uint32_t hval = initval ? initval : FNV1_32A_INIT;
    88         uint8_t *bp = data;                     /* start of buffer */
    89         uint8_t *be = bp + len; /* beyond end of buffer */
     84#   define FNV1_32A_INIT  ((uint32_t)0x811c9dc5)
     85#   define FNV_32_PRIME         ((uint32_t)0x01000193)
    9086
    91         if (data == NULL) return 0;
     87    if (! key) key = FNV1_32A_INIT;
    9288
    93         /*
    94          * FNV-1a hash each octet in the buffer
    95          */
    96         while (bp < be) {
     89    if (data) {
     90        uint8_t *be = data + length;    /* beyond end of buffer */
    9791
    98                 /* xor the bottom with the current octet */
    99                 hval ^= (uint32_t)*bp++;
     92        /* FNV-1a hash each octet in the buffer */
     93        while (data < be) {
    10094
    101                 /* multiply by the 32 bit FNV magic prime mod 2^32 */
     95            /* xor the bottom with the current octet */
     96            key ^= (uint32_t) *data++;
     97
     98            /* multiply by the 32 bit FNV magic prime mod 2^32 */
    10299#ifdef NO_FNV_GCC_OPTIMIZATION
    103                 hval *= FNV_32_PRIME;
     100            key *= FNV_32_PRIME;
    104101#else
    105                 hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
     102            key += (key << 1) + (key << 4) + (key << 7) + (key << 8) + (key << 24);
    106103#endif
    107         }
     104        }
     105    }
    108106
    109         /* return our new hash value */
    110         return hval;
     107    /* return our new hash value */
     108    return key;
     109
     110#   undef FNV_32_PRIME
     111#   undef FNV1_32A_INIT
    111112}
    112113
    113114#undef NO_FNV_GCC_OPTIMIZATION
    114 #undef FNV_32_PRIME
    115 #undef FNV1_32A_INIT
    116 #undef FNV1_32_INIT
    117115
    118116#undef bitsizeof
  • release/3/hashes/tags/2.3/FNVHash.scm

    r8148 r8575  
    7272 */
    7373
    74 #define FNV1_32_INIT            ((uint32_t)0x811c9dc5)
    75 #define FNV1_32A_INIT           FNV1_32_INIT
    76 #define FNV_32_PRIME            ((uint32_t)0x01000193)
    77 
    7874/*
    7975        Useful with the gcc compiler with -O3 on many AMD & Intel CPUs.
     
    8379
    8480static uint32_t
    85 FNVHash (uint8_t *data, uint32_t len, uint32_t initval)
     81FNVHash( uint8_t *data, uint32_t length, uint32_t key )
    8682{
    87         uint32_t hval = initval ? initval : FNV1_32_INIT;
    88         uint8_t *bp = data;                     /* start of buffer */
    89         uint8_t *be = bp + len; /* beyond end of buffer */
     83#   define FNV1_32_INIT         ((uint32_t) 0x811c9dc5)
     84#   define FNV_32_PRIME         ((uint32_t) 0x01000193)
    9085
    91         if (data == NULL) return 0;
     86    if (! key) key = FNV1_32_INIT;
    9287
    93         /*
    94          * FNV-1 hash each octet in the buffer
    95          */
    96         while (bp < be) {
     88    if (data) {
     89        uint8_t *be = data + length;    /* beyond end of buffer */
    9790
    98                 /* multiply by the 32 bit FNV magic prime mod 2^32 */
     91        /* FNV-1 hash each octet in the buffer */
     92        while (data < be) {
     93
     94            /* multiply by the 32 bit FNV magic prime mod 2^32 */
    9995#ifdef NO_FNV_GCC_OPTIMIZATION
    100                 hval *= FNV_32_PRIME;
     96            key *= FNV_32_PRIME;
    10197#else
    102                 hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
     98            key += (key << 1) + (key << 4) + (key << 7) + (key << 8) + (key << 24);
    10399#endif
    104100
    105                 /* xor the bottom with the current octet */
    106                 hval ^= ((uint32_t) *bp++);
    107         }
     101            /* xor the bottom with the current octet */
     102            key ^= ((uint32_t) *data++);
     103        }
     104    }
    108105
    109         /* return our new hash value */
    110         return hval;
     106    /* return our new hash value */
     107    return key;
     108
     109#   undef FNV_32_PRIME
     110#   undef FNV1_32_INIT
    111111}
    112112
    113113#undef NO_FNV_GCC_OPTIMIZATION
    114 #undef FNV_32_PRIME
    115 #undef FNV1_32A_INIT
    116 #undef FNV1_32_INIT
    117114
    118115#undef bitsizeof
  • release/3/hashes/tags/2.3/ISPLHash.scm

    r8148 r8575  
    5959
    6060static uint32_t
    61 ISPLHash (uint8_t *data, uint32_t len, uint32_t initval)
     61ISPLHash( uint8_t *data, uint32_t length, uint32_t key )
    6262{
    63 #  define SHIFT 5
    64 #  define BITS bitsizeof(uint32_t)
     63    if (data) {
     64        uint32_t i;
    6565
    66    uint32_t hash = initval;
    67    uint32_t i;
    68    uint32_t lim = sizeof(uint32_t) < len ? len : sizeof(uint32_t);
     66        uint32_t lim = sizeof( uint32_t ) < length ? length : sizeof( uint32_t );
     67        for (i = 0; i < lim; data++, i++) {
     68            key = (key << 8) | ((uint32_t) *data);
     69        }
    6970
    70    if (data == NULL) return 0;
    71  
    72    for (i = 0; i < lim; data++, i++) {
    73       hash = (hash << 8) | (*data);
    74    }
     71        for (; i < length; data++, i++) {
     72            key = ((key << 5) | ((key >> (bitsizeof( uint32_t ) - 5)) & ((1 << 5) - 1)))
     73                      ^ ((uint32_t) *data);
     74        }
     75    }
    7576
    76    for (; i < len; data++, i++) {
    77       hash = (hash << SHIFT) | ((hash >> (BITS - SHIFT)) & ((1 << SHIFT) - 1));
    78       hash ^= (*data);
    79    }
    80 
    81    return hash;
    82 
    83 #  undef BITS
    84 #  undef SHIFT
     77    return key;
    8578}
    8679
  • release/3/hashes/tags/2.3/JSHash.scm

    r8148 r8575  
    2121
    2222static uint32_t
    23 JSHash (uint8_t *data, uint32_t len, uint32_t initval)
     23JSHash( uint8_t *data, uint32_t length, uint32_t key )
    2424{
    25    uint32_t hash = initval ? initval : 1315423911;
    26    uint32_t i;
     25    if (! key) key = 1315423911;
    2726
    28    if (data == NULL) return 0;
     27    if (data) {
     28        for ( ; length; data++, length--) {
     29            key ^= (key << 5) + ((uint32_t) *data) + (key >> 2);
     30        }
     31    }
    2932
    30    for (i = 0; i < len; data++, i++) {
    31       hash ^= ((hash << 5) + (*data) + (hash >> 2));
    32    }
    33 
    34    return hash;
     33    return key;
    3534}
    3635
  • release/3/hashes/tags/2.3/NDJBHash.scm

    r8148 r8575  
    2525
    2626static uint32_t
    27 NDJBHash (uint8_t *data, uint32_t len, uint32_t initval)
     27NDJBHash( uint8_t *data, uint32_t length, uint32_t key )
    2828{
    29    uint32_t hash = initval ? initval : 5381;
    30    uint32_t i;
     29    if (! key) key = 5381;
    3130
    32    if (data == NULL) return 0;
     31    if (data) {
     32        for ( ; length; data++, length--) {
     33            key = (key * 33) ^ ((uint32_t) *data);
     34        }
     35    }
    3336
    34    for (i = 0; i < len; data++, i++) {
    35       hash = hash * 33 ^ (*data);
    36    }
    37 
    38    return hash;
     37    return key;
    3938}
    4039
  • release/3/hashes/tags/2.3/PHSFHash.scm

    r8148 r8575  
    2121
    2222static uint32_t
    23 PHSFHash (uint8_t *data, uint32_t len, uint32_t initval)
     23PHSFHash( uint8_t *data, uint32_t length, uint32_t key )
    2424{
    25 #   define get16bits(d) (*((uint16_t *)(d)))
     25#   define BITS16_REF( d ) (*((uint16_t *) (d)))
    2626
    27     uint32_t hash = initval ? initval : len;
    28     uint32_t tmp;
    29     uint32_t rem;
     27    if (! key) key = length;
    3028
    31     if (data == NULL) return 0;
     29    if (data) {
     30        uint32_t remlen = length & 3;
    3231
    33     rem = len & 3;
    34     len >>= 2;
     32        length >>= 2;
    3533
    36     /* Main loop */
    37     for (; len > 0; len--) {
    38         hash  += get16bits(data);
    39         tmp    = (get16bits(data + sizeof(uint16_t)) << 11) ^ hash;
    40         hash   = (hash << 16) ^ tmp;
    41         data  += 2 * sizeof(uint16_t);
    42         hash  += hash >> 11;
     34        /* Main loop */
     35        for (; length; length--) {
     36            uint32_t tmp;
     37            key  += BITS16_REF( data );
     38            tmp   = (BITS16_REF( data + sizeof( uint16_t ) ) << 11) ^ key;
     39            key   = (key << sizeof( uint16_t )) ^ tmp;
     40            data += 2 * sizeof( uint16_t );
     41            key  += key >> 11;
     42        }
     43
     44        /* Handle end cases */
     45        switch (remlen) {
     46            case 3: key += BITS16_REF( data );
     47                    key ^= key << 16;
     48                    key ^= data[ sizeof( uint16_t ) ] << 18;
     49                    key += key >> 11;
     50                    break;
     51            case 2: key += BITS16_REF( data );
     52                    key ^= key << 11;
     53                    key += key >> 17;
     54                    break;
     55            case 1: key += *data;
     56                    key ^= key << 10;
     57                    key += key >> 1;
     58        }
     59
     60        /* Force "avalanching" of final 127 bits */
     61        key ^= key << 3;
     62        key += key >> 5;
     63        key ^= key << 2;
     64        key += key >> 15;
     65        key ^= key << 10;
    4366    }
    4467
    45     /* Handle end cases */
    46     switch (rem) {
    47         case 3: hash += get16bits(data);
    48                 hash ^= hash << 16;
    49                 hash ^= data[sizeof (uint16_t)] << 18;
    50                 hash += hash >> 11;
    51                 break;
    52         case 2: hash += get16bits(data);
    53                 hash ^= hash << 11;
    54                 hash += hash >> 17;
    55                 break;
    56         case 1: hash += *data;
    57                 hash ^= hash << 10;
    58                 hash += hash >> 1;
    59     }
     68    return key;
    6069
    61     /* Force "avalanching" of final 127 bits */
    62     hash ^= hash << 3;
    63     hash += hash >> 5;
    64     hash ^= hash << 2;
    65     hash += hash >> 15;
    66     hash ^= hash << 10;
    67 
    68     return hash;
    69 
    70 #   undef get16bits
     70#   undef BITS16_REF
    7171}
    7272
  • release/3/hashes/tags/2.3/PJWHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 /* This hash algorithm is based on work by Peter J. Weinberger of AT&T
    21 Bell Labs. */
     20/* This hash algorithm is based on work by Peter J. Weinberger of AT&T Bell Labs. */
    2221
    23 #if 0
    2422static uint32_t
    25 PJWHash (uint8_t *data, uint32_t len, uint32_t initval)
     23PJWHash( uint8_t *data, uint32_t length, uint32_t key )
    2624{
    27    uint32_t hash = initval;
    28    uint32_t test;
    29    uint32_t i;
     25    if (data) {
     26        for ( ; length; data++, length--) {
     27            uint32_t test;
     28            key = (key << 2) + ((uint32_t) *data);
     29            if ((test = (key & 0xC000))) {
     30                key = ((key ^ (test >> 12)) & 0x3FFF);
     31            }
     32        }
     33    }
    3034
    31    if (data == NULL) return 0;
    32 
    33    for (i = 0; i < len; data++, i++) {
    34       hash = (hash << 2) + (*data);
    35       if ((test = (hash & 0xC000)) != 0) {
    36          hash = ((hash ^ (test >> 12)) & 0x3FFF);
    37       }
    38    }
    39 
    40    return hash;
     35    return key;
    4136}
    42 #else
    43 static uint32_t
    44 PJWHash (uint8_t *data, uint32_t len, uint32_t initval)
    45 {
    46 #  define BitsInUnsignedInt ((uint32_t) bitsizeof (uint32_t))
    47 #  define ThreeQuarters     ((uint32_t) ((BitsInUnsignedInt * 3) / 4))
    48 #  define OneEighth         ((uint32_t) (BitsInUnsignedInt / 8))
    49 #  define HighBits          (((uint32_t) (~0)) << (BitsInUnsignedInt - OneEighth))
    50 
    51    uint32_t hash = initval;
    52    uint32_t test;
    53    uint32_t i;
    54 
    55    if (data == NULL) return 0;
    56 
    57    for (i = 0; i < len; data++, i++) {
    58       hash = (hash << OneEighth) + (*data);
    59       if ((test = (hash & HighBits)) != 0) {
    60          hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
    61       }
    62    }
    63 
    64    return hash;
    65 
    66 #  undef HighBits
    67 #  undef OneEighth
    68 #  undef ThreeQuarters
    69 #  undef BitsInUnsignedInt
    70 }
    71 #endif
    7237
    7338#undef bitsizeof
  • release/3/hashes/tags/2.3/PYHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 /* Python */
     20/* Python Hash */
    2121
    2222static uint32_t
    23 PYHash (uint8_t *data, uint32_t len, uint32_t initval)
     23PYHash( uint8_t *data, uint32_t length, uint32_t key )
    2424{
    25    uint32_t hash;
    26    uint32_t i;
     25    if (! key) key = ((uint32_t) *data) << 7;
    2726
    28    if (data == NULL) return 0;
     27    if (data == NULL) {
     28        int i;
    2929
    30    hash = initval ? initval : (*data) << 7;
     30        for (i = 0; i < length; data++, i++) {
     31            key = (1000003 * key) ^ ((uint32_t) *data);
     32        }
    3133
    32    for (i = 0; i < len; data++, i++) {
    33       hash = (1000003 * hash) ^ (*data);
    34    }
     34        key ^= length;
     35    }
    3536
    36    hash ^= len;
    37 
    38    return (hash == (uint32_t)-1) ? (uint32_t)-2 : hash;
     37    return (((uint32_t) -1) == key) ? ((uint32_t) -2) : key;
    3938}
    4039
  • release/3/hashes/tags/2.3/RJL3Hash.scm

    r8148 r8575  
    1717#>
    1818#include "hashes.h"
    19 
    20 /* Needed due to strange behavior w/ syntax-case - random results! */
    21 #define VALGRIND
    2219
    2320/*
     
    5754*/
    5855
    59 #define hashsize(n) (((uint32_t) 1) << (n))
    60 #define hashmask(n) (hashsize(n) - 1)
    61 #define rot(x, k)   (((x) << (k)) ^ ((x) >> (32 - (k))))
    62 
    63 /*
    64 -------------------------------------------------------------------------------
    65 mix -- mix 3 32-bit values reversibly.
    66 
    67 This is reversible, so any information in (a,b,c) before mix() is
    68 still in (a,b,c) after mix().
    69 
    70 If four pairs of (a,b,c) inputs are run through mix(), or through
    71 mix() in reverse, there are at least 32 bits of the output that
    72 are sometimes the same for one pair and different for another pair.
    73 This was tested for:
    74 * pairs that differed by one bit, by two bits, in any combination
    75   of top bits of (a,b,c), or in any combination of bottom bits of
    76   (a,b,c).
    77 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
    78   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
    79   is commonly produced by subtraction) look like a single 1-bit
    80   difference.
    81 * the base values were pseudorandom, all zero but one bit set, or
    82   all zero plus a counter that starts at zero.
    83 
    84 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
    85 satisfy this are
    86     4  6  8 16 19  4
    87     9 15  3 18 27 15
    88    14  9  3  7 17  3
    89 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
    90 for "differ" defined as + with a one-bit base and a two-bit delta.  I
    91 used http://burtleburtle.net/bob/hash/avalanche.html to choose
    92 the operations, constants, and arrangements of the variables.
    93 
    94 This does not achieve avalanche.  There are input bits of (a,b,c)
    95 that fail to affect some output bits of (a,b,c), especially of a.  The
    96 most thoroughly mixed value is c, but it doesn't really even achieve
    97 avalanche in c.
    98 
    99 This allows some parallelism.  Read-after-writes are good at doubling
    100 the number of bits affected, so the goal of mixing pulls in the opposite
    101 direction as the goal of parallelism.  I did what I could.  Rotates
    102 seem to cost as much as shifts on every machine I could lay my hands
    103 on, and rotates are much kinder to the top and bottom bits, so I used
    104 rotates.
    105 -------------------------------------------------------------------------------
    106 */
    107 
    108 #define mix(a, b, c) { \
    109   a -= c;  a ^= rot(c, 4);  c += b; \
    110   b -= a;  b ^= rot(a, 6);  a += c; \
    111   c -= b;  c ^= rot(b, 8);  b += a; \
    112   a -= c;  a ^= rot(c,16);  c += b; \
    113   b -= a;  b ^= rot(a,19);  a += c; \
    114   c -= b;  c ^= rot(b, 4);  b += a; \
     56static uint32_t
     57RJL3Hash( uint8_t *data, uint32_t length, uint32_t key )
     58{
     59    /*
     60    -------------------------------------------------------------------------------
     61    mix -- mix 3 32-bit values reversibly.
     62
     63    This is reversible, so any information in (a,b,c) before mix() is
     64    still in (a,b,c) after mix().
     65
     66    If four pairs of (a,b,c) inputs are run through mix(), or through
     67    mix() in reverse, there are at least 32 bits of the output that
     68    are sometimes the same for one pair and different for another pair.
     69    This was tested for:
     70    * pairs that differed by one bit, by two bits, in any combination
     71      of top bits of (a,b,c), or in any combination of bottom bits of
     72      (a,b,c).
     73    * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
     74      the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
     75      is commonly produced by subtraction) look like a single 1-bit
     76      difference.
     77    * the base values were pseudorandom, all zero but one bit set, or
     78      all zero plus a counter that starts at zero.
     79
     80    Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
     81    satisfy this are
     82        4  6  8 16 19  4
     83        9 15  3 18 27 15
     84       14  9  3  7 17  3
     85    Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
     86    for "differ" defined as + with a one-bit base and a two-bit delta.  I
     87    used http://burtleburtle.net/bob/hash/avalanche.html to choose
     88    the operations, constants, and arrangements of the variables.
     89
     90    This does not achieve avalanche.  There are input bits of (a,b,c)
     91    that fail to affect some output bits of (a,b,c), especially of a.  The
     92    most thoroughly mixed value is c, but it doesn't really even achieve
     93    avalanche in c.
     94
     95    This allows some parallelism.  Read-after-writes are good at doubling
     96    the number of bits affected, so the goal of mixing pulls in the opposite
     97    direction as the goal of parallelism.  I did what I could.  Rotates
     98    seem to cost as much as shifts on every machine I could lay my hands
     99    on, and rotates are much kinder to the top and bottom bits, so I used
     100    rotates.
     101    -------------------------------------------------------------------------------
     102    */
     103
     104#   define ROT( x, k ) (((x) << (k)) ^ ((x) >> (32 - (k))))
     105
     106#   define MIX( a, b, c ) { \
     107        (a) -= (c);  (a) ^= ROT( (c),  4 );  (c) += (b); \
     108        (b) -= (a);  (b) ^= ROT( (a),  6 );  (a) += (c); \
     109        (c) -= (b);  (c) ^= ROT( (b),  8 );  (b) += (a); \
     110        (a) -= (c);  (a) ^= ROT( (c), 16 );  (c) += (b); \
     111        (b) -= (a);  (b) ^= ROT( (a), 19 );  (a) += (c); \
     112        (c) -= (b);  (c) ^= ROT( (b),  4 );  (b) += (a); \
     113        }
     114
     115    /*
     116    -------------------------------------------------------------------------------
     117    final -- final mixing of 3 32-bit values (a,b,c) into c
     118
     119    Pairs of (a,b,c) values differing in only a few bits will usually
     120    produce values of c that look totally different.  This was tested for
     121    * pairs that differed by one bit, by two bits, in any combination
     122      of top bits of (a,b,c), or in any combination of bottom bits of
     123      (a,b,c).
     124    * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
     125      the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
     126      is commonly produced by subtraction) look like a single 1-bit
     127      difference.
     128    * the base values were pseudorandom, all zero but one bit set, or
     129      all zero plus a counter that starts at zero.
     130
     131    These constants passed:
     132     14 11 25 16 4 14 24
     133     12 14 25 16 4 14 24
     134    and these came close:
     135      4  8 15 26 3 22 24
     136     10  8 15 26 3 22 24
     137     11  8 15 26 3 22 24
     138    -------------------------------------------------------------------------------
     139    */
     140
     141#   define FINAL( a, b, c ) { \
     142        (c) ^= (b); (c) -= ROT( (b), 14 ); \
     143        (a) ^= (c); (a) -= ROT( (c), 11 ); \
     144        (b) ^= (a); (b) -= ROT( (a), 25 ); \
     145        (c) ^= (b); (c) -= ROT( (b), 16 ); \
     146        (a) ^= (c); (a) -= ROT( (c),  4 );  \
     147        (b) ^= (a); (b) -= ROT( (a), 14 ); \
     148        (c) ^= (b); (c) -= ROT( (b), 24 ); \
     149        }
     150
     151#   define GOLDEN_RATIO 0x9E3779B9
     152
     153    if (data) {
     154        uint32_t a, b;
     155
     156        /* Set up the internal state */
     157        a = b = key = GOLDEN_RATIO + length + key;
     158
     159        const uint32_t *k = ((uint32_t *) data);  /* read 32-bit chunks */
     160        const uint8_t  *k8;
     161
     162        /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
     163        while (length > 12) {
     164              a += k[0];
     165              b += k[1];
     166            key += k[2];
     167            MIX( a, b, key );
     168            length -= 12;
     169            k += 3;
     170        }
     171
     172        /*----------------------------- handle the last (probably partial) block */
     173        k8 = ((const uint8_t *) k);
     174        switch (length) {
     175        case 12: key += k[2];
     176                   b += k[1];
     177                   a += k[0];
     178                 break;
     179        case 11: key += ((uint32_t) k8[10]) << 16;  /* fall through */
     180        case 10: key += ((uint32_t) k8[9]) << 8;    /* fall through */
     181        case 9 : key +=  (uint32_t) k8[8];          /* fall through */
     182        case 8 :   b += k[1];
     183                   a += k[0];
     184                 break;
     185        case 7 :   b += ((uint32_t) k8[6]) << 16;   /* fall through */
     186        case 6 :   b += ((uint32_t) k8[5]) << 8;    /* fall through */
     187        case 5 :   b +=  (uint32_t) k8[4];          /* fall through */
     188        case 4 :   a += k[0];
     189                 break;
     190        case 3 :   a += ((uint32_t) k8[2]) << 16;   /* fall through */
     191        case 2 :   a += ((uint32_t) k8[1]) << 8;    /* fall through */
     192        case 1 :   a +=  (uint32_t) k8[0];
     193                 break;
     194        case 0 : return key;              /* zero length strings require no mixing */
     195        }
     196
     197        FINAL( a, b, key );
     198    }
     199
     200    return key;
     201
     202#   undef ROT
     203#   undef MIX
     204#   undef FINAL
    115205}
    116 
    117 /*
    118 -------------------------------------------------------------------------------
    119 final -- final mixing of 3 32-bit values (a,b,c) into c
    120 
    121 Pairs of (a,b,c) values differing in only a few bits will usually
    122 produce values of c that look totally different.  This was tested for
    123 * pairs that differed by one bit, by two bits, in any combination
    124   of top bits of (a,b,c), or in any combination of bottom bits of
    125   (a,b,c).
    126 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
    127   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
    128   is commonly produced by subtraction) look like a single 1-bit
    129   difference.
    130 * the base values were pseudorandom, all zero but one bit set, or
    131   all zero plus a counter that starts at zero.
    132 
    133 These constants passed:
    134  14 11 25 16 4 14 24
    135  12 14 25 16 4 14 24
    136 and these came close:
    137   4  8 15 26 3 22 24
    138  10  8 15 26 3 22 24
    139  11  8 15 26 3 22 24
    140 -------------------------------------------------------------------------------
    141 */
    142 
    143 #define final(a, b, c) { \
    144   c ^= b; c -= rot(b,14); \
    145   a ^= c; a -= rot(c,11); \
    146   b ^= a; b -= rot(a,25); \
    147   c ^= b; c -= rot(b,16); \
    148   a ^= c; a -= rot(c,4);  \
    149   b ^= a; b -= rot(a,14); \
    150   c ^= b; c -= rot(b,24); \
    151 }
    152 
    153 #ifdef C_BIG_ENDIAN
    154 static uint32_t
    155 RJL3Hash (uint8_t *data, uint32_t length, uint32_t initval)
    156 {
    157   uint32_t a, b, c;
    158   union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
    159 
    160   /* Set up the internal state */
    161   a = b = c = 0xdeadbeef + length + initval;
    162 
    163   u.ptr = data;
    164   if ((u.i & 0x3) == 0) {
    165     const uint32_t *k = ((uint32_t *) data);  /* read 32-bit chunks */
    166     const uint8_t  *k8;
    167 
    168     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
    169     while (length > 12) {
    170       a += k[0];
    171       b += k[1];
    172       c += k[2];
    173       mix(a,b,c);
    174       length -= 12;
    175       k += 3;
    176     }
    177 
    178     /*----------------------------- handle the last (probably partial) block */
    179     /*
    180      * "k[2]<<8" actually reads beyond the end of the string, but
    181      * then shifts out the part it's not allowed to read.  Because the
    182      * string is aligned, the illegal read is in the same word as the
    183      * rest of the string.  Every machine with memory protection I've seen
    184      * does it on word boundaries, so is OK with this.  But VALGRIND will
    185      * still catch it and complain.  The masking trick does make the hash
    186      * noticably faster for short strings (like English words).
    187      */
    188 #ifndef VALGRIND
    189 
    190     switch (length) {
    191     case 12: c += k[2]; b += k[1]; a += k[0]; break;
    192     case 11: c += k[2] << 8; b += k[1]; a += k[0]; break;
    193     case 10: c += k[2] << 16; b += k[1]; a += k[0]; break;
    194     case 9 : c += k[2] << 24; b += k[1]; a += k[0]; break;
    195     case 8 : b += k[1]; a += k[0]; break;
    196     case 7 : b += k[1] << 8; a += k[0]; break;
    197     case 6 : b += k[1] << 16; a += k[0]; break;
    198     case 5 : b += k[1] << 24; a += k[0]; break;
    199     case 4 : a += k[0]; break;
    200     case 3 : a += k[0] << 8; break;
    201     case 2 : a += k[0] << 16; break;
    202     case 1 : a += k[0] << 24; break;
    203     case 0 : return c;              /* zero length strings require no mixing */
    204     }
    205 
    206 #else  /* make valgrind happy */
    207 
    208     k8 = ((const uint8_t *) k);
    209     switch (length) {
    210       /* all the case statements fall through */
    211     case 12: c += k[2]; b += k[1]; a += k[0]; break;
    212     case 11: c += ((uint32_t) k8[10]) << 8;  /* fall through */
    213     case 10: c += ((uint32_t) k8[9]) << 16;  /* fall through */
    214     case 9 : c += ((uint32_t) k8[8]) << 24;  /* fall through */
    215     case 8 : b += k[1]; a += k[0]; break;
    216     case 7 : b += ((uint32_t) k8[6]) << 8;   /* fall through */
    217     case 6 : b += ((uint32_t) k8[5]) << 16;  /* fall through */
    218     case 5 : b += ((uint32_t) k8[4]) << 24;  /* fall through */
    219     case 4 : a += k[0]; break;
    220     case 3 : a += ((uint32_t) k8[2]) << 8;   /* fall through */
    221     case 2 : a += ((uint32_t) k8[1]) << 16;  /* fall through */
    222     case 1 : a += ((uint32_t) k8[0]) << 24; break;
    223     case 0 : return c;
    224     }
    225 
    226 #endif /* !VALGRIND */
    227 
    228   } else {                        /* need to read the key one byte at a time */
    229     const uint8_t *k = data;
    230 
    231     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
    232     while (length > 12) {
    233       a += ((uint32_t) k[0]) << 24;
    234       a += ((uint32_t) k[1]) << 16;
    235       a += ((uint32_t) k[2]) << 8;
    236       a += ((uint32_t) k[3]);
    237       b += ((uint32_t) k[4]) << 24;
    238       b += ((uint32_t) k[5]) << 16;
    239       b += ((uint32_t) k[6]) << 8;
    240       b += ((uint32_t) k[7]);
    241       c += ((uint32_t) k[8]) << 24;
    242       c += ((uint32_t) k[9]) << 16;
    243       c += ((uint32_t) k[10]) << 8;
    244       c += ((uint32_t) k[11]);
    245       mix(a,b,c);
    246       length -= 12;
    247       k += 12;
    248     }
    249 
    250     /*-------------------------------- last block: affect all 32 bits of (c) */
    251     switch (length) {
    252       /* all the case statements fall through */
    253     case 12: c+=k[11];
    254     case 11: c += ((uint32_t) k[10]) << 8;
    255     case 10: c += ((uint32_t) k[9]) << 16;
    256     case 9 : c += ((uint32_t) k[8]) << 24;
    257     case 8 : b += k[7];
    258     case 7 : b += ((uint32_t) k[6]) << 8;
    259     case 6 : b += ((uint32_t) k[5]) << 16;
    260     case 5 : b += ((uint32_t) k[4]) << 24;
    261     case 4 : a += k[3];
    262     case 3 : a += ((uint32_t) k[2]) << 8;
    263     case 2 : a += ((uint32_t) k[1]) << 16;
    264     case 1 : a += ((uint32_t) k[0]) << 24;
    265              break;
    266     case 0 : return c;
    267     }
    268   }
    269 
    270   final(a,b,c);
    271   return c;
    272 }
    273 #else
    274 static uint32_t
    275 RJL3Hash (uint8_t *data, uint32_t length, uint32_t initval)
    276 {
    277   uint32_t a,b,c;                                          /* internal state */
    278   union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
    279 
    280   /* Set up the internal state */
    281   a = b = c = 0xdeadbeef + length + initval;
    282 
    283   u.ptr = data;
    284   if ((u.i & 0x3) == 0) {
    285     const uint32_t *k = ((uint32_t *) data);  /* read 32-bit chunks */
    286     const uint8_t  *k8;
    287 
    288     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
    289     while (length > 12) {
    290       a += k[0];
    291       b += k[1];
    292       c += k[2];
    293       mix(a,b,c);
    294       length -= 12;
    295       k += 3;
    296     }
    297 
    298     /*----------------------------- handle the last (probably partial) block */
    299     /*
    300      * "k[2]&0xffffff" actually reads beyond the end of the string, but
    301      * then masks off the part it's not allowed to read.  Because the
    302      * string is aligned, the masked-off tail is in the same word as the
    303      * rest of the string.  Every machine with memory protection I've seen
    304      * does it on word boundaries, so is OK with this.  But VALGRIND will
    305      * still catch it and complain.  The masking trick does make the hash
    306      * noticably faster for short strings (like English words).
    307      */
    308 #ifndef VALGRIND
    309 
    310     switch (length) {
    311     case 12: c += k[2]; b += k[1]; a += k[0]; break;
    312     case 11: c += k[2] & 0xffffff; b += k[1]; a += k[0]; break;
    313     case 10: c += k[2] & 0xffff; b += k[1]; a += k[0]; break;
    314     case 9 : c += k[2] & 0xff; b += k[1]; a += k[0]; break;
    315     case 8 : b += k[1]; a += k[0]; break;
    316     case 7 : b += k[1] & 0xffffff; a += k[0]; break;
    317     case 6 : b += k[1] & 0xffff; a += k[0]; break;
    318     case 5 : b += k[1] & 0xff; a += k[0]; break;
    319     case 4 : a += k[0]; break;
    320     case 3 : a += k[0] & 0xffffff; break;
    321     case 2 : a += k[0] & 0xffff; break;
    322     case 1 : a += k[0] & 0xff; break;
    323     case 0 : return c;              /* zero length strings require no mixing */
    324     }
    325 
    326 #else /* make valgrind happy */
    327 
    328     k8 = ((const uint8_t *) k);
    329     switch (length) {
    330     case 12: c += k[2]; b += k[1]; a += k[0]; break;
    331     case 11: c += ((uint32_t) k8[10]) << 16;  /* fall through */
    332     case 10: c += ((uint32_t) k8[9]) << 8;    /* fall through */
    333     case 9 : c += k8[8];                   /* fall through */
    334     case 8 : b += k[1]; a += k[0]; break;
    335     case 7 : b += ((uint32_t) k8[6]) << 16;   /* fall through */
    336     case 6 : b += ((uint32_t) k8[5]) << 8;    /* fall through */
    337     case 5 : b += k8[4];                   /* fall through */
    338     case 4 : a += k[0]; break;
    339     case 3 : a += ((uint32_t) k8[2]) << 16;   /* fall through */
    340     case 2 : a += ((uint32_t) k8[1]) << 8;    /* fall through */
    341     case 1 : a += k8[0]; break;
    342     case 0 : return c;
    343     }
    344 
    345 #endif /* !valgrind */
    346 
    347   } else if ((u.i & 0x1) == 0) {
    348     const uint16_t *k = ((uint16_t *) data);  /* read 16-bit chunks */
    349     const uint8_t  *k8;
    350 
    351     /*--------------- all but last block: aligned reads and different mixing */
    352     while (length > 12) {
    353       a += k[0] + (((uint32_t) k[1]) << 16);
    354       b += k[2] + (((uint32_t) k[3]) << 16);
    355       c += k[4] + (((uint32_t) k[5]) << 16);
    356       mix(a,b,c);
    357       length -= 12;
    358       k += 6;
    359     }
    360 
    361     /*----------------------------- handle the last (probably partial) block */
    362     k8 = ((const uint8_t *) k);
    363     switch (length) {
    364     case 12: c += k[4]+(((uint32_t) k[5]) << 16);
    365              b += k[2]+(((uint32_t) k[3]) << 16);
    366              a += k[0]+(((uint32_t) k[1]) << 16);
    367              break;
    368     case 11: c += ((uint32_t) k8[10]) << 16;     /* fall through */
    369     case 10: c += k[4];
    370              b += k[2]+(((uint32_t) k[3]) << 16);
    371              a += k[0]+(((uint32_t) k[1]) << 16);
    372              break;
    373     case 9 : c += k8[8];                      /* fall through */
    374     case 8 : b += k[2]+(((uint32_t) k[3]) << 16);
    375              a += k[0]+(((uint32_t) k[1]) << 16);
    376              break;
    377     case 7 : b += ((uint32_t) k8[6]) << 16;      /* fall through */
    378     case 6 : b += k[2];
    379              a += k[0]+(((uint32_t) k[1]) << 16);
    380              break;
    381     case 5 : b += k8[4];                      /* fall through */
    382     case 4 : a += k[0]+(((uint32_t) k[1]) << 16);
    383              break;
    384     case 3 : a += ((uint32_t) k8[2]) << 16;      /* fall through */
    385     case 2 : a += k[0];
    386              break;
    387     case 1 : a += k8[0];
    388              break;
    389     case 0 : return c;                     /* zero length requires no mixing */
    390     }
    391 
    392   } else {                        /* need to read the key one byte at a time */
    393     const uint8_t *k = data;
    394 
    395     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
    396     while (length > 12) {
    397       a += k[0];
    398       a += ((uint32_t) k[1]) << 8;
    399       a += ((uint32_t) k[2]) << 16;
    400       a += ((uint32_t) k[3]) << 24;
    401       b += k[4];
    402       b += ((uint32_t) k[5]) << 8;
    403       b += ((uint32_t) k[6]) << 16;
    404       b += ((uint32_t) k[7]) << 24;
    405       c += k[8];
    406       c += ((uint32_t) k[9]) << 8;
    407       c += ((uint32_t) k[10]) << 16;
    408       c += ((uint32_t) k[11]) << 24;
    409       mix(a,b,c);
    410       length -= 12;
    411       k += 12;
    412     }
    413 
    414     /*-------------------------------- last block: affect all 32 bits of (c) */
    415     switch (length) {
    416       /* all the case statements fall through */
    417     case 12: c += ((uint32_t) k[11]) << 24;
    418     case 11: c += ((uint32_t) k[10]) << 16;
    419     case 10: c += ((uint32_t) k[9]) << 8;
    420     case 9 : c += k[8];
    421     case 8 : b += ((uint32_t) k[7]) << 24;
    422     case 7 : b += ((uint32_t) k[6]) << 16;
    423     case 6 : b += ((uint32_t) k[5]) << 8;
    424     case 5 : b += k[4];
    425     case 4 : a += ((uint32_t) k[3]) << 24;
    426     case 3 : a += ((uint32_t) k[2]) << 16;
    427     case 2 : a += ((uint32_t) k[1]) << 8;
    428     case 1 : a += k[0];
    429              break;
    430     case 0 : return c;
    431     }
    432   }
    433 
    434   final(a,b,c);
    435   return c;
    436 }
    437 #endif
    438 
    439 #undef hashsize
    440 #undef hashmask
    441 #undef rot
    442 #undef mix
    443 #undef final
    444206
    445207#undef bitsizeof
  • release/3/hashes/tags/2.3/RJMXHash.scm

    r8148 r8575  
    2424--------------------------------------------------------------------
    2525*/
    26 
    27 /*
    28 --------------------------------------------------------------------
    29 mix -- mix 3 32-bit values reversibly.
    30 For every delta with one or two bit set, and the deltas of all three
    31   high bits or all three low bits, whether the original value of a,b,c
    32   is almost all zero or is uniformly distributed,
    33 * If mix() is run forward or backward, at least 32 bits in a,b,c
    34   have at least 1/4 probability of changing.
    35 * If mix() is run forward, every bit of c will change between 1/3 and
    36   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
    37 mix() was built out of 36 single-cycle latency instructions in a
    38   structure that could supported 2x parallelism, like so:
    39       a -= b;
    40       a -= c; x = (c>>13);
    41       b -= c; a ^= x;
    42       b -= a; x = (a<<8);
    43       c -= a; b ^= x;
    44       c -= b; x = (b>>13);
    45       ...
    46   Unfortunately, superscalar Pentiums and Sparcs can't take advantage
    47   of that parallelism. They've also turned some of those single-cycle
    48   latency instructions into multi-cycle latency instructions.  Still,
    49   this is the fastest good hash I could find. There were about 2^^68
    50   to choose from. I only looked at a billion or so.
    51 --------------------------------------------------------------------
    52 */
    53 
    54 #define mix(a, b, c) { \
    55   a -= b; a -= c; a ^= (c >> 13); \
    56   b -= c; b -= a; b ^= (a << 8); \
    57   c -= a; c -= b; c ^= (b >> 13); \
    58   a -= b; a -= c; a ^= (c >> 12);  \
    59   b -= c; b -= a; b ^= (a << 16); \
    60   c -= a; c -= b; c ^= (b >> 5); \
    61   a -= b; a -= c; a ^= (c >> 3);  \
    62   b -= c; b -= a; b ^= (a << 10); \
    63   c -= a; c -= b; c ^= (b >> 15); \
    64 }
    6526
    6627/*
     
    9253*/
    9354
    94 #ifdef C_BIG_ENDIAN
    9555static uint32_t
    96 RJMXHash (uint8_t *data, uint32_t length, uint32_t initval)
     56RJMXHash( uint8_t *data, uint32_t length, uint32_t key )
    9757{
    98    /* Set up the internal state */
    99    uint32_t len = length;
    100    uint8_t *k = data;
    101    uint32_t a = 0x9e3779b9;   /* the golden ratio; an arbitrary value */
    102    uint32_t b = 0x9e3779b9;   /* the golden ratio; an arbitrary value */
    103    uint32_t c = initval;      /* the previous hash value */
     58    /*
     59    --------------------------------------------------------------------
     60    mix -- mix 3 32-bit values reversibly.
     61    For every delta with one or two bit set, and the deltas of all three
     62      high bits or all three low bits, whether the original value of a,b,c
     63      is almost all zero or is uniformly distributed,
     64    * If mix() is run forward or backward, at least 32 bits in a,b,c
     65      have at least 1/4 probability of changing.
     66    * If mix() is run forward, every bit of c will change between 1/3 and
     67      2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
     68    mix() was built out of 36 single-cycle latency instructions in a
     69      structure that could supported 2x parallelism, like so:
     70          a -= b;
     71          a -= c; x = (c>>13);
     72          b -= c; a ^= x;
     73          b -= a; x = (a<<8);
     74          c -= a; b ^= x;
     75          c -= b; x = (b>>13);
     76          ...
     77      Unfortunately, superscalar Pentiums and Sparcs can't take advantage
     78      of that parallelism. They've also turned some of those single-cycle
     79      latency instructions into multi-cycle latency instructions.  Still,
     80      this is the fastest good hash I could find. There were about 2^^68
     81      to choose from. I only looked at a billion or so.
     82    --------------------------------------------------------------------
     83    */
    10484
    105   if (data == NULL) return 0;
     85#   define MIX( a, b, c ) { \
     86        (a) -= (b); (a) -= (c); (a) ^= ((c) >> 13); \
     87        (b) -= (c); (b) -= (a); (b) ^= ((a) << 8); \
     88        (c) -= (a); (c) -= (b); (c) ^= ((b) >> 13); \
     89        (a) -= (b); (a) -= (c); (a) ^= ((c) >> 12); \
     90        (b) -= (c); (b) -= (a); (b) ^= ((a) << 16); \
     91        (c) -= (a); (c) -= (b); (c) ^= ((b) >> 5); \
     92        (a) -= (b); (a) -= (c); (a) ^= ((c) >> 3); \
     93        (b) -= (c); (b) -= (a); (b) ^= ((a) << 10); \
     94        (c) -= (a); (c) -= (b); (c) ^= ((b) >> 15); \
     95        }
    10696
    107    /*---------------------------------------- handle most of the key */
    108    while (len >= 12) {
    109       a += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    110       b += (k[4] + (((uint32_t) k[5]) << 8) + (((uint32_t) k[6]) << 16) + (((uint32_t) k[7]) << 24));
    111       c += (k[8] + (((uint32_t) k[9]) << 8) + (((uint32_t) k[10]) << 16) + (((uint32_t) k[11]) << 24));
    112       mix (a, b, c);
    113       k += 12;
    114       len -= 12;
    115    }
     97#   define GOLDEN_RATIO 0x9E3779B9
    11698
    117    /*------------------------------------- handle the last 11 bytes */
    118    c += length;
    119    switch (len) {
    120      /* all the case statements fall through */
    121    case 11: c += (((uint32_t) k[10]) << 24);
    122    case 10: c += (((uint32_t) k[9]) << 16);
    123    case 9 : c += (((uint32_t) k[8]) << 8);
    124       /* the first byte of c is reserved for the length */
    125    case 8 : b += (((uint32_t) k[7]) << 24);
    126    case 7 : b += (((uint32_t) k[6]) << 16);
    127    case 6 : b += (((uint32_t) k[5]) << 8);
    128    case 5 : b += k[4];
    129    case 4 : a += (((uint32_t) k[3]) << 24);
    130    case 3 : a += (((uint32_t) k[2]) << 16);
    131    case 2 : a += (((uint32_t) k[1]) << 8);
    132    case 1 : a += k[0];
    133      /* case 0: nothing left to add */
    134    }
    135    mix (a, b, c);
     99    if (! key) key = length;
    136100
    137    /*-------------------------------------------- report the result */
    138    return c;
     101    if (data) {
     102        uint32_t a, b;
     103
     104        /* Set up the internal state */
     105        a = b = GOLDEN_RATIO;    /* an arbitrary value */
     106
     107        /*---------------------------------------- handle most of the key */
     108        while (length >= 12) {
     109              a += *((uint32_t *) (data + 0));
     110              b += *((uint32_t *) (data + 4));
     111            key += *((uint32_t *) (data + 8));
     112            MIX( a, b, key );
     113            data += 12;
     114            length -= 12;
     115        }
     116
     117        /*------------------------------------- handle the last 11 bytes */
     118        switch (length) {
     119          /* all the case statements fall through */
     120        case 11: key += ((uint32_t) data[ 10 ]) << 24;
     121        case 10: key += ((uint32_t) data[ 9 ]) << 16;
     122        case 9 : key += ((uint32_t) data[ 8 ]) << 8;
     123          /* the first byte of key is reserved for the length */
     124        case 8 :   b += ((uint32_t) data[ 7 ]) << 24;
     125        case 7 :   b += ((uint32_t) data[ 6 ]) << 16;
     126        case 6 :   b += ((uint32_t) data[ 5 ]) << 8;
     127        case 5 :   b +=  (uint32_t) data[ 4 ];
     128        case 4 :   a += ((uint32_t) data[ 3 ]) << 24;
     129        case 3 :   a += ((uint32_t) data[ 2 ]) << 16;
     130        case 2 :   a += ((uint32_t) data[ 1 ]) << 8;
     131        case 1 :   a +=  (uint32_t) data[ 0 ];
     132          /* case 0: nothing left to add */
     133        }
     134
     135        MIX( a, b, key );
     136    }
     137
     138    /*-------------------------------------------- report the result */
     139    return key;
     140
     141# undef MIX
    139142}
    140 #else
    141 static uint32_t
    142 RJMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    143 {
    144    /* Set up the internal state */
    145    uint32_t len = length;
    146    uint8_t *k = data;
    147    uint32_t a = 0x9e3779b9;   /* the golden ratio; an arbitrary value */
    148    uint32_t b = 0x9e3779b9;   /* the golden ratio; an arbitrary value */
    149    uint32_t c = initval;      /* the previous hash value */
    150 
    151   if (data == NULL) return 0;
    152 
    153    /*---------------------------------------- handle most of the key */
    154    if (((uint32_t) k) & 3) {
    155       while (len >= 12) { /* unaligned */
    156          a += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    157          b += (k[4] + (((uint32_t) k[5]) << 8) + (((uint32_t) k[6]) << 16) + (((uint32_t) k[7]) << 24));
    158          c += (k[8] + (((uint32_t) k[9]) << 8) + (((uint32_t) k[10]) << 16) + (((uint32_t) k[11]) << 24));
    159          mix (a, b, c);
    160          k += 12;
    161          len -= 12;
    162       }
    163    } else {
    164       while (len >= 12) { /* aligned */
    165          a += *((uint32_t *) (k + 0));
    166          b += *((uint32_t *) (k + 4));
    167          c += *((uint32_t *) (k + 8));
    168          mix (a, b, c);
    169          k += 12;
    170          len -= 12;
    171       }
    172    }
    173 
    174    /*------------------------------------- handle the last 11 bytes */
    175    c += length;
    176    switch (len) {
    177      /* all the case statements fall through */
    178    case 11: c+=(((uint32_t) k[10]) << 24);
    179    case 10: c += (((uint32_t) k[9]) << 16);
    180    case 9 : c += (((uint32_t) k[8]) << 8);
    181       /* the first byte of c is reserved for the length */
    182    case 8 : b += (((uint32_t) k[7]) << 24);
    183    case 7 : b += (((uint32_t) k[6]) << 16);
    184    case 6 : b += (((uint32_t) k[5]) << 8);
    185    case 5 : b += k[4];
    186    case 4 : a += (((uint32_t) k[3]) << 24);
    187    case 3 : a += (((uint32_t) k[2]) << 16);
    188    case 2 : a += (((uint32_t) k[1]) << 8);
    189    case 1 : a += k[0];
    190      /* case 0: nothing left to add */
    191    }
    192    mix (a, b, c);
    193 
    194    /*-------------------------------------------- report the result */
    195    return c;
    196 }
    197 #endif
    198 
    199 #undef mix
    200143
    201144#undef bitsizeof
  • release/3/hashes/tags/2.3/RSHash.scm

    r8148 r8575  
    4141
    4242static uint32_t
    43 RSHash (uint8_t *data, uint32_t len, uint32_t initval)
     43RSHash(uint8_t *data, uint32_t length, uint32_t key )
    4444{
    45    uint32_t b    = 378551;
    46    uint32_t a    = 63689;
    47    uint32_t hash = initval;
    48    uint32_t i;
     45#   define A 63689U
     46#   define B 378551U
    4947
    50    if (data == NULL) return 0;
     48    if (data) {
     49        uint32_t a = A;
     50        for ( ; length; data++, length--) {
     51            key = key * a + ((uint32_t) *data);
     52            a *= B;
     53        }
     54    }
    5155
    52    for (i = 0; i < len; data++, i++) {
    53       hash = hash * a + (*data);
    54       a *= b;
    55    }
     56    return key;
    5657
    57    return hash;
     58#   undef B
     59#   undef A
    5860}
    5961
  • release/3/hashes/tags/2.3/SDBMHash.scm

    r8148 r8575  
    2424
    2525static uint32_t
    26 SDBMHash (uint8_t *data, uint32_t len, uint32_t initval)
     26SDBMHash( uint8_t *data, uint32_t length, uint32_t key )
    2727{
    28    uint32_t hash = initval;
    29    uint32_t i;
     28    if (data) {
     29        for ( ; length; data++, length--) {
     30            key = ((uint32_t) *data) + (key << 6) + (key << 16) - key;
     31        }
     32    }
    3033
    31    if (data == NULL) return 0;
    32 
    33    for (i = 0; i < len; data++, i++) {
    34       hash = (*data) + (hash << 6) + (hash << 16) - hash;
    35    }
    36 
    37    return hash;
     34    return key;
    3835}
    3936
  • release/3/hashes/tags/2.3/TWMGMXHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 #define mix(key) { \
    21    key = (key + 0x7ED55D16) + (key << 12); \
    22    key = (key ^ 0xC761C23C) ^ (key >> 19); \
    23    key = (key + 0x165667B1) + (key << 5); \
    24    key = (key + 0xD3A2646C) ^ (key << 9); \
    25    key = (key + 0xFD7046C5) + (key << 3); \
    26    key = (key ^ 0xB55A4F09) ^ (key >> 16); \
     20static uint32_t
     21TWMGMXHash( uint8_t *data, uint32_t length, uint32_t key )
     22{
     23    /* Merge 32 bit Mix Function */
     24#   define MIX( key ) { \
     25        (key) = ((key) + 0x7ED55D16) + ((key) << 12); \
     26        (key) = ((key) ^ 0xC761C23C) ^ ((key) >> 19); \
     27        (key) = ((key) + 0x165667B1) + ((key) << 5); \
     28        (key) = ((key) + 0xD3A2646C) ^ ((key) << 9); \
     29        (key) = ((key) + 0xFD7046C5) + ((key) << 3); \
     30        (key) = ((key) ^ 0xB55A4F09) ^ ((key) >> 16); \
     31        }
     32
     33    if (data) {
     34
     35        while (length >= sizeof( uint32_t )) {
     36            key += *((uint32_t *) data);
     37            MIX( key );
     38            data += sizeof( uint32_t );
     39            length -= sizeof( uint32_t );
     40        }
     41
     42        switch (length) {
     43          /* all the case statements fall through */
     44        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     45        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     46        case 1 : key += (uint32_t) data[ 0 ];
     47          /* case 0: nothing left to add */
     48        }
     49        MIX( key );
     50    }
     51
     52    return key;
     53
     54#   undef MIX
    2755}
    28 
    29 #ifdef C_BIG_ENDIAN
    30 static uint32_t
    31 TWMGMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    32 {
    33    uint8_t *k = data;
    34    uint32_t len = length;
    35    uint32_t key = initval;
    36 
    37   if (data == NULL) return 0;
    38 
    39    while (len >= 4) {
    40       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    41       mix (key);
    42       k += 4;
    43       len -= 4;
    44    }
    45 
    46    switch (len) {
    47      /* all the case statements fall through */
    48    case 3 : key += (((uint32_t) k[2]) << 16);
    49    case 2 : key += (((uint32_t) k[1]) << 8);
    50    case 1 : key += k[0];
    51      /* case 0: nothing left to add */
    52    }
    53    mix (key);
    54 
    55    return key;
    56 }
    57 #else
    58 static uint32_t
    59 TWMGMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    60 {
    61    uint8_t *k = data;
    62    uint32_t len = length;
    63    uint32_t key = initval;
    64 
    65   if (data == NULL) return 0;
    66 
    67    if (((uint32_t) k) & 3) {
    68       while (len >= 4) {  /* unaligned */
    69         key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    70         mix (key);
    71         k += 4;
    72         len -= 4;
    73       }
    74    } else {
    75       while (len >= 4) {  /* aligned */
    76         key += *((uint32_t *) (k + 0));
    77         mix (key);
    78         k += 4;
    79         len -= 4;
    80       }
    81    }
    82 
    83    switch (len) {
    84      /* all the case statements fall through */
    85    case 3 : key += (((uint32_t) k[2]) << 16);
    86    case 2 : key += (((uint32_t) k[1]) << 8);
    87    case 1 : key += k[0];
    88      /* case 0: nothing left to add */
    89    }
    90    mix (key);
    91 
    92    return key;
    93 }
    94 #endif
    95 
    96 #undef mix
    9756
    9857#undef bitsizeof
  • release/3/hashes/tags/2.3/TWMXHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 /* Thomas Wang's 32 bit Mix Function */
     20static uint32_t
     21TWMXHash( uint8_t *data, uint32_t length, uint32_t key )
     22{
     23    /* Thomas Wang's 32 bit Mix Function */
     24# ifdef C_SIXTY_FOUR
     25#   define MIX( key ) { \
     26        (key) = ~(key) + ((key) << 21); \
     27        (key) ^= (key) >> 24; \
     28        (key) += ((key) << 3) + ((key) << 8); \
     29        (key) ^= (key) >> 14; \
     30        (key) += ((key) << 2) + ((key) << 4); \
     31        (key) ^= (key) >> 28; \
     32        (key) += (key) << 31; \
     33        }
     34# else
     35#   define MIX( key ) { \
     36        (key) += ~((key) << 15); \
     37        (key) ^= ((key) & 0x7FFFFFFF) >> 10; \
     38        (key) += (key) << 3; \
     39        (key) ^= ((key) & 0x7FFFFFFF) >> 6; \
     40        (key) += ~((key) << 11); \
     41        (key) ^= ((key) & 0x7FFFFFFF) >> 16; \
     42        }
     43# endif
    2144
    22 #define mix(key) { \
    23   key += ~(key << 15); \
    24   key ^= ((key & 0x7FFFFFFF) >> 10); \
    25   key += (key << 3); \
    26   key ^= ((key & 0x7FFFFFFF) >> 6); \
    27   key += ~(key << 11); \
    28   key ^= ((key & 0x7FFFFFFF) >> 16); \
     45    if (data) {
     46
     47# ifdef C_SIXTY_FOUR
     48        uint64_t hash = key;
     49        while (length >= sizeof( uint64_t )) {
     50            hash += *((uint64_t *) data);
     51            MIX( hash );
     52            data += sizeof( uint64_t );
     53            length -= sizeof( uint64_t );
     54        }
     55
     56        switch (length) {
     57          /* all the case statements fall through */
     58        case 7 : hash += (((uint64_t) data[ 6 ]) << 48);
     59        case 6 : hash += (((uint64_t) data[ 5 ]) << 40);
     60        case 5 : hash += (((uint64_t) data[ 4 ]) << 32);
     61        case 4 : hash += (((uint64_t) data[ 3 ]) << 24);
     62        case 3 : hash += (((uint64_t) data[ 2 ]) << 16);
     63        case 2 : hash += (((uint64_t) data[ 1 ]) << 8);
     64        case 1 : hash += (uint64_t) data[ 0 ];
     65          /* case 0: nothing left to add */
     66        }
     67        MIX( hash );
     68        key = (uint32_t) hash;
     69# else
     70        while (length >= sizeof( uint32_t )) {
     71            key += *((uint32_t *) data);
     72            MIX( key );
     73            data += sizeof( uint32_t );
     74            length -= sizeof( uint32_t );
     75        }
     76
     77        switch (length) {
     78          /* all the case statements fall through */
     79        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     80        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     81        case 1 : key += (uint32_t) data[ 0 ];
     82          /* case 0: nothing left to add */
     83        }
     84        MIX( key );
     85# endif
     86    }
     87
     88    return key;
     89
     90#   undef MIX
    2991}
    30 
    31 #if 0
    32 #ifdef C_SIXTY_FOUR
    33 #define mix64shift(key) { \
    34   key = (~key) + (key << 21); \
    35   key = key ^ (key >> 24); \
    36   key = (key + (key << 3)) + (key << 8); \
    37   key = key ^ (key >> 14); \
    38   key = (key + (key << 2)) + (key << 4); \
    39   key = key ^ (key >> 28); \
    40   key = key + (key << 31); \
    41 }
    42 
    43 #define mix6432shift(key) { \
    44   key = (~key) + (key << 18); \
    45   key = key ^ (key >> 31); \
    46   key = key * 21; \
    47   key = key ^ (key >> 11); \
    48   key = key + (key << 6); \
    49   key = key ^ (key >> 22); \
    50 }
    51 #endif
    52 #endif
    53 
    54 #ifdef C_BIG_ENDIAN
    55 static uint32_t
    56 TWMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    57 {
    58    uint8_t *k = data;
    59    uint32_t len = length;
    60    uint32_t key = initval;
    61 
    62   if (data == NULL) return 0;
    63 
    64    while (len >= 4) {
    65       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    66       mix (key);
    67       k += 4;
    68       len -= 4;
    69    }
    70 
    71    switch (len) {
    72      /* all the case statements fall through */
    73    case 3 : key += (((uint32_t) k[2]) << 16);
    74    case 2 : key += (((uint32_t) k[1]) << 8);
    75    case 1 : key += k[0];
    76      /* case 0: nothing left to add */
    77    }
    78    mix (key);
    79 
    80    return key;
    81 }
    82 #else
    83 static uint32_t
    84 TWMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    85 {
    86    uint8_t *k = data;
    87    uint32_t len = length;
    88    uint32_t key = initval;
    89 
    90   if (data == NULL) return 0;
    91 
    92    if (((uint32_t) k) & 3) {
    93       while (len >= 4) {  /* unaligned */
    94         key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    95         mix (key);
    96         k += 4;
    97         len -= 4;
    98       }
    99    } else {
    100       while (len >= 4) {  /* aligned */
    101         key += *((uint32_t *) (k + 0));
    102         mix (key);
    103         k += 4;
    104         len -= 4;
    105       }
    106    }
    107 
    108    switch (len) {
    109      /* all the case statements fall through */
    110    case 3 : key += (((uint32_t) k[2]) << 16);
    111    case 2 : key += (((uint32_t) k[1]) << 8);
    112    case 1 : key += k[0];
    113      /* case 0: nothing left to add */
    114    }
    115    mix (key);
    116 
    117    return key;
    118 }
    119 #endif
    120 
    121 #undef mix
    122 
    123 #if 0
    124 #ifdef C_SIXTY_FOUR
    125 # undef mix64shift
    126 # undef mix6432shift
    127 #endif
    128 #endif
    12992
    13093#undef bitsizeof
  • release/3/hashes/tags/2.3/TWSHMLMXHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 #define mix(key) { \
    21   key = (key ^ 61) ^ (key >> 16); \
    22   key = key + (key << 3); \
    23   key = key ^ (key >> 4); \
    24   key = key * 0x27D4EB2D; \
    25   key = key ^ (key >> 15); \
     20static uint32_t
     21TWSHMLMXHash( uint8_t *data, uint32_t length, uint32_t key )
     22{
     23    /* Shift-Multiply 32 bit Mix Function */
     24#   define MIX( key ) { \
     25        (key) = ((key) ^ 61) ^ ((key) >> 16); \
     26        (key) = (key) + ((key) << 3); \
     27        (key) = (key) ^ ((key) >> 4); \
     28        (key) = (key) * 0x27D4EB2D; \
     29        (key) = (key) ^ ((key) >> 15); \
     30        }
     31
     32    if (data) {
     33
     34        while (length >= sizeof( uint32_t )) {
     35            key += *((uint32_t *) data);
     36            MIX( key );
     37            data += sizeof( uint32_t );
     38            length -= sizeof( uint32_t );
     39        }
     40
     41        switch (length) {
     42          /* all the case statements fall through */
     43        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     44        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     45        case 1 : key += (uint32_t) data[ 0 ];
     46          /* case 0: nothing left to add */
     47        }
     48        MIX( key );
     49    }
     50
     51    return key;
     52
     53#   undef MIX
    2654}
    27 
    28 #ifdef C_BIG_ENDIAN
    29 static uint32_t
    30 TWSHMLMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    31 {
    32    uint8_t *k = data;
    33    uint32_t len = length;
    34    uint32_t key = initval;
    35 
    36   if (data == NULL) return 0;
    37 
    38    while (len >= 4) {
    39       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    40       mix (key);
    41       k += 4;
    42       len -= 4;
    43    }
    44 
    45    switch (len) {
    46      /* all the case statements fall through */
    47    case 3 : key += (((uint32_t) k[2]) << 16);
    48    case 2 : key += (((uint32_t) k[1]) << 8);
    49    case 1 : key += k[0];
    50      /* case 0: nothing left to add */
    51    }
    52    mix (key);
    53 
    54    return key;
    55 }
    56 #else
    57 static uint32_t
    58 TWSHMLMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    59 {
    60    uint8_t *k = data;
    61    uint32_t len = length;
    62    uint32_t key = initval;
    63 
    64   if (data == NULL) return 0;
    65 
    66    if (((uint32_t) k) & 3) {
    67       while (len >= 4) {  /* unaligned */
    68         key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    69         mix (key);
    70         k += 4;
    71         len -= 4;
    72       }
    73    } else {
    74       while (len >= 4) {  /* aligned */
    75         key += *((uint32_t *) (k + 0));
    76         mix (key);
    77         k += 4;
    78         len -= 4;
    79       }
    80    }
    81 
    82    switch (len) {
    83      /* all the case statements fall through */
    84    case 3 : key += (((uint32_t) k[2]) << 16);
    85    case 2 : key += (((uint32_t) k[1]) << 8);
    86    case 1 : key += k[0];
    87      /* case 0: nothing left to add */
    88    }
    89    mix (key);
    90 
    91    return key;
    92 }
    93 #endif
    94 
    95 #undef mix
    9655
    9756#undef bitsizeof
  • release/3/hashes/tags/2.3/TWSHMXHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 #define mix(key) { \
    21   key = ~key + (key << 15); \
    22   key = key ^ (key >> 12); \
    23   key = key + (key << 2); \
    24   key = key ^ (key >> 4); \
    25   key = key * 2057; \
    26   key = key ^ (key >> 16); \
     20static uint32_t
     21TWSHMXHash( uint8_t *data, uint32_t length, uint32_t key )
     22{
     23    /* Shift 32 bit Mix Function */
     24#   define MIX( key ) { \
     25        (key) = ~(key) + ((key) << 15); \
     26        (key) = (key) ^ ((key) >> 12); \
     27        (key) = (key) + ((key) << 2); \
     28        (key) = (key) ^ ((key) >> 4); \
     29        (key) = (key) * 2057; \
     30        (key) = (key) ^ ((key) >> 16); \
     31      }
     32
     33    if (data) {
     34
     35        while (length >= sizeof( uint32_t )) {
     36            key += *((uint32_t *) data);
     37            MIX( key );
     38            data += sizeof( uint32_t );
     39            length -= sizeof( uint32_t );
     40        }
     41
     42        switch (length) {
     43          /* all the case statements fall through */
     44        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     45        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     46        case 1 : key += (uint32_t) data[ 0 ];
     47          /* case 0: nothing left to add */
     48        }
     49        MIX( key );
     50    }
     51
     52    return key;
     53
     54#   undef MIX
    2755}
    28 
    29 #ifdef C_BIG_ENDIAN
    30 static uint32_t
    31 TWSHMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    32 {
    33    uint8_t *k = data;
    34    uint32_t len = length;
    35    uint32_t key = initval;
    36 
    37   if (data == NULL) return 0;
    38 
    39    while (len >= 4) {
    40       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    41       mix (key);
    42       k += 4;
    43       len -= 4;
    44    }
    45 
    46    switch (len) {
    47      /* all the case statements fall through */
    48    case 3 : key += (((uint32_t) k[2]) << 16);
    49    case 2 : key += (((uint32_t) k[1]) << 8);
    50    case 1 : key += k[0];
    51      /* case 0: nothing left to add */
    52    }
    53    mix (key);
    54 
    55    return key;
    56 }
    57 #else
    58 static uint32_t
    59 TWSHMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    60 {
    61    uint8_t *k = data;
    62    uint32_t len = length;
    63    uint32_t key = initval;
    64 
    65   if (data == NULL) return 0;
    66 
    67    if (((uint32_t) k) & 3) {
    68       while (len >= 4) {  /* unaligned */
    69         key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    70         mix (key);
    71         k += 4;
    72         len -= 4;
    73       }
    74    } else {
    75       while (len >= 4) {  /* aligned */
    76         key += *((uint32_t *) (k + 0));
    77         mix (key);
    78         k += 4;
    79         len -= 4;
    80       }
    81    }
    82 
    83    switch (len) {
    84      /* all the case statements fall through */
    85    case 3 : key += (((uint32_t) k[2]) << 16);
    86    case 2 : key += (((uint32_t) k[1]) << 8);
    87    case 1 : key += k[0];
    88      /* case 0: nothing left to add */
    89    }
    90    mix (key);
    91 
    92    return key;
    93 }
    94 #endif
    95 
    96 #undef mix
    9756
    9857#undef bitsizeof
  • release/3/hashes/tags/2.3/TWUserMixHash-support.scm

    r8297 r8575  
    1717#include "hashes.h"
    1818
    19 #define MIXER(key) {\
    20     char numbuf[C_SIZEOF_FLONUM];\
    21     C_word *ptr = (C_word *) &numbuf;\
    22     C_word num = C_unsigned_int_to_num (&ptr, key);\
    23     C_word res;\
    24     C_save (num);\
    25     res = C_callback (mixer, 1);\
    26     key = (uint32_t) C_num_to_unsigned_int (res);\
     19static uint32_t
     20TWUserMixHash( uint8_t *data, uint32_t length, uint32_t key, C_word mixer )
     21{
     22    /* User 32 bit Mix Function */
     23#   define MIX( key ) { \
     24        char numbuf[ C_SIZEOF_FLONUM ]; \
     25        C_word *ptr = (C_word *) &numbuf; \
     26        C_word num = C_unsigned_int_to_num( &ptr, (key) ); \
     27        C_save( num ); \
     28        num = C_callback( mixer, 1 ); \
     29        (key) = (uint32_t) C_num_to_unsigned_int( num ); \
     30        }
     31
     32    if (data) {
     33
     34        while (length >= sizeof( uint32_t )) {
     35            key += *((uint32_t *) data);
     36            MIX( key );
     37            data += sizeof( uint32_t );
     38            length -= sizeof( uint32_t );
     39        }
     40
     41        switch (length) {
     42          /* all the case statements fall through */
     43        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     44        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     45        case 1 : key += (uint32_t) data[ 0 ];
     46          /* case 0: nothing left to add */
     47        }
     48        MIX( key );
    2749    }
    2850
    29 #ifdef C_BIG_ENDIAN
    30 static uint32_t
    31 TWUserMixHash (uint8_t *data, uint32_t length, uint32_t key, void * mixer_data)
    32 {
    33   uint8_t *k = data;
    34   uint32_t len = length;
    35   C_word mixer = (C_word) ((C_SCHEME_BLOCK *) (((char *) mixer_data) - sizeof (C_header)));
     51    return key;
    3652
    37   if (C_header_bits (mixer) != C_CLOSURE_TYPE) {
    38     C_printf ("Error: (TWUserMixHash) invalid mix procedure: not a closure");
    39     return 0;
    40   }
    41 
    42   if (data == NULL) return 0;
    43 
    44   while (len >= 4) {
    45     key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    46     MIXER (key);
    47     k += 4;
    48     len -= 4;
    49   }
    50 
    51   switch (len) {
    52     /* all the case statements fall through */
    53   case 3 : key += (((uint32_t) k[2]) << 16);
    54   case 2 : key += (((uint32_t) k[1]) << 8);
    55   case 1 : key += k[0];
    56     /* case 0: nothing left to add */
    57   }
    58   MIXER (key);
    59 
    60   return key;
     53#   undef MIX
    6154}
    62 #else
    63 static uint32_t
    64 TWUserMixHash (uint8_t *data, uint32_t length, uint32_t key, void * mixer_data)
    65 {
    66   uint8_t *k = data;
    67   uint32_t len = length;
    68   C_word mixer = (C_word) ((C_SCHEME_BLOCK *) (((char *) mixer_data) - sizeof (C_header)));
    69 
    70   if (C_header_bits (mixer) != C_CLOSURE_TYPE) {
    71     C_printf ("Error: (TWUserMixHash) invalid mix procedure: not a closure");
    72     return 0;
    73   }
    74 
    75   if (data == NULL) return 0;
    76 
    77   if (((uint32_t) k) & 3) {
    78     while (len >= 4) {  /* unaligned */
    79       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    80       MIXER (key);
    81       k += 4;
    82       len -= 4;
    83     }
    84   } else {
    85     while (len >= 4) {  /* aligned */
    86       key += *((uint32_t *) (k + 0));
    87       MIXER (key);
    88       k += 4;
    89       len -= 4;
    90     }
    91   }
    92 
    93   switch (len) {
    94    /* all the case statements fall through */
    95   case 3 : key += (((uint32_t) k[2]) << 16);
    96   case 2 : key += (((uint32_t) k[1]) << 8);
    97   case 1 : key += k[0];
    98    /* case 0: nothing left to add */
    99   }
    100   MIXER (key);
    101 
    102   return key;
    103 }
    104 #endif
    10555
    10656#undef bitsizeof
     
    11363                       "TWUserMixHash" scheme-pointer unsigned-integer32
    11464                                       unsigned-integer32
    115                                        nonnull-scheme-pointer))
     65                                       scheme-object))
  • release/3/hashes/tags/2.3/hashes-eggdoc.scm

    r8297 r8575  
    293293
    294294  (history
     295    (version "2.3" "Made little & big endian hashing equivalent. Very minor speed-up. Dropped use of \"iset\".")
    295296    (version "2.2" "Added Rabin-Karp string hash search, TWUserMixHash.")
    296297    (version "2.105" "Added TWSHMXHash, TWSHMLMXHash, TWMGMXHash.")
  • release/3/hashes/tags/2.3/hashes.html

    r8297 r8575  
    355355<h3>Version</h3>
    356356<ul>
    357 <li>2.106 Added Rabin-Karp string hash search, TWUserMixHash.</li>
     357<li>2.3 Made little &amp; big endian hashing equivalent. Very minor speed-up. Dropped use of &quot;iset&quot;.</li>
     358<li>2.2 Added Rabin-Karp string hash search, TWUserMixHash.</li>
    358359<li>2.105 Added TWSHMXHash, TWSHMLMXHash, TWMGMXHash.</li>
    359360<li>2.104 Added make-fixnum-bounded-hash.</li>
  • release/3/hashes/tags/2.3/hashes.meta

    r8297 r8575  
    55 (license "BSD")
    66 (category crypt)
    7  (needs misc-extn miscmacros mathh message-digest box crc iset)
     7 (needs misc-extn miscmacros mathh message-digest box crc)
    88 (author "Kon Lovett")
    99 (egg "hashes.egg")
  • release/3/hashes/tags/2.3/hashes.setup

    r8297 r8575  
    22
    33(required-extension-version
    4   'iset                   "1.4"
    54  'crc                    "1.1"
    65  'box                    "1.8"
  • release/3/hashes/tags/2.3/rabin-karp.scm

    r8297 r8575  
    33
    44(use srfi-1 srfi-13 srfi-69)
    5 (use iset)
    65
    76(eval-when (compile)
     
    2221;;;
    2322
    24 (define (check-procedure loc obj)
     23(define-inline (check-procedure loc obj)
    2524  (##sys#check-closure obj loc) )
    2625
    27 (define (check-string loc obj)
     26(define-inline (check-string loc obj)
    2827  (##sys#check-string obj loc) )
    2928
     
    4948      ; a match.
    5049      [substrs-lens
    51         (iset->list (apply iset
    52                            (map (lambda (x)
    53                                   (check-string 'make-rabin-karp-string-search x)
    54                                   (string-length x) )
    55                                 substrs)))]
     50        (sort! (map (lambda (x)
     51                      (check-string 'make-rabin-karp-string-search x)
     52                      (string-length x) )
     53                    substrs)
     54               <) ]
    5655      ; Search string lookup table
    5756      [substrs-tbl
     
    6362    ; string in the target string, otherwise #f.
    6463    (lambda (str #!optional (start 0) (end (string-length str)))
    65       ; Limit length to search.
    66       (let* (
     64      (let (
    6765          ; Any matching search string at this position?
    6866          [match@
     
    8381        ; Any matching search string?
    8482        (let loop ([pos start])
    85           (cond [(= pos end)    #f]
    86                 [(match@ pos)   => identity]
    87                 [else           (loop (+ pos 1)) ] ) ) ) ) ) )
     83          (and (< pos end)
     84               (or (match@ pos)
     85                   (loop (+ pos 1)) ) ) ) ) ) ) )
  • release/3/hashes/tags/2.3/tests/hashes-test.scm

    r8297 r8575  
    44(use hashes)
    55(use rabin-karp)
     6(use srfi-1)
    67
    78;;;
     
    1415;;;
    1516
    16 (define-constant TSTSTR "The large brown fox jumped over the lazy dog.")
    17 (define TSTSTR-LEN (string-length TSTSTR))
    18 (define TSTSTR-HALF-LEN (fx/ TSTSTR-LEN 2))
     17(define TSTSTR "The large brown fox jumped over the lazy dog.")
     18
     19(define TSTSTR-LEN        (string-length TSTSTR))
     20(define TSTSTR-HALF-LEN   (fx/ TSTSTR-LEN 2))
    1921
    2022;;;
     
    2224(define-test hashes-test "Hash Functions"
    2325
    24         (test/case "Hash-prim"
    25 
    26                 (expect-success "RJMXHash" (RJMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    27                 (expect-success "TWMXHash" (TWMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    28                 (expect-success "TWSHMXHash" (TWSHMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    29                 (expect-success "TWSHMLMXHash" (TWSHMLMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    30                 (expect-success "TWMGMXHash" (TWMGMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    31                 (expect-success "RSHash" (RSHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    32                 (expect-success "JSHash" (JSHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    33                 (expect-success "PJWHash" (PJWHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    34                 (expect-success "ELFHash" (ELFHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    35                 (expect-success "BKDRHash" (BKDRHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    36                 (expect-success "SDBMHash" (SDBMHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    37                 (expect-success "DJBHash" (DJBHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    38                 (expect-success "NDJBHash" (NDJBHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    39                 (expect-success "DEKHash" (DEKHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    40                 (expect-success "APHash" (APHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    41                 (expect-success "CRCHash" (CRCHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    42                 (expect-success "PHSFHash" (PHSFHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    43                 (expect-success "FNVHash" (FNVHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    44                 (expect-success "FNVAHash" (FNVAHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    45                 (expect-success "BRPHash" (BRPHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    46                 (expect-success "PYHash" (PYHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    47                 (expect-success "RJL3Hash" (RJL3Hash-prim TSTSTR TSTSTR-HALF-LEN 0))
    48                 (expect-success "ISPLHash" (ISPLHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    49         )
    50 
    51         (test/case "Hash"
     26        (test/suite "Hash-prim Half Length"
     27
     28                (expect-eqv "RJMXHash"      1495738488 (RJMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     29                (expect-eqv "TWMXHash"      1783737257 (TWMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     30                (expect-eqv "TWSHMXHash"    4294724170 (TWSHMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     31                (expect-eqv "TWSHMLMXHash"  3316553819 (TWSHMLMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     32                (expect-eqv "TWMGMXHash"    3799230039 (TWMGMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     33                (expect-eqv "RSHash"        561364390  (RSHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     34                (expect-eqv "JSHash"        1096595314 (JSHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     35                (expect-eqv "PJWHash"       11905      (PJWHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     36                (expect-eqv "ELFHash"       125889045  (ELFHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     37                (expect-eqv "BKDRHash"      2233812262 (BKDRHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     38                (expect-eqv "SDBMHash"      1850315706 (SDBMHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     39                (expect-eqv "DJBHash"       664891301  (DJBHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     40                (expect-eqv "NDJBHash"      786919305  (NDJBHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     41                (expect-eqv "DEKHash"       4159618807 (DEKHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     42                (expect-eqv "APHash"        3373256484 (APHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     43                (expect-eqv "CRCHash"       4140400781 (CRCHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     44                (expect-eqv "PHSFHash"      4232571984 (PHSFHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     45                (expect-eqv "FNVHash"       2129953783 (FNVHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     46                (expect-eqv "FNVAHash"      1173052123 (FNVAHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     47                (expect-eqv "BRPHash"       1793202933 (BRPHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     48                (expect-eqv "PYHash"        10752      (PYHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     49                (expect-eqv "RJL3Hash"      1304064403  (RJL3Hash-prim TSTSTR TSTSTR-HALF-LEN 0))
     50                (expect-eqv "ISPLHash"      2015390325 (ISPLHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     51        )
     52
     53        (test/suite "Hash Full Length"
    5254
    5355                (expect-eqv "RJMXHash" (RJMXHash-prim TSTSTR TSTSTR-LEN 0) (RJMXHash TSTSTR))
     
    7678        )
    7779
    78         (test/case "Length Arg"
     80        (test/suite "Hash Length Arg"
    7981
    8082                (expect-eqv "RJMXHash" (RJMXHash-prim TSTSTR TSTSTR-HALF-LEN 0) (RJMXHash TSTSTR TSTSTR-HALF-LEN))
     
    103105        )
    104106
    105         (test/case "Digest"
     107        (test/suite "Digest"
    106108
    107109                (expect-success "RJMXHash" (RJMXHash:digest TSTSTR))
     
    151153)
    152154
     155;; This tests whether memory is being corrupted
     156;; There was a problem w/ syntax-case & RJL3Hash
     157
    153158(define-test hashes-random-test "RJL3Hash Idempotent?"
    154         (initial
    155           (define val (RJL3Hash-prim TSTSTR TSTSTR-LEN 0)) )
    156 
    157   (expect-eqv "1" val (RJL3Hash TSTSTR))
    158   (expect-eqv "2" val (RJL3Hash TSTSTR))
    159   (expect-eqv "3" val (RJL3Hash TSTSTR))
    160   (expect-eqv "4" val (RJL3Hash TSTSTR))
    161   (expect-eqv "5" val (RJL3Hash TSTSTR))
    162   (expect-eqv "6" val (RJL3Hash TSTSTR))
    163   (expect-eqv "7" val (RJL3Hash TSTSTR))
    164   (expect-eqv "8" val (RJL3Hash TSTSTR))
    165   (expect-eqv "9" val (RJL3Hash TSTSTR))
    166 )
    167 
    168 (define-test rabin-karp-test "Rabin-Karp Search"
    169         (initial
    170           (define substrs '("quick" "foo" "brown" "dog" "skasfdskjsalksafnsalsfsdsdjkldsajlfsalsk"))
    171           (define hashp)
    172           (define rksp) )
    173 
    174   (expect-set! hashp (make-fixnum-bounded-hash RJL3Hash-prim))
    175   (expect-set! rksp (make-rabin-karp-string-search substrs string=? hashp))
    176   (expect-success "Without start & end" (rksp TSTSTR))
    177   (expect-success "With start & end" (rksp TSTSTR 41 TSTSTR-LEN))
     159  (expect-eqv "1" 2110415480 (RJL3Hash TSTSTR))
     160  (expect-eqv "2" 2110415480 (RJL3Hash TSTSTR))
     161  (expect-eqv "3" 2110415480 (RJL3Hash TSTSTR))
     162  (expect-eqv "4" 2110415480 (RJL3Hash TSTSTR))
     163  (expect-eqv "5" 2110415480 (RJL3Hash TSTSTR))
     164  (expect-eqv "6" 2110415480 (RJL3Hash TSTSTR))
     165  (expect-eqv "7" 2110415480 (RJL3Hash TSTSTR))
     166  (expect-eqv "8" 2110415480 (RJL3Hash TSTSTR))
     167  (expect-eqv "9" 2110415480 (RJL3Hash TSTSTR))
    178168)
    179169
     
    190180    (expect-set! "TWUserMixHash Make" usrmixhsh (receive (make-TWUserMixHash mix #t)))
    191181    (side-effect
    192       (set! hash-prim (car usrmixhsh))
    193       (set! hash (cadr usrmixhsh))
    194       (set! binary:digest (caddr usrmixhsh))
    195       (set! text:digest (cadddr usrmixhsh))
    196       (set! prim:digest (car (cddddr usrmixhsh))) )
    197 
    198   (expect-success "TWUserMixHash-prim" (hash-prim TSTSTR TSTSTR-HALF-LEN 0))
     182      (set! hash-prim       (first usrmixhsh))
     183      (set! hash            (second usrmixhsh))
     184      (set! binary:digest   (third usrmixhsh))
     185      (set! text:digest     (fourth usrmixhsh))
     186      (set! prim:digest     (fifth usrmixhsh)) )
     187
     188  (expect-eqv "TWUserMixHash-prim full-length" 543453076 (hash-prim TSTSTR TSTSTR-LEN 0))
     189  (expect-eqv "TWUserMixHash-prim half-length" 30057 (hash-prim TSTSTR TSTSTR-HALF-LEN 0))
     190
    199191  (expect-eqv "TWUserMixHash Hash" (hash-prim TSTSTR TSTSTR-LEN 0) (hash TSTSTR))
    200192  (expect-eqv "TWUserMixHash Length Arg" (hash-prim TSTSTR TSTSTR-HALF-LEN 0) (hash TSTSTR TSTSTR-HALF-LEN))
    201   (expect-success "TWUserMixHash Digest" (text:digest TSTSTR))
     193
     194  (expect-equal "TWUserMixHash Digest" "20646f94" (text:digest TSTSTR))
     195)
     196
     197(define-test rabin-karp-test "Rabin-Karp Search"
     198        (initial
     199          (define substrs '("quick" "foo" "brown" "dog" "skasfdskjsalksafnsalsfsdsdjkldsajlfsalsk"))
     200          (define hashp)
     201          (define rksp) )
     202
     203  (expect-set! rksp (make-rabin-karp-string-search substrs))
     204
     205  (expect-equal "W/O start & end" '("brown" (10 15)) (rksp TSTSTR))
     206  (expect-equal "W/ start & end" '("dog" (41 44)) (rksp TSTSTR 41 TSTSTR-LEN))
     207
     208  (expect-set! hashp (make-fixnum-bounded-hash RJL3Hash-prim))
     209  (expect-set! rksp (make-rabin-karp-string-search substrs string=? hashp))
     210
     211  (expect-equal "W/O start & end" '("brown" (10 15)) (rksp TSTSTR))
     212  (expect-equal "W/ start & end" '("dog" (41 44)) (rksp TSTSTR 41 TSTSTR-LEN))
    202213)
    203214
  • release/3/hashes/trunk/APHash.scm

    r8148 r8575  
    3333
    3434static uint32_t
    35 APHash (uint8_t *data, uint32_t len, uint32_t initval)
     35APHash( uint8_t *data, uint32_t length, uint32_t key )
    3636{
    37    uint32_t hash = initval;
    38    uint32_t i    = 0;
     37    if (data) {
     38        int i;
     39        for (i = 0; i < length; data++, i++) {
     40            key ^= ((i & 1) == 0) /* even? */
     41                      ? (  (key <<  7) ^ ((uint32_t) *data) ^ (key >> 3))
     42                      : (~((key << 11) ^ ((uint32_t) *data) ^ (key >> 5)));
     43        }
     44    }
    3945
    40    if (data == NULL) return 0;
    41 
    42    for (i = 0; i < len; data++, i++) {
    43       hash ^= ((i & 1) == 0) ? (  (hash <<  7) ^ (*data) ^ (hash >> 3)) :
    44                                (~((hash << 11) ^ (*data) ^ (hash >> 5)));
    45    }
    46 
    47    return hash;
     46    return key;
    4847}
    4948
  • release/3/hashes/trunk/BKDRHash.scm

    r8148 r8575  
    2626
    2727static uint32_t
    28 BKDRHash (uint8_t *data, uint32_t len, uint32_t initval)
     28BKDRHash( uint8_t *data, uint32_t length, uint32_t key )
    2929{
    30    uint32_t seed = 131; /* 31 131 1313 13131 131313 etc.. */
    31    uint32_t hash = initval;
    32    uint32_t i;
     30    if (data) {
     31        uint32_t seed = 131; /* 31 131 1313 13131 131313 etc.. */
     32        for ( ; length; data++, length--) {
     33            key = (key * seed) + ((uint32_t) *data);
     34        }
     35    }
    3336
    34    if (data == NULL) return 0;
    35 
    36    for (i = 0; i < len; data++, i++) {
    37       hash = (hash * seed) + (*data);
    38    }
    39 
    40    return hash;
     37    return key;
    4138}
    4239
  • release/3/hashes/trunk/BRPHash.scm

    r8148 r8575  
    2121
    2222static uint32_t
    23 BRPHash (uint8_t *data, uint32_t len, uint32_t initval)
     23BRPHash( uint8_t *data, uint32_t length, uint32_t key )
    2424{
    25 #  define SHIFT 6
    26 #  define MASK (((uint32_t) (~0)) << (bitsizeof(uint32_t) - SHIFT))
     25#   define MASK (((uint32_t) (~0)) << (bitsizeof( uint32_t ) - 6))
    2726
    28    uint32_t hash = initval;
    29    uint32_t i;
     27    if (data) {
     28        for ( ; length; data++, length--) {
     29            key = (key & MASK) ^ (key << 6) ^ ((uint32_t) *data);
     30        }
     31    }
    3032
    31    if (data == NULL) return 0;
     33    return key;
    3234
    33    for (i = 0; i < len; data++, i++) {
    34       hash = (hash & MASK) ^ (hash << SHIFT) ^ (*data);
    35    }
    36 
    37    return hash;
    38 
    39 #  undef SHIFT
    40 #  undef MASK
     35#   undef MASK
    4136}
    4237
  • release/3/hashes/trunk/DEKHash.scm

    r8148 r8575  
    2525
    2626static uint32_t
    27 DEKHash (uint8_t *data, uint32_t len, uint32_t initval)
     27DEKHash( uint8_t *data, uint32_t length, uint32_t key )
    2828{
    29    uint32_t hash = initval ? initval : len;
    30    uint32_t i;
     29    if (! key) key = length;
    3130
    32    if (data == NULL) return 0;
     31    if (data) {
     32        for ( ; length; data++, length--) {
     33            key = ((key << 5) ^ (key >> 27)) ^ ((uint32_t) *data);
     34        }
     35    }
    3336
    34    for (i = 0; i < len; data++, i++) {
    35       hash = ((hash << 5) ^ (hash >> 27)) ^ (*data);
    36    }
    37 
    38    return hash;
     37    return key;
    3938}
    4039
  • release/3/hashes/trunk/DJBHash.scm

    r8148 r8575  
    2525
    2626static uint32_t
    27 DJBHash (uint8_t *data, uint32_t len, uint32_t initval)
     27DJBHash( uint8_t *data, uint32_t length, uint32_t key )
    2828{
    29    uint32_t hash = initval ? initval : 5381;
    30    uint32_t i;
     29    if (! key) key = 5381;
    3130
    32    if (data == NULL) return 0;
     31    if (data) {
     32        for ( ; length; data++, length--) {
     33            key = ((key << 5) + key) + ((uint32_t) *data);
     34        }
     35    }
    3336
    34    for (i = 0; i < len; data++, i++) {
    35       hash = ((hash << 5) + hash) + (*data);
    36    }
    37 
    38    return hash;
     37    return key;
    3938}
    4039
  • release/3/hashes/trunk/ELFHash.scm

    r8148 r8575  
    2424
    2525static uint32_t
    26 ELFHash (uint8_t *data, uint32_t len, uint32_t initval)
     26ELFHash( uint8_t *data, uint32_t length, uint32_t key )
    2727{
    28    uint32_t hash = initval;
    29    uint32_t x;
    30    uint32_t i;
     28    if (data) {
     29        for ( ; length; data++, length--) {
     30            uint32_t test;
     31            key = (key << 4) + ((uint32_t) *data);
     32            if ((test = (key & 0xF0000000L))) {
     33                key ^= (test >> 24);
     34                key &= ~test;
     35            }
     36        }
     37    }
    3138
    32    if (data == NULL) return 0;
    33 
    34    for (i = 0; i < len; data++, i++) {
    35       hash = (hash << 4) + (*data);
    36       if ((x = (hash & 0xF0000000L)) != 0) {
    37          hash ^= (x >> 24);
    38          hash &= ~x;
    39       }
    40    }
    41 
    42    return hash;
     39    return key;
    4340}
    4441
  • release/3/hashes/trunk/FNVAHash.scm

    r8148 r8575  
    7272 */
    7373
    74 #define FNV1_32_INIT            ((uint32_t)0x811c9dc5)
    75 #define FNV1_32A_INIT           FNV1_32_INIT
    76 #define FNV_32_PRIME            ((uint32_t)0x01000193)
    77 
    7874/*
    7975        Useful with the gcc compiler with -O3 on many AMD & Intel CPUs.
    8076        Undefine if this is the case.
    8177*/
     78
    8279#define NO_FNV_GCC_OPTIMIZATION
    8380
    8481static uint32_t
    85 FNVAHash (uint8_t *data, uint32_t len, uint32_t initval)
     82FNVAHash( uint8_t *data, uint32_t length, uint32_t key )
    8683{
    87         uint32_t hval = initval ? initval : FNV1_32A_INIT;
    88         uint8_t *bp = data;                     /* start of buffer */
    89         uint8_t *be = bp + len; /* beyond end of buffer */
     84#   define FNV1_32A_INIT  ((uint32_t)0x811c9dc5)
     85#   define FNV_32_PRIME         ((uint32_t)0x01000193)
    9086
    91         if (data == NULL) return 0;
     87    if (! key) key = FNV1_32A_INIT;
    9288
    93         /*
    94          * FNV-1a hash each octet in the buffer
    95          */
    96         while (bp < be) {
     89    if (data) {
     90        uint8_t *be = data + length;    /* beyond end of buffer */
    9791
    98                 /* xor the bottom with the current octet */
    99                 hval ^= (uint32_t)*bp++;
     92        /* FNV-1a hash each octet in the buffer */
     93        while (data < be) {
    10094
    101                 /* multiply by the 32 bit FNV magic prime mod 2^32 */
     95            /* xor the bottom with the current octet */
     96            key ^= (uint32_t) *data++;
     97
     98            /* multiply by the 32 bit FNV magic prime mod 2^32 */
    10299#ifdef NO_FNV_GCC_OPTIMIZATION
    103                 hval *= FNV_32_PRIME;
     100            key *= FNV_32_PRIME;
    104101#else
    105                 hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
     102            key += (key << 1) + (key << 4) + (key << 7) + (key << 8) + (key << 24);
    106103#endif
    107         }
     104        }
     105    }
    108106
    109         /* return our new hash value */
    110         return hval;
     107    /* return our new hash value */
     108    return key;
     109
     110#   undef FNV_32_PRIME
     111#   undef FNV1_32A_INIT
    111112}
    112113
    113114#undef NO_FNV_GCC_OPTIMIZATION
    114 #undef FNV_32_PRIME
    115 #undef FNV1_32A_INIT
    116 #undef FNV1_32_INIT
    117115
    118116#undef bitsizeof
  • release/3/hashes/trunk/FNVHash.scm

    r8148 r8575  
    7272 */
    7373
    74 #define FNV1_32_INIT            ((uint32_t)0x811c9dc5)
    75 #define FNV1_32A_INIT           FNV1_32_INIT
    76 #define FNV_32_PRIME            ((uint32_t)0x01000193)
    77 
    7874/*
    7975        Useful with the gcc compiler with -O3 on many AMD & Intel CPUs.
     
    8379
    8480static uint32_t
    85 FNVHash (uint8_t *data, uint32_t len, uint32_t initval)
     81FNVHash( uint8_t *data, uint32_t length, uint32_t key )
    8682{
    87         uint32_t hval = initval ? initval : FNV1_32_INIT;
    88         uint8_t *bp = data;                     /* start of buffer */
    89         uint8_t *be = bp + len; /* beyond end of buffer */
     83#   define FNV1_32_INIT         ((uint32_t) 0x811c9dc5)
     84#   define FNV_32_PRIME         ((uint32_t) 0x01000193)
    9085
    91         if (data == NULL) return 0;
     86    if (! key) key = FNV1_32_INIT;
    9287
    93         /*
    94          * FNV-1 hash each octet in the buffer
    95          */
    96         while (bp < be) {
     88    if (data) {
     89        uint8_t *be = data + length;    /* beyond end of buffer */
    9790
    98                 /* multiply by the 32 bit FNV magic prime mod 2^32 */
     91        /* FNV-1 hash each octet in the buffer */
     92        while (data < be) {
     93
     94            /* multiply by the 32 bit FNV magic prime mod 2^32 */
    9995#ifdef NO_FNV_GCC_OPTIMIZATION
    100                 hval *= FNV_32_PRIME;
     96            key *= FNV_32_PRIME;
    10197#else
    102                 hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
     98            key += (key << 1) + (key << 4) + (key << 7) + (key << 8) + (key << 24);
    10399#endif
    104100
    105                 /* xor the bottom with the current octet */
    106                 hval ^= ((uint32_t) *bp++);
    107         }
     101            /* xor the bottom with the current octet */
     102            key ^= ((uint32_t) *data++);
     103        }
     104    }
    108105
    109         /* return our new hash value */
    110         return hval;
     106    /* return our new hash value */
     107    return key;
     108
     109#   undef FNV_32_PRIME
     110#   undef FNV1_32_INIT
    111111}
    112112
    113113#undef NO_FNV_GCC_OPTIMIZATION
    114 #undef FNV_32_PRIME
    115 #undef FNV1_32A_INIT
    116 #undef FNV1_32_INIT
    117114
    118115#undef bitsizeof
  • release/3/hashes/trunk/ISPLHash.scm

    r8148 r8575  
    5959
    6060static uint32_t
    61 ISPLHash (uint8_t *data, uint32_t len, uint32_t initval)
     61ISPLHash( uint8_t *data, uint32_t length, uint32_t key )
    6262{
    63 #  define SHIFT 5
    64 #  define BITS bitsizeof(uint32_t)
     63    if (data) {
     64        uint32_t i;
    6565
    66    uint32_t hash = initval;
    67    uint32_t i;
    68    uint32_t lim = sizeof(uint32_t) < len ? len : sizeof(uint32_t);
     66        uint32_t lim = sizeof( uint32_t ) < length ? length : sizeof( uint32_t );
     67        for (i = 0; i < lim; data++, i++) {
     68            key = (key << 8) | ((uint32_t) *data);
     69        }
    6970
    70    if (data == NULL) return 0;
    71  
    72    for (i = 0; i < lim; data++, i++) {
    73       hash = (hash << 8) | (*data);
    74    }
     71        for (; i < length; data++, i++) {
     72            key = ((key << 5) | ((key >> (bitsizeof( uint32_t ) - 5)) & ((1 << 5) - 1)))
     73                      ^ ((uint32_t) *data);
     74        }
     75    }
    7576
    76    for (; i < len; data++, i++) {
    77       hash = (hash << SHIFT) | ((hash >> (BITS - SHIFT)) & ((1 << SHIFT) - 1));
    78       hash ^= (*data);
    79    }
    80 
    81    return hash;
    82 
    83 #  undef BITS
    84 #  undef SHIFT
     77    return key;
    8578}
    8679
  • release/3/hashes/trunk/JSHash.scm

    r8148 r8575  
    2121
    2222static uint32_t
    23 JSHash (uint8_t *data, uint32_t len, uint32_t initval)
     23JSHash( uint8_t *data, uint32_t length, uint32_t key )
    2424{
    25    uint32_t hash = initval ? initval : 1315423911;
    26    uint32_t i;
     25    if (! key) key = 1315423911;
    2726
    28    if (data == NULL) return 0;
     27    if (data) {
     28        for ( ; length; data++, length--) {
     29            key ^= (key << 5) + ((uint32_t) *data) + (key >> 2);
     30        }
     31    }
    2932
    30    for (i = 0; i < len; data++, i++) {
    31       hash ^= ((hash << 5) + (*data) + (hash >> 2));
    32    }
    33 
    34    return hash;
     33    return key;
    3534}
    3635
  • release/3/hashes/trunk/NDJBHash.scm

    r8148 r8575  
    2525
    2626static uint32_t
    27 NDJBHash (uint8_t *data, uint32_t len, uint32_t initval)
     27NDJBHash( uint8_t *data, uint32_t length, uint32_t key )
    2828{
    29    uint32_t hash = initval ? initval : 5381;
    30    uint32_t i;
     29    if (! key) key = 5381;
    3130
    32    if (data == NULL) return 0;
     31    if (data) {
     32        for ( ; length; data++, length--) {
     33            key = (key * 33) ^ ((uint32_t) *data);
     34        }
     35    }
    3336
    34    for (i = 0; i < len; data++, i++) {
    35       hash = hash * 33 ^ (*data);
    36    }
    37 
    38    return hash;
     37    return key;
    3938}
    4039
  • release/3/hashes/trunk/PHSFHash.scm

    r8148 r8575  
    2121
    2222static uint32_t
    23 PHSFHash (uint8_t *data, uint32_t len, uint32_t initval)
     23PHSFHash( uint8_t *data, uint32_t length, uint32_t key )
    2424{
    25 #   define get16bits(d) (*((uint16_t *)(d)))
     25#   define BITS16_REF( d ) (*((uint16_t *) (d)))
    2626
    27     uint32_t hash = initval ? initval : len;
    28     uint32_t tmp;
    29     uint32_t rem;
     27    if (! key) key = length;
    3028
    31     if (data == NULL) return 0;
     29    if (data) {
     30        uint32_t remlen = length & 3;
    3231
    33     rem = len & 3;
    34     len >>= 2;
     32        length >>= 2;
    3533
    36     /* Main loop */
    37     for (; len > 0; len--) {
    38         hash  += get16bits(data);
    39         tmp    = (get16bits(data + sizeof(uint16_t)) << 11) ^ hash;
    40         hash   = (hash << 16) ^ tmp;
    41         data  += 2 * sizeof(uint16_t);
    42         hash  += hash >> 11;
     34        /* Main loop */
     35        for (; length; length--) {
     36            uint32_t tmp;
     37            key  += BITS16_REF( data );
     38            tmp   = (BITS16_REF( data + sizeof( uint16_t ) ) << 11) ^ key;
     39            key   = (key << sizeof( uint16_t )) ^ tmp;
     40            data += 2 * sizeof( uint16_t );
     41            key  += key >> 11;
     42        }
     43
     44        /* Handle end cases */
     45        switch (remlen) {
     46            case 3: key += BITS16_REF( data );
     47                    key ^= key << 16;
     48                    key ^= data[ sizeof( uint16_t ) ] << 18;
     49                    key += key >> 11;
     50                    break;
     51            case 2: key += BITS16_REF( data );
     52                    key ^= key << 11;
     53                    key += key >> 17;
     54                    break;
     55            case 1: key += *data;
     56                    key ^= key << 10;
     57                    key += key >> 1;
     58        }
     59
     60        /* Force "avalanching" of final 127 bits */
     61        key ^= key << 3;
     62        key += key >> 5;
     63        key ^= key << 2;
     64        key += key >> 15;
     65        key ^= key << 10;
    4366    }
    4467
    45     /* Handle end cases */
    46     switch (rem) {
    47         case 3: hash += get16bits(data);
    48                 hash ^= hash << 16;
    49                 hash ^= data[sizeof (uint16_t)] << 18;
    50                 hash += hash >> 11;
    51                 break;
    52         case 2: hash += get16bits(data);
    53                 hash ^= hash << 11;
    54                 hash += hash >> 17;
    55                 break;
    56         case 1: hash += *data;
    57                 hash ^= hash << 10;
    58                 hash += hash >> 1;
    59     }
     68    return key;
    6069
    61     /* Force "avalanching" of final 127 bits */
    62     hash ^= hash << 3;
    63     hash += hash >> 5;
    64     hash ^= hash << 2;
    65     hash += hash >> 15;
    66     hash ^= hash << 10;
    67 
    68     return hash;
    69 
    70 #   undef get16bits
     70#   undef BITS16_REF
    7171}
    7272
  • release/3/hashes/trunk/PJWHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 /* This hash algorithm is based on work by Peter J. Weinberger of AT&T
    21 Bell Labs. */
     20/* This hash algorithm is based on work by Peter J. Weinberger of AT&T Bell Labs. */
    2221
    23 #if 0
    2422static uint32_t
    25 PJWHash (uint8_t *data, uint32_t len, uint32_t initval)
     23PJWHash( uint8_t *data, uint32_t length, uint32_t key )
    2624{
    27    uint32_t hash = initval;
    28    uint32_t test;
    29    uint32_t i;
     25    if (data) {
     26        for ( ; length; data++, length--) {
     27            uint32_t test;
     28            key = (key << 2) + ((uint32_t) *data);
     29            if ((test = (key & 0xC000))) {
     30                key = ((key ^ (test >> 12)) & 0x3FFF);
     31            }
     32        }
     33    }
    3034
    31    if (data == NULL) return 0;
    32 
    33    for (i = 0; i < len; data++, i++) {
    34       hash = (hash << 2) + (*data);
    35       if ((test = (hash & 0xC000)) != 0) {
    36          hash = ((hash ^ (test >> 12)) & 0x3FFF);
    37       }
    38    }
    39 
    40    return hash;
     35    return key;
    4136}
    42 #else
    43 static uint32_t
    44 PJWHash (uint8_t *data, uint32_t len, uint32_t initval)
    45 {
    46 #  define BitsInUnsignedInt ((uint32_t) bitsizeof (uint32_t))
    47 #  define ThreeQuarters     ((uint32_t) ((BitsInUnsignedInt * 3) / 4))
    48 #  define OneEighth         ((uint32_t) (BitsInUnsignedInt / 8))
    49 #  define HighBits          (((uint32_t) (~0)) << (BitsInUnsignedInt - OneEighth))
    50 
    51    uint32_t hash = initval;
    52    uint32_t test;
    53    uint32_t i;
    54 
    55    if (data == NULL) return 0;
    56 
    57    for (i = 0; i < len; data++, i++) {
    58       hash = (hash << OneEighth) + (*data);
    59       if ((test = (hash & HighBits)) != 0) {
    60          hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
    61       }
    62    }
    63 
    64    return hash;
    65 
    66 #  undef HighBits
    67 #  undef OneEighth
    68 #  undef ThreeQuarters
    69 #  undef BitsInUnsignedInt
    70 }
    71 #endif
    7237
    7338#undef bitsizeof
  • release/3/hashes/trunk/PYHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 /* Python */
     20/* Python Hash */
    2121
    2222static uint32_t
    23 PYHash (uint8_t *data, uint32_t len, uint32_t initval)
     23PYHash( uint8_t *data, uint32_t length, uint32_t key )
    2424{
    25    uint32_t hash;
    26    uint32_t i;
     25    if (! key) key = ((uint32_t) *data) << 7;
    2726
    28    if (data == NULL) return 0;
     27    if (data == NULL) {
     28        int i;
    2929
    30    hash = initval ? initval : (*data) << 7;
     30        for (i = 0; i < length; data++, i++) {
     31            key = (1000003 * key) ^ ((uint32_t) *data);
     32        }
    3133
    32    for (i = 0; i < len; data++, i++) {
    33       hash = (1000003 * hash) ^ (*data);
    34    }
     34        key ^= length;
     35    }
    3536
    36    hash ^= len;
    37 
    38    return (hash == (uint32_t)-1) ? (uint32_t)-2 : hash;
     37    return (((uint32_t) -1) == key) ? ((uint32_t) -2) : key;
    3938}
    4039
  • release/3/hashes/trunk/RJL3Hash.scm

    r8148 r8575  
    1717#>
    1818#include "hashes.h"
    19 
    20 /* Needed due to strange behavior w/ syntax-case - random results! */
    21 #define VALGRIND
    2219
    2320/*
     
    5754*/
    5855
    59 #define hashsize(n) (((uint32_t) 1) << (n))
    60 #define hashmask(n) (hashsize(n) - 1)
    61 #define rot(x, k)   (((x) << (k)) ^ ((x) >> (32 - (k))))
    62 
    63 /*
    64 -------------------------------------------------------------------------------
    65 mix -- mix 3 32-bit values reversibly.
    66 
    67 This is reversible, so any information in (a,b,c) before mix() is
    68 still in (a,b,c) after mix().
    69 
    70 If four pairs of (a,b,c) inputs are run through mix(), or through
    71 mix() in reverse, there are at least 32 bits of the output that
    72 are sometimes the same for one pair and different for another pair.
    73 This was tested for:
    74 * pairs that differed by one bit, by two bits, in any combination
    75   of top bits of (a,b,c), or in any combination of bottom bits of
    76   (a,b,c).
    77 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
    78   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
    79   is commonly produced by subtraction) look like a single 1-bit
    80   difference.
    81 * the base values were pseudorandom, all zero but one bit set, or
    82   all zero plus a counter that starts at zero.
    83 
    84 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
    85 satisfy this are
    86     4  6  8 16 19  4
    87     9 15  3 18 27 15
    88    14  9  3  7 17  3
    89 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
    90 for "differ" defined as + with a one-bit base and a two-bit delta.  I
    91 used http://burtleburtle.net/bob/hash/avalanche.html to choose
    92 the operations, constants, and arrangements of the variables.
    93 
    94 This does not achieve avalanche.  There are input bits of (a,b,c)
    95 that fail to affect some output bits of (a,b,c), especially of a.  The
    96 most thoroughly mixed value is c, but it doesn't really even achieve
    97 avalanche in c.
    98 
    99 This allows some parallelism.  Read-after-writes are good at doubling
    100 the number of bits affected, so the goal of mixing pulls in the opposite
    101 direction as the goal of parallelism.  I did what I could.  Rotates
    102 seem to cost as much as shifts on every machine I could lay my hands
    103 on, and rotates are much kinder to the top and bottom bits, so I used
    104 rotates.
    105 -------------------------------------------------------------------------------
    106 */
    107 
    108 #define mix(a, b, c) { \
    109   a -= c;  a ^= rot(c, 4);  c += b; \
    110   b -= a;  b ^= rot(a, 6);  a += c; \
    111   c -= b;  c ^= rot(b, 8);  b += a; \
    112   a -= c;  a ^= rot(c,16);  c += b; \
    113   b -= a;  b ^= rot(a,19);  a += c; \
    114   c -= b;  c ^= rot(b, 4);  b += a; \
     56static uint32_t
     57RJL3Hash( uint8_t *data, uint32_t length, uint32_t key )
     58{
     59    /*
     60    -------------------------------------------------------------------------------
     61    mix -- mix 3 32-bit values reversibly.
     62
     63    This is reversible, so any information in (a,b,c) before mix() is
     64    still in (a,b,c) after mix().
     65
     66    If four pairs of (a,b,c) inputs are run through mix(), or through
     67    mix() in reverse, there are at least 32 bits of the output that
     68    are sometimes the same for one pair and different for another pair.
     69    This was tested for:
     70    * pairs that differed by one bit, by two bits, in any combination
     71      of top bits of (a,b,c), or in any combination of bottom bits of
     72      (a,b,c).
     73    * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
     74      the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
     75      is commonly produced by subtraction) look like a single 1-bit
     76      difference.
     77    * the base values were pseudorandom, all zero but one bit set, or
     78      all zero plus a counter that starts at zero.
     79
     80    Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
     81    satisfy this are
     82        4  6  8 16 19  4
     83        9 15  3 18 27 15
     84       14  9  3  7 17  3
     85    Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
     86    for "differ" defined as + with a one-bit base and a two-bit delta.  I
     87    used http://burtleburtle.net/bob/hash/avalanche.html to choose
     88    the operations, constants, and arrangements of the variables.
     89
     90    This does not achieve avalanche.  There are input bits of (a,b,c)
     91    that fail to affect some output bits of (a,b,c), especially of a.  The
     92    most thoroughly mixed value is c, but it doesn't really even achieve
     93    avalanche in c.
     94
     95    This allows some parallelism.  Read-after-writes are good at doubling
     96    the number of bits affected, so the goal of mixing pulls in the opposite
     97    direction as the goal of parallelism.  I did what I could.  Rotates
     98    seem to cost as much as shifts on every machine I could lay my hands
     99    on, and rotates are much kinder to the top and bottom bits, so I used
     100    rotates.
     101    -------------------------------------------------------------------------------
     102    */
     103
     104#   define ROT( x, k ) (((x) << (k)) ^ ((x) >> (32 - (k))))
     105
     106#   define MIX( a, b, c ) { \
     107        (a) -= (c);  (a) ^= ROT( (c),  4 );  (c) += (b); \
     108        (b) -= (a);  (b) ^= ROT( (a),  6 );  (a) += (c); \
     109        (c) -= (b);  (c) ^= ROT( (b),  8 );  (b) += (a); \
     110        (a) -= (c);  (a) ^= ROT( (c), 16 );  (c) += (b); \
     111        (b) -= (a);  (b) ^= ROT( (a), 19 );  (a) += (c); \
     112        (c) -= (b);  (c) ^= ROT( (b),  4 );  (b) += (a); \
     113        }
     114
     115    /*
     116    -------------------------------------------------------------------------------
     117    final -- final mixing of 3 32-bit values (a,b,c) into c
     118
     119    Pairs of (a,b,c) values differing in only a few bits will usually
     120    produce values of c that look totally different.  This was tested for
     121    * pairs that differed by one bit, by two bits, in any combination
     122      of top bits of (a,b,c), or in any combination of bottom bits of
     123      (a,b,c).
     124    * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
     125      the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
     126      is commonly produced by subtraction) look like a single 1-bit
     127      difference.
     128    * the base values were pseudorandom, all zero but one bit set, or
     129      all zero plus a counter that starts at zero.
     130
     131    These constants passed:
     132     14 11 25 16 4 14 24
     133     12 14 25 16 4 14 24
     134    and these came close:
     135      4  8 15 26 3 22 24
     136     10  8 15 26 3 22 24
     137     11  8 15 26 3 22 24
     138    -------------------------------------------------------------------------------
     139    */
     140
     141#   define FINAL( a, b, c ) { \
     142        (c) ^= (b); (c) -= ROT( (b), 14 ); \
     143        (a) ^= (c); (a) -= ROT( (c), 11 ); \
     144        (b) ^= (a); (b) -= ROT( (a), 25 ); \
     145        (c) ^= (b); (c) -= ROT( (b), 16 ); \
     146        (a) ^= (c); (a) -= ROT( (c),  4 );  \
     147        (b) ^= (a); (b) -= ROT( (a), 14 ); \
     148        (c) ^= (b); (c) -= ROT( (b), 24 ); \
     149        }
     150
     151#   define GOLDEN_RATIO 0x9E3779B9
     152
     153    if (data) {
     154        uint32_t a, b;
     155
     156        /* Set up the internal state */
     157        a = b = key = GOLDEN_RATIO + length + key;
     158
     159        const uint32_t *k = ((uint32_t *) data);  /* read 32-bit chunks */
     160        const uint8_t  *k8;
     161
     162        /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
     163        while (length > 12) {
     164              a += k[0];
     165              b += k[1];
     166            key += k[2];
     167            MIX( a, b, key );
     168            length -= 12;
     169            k += 3;
     170        }
     171
     172        /*----------------------------- handle the last (probably partial) block */
     173        k8 = ((const uint8_t *) k);
     174        switch (length) {
     175        case 12: key += k[2];
     176                   b += k[1];
     177                   a += k[0];
     178                 break;
     179        case 11: key += ((uint32_t) k8[10]) << 16;  /* fall through */
     180        case 10: key += ((uint32_t) k8[9]) << 8;    /* fall through */
     181        case 9 : key +=  (uint32_t) k8[8];          /* fall through */
     182        case 8 :   b += k[1];
     183                   a += k[0];
     184                 break;
     185        case 7 :   b += ((uint32_t) k8[6]) << 16;   /* fall through */
     186        case 6 :   b += ((uint32_t) k8[5]) << 8;    /* fall through */
     187        case 5 :   b +=  (uint32_t) k8[4];          /* fall through */
     188        case 4 :   a += k[0];
     189                 break;
     190        case 3 :   a += ((uint32_t) k8[2]) << 16;   /* fall through */
     191        case 2 :   a += ((uint32_t) k8[1]) << 8;    /* fall through */
     192        case 1 :   a +=  (uint32_t) k8[0];
     193                 break;
     194        case 0 : return key;              /* zero length strings require no mixing */
     195        }
     196
     197        FINAL( a, b, key );
     198    }
     199
     200    return key;
     201
     202#   undef ROT
     203#   undef MIX
     204#   undef FINAL
    115205}
    116 
    117 /*
    118 -------------------------------------------------------------------------------
    119 final -- final mixing of 3 32-bit values (a,b,c) into c
    120 
    121 Pairs of (a,b,c) values differing in only a few bits will usually
    122 produce values of c that look totally different.  This was tested for
    123 * pairs that differed by one bit, by two bits, in any combination
    124   of top bits of (a,b,c), or in any combination of bottom bits of
    125   (a,b,c).
    126 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
    127   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
    128   is commonly produced by subtraction) look like a single 1-bit
    129   difference.
    130 * the base values were pseudorandom, all zero but one bit set, or
    131   all zero plus a counter that starts at zero.
    132 
    133 These constants passed:
    134  14 11 25 16 4 14 24
    135  12 14 25 16 4 14 24
    136 and these came close:
    137   4  8 15 26 3 22 24
    138  10  8 15 26 3 22 24
    139  11  8 15 26 3 22 24
    140 -------------------------------------------------------------------------------
    141 */
    142 
    143 #define final(a, b, c) { \
    144   c ^= b; c -= rot(b,14); \
    145   a ^= c; a -= rot(c,11); \
    146   b ^= a; b -= rot(a,25); \
    147   c ^= b; c -= rot(b,16); \
    148   a ^= c; a -= rot(c,4);  \
    149   b ^= a; b -= rot(a,14); \
    150   c ^= b; c -= rot(b,24); \
    151 }
    152 
    153 #ifdef C_BIG_ENDIAN
    154 static uint32_t
    155 RJL3Hash (uint8_t *data, uint32_t length, uint32_t initval)
    156 {
    157   uint32_t a, b, c;
    158   union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
    159 
    160   /* Set up the internal state */
    161   a = b = c = 0xdeadbeef + length + initval;
    162 
    163   u.ptr = data;
    164   if ((u.i & 0x3) == 0) {
    165     const uint32_t *k = ((uint32_t *) data);  /* read 32-bit chunks */
    166     const uint8_t  *k8;
    167 
    168     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
    169     while (length > 12) {
    170       a += k[0];
    171       b += k[1];
    172       c += k[2];
    173       mix(a,b,c);
    174       length -= 12;
    175       k += 3;
    176     }
    177 
    178     /*----------------------------- handle the last (probably partial) block */
    179     /*
    180      * "k[2]<<8" actually reads beyond the end of the string, but
    181      * then shifts out the part it's not allowed to read.  Because the
    182      * string is aligned, the illegal read is in the same word as the
    183      * rest of the string.  Every machine with memory protection I've seen
    184      * does it on word boundaries, so is OK with this.  But VALGRIND will
    185      * still catch it and complain.  The masking trick does make the hash
    186      * noticably faster for short strings (like English words).
    187      */
    188 #ifndef VALGRIND
    189 
    190     switch (length) {
    191     case 12: c += k[2]; b += k[1]; a += k[0]; break;
    192     case 11: c += k[2] << 8; b += k[1]; a += k[0]; break;
    193     case 10: c += k[2] << 16; b += k[1]; a += k[0]; break;
    194     case 9 : c += k[2] << 24; b += k[1]; a += k[0]; break;
    195     case 8 : b += k[1]; a += k[0]; break;
    196     case 7 : b += k[1] << 8; a += k[0]; break;
    197     case 6 : b += k[1] << 16; a += k[0]; break;
    198     case 5 : b += k[1] << 24; a += k[0]; break;
    199     case 4 : a += k[0]; break;
    200     case 3 : a += k[0] << 8; break;
    201     case 2 : a += k[0] << 16; break;
    202     case 1 : a += k[0] << 24; break;
    203     case 0 : return c;              /* zero length strings require no mixing */
    204     }
    205 
    206 #else  /* make valgrind happy */
    207 
    208     k8 = ((const uint8_t *) k);
    209     switch (length) {
    210       /* all the case statements fall through */
    211     case 12: c += k[2]; b += k[1]; a += k[0]; break;
    212     case 11: c += ((uint32_t) k8[10]) << 8;  /* fall through */
    213     case 10: c += ((uint32_t) k8[9]) << 16;  /* fall through */
    214     case 9 : c += ((uint32_t) k8[8]) << 24;  /* fall through */
    215     case 8 : b += k[1]; a += k[0]; break;
    216     case 7 : b += ((uint32_t) k8[6]) << 8;   /* fall through */
    217     case 6 : b += ((uint32_t) k8[5]) << 16;  /* fall through */
    218     case 5 : b += ((uint32_t) k8[4]) << 24;  /* fall through */
    219     case 4 : a += k[0]; break;
    220     case 3 : a += ((uint32_t) k8[2]) << 8;   /* fall through */
    221     case 2 : a += ((uint32_t) k8[1]) << 16;  /* fall through */
    222     case 1 : a += ((uint32_t) k8[0]) << 24; break;
    223     case 0 : return c;
    224     }
    225 
    226 #endif /* !VALGRIND */
    227 
    228   } else {                        /* need to read the key one byte at a time */
    229     const uint8_t *k = data;
    230 
    231     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
    232     while (length > 12) {
    233       a += ((uint32_t) k[0]) << 24;
    234       a += ((uint32_t) k[1]) << 16;
    235       a += ((uint32_t) k[2]) << 8;
    236       a += ((uint32_t) k[3]);
    237       b += ((uint32_t) k[4]) << 24;
    238       b += ((uint32_t) k[5]) << 16;
    239       b += ((uint32_t) k[6]) << 8;
    240       b += ((uint32_t) k[7]);
    241       c += ((uint32_t) k[8]) << 24;
    242       c += ((uint32_t) k[9]) << 16;
    243       c += ((uint32_t) k[10]) << 8;
    244       c += ((uint32_t) k[11]);
    245       mix(a,b,c);
    246       length -= 12;
    247       k += 12;
    248     }
    249 
    250     /*-------------------------------- last block: affect all 32 bits of (c) */
    251     switch (length) {
    252       /* all the case statements fall through */
    253     case 12: c+=k[11];
    254     case 11: c += ((uint32_t) k[10]) << 8;
    255     case 10: c += ((uint32_t) k[9]) << 16;
    256     case 9 : c += ((uint32_t) k[8]) << 24;
    257     case 8 : b += k[7];
    258     case 7 : b += ((uint32_t) k[6]) << 8;
    259     case 6 : b += ((uint32_t) k[5]) << 16;
    260     case 5 : b += ((uint32_t) k[4]) << 24;
    261     case 4 : a += k[3];
    262     case 3 : a += ((uint32_t) k[2]) << 8;
    263     case 2 : a += ((uint32_t) k[1]) << 16;
    264     case 1 : a += ((uint32_t) k[0]) << 24;
    265              break;
    266     case 0 : return c;
    267     }
    268   }
    269 
    270   final(a,b,c);
    271   return c;
    272 }
    273 #else
    274 static uint32_t
    275 RJL3Hash (uint8_t *data, uint32_t length, uint32_t initval)
    276 {
    277   uint32_t a,b,c;                                          /* internal state */
    278   union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
    279 
    280   /* Set up the internal state */
    281   a = b = c = 0xdeadbeef + length + initval;
    282 
    283   u.ptr = data;
    284   if ((u.i & 0x3) == 0) {
    285     const uint32_t *k = ((uint32_t *) data);  /* read 32-bit chunks */
    286     const uint8_t  *k8;
    287 
    288     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
    289     while (length > 12) {
    290       a += k[0];
    291       b += k[1];
    292       c += k[2];
    293       mix(a,b,c);
    294       length -= 12;
    295       k += 3;
    296     }
    297 
    298     /*----------------------------- handle the last (probably partial) block */
    299     /*
    300      * "k[2]&0xffffff" actually reads beyond the end of the string, but
    301      * then masks off the part it's not allowed to read.  Because the
    302      * string is aligned, the masked-off tail is in the same word as the
    303      * rest of the string.  Every machine with memory protection I've seen
    304      * does it on word boundaries, so is OK with this.  But VALGRIND will
    305      * still catch it and complain.  The masking trick does make the hash
    306      * noticably faster for short strings (like English words).
    307      */
    308 #ifndef VALGRIND
    309 
    310     switch (length) {
    311     case 12: c += k[2]; b += k[1]; a += k[0]; break;
    312     case 11: c += k[2] & 0xffffff; b += k[1]; a += k[0]; break;
    313     case 10: c += k[2] & 0xffff; b += k[1]; a += k[0]; break;
    314     case 9 : c += k[2] & 0xff; b += k[1]; a += k[0]; break;
    315     case 8 : b += k[1]; a += k[0]; break;
    316     case 7 : b += k[1] & 0xffffff; a += k[0]; break;
    317     case 6 : b += k[1] & 0xffff; a += k[0]; break;
    318     case 5 : b += k[1] & 0xff; a += k[0]; break;
    319     case 4 : a += k[0]; break;
    320     case 3 : a += k[0] & 0xffffff; break;
    321     case 2 : a += k[0] & 0xffff; break;
    322     case 1 : a += k[0] & 0xff; break;
    323     case 0 : return c;              /* zero length strings require no mixing */
    324     }
    325 
    326 #else /* make valgrind happy */
    327 
    328     k8 = ((const uint8_t *) k);
    329     switch (length) {
    330     case 12: c += k[2]; b += k[1]; a += k[0]; break;
    331     case 11: c += ((uint32_t) k8[10]) << 16;  /* fall through */
    332     case 10: c += ((uint32_t) k8[9]) << 8;    /* fall through */
    333     case 9 : c += k8[8];                   /* fall through */
    334     case 8 : b += k[1]; a += k[0]; break;
    335     case 7 : b += ((uint32_t) k8[6]) << 16;   /* fall through */
    336     case 6 : b += ((uint32_t) k8[5]) << 8;    /* fall through */
    337     case 5 : b += k8[4];                   /* fall through */
    338     case 4 : a += k[0]; break;
    339     case 3 : a += ((uint32_t) k8[2]) << 16;   /* fall through */
    340     case 2 : a += ((uint32_t) k8[1]) << 8;    /* fall through */
    341     case 1 : a += k8[0]; break;
    342     case 0 : return c;
    343     }
    344 
    345 #endif /* !valgrind */
    346 
    347   } else if ((u.i & 0x1) == 0) {
    348     const uint16_t *k = ((uint16_t *) data);  /* read 16-bit chunks */
    349     const uint8_t  *k8;
    350 
    351     /*--------------- all but last block: aligned reads and different mixing */
    352     while (length > 12) {
    353       a += k[0] + (((uint32_t) k[1]) << 16);
    354       b += k[2] + (((uint32_t) k[3]) << 16);
    355       c += k[4] + (((uint32_t) k[5]) << 16);
    356       mix(a,b,c);
    357       length -= 12;
    358       k += 6;
    359     }
    360 
    361     /*----------------------------- handle the last (probably partial) block */
    362     k8 = ((const uint8_t *) k);
    363     switch (length) {
    364     case 12: c += k[4]+(((uint32_t) k[5]) << 16);
    365              b += k[2]+(((uint32_t) k[3]) << 16);
    366              a += k[0]+(((uint32_t) k[1]) << 16);
    367              break;
    368     case 11: c += ((uint32_t) k8[10]) << 16;     /* fall through */
    369     case 10: c += k[4];
    370              b += k[2]+(((uint32_t) k[3]) << 16);
    371              a += k[0]+(((uint32_t) k[1]) << 16);
    372              break;
    373     case 9 : c += k8[8];                      /* fall through */
    374     case 8 : b += k[2]+(((uint32_t) k[3]) << 16);
    375              a += k[0]+(((uint32_t) k[1]) << 16);
    376              break;
    377     case 7 : b += ((uint32_t) k8[6]) << 16;      /* fall through */
    378     case 6 : b += k[2];
    379              a += k[0]+(((uint32_t) k[1]) << 16);
    380              break;
    381     case 5 : b += k8[4];                      /* fall through */
    382     case 4 : a += k[0]+(((uint32_t) k[1]) << 16);
    383              break;
    384     case 3 : a += ((uint32_t) k8[2]) << 16;      /* fall through */
    385     case 2 : a += k[0];
    386              break;
    387     case 1 : a += k8[0];
    388              break;
    389     case 0 : return c;                     /* zero length requires no mixing */
    390     }
    391 
    392   } else {                        /* need to read the key one byte at a time */
    393     const uint8_t *k = data;
    394 
    395     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
    396     while (length > 12) {
    397       a += k[0];
    398       a += ((uint32_t) k[1]) << 8;
    399       a += ((uint32_t) k[2]) << 16;
    400       a += ((uint32_t) k[3]) << 24;
    401       b += k[4];
    402       b += ((uint32_t) k[5]) << 8;
    403       b += ((uint32_t) k[6]) << 16;
    404       b += ((uint32_t) k[7]) << 24;
    405       c += k[8];
    406       c += ((uint32_t) k[9]) << 8;
    407       c += ((uint32_t) k[10]) << 16;
    408       c += ((uint32_t) k[11]) << 24;
    409       mix(a,b,c);
    410       length -= 12;
    411       k += 12;
    412     }
    413 
    414     /*-------------------------------- last block: affect all 32 bits of (c) */
    415     switch (length) {
    416       /* all the case statements fall through */
    417     case 12: c += ((uint32_t) k[11]) << 24;
    418     case 11: c += ((uint32_t) k[10]) << 16;
    419     case 10: c += ((uint32_t) k[9]) << 8;
    420     case 9 : c += k[8];
    421     case 8 : b += ((uint32_t) k[7]) << 24;
    422     case 7 : b += ((uint32_t) k[6]) << 16;
    423     case 6 : b += ((uint32_t) k[5]) << 8;
    424     case 5 : b += k[4];
    425     case 4 : a += ((uint32_t) k[3]) << 24;
    426     case 3 : a += ((uint32_t) k[2]) << 16;
    427     case 2 : a += ((uint32_t) k[1]) << 8;
    428     case 1 : a += k[0];
    429              break;
    430     case 0 : return c;
    431     }
    432   }
    433 
    434   final(a,b,c);
    435   return c;
    436 }
    437 #endif
    438 
    439 #undef hashsize
    440 #undef hashmask
    441 #undef rot
    442 #undef mix
    443 #undef final
    444206
    445207#undef bitsizeof
  • release/3/hashes/trunk/RJMXHash.scm

    r8148 r8575  
    2424--------------------------------------------------------------------
    2525*/
    26 
    27 /*
    28 --------------------------------------------------------------------
    29 mix -- mix 3 32-bit values reversibly.
    30 For every delta with one or two bit set, and the deltas of all three
    31   high bits or all three low bits, whether the original value of a,b,c
    32   is almost all zero or is uniformly distributed,
    33 * If mix() is run forward or backward, at least 32 bits in a,b,c
    34   have at least 1/4 probability of changing.
    35 * If mix() is run forward, every bit of c will change between 1/3 and
    36   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
    37 mix() was built out of 36 single-cycle latency instructions in a
    38   structure that could supported 2x parallelism, like so:
    39       a -= b;
    40       a -= c; x = (c>>13);
    41       b -= c; a ^= x;
    42       b -= a; x = (a<<8);
    43       c -= a; b ^= x;
    44       c -= b; x = (b>>13);
    45       ...
    46   Unfortunately, superscalar Pentiums and Sparcs can't take advantage
    47   of that parallelism. They've also turned some of those single-cycle
    48   latency instructions into multi-cycle latency instructions.  Still,
    49   this is the fastest good hash I could find. There were about 2^^68
    50   to choose from. I only looked at a billion or so.
    51 --------------------------------------------------------------------
    52 */
    53 
    54 #define mix(a, b, c) { \
    55   a -= b; a -= c; a ^= (c >> 13); \
    56   b -= c; b -= a; b ^= (a << 8); \
    57   c -= a; c -= b; c ^= (b >> 13); \
    58   a -= b; a -= c; a ^= (c >> 12);  \
    59   b -= c; b -= a; b ^= (a << 16); \
    60   c -= a; c -= b; c ^= (b >> 5); \
    61   a -= b; a -= c; a ^= (c >> 3);  \
    62   b -= c; b -= a; b ^= (a << 10); \
    63   c -= a; c -= b; c ^= (b >> 15); \
    64 }
    6526
    6627/*
     
    9253*/
    9354
    94 #ifdef C_BIG_ENDIAN
    9555static uint32_t
    96 RJMXHash (uint8_t *data, uint32_t length, uint32_t initval)
     56RJMXHash( uint8_t *data, uint32_t length, uint32_t key )
    9757{
    98    /* Set up the internal state */
    99    uint32_t len = length;
    100    uint8_t *k = data;
    101    uint32_t a = 0x9e3779b9;   /* the golden ratio; an arbitrary value */
    102    uint32_t b = 0x9e3779b9;   /* the golden ratio; an arbitrary value */
    103    uint32_t c = initval;      /* the previous hash value */
     58    /*
     59    --------------------------------------------------------------------
     60    mix -- mix 3 32-bit values reversibly.
     61    For every delta with one or two bit set, and the deltas of all three
     62      high bits or all three low bits, whether the original value of a,b,c
     63      is almost all zero or is uniformly distributed,
     64    * If mix() is run forward or backward, at least 32 bits in a,b,c
     65      have at least 1/4 probability of changing.
     66    * If mix() is run forward, every bit of c will change between 1/3 and
     67      2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
     68    mix() was built out of 36 single-cycle latency instructions in a
     69      structure that could supported 2x parallelism, like so:
     70          a -= b;
     71          a -= c; x = (c>>13);
     72          b -= c; a ^= x;
     73          b -= a; x = (a<<8);
     74          c -= a; b ^= x;
     75          c -= b; x = (b>>13);
     76          ...
     77      Unfortunately, superscalar Pentiums and Sparcs can't take advantage
     78      of that parallelism. They've also turned some of those single-cycle
     79      latency instructions into multi-cycle latency instructions.  Still,
     80      this is the fastest good hash I could find. There were about 2^^68
     81      to choose from. I only looked at a billion or so.
     82    --------------------------------------------------------------------
     83    */
    10484
    105   if (data == NULL) return 0;
     85#   define MIX( a, b, c ) { \
     86        (a) -= (b); (a) -= (c); (a) ^= ((c) >> 13); \
     87        (b) -= (c); (b) -= (a); (b) ^= ((a) << 8); \
     88        (c) -= (a); (c) -= (b); (c) ^= ((b) >> 13); \
     89        (a) -= (b); (a) -= (c); (a) ^= ((c) >> 12); \
     90        (b) -= (c); (b) -= (a); (b) ^= ((a) << 16); \
     91        (c) -= (a); (c) -= (b); (c) ^= ((b) >> 5); \
     92        (a) -= (b); (a) -= (c); (a) ^= ((c) >> 3); \
     93        (b) -= (c); (b) -= (a); (b) ^= ((a) << 10); \
     94        (c) -= (a); (c) -= (b); (c) ^= ((b) >> 15); \
     95        }
    10696
    107    /*---------------------------------------- handle most of the key */
    108    while (len >= 12) {
    109       a += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    110       b += (k[4] + (((uint32_t) k[5]) << 8) + (((uint32_t) k[6]) << 16) + (((uint32_t) k[7]) << 24));
    111       c += (k[8] + (((uint32_t) k[9]) << 8) + (((uint32_t) k[10]) << 16) + (((uint32_t) k[11]) << 24));
    112       mix (a, b, c);
    113       k += 12;
    114       len -= 12;
    115    }
     97#   define GOLDEN_RATIO 0x9E3779B9
    11698
    117    /*------------------------------------- handle the last 11 bytes */
    118    c += length;
    119    switch (len) {
    120      /* all the case statements fall through */
    121    case 11: c += (((uint32_t) k[10]) << 24);
    122    case 10: c += (((uint32_t) k[9]) << 16);
    123    case 9 : c += (((uint32_t) k[8]) << 8);
    124       /* the first byte of c is reserved for the length */
    125    case 8 : b += (((uint32_t) k[7]) << 24);
    126    case 7 : b += (((uint32_t) k[6]) << 16);
    127    case 6 : b += (((uint32_t) k[5]) << 8);
    128    case 5 : b += k[4];
    129    case 4 : a += (((uint32_t) k[3]) << 24);
    130    case 3 : a += (((uint32_t) k[2]) << 16);
    131    case 2 : a += (((uint32_t) k[1]) << 8);
    132    case 1 : a += k[0];
    133      /* case 0: nothing left to add */
    134    }
    135    mix (a, b, c);
     99    if (! key) key = length;
    136100
    137    /*-------------------------------------------- report the result */
    138    return c;
     101    if (data) {
     102        uint32_t a, b;
     103
     104        /* Set up the internal state */
     105        a = b = GOLDEN_RATIO;    /* an arbitrary value */
     106
     107        /*---------------------------------------- handle most of the key */
     108        while (length >= 12) {
     109              a += *((uint32_t *) (data + 0));
     110              b += *((uint32_t *) (data + 4));
     111            key += *((uint32_t *) (data + 8));
     112            MIX( a, b, key );
     113            data += 12;
     114            length -= 12;
     115        }
     116
     117        /*------------------------------------- handle the last 11 bytes */
     118        switch (length) {
     119          /* all the case statements fall through */
     120        case 11: key += ((uint32_t) data[ 10 ]) << 24;
     121        case 10: key += ((uint32_t) data[ 9 ]) << 16;
     122        case 9 : key += ((uint32_t) data[ 8 ]) << 8;
     123          /* the first byte of key is reserved for the length */
     124        case 8 :   b += ((uint32_t) data[ 7 ]) << 24;
     125        case 7 :   b += ((uint32_t) data[ 6 ]) << 16;
     126        case 6 :   b += ((uint32_t) data[ 5 ]) << 8;
     127        case 5 :   b +=  (uint32_t) data[ 4 ];
     128        case 4 :   a += ((uint32_t) data[ 3 ]) << 24;
     129        case 3 :   a += ((uint32_t) data[ 2 ]) << 16;
     130        case 2 :   a += ((uint32_t) data[ 1 ]) << 8;
     131        case 1 :   a +=  (uint32_t) data[ 0 ];
     132          /* case 0: nothing left to add */
     133        }
     134
     135        MIX( a, b, key );
     136    }
     137
     138    /*-------------------------------------------- report the result */
     139    return key;
     140
     141# undef MIX
    139142}
    140 #else
    141 static uint32_t
    142 RJMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    143 {
    144    /* Set up the internal state */
    145    uint32_t len = length;
    146    uint8_t *k = data;
    147    uint32_t a = 0x9e3779b9;   /* the golden ratio; an arbitrary value */
    148    uint32_t b = 0x9e3779b9;   /* the golden ratio; an arbitrary value */
    149    uint32_t c = initval;      /* the previous hash value */
    150 
    151   if (data == NULL) return 0;
    152 
    153    /*---------------------------------------- handle most of the key */
    154    if (((uint32_t) k) & 3) {
    155       while (len >= 12) { /* unaligned */
    156          a += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    157          b += (k[4] + (((uint32_t) k[5]) << 8) + (((uint32_t) k[6]) << 16) + (((uint32_t) k[7]) << 24));
    158          c += (k[8] + (((uint32_t) k[9]) << 8) + (((uint32_t) k[10]) << 16) + (((uint32_t) k[11]) << 24));
    159          mix (a, b, c);
    160          k += 12;
    161          len -= 12;
    162       }
    163    } else {
    164       while (len >= 12) { /* aligned */
    165          a += *((uint32_t *) (k + 0));
    166          b += *((uint32_t *) (k + 4));
    167          c += *((uint32_t *) (k + 8));
    168          mix (a, b, c);
    169          k += 12;
    170          len -= 12;
    171       }
    172    }
    173 
    174    /*------------------------------------- handle the last 11 bytes */
    175    c += length;
    176    switch (len) {
    177      /* all the case statements fall through */
    178    case 11: c+=(((uint32_t) k[10]) << 24);
    179    case 10: c += (((uint32_t) k[9]) << 16);
    180    case 9 : c += (((uint32_t) k[8]) << 8);
    181       /* the first byte of c is reserved for the length */
    182    case 8 : b += (((uint32_t) k[7]) << 24);
    183    case 7 : b += (((uint32_t) k[6]) << 16);
    184    case 6 : b += (((uint32_t) k[5]) << 8);
    185    case 5 : b += k[4];
    186    case 4 : a += (((uint32_t) k[3]) << 24);
    187    case 3 : a += (((uint32_t) k[2]) << 16);
    188    case 2 : a += (((uint32_t) k[1]) << 8);
    189    case 1 : a += k[0];
    190      /* case 0: nothing left to add */
    191    }
    192    mix (a, b, c);
    193 
    194    /*-------------------------------------------- report the result */
    195    return c;
    196 }
    197 #endif
    198 
    199 #undef mix
    200143
    201144#undef bitsizeof
  • release/3/hashes/trunk/RSHash.scm

    r8148 r8575  
    4141
    4242static uint32_t
    43 RSHash (uint8_t *data, uint32_t len, uint32_t initval)
     43RSHash(uint8_t *data, uint32_t length, uint32_t key )
    4444{
    45    uint32_t b    = 378551;
    46    uint32_t a    = 63689;
    47    uint32_t hash = initval;
    48    uint32_t i;
     45#   define A 63689U
     46#   define B 378551U
    4947
    50    if (data == NULL) return 0;
     48    if (data) {
     49        uint32_t a = A;
     50        for ( ; length; data++, length--) {
     51            key = key * a + ((uint32_t) *data);
     52            a *= B;
     53        }
     54    }
    5155
    52    for (i = 0; i < len; data++, i++) {
    53       hash = hash * a + (*data);
    54       a *= b;
    55    }
     56    return key;
    5657
    57    return hash;
     58#   undef B
     59#   undef A
    5860}
    5961
  • release/3/hashes/trunk/SDBMHash.scm

    r8148 r8575  
    2424
    2525static uint32_t
    26 SDBMHash (uint8_t *data, uint32_t len, uint32_t initval)
     26SDBMHash( uint8_t *data, uint32_t length, uint32_t key )
    2727{
    28    uint32_t hash = initval;
    29    uint32_t i;
     28    if (data) {
     29        for ( ; length; data++, length--) {
     30            key = ((uint32_t) *data) + (key << 6) + (key << 16) - key;
     31        }
     32    }
    3033
    31    if (data == NULL) return 0;
    32 
    33    for (i = 0; i < len; data++, i++) {
    34       hash = (*data) + (hash << 6) + (hash << 16) - hash;
    35    }
    36 
    37    return hash;
     34    return key;
    3835}
    3936
  • release/3/hashes/trunk/TWMGMXHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 #define mix(key) { \
    21    key = (key + 0x7ED55D16) + (key << 12); \
    22    key = (key ^ 0xC761C23C) ^ (key >> 19); \
    23    key = (key + 0x165667B1) + (key << 5); \
    24    key = (key + 0xD3A2646C) ^ (key << 9); \
    25    key = (key + 0xFD7046C5) + (key << 3); \
    26    key = (key ^ 0xB55A4F09) ^ (key >> 16); \
     20static uint32_t
     21TWMGMXHash( uint8_t *data, uint32_t length, uint32_t key )
     22{
     23    /* Merge 32 bit Mix Function */
     24#   define MIX( key ) { \
     25        (key) = ((key) + 0x7ED55D16) + ((key) << 12); \
     26        (key) = ((key) ^ 0xC761C23C) ^ ((key) >> 19); \
     27        (key) = ((key) + 0x165667B1) + ((key) << 5); \
     28        (key) = ((key) + 0xD3A2646C) ^ ((key) << 9); \
     29        (key) = ((key) + 0xFD7046C5) + ((key) << 3); \
     30        (key) = ((key) ^ 0xB55A4F09) ^ ((key) >> 16); \
     31        }
     32
     33    if (data) {
     34
     35        while (length >= sizeof( uint32_t )) {
     36            key += *((uint32_t *) data);
     37            MIX( key );
     38            data += sizeof( uint32_t );
     39            length -= sizeof( uint32_t );
     40        }
     41
     42        switch (length) {
     43          /* all the case statements fall through */
     44        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     45        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     46        case 1 : key += (uint32_t) data[ 0 ];
     47          /* case 0: nothing left to add */
     48        }
     49        MIX( key );
     50    }
     51
     52    return key;
     53
     54#   undef MIX
    2755}
    28 
    29 #ifdef C_BIG_ENDIAN
    30 static uint32_t
    31 TWMGMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    32 {
    33    uint8_t *k = data;
    34    uint32_t len = length;
    35    uint32_t key = initval;
    36 
    37   if (data == NULL) return 0;
    38 
    39    while (len >= 4) {
    40       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    41       mix (key);
    42       k += 4;
    43       len -= 4;
    44    }
    45 
    46    switch (len) {
    47      /* all the case statements fall through */
    48    case 3 : key += (((uint32_t) k[2]) << 16);
    49    case 2 : key += (((uint32_t) k[1]) << 8);
    50    case 1 : key += k[0];
    51      /* case 0: nothing left to add */
    52    }
    53    mix (key);
    54 
    55    return key;
    56 }
    57 #else
    58 static uint32_t
    59 TWMGMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    60 {
    61    uint8_t *k = data;
    62    uint32_t len = length;
    63    uint32_t key = initval;
    64 
    65   if (data == NULL) return 0;
    66 
    67    if (((uint32_t) k) & 3) {
    68       while (len >= 4) {  /* unaligned */
    69         key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    70         mix (key);
    71         k += 4;
    72         len -= 4;
    73       }
    74    } else {
    75       while (len >= 4) {  /* aligned */
    76         key += *((uint32_t *) (k + 0));
    77         mix (key);
    78         k += 4;
    79         len -= 4;
    80       }
    81    }
    82 
    83    switch (len) {
    84      /* all the case statements fall through */
    85    case 3 : key += (((uint32_t) k[2]) << 16);
    86    case 2 : key += (((uint32_t) k[1]) << 8);
    87    case 1 : key += k[0];
    88      /* case 0: nothing left to add */
    89    }
    90    mix (key);
    91 
    92    return key;
    93 }
    94 #endif
    95 
    96 #undef mix
    9756
    9857#undef bitsizeof
  • release/3/hashes/trunk/TWMXHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 /* Thomas Wang's 32 bit Mix Function */
     20static uint32_t
     21TWMXHash( uint8_t *data, uint32_t length, uint32_t key )
     22{
     23    /* Thomas Wang's 32 bit Mix Function */
     24# ifdef C_SIXTY_FOUR
     25#   define MIX( key ) { \
     26        (key) = ~(key) + ((key) << 21); \
     27        (key) ^= (key) >> 24; \
     28        (key) += ((key) << 3) + ((key) << 8); \
     29        (key) ^= (key) >> 14; \
     30        (key) += ((key) << 2) + ((key) << 4); \
     31        (key) ^= (key) >> 28; \
     32        (key) += (key) << 31; \
     33        }
     34# else
     35#   define MIX( key ) { \
     36        (key) += ~((key) << 15); \
     37        (key) ^= ((key) & 0x7FFFFFFF) >> 10; \
     38        (key) += (key) << 3; \
     39        (key) ^= ((key) & 0x7FFFFFFF) >> 6; \
     40        (key) += ~((key) << 11); \
     41        (key) ^= ((key) & 0x7FFFFFFF) >> 16; \
     42        }
     43# endif
    2144
    22 #define mix(key) { \
    23   key += ~(key << 15); \
    24   key ^= ((key & 0x7FFFFFFF) >> 10); \
    25   key += (key << 3); \
    26   key ^= ((key & 0x7FFFFFFF) >> 6); \
    27   key += ~(key << 11); \
    28   key ^= ((key & 0x7FFFFFFF) >> 16); \
     45    if (data) {
     46
     47# ifdef C_SIXTY_FOUR
     48        uint64_t hash = key;
     49        while (length >= sizeof( uint64_t )) {
     50            hash += *((uint64_t *) data);
     51            MIX( hash );
     52            data += sizeof( uint64_t );
     53            length -= sizeof( uint64_t );
     54        }
     55
     56        switch (length) {
     57          /* all the case statements fall through */
     58        case 7 : hash += (((uint64_t) data[ 6 ]) << 48);
     59        case 6 : hash += (((uint64_t) data[ 5 ]) << 40);
     60        case 5 : hash += (((uint64_t) data[ 4 ]) << 32);
     61        case 4 : hash += (((uint64_t) data[ 3 ]) << 24);
     62        case 3 : hash += (((uint64_t) data[ 2 ]) << 16);
     63        case 2 : hash += (((uint64_t) data[ 1 ]) << 8);
     64        case 1 : hash += (uint64_t) data[ 0 ];
     65          /* case 0: nothing left to add */
     66        }
     67        MIX( hash );
     68        key = (uint32_t) hash;
     69# else
     70        while (length >= sizeof( uint32_t )) {
     71            key += *((uint32_t *) data);
     72            MIX( key );
     73            data += sizeof( uint32_t );
     74            length -= sizeof( uint32_t );
     75        }
     76
     77        switch (length) {
     78          /* all the case statements fall through */
     79        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     80        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     81        case 1 : key += (uint32_t) data[ 0 ];
     82          /* case 0: nothing left to add */
     83        }
     84        MIX( key );
     85# endif
     86    }
     87
     88    return key;
     89
     90#   undef MIX
    2991}
    30 
    31 #if 0
    32 #ifdef C_SIXTY_FOUR
    33 #define mix64shift(key) { \
    34   key = (~key) + (key << 21); \
    35   key = key ^ (key >> 24); \
    36   key = (key + (key << 3)) + (key << 8); \
    37   key = key ^ (key >> 14); \
    38   key = (key + (key << 2)) + (key << 4); \
    39   key = key ^ (key >> 28); \
    40   key = key + (key << 31); \
    41 }
    42 
    43 #define mix6432shift(key) { \
    44   key = (~key) + (key << 18); \
    45   key = key ^ (key >> 31); \
    46   key = key * 21; \
    47   key = key ^ (key >> 11); \
    48   key = key + (key << 6); \
    49   key = key ^ (key >> 22); \
    50 }
    51 #endif
    52 #endif
    53 
    54 #ifdef C_BIG_ENDIAN
    55 static uint32_t
    56 TWMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    57 {
    58    uint8_t *k = data;
    59    uint32_t len = length;
    60    uint32_t key = initval;
    61 
    62   if (data == NULL) return 0;
    63 
    64    while (len >= 4) {
    65       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    66       mix (key);
    67       k += 4;
    68       len -= 4;
    69    }
    70 
    71    switch (len) {
    72      /* all the case statements fall through */
    73    case 3 : key += (((uint32_t) k[2]) << 16);
    74    case 2 : key += (((uint32_t) k[1]) << 8);
    75    case 1 : key += k[0];
    76      /* case 0: nothing left to add */
    77    }
    78    mix (key);
    79 
    80    return key;
    81 }
    82 #else
    83 static uint32_t
    84 TWMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    85 {
    86    uint8_t *k = data;
    87    uint32_t len = length;
    88    uint32_t key = initval;
    89 
    90   if (data == NULL) return 0;
    91 
    92    if (((uint32_t) k) & 3) {
    93       while (len >= 4) {  /* unaligned */
    94         key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    95         mix (key);
    96         k += 4;
    97         len -= 4;
    98       }
    99    } else {
    100       while (len >= 4) {  /* aligned */
    101         key += *((uint32_t *) (k + 0));
    102         mix (key);
    103         k += 4;
    104         len -= 4;
    105       }
    106    }
    107 
    108    switch (len) {
    109      /* all the case statements fall through */
    110    case 3 : key += (((uint32_t) k[2]) << 16);
    111    case 2 : key += (((uint32_t) k[1]) << 8);
    112    case 1 : key += k[0];
    113      /* case 0: nothing left to add */
    114    }
    115    mix (key);
    116 
    117    return key;
    118 }
    119 #endif
    120 
    121 #undef mix
    122 
    123 #if 0
    124 #ifdef C_SIXTY_FOUR
    125 # undef mix64shift
    126 # undef mix6432shift
    127 #endif
    128 #endif
    12992
    13093#undef bitsizeof
  • release/3/hashes/trunk/TWSHMLMXHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 #define mix(key) { \
    21   key = (key ^ 61) ^ (key >> 16); \
    22   key = key + (key << 3); \
    23   key = key ^ (key >> 4); \
    24   key = key * 0x27D4EB2D; \
    25   key = key ^ (key >> 15); \
     20static uint32_t
     21TWSHMLMXHash( uint8_t *data, uint32_t length, uint32_t key )
     22{
     23    /* Shift-Multiply 32 bit Mix Function */
     24#   define MIX( key ) { \
     25        (key) = ((key) ^ 61) ^ ((key) >> 16); \
     26        (key) = (key) + ((key) << 3); \
     27        (key) = (key) ^ ((key) >> 4); \
     28        (key) = (key) * 0x27D4EB2D; \
     29        (key) = (key) ^ ((key) >> 15); \
     30        }
     31
     32    if (data) {
     33
     34        while (length >= sizeof( uint32_t )) {
     35            key += *((uint32_t *) data);
     36            MIX( key );
     37            data += sizeof( uint32_t );
     38            length -= sizeof( uint32_t );
     39        }
     40
     41        switch (length) {
     42          /* all the case statements fall through */
     43        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     44        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     45        case 1 : key += (uint32_t) data[ 0 ];
     46          /* case 0: nothing left to add */
     47        }
     48        MIX( key );
     49    }
     50
     51    return key;
     52
     53#   undef MIX
    2654}
    27 
    28 #ifdef C_BIG_ENDIAN
    29 static uint32_t
    30 TWSHMLMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    31 {
    32    uint8_t *k = data;
    33    uint32_t len = length;
    34    uint32_t key = initval;
    35 
    36   if (data == NULL) return 0;
    37 
    38    while (len >= 4) {
    39       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    40       mix (key);
    41       k += 4;
    42       len -= 4;
    43    }
    44 
    45    switch (len) {
    46      /* all the case statements fall through */
    47    case 3 : key += (((uint32_t) k[2]) << 16);
    48    case 2 : key += (((uint32_t) k[1]) << 8);
    49    case 1 : key += k[0];
    50      /* case 0: nothing left to add */
    51    }
    52    mix (key);
    53 
    54    return key;
    55 }
    56 #else
    57 static uint32_t
    58 TWSHMLMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    59 {
    60    uint8_t *k = data;
    61    uint32_t len = length;
    62    uint32_t key = initval;
    63 
    64   if (data == NULL) return 0;
    65 
    66    if (((uint32_t) k) & 3) {
    67       while (len >= 4) {  /* unaligned */
    68         key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    69         mix (key);
    70         k += 4;
    71         len -= 4;
    72       }
    73    } else {
    74       while (len >= 4) {  /* aligned */
    75         key += *((uint32_t *) (k + 0));
    76         mix (key);
    77         k += 4;
    78         len -= 4;
    79       }
    80    }
    81 
    82    switch (len) {
    83      /* all the case statements fall through */
    84    case 3 : key += (((uint32_t) k[2]) << 16);
    85    case 2 : key += (((uint32_t) k[1]) << 8);
    86    case 1 : key += k[0];
    87      /* case 0: nothing left to add */
    88    }
    89    mix (key);
    90 
    91    return key;
    92 }
    93 #endif
    94 
    95 #undef mix
    9655
    9756#undef bitsizeof
  • release/3/hashes/trunk/TWSHMXHash.scm

    r8148 r8575  
    1818#include "hashes.h"
    1919
    20 #define mix(key) { \
    21   key = ~key + (key << 15); \
    22   key = key ^ (key >> 12); \
    23   key = key + (key << 2); \
    24   key = key ^ (key >> 4); \
    25   key = key * 2057; \
    26   key = key ^ (key >> 16); \
     20static uint32_t
     21TWSHMXHash( uint8_t *data, uint32_t length, uint32_t key )
     22{
     23    /* Shift 32 bit Mix Function */
     24#   define MIX( key ) { \
     25        (key) = ~(key) + ((key) << 15); \
     26        (key) = (key) ^ ((key) >> 12); \
     27        (key) = (key) + ((key) << 2); \
     28        (key) = (key) ^ ((key) >> 4); \
     29        (key) = (key) * 2057; \
     30        (key) = (key) ^ ((key) >> 16); \
     31      }
     32
     33    if (data) {
     34
     35        while (length >= sizeof( uint32_t )) {
     36            key += *((uint32_t *) data);
     37            MIX( key );
     38            data += sizeof( uint32_t );
     39            length -= sizeof( uint32_t );
     40        }
     41
     42        switch (length) {
     43          /* all the case statements fall through */
     44        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     45        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     46        case 1 : key += (uint32_t) data[ 0 ];
     47          /* case 0: nothing left to add */
     48        }
     49        MIX( key );
     50    }
     51
     52    return key;
     53
     54#   undef MIX
    2755}
    28 
    29 #ifdef C_BIG_ENDIAN
    30 static uint32_t
    31 TWSHMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    32 {
    33    uint8_t *k = data;
    34    uint32_t len = length;
    35    uint32_t key = initval;
    36 
    37   if (data == NULL) return 0;
    38 
    39    while (len >= 4) {
    40       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    41       mix (key);
    42       k += 4;
    43       len -= 4;
    44    }
    45 
    46    switch (len) {
    47      /* all the case statements fall through */
    48    case 3 : key += (((uint32_t) k[2]) << 16);
    49    case 2 : key += (((uint32_t) k[1]) << 8);
    50    case 1 : key += k[0];
    51      /* case 0: nothing left to add */
    52    }
    53    mix (key);
    54 
    55    return key;
    56 }
    57 #else
    58 static uint32_t
    59 TWSHMXHash (uint8_t *data, uint32_t length, uint32_t initval)
    60 {
    61    uint8_t *k = data;
    62    uint32_t len = length;
    63    uint32_t key = initval;
    64 
    65   if (data == NULL) return 0;
    66 
    67    if (((uint32_t) k) & 3) {
    68       while (len >= 4) {  /* unaligned */
    69         key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    70         mix (key);
    71         k += 4;
    72         len -= 4;
    73       }
    74    } else {
    75       while (len >= 4) {  /* aligned */
    76         key += *((uint32_t *) (k + 0));
    77         mix (key);
    78         k += 4;
    79         len -= 4;
    80       }
    81    }
    82 
    83    switch (len) {
    84      /* all the case statements fall through */
    85    case 3 : key += (((uint32_t) k[2]) << 16);
    86    case 2 : key += (((uint32_t) k[1]) << 8);
    87    case 1 : key += k[0];
    88      /* case 0: nothing left to add */
    89    }
    90    mix (key);
    91 
    92    return key;
    93 }
    94 #endif
    95 
    96 #undef mix
    9756
    9857#undef bitsizeof
  • release/3/hashes/trunk/TWUserMixHash-support.scm

    r8297 r8575  
    1717#include "hashes.h"
    1818
    19 #define MIXER(key) {\
    20     char numbuf[C_SIZEOF_FLONUM];\
    21     C_word *ptr = (C_word *) &numbuf;\
    22     C_word num = C_unsigned_int_to_num (&ptr, key);\
    23     C_word res;\
    24     C_save (num);\
    25     res = C_callback (mixer, 1);\
    26     key = (uint32_t) C_num_to_unsigned_int (res);\
     19static uint32_t
     20TWUserMixHash( uint8_t *data, uint32_t length, uint32_t key, C_word mixer )
     21{
     22    /* User 32 bit Mix Function */
     23#   define MIX( key ) { \
     24        char numbuf[ C_SIZEOF_FLONUM ]; \
     25        C_word *ptr = (C_word *) &numbuf; \
     26        C_word num = C_unsigned_int_to_num( &ptr, (key) ); \
     27        C_save( num ); \
     28        num = C_callback( mixer, 1 ); \
     29        (key) = (uint32_t) C_num_to_unsigned_int( num ); \
     30        }
     31
     32    if (data) {
     33
     34        while (length >= sizeof( uint32_t )) {
     35            key += *((uint32_t *) data);
     36            MIX( key );
     37            data += sizeof( uint32_t );
     38            length -= sizeof( uint32_t );
     39        }
     40
     41        switch (length) {
     42          /* all the case statements fall through */
     43        case 3 : key += (((uint32_t) data[ 2 ]) << 16);
     44        case 2 : key += (((uint32_t) data[ 1 ]) << 8);
     45        case 1 : key += (uint32_t) data[ 0 ];
     46          /* case 0: nothing left to add */
     47        }
     48        MIX( key );
    2749    }
    2850
    29 #ifdef C_BIG_ENDIAN
    30 static uint32_t
    31 TWUserMixHash (uint8_t *data, uint32_t length, uint32_t key, void * mixer_data)
    32 {
    33   uint8_t *k = data;
    34   uint32_t len = length;
    35   C_word mixer = (C_word) ((C_SCHEME_BLOCK *) (((char *) mixer_data) - sizeof (C_header)));
     51    return key;
    3652
    37   if (C_header_bits (mixer) != C_CLOSURE_TYPE) {
    38     C_printf ("Error: (TWUserMixHash) invalid mix procedure: not a closure");
    39     return 0;
    40   }
    41 
    42   if (data == NULL) return 0;
    43 
    44   while (len >= 4) {
    45     key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    46     MIXER (key);
    47     k += 4;
    48     len -= 4;
    49   }
    50 
    51   switch (len) {
    52     /* all the case statements fall through */
    53   case 3 : key += (((uint32_t) k[2]) << 16);
    54   case 2 : key += (((uint32_t) k[1]) << 8);
    55   case 1 : key += k[0];
    56     /* case 0: nothing left to add */
    57   }
    58   MIXER (key);
    59 
    60   return key;
     53#   undef MIX
    6154}
    62 #else
    63 static uint32_t
    64 TWUserMixHash (uint8_t *data, uint32_t length, uint32_t key, void * mixer_data)
    65 {
    66   uint8_t *k = data;
    67   uint32_t len = length;
    68   C_word mixer = (C_word) ((C_SCHEME_BLOCK *) (((char *) mixer_data) - sizeof (C_header)));
    69 
    70   if (C_header_bits (mixer) != C_CLOSURE_TYPE) {
    71     C_printf ("Error: (TWUserMixHash) invalid mix procedure: not a closure");
    72     return 0;
    73   }
    74 
    75   if (data == NULL) return 0;
    76 
    77   if (((uint32_t) k) & 3) {
    78     while (len >= 4) {  /* unaligned */
    79       key += (k[0] + (((uint32_t) k[1]) << 8) + (((uint32_t) k[2]) << 16) + (((uint32_t) k[3]) << 24));
    80       MIXER (key);
    81       k += 4;
    82       len -= 4;
    83     }
    84   } else {
    85     while (len >= 4) {  /* aligned */
    86       key += *((uint32_t *) (k + 0));
    87       MIXER (key);
    88       k += 4;
    89       len -= 4;
    90     }
    91   }
    92 
    93   switch (len) {
    94    /* all the case statements fall through */
    95   case 3 : key += (((uint32_t) k[2]) << 16);
    96   case 2 : key += (((uint32_t) k[1]) << 8);
    97   case 1 : key += k[0];
    98    /* case 0: nothing left to add */
    99   }
    100   MIXER (key);
    101 
    102   return key;
    103 }
    104 #endif
    10555
    10656#undef bitsizeof
     
    11363                       "TWUserMixHash" scheme-pointer unsigned-integer32
    11464                                       unsigned-integer32
    115                                        nonnull-scheme-pointer))
     65                                       scheme-object))
  • release/3/hashes/trunk/hashes-eggdoc.scm

    r8297 r8575  
    293293
    294294  (history
     295    (version "2.3" "Made little & big endian hashing equivalent. Very minor speed-up. Dropped use of \"iset\".")
    295296    (version "2.2" "Added Rabin-Karp string hash search, TWUserMixHash.")
    296297    (version "2.105" "Added TWSHMXHash, TWSHMLMXHash, TWMGMXHash.")
  • release/3/hashes/trunk/hashes.html

    r8297 r8575  
    355355<h3>Version</h3>
    356356<ul>
    357 <li>2.106 Added Rabin-Karp string hash search, TWUserMixHash.</li>
     357<li>2.3 Made little &amp; big endian hashing equivalent. Very minor speed-up. Dropped use of &quot;iset&quot;.</li>
     358<li>2.2 Added Rabin-Karp string hash search, TWUserMixHash.</li>
    358359<li>2.105 Added TWSHMXHash, TWSHMLMXHash, TWMGMXHash.</li>
    359360<li>2.104 Added make-fixnum-bounded-hash.</li>
  • release/3/hashes/trunk/hashes.meta

    r8297 r8575  
    55 (license "BSD")
    66 (category crypt)
    7  (needs misc-extn miscmacros mathh message-digest box crc iset)
     7 (needs misc-extn miscmacros mathh message-digest box crc)
    88 (author "Kon Lovett")
    99 (egg "hashes.egg")
  • release/3/hashes/trunk/hashes.setup

    r8297 r8575  
    22
    33(required-extension-version
    4   'iset                   "1.4"
    54  'crc                    "1.1"
    65  'box                    "1.8"
  • release/3/hashes/trunk/rabin-karp.scm

    r8297 r8575  
    33
    44(use srfi-1 srfi-13 srfi-69)
    5 (use iset)
    65
    76(eval-when (compile)
     
    2221;;;
    2322
    24 (define (check-procedure loc obj)
     23(define-inline (check-procedure loc obj)
    2524  (##sys#check-closure obj loc) )
    2625
    27 (define (check-string loc obj)
     26(define-inline (check-string loc obj)
    2827  (##sys#check-string obj loc) )
    2928
     
    4948      ; a match.
    5049      [substrs-lens
    51         (iset->list (apply iset
    52                            (map (lambda (x)
    53                                   (check-string 'make-rabin-karp-string-search x)
    54                                   (string-length x) )
    55                                 substrs)))]
     50        (sort! (map (lambda (x)
     51                      (check-string 'make-rabin-karp-string-search x)
     52                      (string-length x) )
     53                    substrs)
     54               <) ]
    5655      ; Search string lookup table
    5756      [substrs-tbl
     
    6362    ; string in the target string, otherwise #f.
    6463    (lambda (str #!optional (start 0) (end (string-length str)))
    65       ; Limit length to search.
    66       (let* (
     64      (let (
    6765          ; Any matching search string at this position?
    6866          [match@
     
    8381        ; Any matching search string?
    8482        (let loop ([pos start])
    85           (cond [(= pos end)    #f]
    86                 [(match@ pos)   => identity]
    87                 [else           (loop (+ pos 1)) ] ) ) ) ) ) )
     83          (and (< pos end)
     84               (or (match@ pos)
     85                   (loop (+ pos 1)) ) ) ) ) ) ) )
  • release/3/hashes/trunk/tests/hashes-test.scm

    r8297 r8575  
    44(use hashes)
    55(use rabin-karp)
     6(use srfi-1)
    67
    78;;;
     
    1415;;;
    1516
    16 (define-constant TSTSTR "The large brown fox jumped over the lazy dog.")
    17 (define TSTSTR-LEN (string-length TSTSTR))
    18 (define TSTSTR-HALF-LEN (fx/ TSTSTR-LEN 2))
     17(define TSTSTR "The large brown fox jumped over the lazy dog.")
     18
     19(define TSTSTR-LEN        (string-length TSTSTR))
     20(define TSTSTR-HALF-LEN   (fx/ TSTSTR-LEN 2))
    1921
    2022;;;
     
    2224(define-test hashes-test "Hash Functions"
    2325
    24         (test/case "Hash-prim"
    25 
    26                 (expect-success "RJMXHash" (RJMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    27                 (expect-success "TWMXHash" (TWMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    28                 (expect-success "TWSHMXHash" (TWSHMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    29                 (expect-success "TWSHMLMXHash" (TWSHMLMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    30                 (expect-success "TWMGMXHash" (TWMGMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    31                 (expect-success "RSHash" (RSHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    32                 (expect-success "JSHash" (JSHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    33                 (expect-success "PJWHash" (PJWHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    34                 (expect-success "ELFHash" (ELFHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    35                 (expect-success "BKDRHash" (BKDRHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    36                 (expect-success "SDBMHash" (SDBMHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    37                 (expect-success "DJBHash" (DJBHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    38                 (expect-success "NDJBHash" (NDJBHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    39                 (expect-success "DEKHash" (DEKHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    40                 (expect-success "APHash" (APHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    41                 (expect-success "CRCHash" (CRCHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    42                 (expect-success "PHSFHash" (PHSFHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    43                 (expect-success "FNVHash" (FNVHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    44                 (expect-success "FNVAHash" (FNVAHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    45                 (expect-success "BRPHash" (BRPHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    46                 (expect-success "PYHash" (PYHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    47                 (expect-success "RJL3Hash" (RJL3Hash-prim TSTSTR TSTSTR-HALF-LEN 0))
    48                 (expect-success "ISPLHash" (ISPLHash-prim TSTSTR TSTSTR-HALF-LEN 0))
    49         )
    50 
    51         (test/case "Hash"
     26        (test/suite "Hash-prim Half Length"
     27
     28                (expect-eqv "RJMXHash"      1495738488 (RJMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     29                (expect-eqv "TWMXHash"      1783737257 (TWMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     30                (expect-eqv "TWSHMXHash"    4294724170 (TWSHMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     31                (expect-eqv "TWSHMLMXHash"  3316553819 (TWSHMLMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     32                (expect-eqv "TWMGMXHash"    3799230039 (TWMGMXHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     33                (expect-eqv "RSHash"        561364390  (RSHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     34                (expect-eqv "JSHash"        1096595314 (JSHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     35                (expect-eqv "PJWHash"       11905      (PJWHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     36                (expect-eqv "ELFHash"       125889045  (ELFHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     37                (expect-eqv "BKDRHash"      2233812262 (BKDRHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     38                (expect-eqv "SDBMHash"      1850315706 (SDBMHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     39                (expect-eqv "DJBHash"       664891301  (DJBHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     40                (expect-eqv "NDJBHash"      786919305  (NDJBHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     41                (expect-eqv "DEKHash"       4159618807 (DEKHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     42                (expect-eqv "APHash"        3373256484 (APHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     43                (expect-eqv "CRCHash"       4140400781 (CRCHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     44                (expect-eqv "PHSFHash"      4232571984 (PHSFHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     45                (expect-eqv "FNVHash"       2129953783 (FNVHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     46                (expect-eqv "FNVAHash"      1173052123 (FNVAHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     47                (expect-eqv "BRPHash"       1793202933 (BRPHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     48                (expect-eqv "PYHash"        10752      (PYHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     49                (expect-eqv "RJL3Hash"      1304064403  (RJL3Hash-prim TSTSTR TSTSTR-HALF-LEN 0))
     50                (expect-eqv "ISPLHash"      2015390325 (ISPLHash-prim TSTSTR TSTSTR-HALF-LEN 0))
     51        )
     52
     53        (test/suite "Hash Full Length"
    5254
    5355                (expect-eqv "RJMXHash" (RJMXHash-prim TSTSTR TSTSTR-LEN 0) (RJMXHash TSTSTR))
     
    7678        )
    7779
    78         (test/case "Length Arg"
     80        (test/suite "Hash Length Arg"
    7981
    8082                (expect-eqv "RJMXHash" (RJMXHash-prim TSTSTR TSTSTR-HALF-LEN 0) (RJMXHash TSTSTR TSTSTR-HALF-LEN))
     
    103105        )
    104106
    105         (test/case "Digest"
     107        (test/suite "Digest"
    106108
    107109                (expect-success "RJMXHash" (RJMXHash:digest TSTSTR))
     
    151153)
    152154
     155;; This tests whether memory is being corrupted
     156;; There was a problem w/ syntax-case & RJL3Hash
     157
    153158(define-test hashes-random-test "RJL3Hash Idempotent?"
    154         (initial
    155           (define val (RJL3Hash-prim TSTSTR TSTSTR-LEN 0)) )
    156 
    157   (expect-eqv "1" val (RJL3Hash TSTSTR))
    158   (expect-eqv "2" val (RJL3Hash TSTSTR))
    159   (expect-eqv "3" val (RJL3Hash TSTSTR))
    160   (expect-eqv "4" val (RJL3Hash TSTSTR))
    161   (expect-eqv "5" val (RJL3Hash TSTSTR))
    162   (expect-eqv "6" val (RJL3Hash TSTSTR))
    163   (expect-eqv "7" val (RJL3Hash TSTSTR))
    164   (expect-eqv "8" val (RJL3Hash TSTSTR))
    165   (expect-eqv "9" val (RJL3Hash TSTSTR))
    166 )
    167 
    168 (define-test rabin-karp-test "Rabin-Karp Search"
    169         (initial
    170           (define substrs '("quick" "foo" "brown" "dog" "skasfdskjsalksafnsalsfsdsdjkldsajlfsalsk"))
    171           (define hashp)
    172           (define rksp) )
    173 
    174   (expect-set! hashp (make-fixnum-bounded-hash RJL3Hash-prim))
    175   (expect-set! rksp (make-rabin-karp-string-search substrs string=? hashp))
    176   (expect-success "Without start & end" (rksp TSTSTR))
    177   (expect-success "With start & end" (rksp TSTSTR 41 TSTSTR-LEN))
     159  (expect-eqv "1" 2110415480 (RJL3Hash TSTSTR))
     160  (expect-eqv "2" 2110415480 (RJL3Hash TSTSTR))
     161  (expect-eqv "3" 2110415480 (RJL3Hash TSTSTR))
     162  (expect-eqv "4" 2110415480 (RJL3Hash TSTSTR))
     163  (expect-eqv "5" 2110415480 (RJL3Hash TSTSTR))
     164  (expect-eqv "6" 2110415480 (RJL3Hash TSTSTR))
     165  (expect-eqv "7" 2110415480 (RJL3Hash TSTSTR))
     166  (expect-eqv "8" 2110415480 (RJL3Hash TSTSTR))
     167  (expect-eqv "9" 2110415480 (RJL3Hash TSTSTR))
    178168)
    179169
     
    190180    (expect-set! "TWUserMixHash Make" usrmixhsh (receive (make-TWUserMixHash mix #t)))
    191181    (side-effect
    192       (set! hash-prim (car usrmixhsh))
    193       (set! hash (cadr usrmixhsh))
    194       (set! binary:digest (caddr usrmixhsh))
    195       (set! text:digest (cadddr usrmixhsh))
    196       (set! prim:digest (car (cddddr usrmixhsh))) )
    197 
    198   (expect-success "TWUserMixHash-prim" (hash-prim TSTSTR TSTSTR-HALF-LEN 0))
     182      (set! hash-prim       (first usrmixhsh))
     183      (set! hash            (second usrmixhsh))
     184      (set! binary:digest   (third usrmixhsh))
     185      (set! text:digest     (fourth usrmixhsh))
     186      (set! prim:digest     (fifth usrmixhsh)) )
     187
     188  (expect-eqv "TWUserMixHash-prim full-length" 543453076 (hash-prim TSTSTR TSTSTR-LEN 0))
     189  (expect-eqv "TWUserMixHash-prim half-length" 30057 (hash-prim TSTSTR TSTSTR-HALF-LEN 0))
     190
    199191  (expect-eqv "TWUserMixHash Hash" (hash-prim TSTSTR TSTSTR-LEN 0) (hash TSTSTR))
    200192  (expect-eqv "TWUserMixHash Length Arg" (hash-prim TSTSTR TSTSTR-HALF-LEN 0) (hash TSTSTR TSTSTR-HALF-LEN))
    201   (expect-success "TWUserMixHash Digest" (text:digest TSTSTR))
     193
     194  (expect-equal "TWUserMixHash Digest" "20646f94" (text:digest TSTSTR))
     195)
     196
     197(define-test rabin-karp-test "Rabin-Karp Search"
     198        (initial
     199          (define substrs '("quick" "foo" "brown" "dog" "skasfdskjsalksafnsalsfsdsdjkldsajlfsalsk"))
     200          (define hashp)
     201          (define rksp) )
     202
     203  (expect-set! rksp (make-rabin-karp-string-search substrs))
     204
     205  (expect-equal "W/O start & end" '("brown" (10 15)) (rksp TSTSTR))
     206  (expect-equal "W/ start & end" '("dog" (41 44)) (rksp TSTSTR 41 TSTSTR-LEN))
     207
     208  (expect-set! hashp (make-fixnum-bounded-hash RJL3Hash-prim))
     209  (expect-set! rksp (make-rabin-karp-string-search substrs string=? hashp))
     210
     211  (expect-equal "W/O start & end" '("brown" (10 15)) (rksp TSTSTR))
     212  (expect-equal "W/ start & end" '("dog" (41 44)) (rksp TSTSTR 41 TSTSTR-LEN))
    202213)
    203214
Note: See TracChangeset for help on using the changeset viewer.