Date: Wed, 29 Dec 2010 07:18:43 GMT From: Zheng Liu <lz@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 187277 for review Message-ID: <201012290718.oBT7Ihch069459@skunkworks.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://p4web.freebsd.org/@@187277?ac=10 Change 187277 by lz@gnehzuil-freebsd on 2010/12/29 07:17:36 Make ext4fs can support 3 types of hash function: MD4, Legacy and TEA. * Create two new files (ext4_hash.[ch]) to save hash functions. * Add 2 new hash functions: TEA and Legacy. * Make all hash functions under MIT liencse. I have sent an email to author for asking to relicense their license into BSD license. Affected files ... .. //depot/projects/soc2010/ext4fs/src/sys/fs/ext4fs/ext4_hash.c#1 add .. //depot/projects/soc2010/ext4fs/src/sys/fs/ext4fs/ext4_hash.h#1 add .. //depot/projects/soc2010/ext4fs/src/sys/fs/ext4fs/ext4_htree.c#4 edit .. //depot/projects/soc2010/ext4fs/src/sys/fs/ext4fs/ext4_htree.h#3 edit .. //depot/projects/soc2010/ext4fs/src/sys/modules/ext4fs/Makefile#3 edit Differences ... ==== //depot/projects/soc2010/ext4fs/src/sys/fs/ext4fs/ext4_htree.c#4 (text+ko) ==== @@ -42,6 +42,7 @@ #include <fs/ext4fs/ext4_dinode.h> #include <fs/ext4fs/ext4_dir.h> #include <fs/ext4fs/ext4_htree.h> +#include <fs/ext4fs/ext4_hash.h> static int ext4_get_limit(struct dirindex_entry *); static int ext4_root_limit(struct inode *, int); @@ -52,186 +53,6 @@ static int ext4_get_next_block(struct vnode *, u_int32_t, struct dirindex_frame *, struct dirindex_frame *, u_int32_t *); -static u_int32_t half_md4_transform(u_int32_t [], u_int32_t []); -static void str2hashbuf_signed(const char *, int, u_int32_t *, int); -static void str2hashbuf_unsigned(const char *, int, u_int32_t *, int); - -/* - * Constants for MD4Transform routine. - */ -#define S11 3 -#define S12 7 -#define S13 11 -#define S14 19 -#define S21 3 -#define S22 5 -#define S23 9 -#define S24 13 -#define S31 3 -#define S32 9 -#define S33 11 -#define S34 15 - -/* F, G and H are basic MD4 functions. - */ -#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) -#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) -#define H(x, y, z) ((x) ^ (y) ^ (z)) - -/* ROTATE_LEFT rotates x left n bits. - */ -#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) - -/* FF, GG and HH are transformations for rounds 1, 2 and 3 */ -/* Rotation is separate from addition to prevent recomputation */ -#define FF(a, b, c, d, x, s) { \ - (a) += F ((b), (c), (d)) + (x); \ - (a) = ROTATE_LEFT ((a), (s)); \ - } -#define GG(a, b, c, d, x, s) { \ - (a) += G ((b), (c), (d)) + (x) + (u_int32_t)0x5a827999; \ - (a) = ROTATE_LEFT ((a), (s)); \ - } -#define HH(a, b, c, d, x, s) { \ - (a) += H ((b), (c), (d)) + (x) + (u_int32_t)0x6ed9eba1; \ - (a) = ROTATE_LEFT ((a), (s)); \ - } - -/* - * MD4 basic transformation. Transforms state based on block. - * - * XXX: we just implement a half md4 algorithm because Linux uses - * this algoirhtm. This function copies from kern/md4c.c file and - * is modified according to Linux's implementation. - */ -static u_int32_t -half_md4_transform(u_int32_t buf[4], u_int32_t in[8]) -{ - u_int32_t a = buf[0], b = buf[1], c = buf[2], d = buf[3]; - - /* Round 1 */ - FF (a, b, c, d, in[ 0], S11); /* 1 */ - FF (d, a, b, c, in[ 1], S12); /* 2 */ - FF (c, d, a, b, in[ 2], S13); /* 3 */ - FF (b, c, d, a, in[ 3], S14); /* 4 */ - FF (a, b, c, d, in[ 4], S11); /* 5 */ - FF (d, a, b, c, in[ 5], S12); /* 6 */ - FF (c, d, a, b, in[ 6], S13); /* 7 */ - FF (b, c, d, a, in[ 7], S14); /* 8 */ - - /* Round 2 */ - GG (a, b, c, d, in[ 1], S21); /* 17 */ - GG (d, a, b, c, in[ 3], S22); /* 18 */ - GG (c, d, a, b, in[ 5], S23); /* 19 */ - GG (b, c, d, a, in[ 7], S24); /* 20 */ - GG (a, b, c, d, in[ 0], S21); /* 21 */ - GG (d, a, b, c, in[ 2], S22); /* 22 */ - GG (c, d, a, b, in[ 4], S23); /* 23 */ - GG (b, c, d, a, in[ 6], S24); /* 24 */ - - /* Round 3 */ - HH (a, b, c, d, in[ 3], S31); /* 33 */ - HH (d, a, b, c, in[ 7], S32); /* 34 */ - HH (c, d, a, b, in[ 2], S33); /* 35 */ - HH (b, c, d, a, in[ 6], S34); /* 36 */ - HH (a, b, c, d, in[ 1], S31); /* 37 */ - HH (d, a, b, c, in[ 5], S32); /* 38 */ - HH (c, d, a, b, in[ 0], S33); /* 39 */ - HH (b, c, d, a, in[ 4], S34); /* 40 */ - - buf[0] += a; - buf[1] += b; - buf[2] += c; - buf[3] += d; - - return buf[1]; /* "most hashed" word */ -} - -/* - * It does not implement signed version of str2hashbuf function in Haiku. - * But in Linux, the difference between signed's and unsigned's just - * is variable type. - */ -static void -str2hashbuf_signed(const char *msg, int len, u_int32_t *buf, int num) -{ - u_int32_t pad, val; - int i, cnt, max_len, remain; - const signed char *scp = (const signed char *)msg; - - pad = (u_int32_t)len; - pad = (pad << 8) | pad; - pad = (pad << 16) | pad; - - max_len = num * 4; - if (len > max_len) - len = max_len; - - cnt = len / 4; - - for (i = 0; i < cnt; i++) { - val = (pad << 8) | *(scp++); - val = (val << 8) | *(scp++); - val = (val << 8) | *(scp++); - val = (val << 8) | *(scp++); - buf[i] = val; - } - - if (cnt < num) { - remain = len % 4; - val = pad; - for (i = 0; i < remain; i++) - val = (val << 8) + *(scp++); - - buf[cnt] = val; - - for (i = cnt + 1; i < num; i++) - buf[i] = pad; - } -} - -/* - * Refer Haiku's implementation. This implemention is MIT license. - * So the kernel can not be contaminated. - */ -static void -str2hashbuf_unsigned(const char *msg, int len, u_int32_t *buf, int num) -{ - u_int32_t pad, val; - int i, cnt, max_len, remain; - const unsigned char *ucp = (const unsigned char *)msg; - - pad = (u_int32_t)len; - pad = (pad << 8) | pad; - pad = (pad << 16) | pad; - - max_len = num * 4; - if (len > max_len) - len = max_len; - - cnt = len / 4; - - for (i = 0; i < cnt; i++) { - val = (pad << 8) | *(ucp++); - val = (val << 8) | *(ucp++); - val = (val << 8) | *(ucp++); - val = (val << 8) | *(ucp++); - buf[i] = val; - } - - if (cnt < num) { - remain = len % 4; - val = pad; - for (i = 0; i < remain; i++) - val = (val << 8) + *(ucp++); - - buf[cnt] = val; - - for (i = cnt + 1; i < num; i++) - buf[i] = pad; - } -} - int ext4_is_dirindex(struct inode *ip) { @@ -320,12 +141,32 @@ hash = buf[1]; break; case DIRINDEX_HASH_LEGACY: + hash = legacy_hash_signed(name, namelen); break; case DIRINDEX_HASH_LEGACY_UNSIGNED: + hash = legacy_hash_unsigned(name, namelen); break; case DIRINDEX_HASH_TEA: + p = name; + while (namelen > 0) { + str2hashbuf_signed(p, namelen, in, 4); + TEA_transform(buf, in); + name -= 16; + p += 16; + } + minhash = buf[1]; + hash = buf[0]; break; case DIRINDEX_HASH_TEA_UNSIGNED: + p = name; + while (namelen > 0) { + str2hashbuf_unsigned(p, namelen, in, 4); + TEA_transform(buf, in); + name -= 16; + p += 16; + } + minhash = buf[1]; + hash = buf[0]; break; default: hp->di_hash = 0; ==== //depot/projects/soc2010/ext4fs/src/sys/fs/ext4fs/ext4_htree.h#3 (text+ko) ==== @@ -94,7 +94,7 @@ u_int32_t *di_seed; }; -/* ext2_htree.c */ +/* ext4_htree.c */ int ext4_is_dirindex(struct inode *); int ext4_dirindex_lookup(struct vnode *, char *, int, doff_t *, struct buf **, doff_t *prevoffp); ==== //depot/projects/soc2010/ext4fs/src/sys/modules/ext4fs/Makefile#3 (text+ko) ==== @@ -5,6 +5,6 @@ SRCS= opt_ddb.h opt_quota.h opt_suiddir.h vnode_if.h \ ext4_alloc.c ext4_balloc.c ext4_bmap.c ext4_extents.c \ ext4_inode.c ext4_inode_cnv.c ext4_lookup.c ext4_subr.c \ - ext4_vfsops.c ext4_vnops.c ext4_htree.c + ext4_vfsops.c ext4_vnops.c ext4_htree.c ext4_hash.c .include <bsd.kmod.mk>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201012290718.oBT7Ihch069459>