lib/hashfunc.c

   1 /*
   2  *      Hyper-super-meta-alt-control-shift extra fast str_len() and hash_*()
   3  *      routines
   4  *
   5  *      It is always at least as fast as the classical strlen() routine and for
   6  *      strings longer than 100 characters, it is substantially faster.
   7  *
   8  *      (c) 2002, Robert Spalek <robert@ucw.cz>
   9  */
  10
  11 #include "lib/lib.h"
  12 #include "lib/hashfunc.h"
  13 #include "lib/chartype.h"
  14
  15 /* The number of bits the hash in the function hash_*() is rotated by after
  16  * every pass.  It should be prime with the word size.  */
  17 #define SHIFT_BITS      5
  18
  19 /* A bit-mask which clears higher bytes than a given threshold.  */
  20 static uns mask_higher_bits[sizeof(uns)];
  21
  22 static void CONSTRUCTOR
  23 hashfunc_init(void)
  24 {
  25         uns i, j;
  26         byte *str;
  27         for (i=0; i<sizeof(uns); i++)
  28         {
  29                 str = (byte *) (mask_higher_bits + i);
  30                 for (j=0; j<i; j++)
  31                         str[j] = -1;
  32                 for (j=i; j<sizeof(uns); j++)
  33                         str[j] = 0;
  34         }
  35 }
  36
  37 static inline uns CONST
  38 str_len_uns(uns x)
  39 {
  40         const uns sub = ((uns) -1) / 0xff;
  41         const uns and = sub * 0x80;
  42         uns a, i;
  43         byte *bytes;
  44         a = (x ^ (x - sub)) & and;
  45         /*
  46          * x_2 = x - 0x01010101;
  47          * x_3 = x ^ x_2;
  48          * a = x_3 & 0x80808080;
  49          *
  50          * If no byte of x is in {0, 0x80}, then the highest bit of each byte
  51          * of x_2 is the same as of x.  Hence x_3 has all these highest bits
  52          * cleared.  If a == 0, then we are sure there is no zero byte in x.
  53          */
  54         if (!a)
  55                 return sizeof(uns);
  56         bytes = (byte *) &x;
  57         for (i=0; i<sizeof(uns) && bytes[i]; i++);
  58         return i;
  59 }
  60
  61 inline uns
  62 str_len_aligned(const byte *str)
  63 {
  64         const uns *u = (const uns *) str;
  65         uns len = 0;
  66         while (1)
  67         {
  68                 uns l = str_len_uns(*u++);
  69                 len += l;
  70                 if (l < sizeof(uns))
  71                         return len;
  72         }
  73 }
  74
  75 inline uns
  76 hash_string_aligned(const byte *str)
  77 {
  78         const uns *u = (const uns *) str;
  79         uns hash = 0;
  80         while (1)
  81         {
  82                 uns last_len = str_len_uns(*u);
  83                 hash = ROL(hash, SHIFT_BITS);
  84                 if (last_len < sizeof(uns))
  85                 {
  86                         uns tmp = *u & mask_higher_bits[last_len];
  87                         hash ^= tmp;
  88                         return hash;
  89                 }
  90                 hash ^= *u++;
  91         }
  92 }
  93
  94 inline uns
  95 hash_block_aligned(const byte *str, uns len)
  96 {
  97         const uns *u = (const uns *) str;
  98         uns hash = 0;
  99         while (len >= sizeof(uns))
 100         {
 101                 hash = ROL(hash, SHIFT_BITS) ^ *u++;
 102                 len -= sizeof(uns);
 103         }
 104         hash = ROL(hash, SHIFT_BITS) ^ (*u & mask_higher_bits[len]);
 105         return hash;
 106 }
 107
 108 #ifndef CPU_ALLOW_UNALIGNED
 109 uns
 110 str_len(const byte *str)
 111 {
 112         uns shift = UNALIGNED_PART(str, uns);
 113         if (!shift)
 114                 return str_len_aligned(str);
 115         else
 116         {
 117                 uns i;
 118                 shift = sizeof(uns) - shift;
 119                 for (i=0; i<shift; i++)
 120                         if (!str[i])
 121                                 return i;
 122                 return shift + str_len_aligned(str + shift);
 123         }
 124 }
 125
 126 uns
 127 hash_string(const byte *str)
 128 {
 129         uns shift = UNALIGNED_PART(str, uns);
 130         if (!shift)
 131                 return hash_string_aligned(str);
 132         else
 133         {
 134                 uns hash = 0;
 135                 uns i;
 136                 for (i=0; ; i++)
 137                 {
 138                         uns modulo = i % sizeof(uns);
 139                         uns shift;
 140 #ifdef  CPU_LITTLE_ENDIAN
 141                         shift = modulo;
 142 #else
 143                         shift = sizeof(uns) - 1 - modulo;
 144 #endif
 145                         if (!modulo)
 146                                 hash = ROL(hash, SHIFT_BITS);
 147                         if (!str[i])
 148                                 break;
 149                         hash ^= str[i] << (shift * 8);
 150                 }
 151                 return hash;
 152         }
 153 }
 154
 155 uns
 156 hash_block(const byte *str, uns len)
 157 {
 158         uns shift = UNALIGNED_PART(str, uns);
 159         if (!shift)
 160                 return hash_block_aligned(str, len);
 161         else
 162         {
 163                 uns hash = 0;
 164                 uns i;
 165                 for (i=0; ; i++)
 166                 {
 167                         uns modulo = i % sizeof(uns);
 168                         uns shift;
 169 #ifdef  CPU_LITTLE_ENDIAN
 170                         shift = modulo;
 171 #else
 172                         shift = sizeof(uns) - 1 - modulo;
 173 #endif
 174                         if (!modulo)
 175                                 hash = ROL(hash, SHIFT_BITS);
 176                         if (i >= len)
 177                                 break;
 178                         hash ^= str[i] << (shift * 8);
 179                 }
 180                 return hash;
 181         }
 182 }
 183 #endif
 184
 185 uns
 186 hash_string_nocase(const byte *str)
 187 {
 188         uns hash = 0;
 189         uns i;
 190         for (i=0; ; i++)
 191         {
 192                 uns modulo = i % sizeof(uns);
 193                 uns shift;
 194 #ifdef  CPU_LITTLE_ENDIAN
 195                 shift = modulo;
 196 #else
 197                 shift = sizeof(uns) - 1 - modulo;
 198 #endif
 199                 if (!modulo)
 200                         hash = ROL(hash, SHIFT_BITS);
 201                 if (!str[i])
 202                         break;
 203                 hash ^= Cupcase(str[i]) << (shift * 8);
 204         }
 205         return hash;
 206 }