search.c
/// Bitap algorithm / Baeza-Yates-Gonnet algorithm (for C strings)
Bitap algorithm / Baeza-Yates-Gonnet algorithm (for C strings)
Bitap algorithm / Baeza - Yates - Gonnet algorithm ( for C strings )
const char* searchBitap(const char* haystack, size_t haystackLength,
                        const char* needle,   size_t needleLength)
{
  if (!haystack || !needle || haystackLength < needleLength)
    return NULL;
  if (needleLength == 0)
    return haystack;
  const size_t MaxBitWidth  = 8 * sizeof(int) - 1;
  if (needleLength > MaxBitWidth)
    return searchNative(haystack, haystackLength, needle, needleLength);
  const size_t AlphabetSize = 256;
  unsigned int masks[AlphabetSize];
  size_t i;
  for (i = 0; i < AlphabetSize; i++)
    masks[i] = ~0;
  for (i = 0; i < needleLength; i++)
    masks[(unsigned char)needle[i]] &= ~(1 << i);
  const char* haystackEnd = haystack + haystackLength;
  unsigned int state = ~1;
  const unsigned int FullMatch = 1 << needleLength;
  while (haystack != haystackEnd)
  {
    state  |= masks[(unsigned char)*haystack];
    state <<= 1;
    if ((state & FullMatch) == 0)
      return (haystack - needleLength) + 1;
    haystack++;
  }
  return NULL;
}
const char * searchBitap ( const char * haystack , size_t haystackLength , const char * needle , size_t needleLength ) { if ( ! haystack || ! needle || haystackLength < needleLength ) return NULL ; if ( needleLength == 0 ) return haystack ; const size_t MaxBitWidth = 8 * sizeof ( int ) - 1 ; if ( needleLength > MaxBitWidth ) return searchNative ( haystack , haystackLength , needle , needleLength ) ; const size_t AlphabetSize = 256 ; unsigned int masks [ AlphabetSize ] ; size_t i ; for ( i = 0 ; i < AlphabetSize ; i ++ ) masks [ i ] = ~ 0 ; for ( i = 0 ; i < needleLength ; i ++ ) masks [ ( unsigned char ) needle [ i ] ] &= ~ ( 1 << i ) ; const char * haystackEnd = haystack + haystackLength ; unsigned int state = ~ 1 ; const unsigned int FullMatch = 1 << needleLength ; while ( haystack != haystackEnd ) { state |= masks [ ( unsigned char ) * haystack ] ; state <<= 1 ; if ( ( state & FullMatch ) == 0 ) return ( haystack - needleLength ) + 1 ; haystack ++ ; } return NULL ; }
Bitap algorithm / Baeza-Yates-Gonnet algorithm (for C strings)
Bitap algorithm / Baeza - Yates - Gonnet algorithm ( for C strings )
// detect invalid input // empty needle matches everything // create bit masks for each possible byte / ASCII character // each mask is as wide as needleLength // only if needleLength bits fit into an integer (minus 1), the algorithm will be fast // one mask per allowed character (1 byte => 2^8 => 256) // where all bits are set except those where the character is found in needle // points beyond last considered byte // initial state mask has all bits set except the lowest one // update the bit array // if an unset bit "bubbled up" we have a match // needle not found in haystack