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