home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / hashalg.aqm / hashalg.asm
Encoding:
Assembly Source File  |  1985-04-10  |  8.4 KB  |  289 lines
  1.     page    66,80
  2. title    HASH_IT
  3.     ;
  4.     ; A hashing algorithm test driver by William DeGrandpre, 12/84
  5.     ;
  6.     ; Features:
  7.     ;    A symbol table which is loaded once from a disk file 
  8.     ;    by block read and is accessed directly from the DTA.
  9.     ;    A short integer hash table.
  10.     ;    A table-zeroing procedure.
  11.     ;    Relative timing routines.
  12.     ;    A collision counter/reporter.
  13.     ;    Macro defined algorithm test structures
  14.     ;    Hashing algorithms, including:
  15.     ;         (1) The standard sum-of-ASCII-character values.
  16.     ;         (2) My exclusive-or procedure.
  17.     ;
  18.     ; Equates:
  19. str_len equ    6    ; length of ASCII output string
  20. nam_len equ    8    ; length of a symbol.
  21. rec_len equ    10    ; length of a record including cr-lf.
  22. nt_len    equ    100    ; number of records (names) in the table.
  23. ht_len    equ    101    ; bytes in integer hash table. Should be prime.
  24. no_iter equ    100    ; number of iterations for time test.
  25. dta_len equ    1024    ; table size allocation, at least rec_len*nt_len.
  26.     ;          
  27.     ; Macros:
  28.     ;
  29. sethsh    macro
  30.     ;     This macro sets up addresses and values for the hashing
  31.     ; procedures and defines register usage for test purposes:
  32.     ; AX and DX are used for calculations
  33.     ; BX indexes the hash table using [bx+di] addressing
  34.     push    cx        ;save count of external loops
  35.     mov    cx,nt_len    ;number of records to hash
  36.     mov    bp,ht_len    ;divisor to get remainder offset
  37.     lea    di,hsh_tbl    ;di points to hash table
  38.     lea    si,nam_tbl    ;si points to name table
  39.     ; Remember to pop CX before exiting hashing procedure
  40.     endm
  41.     ;
  42. stdtst    macro    ptitle, pprocd
  43.     local lop,notm
  44.     ;     This macro provides a standard test protocol for testing
  45.     ; all hashing procedures. It calls the procedure once to count
  46.     ; collisions and no_iter times for timing purposes.
  47.     ;
  48.     lea    dx,ptitle    ;print procedure title
  49.     call    scr_out
  50.     call    ht_clr        ;zero the hash table values
  51.     call    pprocd        ;call once for collision count
  52.     call    ht_cnt        ;count collisions
  53.     mov    fcount,dx    ;store collision count
  54.     sub    cx,cx        ;set system timer to zero
  55.     sub    dx,dx        ;using BIOS interrupt for speed
  56.     mov    ftime,dx    ;zero time in case not used
  57.     mov    ah,01
  58.     int    1ah        ;zero timer
  59.     mov    cx,no_iter    ;set up for time test
  60.     jcxz    notm        ;skip timing routine
  61. lop:    call    pprocd        ;call the procedure
  62.     loop    lop        ;until enough iterations to count
  63.     mov    ah,00        ;now get final time
  64.     int    1ah        ;read timer
  65.     mov    ftime,dx    ;assume only low word changed
  66. notm:  call    ht_stat     ;report final results
  67.     ret 
  68.     endm
  69.  
  70. staksg    segment para stack 'stack'
  71.     dw    64 dup(?)
  72. staksg    ends
  73.     ;
  74. datasg    segment para 'data'
  75. nam_tbl db    dta_len dup(?)       ;DTA and symbol list
  76. fcbr    label    byte        ;FCB 
  77. fcbdr    db    02        ;drive B
  78. fcbnm    db    "SYMBOLS "    ;file name
  79. fcbext    db    "DOC"        ;and extension
  80. fcbbl    dw    0000        ;DOS use
  81. fcbrs    dw    0000
  82. fcbdos    dd    ?
  83.     dw    ?
  84.     dt    ?
  85.     db    00
  86. fcbrn    dd    00000000
  87.     ;
  88. ftime    dw    0        ; save low word of timer here
  89. fcount    dw    0        ; save final count here
  90. hsh_tbl db    ht_len dup(?)
  91.  
  92. col_msg db    0ah,0dh,"Number of collisions: "
  93. col_cnt db    str_len dup(" ")
  94.     db    0ah,0dh,"$"
  95. tim_msg db    0ah,0dh,"Time in counts: "
  96. tim_cnt db    str_len dup(" ")
  97.     db    0ah,0dh,"$"
  98. prg_ttl db    0dh,0ah,09h,"Hashing Algorithm Test",0dh,0ah,"$"
  99. asc_ttl db    0dh,0ah,"Test 1: ASCII Sum",0dh,0ah,"$"
  100. xor_ttl db    0dh,0ah,"Test 2: XOR symbol halves",0dh,0ah,"$"
  101.         ; put any other titles here
  102. datasg    ends
  103.     ;
  104. codesg    segment para 'code'
  105. hash_it proc    far
  106.     assume cs:codesg, ds:datasg, ss:staksg, es:datasg
  107.     ;    set up for return to DOS
  108.     push    ds
  109.     sub    ax,ax
  110.     push    ax
  111.     mov    ax,datasg
  112.     mov    ds,ax
  113.     mov    es,ax
  114.     ;    end setup, now print title
  115.     lea    dx,prg_ttl
  116.     call    scr_out
  117.     call    fill_tbl       ;load symbol table
  118.     call    hsh_asc        ;test ASCII sum hash method
  119.     call    hsh_xor        ;test XOR hash method
  120.     ;     put any other test calls here
  121.     ret
  122. hash_it endp
  123.     ;
  124. scr_out proc    near
  125.     ;     This procedure prints a message with address in DX
  126.     ; on the screen using DOS interrupt 21h.
  127.     push    ax        ;save affected register
  128.     mov    ah,09
  129.     int    21h        ;do the interrupt
  130.     pop    ax        ;restore ax
  131.     ret
  132. scr_out endp
  133.     ;
  134. hsh_asc proc    near
  135.     ;     This procedure tests the hashing method in which the
  136.     ; ASCII values of each character in a symbol are summed, then
  137.     ; divided by the table length, with the remainder used as
  138.     ; the hash key. Easily implemented in high level languages.
  139.     ; The stdtst macro does all the work.
  140.     ;
  141.     stdtst    asc_ttl,asc_hsh
  142. hsh_asc endp
  143.     ;
  144. asc_hsh proc    near
  145.     ;     This procedure performs ASCII sum symbol hashing.
  146.     ; The sethsh macro establishes addressing for the test.
  147.     ;
  148.     sethsh
  149. loopa:    sub    dx,dx        ;zero dx for sum.
  150.     push    cx        ;save outer loop count
  151.     mov    cx,nam_len    ;number of bytes to sum
  152. loopb:    mov    al,[si]     ;get byte into al
  153.     cbw            ;convert to integer
  154.     add    dx,ax        ;and add to total for name
  155.     inc    si        ;next byte
  156.     loop    loopb        ;repeat until name bytes are summed
  157.     mov    ax,dx        ;set up to divide
  158.     sub    dx,dx        ;need unsigned dw dividend
  159.     div    bp        ;divide by table length
  160.     mov    bx,dx        ;remainder to index reg
  161.     inc    byte ptr [bx+di] ;increment hash table byte accessed
  162.     inc    si        ;skip cr-lf at end of record
  163.     inc    si
  164.     pop    cx        ;restore count of outer loopa
  165.     loop    loopa        ;repeat until table is done
  166.     pop    cx        ;restore external count
  167.     ret
  168. asc_hsh endp
  169.     ;
  170. hsh_xor proc    near
  171.     ;     This procedure tests an hashing algorithm which exclusive-ors
  172.     ; the first and second halves of an 8-byte symbol to create a
  173.     ; double word which is divided by the table length. The remainder
  174.     ; is then used as the hash key. Again the macro does the work.
  175.     ;
  176.     stdtst    xor_ttl,xor_hsh
  177. hsh_xor endp
  178.     ;
  179. xor_hsh proc    near
  180.     ;     This procedure performs XOR hashing of one table
  181.     ; The macro sethsh establishes addressing
  182.     ;
  183.     sethsh
  184. loopc:    mov    dx,word ptr [si]    ;first bytes to high word
  185.     mov    ax,word ptr [si+2]    ;second 2 to low
  186.     xor    dx,word ptr [si+4]    ;xor high bytes
  187.     xor    ax,word ptr [si+6]    ;then low with last 2
  188.     xor    ax,dx            ;finally xor together
  189.     sub    dx,dx            ;zero dx for dw division
  190.     div    bp            ;divide by table length
  191.     mov    bx,dx            ;remainder to index
  192.     inc    byte ptr [bx+di]    ;inc accessed byte
  193.     add    si,rec_len        ;move to next record
  194.     loop    loopc        ; repeat until table is traversed
  195.     pop    cx            ;restore external count
  196.     ret
  197. xor_hsh endp
  198.     ;
  199. fill_tbl proc    near
  200.     ;     This procedure fills the symbol table from a sequential disk
  201.     ; file. The table is filled once before the hashing algorithms are
  202.     ; tested to exclude disk i/o from algorithm timing.
  203.     ;
  204.     ; open file
  205.     lea    dx,fcbr
  206.     mov    ah,0fh
  207.     int    21h
  208.     ; set record size and DTA address
  209.     mov    fcbrs,rec_len
  210.     lea    dx,nam_tbl
  211.     mov    ah,1ah
  212.     int    21h
  213.     ; read disk file in block read. Compatible with DOS 1.1 and up
  214.     mov    cx,nt_len
  215.     lea    dx,fcbr
  216.     mov    ah,27h
  217.     int    21h
  218.     ret
  219. fill_tbl endp
  220.     ;
  221. ht_clr    proc    near
  222.     ;     This procedure zeroes the hash table. For this test, the
  223.     ; hash table is simply an array of byte integers in which a
  224.     ; count of the number of hits on that location is kept.
  225.     ;
  226.     sub    al,al        ;get a convenient zero
  227.     lea    bx,hsh_tbl    ;get table address
  228.     mov    cx,ht_len    ;set count to table length
  229. loopd:    mov    [bx],al     ;zero byte in table
  230.     inc    bx        ;set up for next byte
  231.     loop    loopd        ;repeat until table is zeroed
  232.     ret
  233. ht_clr    endp
  234.     ;
  235. ht_cnt    proc    near
  236.     ;     This procedure counts collisions in the hash table and
  237.     ; returns the result in dx.
  238.     ;
  239.     lea    bx,hsh_tbl    ;get table address
  240.     mov    cx,ht_len    ;and size
  241.     sub    ah,ah        ;zero ah for unsigned math
  242.     sub    dx,dx        ;zero dx for sum
  243. looph:    mov    al,[bx]     ;move byte to al, sure its positive
  244.     cmp    ax,1        ;0 or 1 is no collision
  245.     jbe    nxtb
  246.     dec    ax        ;allow for 1 hit
  247.     add    dx,ax        ;add collisions to sum
  248. nxtb:    inc    bx        ;move to next byte
  249.     loop    looph        ;repeat until table traversed
  250.     ret
  251. ht_cnt    endp
  252.     ;
  253. ht_stat proc    near
  254.     ;     This procedure produces the collision count and time results
  255.     ; of a hashing test.
  256.     ; 1. Display collisions
  257.     mov    ax,fcount        ;count in ax
  258.     lea    bx,col_cnt        ;where to put ASCII string
  259.     call    asc_con         ;convert count
  260.     lea    dx,col_msg        ;and print it
  261.     call    scr_out
  262.     ; 2. Display time
  263.     mov    ax,ftime        ;done same as count
  264.     lea    bx,tim_cnt
  265.     call    asc_con
  266.     lea    dx,tim_msg
  267.     call    scr_out
  268.     ret
  269. ht_stat endp
  270.     ;
  271. asc_con proc    near
  272.     ;     This procedure converts an unsigned integer in ax into a
  273.     ; str_len byte string pointed to by bx.
  274.     ;
  275.     add    bx,str_len-1    ;move to end of string space
  276.     mov    cx,str_len    ;string length in cx
  277.     mov    si,10        ;converting to base 10
  278. loopm:    sub    dx,dx        ;zero for unsigned divide
  279.     div    si
  280.     add    dl,'0'        ;make it ASCII
  281.     mov    [bx],dl     ;put character in buffer
  282.     dec    bx        ;back up to next position
  283.     loop    loopm        ;repeat until buffer is full
  284.     ret
  285. asc_con endp
  286.     ;
  287. codesg    ends
  288.     end    hash_it
  289. c    bx        ;back up to next