Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
hash.c
Go to the documentation of this file.
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 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 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  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) {
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;
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;
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 == (EXT4_HTREE_EOF_32BIT << 1))
204  hash = (EXT4_HTREE_EOF_32BIT - 1) << 1;
205  hinfo->hash = hash;
206  hinfo->minor_hash = minor_hash;
207  return 0;
208 }