home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1989 / 07 / menico.lst < prev    next >
File List  |  1989-06-10  |  10KB  |  275 lines
  1.  
  2. _FASTER STRING SEARCHES_
  3. by Costas Menico
  4.  
  5. [LISTIN╟ ONE]
  6.  
  7.  
  8. ;====================================================================
  9. ;       Faster string search routine to substitute the POS()
  10. ;       function in Turbo Pascal 4 or 5. Based on the Boyer-Moore
  11. ;       algorithm.
  12. ;       Program author: Costas Menico.
  13. ;       Declare as follows:
  14. ;       {$F+}
  15. ;       {$L search.obj}
  16. ;       function posbm(pat,str:string): byte; external;
  17. ;       Call as follows from Turbo 4 or Turbo 5
  18. ;       location := posbm(pat, str);
  19. ;====================================================================
  20.  
  21. skiparrlength equ 256           ; Length of the skip array
  22.  
  23. ; Function work stack
  24. dstk    struc
  25. patlen  dw      ?               ; pattern length (also BP base work area)
  26. strlen  dw      ?               ; string length
  27. skiparr db      skiparrlength dup(?)    ; skip array
  28. pattxt  dd      0               ; pattern address
  29. strtxt  dd      0               ; string text address
  30. dstk    ends
  31.  
  32. ; Total stack (Callers plus work stack)
  33. cstk    struc
  34. ourdata db      size dstk dup(?); work stack size
  35. bpsave  dw      0               ; save bp here
  36. retaddr dd      0               ; points to return address
  37. straddr dd      0               ; points to string address
  38. pataddr dd      0               ; points to pattern address
  39. cstk    ends
  40.  
  41. paramsize equ size pataddr + size straddr ; Size of parameter list.
  42.  
  43. public  posbm                   ; Function name declaration
  44.  
  45. code    segment para public 'code'
  46.         assume cs:code
  47. ;
  48. ; ---- Entry point to POSBM function.
  49. ;
  50. posbm   proc    far
  51.         push    bp              ; Save BP
  52.         sub     sp, size dstk   ; Create work area
  53.         mov     bp, sp          ; Adjust our base pointer
  54.  
  55.         push    ds              ; Save callers data segment
  56.  
  57.         xor     ah, ah          ; Clear register and
  58.         cld                     ; Set direction flag
  59.  
  60. ; Get and save the length and address of the pattern
  61.         lds     si, [bp.pataddr];
  62.         mov     word ptr [bp.pattxt][2], ds
  63.         lodsb                   ; Get length of pattern (1 byte)
  64.         or      al, al          ; If pattern length is null then exit
  65.         jne     notnullp
  66.         jmp     nomatch
  67.  
  68. notnullp:
  69.         mov     cx, ax          ; Save length to check if 1 later.
  70.  
  71.         mov     [bp.patlen], ax ; Save length of pattern
  72.         mov     word ptr [bp.pattxt], si; Save address
  73.  
  74. ; Get and save the length and address of the string text
  75.         lds     si, [bp.straddr]
  76.         mov     word ptr [bp.strtxt][2], ds
  77.         lodsb                   ; Get length of string
  78.         or      al, al          ; If string text is null then exit
  79.         jne     notnulls
  80.         jmp     nomatch
  81.  
  82. notnulls:
  83.         mov     [bp.strlen], ax ; Save length of string
  84.         mov     word ptr [bp.strtxt], si; Save address
  85.  
  86.         cmp     cx, 1           ; Is length of pattern 1 char?
  87.         jne     do_boyer_moore  ; No - Do Boyer-Moore.
  88.         lds     si, [bp.pattxt] ; Yes - Do a straight search.
  89.         lodsb                   ; Get the single character pattern.
  90.         les     di, [bp.strtxt] ; Get the address of the string.
  91.         mov     cx, [bp.strlen] ; Get length of string.
  92.         repne   scasb           ; Search.
  93.         jz      match1          ; Found - Adjust last DI pos.
  94.         jmp     nomatch         ; Not Found - Exit.
  95. match1:
  96.         mov     si, di          ; Transfer DI pos to SI.
  97.         sub     si, 2           ; Adjust SI position.
  98.         jmp     exactmatch      ; Determin offset
  99.  
  100. do_boyer_moore:
  101.  
  102. ; Fill the ascii character skiparray with the
  103. ; length of the pattern
  104.         lea     di, [bp.skiparr]        ; Get skip array address
  105.         mov     dx, ss
  106.         mov     es, dx
  107.         mov     al,byte ptr [bp.patlen] ; Get size of pattern
  108.         mov     ah,al                   ; Put in to AH as well
  109.         mov     cx, skiparrlength / 2   ; Get size of array
  110.         rep     stosw                   ; Fill with length of pat
  111.  
  112. ; Replace in the ascii skiparray the corresponding
  113. ; character offset from the end of the pattern minus 1
  114.         lds     si, [bp.pattxt] ; Get pattern address
  115.         lea     bx, [bp.skiparr]; Get skip array address
  116.         mov     cx, [bp.patlen] ; Get length minus one.
  117.         dec     cx
  118.  
  119.         mov     bx, bp          ; save BP
  120.         lea     bp, [bp.skiparr]; Get skip array address
  121.         xor     ah, ah
  122. fill_skiparray:
  123.         lodsb                   ; Get character from pattern
  124.         mov     di, ax          ; Use it as an index
  125.         mov     [bp+di], cl     ; Store its offset in to skip array
  126.         loop    fill_skiparray
  127.  
  128.         lodsb
  129.         mov     di, ax
  130.         mov     [bp+di], cl     ; Store the last skip value
  131.         mov     bp, bx          ; Recover BP
  132.  
  133. ; Now initialize our pattern and string text pointers to
  134. ; start searching
  135.         lds     si, [bp.strtxt] ; Get the string address.
  136.         lea     di, [bp.skiparr]; Get the skip array address.
  137.         mov     dx, [bp.strlen] ; Get the string length.
  138.         dec     dx              ;   minus 1 for eos check.
  139.         mov     ax, [bp.patlen] ; Get the pattern length.
  140.         dec     ax              ; Starting skip value.
  141.         xor     bh, bh          ; Zero high of BX.
  142.         std                     ; Set to reverse compare.
  143.  
  144. ; Get character from text. Use the character as an index
  145. ; in to the skip array, looking for a skip value of 0 .
  146. ; If found, execute a brute force search on the pattern.
  147. searchlast:
  148.         sub     dx, ax          ; Check if string exhausted.
  149.         jc      nomatch         ; Yes - no match.
  150.         add     si, ax          ; No - slide pattern with skip value.
  151.         mov     bl, [si]        ; Get character, use as an index
  152.         mov     al, ss:[di+bx]  ;   and get the new skip value.
  153.         or      al, al          ; If 0, then possible match
  154.         jne     searchlast      ;   try again by sliding to right.
  155.  
  156. ; We have a possible match, therefore
  157. ; do the reverse Brute-force compare
  158.         mov     bx, si          ; Save string address.
  159.         mov     cx, [bp.patlen] ; Get pattern length.
  160.         les     di, [bp.pattxt] ; Get pattern address
  161.         dec     di              ;  adjust
  162.         add     di, cx          ;  and add to point to eos.
  163.         repe    cmpsb           ; Do reverse compare.
  164.         je      exactmatch      ; If equal we found a match
  165.         mov     ax, 1           ;   else set skip value to 1.
  166.         lea     di, [bp.skiparr]; Get address of skip array.
  167.         mov     si, bx          ; Get address of string.
  168.         xor     bh, bh          ; No - Zero high of BX.
  169.         jmp short searchlast    ; Try again.
  170.  
  171. exactmatch:
  172.         mov     ax, si          ; Save current position in string.
  173.         lds     si, [bp.strtxt] ; Get start of strtxt.
  174.         sub     ax, si          ; Subtract and add 2 to get position
  175.         add     ax, 2           ;   in strtxt where pattern is found.
  176.         jmp     short endsearch ; Exit function
  177.  
  178. nomatch:
  179.         xor     ax, ax          ; No match, return a 0
  180.  
  181. endsearch:
  182.         cld
  183.         pop     ds              ; Recover DS for Turbo Pascal
  184.  
  185.         mov     sp, bp          ; Recover last stack position.
  186.         add     sp, size dstk   ; Clear up work area.
  187.         pop     bp              ; Recover BP
  188.         ret     paramsize       ; Return with ax the POSBM value.
  189. posbm   endp
  190.  
  191. code    ends
  192. end
  193.  
  194.  
  195. [LISTIN╟ TWO]
  196.  
  197. { -- Benchmark program to demonstrate the speed difference
  198.   -- between the POS() in Turbo Pascal 4 or 5 brute-force
  199.   -- and the Boyer-Moore Method function POSBM()
  200.   -- Program Author: Costas Menico
  201. }
  202. program search;
  203. uses dos,crt;
  204.  
  205. { -- Link in the POSBM Boyer-Moore function -- }
  206. {$F+}
  207. {$L POSBM}
  208. function posbm(pat,str:string):byte; external;
  209.  
  210. { Prints bencmark timing information }
  211. procedure showtime(s:string; t: registers);
  212. begin
  213.   writeln(s,' Hrs:',t.ch,' Min:',t.cl,' Sec:',t.dh,' Milsec:',t.dl);
  214. end;
  215.  
  216. var
  217.   pat,str: string;
  218.   i:integer;
  219.   j:integer;
  220.   start,finish: registers;
  221.  
  222. const
  223.   longloop = 2000;
  224.  
  225. begin
  226.  
  227.   clrscr;
  228.  
  229.   { -- Create a random string of length 255 -- }
  230.   randomize;
  231.   for i:=1 to 255 do str[i]:=chr(random(255)+1);
  232.   str[0]:=chr(255);
  233.  
  234.   { -- Initialize a pattern string with the last five characters
  235.     -- in the random string as the pattern to search for. -- }
  236.   pat:=copy(str,251,5);
  237.  
  238.   { -- First do a search with the regular POS function -- }
  239.   writeln('Search using Brute-Force Method');
  240.   start.ah := $2c;
  241.   msdos(start);       { -- Get start time -- }
  242.  
  243.   for j:=1 to longloop do
  244.     i:=pos(pat,str);  { -- Do search a few times Brute-Force -- }
  245.  
  246.   finish.ah := $2c;   { -- Get finish time -- }
  247.   msdos(finish);
  248.  
  249.   showtime('Start ',start);    { -- Show start time -- }
  250.   showtime('Finish',finish);   { -- Show finish time -- }
  251.   writeln('Pattern found at =',i); { -- Print string position -- }
  252.   writeln;
  253.  
  254.   { -- Now do search with the POSBM() (Boyer-Moore) function -- }
  255.   writeln('Search using Boyer-Moore Method');
  256.   start.ah := $2c;
  257.   msdos(start);       { -- Get start time -- }
  258.  
  259.   for j:=1 to longloop do
  260.     i:=posbm(pat,str);{ -- Do search a few times Boyer-Moore -- }
  261.  
  262.   finish.ah := $2c;   { -- Get finish time -- }
  263.   msdos(finish);
  264.  
  265.   showtime('Start ',start);    { -- Show start time -- }
  266.   showtime('Finish',finish);   { -- Show finish time -- }
  267.   writeln('Pattern found at =',i); { -- Print string position -- }
  268.  
  269.   writeln;
  270.   writeln('DONE.. PRESS ENTER');
  271.   readln;
  272. end.
  273.  
  274.  
  275.