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