Don't like ads? PRO users don't see any ads ;-)
Guest

Path component hashing

By: a guest on Mar 1st, 2012  |  syntax: C  |  size: 1.44 KB  |  hits: 4,665  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #define ONEBYTES        0x0101010101010101ul
  2. #define SLASHBYTES      0x2f2f2f2f2f2f2f2ful
  3. #define HIGHBITS        0x8080808080808080ul
  4.  
  5. /* Return the high bit set in the first byte that is a zero */
  6. static inline unsigned long has_zero(unsigned long a)
  7. {
  8.         return ((a - ONEBYTES) & ~a) & HIGHBITS;
  9. }
  10.  
  11. /*
  12.  * Calculate the length and hash of the path component, and
  13.  * return the beginning of the next one (or the pointer to the
  14.  * final NUL character if none).
  15.  */
  16. static inline const char *hash_name(struct qstr *str, const char *name)
  17. {
  18.         unsigned long a, mask;
  19.         unsigned long hash = 0;
  20.         unsigned long len = 0;
  21.  
  22.         str->name = name;
  23.         a = 0;
  24.         len = -sizeof(unsigned long);
  25.         do {
  26.                 hash = (hash + a) * 11;
  27.                 len += sizeof(unsigned long);
  28.                 a = *(unsigned long *)(name+len);
  29.                 /* Do we have any NUL or '/' bytes in this word? */
  30.                 mask = has_zero(a) | has_zero(a ^ SLASHBYTES);
  31.         } while (!mask);
  32.  
  33.         /* The mask *below* the first high bit set */
  34.         mask = (mask - 1) & ~mask;
  35.         mask >>= 7;
  36.         hash += a & mask;
  37.         str->hash = fold_hash(hash);
  38.  
  39.         /* Get the final path component length */
  40.         len += ffz(mask) / 8;
  41.         str->len = len;
  42.  
  43.         /* remove trailing slashes */
  44.         while (name[len] == '/')
  45.                 len++;
  46.  
  47.         return name+len;
  48. }