Merge git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6 into for-linus
[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 (const char *name, int len)
39 {
40         __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
41         while (len--) {
42                 __u32 hash = hash1 + (hash0 ^ (*name++ * 7152373));
43
44                 if (hash & 0x80000000) hash -= 0x7fffffff;
45                 hash1 = hash0;
46                 hash0 = hash;
47         }
48         return (hash0 << 1);
49 }
50
51 static void str2hashbuf(const char *msg, int len, __u32 *buf, int num)
52 {
53         __u32   pad, val;
54         int     i;
55
56         pad = (__u32)len | ((__u32)len << 8);
57         pad |= pad << 16;
58
59         val = pad;
60         if (len > num*4)
61                 len = num * 4;
62         for (i=0; i < len; i++) {
63                 if ((i % 4) == 0)
64                         val = pad;
65                 val = msg[i] + (val << 8);
66                 if ((i % 4) == 3) {
67                         *buf++ = val;
68                         val = pad;
69                         num--;
70                 }
71         }
72         if (--num >= 0)
73                 *buf++ = val;
74         while (--num >= 0)
75                 *buf++ = pad;
76 }
77
78 /*
79  * Returns the hash of a filename.  If len is 0 and name is NULL, then
80  * this function can be used to test whether or not a hash version is
81  * supported.
82  *
83  * The seed is an 4 longword (32 bits) "secret" which can be used to
84  * uniquify a hash.  If the seed is all zero's, then some default seed
85  * may be used.
86  *
87  * A particular hash version specifies whether or not the seed is
88  * represented, and whether or not the returned hash is 32 bits or 64
89  * bits.  32 bit hashes will return 0 for the minor hash.
90  */
91 int ext3fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
92 {
93         __u32   hash;
94         __u32   minor_hash = 0;
95         const char      *p;
96         int             i;
97         __u32           in[8], buf[4];
98
99         /* Initialize the default seed for the hash checksum functions */
100         buf[0] = 0x67452301;
101         buf[1] = 0xefcdab89;
102         buf[2] = 0x98badcfe;
103         buf[3] = 0x10325476;
104
105         /* Check to see if the seed is all zero's */
106         if (hinfo->seed) {
107                 for (i=0; i < 4; i++) {
108                         if (hinfo->seed[i])
109                                 break;
110                 }
111                 if (i < 4)
112                         memcpy(buf, hinfo->seed, sizeof(buf));
113         }
114
115         switch (hinfo->hash_version) {
116         case DX_HASH_LEGACY:
117                 hash = dx_hack_hash(name, len);
118                 break;
119         case DX_HASH_HALF_MD4:
120                 p = name;
121                 while (len > 0) {
122                         str2hashbuf(p, len, in, 8);
123                         half_md4_transform(buf, in);
124                         len -= 32;
125                         p += 32;
126                 }
127                 minor_hash = buf[2];
128                 hash = buf[1];
129                 break;
130         case DX_HASH_TEA:
131                 p = name;
132                 while (len > 0) {
133                         str2hashbuf(p, len, in, 4);
134                         TEA_transform(buf, in);
135                         len -= 16;
136                         p += 16;
137                 }
138                 hash = buf[0];
139                 minor_hash = buf[1];
140                 break;
141         default:
142                 hinfo->hash = 0;
143                 return -1;
144         }
145         hash = hash & ~1;
146         if (hash == (EXT3_HTREE_EOF << 1))
147                 hash = (EXT3_HTREE_EOF-1) << 1;
148         hinfo->hash = hash;
149         hinfo->minor_hash = minor_hash;
150         return 0;
151 }