page@swan.ulowell.edu (Bob Page) (01/20/88)
bryce@hoser.berkeley.edu (Bryce Nesbitt) wrote:
> this hash function is valid ONLY for filesystems of type "DOS ".
That should be "DOS\0" or "DOS<NULL>", not "DOS<SPACE>".
Present and Future DOS haquers: you should check this from now on.
Since the DOS utilities all want to see 'D' 'O' 'S' as the first three
bytes of block zero (and don't care about the next byte), it is safe
to assume that future versions of the file system will have something
OTHER than '\0' there.
So, if the LSByte of block 0, longword 0 is a zero, you're using the
OLD file system. If it isn't, either the disk is trashed or you're
using a NEW file system.
..Bob
--
Bob Page, U of Lowell CS Dept. page@swan.ulowell.edu ulowell!page
"I don't know such stuff. I just do eyes." -- from 'Blade Runner'bryce@hoser.berkeley.edu (Bryce Nesbitt) (01/21/88)
[ 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