hash tables in asm
Colin MacIntyre
Colin
Steve
>Hey guys I'm looking for a dead simple hash table implementation in assembl=
>y, preferably NASM. I have the fnv algorithm already, now just need some in=
>spiration on how asm might do lookups into a dictionary. Can't seem to find=
> anything... but I may not be using the right keywords.
Hi,
Not exactly sure what you are asking for. So this might be
mostly noise? Comments and code from a *.GIF image translation
or creation program. With some edits to clarify [...]. MASM
16-bit code. GIF has a max ot 4096 tokens in the table. Other's
code references hopefully will give you further clues.
; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Test of LZW encoding.
Code based on, or influenced by:
D.E. Knuth's AOCP, Searching chapter, 6.4 hashing. Basicly using
a slightly munged "Open scatter table search and insertion". I use
a shift and add hash function and a non-prime table size.
Tom Pfau and David Kirschbaum's LZWCOMP3.ASM. Well sorta. Looked
at code for ideas. They use a different hash that I cannot exactly
see how it avoids errors. [... Never figured out most of that. ]
Thomas G. Lane's Independent JPEG Group's jwrgif.c. [...] I use a
serial variant of that parallel hash table. [...]
; - - - Hash table entry, [...]
Hash_rec STRUC
HCode DW ? ; Code of the symbol in slot i, or [-1] if empty slot.
HPrefix DW ? ; Symbol's prefix code; undefined if empty slot.
HSuffix DB ? ; Symbol Suffix character.
;[...]
Hash_rec ENDS
HSize EQU 5120 ; Hash table size for ~80% occupancy. Not prime [#]
; as AoCP wants.
LZWHash Hash_rec HSize DUP(<>) ; syntax for a structure.
[...]
; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
; 27 March 2008, make a hash to index the LZW token array. Use logic
; similar to Unix COMPRESS code. [ ... Input character in AX preserved.
; Also uses current Prefix value.
; Output is index / slot / table entry / pointer returned in SI. ]
INDEX:
PUSH BX ; Not sure if this is necessary...
PUSH CX ; But protect yourself while debugging.
MOV SI,AX ; Move character into Source Index register.
MOV CX,4
SHL SI,CL ; Shift to make comparable to table size.
ADD SI,[Prefix] ; Make hash dependent on both prefix and character.
CMP SI,HSize ; Too big?
JB Idx1
SUB SI,HSize ; Yep. [ Resize to remain in hash table. ]
Idx1:
; Multiply hash number by record size.
MOV BX,SI ; Five bytes per table entry.
SHL SI,1
;[...]
SHL SI,1
ADD SI,BX
ADD SI,OFFSET LZWHash ; And point into the table
POP CX
POP BX
RET
; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
; [...]
That is the hash function to create an index into the hash table.
It is then used to examine the table to see if that table entry is
empty or in use. If in use, is it the one wanted or a collision?
My code to do that is LZW/GIF specific so not posted. COMPRESS
reference from Lane C code.
Regards,
Steve N.
Nathan
wrote:
> Hey guys I'm looking for a dead simple hash table implementation in assembly, preferably NASM. I have the fnv algorithm already, now just need some inspiration on how asm might do lookups into a dictionary. Can't seem to find anything... but I may not be using the right keywords.
>
> Colin
There exist plenty of source code examples for you to examine:
http://sourceforge.net/projects/asmlib/
http://sourceforge.net/projects/hla-stdlib/
...and that's just a few links that I could think of at the moment.
You'll likely stumble into more useful source here: http://www.delicious.com/Evenbit
Hope that helps.
Nathan.
--
http://clax.inspiretomorrow.net
http://clax.inspiretomorrow.net/clax86.html
http://www.fysnet.net/faq/index.htm