1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229
| library PosBM;
uses
windows;
// Routines internes ***********************************************************
type TSkip = array[0..255] of longword;
var SkipBuf: TSkip;
// Compare SStr à Str depuis la position de edx dans Str
// comparaisons faites en dwords
// Entrée :
// 1 - esi pointe sur la Str et edi sur la SStr
// 2 - ecx contient l'indice de la borne
// 3 - edx contient la longueur de la collection SStr
// Retour :
// 1 - CarryFlag à 1 si occurence trouvée et à 0 sinon
// 2 - ecx renvoie la position du byte d'arrêt sur Str
procedure CompBM_D; register;
asm
push edi
push esi // adresse départ Str
add esi,ecx // placer esi sur la borne de départ
mov ecx,edx // edx garde length(SStr)
// comparaison descendante
std
add esi,ecx // pointer fin Str + 1
add edi,ecx // pointer fin SStr + 1
// Byte à Byte
@Bytes:
and ecx,$3 // combien de bytes en reste ?
jz @DWords // aucun
@RBytes:
dec esi // se placer sur dernier byte
dec edi
mov al,byte ptr[edi]
cmp al,byte ptr[esi]
jne @FinNon // byte discordant
dec ecx
jnz @Rbytes
// DWord à DWord
@DWords:
mov ecx,edx // combien de DWords entiers ?
shr ecx,$2
jz @FinOui // aucun
@RDWords:
sub esi,$4 // se placer dword en dessous
sub edi,$4
mov eax,DWord ptr[esi]
cmp eax,DWord ptr[edi]
jne @ByteD // si pas égaux, aller au byte défaillant
dec ecx
jnz @RDWords
jmp @FinOui // tous DWords bons
@ByteD: // cas d'un Dword défaillant
mov ecx,$4 // rattraper le décalage
add esi,ecx // et chercher le byte défaillant
@RByteD:
dec esi
cmp al,byte ptr[esi]
jne @FinNon
shr eax,$8
dec ecx
jnz @RByteD
// Retours de routine
@FinNon: // retour false
xor eax,eax
jmp @Fin
@FinOui: // retour true
mov eax,$1
@Fin:
mov ecx,esi
pop esi // remise adresse Départ
sub ecx,esi // calcul place du byte d'arrivée
pop edi
shr eax,$1 // positionnement du carry flag
end;
// Compare SStr à Str depuis la position de ecx dans Str
// comparaisons faites en bytes à reculons
// Entrée :
// 1 - esi pointe sur la Str et edi sur la SStr
// 2 - ecx contient l'indice de la borne de départ dans Str
// 3 - edx contient la longueur de la collection SStr
// Retour :
// 1 - Carry Flag à 1 si occurence trouvée et à 0 sinon
// 2 - ecx renvoie la position du byte d'arrêt sur Str
procedure CompBM_B;
asm
push edi
push esi // adresse départ Str
add esi,ecx // placer esi sur la borne de départ
mov ecx,edx // ecx = length(SStr)
// coulisseau
mov al,byte ptr[esi]
cmp al,byte ptr[edi]
je @coulisse
add esi,ecx
dec esi
jmp @FinNon
@Coulisse:
// comparaison descendante
add edi,ecx // pointer fin SStr + 1
add esi,ecx // pointer Str en rapport
// Byte à Byte
@RBytes:
dec esi
dec edi
mov al,byte ptr[edi]
mov ah,byte ptr[esi]
cmp ah,al
jne @FinNon // byte discordant
dec ecx
jnz @Rbytes
@FinOui: // retour true
mov eax,$1
jmp @Fin
@FinNon: // retour false
xor eax,eax
@Fin:
mov ecx,esi // adresse byte arrêt
pop esi // remise adresse Départ
sub ecx,esi // calcul rang du byte d'arrivée
pop edi
shr eax,$1 // positionnement du carry flag
end;
// Routines exportables ********************************************************
// Initialise le tableau Skip des sauts du Boyer-Moore
// en fonction de la collection à rechercher
procedure InitSkipBuf(SStr : Pointer; LenSStr: longword); StdCall;
asm
push edi
lea edi,[SkipBuf] // edi pointe SkipBuf
push esi
mov esi,[ebp]+$08 // esi pointe SStr
mov eax,[ebp]+$0C // eax = len(SStr)
// FillInt
mov ecx,$100 // 256 itérations
rep stosd // remplissage total avec lenSub
sub edi,$400 // remise edi au début de SkipBuf
// boucle des sauts
mov ecx,eax // eax contient toujours len SStr
@RSkip:
dec ecx
jz @Fin
xor eax,eax
mov al,byte ptr[esi] // al contient le byte
shl eax,$2 // valeur du byte x 4
mov DWord ptr[edi+eax],ecx
inc esi
jmp @RSkip
@Fin:
pop esi
pop edi
end;
// Algorithme de Boyer-Moore pour la recherche d'occurence
// d'une collection de bytes dans une autre collection de bytes plus grande
// L'occurence peut avoir une capacité de plus de 256 octets
// Retourne le rang de la 1ère occurence trouvée à partir de Depuis
// Retourne 0 si aucune trouvée
// Routine orientée recherche par Bytes si LSStr<400 et DWords Si >400
function PosBM_KR(SStr, Str : Pointer; LSStr, LStr, Depuis :longWord): longword; stdcall;
var PosMax,Depart : longWord;
asm
push ebx
lea ebx,[SkipBuf] // ebx pointe la Table de sauts
push edi
mov edi,[ebp]+$08 // edi pointe SStr
push esi
mov esi,[ebp]+$0C // esi pointe Str
mov edx,[ebp]+$10 // edx garde la longueur de SStr
mov eax,[ebp]+$14
sub eax,edx
jl @FinNulle // si SStr>Str
mov PosMax,eax // AMax = Borne supérieure extrême
mov ecx,[ebp]+$18
dec ecx // ecx = variable Depuis
cmp edx,$1FF
jg @WhileD
@WhileB: // Tant que pas trouvée ou fin Str
mov Depart,ecx
cmp PosMax,ecx
jb @FinNulle // Fin de Str
call CompBM_B // ecx = rang occurence si CF=1
jc @FinBonne // CF indicateur oui - non
xor eax,eax // pas trouvée, on saute en BM
mov al,byte ptr[esi]+ecx // byte d'arrêt
shl eax,$2 // indice x 4 pour DWord
mov ecx,DWord ptr[ebx]+eax // décalage par SkipBuf[byte d'arrêt]
add ecx,Depart
jmp @WhileB
@WhileD: // Tant que pas trouvée ou fin Str
mov Depart,ecx
cmp PosMax,ecx
jb @FinNulle // Fin de Str
call CompBM_D // ecx = rang occurence si CF=1
jc @FinBonne // CF indicateur oui - non
xor eax,eax // pas trouvée, on saute en BM
mov al,byte ptr[esi]+ecx // byte d'arrêt
shl eax,$2 // indice x 4 pour DWord
mov ecx,DWord ptr[ebx]+eax // décalage par SkipBuf[byte d'arrêt]
add ecx,Depart
jmp @WhileD
@FinNulle:
xor eax,eax
jmp @Fin
@FinBonne:
inc ecx
mov eax,ecx // retour du rang de l'occurence trouvée
@Fin:
pop esi
pop edi
pop ebx
end;
// *****************************************************************************
exports
InitSkipBuf,
PosBM_KR;
// *****************************************************************************
begin
end. |
Partager