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