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