blob: e5c76903d722d8abf4dbe8b45a4308aa96fd7eb8 [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
79int btrfs_name_hash(const char *name, int len, u64 *hash_result)
80{
81 __u32 hash;
82 __u32 minor_hash = 0;
83 const char *p;
84 __u32 in[8], buf[2];
85
Chris Masone20d96d2007-03-22 12:13:20 -040086 if (len == 1 && *name == '.') {
87 *hash_result = 1;
88 return 0;
89 } else if (len == 2 && name[0] == '.' && name[1] == '.') {
90 *hash_result = 2;
91 return 0;
92 }
93
Chris Mason62e27492007-03-15 12:56:47 -040094 /* Initialize the default seed for the hash checksum functions */
95 buf[0] = 0x67452301;
96 buf[1] = 0xefcdab89;
97 buf[2] = 0x98badcfe;
98 buf[3] = 0x10325476;
99
100 p = name;
101 while (len > 0) {
102 str2hashbuf(p, len, in, 4);
103 TEA_transform(buf, in);
104 len -= 16;
105 p += 16;
106 }
107 hash = buf[0];
108 minor_hash = buf[1];
109 *hash_result = buf[0];
110 *hash_result <<= 32;
111 *hash_result |= buf[1];
112 return 0;
113}