Branch data Line data Source code
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 : 0 : static void TEA_transform(__u32 buf[4], __u32 const in[])
20 : : {
21 : : __u32 sum = 0;
22 : 0 : __u32 b0 = buf[0], b1 = buf[1];
23 : 0 : __u32 a = in[0], b = in[1], c = in[2], d = in[3];
24 : : int n = 16;
25 : :
26 : : do {
27 : 0 : sum += DELTA;
28 : 0 : b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
29 : 0 : b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
30 [ # # ]: 0 : } while (--n);
31 : :
32 : 0 : buf[0] += b0;
33 : 0 : buf[1] += b1;
34 : 0 : }
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 [ - ]: 0 : while (len--) {
44 : 0 : hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));
45 : :
46 [ # # ]: 0 : if (hash & 0x80000000)
47 : 0 : hash -= 0x7fffffff;
48 : : hash1 = hash0;
49 : : hash0 = hash;
50 : : }
51 : 0 : 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 [ # # ]: 0 : while (len--) {
60 : 0 : hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));
61 : :
62 [ # # ]: 0 : if (hash & 0x80000000)
63 : 0 : hash -= 0x7fffffff;
64 : : hash1 = hash0;
65 : : hash0 = hash;
66 : : }
67 : 0 : return hash0 << 1;
68 : : }
69 : :
70 : 0 : 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 : 222429 : pad = (__u32)len | ((__u32)len << 8);
77 : 222429 : pad |= pad << 16;
78 : :
79 : : val = pad;
80 [ + + ]: 222429 : if (len > num*4)
81 : : len = num * 4;
82 [ + + ]: 2641633 : for (i = 0; i < len; i++) {
83 [ + + ]: 2419204 : if ((i % 4) == 0)
84 : : val = pad;
85 : 2419204 : val = ((int) scp[i]) + (val << 8);
86 [ + + ]: 2419204 : if ((i % 4) == 3) {
87 : 535370 : *buf++ = val;
88 : : val = pad;
89 : 535370 : num--;
90 : : }
91 : : }
92 [ + + ]: 222429 : if (--num >= 0)
93 : 222429 : *buf++ = val;
94 [ + + ]: 1257436 : while (--num >= 0)
95 : 1035007 : *buf++ = pad;
96 : 222429 : }
97 : :
98 : 0 : 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 : 0 : pad = (__u32)len | ((__u32)len << 8);
105 : 0 : pad |= pad << 16;
106 : :
107 : : val = pad;
108 [ # # ]: 0 : if (len > num*4)
109 : : len = num * 4;
110 [ # # ]: 0 : for (i = 0; i < len; i++) {
111 [ # # ]: 0 : if ((i % 4) == 0)
112 : : val = pad;
113 : 0 : val = ((int) ucp[i]) + (val << 8);
114 [ # # ]: 0 : if ((i % 4) == 3) {
115 : 0 : *buf++ = val;
116 : : val = pad;
117 : 0 : num--;
118 : : }
119 : : }
120 [ # # ]: 0 : if (--num >= 0)
121 : 0 : *buf++ = val;
122 [ # # ]: 0 : while (--num >= 0)
123 : 0 : *buf++ = pad;
124 : 0 : }
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 : 0 : 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 : 209233 : buf[0] = 0x67452301;
151 : 209233 : buf[1] = 0xefcdab89;
152 : 209233 : buf[2] = 0x98badcfe;
153 : 209233 : buf[3] = 0x10325476;
154 : :
155 : : /* Check to see if the seed is all zero's */
156 [ + ]: 209233 : if (hinfo->seed) {
157 [ + - ]: 209246 : for (i = 0; i < 4; i++) {
158 [ + - ]: 209246 : if (hinfo->seed[i]) {
159 : 209246 : memcpy(buf, hinfo->seed, sizeof(buf));
160 : 209246 : break;
161 : : }
162 : : }
163 : : }
164 : :
165 [ - - + - : 209233 : switch (hinfo->hash_version) {
- - ]
166 : : case DX_HASH_LEGACY_UNSIGNED:
167 : : hash = dx_hack_hash_unsigned(name, len);
168 : 0 : break;
169 : : case DX_HASH_LEGACY:
170 : : hash = dx_hack_hash_signed(name, len);
171 : 0 : break;
172 : : case DX_HASH_HALF_MD4_UNSIGNED:
173 : : str2hashbuf = str2hashbuf_unsigned;
174 : : case DX_HASH_HALF_MD4:
175 : : p = name;
176 [ + + ]: 431637 : while (len > 0) {
177 : 222402 : (*str2hashbuf)(p, len, in, 8);
178 : 222408 : half_md4_transform(buf, in);
179 : 222399 : len -= 32;
180 : 222399 : p += 32;
181 : : }
182 : 209235 : minor_hash = buf[2];
183 : 209235 : hash = buf[1];
184 : 209235 : break;
185 : : case DX_HASH_TEA_UNSIGNED:
186 : : str2hashbuf = str2hashbuf_unsigned;
187 : : case DX_HASH_TEA:
188 : : p = name;
189 [ # # ]: 0 : while (len > 0) {
190 : 0 : (*str2hashbuf)(p, len, in, 4);
191 : 0 : TEA_transform(buf, in);
192 : 0 : len -= 16;
193 : 0 : p += 16;
194 : : }
195 : 0 : hash = buf[0];
196 : 0 : minor_hash = buf[1];
197 : 0 : break;
198 : : default:
199 : 0 : hinfo->hash = 0;
200 : 0 : return -1;
201 : : }
202 : 209230 : hash = hash & ~1;
203 [ - + ]: 209230 : if (hash == (EXT4_HTREE_EOF_32BIT << 1))
204 : : hash = (EXT4_HTREE_EOF_32BIT - 1) << 1;
205 : 209230 : hinfo->hash = hash;
206 : 209230 : hinfo->minor_hash = minor_hash;
207 : 209230 : return 0;
208 : : }
|
