blob: 1555024e3b36b26a56f8a7c47f191740171f9934 [file] [log] [blame]
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001/*
Mingming Cao617ba132006-10-11 01:20:53 -07002 * linux/fs/ext4/hash.c
Dave Kleikampac27a0e2006-10-11 01:20:50 -07003 *
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>
Mingming Caodab291a2006-10-11 01:21:01 -070013#include <linux/jbd2.h>
Mingming Cao617ba132006-10-11 01:20:53 -070014#include <linux/ext4_fs.h>
Dave Kleikampac27a0e2006-10-11 01:20:50 -070015#include <linux/cryptohash.h>
16
17#define DELTA 0x9E3779B9
18
19static 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 */
38static __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
51static 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 */
Mingming Cao617ba132006-10-11 01:20:53 -070091int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
Dave Kleikampac27a0e2006-10-11 01:20:50 -070092{
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;
Mingming Cao617ba132006-10-11 01:20:53 -0700146 if (hash == (EXT4_HTREE_EOF << 1))
147 hash = (EXT4_HTREE_EOF-1) << 1;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700148 hinfo->hash = hash;
149 hinfo->minor_hash = minor_hash;
150 return 0;
151}