ucw/hashfunc.c

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