home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1986 / 10 / dunclst.oct < prev    next >
Text File  |  1986-10-31  |  7KB  |  204 lines
  1.  
  2. LISTING 1 for OCT 86 16-BIT TOOLBOX COLUMN
  3. ------------------------------------------
  4.  
  5.  
  6. ;
  7. ; Boyer-Moore text matching algorithm 
  8. ; described in Scientific American Sept. 1984, pp. 67-68.
  9. ; Implemented for 8086 by Ray Duncan, June 1986. 
  10. ;
  11. ; Call with:    DS:SI = pattern address
  12. ;               AX    = pattern length  
  13. ;               ES:DI = address of string to be searched
  14. ;               DX    = length of string to be searched
  15. ;               assumes "CTAB" in same segment as pattern string
  16. ;
  17. ; Returns:      CY    = True if no match
  18. ;               or      
  19. ;               CY    = False if match, and
  20. ;               ES:DI = pointer to matched string 
  21.  
  22. boyer   proc    near
  23.  
  24.         mov     bp,si           ; save pattern offset
  25.         push    di              ; save searched string offset
  26.         push    es              ; save searched string segment
  27.         push    dx              ; save searched string length
  28.         push    ds
  29.         pop     es              ; point to table with ES
  30.  
  31.         mov     cx,256          ; initialize all of table 
  32.         mov     di,offset ctab  ; to length of pattern
  33.         cld
  34.         rep stosb
  35.  
  36.         dec     ax              ; AX = pattern length - 1 
  37.         xor     cx,cx           ; init pattern char. counter
  38.         xor     bh,bh           ; BX will be used to index,
  39.                                 ; with char in the lower half
  40.  
  41. b1:                             ; build table of increments                     
  42.                                 ; for each possible char. value
  43.         mov     bl,[si]         ; get character
  44.         mov     dx,ax           ; calc distance from end
  45.         sub     dx,cx           ; of pattern
  46.         mov     [bx+ctab],dl    ; put into table 
  47.         inc     si              ; advance through pattern
  48.         inc     cx
  49.         cmp     cx,ax           ; done with pattern?
  50.         jne     b1              ; no, loop
  51.  
  52.         pop     dx              ; restore searched string length
  53.         pop     es              ; restore searched string segment
  54.         pop     di              ; restore searched string offset
  55.         std                     ; strings will be compared
  56.                                 ; from their ends backwards
  57.  
  58. b2:     mov     si,bp           ; get pattern addr
  59.         add     di,ax           ; point to ends of strings
  60.         add     si,ax
  61.         mov     cx,ax           ; get length to compare
  62.         inc     cx
  63.         repz cmpsb              ; now compare strings
  64.         jz      b3              ; jump if whole string matched
  65.         inc     di              ; point to mismatched char 
  66.         mov     bl,es:[di]      ; and fetch it, then
  67.         mov     bl,[bx+ctab]    ; get displacement amount
  68.         sub     di,cx           ; restore searched string address
  69.         add     di,bx           ; update searched string pointer
  70.         sub     dx,bx           ; update remaining length
  71.         cmp     dx,ax           ; enough left to compare again?
  72.         ja      b2              ; jump if searched string not exhausted
  73.         stc                     ; no match, return CY=True 
  74.         jmp     b4
  75.  
  76. b3:     inc     di              ; match found, return CY=False
  77.         clc                     ; and ES:DI = pointer to matched string
  78.  
  79. b4:     cld                     ; return to caller with direction
  80.         ret                     ; flag cleared
  81.  
  82. boyer   endp
  83.  
  84. ;
  85. ; Table of possible byte values:  if the value exists in the pattern 
  86. ; string, its byte contains its offset from the end of the pattern.
  87. ; If the value does not occur in the pattern, its byte contains the 
  88. ; length of the pattern.
  89.  
  90. ctab    db      256 dup (?)
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98. LISTING 2  FOR OCT 86 16-BIT TOOLBOX COLUMN
  99. -------------------------------------------
  100.  
  101.  
  102. ;
  103. ; General string matching routine for 8086
  104. ; (brute force version using 8086 string primitives)
  105. ; by Ray Duncan, June 1986
  106. ;
  107. ; Call with:    DS:SI = pattern address
  108. ;               AX    = pattern length 
  109. ;               ES:DI = address of string to be searched
  110. ;               DX    = length of string to be searched
  111. ;
  112. ; Returns:      CY    = True if no match 
  113. ;               or
  114. ;               CY    = False if match, and 
  115. ;               ES:DI = pointer to matched string 
  116. ;
  117. smatch  proc    near
  118.  
  119.         mov     bp,si                   ; save pattern offset
  120.         mov     bx,ax                   ; BX := pattern length 
  121.         dec     bx                      ; decrement it by one
  122.         cld
  123.  
  124. s1:     mov     si,bp                   ; AL := first char of pattern
  125.         lodsb
  126.         mov     cx,dx                   ; remaining searched string length
  127.         repnz scasb                     ; look for match on first char.
  128.         jnz     s3                      ; searched string exhausted, exit
  129.         mov     dx,cx                   ; save new string length
  130.         mov     cx,bx                   ; get pattern length - 1
  131.         repz cmpsb                      ; compare remainder of strings
  132.         jz      s2                      ; everything matched
  133.         add     di,cx                   ; no match, restore string addr
  134.         sub     di,bx                   ; advanced by one char.
  135.         cmp     dx,bx                   ; searched string exhausted?
  136.         ja      s1                      ; some string left, try again
  137.         jmp     s3                      ; no match, jump to return 
  138.  
  139. s2:     sub     di,bx                   ; match was found,
  140.         dec     di                      ; let ES:DI = addr of matched string
  141.         clc                             ; and return CY=False
  142.         ret
  143.  
  144. s3:     stc                             ; no match, return CY=True
  145.         ret
  146.  
  147. smatch  endp
  148.  
  149.  
  150.  
  151.  
  152.  
  153. LISTING 3 for Oct 86 16-BIT TOOLBOX COLUMN
  154. ------------------------------------------
  155.  
  156.  
  157.  
  158. { -------------------------------- }
  159. {               C2I                }
  160. { Convert .COM file to Inline Code }
  161. {     by George F. Smith, 1986     }
  162. {                                  }
  163. { Sample usage:                    }
  164. {     A>C2I File.Com >File.inl     }  
  165. { -------------------------------- }
  166.  
  167. {$P1024,D-}
  168.  
  169. var
  170.    ctr,                       { LineSize counter }
  171.    bits  : byte;              { com file byte }
  172.    Com   : file of byte;      { com file handle }
  173.  
  174. const
  175.    LineSize = 70;
  176.    hex : array[0..15] of char = '0123456789ABCDEF';
  177.  
  178.  
  179. BEGIN
  180.  
  181.    Assign(Com,ParamStr(1));   { com file name from command line }
  182.    Reset(Com);
  183.  
  184.    write('InLine (  ');
  185.    ctr := 10;                 { initialize counter }
  186.  
  187.    While not eof(Com) do
  188.    begin
  189.       read(Com,bits);         { Get com data . . .  }
  190.       Write('/$',             { . . . put it inline }
  191.             hex [ bits shr 4 and $0F ] ,
  192.             hex [ bits and $0F ]       ,' ');
  193.       ctr := ctr + 5;
  194.       if ctr = LineSize then
  195.       begin
  196.          ctr := 0;            { Reset counter and }
  197.          writeln;             { start a new line  }
  198.       end;
  199.    end;
  200.    Write(' );');              { Finish inline statement }
  201.    Write(^Z);
  202.    Close(Com);
  203.  
  204. END.   { C2I }