* dirhash.c -- Calculate the hash of a directory entry
*
* Copyright (c) 2001 Daniel Phillips
- *
+ *
* Copyright (c) 2002 Theodore Ts'o.
*
* %Begin-Header%
- * This file may be redistributed under the terms of the GNU Public
- * License.
+ * This file may be redistributed under the terms of the GNU Library
+ * General Public License, version 2.
* %End-Header%
*/
+#include "config.h"
#include <stdio.h>
+#include <string.h>
+#include <limits.h>
#include "ext2_fs.h"
#include "ext2fs.h"
+#include "ext2fsP.h"
+
+/*
+ * Keyed 32-bit hash function using TEA in a Davis-Meyer function
+ * H0 = Key
+ * Hi = E Mi(Hi-1) + Hi-1
+ *
+ * (see Applied Cryptography, 2nd edition, p448).
+ *
+ * Jeremy Fitzhardinge <jeremy@zip.com.au> 1998
+ *
+ * This code is made available under the terms of the GPL
+ */
+#define DELTA 0x9E3779B9
+
+static void TEA_transform(__u32 buf[4], __u32 const in[])
+{
+ __u32 sum = 0;
+ __u32 b0 = buf[0], b1 = buf[1];
+ __u32 a = in[0], b = in[1], c = in[2], d = in[3];
+ int n = 16;
+
+ do {
+ sum += DELTA;
+ b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
+ b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
+ } while(--n);
+
+ buf[0] += b0;
+ buf[1] += b1;
+}
/* F, G and H are basic MD4 functions: selection, majority, parity */
#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
/*
* Basic cut-down MD4 transform. Returns only 32 bits of result.
*/
-static __u32 halfMD4Transform (__u32 buf[4], __u32 const in[])
+static void halfMD4Transform (__u32 buf[4], __u32 const in[])
{
__u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
buf[1] += b;
buf[2] += c;
buf[3] += d;
-
- return buf[1]; /* "most hashed" word */
- /* Alternative: return sum of all words? */
}
#undef ROUND
#undef K3
/* The old legacy hash */
-static ext2_dirhash_t dx_hack_hash (const char *name, int len)
+static ext2_dirhash_t dx_hack_hash (const char *name, int len,
+ int unsigned_flag)
{
- __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
+ __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
+ const unsigned char *ucp = (const unsigned char *) name;
+ const signed char *scp = (const signed char *) name;
+ int c;
+
while (len--) {
- __u32 hash = hash1 + (hash0 ^ (*name++ * 7152373));
-
+ if (unsigned_flag)
+ c = (int) *ucp++;
+ else
+ c = (int) *scp++;
+ hash = hash1 + (hash0 ^ (c * 7152373));
+
if (hash & 0x80000000) hash -= 0x7fffffff;
hash1 = hash0;
hash0 = hash;
return (hash0 << 1);
}
+static void str2hashbuf(const char *msg, int len, __u32 *buf, int num,
+ int unsigned_flag)
+{
+ __u32 pad, val;
+ int i, c;
+ const unsigned char *ucp = (const unsigned char *) msg;
+ const signed char *scp = (const signed char *) msg;
+
+ pad = (__u32)len | ((__u32)len << 8);
+ pad |= pad << 16;
+
+ val = pad;
+ if (len > num*4)
+ len = num * 4;
+ for (i=0; i < len; i++) {
+ if (unsigned_flag)
+ c = (int) ucp[i];
+ else
+ c = (int) scp[i];
+
+ val = c + (val << 8);
+ if ((i % 4) == 3) {
+ *buf++ = val;
+ val = pad;
+ num--;
+ }
+ }
+ if (--num >= 0)
+ *buf++ = val;
+ while (--num >= 0)
+ *buf++ = pad;
+}
+
/*
* Returns the hash of a filename. If len is 0 and name is NULL, then
* this function can be used to test whether or not a hash version is
* supported.
- *
+ *
* The seed is an 4 longword (32 bits) "secret" which can be used to
* uniquify a hash. If the seed is all zero's, then some default seed
* may be used.
- *
+ *
* A particular hash version specifies whether or not the seed is
* represented, and whether or not the returned hash is 32 bits or 64
* bits. 32 bit hashes will return 0 for the minor hash.
+ *
+ * This function doesn't do any normalization or casefolding of the
+ * input string. To take charset encoding into account, use
+ * ext2fs_dirhash2.
+ *
*/
errcode_t ext2fs_dirhash(int version, const char *name, int len,
- const __u32 seed[4],
+ const __u32 *seed,
ext2_dirhash_t *ret_hash,
ext2_dirhash_t *ret_minor_hash)
{
__u32 hash;
__u32 minor_hash = 0;
- char *p;
- int i;
+ const char *p;
+ int i;
+ __u32 in[8], buf[4];
+ int unsigned_flag = 0;
+
+ /* Initialize the default seed for the hash checksum functions */
+ buf[0] = 0x67452301;
+ buf[1] = 0xefcdab89;
+ buf[2] = 0x98badcfe;
+ buf[3] = 0x10325476;
/* Check to see if the seed is all zero's */
- for (i=0; i < 4; i++) {
- if (seed[i])
- break;
- }
-
- if (version == EXT2_HASH_LEGACY)
- hash = dx_hack_hash(name, len);
- else if ((version == EXT2_HASH_HALF_MD4) ||
- (version == EXT2_HASH_HALF_MD4_SEED) ||
- (version == EXT2_HASH_HALF_MD4_64)) {
- char in[32];
- __u32 buf[4];
-
- if ((i == 4) || (version == EXT2_HASH_HALF_MD4)) {
- buf[0] = 0x67452301;
- buf[1] = 0xefcdab89;
- buf[2] = 0x98badcfe;
- buf[3] = 0x10325476;
- } else
- memcpy(buf, in, sizeof(buf));
- while (len) {
- if (len < 32) {
- memcpy(in, name, len);
- memset(in+len, 0, 32-len);
- hash = halfMD4Transform(buf, (__u32 *) in);
+ if (seed) {
+ for (i=0; i < 4; i++) {
+ if (seed[i])
break;
- }
- hash = halfMD4Transform(buf, (__u32 *) p);
+ }
+ if (i < 4)
+ memcpy(buf, seed, sizeof(buf));
+ }
+
+ switch (version) {
+ case EXT2_HASH_LEGACY_UNSIGNED:
+ unsigned_flag++;
+ /* fallthrough */
+ case EXT2_HASH_LEGACY:
+ hash = dx_hack_hash(name, len, unsigned_flag);
+ break;
+ case EXT2_HASH_HALF_MD4_UNSIGNED:
+ unsigned_flag++;
+ /* fallthrough */
+ case EXT2_HASH_HALF_MD4:
+ p = name;
+ while (len > 0) {
+ str2hashbuf(p, len, in, 8, unsigned_flag);
+ halfMD4Transform(buf, in);
len -= 32;
p += 32;
}
- if (version == EXT2_HASH_HALF_MD4_64)
- minor_hash = buf[2];
- } else {
+ minor_hash = buf[2];
+ hash = buf[1];
+ break;
+ case EXT2_HASH_TEA_UNSIGNED:
+ unsigned_flag++;
+ /* fallthrough */
+ case EXT2_HASH_TEA:
+ p = name;
+ while (len > 0) {
+ str2hashbuf(p, len, in, 4, unsigned_flag);
+ TEA_transform(buf, in);
+ len -= 16;
+ p += 16;
+ }
+ hash = buf[0];
+ minor_hash = buf[1];
+ break;
+ default:
*ret_hash = 0;
return EXT2_ET_DIRHASH_UNSUPP;
}
- *ret_hash = hash;
+ *ret_hash = hash & ~1;
if (ret_minor_hash)
*ret_minor_hash = minor_hash;
return 0;
-
}
+/*
+ * Returns the hash of a filename considering normalization and
+ * casefolding. This is a wrapper around ext2fs_dirhash with string
+ * encoding support based on the nls_table and the flags. Check
+ * ext2fs_dirhash for documentation on the input and output parameters.
+ */
+errcode_t ext2fs_dirhash2(int version, const char *name, int len,
+ const struct ext2fs_nls_table *charset,
+ int hash_flags, const __u32 *seed,
+ ext2_dirhash_t *ret_hash,
+ ext2_dirhash_t *ret_minor_hash)
+{
+ errcode_t r;
+ int dlen;
+
+ if (len && charset && (hash_flags & EXT4_CASEFOLD_FL)) {
+ char buff[PATH_MAX];
+ dlen = charset->ops->casefold(charset,
+ (const unsigned char *) name, len,
+ (unsigned char *) buff, sizeof(buff));
+ if (dlen < 0) {
+ if (dlen == -EINVAL)
+ goto opaque_seq;
+ return dlen;
+ }
+ r = ext2fs_dirhash(version, buff, dlen, seed, ret_hash,
+ ret_minor_hash);
+ return r;
+ }
+
+opaque_seq:
+ return ext2fs_dirhash(version, name, len, seed, ret_hash,
+ ret_minor_hash);
+}
git://git.whamcloud.com / tools / e2fsprogs.git / blobdiff