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. |
Algorithme de Boyer-Moore
Répondre avec citation
Envoyé par Gilbert Geyer
Partager