Amélioration de la fonction Pos()

Soyez le premier à donner votre avis sur cette source.

Vue 3 512 fois - Téléchargée 434 fois

Description

J'ai repris la fonction pos() que j'utilise souvent en modifiant son comportement:
La fonction recherche toutes les occurrences dans la cible et retourne les positions.
Il est possible de ne scruter q'une partie de la cible.
Il faut indiquer en plus de la fonction standard le point de départ de la recherche
et éventuellement la fin.
j'ai lu un tutoriel "débuter en assembleur avec Delphi par Kr85" qui m'a incité
a essayer, c'est très amusant.

MODIFICATIONS du 25/06/2015
PosDJ(SubSTR,STR,Depuis,jusqua) procède à une recherche binaire
posMn(SubSTR,STR,Depuis,jusqua) procéde à une recherche sans différence entre MAJ et min

Pour trouver la position de toutes les occurrences du mot dans le texte =

D:=1; While posMn(mot,texte,D) <> 0 do je trouve tous les mots;

function Pos(Const SubSTR,Scible:string; FiltreMajuscule : boolean;
var Depuis:integer; jusqua:integer=0):integer; StdCall;
{ Pas de différences entre MAJ et min si filtreMajuscule = true
Limites: Depuis > 0 , jusqua >= 0 si 0 alors length(Scible)
Résultat:
la fonction retourne la position de SubSTR dans Scible
Depuis retourne la position de début pour la prochaine recherche
si Retour = 0 alors subSTR n'est pas dans SCible
si retour=0 et Depuis inchangé alors erreur de données
}

Const PosLength = -4;
_SubSTR_ = $08; _Scible_ = $0C; _Filtre_ = $10; _Depuis_ = $14;
_jusqua_ = $18;
//var locales
_DebutCible_ = -$04; _CompteurSubSTR_ = -$08;

asm // PUSH EBP MOV EBP,ESP
{EAX,EDX,ECX sont disponibles
Récupèration des adresses de SubSTR et Scible
Const SubSTR,Scible = MOV ESI , SubSTR ....
Var SubSTR,Scible = MOV ESI , SubSTR
MOV ESI , [ESI] ....
}
ADD ESP, _CompteurSubSTR_ //vars locales
PUSH EBX
PUSH ESI
PUSH EDI
//contrôle des données
MOV ESI,[EBP+_SubSTR_] //test SubSTR <> '' [ESI]=ptr(SubSTR)
MOV EDI,[EBP+_Scible_] //test Scible <> '' [EDI]=ptr(Scible)
CMP ESI,1 // CF=1 si ESI=0 (vide)
SBB EAX,EAX // -1 si ESI=0
CMP EDI,1 // CF=1 si EDI=0
SBB EAX,0 // négatif si EDI ou ESI vide autrement EAX= 0
JNZ @Erreur
mov eax,[EDI+PosLength] // Length(Scible) dans EAX
mov edx,[EBP+_jusqua_]
dec edx // jusqua-1
and edx,$7FFFFFFF // garde nombre positif ?
dec eax //length(Scible)-1
xor ecx,ecx
cmp eax,edx // cmp length(Scible)-1,jusqua-1
setl cl // eax < edx cl=1
neg ecx // si cl 1 = FFFFFFFF si cl 0 = 0
mov ebx,ecx //masque dans ebx
and ebx,eax // eax copié dans ebx si eax < edx ou 0
not ecx //inverse les bit de ecx
and ecx,edx //copie éventuelle de edx dans ecx
or ebx,ecx //retient eax ou edx
inc ebx //inc position dernier char du test
MOV EAX,[EBP+_Depuis_]
MOV ECX,[EAX] //Depuis dans ECX
XOR EAX,EAX //test si Depuis < 1 alors Depuis=1
SUB ECX,1
SETS AL // EAX=1 si signe négatif
XOR EAX,1 // inverse EAX
NEG EAX //inversion en complément à 2
AND ECX,EAX // masque 0000... ou FFFF...
INC ECX //ECX contient 1 mini
MOV EDX,[ESI+PosLength] //EDX =length(SubSTR)
MOV EAX,ECX // EAX=Depuis
ADD EAX,EDX
DEC EAX //EAX = Depuis+length(SubSTR)
CMP EAX,EBX
JNBE @Erreur //Depuis+len(Substr) > len(Scible)ouJusqua
//-----------contrôle des entrées terminé ici
//ECX=Depuis EBX=compteur EDX=length(subSTR)
//ESI=subSTR EDI=Scible
SUB EBX,EAX
INC EBX
MOV [EBP+_DebutCible_],EDI // sauve adresse debut Scible
ADD EDI,ECX
DEC EDI //début du test de Scible
//--------test le filtreMajuscule---20h ou 0h dans AL
XOR EAX,EAX //false = 0
MOV ECX,[EBP+_filtre_]
SUB ECX,1 //CF=1 si ECX=0 false
CMC // inverse CF CF=0 si false
RCL EAX,6 //CF est copié dans le bit5
//------------------------ Début des boucles de lecture EBX = compteur----
MOV CL,[ESI]
OR CL,AL //si 20h alors minuscule?
INC ESI
SUB EDX,2 //EDX = len(subSTR)-2
PUSH EDX
JC @Boucle1charSubSTR //EDX < 0 donc len(subSTR)=1
//lecture par 2 chars à partir d'ici
mov ah,al // or 20h
mov ch,[esi]
or ch,al //CX= 2 premiers chars de subSTR
dec esi
add esi,edx //ESI = ptr avant dernier char de subSTR
inc edx //len(subSTR)-1
shr edx,1
cmp edx,1
adc edx,0 // mini = 1 dans edx
mov[ebp+_compteurSubSTR_],edx // (len(subSTR)-1)/2

@LireScible: // boucle de lecture > 1 char dans subSTR
MOV DX,[EDI]
OR DX,AX // 0h ou 20h
CMP CX,DX // SubSTR[1-2]=Scible[EDI]
JZ @SuivantsubSTR // Chars identiques
@RetourSuivantsubSTR: // subSTR <> Scible ici
INC EDI
DEC EBX
JNZ @LireScible

//pas trouvé de correspondance----------
@Pas1char:
POP EDX //len subSTR-2
ADD EDX,2
SUB EDI,[EBP+_DebutCible_]
ADD EDI,EDX
MOV ESI,[EBP+_Depuis_]
MOV [ESI],EDI //Length(Scible)+1 mis dans Depuis
@Erreur:
XOR EAX,EAX //Result=0
JMP @fin

@EchecLectureSubSTR:
POP EDI
POP ECX
POP ESI
POP EBX
JMP @RetourSuivantSubStr

@Boucle1charSubSTR: // boucle de lecture 1 char dans subSTR
mov ch,[edi]
or ch,al
cmp ch,cl
jz @trouve1
inc edi
dec ebx
jnz @Boucle1charSubSTR
jmp @Pas1char

//--------trouvé ici SubSTR[1] dans Scible[EDI]
@SuivantsubSTR:
//test à partir de la fin de subSTR
MOV EDX,[ESP] //compteur subSTR
PUSH EBX
PUSH ESI //sauve ptr char subSTR
PUSH ECX // 2 char de subSTR
PUSH EDI //Scible
ADD EDI,EDX //au dessus de der char de subSTR
mov edx,[ebp+_compteurSubSTR_];

@LireSubSTR: //correspondance de la totalité de subSTR
MOV CX,[ESI]
OR CX,AX
MOV BX,[EDI]
OR BX,AX
CMP BX,CX
JNZ @EchecLectureSubSTR
SUB ESI,2
SUB EDI,2
DEC EDX
JNZ @LireSubSTR
//trouve correspondance de tous les char
POP EDI
POP ECX
POP ESI
POP EBX
@Trouve1:
POP EDX //len subSTR-2
ADD EDX,2
SUB EDI,[EBP+_DebutCible_]
MOV EAX,EDI
INC EAX //RESULT ici
ADD EDX,EAX
MOV ESI,[EBP+_Depuis_]
MOV [ESI],EDX //Prochain depuis
@Fin:
POP EDI
POP ESI
POP EBX
MOV ESP,EBP //restitue var(s) locale(s)
end; //POP EBP RET 16

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Re-bonjour,

Pour en savoir plus sur l'astuce à la base de la vitesse d'exécution de BMHPascalC5T voir ici

http://www.developpez.net/forums/d1530223-2/environnements-developpement/delphi/algorithme-boyer-moore/

Voir le message d'Aujourd'hui 13/07/2015 à 11h09 (message n°#35) qui commence par "Le projet de Brute force de Rekin85 m'a donné une idée d'un Boyer-Moore "brutal" qui utilise un coulisseau à 5 Trous"

Je pense que l'amélioration est susceptible de vous intéresser.

Cordialement, et à +.
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
> cs_pseudo3
Bonjour,
J'ai regardé, c'est une autre façon de 'voir les choses'.
Une autre approche.
Mais plus rapide sans aucun doute, bravo.
Je vais rester sur une approche binaire, ce sera intéressant de voir de combien la différence entre ces 2 approches se réduit en ms avec l'ASM?
Il est aussi possible de 'fouiller' avec votre méthode et ensuite de confirmer octets après octets la validité absolue de la 'trouvaille', ce qui marierai les 2 approches!
je retourne sur la plage.
>
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019

Bonjour,

>> "J'ai regardé, c'est une autre façon de 'voir les choses'. Une autre approche.Mais plus rapide sans aucun doute, bravo."

A noter en plus que cette autre approche rend l'algo "tolérant certaines fautes de frappe" susceptibles de polluer les Textes dans lesquels on fait une recherche comme par exemple : je cherche "Yellow submarine" et l'un des textes contient "Yallow submarine" et l'autre "Yellow submarime"
Dans un tel cas l'algo trouve l'occurrence alors qu'un algo "strict" tel que PosEx ne la trouve pas.

>> "Je vais rester sur une approche binaire, ce sera intéressant de voir de combien la différence entre ces 2 approches se réduit en ms avec l'ASM?" :

Ce serait effectivement intéressant.

>> "Il est aussi possible de 'fouiller' avec votre méthode et ensuite de confirmer octets après octets la validité absolue de la 'trouvaille', ce qui marierai les 2 approches! " :

Bin comme ma méthode est tolérante à un certain nombre de fautes de frappe cela supposerait qu'il soit possible de confirmer par une logique :
- soit que les occurrences trouvées contiennent de simples fautes de frappe,
- soit qu'il s'agit d'occurrences parasites.

>> "je retourne sur la plage." :

Bonne baignade...

Cordialement, et à +.
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
> cs_pseudo3
Bonsoir,
Les baignades sont terminées, hélas.


Salutations.
Bonjour,

J'ai enfin trouvé la cause de la Violation d'accès : c'est l'instruction if BM.Par2chars <> nil then FreeMem(BM.Par2chars, BM.Volar2chars) qui la causait :
function Fab_Sauts(var BM: TreBMH2C): boolean;
var I: integer;
begin
ShowMessage('Fab_Sauts Deb');
Result := length(BM.mot) > 1; if not Result then exit;
BM.jusqua := 0; BM.Depuis := 1;
BM.Lmot := length(BM.mot); BM.ForceBrut := BM.Lmot < ctposDJ;
if BM.ForceBrut then begin showmessage('exit Fab_Sauts'); exit; end;

fillchar(BM.arNchars, succ(ctNchar), 0);
//comptage Nb lettres <>
for I := 1 to BM.Lmot do BM.arNchars[ord(BM.mot[I])] := 1;
BM.NcharDiff := 1;
ShowMessage('Fab_Sauts 1');
for I := 0 to Pred(ord(BM.mot[1])) do if BM.arNchars[I] <> 0 then
begin inc(BM.NcharDiff); BM.arNchars[I] := BM.NcharDiff; end;
ShowMessage('Fab_Sauts 2');
for I := Succ(ord(BM.mot[1])) to ctNchar do if BM.arNchars[I] <> 0 then
begin inc(BM.NcharDiff); BM.arNchars[I] := BM.NcharDiff; end;
ShowMessage('Fab_Sauts 3');
//normalisation 2^n
BM.NbLignes := Succ(BM.NcharDiff);
//if BM.Par2chars <> nil then FreeMem(BM.Par2chars, BM.Volar2chars); < ici la cause de la V.A.
BM.Volar2chars := (BM.NbLignes * BM.NbLignes * sizeof(Word));
GetMem(BM.Par2chars, BM.Volar2chars);
ShowMessage('Fab_Sauts 4');
fillWord(BM.Par2chars^, BM.NbLignes * BM.NbLignes, BM.Lmot);
fillWord(BM.Par2chars^, BM.NbLignes * 2, Pred(BM.Lmot));
fillWord(BM.Par2chars^, BM.NbLignes, BM.Lmot);
ShowMessage('Fab_Sauts 5');
//remplissage de la table
for I := 1 to BM.Lmot - 2 do
BM.Par2chars^[BM.arNchars[ord(BM.mot[I])] +
BM.arNchars[ord(BM.mot[Succ(I)])] * BM.NbLignes] := Pred(BM.Lmot) - I;
ShowMessage('Fab_Sauts Fin');
end;


Résultats du test :

TEXTE : -Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!-Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!-Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!-Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!

len V2C.texte : 380

MOT : Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!

2000000 trouvailles en ---------------78 ms

MOT : Bon
len V2C.texte : 380

4000000 trouvailles en ---------------125 ms

Cordialement, et à +.
Afficher les 115 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.