Home | History | Annotate | Download | only in ext2fs
      1 /*
      2  * dirhash.c -- Calculate the hash of a directory entry
      3  *
      4  * Copyright (c) 2001  Daniel Phillips
      5  *
      6  * Copyright (c) 2002 Theodore Ts'o.
      7  *
      8  * %Begin-Header%
      9  * This file may be redistributed under the terms of the GNU Library
     10  * General Public License, version 2.
     11  * %End-Header%
     12  */
     13 
     14 #include <stdio.h>
     15 #include <string.h>
     16 
     17 #include "ext2_fs.h"
     18 #include "ext2fs.h"
     19 
     20 /*
     21  * Keyed 32-bit hash function using TEA in a Davis-Meyer function
     22  *   H0 = Key
     23  *   Hi = E Mi(Hi-1) + Hi-1
     24  *
     25  * (see Applied Cryptography, 2nd edition, p448).
     26  *
     27  * Jeremy Fitzhardinge <jeremy (at) zip.com.au> 1998
     28  *
     29  * This code is made available under the terms of the GPL
     30  */
     31 #define DELTA 0x9E3779B9
     32 
     33 static void TEA_transform(__u32 buf[4], __u32 const in[])
     34 {
     35 	__u32	sum = 0;
     36 	__u32	b0 = buf[0], b1 = buf[1];
     37 	__u32	a = in[0], b = in[1], c = in[2], d = in[3];
     38 	int	n = 16;
     39 
     40 	do {
     41 		sum += DELTA;
     42 		b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
     43 		b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
     44 	} while(--n);
     45 
     46 	buf[0] += b0;
     47 	buf[1] += b1;
     48 }
     49 
     50 /* F, G and H are basic MD4 functions: selection, majority, parity */
     51 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
     52 #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
     53 #define H(x, y, z) ((x) ^ (y) ^ (z))
     54 
     55 /*
     56  * The generic round function.  The application is so specific that
     57  * we don't bother protecting all the arguments with parens, as is generally
     58  * good macro practice, in favor of extra legibility.
     59  * Rotation is separate from addition to prevent recomputation
     60  */
     61 #define ROUND(f, a, b, c, d, x, s)	\
     62 	(a += f(b, c, d) + x, a = (a << s) | (a >> (32-s)))
     63 #define K1 0
     64 #define K2 013240474631UL
     65 #define K3 015666365641UL
     66 
     67 /*
     68  * Basic cut-down MD4 transform.  Returns only 32 bits of result.
     69  */
     70 static void halfMD4Transform (__u32 buf[4], __u32 const in[])
     71 {
     72 	__u32	a = buf[0], b = buf[1], c = buf[2], d = buf[3];
     73 
     74 	/* Round 1 */
     75 	ROUND(F, a, b, c, d, in[0] + K1,  3);
     76 	ROUND(F, d, a, b, c, in[1] + K1,  7);
     77 	ROUND(F, c, d, a, b, in[2] + K1, 11);
     78 	ROUND(F, b, c, d, a, in[3] + K1, 19);
     79 	ROUND(F, a, b, c, d, in[4] + K1,  3);
     80 	ROUND(F, d, a, b, c, in[5] + K1,  7);
     81 	ROUND(F, c, d, a, b, in[6] + K1, 11);
     82 	ROUND(F, b, c, d, a, in[7] + K1, 19);
     83 
     84 	/* Round 2 */
     85 	ROUND(G, a, b, c, d, in[1] + K2,  3);
     86 	ROUND(G, d, a, b, c, in[3] + K2,  5);
     87 	ROUND(G, c, d, a, b, in[5] + K2,  9);
     88 	ROUND(G, b, c, d, a, in[7] + K2, 13);
     89 	ROUND(G, a, b, c, d, in[0] + K2,  3);
     90 	ROUND(G, d, a, b, c, in[2] + K2,  5);
     91 	ROUND(G, c, d, a, b, in[4] + K2,  9);
     92 	ROUND(G, b, c, d, a, in[6] + K2, 13);
     93 
     94 	/* Round 3 */
     95 	ROUND(H, a, b, c, d, in[3] + K3,  3);
     96 	ROUND(H, d, a, b, c, in[7] + K3,  9);
     97 	ROUND(H, c, d, a, b, in[2] + K3, 11);
     98 	ROUND(H, b, c, d, a, in[6] + K3, 15);
     99 	ROUND(H, a, b, c, d, in[1] + K3,  3);
    100 	ROUND(H, d, a, b, c, in[5] + K3,  9);
    101 	ROUND(H, c, d, a, b, in[0] + K3, 11);
    102 	ROUND(H, b, c, d, a, in[4] + K3, 15);
    103 
    104 	buf[0] += a;
    105 	buf[1] += b;
    106 	buf[2] += c;
    107 	buf[3] += d;
    108 }
    109 
    110 #undef ROUND
    111 #undef F
    112 #undef G
    113 #undef H
    114 #undef K1
    115 #undef K2
    116 #undef K3
    117 
    118 /* The old legacy hash */
    119 static ext2_dirhash_t dx_hack_hash (const char *name, int len,
    120 				    int unsigned_flag)
    121 {
    122 	__u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
    123 	const unsigned char *ucp = (const unsigned char *) name;
    124 	const signed char *scp = (const signed char *) name;
    125 	int c;
    126 
    127 	while (len--) {
    128 		if (unsigned_flag)
    129 			c = (int) *ucp++;
    130 		else
    131 			c = (int) *scp++;
    132 		hash = hash1 + (hash0 ^ (c * 7152373));
    133 
    134 		if (hash & 0x80000000) hash -= 0x7fffffff;
    135 		hash1 = hash0;
    136 		hash0 = hash;
    137 	}
    138 	return (hash0 << 1);
    139 }
    140 
    141 static void str2hashbuf(const char *msg, int len, __u32 *buf, int num,
    142 			int unsigned_flag)
    143 {
    144 	__u32	pad, val;
    145 	int	i, c;
    146 	const unsigned char *ucp = (const unsigned char *) msg;
    147 	const signed char *scp = (const signed char *) msg;
    148 
    149 	pad = (__u32)len | ((__u32)len << 8);
    150 	pad |= pad << 16;
    151 
    152 	val = pad;
    153 	if (len > num*4)
    154 		len = num * 4;
    155 	for (i=0; i < len; i++) {
    156 		if ((i % 4) == 0)
    157 			val = pad;
    158 		if (unsigned_flag)
    159 			c = (int) ucp[i];
    160 		else
    161 			c = (int) scp[i];
    162 
    163 		val = c + (val << 8);
    164 		if ((i % 4) == 3) {
    165 			*buf++ = val;
    166 			val = pad;
    167 			num--;
    168 		}
    169 	}
    170 	if (--num >= 0)
    171 		*buf++ = val;
    172 	while (--num >= 0)
    173 		*buf++ = pad;
    174 }
    175 
    176 /*
    177  * Returns the hash of a filename.  If len is 0 and name is NULL, then
    178  * this function can be used to test whether or not a hash version is
    179  * supported.
    180  *
    181  * The seed is an 4 longword (32 bits) "secret" which can be used to
    182  * uniquify a hash.  If the seed is all zero's, then some default seed
    183  * may be used.
    184  *
    185  * A particular hash version specifies whether or not the seed is
    186  * represented, and whether or not the returned hash is 32 bits or 64
    187  * bits.  32 bit hashes will return 0 for the minor hash.
    188  */
    189 errcode_t ext2fs_dirhash(int version, const char *name, int len,
    190 			 const __u32 *seed,
    191 			 ext2_dirhash_t *ret_hash,
    192 			 ext2_dirhash_t *ret_minor_hash)
    193 {
    194 	__u32	hash;
    195 	__u32	minor_hash = 0;
    196 	const char	*p;
    197 	int		i;
    198 	__u32 		in[8], buf[4];
    199 	int		unsigned_flag = 0;
    200 
    201 	/* Initialize the default seed for the hash checksum functions */
    202 	buf[0] = 0x67452301;
    203 	buf[1] = 0xefcdab89;
    204 	buf[2] = 0x98badcfe;
    205 	buf[3] = 0x10325476;
    206 
    207 	/* Check to see if the seed is all zero's */
    208 	if (seed) {
    209 		for (i=0; i < 4; i++) {
    210 			if (seed[i])
    211 				break;
    212 		}
    213 		if (i < 4)
    214 			memcpy(buf, seed, sizeof(buf));
    215 	}
    216 
    217 	switch (version) {
    218 	case EXT2_HASH_LEGACY_UNSIGNED:
    219 		unsigned_flag++;
    220 	case EXT2_HASH_LEGACY:
    221 		hash = dx_hack_hash(name, len, unsigned_flag);
    222 		break;
    223 	case EXT2_HASH_HALF_MD4_UNSIGNED:
    224 		unsigned_flag++;
    225 	case EXT2_HASH_HALF_MD4:
    226 		p = name;
    227 		while (len > 0) {
    228 			str2hashbuf(p, len, in, 8, unsigned_flag);
    229 			halfMD4Transform(buf, in);
    230 			len -= 32;
    231 			p += 32;
    232 		}
    233 		minor_hash = buf[2];
    234 		hash = buf[1];
    235 		break;
    236 	case EXT2_HASH_TEA_UNSIGNED:
    237 		unsigned_flag++;
    238 	case EXT2_HASH_TEA:
    239 		p = name;
    240 		while (len > 0) {
    241 			str2hashbuf(p, len, in, 4, unsigned_flag);
    242 			TEA_transform(buf, in);
    243 			len -= 16;
    244 			p += 16;
    245 		}
    246 		hash = buf[0];
    247 		minor_hash = buf[1];
    248 		break;
    249 	default:
    250 		*ret_hash = 0;
    251 		return EXT2_ET_DIRHASH_UNSUPP;
    252 	}
    253 	*ret_hash = hash & ~1;
    254 	if (ret_minor_hash)
    255 		*ret_minor_hash = minor_hash;
    256 	return 0;
    257 }
    258