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 = ~0U / 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 all bytes of x are nonzero, then the highest bit of each byte of
  51          * x_2 is lower or equal to the corresponding bit of x.  Hence x_3 has
  52          * all these highest bits cleared (the target bit is set iff the source
  53          * bit has changed from 0 to 1).  If a == 0, then we are sure there is
  54          * no zero byte in x.
  55          */
  56         if (!a)
  57                 return sizeof(uns);
  58         bytes = (byte *) &x;
  59         for (i=0; i<sizeof(uns) && bytes[i]; i++);
  60         return i;
  61 }
  62
  63 inline uns
  64 str_len_aligned(const byte *str)
  65 {
  66         const uns *u = (const uns *) str;
  67         uns len = 0;
  68         while (1)
  69         {
  70                 uns l = str_len_uns(*u++);
  71                 len += l;
  72                 if (l < sizeof(uns))
  73                         return len;
  74         }
  75 }
  76
  77 inline uns
  78 hash_string_aligned(const byte *str)
  79 {
  80         const uns *u = (const uns *) str;
  81         uns hash = 0;
  82         while (1)
  83         {
  84                 uns last_len = str_len_uns(*u);
  85                 hash = ROL(hash, SHIFT_BITS);
  86                 if (last_len < sizeof(uns))
  87                 {
  88                         uns tmp = *u & mask_higher_bits[last_len];
  89                         hash ^= tmp;
  90                         return hash;
  91                 }
  92                 hash ^= *u++;
  93         }
  94 }
  95
  96 inline uns
  97 hash_block_aligned(const byte *str, uns len)
  98 {
  99         const uns *u = (const uns *) str;
 100         uns hash = 0;
 101         while (len >= sizeof(uns))
 102         {
 103                 hash = ROL(hash, SHIFT_BITS) ^ *u++;
 104                 len -= sizeof(uns);
 105         }
 106         hash = ROL(hash, SHIFT_BITS) ^ (*u & mask_higher_bits[len]);
 107         return hash;
 108 }
 109
 110 #ifndef CPU_ALLOW_UNALIGNED
 111 uns
 112 str_len(const byte *str)
 113 {
 114         uns shift = UNALIGNED_PART(str, uns);
 115         if (!shift)
 116                 return str_len_aligned(str);
 117         else
 118         {
 119                 uns i;
 120                 shift = sizeof(uns) - shift;
 121                 for (i=0; i<shift; i++)
 122                         if (!str[i])
 123                                 return i;
 124                 return shift + str_len_aligned(str + shift);
 125         }
 126 }
 127
 128 uns
 129 hash_string(const byte *str)
 130 {
 131         uns shift = UNALIGNED_PART(str, uns);
 132         if (!shift)
 133                 return hash_string_aligned(str);
 134         else
 135         {
 136                 uns hash = 0;
 137                 uns i;
 138                 for (i=0; ; i++)
 139                 {
 140                         uns modulo = i % sizeof(uns);
 141                         uns shift;
 142 #ifdef  CPU_LITTLE_ENDIAN
 143                         shift = modulo;
 144 #else
 145                         shift = sizeof(uns) - 1 - modulo;
 146 #endif
 147                         if (!modulo)
 148                                 hash = ROL(hash, SHIFT_BITS);
 149                         if (!str[i])
 150                                 break;
 151                         hash ^= str[i] << (shift * 8);
 152                 }
 153                 return hash;
 154         }
 155 }
 156
 157 uns
 158 hash_block(const byte *str, uns len)
 159 {
 160         uns shift = UNALIGNED_PART(str, uns);
 161         if (!shift)
 162                 return hash_block_aligned(str, len);
 163         else
 164         {
 165                 uns hash = 0;
 166                 uns i;
 167                 for (i=0; ; i++)
 168                 {
 169                         uns modulo = i % sizeof(uns);
 170                         uns shift;
 171 #ifdef  CPU_LITTLE_ENDIAN
 172                         shift = modulo;
 173 #else
 174                         shift = sizeof(uns) - 1 - modulo;
 175 #endif
 176                         if (!modulo)
 177                                 hash = ROL(hash, SHIFT_BITS);
 178                         if (i >= len)
 179                                 break;
 180                         hash ^= str[i] << (shift * 8);
 181                 }
 182                 return hash;
 183         }
 184 }
 185 #endif
 186
 187 uns
 188 hash_string_nocase(const byte *str)
 189 {
 190         uns hash = 0;
 191         uns i;
 192         for (i=0; ; i++)
 193         {
 194                 uns modulo = i % sizeof(uns);
 195                 uns shift;
 196 #ifdef  CPU_LITTLE_ENDIAN
 197                 shift = modulo;
 198 #else
 199                 shift = sizeof(uns) - 1 - modulo;
 200 #endif
 201                 if (!modulo)
 202                         hash = ROL(hash, SHIFT_BITS);
 203                 if (!str[i])
 204                         break;
 205                 hash ^= Cupcase(str[i]) << (shift * 8);
 206         }
 207         return hash;
 208 }