PERFORCE change 187277 for review
Zheng Liu
lz at FreeBSD.org
Wed Dec 29 07:18:44 UTC 2010
http://p4web.freebsd.org/@@187277?ac=10
Change 187277 by lz at 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>
More information about the p4-projects
mailing list