blob: 21037cfca9bde6a4b527f7cb02489937ad563416 [file] [log] [blame]
Chris Mason62e27492007-03-15 12:56:47 -04001/*
Chris Mason6cbd5572007-06-12 09:07:21 -04002 * 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/*
Chris Mason62e27492007-03-15 12:56:47 -040020 * 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
Chris Masone20d96d2007-03-22 12:13:20 -040031#include <linux/types.h>
Chris Mason35b7e472007-05-02 15:53:43 -040032#include "hash.h"
Chris Mason62e27492007-03-15 12:56:47 -040033#define DELTA 0x9E3779B9
34
35static 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
52static 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
David Millerdf68b8a2008-02-15 10:40:52 -050079u64 btrfs_name_hash(const char *name, int len)
Chris Mason62e27492007-03-15 12:56:47 -040080{
81 __u32 hash;
82 __u32 minor_hash = 0;
83 const char *p;
Alex Chiang140dfd02008-04-01 11:21:40 -040084 __u32 in[8], buf[4];
David Millerdf68b8a2008-02-15 10:40:52 -050085 u64 hash_result;
Chris Mason62e27492007-03-15 12:56:47 -040086
Chris Masone20d96d2007-03-22 12:13:20 -040087 if (len == 1 && *name == '.') {
David Millerdf68b8a2008-02-15 10:40:52 -050088 return 1;
Chris Masone20d96d2007-03-22 12:13:20 -040089 } else if (len == 2 && name[0] == '.' && name[1] == '.') {
David Millerdf68b8a2008-02-15 10:40:52 -050090 return 2;
Chris Masone20d96d2007-03-22 12:13:20 -040091 }
92
Chris Mason62e27492007-03-15 12:56:47 -040093 /* 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];
David Millerdf68b8a2008-02-15 10:40:52 -0500108 hash_result = buf[0];
109 hash_result <<= 32;
110 hash_result |= buf[1];
111 return hash_result;
Chris Mason62e27492007-03-15 12:56:47 -0400112}