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 #include <linux/types.h>
  14 #define DELTA 0x9E3779B9
  15
  16 static void TEA_transform(__u32 buf[2], __u32 const in[])
  17 {
  18         __u32   sum = 0;
  19         __u32   b0 = buf[0], b1 = buf[1];
  20         __u32   a = in[0], b = in[1], c = in[2], d = in[3];
  21         int     n = 16;
  22
  23         do {
  24                 sum += DELTA;
  25                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
  26                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
  27         } while(--n);
  28
  29         buf[0] += b0;
  30         buf[1] += b1;
  31 }
  32
  33 static void str2hashbuf(const char *msg, int len, __u32 *buf, int num)
  34 {
  35         __u32   pad, val;
  36         int     i;
  37
  38         pad = (__u32)len | ((__u32)len << 8);
  39         pad |= pad << 16;
  40
  41         val = pad;
  42         if (len > num*4)
  43                 len = num * 4;
  44         for (i=0; i < len; i++) {
  45                 if ((i % 4) == 0)
  46                         val = pad;
  47                 val = msg[i] + (val << 8);
  48                 if ((i % 4) == 3) {
  49                         *buf++ = val;
  50                         val = pad;
  51                         num--;
  52                 }
  53         }
  54         if (--num >= 0)
  55                 *buf++ = val;
  56         while (--num >= 0)
  57                 *buf++ = pad;
  58 }
  59
  60 int btrfs_name_hash(const char *name, int len, u64 *hash_result)
  61 {
  62         __u32   hash;
  63         __u32   minor_hash = 0;
  64         const char      *p;
  65         __u32           in[8], buf[2];
  66
  67         if (len == 1 && *name == '.') {
  68                 *hash_result = 1;
  69                 return 0;
  70         } else if (len == 2 && name[0] == '.' && name[1] == '.') {
  71                 *hash_result = 2;
  72                 return 0;
  73         }
  74
  75         /* Initialize the default seed for the hash checksum functions */
  76         buf[0] = 0x67452301;
  77         buf[1] = 0xefcdab89;
  78         buf[2] = 0x98badcfe;
  79         buf[3] = 0x10325476;
  80
  81         p = name;
  82         while (len > 0) {
  83                 str2hashbuf(p, len, in, 4);
  84                 TEA_transform(buf, in);
  85                 len -= 16;
  86                 p += 16;
  87         }
  88         hash = buf[0];
  89         minor_hash = buf[1];
  90         *hash_result = buf[0];
  91         *hash_result <<= 32;
  92         *hash_result |= buf[1];
  93         return 0;
  94 }