home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / progmisc / searchbm.zip / BM.ASM next >
Assembly Source File  |  1993-06-05  |  4KB  |  194 lines
  1. ; filename: BM.ASM
  2. ; fast search routine to search strings in ARRAYS OF CHARS
  3. ; function in Turbo Pascal >= 4. Based on the Boyer-Moore algorithm.
  4. ; program author: Costas Menico.
  5. ; Very small modifications for using an ARRAY OF CHAR buffer instead of
  6. ; a string made by Jochen Magnus in May 93.
  7. ; declare as follows:
  8. ; {$F+}
  9. ; {$L BM.OBJ}
  10. ; function posbm(pat:string; var buffer; buflen:word):WORD; external;
  11. ; call as follows from Turbo 4..7:
  12. ; location := posbm(pat, buf, buflen);
  13. ; call for a search in a string typed buffer:
  14. ; location := posbm(pat, str[1], length(str));
  15.  
  16.  
  17. skiparrlength    equ    256
  18.  
  19. ; function work stack
  20.  
  21. dstk        struc
  22. patlen        dw    ?
  23. strlen        dw    ?
  24. skiparr        db    skiparrlength dup(?)
  25. pattxt        dd    0
  26. strtxt        dd    0
  27. dstk        ends
  28.  
  29. ; total stack (callers plus work stack)
  30.  
  31. cstk        struc
  32. ourdata        db    size dstk dup(?)
  33. bpsave        dw    0
  34. retaddr        dd    0
  35. paramlen       dw   0                                   ; JO
  36. straddr        dd    0
  37. pataddr        dd    0
  38. cstk        ends
  39.  
  40. paramsize    equ    size pataddr+size straddr +size paramlen       ; +2  JO
  41.  
  42. code        segment    para public
  43.         assume cs:code
  44.  
  45. ; entry point to posbm function
  46.  
  47. posbm        proc    far
  48.         public    posbm
  49.  
  50.         push    bp
  51.              sub    sp, size dstk
  52.              mov    bp, sp
  53.              push    ds
  54.              xor    ah, ah
  55.              cld
  56.  
  57. ; get and save the length and address of the pattern
  58.  
  59.         lds    si, [bp.pataddr]
  60.              mov    word ptr [bp.pattxt][2], ds
  61.              lodsb
  62.              or    al, al
  63.              jne    notnullp
  64.              jmp    nomatch
  65.  
  66. notnullp:
  67.         mov    cx, ax
  68.              mov    [bp.patlen], ax
  69.              mov    word ptr [bp.pattxt], si
  70.  
  71. ; get and save the length and address of the string text
  72.  
  73.         lds    si, [bp.straddr]
  74.              mov    word ptr [bp.strtxt][2], ds
  75.              mov ax,[bp.paramlen]                      ; JO
  76.              or  ax,ax                                  ; JO
  77.              jne    notnulls
  78.              jmp    nomatch
  79.  
  80. notnulls:
  81.         mov    [bp.strlen], ax
  82.              mov    word ptr [bp.strtxt], si
  83.              cmp    cx, 1
  84.              jne    do_boyer_moore
  85.              lds    si, [bp.pattxt]
  86.              lodsb
  87.              les    di, [bp.strtxt]
  88.              mov    cx, [bp.strlen]
  89.              repne    scasb
  90.              jz    match1
  91.              jmp    nomatch
  92.  
  93. match1:
  94.         mov    si, di
  95.              sub    si, 2
  96.              jmp    exactmatch
  97.  
  98. do_boyer_moore:
  99.  
  100. ; fill the ASCII character skiparray with the
  101. ; length of the pattern
  102.  
  103.         lea    di, [bp.skiparr]
  104.              mov    dx, ss
  105.              mov    es, dx
  106.              mov    al, byte ptr [bp.patlen]
  107.              mov    ah, al
  108.              mov    cx, skiparrlength/2
  109.              rep    stosw
  110.  
  111. ; replace in the ASCII skiparray the corresponding
  112. ; character offset from the end of the pattern minus 1
  113.  
  114.         lds    si, [bp.pattxt]
  115.              lea    bx, [bp.skiparr]
  116.              mov    cx, [bp.patlen]
  117.              dec    cx
  118.              mov    bx, bp
  119.              lea    bp, [bp.skiparr]
  120.              xor    ah, ah
  121.  
  122. fill_skiparray:
  123.         lodsb
  124.              mov    di, ax
  125.              mov    [bp+di], cl
  126.              loop    fill_skiparray
  127.              lodsb
  128.              mov    di, ax
  129.              mov    [bp+di], cl
  130.              mov    bp, bx
  131.  
  132. ; now initialize our pattern and string text pointers to
  133. ; start searching
  134.  
  135.         lds    si, [bp.strtxt]
  136.              lea    di, [bp.skiparr]
  137.              mov    dx, [bp.strlen]
  138.              dec    dx
  139.              mov    ax, [bp.patlen]
  140.              dec    ax
  141.              xor    bh, bh
  142.              std
  143.  
  144. ; get character from text. use the character as an index
  145. ; into the skiparray, looking for a skip value of 0.
  146. ; if found, execute a brute-force search on the pattern
  147.  
  148. searchlast:
  149.         sub    dx, ax
  150.              jc    nomatch
  151.              add    si, ax
  152.              mov    bl, [si]
  153.              mov    al, ss:[di+bx]
  154.              or    al, al
  155.              jne    searchlast
  156.  
  157. ; we have a possible match, therefore
  158. ; do the reverse brute-force compare
  159.  
  160.         mov    bx, si
  161.              mov    cx, [bp.patlen]
  162.              les    di, [bp.pattxt]
  163.              dec    di
  164.              add    di, cx
  165.              repe    cmpsb
  166.              je    exactmatch
  167.              mov    ax, 1
  168.              lea    di, [bp.skiparr]
  169.              mov    si, bx
  170.              xor    bh, bh
  171.              jmp    short searchlast
  172.  
  173. exactmatch:
  174.         mov    ax, si
  175.              lds    si, [bp.strtxt]
  176.              sub    ax, si
  177.              add    ax, 2
  178.              jmp    short endsearch
  179.  
  180. nomatch:
  181.         xor    ax, ax
  182.  
  183. endsearch:
  184.         cld
  185.              pop    ds
  186.              mov    sp, bp
  187.              add    sp, size dstk
  188.              pop    bp
  189.              ret    paramsize
  190. posbm        endp
  191.  
  192. code        ends
  193.         end
  194.