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