Programmation C
12 sujets de 1 à 12 (sur un total de 12)
-
Salut à tous,
Je ne sais pas trop où poster alors je m’étale dans le bar. Habitué à coder en asm, j’ai besoin pour un
projet de coder une routine de recherche en C (langage que je ne maîtrise pas bien).Le problème: Je cherche à faire une routine qui soit capable de trouver une chaine hexadécimale (pas des caractères) dans un buffer de data (du bin donc). Par exemple chercher: 0x75485265 (et typiquement des chaines assez longues).
J’ai codé une routine mais elle est lente. Si vous avez des sources, docs, ou conseils à me donner pour faire quelque chose de rapide et efficace, je serai ravi.
Merci.
Amiga 500 Rev6
Amiga 500 Rev5
Amiga 1200 + MTEC68030
Amiga 4000/030
Je ne maîtrise pas du tout le c ou c++.
Je te propose ce genre d’algo.
Si tu cherches une chaîne ABCDEF…Z.
Pourquoi ne pas chercher une première partie et si ça match, de regarder si la suivante match aussi.
Genre if str==’AB’ tu continue la recherches suivante si tu as ‘CD’ si tu l’as tu continues avec ‘DE’…
La tu es sur d’aller un peu plus vite car tu cherches 2 et ensuite les 2 suivant les 2 de ta recherche
Peut être avec de la recurisvite…. Ça pourrait aller plus vite.
Qu’en pensez vous ?
Après comme dit plus haut, je ne suis pas pro de la programmation. ^^
Un petit lien ici mieux documenté.
Amiga + CPC + PC = La meme passion !
Sympa comme challenge 🙂
Avec un bon vieux memcmp(), tu dois pouvoir économiser un peu de temps CPU, puisque la fonction abandonnera la comparaison à la première différence constatée.
On retomberait donc un peu sur la solution proposée par @Thor1230
En gros, tu fais une boucle qui fait un memcmp() sur ton bloc de réference, et si la comparaison échoue, tu avances…
Possiblement optimisable, d’ailleurs (mais j’suis pas une brute en algo…)
Si tu veux partager ton source, n’hésite pas (ici ou sur un gist ou autre)PS. le C ne sait pas comparer plusieurs octets d’un coup avec l’opérateur =
C’est un langage volontairement rudimentaire (sans ouvrir le débat, on peut dire que le C est plus proche de l’ASM que du C++)Qu’appelles tu lente ? Tu peux donner ton implem pour qu’on regarde ?
Tu t’autorise à des fonctions de support (strchr(), strstr() ?
Ta routines est supposée te retourner quoi ? Si je suppose que le début de la chaine hexa convient, alors ceci marche:
#if 1 /* si on a droit à cet include: */ #include <string.h> #else /* on implemente tout: */ /* on peut être plus rapide avec l'algo Knuth-Morris-Pratt qui est sans doute implémenté dans la routine standard */ char *strstr(char *s, char *t) { if(!*s) return *t ? NULL : s; /* cas débile, mais bon */ do { /* j'aurais bien utilisé "i", mais [ i ] est interprété comme une mise en italique :( */ int j=0; while(s[j] && s[j]==t[j]) ++j; if(!t[j]) return s; } while(*++s); return NULL; } #endif /* x entre min et max */ #define between(x,min,max) ((min)<=(x) && (x)<=(max)) /* x un chiffre hexa (case insensitive) */ #define hexdigit(x) (\ between(x,'0','9') || \ between(x,'a','f') || \ between(x,'A','F') ) /* retourne un pointeur sur une chaine hexa contenu dans la chaine "s", ou NULL s'il n'y a pas de chaines hexa */ char *findhex(char *s) { char *t = strstr(s, "0x"), c; return t && (c=t[2]) && hexdigit(c) ? t : NULL; }Si tu veux en plus retourner en plus la longueur de la chaine hexa:
/* pareil que findhex(), mais retourne dans "*len" la longeur de la chaine hexa */ char *findhex2(char *s, int *len) { char *t = findhex(s); *len = -1; /* ou autre chose */ if(t) { int j=3; char c; while((c=t[j]) && hexdigit(c)) ++j; *len = j; } return t; }Samuel.
Amiga A500 + GVP530 (8Mo/fpu/mmu/scsi) - en panne 🙁
A500 (+ 1Mo PPS), A1200 (Blizzard-IV/fpu/64Mo)
A500 Vampire V2+ ^8^ 🙂
(mais aussi TO8, TO8D, TO9. Groupe PULS.)
Si tu cherches ABCD, tu commences par chercher tous les A et tu stockes dans un tableau les 3 caractères qui le suivent donc tu auras un tableau qui ne contiendra que les chaînes de 4 caractères commençant pas A avec bien entendu la position en mémoire dans un fichier où dans une grande chaîne. . Dans ce tableau tu cherches B en 2ème lettre si il n’y est pas tu supprimes l’occurrence dans le tableau, ensuite pareil pour C et D.
L’avantage c’est que tu ne vas scanner toute la liste qu’une fois et qu’au fur et à mesure il y a de moins en moins de données à scanner.. A la fin dans ton tableau il te restera les chaînes ABCD et les pointeurs associés….WINUAE...
Déjà le C K&R est LE langage 🙂 le seul truc c’est qu’il faut réfléchir on est loin de l’IHM construite en 5 minutes en PHP.
La réponse de samuel doit pas mal marcher même si il est illisible on dirait du forth 🙂ta demande est trop floue si tu arrives à la préciser notamment sur le format de ta chaine sa longueur dans laquelle il faut rechercher, on pourrait aller sur des opérations au niveau du binaire avec des opérateurs logiques en embarqué temps réel on a pas beaucoup de place ni de temps on l’utilise beaucoup. ça me rapelle des souvenirs meme si ça fait 15 ans que j’ai pas pondu de code, ça manque …
Sinon quand vous chercher des algos numériques il y a beaucoup de choses là.
C’est pas illisible, c’est du C! 😛
On peut faire pire en utilisant exlusivement des pointeurs au lieux de tableaux, mais ca change pas le code produit et rend la lecture plus complexe.
https://franke.ms/cex/z/YBnI06
Samuel.
Amiga A500 + GVP530 (8Mo/fpu/mmu/scsi) - en panne 🙁
A500 (+ 1Mo PPS), A1200 (Blizzard-IV/fpu/64Mo)
A500 Vampire V2+ ^8^ 🙂
(mais aussi TO8, TO8D, TO9. Groupe PULS.)
@sam
Je pense pas que ta version prenne en compte que la chaine puisse contenir des 0 et non pas seulement finir par un 0Et aussi que le début de l’hexa cherché puisse être « a cheval » sur 2 octets
Genre cherche AB et le trouve dans 2A BC
@spectro88
On est d’accord mais pourquoi garder les endroits ou on a trouvé le 1er octet dans une liste (vite saturée => plus de mémoire)
autant finir de comparer la chaine hexa
Genre: tant que pareil comparer sinon echouerPour vraiment maximiser les perfs il faudrait lire deux ULONG de 32 bits et les shifter et comparer a un ULONG contenant en binaire les 8 premiers digits de la chaine hexa
@thellier Je ne vois pas ce qui te bloque:
- Qu’entends tu par « finir par 0 »: caractère ‘0’ Ou ‘\0’ ? En C une chaine s’arrête toujours sur ‘\0’, et il est bien question de trouver un 0xHHHHHH dans une chaine. Si on ne parle pas de chaine mais de binaire, c’est pas difficile il suffit de remplacer les tests à ‘\0’ par une égalité du pointeur avec l’adresse de fin.
- Je ne comprends pas le « à cheval sur 2 octets ». Peux tu préciser ? (car je ne vois pas de 0x dans ton exemple, et le A et le B ne semblent pas être non plus des caractères)
hmm .. c’est lié à la spec qui est imprécise. Moi j’ai compris trouver 0xHHHHHH(inconnu) dans une chaine. Et toi tu as compris étant donné un motif *binaire* connu, le retrouve-ton dans une flux de bit ? C’est pas la même chose en effet. Par contre c’est typique des algorithmes de recherches de motifs à base de machines à états (algo KMP). Est-ce que l’OP peut préciser sa demande: flux de données binaire ok mais alignement à l’octet, au 1/2 octet ou au bit ?
Samuel.
Amiga A500 + GVP530 (8Mo/fpu/mmu/scsi) - en panne 🙁
A500 (+ 1Mo PPS), A1200 (Blizzard-IV/fpu/64Mo)
A500 Vampire V2+ ^8^ 🙂
(mais aussi TO8, TO8D, TO9. Groupe PULS.)Bon je propose autre chose dans le cas on cherche non pas une chaine hexa, mais un motif de 32bits pré-déterminé (motif) aligné suivant « alignment » dans une chaine binaire
typedef unsigned char byte; int find( byte *buffer /* buffer binaire */, int len /* longueur en octets */, int alignment /* alignement du motif recherché en bits de 1 à 8 */ , long motif /* le truc qu'on cherche a trouver dans le bon bit/byte-order) */ ) { int i, j = 8, m =(1<<alignment)-1 ; long t = 0; if((j-=alignment)>=0) for(i=0;i<len;) { t = (t<<alignment) | ((buffer[ i ]>>j) & m); if(t==motif) return i*8 + ((8-j)&7); /* on retourne l'offset en bits */ if((j-=alignment ) <=0) j += 8, ++i; } return -1; /* rien trouvé */ } int find1(byte *buffer, int len, long motif) { /* aligné sur 1 bit */ return find(buffer, len, 1, motif); } int find4(byte *buffer, int len, long motif) { /* aligné sur 1/2 octet */ return find(buffer, len, 4, motif); } int find8(byte *buffer, int len, long motif) { /* aligné sur 1 octet */ return find(buffer, len, 8, motif); }Le code ASM produit m’a l’air bien pour le find8:
_find8: move.l d2,-(sp) move.l (12,sp),a1 move.l (16,sp),d2 move.l a1,d0 jle .L41 clr.l d0 clr.l d1 move.l (8,sp),a0 .L40: lsl.l #8,d1 or.b (a0)+,d1 cmp.l d2,d1 jeq .L45 addq.l #1,d0 cmp.l a1,d0 jne .L40 .L41: moveq #-1,d0 move.l (sp)+,d2 rts .L45: lsl.l #3,d0 move.l (sp)+,d2 rtsSamuel.
Amiga A500 + GVP530 (8Mo/fpu/mmu/scsi) - en panne 🙁
A500 (+ 1Mo PPS), A1200 (Blizzard-IV/fpu/64Mo)
A500 Vampire V2+ ^8^ 🙂
(mais aussi TO8, TO8D, TO9. Groupe PULS.)
12 sujets de 1 à 12 (sur un total de 12)
- Vous devez être connecté pour répondre à ce sujet.
› Forums › AmigaOS, MorphOS et AROS › Développement › Programmation C
