fs/btrfs/hash.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 /*
  20  *  Original copy from:
  21  *  linux/fs/ext3/hash.c
  22  *
  23  * Copyright (C) 2002 by Theodore Ts'o
  24  *
  25  * This file is released under the GPL v2.
  26  *
  27  * This file may be redistributed under the terms of the GNU Public
  28  * License.
  29  */
  30
  31 #include <linux/types.h>
  32 #include "hash.h"
  33 #define DELTA 0x9E3779B9
  34
  35 static void TEA_transform(__u32 buf[2], __u32 const in[])
  36 {
  37         __u32   sum = 0;
  38         __u32   b0 = buf[0], b1 = buf[1];
  39         __u32   a = in[0], b = in[1], c = in[2], d = in[3];
  40         int     n = 16;
  41
  42         do {
  43                 sum += DELTA;
  44                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
  45                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
  46         } while(--n);
  47
  48         buf[0] += b0;
  49         buf[1] += b1;
  50 }
  51
  52 static void str2hashbuf(const char *msg, int len, __u32 *buf, int num)
  53 {
  54         __u32   pad, val;
  55         int     i;
  56
  57         pad = (__u32)len | ((__u32)len << 8);
  58         pad |= pad << 16;
  59
  60         val = pad;
  61         if (len > num*4)
  62                 len = num * 4;
  63         for (i=0; i < len; i++) {
  64                 if ((i % 4) == 0)
  65                         val = pad;
  66                 val = msg[i] + (val << 8);
  67                 if ((i % 4) == 3) {
  68                         *buf++ = val;
  69                         val = pad;
  70                         num--;
  71                 }
  72         }
  73         if (--num >= 0)
  74                 *buf++ = val;
  75         while (--num >= 0)
  76                 *buf++ = pad;
  77 }
  78
  79 u64 btrfs_name_hash(const char *name, int len)
  80 {
  81         __u32   hash;
  82         __u32   minor_hash = 0;
  83         const char      *p;
  84         __u32           in[8], buf[4];
  85         u64             hash_result;
  86
  87         if (len == 1 && *name == '.') {
  88                 return 1;
  89         } else if (len == 2 && name[0] == '.' && name[1] == '.') {
  90                 return 2;
  91         }
  92
  93         /* Initialize the default seed for the hash checksum functions */
  94         buf[0] = 0x67452301;
  95         buf[1] = 0xefcdab89;
  96         buf[2] = 0x98badcfe;
  97         buf[3] = 0x10325476;
  98
  99         p = name;
 100         while (len > 0) {
 101                 str2hashbuf(p, len, in, 4);
 102                 TEA_transform(buf, in);
 103                 len -= 16;
 104                 p += 16;
 105         }
 106         hash = buf[0];
 107         minor_hash = buf[1];
 108         hash_result = buf[0];
 109         hash_result <<= 32;
 110         hash_result |= buf[1];
 111         return hash_result;
 112 }