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