lib/str_hash.c

   1 /*
   2  *      Hyper-super-meta-alt-control-shift extra fast str_len() and str_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/str_hash.h"
  13
  14 /* The number of bits the hash (in the function str_hash()) is rotated after
  15  * every pass by.  It should be prime with the word size.  */
  16 #define SHIFT_BITS      5
  17
  18 /* A bit-mask which clears higher bytes than a given threshold.  */
  19 static uns mask_higher_bits[sizeof(uns)];
  20
  21 static void CONSTRUCTOR
  22 str_hash_init(void)
  23 {
  24         uns i, j;
  25         char *str;
  26         for (i=0; i<sizeof(uns); i++)
  27         {
  28                 str = (char *) mask_higher_bits + i;
  29                 for (j=0; j<i; j++)
  30                         str[j] = -1;
  31                 for (j=i; j<sizeof(uns); j++)
  32                         str[j] = 0;
  33         }
  34 }
  35
  36 static inline uns str_len_uns(uns x) __attribute__((const));
  37
  38 static inline uns
  39 str_len_uns(uns x)
  40 {
  41         const uns sub = ((uns) -1) / 0xff;
  42         const uns and = sub * 0x80;
  43         uns a, i;
  44         char *bytes;
  45         a = (x ^ (x - sub)) & and;
  46         /*
  47          * x_2 = x - 0x01010101;
  48          * x_3 = x ^ x_2;
  49          * a = x_3 & 0x80808080;
  50          *
  51          * If none byte of x is in {0, 0x80}, then the highest bit of each byte
  52          * of x_2 is the same as of x.  Hence x_3 has all these highest bits
  53          * cleared.  If a == 0, then we are sure there is no zero byte in x.
  54          */
  55         if (!a)
  56                 return sizeof(uns);
  57         bytes = (char *) &x;
  58         for (i=0; i<sizeof(uns) && bytes[i]; i++);
  59         return i;
  60 }
  61
  62 uns
  63 str_len(const char *str)
  64 {
  65         const uns *u = (const uns *) str;
  66         uns len = 0;
  67         while (1)
  68         {
  69                 uns l = str_len_uns(*u++);
  70                 len += l;
  71                 if (l < sizeof(uns))
  72                         return len;
  73         }
  74 }
  75
  76 uns
  77 str_hash(const char *str)
  78 {
  79         const uns *u = (const uns *) str;
  80         uns hash = 0;
  81         while (1)
  82         {
  83                 uns last_len = str_len_uns(*u);
  84                 hash = ROL(hash, SHIFT_BITS);
  85                 if (last_len < sizeof(uns))
  86                 {
  87                         uns tmp = *u & mask_higher_bits[last_len];
  88                         hash ^= tmp;
  89                         return hash;
  90                 }
  91                 hash ^= *u++;
  92         }
  93 }