Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/sparc-2.6
[linux-2.6] / fs / ext3 / hash.c
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 <linux/fs.h>
13 #include <linux/jbd.h>
14 #include <linux/ext3_fs.h>
15 #include <linux/cryptohash.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 ext3fs_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 == (EXT3_HTREE_EOF << 1))
204                 hash = (EXT3_HTREE_EOF-1) << 1;
205         hinfo->hash = hash;
206         hinfo->minor_hash = minor_hash;
207         return 0;
208 }