| iMatix home page
| << | < | > | >>
SFL Logo SFL
Version 2.11

 

memfind_rb

#include "sflfind.h"
void *
memfind_rb (const void  *in_block,      /*  Block containing data            */
            size_t       block_size,    /*  Size of block in bytes           */
            const void  *in_pattern,    /*  Pattern to search for            */
            size_t       pattern_size,  /*  Size of pattern block            */
            size_t      *shift,         /*  Shift table (search buffer)      */
            Bool        *repeat_find)   /*  TRUE: search buffer already init */

Synopsis

Searches for a pattern in a block of memory using the Boyer- Moore-Horspool-Sunday algorithm. The block and pattern may contain any values; you must explicitly provide their lengths. Returns a pointer to the pattern if found within the block, or NULL if the pattern was not found. On the first search with a given pattern, *repeat_find should be FALSE. It will be set to TRUE after the shift table is initialised, allowing the initialisation phase to be skipped on subsequent searches. shift must point to an array big enough to hold 256 (8**2) size_t values. This function is meant to handle binary data, for repeated searches for the same pattern. If you need to search strings, use the strfind r() or strfind rb() functions. If you wish to search for a pattern only once consider using memfind r(). Reentrant.

Source Code - (sflfind.c)

{
    size_t
        byte_nbr,                       /*  Distance through block           */
        match_size;                     /*  Size of matched part             */
    const byte
        *match_base = NULL,             /*  Base of match of pattern         */
        *match_ptr  = NULL,             /*  Point within current match       */
        *limit      = NULL;             /*  Last potiental match point       */
    const byte
        *block   = (byte *) in_block,   /*  Concrete pointer to block data   */
        *pattern = (byte *) in_pattern; /*  Concrete pointer to search value */

    ASSERT (block);                     /*  Expect non-NULL pointers, but    */
    ASSERT (pattern);                   /*  fail gracefully if not debugging */
    ASSERT (shift);                     /*  NULL repeat_find => is false     */
    if (block == NULL || pattern == NULL || shift == NULL)
        return (NULL);

    /*  Pattern must be smaller or equal in size to string                   */
    if (block_size < pattern_size)
        return (NULL);                  /*  Otherwise it's not found         */

    if (pattern_size == 0)              /*  Empty patterns match at start    */
        return ((void *)block);

    /*  Build the shift table unless we're continuing a previous search      */

    /*  The shift table determines how far to shift before trying to match   */
    /*  again, if a match at this point fails.  If the byte after where the  */
    /*  end of our pattern falls is not in our pattern, then we start to     */
    /*  match again after that byte; otherwise we line up the last occurence */
    /*  of that byte in our pattern under that byte, and try match again.    */

    if (!repeat_find || !*repeat_find)
      {
        for (byte_nbr = 0; byte_nbr < 256; byte_nbr++)
            shift [byte_nbr] = pattern_size + 1;
        for (byte_nbr = 0; byte_nbr < pattern_size; byte_nbr++)
            shift [(byte) pattern [byte_nbr]] = pattern_size - byte_nbr;

        if (repeat_find)
            *repeat_find = TRUE;
      }

    /*  Search for the block, each time jumping up by the amount             */
    /*  computed in the shift table                                          */

    limit = block + (block_size - pattern_size + 1);
    ASSERT (limit > block);

    for (match_base = block;
         match_base < limit;
         match_base += shift [*(match_base + pattern_size)])
      {
        match_ptr  = match_base;
        match_size = 0;

        /*  Compare pattern until it all matches, or we find a difference    */
        while (*match_ptr++ == pattern [match_size++])
          {
            ASSERT (match_size <= pattern_size &&
                    match_ptr == (match_base + match_size));

            /*  If we found a match, return the start address                */
            if (match_size >= pattern_size)
              return ((void*)(match_base));

          }
      }
    return (NULL);                      /*  Found nothing                    */
}

| << | < | > | >> iMatix Copyright © 1996-2000 iMatix Corporation