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 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326
| library PosBM;
uses windows;
// Routines et variables internes **********************************************
type TSkip = array[0..255] of longword;
var SkipBuf: TSkip; // Table des sauts du Boyer-Moore
const SeuilEx_BM : longword = $6;
// Compare SStr à Str depuis la position de ecx dans Str
// comparaisons faites en dwords et/ou bytes avec NbDw et NbBy
// 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
// 3 - eax toujours =0
procedure CompBM_BD; 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
add esi,ecx // pointer fin Str + 1
add edi,ecx // pointer fin SStr + 1
// Byte à Byte
@Bytes:
mov ecx,edx
and ecx,$3
jz @DWords
@RBytes: // shunter si un des derniers discordant
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[edi]
cmp eax,DWord ptr[esi]
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;
// Routines exportables ********************************************************
// permet d'initialiser le seuil de basculement des deux Pos
// En deçà c'est pour PosEx_KR, au delà c'est pour PosBM_KR
// Renseigne donc la constante SeuilEx_BM
procedure InitSeuil(Seuil: longword); StdCall
asm
mov eax,[ebp]+$08
mov SeuilEx_BM,eax
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 mais au minimum 5
// Retourne le rang de la 1ère occurence trouvée à partir de Depuis
// Retourne 0 si aucune trouvée
function PosBM_KR(SStr, Str : Pointer; LSStr, LStr, Depuis :longWord): longword; stdcall;
var PosMax,Depart: longWord;
asm
push ebx //pointeur sur SkipBuf
lea ebx,[SkipBuf]
push edi
mov edi,[ebp]+$08 // edi pointe Texte
push esi
mov esi,[ebp]+$0C // esi pointe Mot
mov edx,[ebp]+$10 // len Mot
mov eax,[ebp]+$14 // len Texte
sub eax,edx
inc eax // edx nb max de bytes
mov PosMax,eax
mov ecx,[ebp]+$18
dec ecx // indice de départ
mov Depart,ecx
@SearchOne:
cmp ecx,PosMax
jae @FinNulle
mov al,byte ptr[esi]+ecx
cmp al,byte ptr[edi]
je @Compare
add ecx,edx
dec ecx
mov al,byte ptr[esi]+ecx
and eax,$FF
jmp @Decale
@Compare: // Comparaison et sauts
call CompBM_BD
jc @FinBonne // CF indicateur oui - non
mov al,byte ptr[esi]+ecx // byte défaillant
@Decale:
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
mov Depart,ecx
jmp @SearchOne
@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;
// Algorithme brute force 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
// Largement inspiré de PosEx de Delphi
function PosEx_KR(SStr,Str: pointer; LSStr,LStr,Depuis: longword ): longword; StdCall;
asm
mov eax,[ebp]+$08 // adresse SStr
mov edx,[ebp]+$0C
dec edx // adresse Str - 1
mov ecx,[ebp]+$18 // offset Depuis
dec ecx
push ebx
push edi
push esi
mov edi,[ebp]+$10 // Length(SStr)
mov esi,[ebp]+$14 // Length(Str)
push ebp
push edx
add ecx,edi
lea ebp,[eax+edi] // Pointe dernier byte de SStr + 1
add esi,edx // Pointe dernier byte de S
mov eax,[ebp-$1] // Dernier byte de SStr
and eax,$FF
add edx,ecx // Position dans Str du dernier byte
mov ah,al
neg edi // - Length(SStr)
mov ecx,eax
shl eax,$10
or ecx,eax
@BoucleMain:
add edx,$4
cmp edx,esi
ja @Reste // 1 à 4 Positions en reste
mov eax,[edx-$4] // 4 Bytes suivant de Str
xor eax,ecx // aucun byte
lea ebx,[eax-$01010101]
not eax
and eax,ebx
and eax,$80808080
jz @BoucleMain // jusqu'à aucune correspondance du dernier byte
bsf eax,eax // Premier Bit correspondant
shr eax,$3 // rang du byte correspondant (0..3)
lea edx,[eax+edx-$4] // Adresse
@Compare:
inc edx
cmp edi,-$4
jle @Large // Lenght(SStr) >= 4
cmp edi,-$1
je @Resultat // Exit si Lenght(SStr) = 1
mov ax,[ebp+edi]
cmp ax,[edx+edi]
jne @BoucleMain // pas de correspondance dans les deux premiers bytes
jmp @Resultat
@Reste:
sub edx,$4
@BoucleReste:
cmp cl,[edx]
je @Compare
cmp edx,esi
jae @NonTrouve
inc edx
jmp @BoucleReste
@Large:
mov eax,[ebp-$4] // Compare les 4 derniers bytes
cmp eax,[edx-$4]
jne @BoucleMain // pas de correspondance
mov ebx,edi
@BoucleCompare: // Compare les bytes du reste
add ebx,$4 // Compare 4 bytes à la fois
jge @Resultat // Tous bons
mov eax,[ebp+ebx-$4]
cmp eax,[edx+ebx-$4]
je @BoucleCompare
jmp @BoucleMain // Pas de correspondance
@NonTrouve:
pop edx // Pas trouvé
pop ebp
pop esi
pop edi
pop ebx
xor eax,eax // retour 0
jmp @Fin
@Resultat: // correspondance complète
lea eax,[edx+edi] // Calcule et retourne le résultat
pop edx
pop ebp
pop esi
pop edi
pop ebx
sub eax,edx // soustrait la position de départ
@Fin:
end;
// Initialise le tableau Skip des sauts du Boyer-Moore
// en fonction de la collection à rechercher
procedure InitSkipBuf(SStr : Pointer; LenSStr: longword); StdCall;
asm
push esi
mov esi,[ebp]+$08 // esi pointe SStr
mov eax,[ebp]+$0C // eax = len(SStr)
push edi
lea edi,[SkipBuf] // edi pointe SkipBuf
@FillInt:
cld // remplissage en montant
mov ecx,$100 // 256 itérations
rep stosd // remplissage total avec lenSub
sub edi,$400 // remise edi au début de SkipBuf
mov ecx,eax // eax contient toujours len SStr
@RSkip:
dec ecx
jle @Fin
mov al,byte ptr[esi] // al contient le byte
and eax,$FF
shl eax,$2 // valeur du byte x 4
mov DWord ptr[edi+eax],ecx
inc esi
jmp @RSkip
@Fin:
pop edi
pop esi
end;
// Appel function externe générale
// Choix du mode Boyer-Moore au delà de 5 bytes en LSStr
function Pos_KR(SStr,Str: pointer; LSStr,LStr,Depuis : Longword): longword; StdCall;
asm
// Cas d'invalidités d'appel
mov eax,[ebp]+$10 // LSStr
mov edx,[ebp]+$14 // LStr
mov ecx,[ebp]+$18 // Depuis
test eax,eax
jz @Nul // LSStr = 0
test edx,edx
jz @Nul // LStr = 0
cmp eax,edx
ja @Nul // LSStr > LStr
cmp ecx,$1
jb @Nul // Depuis < 1
sub edx,eax
cmp ecx,edx // Depuis > LStr-LSStr
jb @Go
@Nul:
xor eax,eax // Retour @
jmp @Fin
@Go: // Appel des routines
mov ecx,[ebp]+$18
push ecx
mov ecx,[ebp]+$14
push ecx
mov ecx,[ebp]+$10
push ecx
mov ecx,[ebp]+$0C
push ecx
mov ecx,[ebp]+$08
push ecx
cmp eax,SeuilEx_BM // Au delà de SeuilEx_BM ?
ja @PosBM
@PosEx:
call PosEx_KR
jmp @Fin
@PosBM:
call PosBM_KR
@Fin:
end;
// *****************************************************************************
exports
InitSeuil,
PosBM_KR,
PosEx_KR,
InitSkipBuf,
Pos_KR;
// *****************************************************************************
begin
end. |
Partager