; Recherche dans un tampon d'un motif spécifié. En cas de discordance,
; utilise la valeur de l'octet qui ne correspond pas pour sauter autant 
; de correspondances possibles (Boyer-Moore partiel).
; Retourne l'offset de départ de la première correspondance à rechercher, ou NULL 
; si aucune correspondance n'est trouvée.
; Testée avec TASM.
; Appelable en C near comme suit:
;       unsigned char * FindString(unsigned char * BufferPtr,
;          unsigned int BufferLength, unsigned char * PatternPtr,
;          unsigned int PatternLength);

parms   struc
        dw      2 dup(?) ;BP & adresse de retour empilés
BufferPtr dw    ?        ;pointeur sur le tampon à rechercher
BufferLength dw ?        ;nombre d'octets dans le tampon à rechercher
PatternPtr dw   ?        ;pointeur sur le motif que l'on recherche
PatternLength dw ?       ;longueur du motif
parms   ends

        .model small
        .code
        public _FindString
_FindString     proc    near
        cld
        push    bp      ;préserve la stack frame de l'appelant
        mov     bp,sp   ;pointe sur notre stack frame
        push    si      ;préserve les variables registre de l'appelant
        push    di
        sub     sp,256*2 ;alloue de l'espace à SkipTable
; Crée la table des distances pour sauter les discordances
; de chaque valeur d'octet possible. Premièrement, initialise tous les sauts
; avec la longueur du motif; ce qui correspond à la distance de saut des octets 
, qui n'apparaissent pas dans le motif.
        mov     ax,[bp+PatternLength]
        and     ax,ax       ;retourne immédiatement une correspondance si le motif
        jz      InstantMatch; à une longueur=0
        mov     di,ds
        mov     es,di   ;ES=DS=SS
        mov     di,sp   ;pointe sur SkipBuffer
        mov     cx,256
        rep     stosw
        dec     ax            ;dès à présent, nous avons uniquement besoin de
        mov     [bp+PatternLength],ax   ; PatternLength - 1
; Pointe sur le dernier octet (le plus à droite) de la première concordance 
; potentielle dans le tampon.
        add     [bp+BufferPtr],ax
; Rejette si le tampon est trop petit, et place le nombre de correspondances
; du motif dans le tampon.
        sub     [bp+BufferLength],ax
        jbe     NoMatch
; Paramètre les valeurs de saut des octets qui apparaissent dans le motif
; avec la distance allant de l'octet à la fin du motif. S'il y a de multiples 
; occurrences du même octet, la valeur de saut de l'occurrence la plus à droite
; est utilisée. Remarquez que l'octet le plus à droite du
; motif n'est pas entré dans la table de sauts ; si nous récupérons cette valeur 
; pour une discordance, nous savons déjà que l'extrémité droite du motif a
; déjà dépassée l'emplacement de la discordance, aussi ce n'est pas un octet 
; pertinent.
        mov     si,[bp+PatternPtr] ;pointe sur le début du motif
        and     ax,ax    ;y a-t-il d'autres sauts à positionner?
        jz      SetSkipDone ;non
        mov     di,sp    ;pointe sur SkipBuffer
SetSkipLoop:
        sub     bx,bx   ;prépare l'adressage de mot de la valeur
        mov     bl,[si] ;récupère le prochain octet du motif
        inc     si      ;avance le pointeur du motif
        shl     bx,1
        mov     [di+bx],ax ;paramètre la valeur de saut quand cette valeur de 
                           ;l'octet est la valeur de discordance dans le tampon
        dec     ax
        jnz     SetSkipLoop
SetSkipDone:
        mov     dl,[si] ;DL=octet le plus à droite du motif dès à présent
        dec     si      ;pointe sur le prochain octet le plus droite du motif 
        mov     [bp+PatternPtr],si ; dès à présent
;Recherche le tampon.
        std                          ;inverse REPZ CMPSB
        mov     di,[bp+BufferPtr]    ;pointe sur le premier emplacement recherché
        mov     cx,[bp+BufferLength] ;nombre de correspondances à vérifier
SearchLoop:
        mov     si,sp           ;pointe sur SI dans SkipTable
; Saute jusqu'à il y a une correspondance avec l'octet le plus à droite du motif.
QuickSearchLoop:
        mov     bl,[di] ;ici l'octet le plus à droite du tampon 
        cmp     dl,bl   ;correspond il à l'octet le plus à droite du motif?
        jz      FullCompare ;oui, alors
        sub     bh,bh   ;convertissons le en un mot
        add     bx,bx   ;prépare le pré-calcul dans SkipTable
        mov     ax,[si+bx] ;récupère la valeur du saut dans la table de sauts pour cette
                        ; valeur discordante
        add     di,ax   ;BufferPtr += Skip;
        sub     cx,ax   ;BufferLength -= Skip;
        ja      QuickSearchLoop ;continue s'il n'y a plus rien dans le tampon
        jmp     short NoMatch
; Retourne un pointeur sur le début du tampon  (pour un motif 0 de long).
        align   2
InstantMatch:
        mov     ax,[bp+BufferPtr]
        jmp     short Done
; Compare  les emplacements du motif et du tampon, en repartant de
; la mémoire haute à la basse (droite à gauche).
        align   2
FullCompare:
        mov     [bp+BufferPtr],di       ;sauve l'état actuel 
        mov     [bp+BufferLength],cx    ; de la recherche
        mov     cx,[bp+PatternLength] ;nombre d'octets restant à comparer
        jcxz    Match   ;fait, s'il n'y avait qu'un caractère
        mov     si,[bp+PatternPtr] ;pointe sur les prochains octets les plus à droite
        dec     di      ;des emplacements du tampon et du motif
        repz    cmpsb   ;compare le reste du motif
        jz      Match   ;nous avons trouvé une correspondance
; C'est une discordance ;voyons ce que nous en apprenons.
        inc     di      ;compense le dépassement d'un octet de REPZ CMPSB;
                        ;pointe sur l'emplacement de la discordance dans le tampon 
                        ;nombre d'octets qui correspondaient.

        mov     si,[bp+BufferPtr]
        sub     si,di
; Si, en nous basant sur le caractère de discordance, nous ne pouvons même pas 
; sauter aussi loin que de là d'où nous avons commencé cette comparaison, alors 
; nous avançons simplement de 1 jusqu'à la prochaine correspondance éventuelle;
; sinon, nous sautons de la distance de saut du caractère discordant à partir du 
; point de comparaison, moins la distance parcourue par la correspondance 
; partielle.
        sub     bx,bx   ;prépare l'adressage du mot de la valeur de l'octet
        mov     bl,[di] ;récupère la valeur de l'octet discordant dans le tampon 
        add     bx,bx   ;prépare le pré-calcul du mot
        add     bx,sp   ;SP pointe sur SkipTable
        mov     cx,[bx] ;récupère la valeur de saut de cette discordance
        mov     ax,1    ;suppose que nous avançons juste au prochain
                        ;emplacement de correspondance éventuel
        sub     cx,si   ;le saut est-il suffisamment loin?
        jna     MoveAhead ;non, effectuons une avance par défaut de 1
        mov     ax,cx   ;oui; c'est la distance du saut du dernier emplacement 
                        ; vérifie d'une éventuelle correspondance
MoveAhead:
; Saute et effectue la prochaine comparaison, s'il n'y a plus d'emplacement tampon 
; à vérifier.
        mov     di,[bp+BufferPtr]
        add     di,ax                   ;BufferPtr += Skip;
        mov     cx,[bp+BufferLength]
        sub     cx,ax                   ;BufferLength -= Skip;
        ja      SearchLoop              ;continue s'il ne reste plus de tampon
; Retourne un pointeur NULL s'il n'y a aucune correspondance.
        align   2
NoMatch:
        sub     ax,ax
        jmp     short Done
; Retourne le début de la correspondance dans le tampon (BufferPtr - (PatternLength - 1)).
        align   2
Match:
        mov     ax,[bp+BufferPtr]
        sub     ax,[bp+PatternLength]
Done:
        cld              ;restaure le drapeau de direction par défaut
        add     sp,256*2 ;désalloue de l'espace à SkipTable
        pop     di       ;restaure les variables registre de l'appelant
        pop     si
        pop     bp       ;restaure la stack frame de l'appelant
        ret
_FindString     endp
        end