Programmation C

12 sujets de 1 à 12 (sur un total de 12)

  • Mathdea

    • Messages : 236
    #349162

    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

    Thor1230

    • Messages : 920
    #349221

    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é.

    https://forums.futura-sciences.com/programmation-langages-algorithmique/141329-chercher-une-chaine-de-caractere-un-texte-langage-c.html#:~:text=Re%20%3A%20chercher%20une%20chaine%20de%20caractère%20dans%20un%20texte%20en%20Langage%20C,-Salut%2C&text=Bonjour%2C,sous-chaîne%20dans%20une%20chaîne.&text=La%20fonction%20strstr()%20fait,disponible%20sur%20toutes%20les%20platformes.

    Amiga + CPC + PC = La meme passion !

    Astrofra

    • Messages : 12
    #349238

    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++)

    __sam__

    • Messages : 2686
    #349241

    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.)

    SPeCTRo88

    • Messages : 606
    #349243

    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….

    INFINITIV A1200+Vampire V1200v2+MKIIcr+RYS+SUM USB V2+CF32Go+CF16Go+CF8Go+HDD120Go

    gordini21

    • Messages : 33
    #349245

    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à.

    Cliquer pour accéder à NumericalRecipesinC.pdf

    __sam__

    • Messages : 2686
    #349248

    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.)

    gordini21

    • Messages : 33
    #349250

    🙂 pour moi c’est lisible et je te rassure j’ai fait bien pire sur des logiciels de traction ferroviaire avec 2Mo on a pas trop le choix faut compacter.

    lexomil

    • Messages : 209
    #349277

    J’aurais tendance à d’abord convertir la chaine que tu recherches en binaire (tableau d’octets) et de faire ensuite de simples comparaisons octet par octet dans ton buffer.

    sinon j’ai pas pu m’empécher de downloader le bouquin proposé par gordini 🙂

    thellier

    • Messages : 673
    #349279

    @sam
    Je pense pas que ta version prenne en compte que la chaine puisse contenir des 0 et non pas seulement finir par un 0

    Et 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 echouer

    Pour 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

    __sam__

    • Messages : 2686
    #349291

    @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.)

    __sam__

    • Messages : 2686
    #349313

    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
            rts
    

    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.)

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

Do NOT follow this link or you will be banned from the site!