home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / pctchnqs / 1991 / number4 / l1.c < prev    next >
Text File  |  1991-07-21  |  4KB  |  86 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 Borland C++ 2.0 in C mode and the small model. */
  7.  
  8. #include <stdio.h>
  9.  
  10. unsigned char * FindString(unsigned char * BufferPtr,
  11.    unsigned int BufferLength, unsigned char * PatternPtr,
  12.    unsigned int PatternLength)
  13. {
  14.    unsigned char * WorkingPatternPtr, * WorkingBufferPtr;
  15.    unsigned int CompCount, SkipTable[256], Skip, DistanceMatched;
  16.    int i;
  17.  
  18.    /* Reject if the buffer is too small */
  19.    if (BufferLength < PatternLength) return(NULL);
  20.  
  21.    /* Return an instant match if the pattern is 0-length */
  22.    if (PatternLength == 0) return(BufferPtr);
  23.  
  24.    /* Create the table of distances by which to skip ahead on
  25.       mismatches for every possible byte value */
  26.    /* Initialize all skips to the pattern length; this is the skip
  27.       distance for bytes that don't appear in the pattern */
  28.    for (i = 0; i < 256; i++) SkipTable[i] = PatternLength;
  29.    /* Set the skip values for the bytes that do appear in the pattern
  30.       to the distance from the byte location to the end of the
  31.       pattern. When there are multiple instances of the same byte, the
  32.       rightmost instance's skip value is used. Note that the rightmost
  33.       byte of the pattern isn't entered in the skip table; if we get
  34.       that value for a mismatch, we know for sure that the right end
  35.       of the pattern has already passed the mismatch location, so this
  36.       is not a relevant byte for skipping purposes */
  37.    for (i = 0; i < (PatternLength - 1); i++)
  38.       SkipTable[PatternPtr[i]] = PatternLength - i - 1;
  39.  
  40.    /* Point to rightmost byte of the pattern */
  41.    PatternPtr += PatternLength - 1;
  42.    /* Point to last (rightmost) byte of the first potential pattern
  43.       match location in the buffer */
  44.    BufferPtr += PatternLength - 1;
  45.    /* Count of number of potential pattern match locations in
  46.       buffer */
  47.    BufferLength -= PatternLength - 1;
  48.  
  49.    /* Search the buffer */
  50.    while (1) {
  51.       /* See if we have a match at this buffer location */
  52.       WorkingPatternPtr = PatternPtr;
  53.       WorkingBufferPtr = BufferPtr;
  54.       CompCount = PatternLength;
  55.       /* Compare the pattern and the buffer location, searching from
  56.          high memory toward low (right to left) */
  57.       while (*WorkingPatternPtr-- == *WorkingBufferPtr--) {
  58.          /* If we've matched the entire pattern, it's a match */
  59.          if (--CompCount == 0)
  60.             /* Return a pointer to the start of the match location */
  61.             return(BufferPtr - PatternLength + 1);
  62.       }
  63.       /* It's a mismatch; let's see what we can learn from it */
  64.       WorkingBufferPtr++;  /* point back to the mismatch location */
  65.       /* # of bytes that did match */
  66.       DistanceMatched = BufferPtr - WorkingBufferPtr;
  67.       /* If, based on the mismatch character, we can't even skip ahead
  68.          as far as where we started this particular comparison, then
  69.          just advance by 1 to the next potential match; otherwise,
  70.          skip ahead from the mismatch location by the skip distance
  71.          for the mismatch character */
  72.       if (SkipTable[*WorkingBufferPtr] <= DistanceMatched)
  73.          Skip = 1;   /* skip doesn't do any good, advance by 1 */
  74.       else
  75.          /* Use skip value, accounting for distance covered by the
  76.             partial match */
  77.          Skip = SkipTable[*WorkingBufferPtr] - DistanceMatched;
  78.       /* If skipping ahead would exhaust the buffer, we're done
  79.          without a match */
  80.       if (Skip >= BufferLength) return(NULL);
  81.       /* Skip ahead and perform the next comparison */
  82.       BufferLength -= Skip;
  83.       BufferPtr += Skip;
  84.    }
  85. }
  86.