]>
Commit | Line | Data |
---|---|---|
6cbd5570 CM |
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 | ||
62e2749e CM |
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 | ||
e20d96d6 | 31 | #include <linux/types.h> |
35b7e476 | 32 | #include "hash.h" |
62e2749e CM |
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 | ||
df68b8a7 | 79 | u64 btrfs_name_hash(const char *name, int len) |
62e2749e CM |
80 | { |
81 | __u32 hash; | |
82 | __u32 minor_hash = 0; | |
83 | const char *p; | |
140dfd00 | 84 | __u32 in[8], buf[4]; |
df68b8a7 | 85 | u64 hash_result; |
62e2749e | 86 | |
e20d96d6 | 87 | if (len == 1 && *name == '.') { |
df68b8a7 | 88 | return 1; |
e20d96d6 | 89 | } else if (len == 2 && name[0] == '.' && name[1] == '.') { |
df68b8a7 | 90 | return 2; |
e20d96d6 CM |
91 | } |
92 | ||
62e2749e CM |
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]; | |
df68b8a7 DM |
108 | hash_result = buf[0]; |
109 | hash_result <<= 32; | |
110 | hash_result |= buf[1]; | |
111 | return hash_result; | |
62e2749e | 112 | } |