/*Recherche un motif spécifié dans un tampon. En cas de discordance,
 utilise la valeur de l'octet discordant pour passer autant d'emplacements
 potentielles de correspondance(algorithme Boyer-Moore partiel).
 Retourne l'offset du début de la première correspondance 
 ou NULL si aucune correspondance n'est trouvée.
 Testé avec Borland C++ en mode C et le modèle small. */

#include <stdio.h>

unsigned char * FindString(unsigned char * BufferPtr,
   unsigned int BufferLength, unsigned char * PatternPtr,
   unsigned int PatternLength)
{
   unsigned char * WorkingPatternPtr, * WorkingBufferPtr;
   unsigned int CompCount, SkipTable[256], Skip, DistanceMatched;
   int i;

   /* Echec si le tampon est trop petit */
   if (BufferLength < PatternLength) return(NULL);

   /* Retourne une correspondance immédiate si le motif à une longueur=0*/
   if (PatternLength == 0) return(BufferPtr);

   /* Crée une table de distances à laquelle nous nous référerons lors
      d'une discordance pour nous déplacer d'une des valeurs possible
   /* Initialise tous les sauts à la longueur du motif; c'est la distance de saut 
      des octets qui n'apparaissent pas le motif */
   for (i = 0; i < 256; i++) SkipTable[i] = PatternLength;
   /* Paramètre les sauts pour les octets qui apparaissent dans le motif
      avec la distance entre l'octet et la fin du motif.
      Quand il y a des instances multiples du même octet, la valeur de saut la 
      plus à droite est utilisée. Notez que l'octet le plus à droite
      du motif n'est pas entré dans la table de saut; si nous prenons cette valeur
      comme discordance, nous somme sûr que le coté droit du motif à déjà dépassé 
      l'emplacement de la discordance ; aussi ce n'est pas un octet intéressant 
      
for (i = 0; i < (PatternLength - 1); i++)
      SkipTable[PatternPtr[i]] = PatternLength - i - 1;

   /* Pointe sur l'octet le plus à droite du motif */
   PatternPtr += PatternLength - 1;
   /* Pointe sur le dernier octet (le plus à droite) du premier motif 
      éventuellement correspondant dans le tampon */
   BufferPtr += PatternLength - 1;
   /* Compte le nombre de correspondances éventuelles dans le tampon */
   BufferLength -= PatternLength - 1;

   /* Recherche dans le tampon */
   while (1) {
 /* Vérifions si nous avons un correspondance à cet emplacement dans le tampon */
      WorkingPatternPtr = PatternPtr;
      WorkingBufferPtr = BufferPtr;
      CompCount = PatternLength;
      /* Compare le motif et le tampon, en partant de la mémoire haute
       à la basse(droite à gauche) */
      while (*WorkingPatternPtr-- == *WorkingBufferPtr--) {
         /*Si nous avons une correspondance totale, c'est une correspondance */
         if (--CompCount == 0)
            /* Retourne un pointeur sur la correspondance trouvée */
            return(BufferPtr - PatternLength + 1);
      }
      /*C'est une discordance; que pouvons-nous apprendre */
      WorkingBufferPtr++;  /* repointe sur la discordance */
      /* nombre d'octets qui correspondaient */
      DistanceMatched = BufferPtr - WorkingBufferPtr;
      /* 
         Si basé sur un caractère discordant, nous pouvons juste avancé de 1
         vers le prochaine concordance potentielle*/

if (SkipTable[*WorkingBufferPtr] <= DistanceMatched)
         Skip = 1;   /*le saut n'est pas bien effectué, avance de 1 */
      else
         /* Utilise la valeur de saut, en comptant la distance couverte par
            correspondance partielle */
         Skip = SkipTable[*WorkingBufferPtr] - DistanceMatched;
      /* Sauter plus avant atteindrait la fin du tampon. Nous avons donc 
         terminer sans trouver de correspondance*/

      if (Skip >= BufferLength) return(NULL);
      /* saute et réalise un nouvelle comparaison */
      BufferLength -= Skip;
      BufferPtr += Skip;
   }
}