Root/
1 | /* |
2 | * linux/fs/ext4/hash.c |
3 | * |
4 | * Copyright (C) 2002 by Theodore Ts'o |
5 | * |
6 | * This file is released under the GPL v2. |
7 | * |
8 | * This file may be redistributed under the terms of the GNU Public |
9 | * License. |
10 | */ |
11 | |
12 | #include <linux/fs.h> |
13 | #include <linux/jbd2.h> |
14 | #include <linux/cryptohash.h> |
15 | #include "ext4.h" |
16 | |
17 | #define DELTA 0x9E3779B9 |
18 | |
19 | static void TEA_transform(__u32 buf[4], __u32 const in[]) |
20 | { |
21 | __u32 sum = 0; |
22 | __u32 b0 = buf[0], b1 = buf[1]; |
23 | __u32 a = in[0], b = in[1], c = in[2], d = in[3]; |
24 | int n = 16; |
25 | |
26 | do { |
27 | sum += DELTA; |
28 | b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); |
29 | b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); |
30 | } while (--n); |
31 | |
32 | buf[0] += b0; |
33 | buf[1] += b1; |
34 | } |
35 | |
36 | |
37 | /* The old legacy hash */ |
38 | static __u32 dx_hack_hash_unsigned(const char *name, int len) |
39 | { |
40 | __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; |
41 | const unsigned char *ucp = (const unsigned char *) name; |
42 | |
43 | while (len--) { |
44 | hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373)); |
45 | |
46 | if (hash & 0x80000000) |
47 | hash -= 0x7fffffff; |
48 | hash1 = hash0; |
49 | hash0 = hash; |
50 | } |
51 | return hash0 << 1; |
52 | } |
53 | |
54 | static __u32 dx_hack_hash_signed(const char *name, int len) |
55 | { |
56 | __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; |
57 | const signed char *scp = (const signed char *) name; |
58 | |
59 | while (len--) { |
60 | hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373)); |
61 | |
62 | if (hash & 0x80000000) |
63 | hash -= 0x7fffffff; |
64 | hash1 = hash0; |
65 | hash0 = hash; |
66 | } |
67 | return hash0 << 1; |
68 | } |
69 | |
70 | static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num) |
71 | { |
72 | __u32 pad, val; |
73 | int i; |
74 | const signed char *scp = (const signed char *) msg; |
75 | |
76 | pad = (__u32)len | ((__u32)len << 8); |
77 | pad |= pad << 16; |
78 | |
79 | val = pad; |
80 | if (len > num*4) |
81 | len = num * 4; |
82 | for (i = 0; i < len; i++) { |
83 | if ((i % 4) == 0) |
84 | val = pad; |
85 | val = ((int) scp[i]) + (val << 8); |
86 | if ((i % 4) == 3) { |
87 | *buf++ = val; |
88 | val = pad; |
89 | num--; |
90 | } |
91 | } |
92 | if (--num >= 0) |
93 | *buf++ = val; |
94 | while (--num >= 0) |
95 | *buf++ = pad; |
96 | } |
97 | |
98 | static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num) |
99 | { |
100 | __u32 pad, val; |
101 | int i; |
102 | const unsigned char *ucp = (const unsigned char *) msg; |
103 | |
104 | pad = (__u32)len | ((__u32)len << 8); |
105 | pad |= pad << 16; |
106 | |
107 | val = pad; |
108 | if (len > num*4) |
109 | len = num * 4; |
110 | for (i = 0; i < len; i++) { |
111 | if ((i % 4) == 0) |
112 | val = pad; |
113 | val = ((int) ucp[i]) + (val << 8); |
114 | if ((i % 4) == 3) { |
115 | *buf++ = val; |
116 | val = pad; |
117 | num--; |
118 | } |
119 | } |
120 | if (--num >= 0) |
121 | *buf++ = val; |
122 | while (--num >= 0) |
123 | *buf++ = pad; |
124 | } |
125 | |
126 | /* |
127 | * Returns the hash of a filename. If len is 0 and name is NULL, then |
128 | * this function can be used to test whether or not a hash version is |
129 | * supported. |
130 | * |
131 | * The seed is an 4 longword (32 bits) "secret" which can be used to |
132 | * uniquify a hash. If the seed is all zero's, then some default seed |
133 | * may be used. |
134 | * |
135 | * A particular hash version specifies whether or not the seed is |
136 | * represented, and whether or not the returned hash is 32 bits or 64 |
137 | * bits. 32 bit hashes will return 0 for the minor hash. |
138 | */ |
139 | int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo) |
140 | { |
141 | __u32 hash; |
142 | __u32 minor_hash = 0; |
143 | const char *p; |
144 | int i; |
145 | __u32 in[8], buf[4]; |
146 | void (*str2hashbuf)(const char *, int, __u32 *, int) = |
147 | str2hashbuf_signed; |
148 | |
149 | /* Initialize the default seed for the hash checksum functions */ |
150 | buf[0] = 0x67452301; |
151 | buf[1] = 0xefcdab89; |
152 | buf[2] = 0x98badcfe; |
153 | buf[3] = 0x10325476; |
154 | |
155 | /* Check to see if the seed is all zero's */ |
156 | if (hinfo->seed) { |
157 | for (i = 0; i < 4; i++) { |
158 | if (hinfo->seed[i]) |
159 | break; |
160 | } |
161 | if (i < 4) |
162 | memcpy(buf, hinfo->seed, sizeof(buf)); |
163 | } |
164 | |
165 | switch (hinfo->hash_version) { |
166 | case DX_HASH_LEGACY_UNSIGNED: |
167 | hash = dx_hack_hash_unsigned(name, len); |
168 | break; |
169 | case DX_HASH_LEGACY: |
170 | hash = dx_hack_hash_signed(name, len); |
171 | break; |
172 | case DX_HASH_HALF_MD4_UNSIGNED: |
173 | str2hashbuf = str2hashbuf_unsigned; |
174 | case DX_HASH_HALF_MD4: |
175 | p = name; |
176 | while (len > 0) { |
177 | (*str2hashbuf)(p, len, in, 8); |
178 | half_md4_transform(buf, in); |
179 | len -= 32; |
180 | p += 32; |
181 | } |
182 | minor_hash = buf[2]; |
183 | hash = buf[1]; |
184 | break; |
185 | case DX_HASH_TEA_UNSIGNED: |
186 | str2hashbuf = str2hashbuf_unsigned; |
187 | case DX_HASH_TEA: |
188 | p = name; |
189 | while (len > 0) { |
190 | (*str2hashbuf)(p, len, in, 4); |
191 | TEA_transform(buf, in); |
192 | len -= 16; |
193 | p += 16; |
194 | } |
195 | hash = buf[0]; |
196 | minor_hash = buf[1]; |
197 | break; |
198 | default: |
199 | hinfo->hash = 0; |
200 | return -1; |
201 | } |
202 | hash = hash & ~1; |
203 | if (hash == (EXT4_HTREE_EOF << 1)) |
204 | hash = (EXT4_HTREE_EOF-1) << 1; |
205 | hinfo->hash = hash; |
206 | hinfo->minor_hash = minor_hash; |
207 | return 0; |
208 | } |
209 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9