From 52783e0ca72a80c549e9d266b3472f78fc61bdb2 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Mon, 11 Mar 2002 15:04:45 -0500 Subject: [PATCH] Add new function to the libext2fs library, ext2fs_dirhash, which calculates the hash of a filename for indexed directories. --- debugfs/ChangeLog | 5 +++++ debugfs/htree.c | 33 ++++++++++++++---------------- lib/ext2fs/ChangeLog | 7 +++++++ lib/ext2fs/Makefile.in | 2 ++ lib/ext2fs/dirhash.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++ lib/ext2fs/ext2_err.et.in | 3 +++ lib/ext2fs/ext2fs.h | 7 +++++++ 7 files changed, 90 insertions(+), 18 deletions(-) create mode 100644 lib/ext2fs/dirhash.c diff --git a/debugfs/ChangeLog b/debugfs/ChangeLog index 2940820..003b559 100644 --- a/debugfs/ChangeLog +++ b/debugfs/ChangeLog @@ -1,3 +1,8 @@ +2002-03-11 Theodore Tso + + * htree.c (htree_dump_leaf_node): Use the ext2_dirhash function + instead of a local static function. + 2002-03-08 Theodore Tso * Release of E2fsprogs 1.27 diff --git a/debugfs/htree.c b/debugfs/htree.c index 86909a7..a6d4eef 100644 --- a/debugfs/htree.c +++ b/debugfs/htree.c @@ -29,21 +29,6 @@ extern int optreset; /* defined by BSD, but not others */ static FILE *pager; -static unsigned dx_hack_hash (const char *name, int len) -{ - __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; - while (len--) { - __u32 hash = hash1 + (hash0 ^ (*name++ * 7152373)); - - if (hash & 0x80000000) hash -= 0x7fffffff; - hash1 = hash0; - hash0 = hash; - } - return hash0; -} - -#define dx_hash(s,n) (dx_hack_hash(s,n) << 1) - static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino, struct ext2_inode *inode, blk_t blk, char *buf) @@ -54,6 +39,7 @@ static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino, char name[EXT2_NAME_LEN]; char tmp[EXT2_NAME_LEN + 16]; blk_t pblk; + ext2_dirhash_t hash; errcode = ext2fs_bmap(fs, ino, inode, buf, 0, blk, &pblk); if (errcode) { @@ -82,8 +68,12 @@ static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino, (dirent->name_len & 0xFF) : EXT2_NAME_LEN; strncpy(name, dirent->name, thislen); name[thislen] = '\0'; + errcode = ext2fs_dirhash(0, name, thislen, &hash); + if (errcode) + com_err("htree_dump_leaf_node", errcode, + "while calculating hash"); sprintf(tmp, "%u 0x%08x (%d) %s ", dirent->inode, - dx_hash(name, thislen), dirent->rec_len, name); + hash, dirent->rec_len, name); thislen = strlen(tmp); if (col + thislen > 80) { fprintf(pager, "\n"); @@ -266,12 +256,19 @@ errout: */ void do_dx_hash(int argc, char *argv[]) { + ext2_dirhash_t hash; + errcode_t err; + if (argc != 2) { com_err(argv[0], 0, "usage: dx_hash filename"); return; } - printf("Hash of %s is 0x%0x\n", argv[1], - dx_hash(argv[1], strlen(argv[1]))); + err = ext2fs_dirhash(0, argv[1], strlen(argv[1]), &hash); + if (err) { + com_err(argv[0], err, "while caclulating hash"); + return; + } + printf("Hash of %s is 0x%0x\n", argv[1], hash); } /* diff --git a/lib/ext2fs/ChangeLog b/lib/ext2fs/ChangeLog index 952c51c..bd58b99 100644 --- a/lib/ext2fs/ChangeLog +++ b/lib/ext2fs/ChangeLog @@ -1,3 +1,10 @@ +2002-03-11 Theodore Tso + + * ext2_err.et.in (EXT2_ET_DIRHASH_UNSUPP): New error code + + * dirhash.c (ext2fs_dirhash): New function which calculates the + hash for a filename in an indexed directory. + 2002-03-08 Theodore Tso * Release of E2fsprogs 1.27 diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in index 6297abf..b302b08 100644 --- a/lib/ext2fs/Makefile.in +++ b/lib/ext2fs/Makefile.in @@ -30,6 +30,7 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \ dblist.o \ dblist_dir.o \ dirblock.o \ + dirhash.o \ dir_iterate.o \ expanddir.o \ ext_attr.o \ @@ -79,6 +80,7 @@ SRCS= ext2_err.c \ $(srcdir)/dblist.c \ $(srcdir)/dblist_dir.c \ $(srcdir)/dirblock.c \ + $(srcdir)/dirhash.c \ $(srcdir)/dir_iterate.c \ $(srcdir)/dupfs.c \ $(srcdir)/expanddir.c \ diff --git a/lib/ext2fs/dirhash.c b/lib/ext2fs/dirhash.c new file mode 100644 index 0000000..5f71c6d --- /dev/null +++ b/lib/ext2fs/dirhash.c @@ -0,0 +1,51 @@ +/* + * 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. + * %End-Header% + */ + +#include + +#include "ext2_fs.h" +#include "ext2fs.h" + +static ext2_dirhash_t dx_hack_hash (const char *name, int len) +{ + __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; + while (len--) { + __u32 hash = hash1 + (hash0 ^ (*name++ * 7152373)); + + if (hash & 0x80000000) hash -= 0x7fffffff; + hash1 = hash0; + hash0 = hash; + } + return hash0; +} + +/* + * 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. + */ +errcode_t ext2fs_dirhash(int version, const char *name, int len, + ext2_dirhash_t *ret_hash) +{ + __u32 hash; + + if (version == 0) + hash = dx_hack_hash(name, len); + else { + *ret_hash = 0; + return EXT2_ET_DIRHASH_UNSUPP; + } + *ret_hash = hash; + return 0; + +} diff --git a/lib/ext2fs/ext2_err.et.in b/lib/ext2fs/ext2_err.et.in index ab36c9d..c22e5d8 100644 --- a/lib/ext2fs/ext2_err.et.in +++ b/lib/ext2fs/ext2_err.et.in @@ -275,5 +275,8 @@ ec EXT2_ET_LOAD_EXT_JOURNAL, ec EXT2_ET_NO_JOURNAL, "Journal not found" +ec EXT2_ET_DIRHASH_UNSUPP, + "Directory hash unsupported" + end diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h index 15d0b6f..d55cd50 100644 --- a/lib/ext2fs/ext2fs.h +++ b/lib/ext2fs/ext2fs.h @@ -65,6 +65,7 @@ typedef __u32 blk_t; typedef __u32 dgrp_t; typedef __u32 ext2_off_t; typedef __s64 e2_blkcnt_t; +typedef __u32 ext2_dirhash_t; #if EXT2_FLAT_INCLUDES #include "com_err.h" @@ -406,6 +407,7 @@ typedef struct ext2_icount *ext2_icount_t; #define EXT2_LIB_FEATURE_COMPAT_SUPP (EXT2_FEATURE_COMPAT_DIR_PREALLOC|\ EXT2_FEATURE_COMPAT_IMAGIC_INODES|\ EXT3_FEATURE_COMPAT_HAS_JOURNAL|\ + EXT2_FEATURE_COMPAT_DIR_INDEX|\ EXT2_FEATURE_COMPAT_EXT_ATTR) /* This #ifdef is temporary until compression is fully supported */ @@ -599,6 +601,11 @@ extern errcode_t ext2fs_read_dir_block(ext2_filsys fs, blk_t block, extern errcode_t ext2fs_write_dir_block(ext2_filsys fs, blk_t block, void *buf); +/* dirhash.c */ +extern errcode_t ext2fs_dirhash(int version, const char *name, int len, + ext2_dirhash_t *ret_hash); + + /* dir_iterate.c */ extern errcode_t ext2fs_dir_iterate(ext2_filsys fs, ext2_ino_t dir, -- 1.8.3.1