home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / pctchnqs / 1991 / number4 / l3.asm < prev    next >
Assembly Source File  |  1991-07-21  |  8KB  |  161 lines
  1. ; Searches a buffer for a specified pattern. In case of a mismatch,
  2. ; uses the value of the mismatched byte to skip across as many
  3. ; potential match locations as possible (partial Boyer-Moore).
  4. ; Returns start offset of first match searching forward, or NULL if
  5. ; no match is found.
  6. ; Tested with TASM 2.0.
  7. ; C near-callable as:
  8. ;       unsigned char * FindString(unsigned char * BufferPtr,
  9. ;          unsigned int BufferLength, unsigned char * PatternPtr,
  10. ;          unsigned int PatternLength);
  11.  
  12. parms   struc
  13.         dw      2 dup(?) ;pushed BP & return address
  14. BufferPtr dw    ?       ;pointer to buffer to be searched
  15. BufferLength dw ?       ;# of bytes in buffer to be searched
  16. PatternPtr dw   ?       ;pointer to pattern for which to search
  17. PatternLength dw ?      ;length of pattern for which to search
  18. parms   ends
  19.  
  20.         .model small
  21.         .code
  22.         public _FindString
  23. _FindString     proc    near
  24.         cld
  25.         push    bp      ;preserve caller's stack frame
  26.         mov     bp,sp   ;point to our stack frame
  27.         push    si      ;preserve caller's register variables
  28.         push    di
  29.         sub     sp,256*2 ;allocate space for SkipTable
  30. ; Create the table of distances by which to skip ahead on mismatches
  31. ; for every possible byte value. First, initialize all skips to the
  32. ; pattern length; this is the skip distance for bytes that don't
  33. ; appear in the pattern.
  34.         mov     ax,[bp+PatternLength]
  35.         and     ax,ax   ;return an instant match if the pattern is
  36.         jz      InstantMatch ; 0-length
  37.         mov     di,ds
  38.         mov     es,di   ;ES=DS=SS
  39.         mov     di,sp   ;point to SkipBuffer
  40.         mov     cx,256
  41.         rep     stosw
  42.         dec     ax                      ;from now on, we only need
  43.         mov     [bp+PatternLength],ax   ; PatternLength - 1
  44. ; Point to last (rightmost) byte of first potential pattern match
  45. ; location in buffer.
  46.         add     [bp+BufferPtr],ax
  47. ; Reject if buffer is too small, and set the count of the number of
  48. ; potential pattern match locations in the buffer.
  49.         sub     [bp+BufferLength],ax
  50.         jbe     NoMatch
  51. ; Set the skip values for the bytes that do appear in the pattern to
  52. ; the distance from the byte location to the end of the pattern. When
  53. ; there are multiple instances of the same byte, the rightmost
  54. ; instance's skip value is used. Note that the rightmost byte of the
  55. ; pattern isn't entered in the skip table; if we get that value for a
  56. ; mismatch, we know for sure that the right end of the pattern has
  57. ; already passed the mismatch location, so this is not a relevant byte
  58. ; for skipping purposes.
  59.         mov     si,[bp+PatternPtr] ;point to start of pattern
  60.         and     ax,ax   ;are there any skips to set?
  61.         jz      SetSkipDone ;no
  62.         mov     di,sp   ;point to SkipBuffer
  63. SetSkipLoop:
  64.         sub     bx,bx   ;prepare for word addressing off byte value
  65.         mov     bl,[si] ;get the next pattern byte
  66.         inc     si      ;advance the pattern pointer
  67.         shl     bx,1    ;prepare for word look-up
  68.         mov     [di+bx],ax ;set the skip value when this byte value is
  69.                         ; the mismatch value in the buffer
  70.         dec     ax
  71.         jnz     SetSkipLoop
  72. SetSkipDone:
  73.         mov     dl,[si] ;DL=rightmost pattern byte from now on
  74.         dec     si      ;point to next-to-rightmost byte of pattern
  75.         mov     [bp+PatternPtr],si ; from now on
  76. ; Search the buffer.
  77.         std                     ;for backward REPZ CMPSB
  78.         mov     di,[bp+BufferPtr] ;point to the first search location
  79.         mov     cx,[bp+BufferLength] ;# of match locations to check
  80. SearchLoop:
  81.         mov     si,sp           ;point SI to SkipTable
  82. ; Skip through until there's a match for the rightmost pattern byte.
  83. QuickSearchLoop:
  84.         mov     bl,[di] ;rightmost buffer byte at this location
  85.         cmp     dl,bl   ;does it match the rightmost pattern byte?
  86.         jz      FullCompare ;yes, so keep going
  87.         sub     bh,bh   ;convert to a word
  88.         add     bx,bx   ;prepare for look-up in SkipTable
  89.         mov     ax,[si+bx] ;get skip value from skip table for this
  90.                         ; mismatch value
  91.         add     di,ax   ;BufferPtr += Skip;
  92.         sub     cx,ax   ;BufferLength -= Skip;
  93.         ja      QuickSearchLoop ;continue if any buffer left
  94.         jmp     short NoMatch
  95. ; Return a pointer to the start of the buffer (for 0-length pattern).
  96.         align   2
  97. InstantMatch:
  98.         mov     ax,[bp+BufferPtr]
  99.         jmp     short Done
  100. ; Compare the pattern and the buffer location, searching from high
  101. ; memory toward low (right to left).
  102.         align   2
  103. FullCompare:
  104.         mov     [bp+BufferPtr],di       ;save the current state of
  105.         mov     [bp+BufferLength],cx    ; the search
  106.         mov     cx,[bp+PatternLength] ;# of bytes yet to compare
  107.         jcxz    Match   ;done if there was only one character
  108.         mov     si,[bp+PatternPtr] ;point to next-to-rightmost bytes
  109.         dec     di      ; of buffer location and pattern
  110.         repz    cmpsb   ;compare the rest of the pattern
  111.         jz      Match   ;that's it; we've found a match
  112. ; It's a mismatch; let's see what we can learn from it.
  113.         inc     di      ;compensate for 1-byte overrun of REPZ CMPSB;
  114.                         ; point to mismatch location in buffer
  115. ; # of bytes that did match.
  116.         mov     si,[bp+BufferPtr]
  117.         sub     si,di
  118. ; If, based on the mismatch character, we can't even skip ahead as far
  119. ; as where we started this particular comparison, then just advance by
  120. ; 1 to the next potential match; otherwise, skip ahead from this
  121. ; comparison location by the skip distance for the mismatch character,
  122. ; less the distance covered by the partial match.
  123.         sub     bx,bx   ;prepare for word addressing off byte value
  124.         mov     bl,[di] ;get the value of the mismatch byte in buffer
  125.         add     bx,bx   ;prepare for word look-up
  126.         add     bx,sp   ;SP points to SkipTable
  127.         mov     cx,[bx] ;get the skip value for this mismatch
  128.         mov     ax,1    ;assume we'll just advance to the next
  129.                         ; potential match location
  130.         sub     cx,si   ;is the skip far enough to be worth taking?
  131.         jna     MoveAhead ;no, go with the default advance of 1
  132.         mov     ax,cx   ;yes; this is the distance to skip ahead from
  133.                         ; the last potential match location checked
  134. MoveAhead:
  135. ; Skip ahead and perform the next comparison, if there's any buffer
  136. ; left to check.
  137.         mov     di,[bp+BufferPtr]
  138.         add     di,ax                   ;BufferPtr += Skip;
  139.         mov     cx,[bp+BufferLength]
  140.         sub     cx,ax                   ;BufferLength -= Skip;
  141.         ja      SearchLoop              ;continue if any buffer left
  142. ; Return a NULL pointer for no match.
  143.         align   2
  144. NoMatch:
  145.         sub     ax,ax
  146.         jmp     short Done
  147. ; Return start of match in buffer (BufferPtr - (PatternLength - 1)).
  148.         align   2
  149. Match:
  150.         mov     ax,[bp+BufferPtr]
  151.         sub     ax,[bp+PatternLength]
  152. Done:
  153.         cld             ;restore default direction flag
  154.         add     sp,256*2 ;deallocate space for SkipTable
  155.         pop     di      ;restore caller's register variables
  156.         pop     si
  157.         pop     bp      ;restore caller's stack frame
  158.         ret
  159. _FindString     endp
  160.         end
  161.