Path: utzoo!mnetor!uunet!husc6!think!ames!ucbcad!pasteur!ucbvax!hoser!bryce
From: bryce@hoser.berkeley.edu (Bryce Nesbitt)
Newsgroups: comp.sys.amiga
Subject: AmigaLine6 - How to calulate the AmigaDOS hash function (update)
Message-ID: <22681@ucbvax.BERKELEY.EDU>
Date: 20 Jan 88 20:48:34 GMT
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: bryce@hoser.berkeley.edu (Bryce Nesbitt)
Organization: The Logic Foundation
Lines: 104

[ Sigh, AmigaLine6 contained an error, and was not as "definitive"
as I like to make them.  I'm breaking tradition by replacing it
under the same number, rather than releasing the update as
AmigaLine8.  Please kill any old AmigaLine6 you may have saved.

BTW:  Don't mail me asking for back issues... I don't provide
that service ]


----------------------------------------------------------------------------
			Technical Note #6
	    How to calulate the AmigaDOS hash function

SUMMARY

$ 6/0 How to calulate the AmigaDOS hash function
$ release 2
$ 20-Jan-88 Bryce Nesbitt (from Neil Katin) / BDI (Commodore-Amiga Inc.)
$ AmigaDOS, disk, directory, hash function, directory block, file system

    AmigaDOS uses a hashed directory structure for very rapid finding of a
file (given the complete path name).  This note gives a function to find the
hash value of a name.

----------------------------------------------------------------------------

/* hasher.c - By Bryce Nesbitt

    Calulates hash values.

    In order to find a particlar file, AmigaDOS applies the hash function
to the filename.  The resulting value is looked up in the hash table for a
particular directory.  Zero at this location indicates the file does not
exist.	A non-zero number is a key for a block.  This will either be the
proper file, or one in a chain of names which all have the same hash value.
See the AmigaDOS Technical Reference Manual for more deails.

    Remember that these hash functions will be valid ONLY for filesystems
of type "DOS\0".  This file system identifier is stored in the first long
of the boot block.

    The size of the hash table for a particular file is stored in a long
word at offset $C (12) in the root block.  Normally with 90mm disks this
will indicate that the table has $48 (72) entires.


    This example was based on examples by Neil Katin (pyramid!amiga!neil)
and Carolyn Scheppner ({allegra,ihnp4,rutgers}!cbmvax!carolyn).
*/

typedef unsigned short USHORT;
/* Remove if duplicated elsewhere */

USHORT HashString(unsigned char *,USHORT);
/* For old compilers use "USORT HashString();" */


void main( argc, argv )
int  argc;
char *argv[];
{
USHORT hashoffset;

    if( argc != 2 ) {
	printf("Calulates the offset into a 72 entry AmigaDOS hash table\n");
	printf("Usage: %s <name>\n", argv[0] );
	exit(5);
    }
    hashoffset=HashString( argv[1],72 );
    /* Don't assume the hash table size will always be 72! */
    printf( "Table entry is $%x (%d)\n", hashoffset, hashoffset );
    printf( "Byte location in block is $%x (%d)\n", (hashoffset+6)<<2,
    (hashoffset+6)<<2);
}



USHORT HashString(string,tablesize)
unsigned char  *string;
USHORT tablesize;
{
    register unsigned char c;
    register USHORT result;


    result = strlen(string);

    while( c = *string ) {
	if( c >= 'a' && c <= 'z' ) {    /* If lower case */
	    c = c - 'a'+'A';           /* Convert to upper */
	}
	result = (( result * 13 + c ) & 0x7ff);
	string++;
    }

    return( (USHORT)(result % tablesize) );
}


|\ /|  . Ack! (NAK, SOH, EOT)
{o O} . bryce@hoser.berkeley.EDU -or- ucbvax!hoser!bryce (or try "cogsci")
 (")
  U	"As an engineer, I only set the value of a product... not the cost."
	-Bryce Nesbitt