fs/btrfs/hash.c

   1 /*
   2  *  Original copy from:
   3  *  linux/fs/ext3/hash.c
   4  *
   5  * Copyright (C) 2002 by Theodore Ts'o
   6  *
   7  * This file is released under the GPL v2.
   8  *
   9  * This file may be redistributed under the terms of the GNU Public
  10  * License.
  11  */
  12
  13 #define DELTA 0x9E3779B9
  14
  15 static void TEA_transform(__u32 buf[2], __u32 const in[])
  16 {
  17         __u32   sum = 0;
  18         __u32   b0 = buf[0], b1 = buf[1];
  19         __u32   a = in[0], b = in[1], c = in[2], d = in[3];
  20         int     n = 16;
  21
  22         do {
  23                 sum += DELTA;
  24                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
  25                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
  26         } while(--n);
  27
  28         buf[0] += b0;
  29         buf[1] += b1;
  30 }
  31
  32 static void str2hashbuf(const char *msg, int len, __u32 *buf, int num)
  33 {
  34         __u32   pad, val;
  35         int     i;
  36
  37         pad = (__u32)len | ((__u32)len << 8);
  38         pad |= pad << 16;
  39
  40         val = pad;
  41         if (len > num*4)
  42                 len = num * 4;
  43         for (i=0; i < len; i++) {
  44                 if ((i % 4) == 0)
  45                         val = pad;
  46                 val = msg[i] + (val << 8);
  47                 if ((i % 4) == 3) {
  48                         *buf++ = val;
  49                         val = pad;
  50                         num--;
  51                 }
  52         }
  53         if (--num >= 0)
  54                 *buf++ = val;
  55         while (--num >= 0)
  56                 *buf++ = pad;
  57 }
  58
  59 int btrfs_name_hash(const char *name, int len, u64 *hash_result)
  60 {
  61         __u32   hash;
  62         __u32   minor_hash = 0;
  63         const char      *p;
  64         __u32           in[8], buf[2];
  65
  66         /* Initialize the default seed for the hash checksum functions */
  67         buf[0] = 0x67452301;
  68         buf[1] = 0xefcdab89;
  69         buf[2] = 0x98badcfe;
  70         buf[3] = 0x10325476;
  71
  72         p = name;
  73         while (len > 0) {
  74                 str2hashbuf(p, len, in, 4);
  75                 TEA_transform(buf, in);
  76                 len -= 16;
  77                 p += 16;
  78         }
  79         hash = buf[0];
  80         minor_hash = buf[1];
  81         *hash_result = buf[0];
  82         *hash_result <<= 32;
  83         *hash_result |= buf[1];
  84         return 0;
  85 }