Journal Parlons C, parlons pipe !

27
21
août
2012

Mon livre de chevet, Unleashed C (non je mens, mon livre de chevet reste Playboy, mais ça fait moins sérieux), propose d'implémenter une FIFO (ou "pipe", pour tube en anglais) de la façon suivante (approximativement, j'ai simplifié la représentation (surtout il y avait QUEUE écrit et je veux pas de problèmes)) :

+----------+
| taille   |
+----------+
| debut    |-------+
+----------+       |
| fin      |       |
+----------+       V
  |              +---+---------+
  |              | s | donnes  |
  |              +---+---------+
  |                |
  |                V
  |              +---+---------+
  +------------->| s | donnes  |
                 +---+---------+
                   |
                   V
                   NULL

Avec, bien entendu, plein de code C manipulant des pointeurs (que j'aime :D).

Moi je veux une petite FIFO. Une pouvant contenir 4 caractères (voir 8) ; la version du livre est un peu gore dans ce cas.

Une FIFO, on pousse à droite, ça sort à gauche. On pousse à droite … ça me rappelle un opérateur : <<. Je prends une variable, pouvant contenir des valeurs de 4 ou 8 octets, une variable pour compter et j'ai une FIFO. Rudimentaire mais suffisante !

Donc ma FIFO commence sa vie avec une structure :

/* Ne pas déraper, ne pas déraper, ... */
typedef struct s_small_dick { /* /o\ */
    unsigned char count;
    uint32_t data; /* uint64_t pour 8 caracteres */
} SmallFifo;

Ensuite il faut quelques fonctions pour la faire vivre. D'abord l'initialisation (pour la forme) :

void sf_init(SmallFifo * f)
{
    if(f==NULL) return;
    f->count=0;
    f->data=0;
    return;
}

Ensuite je veux pouvoir ajouter des valeurs. Cette opération est d'une simplicité déconcertante.

void sf_push(SmallFifo * f, unsigned char b)
{
    if(f==NULL) return;
    /* C'est une FIFO qui, si elle est pleine, éliminent les valeurs les plus
     * anciennes (pas conseillé pour la retraite ^^).
     */
    f->data=(f->data<<8)|b;
    if(f->count<sizeof(f->data)) f->count++;
}

Pour récupérer les valeurs, nous allons, très simplement, appliquer la méthode suivante :

unsigned char sf_pop(SmallFifo * f)
{
    if(f==NULL) return 0x00;
    /* Pas tomber trop bas */
    if(f->count>0) f->count--;
    return (unsigned char)(f->data>>(8 * f->count)) & 0xFF;
}

Et, pour la forme, une fonction qui retourne une valeur différente de 0 s'il y a encore des données dans notre FIFO :

unsigned char sf_has_data(SmallFifo * f)
{
    if(f==NULL) return 0x00;
    if(f->count>0) return 0xEB; /* mes initiales \o/ */
    return 0x00;
}

Bien entendu, ce code n'a été que brièvement testé et contient, peut-être, des erreurs.

int main(int argc, char ** argv)
{
    SmallFifo ma_fifo;
    char des_valeurs[]="abcdefghijklmnopqrstuvwxyz";
    int i=0; /* un compteur */

    sf_init(&ma_fifo);

    for(i=0;i<4;i++) {
        sf_push(&ma_fifo, des_valeurs[i]);
    }
    while(sf_has_data(&ma_fifo)) {
        printf("%c ", sf_pop(&ma_fifo));
    }
    printf("\n");

    for(i=0;i<26;i++) {
        sf_push(&ma_fifo, des_valeurs[i]);
    }
    while(sf_has_data(&ma_fifo)) {
        printf("%c ", sf_pop(&ma_fifo));
    }
    printf("\n");

    return 0;
}

Pour tester ce code, n'oubliez pas d'inclure stdint.h ou alors changer le type en unsigned long int, ça devrait faire 4 octets même sur un AVR ou un PIC.

PS: Si, par mégarde, j'ai choqué une femme dans ce journal, j'en suis désolé. Pour me faire pardonner, j'accepterais jusqu'aux châtiments corporels, y compris être tuer et violer tant que ça reste dans cet ordre là (sauf ma copine, halle_berry.jpeg, qui peut le faire dans l'ordre inverse).

  • # Constante invalide

    Posté par . Évalué à  10 .

     if(f->count>0) return 0xEB; /* mes initiales \o/ */
    
    

    Moi, je lis « Enormous Boobs ». C'est sexiste ! Je te demande de changer de constante.

    unsigned char sf_pop(SmallFifo * f)
    {
         if(f==NULL) return 0x00;
         /* Pas tomber trop bas */
         if(f->count>0) f->count--;
         return (unsigned char)(f->data>>(8 * f->count)) & 0xFF;
    }
    
    

    Quand tu fais ceci, tu récupères l'octet situé à la position « count », mais tu n'effaces pas le contenu de « data », et tu ne tiens pas compte du fait non plus que ta file peut être vide (sauf pour la gestion de « count »). Ça veut dire d'une part que si tu continues à dépiler une file vide, tu vas obtenir à chaque fois la dernière valeur dépilée qui peut être non nulle.

    Puisque tu utilises déjà des opérateurs de décalage sur des registres du même format, pourquoi ne t'en sers-tu pas pour décaler directement le contenu de ta file ?

    data >>=8;
    return data & 0xff;
    
    
    • [^] # Re: Constante invalide

      Posté par (page perso) . Évalué à  1 .

      Bien vu. je n'y avais pas penser. Merci :)

      "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

      • [^] # Re: Constante invalide

        Posté par (page perso) . Évalué à  10 .

        Alors, tu remplace le verbe par mordre, et si ça donne "mordu", tu met un "é" à la place du er. Ça fonctionne à la fois dans les commentaires et les journaux ("être tuer et violer" => "être mordu et mordu", donc "être tué et violé")

        PS : Pour le reste des conjugaisons, je te laisse te renseigner, mais il y a d'autres règles, et "C'est une FIFO qui […] éliminent les valeurs" confirme que "ce code […] contient, peut-être, des erreurs."

      • [^] # Re: Constante invalide

        Posté par (page perso) . Évalué à  3 .

        Ah non ! là tu as une LIFO ! Le dernier élément entré est le premier sorti dans ton cas :

          +-------+-------+-------+-------+
        1 |   0   |   A   |   B   |   C   | << 8 | 'D'
          +-------+-------+-------+-------+ 
          +-------+-------+-------+-------+
        2 |   A   |   B   |   C   |   D   | >> 8
          +-------+-------+-------+-------+ 
          +-------+-------+-------+-------+
        3 |   0   |   A   |   B   |   C   | 
          +-------+-------+-------+-------+ 
        
        

        "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

        • [^] # Re: Constante invalide

          Posté par . Évalué à  2 .

          Oui, c'est parce que j'ai un raccourci trop rapide, en effet.

          Le principe demeure cela dit mais en fait, c'est déjà ce que tu fais à l'entrée. Tu décales à l'empilement et tu vas chercher la bonne position au dépilement. C'est effectivement l'un ou autre.

          • [^] # Re: Constante invalide

            Posté par (page perso) . Évalué à  2 .

            Si je fais ainsi, c'est parce que l'empilement est fait durant une interruption, donc je fais le plus simple et court possible afin d'en sortir au plus vite.

            "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

            • [^] # Re: Constante invalide

              Posté par (page perso) . Évalué à  5 . Dernière modification : le 22/08/12 à 16:52

              Si tu veux faire court en général:

              au lieu de:

                  unsigned char sf_has_data(SmallFifo * f)
                  {
                      if(f==NULL) return 0x00;
                      if(f->count>0) return 0xEB; /* mes initiales \o/ */
                      return 0x00;
                  }
              
              

              utilise plutôt:

                  unsigned char sf_has_data(SmallFifo * f)
                  {
                      assert (f != NULL);
                      return (f->count > 0);
                  }
              
              

              Tu pourras désactiver les assertions dans un build en mode release. Perso je fais plutôt des fonctions is_empty que has_data, je pense que c'est plus répandu. Ah, et tu gagnes un tout petit peu sur le return, mais tu n'as certes plus tes initiales :)

              • [^] # Re: Constante invalide

                Posté par (page perso) . Évalué à  3 .

                Pour les assert, je les utilises très peu dans les bibliothèques de fonctions : ces fonctions peuvent être utilisées dans du code dont tous les chemins n'ont pas été testés avant d'être en production et c'est souvent à ce moment là que le bug apparaît.

                Pour le has_data, perso je trouve plus joli :

                while(has_data());
                
                

                que

                while(!is_empty());
                
                

                Mais c'est très personnel tout ça :)

                "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

                • [^] # Re: Constante invalide

                  Posté par (page perso) . Évalué à  2 .

                  Ah mais je suis d'accord avec toi sur les assert, c'est juste que tu n'as pas dit que c'était pour une bibliothèque ;-).

                  Pour le has_data, je dirais que un popcorn_bag.has_data() est plus laid que popcorn_bag.is_empty(), même si effectivement, quand on écrit une application on a tendance à tester plus souvent la présence que l'absence de données (sauf dans les préconditions).

                • [^] # Re: Constante invalide

                  Posté par . Évalué à  6 .

                  C'est même encore mieux avec

                      while(I_can_haz_data());
                  
                  

                  :)

                • [^] # Re: Constante invalide

                  Posté par (page perso) . Évalué à  2 .

                  Pour les assert, je les utilises très peu dans les bibliothèques de fonctions

                  Ama c'est justement là qu'ils sont utilent, là le code peut tourner bien après que la FIFO soit initialisée (même si elle est nulle). Ça devrait crasher dès le début. En plus ça spécifie le contrat.

                  Perso j'aime bien quand y'a des espaces dans le code, ça coûte pas chère et ça améliore la lisibilité (j'suis un vieux con à lunettes).

                  if (f->count > 0)

                  Pour info tu as sys/queue.h qui gère des listes tout en macros (mais pas de taille fixe).
                  http://fxr.watson.org/fxr/source/sys/queue.h

    • [^] # Lapin tout compris

      Posté par (page perso) . Évalué à  1 .

      Il m'a pas mal perturbé de "& 0xFF".
      Si j'ai compris, il s'agit en fait de ne garder que le dernier octet de data?

      Si c'est bien ça, "& 0x000000FF" me semble plus lisible. (J'ai pu me gourer sur le nombre de 0)

      • [^] # Re: Lapin tout compris

        Posté par . Évalué à  10 .

        (J'ai pu me gourer sur le nombre de 0)

        Tu viens d'expliquer pourquoi il ne l'a pas fait comme ça.

        Je suis dans ma tour d'ivoire (rien à foutre des autres, dites moi un truc pour moi), si je ne pose pas explicitement une question pour les 99%, les kévin, les Mm Michu alors c'est que je ne parle pas d'eux.

      • [^] # Re: Lapin tout compris

        Posté par . Évalué à  2 .

        Bah, le "& 0xFF" ne sert à rien puisque data est initialisé à 0 au départ et que c'est un unsigned int..

  • # compteur ?

    Posté par . Évalué à  10 . Dernière modification : le 21/08/12 à 14:33

    C'est pas plus simple d'utiliser un tableau d'octet et un compteur de début et de fin ? Comme un buffer tournant ?

    "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

    • [^] # Re: compteur ?

      Posté par . Évalué à  4 .

      Si.

    • [^] # Re: compteur ?

      Posté par (page perso) . Évalué à  1 .

      Si, mais ça fait une variable de plus, donc de la mémoire en moins.

      "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

      • [^] # Re: compteur ?

        Posté par . Évalué à  1 .

        C'est vrai, mais ça te permet en revanche de gérer une file d'une longueur arbitraire sans avoir à décaler tout son contenu. Avec 4 octets, la différence est subtile, avec 4096 elle devient beaucoup plus nette.

        • [^] # Re: compteur ?

          Posté par (page perso) . Évalué à  2 .

          Oui, mais je veux une file pour quelques octets. Pour 4096 valeurs, j'utiliserais une version proche de celle présentée au début.

          "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

          • [^] # Re: compteur ?

            Posté par . Évalué à  2 .

            Oui mais justement, même pour quelques octets, c'est plus simple et plus efficace : en fait, la méthode des décalages telle que tu l'as écrite n'est intéressante qu'à partir du moment où ta file tient sur un seul entier (ou que les mots que tu empiles ne sont pas multiples de huit bits). Dès que tu dépasses 8 octets (si l'on considère le cas du long long), alors tu es obligé d'utiliser plusieurs variables consécutives.

            De là, soit tu utilises une boucle et un pointeur, ce qui t'oblige à déclarer des variables supplémentaires, soit tu gères manuellement chacun de tes registres en contrôlant à chaque fois s'il est concerné en fonction de la valeur de « count ». Tu gagnes quatre octets de RAM mais tu perds 64 octets de ROM. Ce genre de chose est effectivement à prendre en compte dans le cas de micro-contrôleurs, mais pas sur PC. Pas seulement parce que la quantité de RAM disponible est considérable, mais surtout parce que c'est la même dans les deux cas.

            • [^] # Re: compteur ?

              Posté par (page perso) . Évalué à  3 .

              Je pensais que la référence aux micro-contrôleurs en fin de journal permettrait de faire comprendre que la cible de ce code est des petits micro-contrôleurs avec quelques centaines d'octet de RAM.
              Et si je veux un file pour 4 ou 8 octets, le cas où j'en ai 6000 ne m'intéresse pas. La vitesse de remplissage de la file est de l'ordre de 800 octets par secondes et je peux les traiter dix fois plus vite. Le seul cas où la pile est utilisée, c'est juste pour que le processeur dorme un peu plus et donc économise du courant (j'attend un taux de remplissage avant de commencer le traitement).

              "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

      • [^] # Re: compteur ?

        Posté par (page perso) . Évalué à  1 .

        Si tu veux jouer à ça :

        • Si tu te limite à un queue de 4(8) chars, tes index tiennent sur 2(3) bites. Au total tu as 4(6) bites utilisées. C'est bien moins que ton "unsigned char count" pour compter jusqu'à 4.
        • Quand on sait que, en général, tes structures sont alignées sur 32 bites (voir 64 sur les porcs boostés aux hormones), tu as de l'espace à remplir, tu peux avoir quelque bites de plus.

        Pardon aux familles …

        Matthieu Gautier|irc:starmad

        • [^] # Re: compteur ?

          Posté par (page perso) . Évalué à  4 .

          Non, mais j'ai mis, en fin de journal, des références aux micro-contrôleurs AVR ou PIC qui sont 8 bits et ont de quelques centaines d'octets à quelques kilo-octets de RAM disponible.

          Donc des structures alignées sur 32 bits, voir 64 bits, … non.

          "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

          • [^] # Re: compteur ?

            Posté par (page perso) . Évalué à  2 .

            Ouai, enfin à ce moment là, t'es en train de manipuler des entiers 32 bits avec un proc 8 bits. Tu gagnes peut-être en mémoire mais ça coute cher derrière au niveau proc. (Surtout que tu as l'air de vouloir faire ça rapidement, au regard d'un de tes autres commentaires)

            Et puis ma première solution tient toujours :P

            Matthieu Gautier|irc:starmad

            • [^] # Re: compteur ?

              Posté par (page perso) . Évalué à  3 .

              Mais je privilégie l'espace mémoire à la vitesse. La vitesse, j'ai une bonne marge. La mémoire, peu de marge.

              Mais je ne dis pas que ma solution est la solution. C'est une solution qui me semble élégante et fonctionnelle. Je peux me tromper lamentablement. C'est pourquoi je la présente, afin de partager ma réflexion et avoir des avis en retour (il y'a certainement des gens bien plus expérimentés que moi sur ce site).

              "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

              • [^] # Re: compteur ?

                Posté par (page perso) . Évalué à  2 .

                Bon c'est plus pour le fun la rigolade qu'autre chose, mais je l'ai fait avec un tableau circulaire.

                Je ne suis pas sur que ça sois plus performant …

                #include <string.h>
                
                
                #define readMask            0b00110000
                #define readOverflowMask    0b10111111
                #define writeMask           0b00000011
                #define writeOverflowMask   0b11110011
                
                #define dataPresentMask     0b10000000
                
                #define GET_READ(X)  (((X)&readMask)>>4)
                #define INC_READ(X)  (((X)+(1<<4))&readOverflowMask)
                
                #define GET_WRITE(X)  ((X)&writeMask)
                #define INC_WRITE(X)  (((X)+1)&writeOverflowMask)
                
                /* Pas taper, c'est pas moi qui ai choisi le nom */
                typedef struct s_small_dick { /* /o\ */
                    unsigned char index;
                    char data[4];
                } SmallFifo;
                
                void sf_init(SmallFifo * f)
                {
                    if (f == NULL) return;
                    f->index=0;
                    memset(f->data, 0, 4);
                    return;
                }
                
                void sf_push(SmallFifo * f, unsigned char b)
                {
                    if(f==NULL) return;
                    /* C'est une FIFO qui, si elle est pleine, éliminent les valeurs les plus
                     * anciennes (pas conseillé pour la retraite ^^).
                     * On increment avant. C'est utile au moment du read, on incremente avant et on a pas besoin de stoker la valeur de retour dans une variable temporaire.
                     */
                
                    if ( f->index&dataPresentMask && (f->index&writeMask)==((f->index&readMask)>>4) )
                    {
                        /* On est en train de boucler en écriture et on efface les anciennes valeures.
                         * On avance aussi le readIndex
                         */
                         f->index = INC_READ(f->index);
                    }
                
                    f->index = INC_WRITE(f->index)|dataPresentMask;
                
                
                    f->data[GET_WRITE(f->index)] = b;
                
                }
                
                unsigned char sf_pop(SmallFifo * f)
                {
                    if(f==NULL) return 0x00;
                    f->index = INC_READ(f->index);
                    if ( GET_WRITE(f->index) == GET_READ(f->index) )
                        /* si on a "ratraper" le writeIndex, il n'y a plus de donnée */
                        f->index &= ~dataPresentMask;
                    return f->data[GET_READ(f->index)];
                }
                
                unsigned char sf_has_data(SmallFifo * f)
                {
                    if(f==NULL) return 0x00;
                    if( f->index&dataPresentMask ) return 0xEB;
                    return 0x00;
                }
                
                int main(int argc, char ** argv)
                {
                    SmallFifo ma_fifo;
                    char des_valeurs[]="abcdefghijklmnopqrstuvwxyz";
                    int i=0; /* un compteur */
                
                    sf_init(&ma_fifo);
                
                    for(i=0;i<4;i++) {
                        sf_push(&ma_fifo, des_valeurs[i]);
                    }
                
                    while(sf_has_data(&ma_fifo)) {
                        printf("%c ", sf_pop(&ma_fifo));
                    }
                    printf("\n");
                
                    for(i=0;i<26;i++) {
                        sf_push(&ma_fifo, des_valeurs[i]);
                    }
                
                    while(sf_has_data(&ma_fifo)) {
                        printf("%c ", sf_pop(&ma_fifo));
                    }
                    printf("\n");
                
                    return 0;
                }
                
                

                Matthieu Gautier|irc:starmad

                • [^] # Re: compteur ?

                  Posté par . Évalué à  2 .

                  Je serais curieux de savoir si cela change quelques choses d'utiliser un tableau de taille 5 pour éviter d'avoir uns structure. Souvent les structures sont alignés en mémoire sur la taille du plus grand type C, qui peut être 16 bits ici. Ce n'est en général pas le cas des tableaux simples.

                  "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

        • [^] # Re: compteur ?

          Posté par . Évalué à  5 .

          Y a beaucoup de bites, et peu de bits, dans ce commentaire…

          • [^] # Re: compteur ?

            Posté par (page perso) . Évalué à  -2 .

            Si il n'y avait que ça…

            Mais bon, je me suis déjà excusé par avance.

            Matthieu Gautier|irc:starmad

            • [^] # Re: compteur ?

              Posté par . Évalué à  7 .

              C'est cool les excuses, c'est comme les démentis de ministres ou les condamnations de chefs d'État. Ça coûte rien, ça fais joli à la télé et personne te demande d'être sincère.

              Je suis dans ma tour d'ivoire (rien à foutre des autres, dites moi un truc pour moi), si je ne pose pas explicitement une question pour les 99%, les kévin, les Mm Michu alors c'est que je ne parle pas d'eux.

              • [^] # Re: compteur ?

                Posté par (page perso) . Évalué à  -2 .

                A ouai, en fait vous avez aucun humour dès que c'est un peu sexuel, c'est ça ?

                (Et qu'on ne me parle pas de sexisme, je ne vois pas pourquoi les filles devraient être plus choquées que les garçon, ou inversement)

                La prochaine fois, je ne m'excuserai pas. Na!

                Matthieu Gautier|irc:starmad

                • [^] # Re: compteur ?

                  Posté par . Évalué à  3 .

                  En fait tu n'a aucun humour dès que ça parle à peine de sexe ?

                  L'ironie était trop subtile ? Je présumais que l'allusion aux politiques aurait suffit à te faire voir l'humour.

                  Par contre je ne m'excuse pas de la situation, je préfère rester sincère (et là ce n'est pas ironique).

                  Je suis dans ma tour d'ivoire (rien à foutre des autres, dites moi un truc pour moi), si je ne pose pas explicitement une question pour les 99%, les kévin, les Mm Michu alors c'est que je ne parle pas d'eux.

                  • [^] # Re: compteur ?

                    Posté par . Évalué à  5 .

                    Un journal qui parle de langage C, qui tente de résoudre un cas de figure technique et qui finit en troll politico-sexiste dès le cinquième niveau d'imbrication : pas de doute, on est bien sur DLFP. Tout va bien. :-)

          • [^] # Re: compteur ?

            Posté par . Évalué à  2 .

            en même temps ça parle de pipe…

            Il ne faut pas décorner les boeufs avant d'avoir semé le vent

        • [^] # Re: compteur ?

          Posté par . Évalué à  1 .

          Petite implémentation sans compteur, pour le fun:

          #include <stdio.h>
          #include <stdint.h>
          #include <assert.h>
          
          typedef uint64_t fifo_t;
          
          #define FIFO_CAPACITY   (sizeof(fifo_t))
          
          static inline void fifo_init(fifo_t *f) {
              *f = 0;
          }
          
          static inline int fifo_is_empty(fifo_t *f) {
              return ((*f) == 0);
          }
          
          static inline void fifo_push(fifo_t *f, char val) {
              *f <<= 8;
              *f |= (0x80 | val);
          }
          
          static inline char fifo_read(fifo_t *f) {
              char res;
          
              while ((*f & (0x80UL << (8 * (FIFO_CAPACITY - 1)))) == 0)
                  *f <<= 8;
          
              res = (*f & (0x7fUL << (8 * (FIFO_CAPACITY - 1)))) >> (8 * (FIFO_CAPACITY - 1));
              *f <<= 8;
          
              return res;
          }
          
          int main(int ac, char **av) {
              const char alphabet[] = "abcdefghijklmnopqrstuvwxyz";
              fifo_t fifo;
              int i;
          
              fifo_init(&fifo);
          
              assert(fifo_is_empty(&fifo));
          
              for (i = 0; i < FIFO_CAPACITY; i++)
                  fifo_push(&fifo, alphabet[i]);
          
              while (!fifo_is_empty(&fifo))
                  printf("Read: %c\n", fifo_read(&fifo));
          
              assert(fifo_is_empty(&fifo));
          
              fifo_push(&fifo, 'z');
              assert(fifo_read(&fifo) == 'z');
          
              return 0;
          }
          
          
          • [^] # Re: compteur ?

            Posté par . Évalué à  2 . Dernière modification : le 22/08/12 à 16:51

            Tes char tiennent sur 7bits, les originaux sur 8bits sinon c'est amusant comme idée: maximiser la performance du push, au détriment d'avoir un pop/read lent.
            Autre méthode avec le même stockage qu'à l'origine:

            static inline char fifo_read(fifo_t *f) {
                  char res;
                  int8 cnt = 0;
                  fifo_t copie = *f;
                  do {
                    res = copie & 0x7f; /*on peut calculer res après aussi */
                    copie >>= 8;
                    cnt++;
                  } while (copie != 0);
            
                  *f &= ~((1 << 8*cnt)-1);
                  return res;
            }
            
            

            Après il y a des fonctions qui donne le numéro du bit de poids fort qui peuvent être plus performante mais moins portable.

      • [^] # Re: compteur ?

        Posté par . Évalué à  2 .

        Et la taille du code ? (bon évidemment s'il reste en ROM il n'est pas en RAM, mais généralement le code est en RAM. Donc faut bien vérifier lequel prend vraiment moins de place…)

        Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

        • [^] # Re: compteur ?

          Posté par . Évalué à  1 .

          La plupart des micro-controlleurs (en tout cas ceux que j'ai utilisé) exécutent le code directement à partir de la ROM, sans le copier en RAM.

  • # Merci

    Posté par (page perso) . Évalué à  10 .

    Je ne pratique pas le C parce que les soucis de gestion bas niveau ne m'avaient pas l'air intéressants. Mais avec ce journal et le dernier, agrémentés de petits commentaires qui font vivre le code et nous donnent des explications sur le pourquoi, ça donne envie. J'aime beaucoup l'approche linéaire qui suit le raisonnement qu'aurait un développeur.

    J'ai hâte de lire la suite !

    En un mot : Merci !

    • [^] # Re: Merci

      Posté par (page perso) . Évalué à  4 .

      :) ça fait plaisir ce genre de commentaires. Merci.

      "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

    • [^] # Re: Merci

      Posté par . Évalué à  1 .

      Sur de petit exemples comme ça, c'est amusant les optimisations de bas niveau, c'est quand tu essaye de faire un "gros" programme que tu vois rapidement l'intérêt des langage de haut niveau comme Python/OCaml..

  • # question conne

    Posté par (page perso) . Évalué à  3 .

    A quoi te sert le return à la fin de sf_init ? C'est ptête un oubli de ta part ou bien une subtilité qui m'aurait échappé, c'est pour ça que je pose la question.

    Chippeur, arrête de chipper !

    • [^] # Re: question conne

      Posté par (page perso) . Évalué à  6 .

      Je trouve joli les return;. C'est la seule explication.

      "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

      • [^] # Re: question conne

        Posté par (page perso) . Évalué à  10 .

        C'est vrai que maintenant que tu le dis, plus je le regarde et plus les larmes me montent aux yeux.

        Chippeur, arrête de chipper !

        • [^] # Re: question conne

          Posté par . Évalué à  -3 .

          C'est vrai que maintenant que tu le dis, plus je le regarde et plus les larmes me montent aux yeux.

          +42 pour m'avoir déclenché un fou-rire.

  • # Gestion des paramètres

    Posté par . Évalué à  3 . Dernière modification : le 21/08/12 à 15:47

    Dans toutes tes fonctions tu gère les paramètres NULL comme ça :

    void my_function(SmallFifo * f)
    {
        if(f==NULL) return;
        /* le reste de la méthode */
    }
    
    

    Je comprend bien le coté esthétique, mais n'est-il pas plus performant (si on considère que l'utilisateur va plus souvent t'envoyer un pointeur valide qu'un NULL) d'écrire :

    void my_function(SmallFifo * f)
    {
        if(f!=NULL) {
            /* le reste de la méthode */
        } else {
            return NULL;
        }
    }
    
    

    Si je ne me trompe pas ça diminue les erreurs de prefetch d'instructions par la CPU (je crois savoir que c'est important sur des CPU avec un pipeline long comme les P4, je ne sais pas si c'est valable sur ton micro-controlleur.

    PS : à la réflexion la condition est un peu plus lourde donc peut être que c'est pas si bien que ça.

    Je suis dans ma tour d'ivoire (rien à foutre des autres, dites moi un truc pour moi), si je ne pose pas explicitement une question pour les 99%, les kévin, les Mm Michu alors c'est que je ne parle pas d'eux.

    • [^] # Re: Gestion des paramètres

      Posté par (page perso) . Évalué à  3 .

      Tu soulèves un point pertinent. Je n'ai rien vu sur ce sujet, mais comme il y a une instruction Compare, Skip if Equal, ça me semble logique de le faire comme je le fais. Maintenant je n'ai pas encore regarder plus en détail que ça.

      "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

      • [^] # Re: Gestion des paramètres

        Posté par . Évalué à  1 .

        Je suis aussi étonné de cette gestion des paramètres nulls, je ne comprend pas quel sens aurait l'initialisation réussie de rien du tout.

        Ça me semble risquer le fait que l'on puisse faire tourner ce code super longtemps avant de se rendre compte qu'il n'y a tout simplement pas de file et que les fonctions faisaient poliment semblant de travailler dessus « Ne le contrarions pas, dieu sait ce qu'il nous arriverait sinon ».

        Please do not feed the trolls

    • [^] # Re: Gestion des paramètres

      Posté par (page perso) . Évalué à  2 .

      Si je ne me trompe pas ça diminue les erreurs de prefetch d'instructions par la CPU (je crois savoir que c'est important sur des CPU avec un pipeline long comme les P4, je ne sais pas si c'est valable sur ton micro-controlleur.

      Beaucoup de processeurs (dont le P4) ont une bonne prédiction de branchement. De plus on peut espérer que si sur l'architecture cible la deuxième écriture est beaucoup plus performante que la première le compilateur fasse l'optimisation tout seul. De manière générale, si on peut se permettre de tester partout, il parait plus approprié d'écrire le code le plus lisible possible.

      • [^] # Re: Gestion des paramètres

        Posté par (page perso) . Évalué à  3 .

        En cas de doute tu peux optimiser cela. La GLib utilise les macros G_LIKELY/G_UNLIKELY comme front-end aux directives gcc idoines.

        Du coup, un:

        if G_UNLIKELY (f == NULL) return;
        
        

        n'est pas moins clair ni performant, juste un poil plus lourd à écrire. Reste plus qu'à tester la version avec et sans pour son architecture, pour savoir si cela apporte quelque chose ou si la prédiction de branches de gcc est suffisante.

      • [^] # Re: Gestion des paramètres

        Posté par . Évalué à  1 .

        Beaucoup de processeurs (dont le P4) ont une bonne prédiction de branchement.

        Quelle heuristique ils utilisent ?

        Je suis dans ma tour d'ivoire (rien à foutre des autres, dites moi un truc pour moi), si je ne pose pas explicitement une question pour les 99%, les kévin, les Mm Michu alors c'est que je ne parle pas d'eux.

        • [^] # Re: Gestion des paramètres

          Posté par . Évalué à  3 .

          Ils ont une table interne au processeur. Quand tu passes sur un choix, il vire l’entrée la plus ancienne et ajoute que à telle adresse on a sauté ou pas. Au passage suivant il recommence. Au bout de quelques passages, si le saut est plus courant, le proc va suposé que tu va « jumpé » (le saut) est donc remplir le pipe avec ce qui suit le saut. Ça évite le flush du pipe en cas de mauvais branchement.
          J’avais fait des tests sur PowerPC en 2004 pour mon boulot sur une petite fonction.
          1er passage 2μs (2000ns)
          2ième passage 1800ns. (cache instruction rempli)

          18ième passage 1800ns.
          19ième passage 950ns.

          De 2 à 18 le temps varié avec un écart type de 50ns. Au 19ième passage, je gagnais 1μs. Il faut voir que ceci se met en place que en cas de boucle, et si un autre processus ne prend pas la main pour exploser tous les points de passage noté.
          Ce test remonte à il y a quelques temps. Je ne sais pas comment gère les CPUs multi-cœur. La table est-elle commune ? ou lié à un cœur ? Dans ce cas, l’OS a intérêt à remettre un même thread sur le même cœur.

          • [^] # Re: Gestion des paramètres

            Posté par (page perso) . Évalué à  3 .

            Le problème d'un tel mécanisme sur le type de cible de l'auteur, c'est que si son temps de traitement est trop lent avant que le proco n'ait optimisé la boucle, le buffer explose. Et si le traitement "non optimisé" est suffisamment rapide, alors l'optimisation ne sert à rien.
            Les applications de ce type sont généralement temps réelles. Il faut traiter les données à mesure qu'elles se présentent au micro-contrôleur : impossible de les traiter plus rapidement, interdit de les traiter plus lentement.

            (En outre, un proco 8 bits à peu de chance de posséder un tel mécanismes de prédictions).

        • [^] # Re: Gestion des paramètres

          Posté par . Évalué à  3 .

          Il existe plusieurs niveau de complexité.

          Les instructions de saut typique contiennent l'adresse de saut. Il faut savoir si le saut est effectué ou pas avant la fin de l’exécution de "quelques instructions" dans le pipeline.

          Le niveau le plus basique est : "forward not taken, backward taken". En gros, si l'adresse est en avant du PC, le saut n'est pas pris (cas d'un if qui est vrai), si le saut est en arrière, il est pris (cas d'une boucle).

          Dans les faits, cette prédiction n'est pas si mauvaise que ça.

          Le niveau suivant utilise une machine d'état à 4 états : strong taken - taken - not taken - strongly not taken. Le saut effectué ou pas fait changer d'état cette machine d'état. Il existe des cpu qui ont une seul de ces machines, pour aller plus loin que la prédiction statique. Les cpu moderne disposent de ces 2 bits d'information pour quelques centaines d'adresses d'instruction de saut.

          Seul les cpus de la génération du core 2 et suivant possèdent une gestion des sauts indirects, avec sauvegarde de l'adresse de saut dans le buffer (comme les tableaux de fonction ou les vtable).

          "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

          • [^] # Re: Gestion des paramètres

            Posté par . Évalué à  2 .

            Merci pour les explications.

            Le niveau le plus basique est : "forward not taken, backward taken". En gros, si l'adresse est en avant du PC, le saut n'est pas pris (cas d'un if qui est vrai), si le saut est en arrière, il est pris (cas d'une boucle).

            Ça signifie bien que c'est le return qui est chargé dans le cas présent, c'est ça ?

            Je suis dans ma tour d'ivoire (rien à foutre des autres, dites moi un truc pour moi), si je ne pose pas explicitement une question pour les 99%, les kévin, les Mm Michu alors c'est que je ne parle pas d'eux.

            • [^] # Re: Gestion des paramètres

              Posté par . Évalué à  2 .

              Dans ton code objet, le fetcher du cpu, le bloc qui va chercher les instructions a executer va tomber sur un
              JUMP 0X012345678

              Cette instruction peut être conditionnel, or la condition n'est pas calculer. Il doit choisir si il va chercher l'adresse PC+4 comme d'habitude (sur un risc 32 bits) ou 0x012345678.

              Savoir si la clause du if qui est exécuté dépend de la forme du code assembleur choisi par le compilateur. J'aurais tendance à dire que dans un if qui a 2 clause, la clause vrai sera privilégié, mais si il n'y a qu'une clause, elle sera sauté.

              "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

  • # static ?

    Posté par . Évalué à  2 .

    Est-ce que ce genre de code est mis dans un .h ou dans son .c à part ?

    Si la bibliothèque est souvent utilisé, du code "static" (ou static inline) peut être très compact, si mis dans le .h.

    "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

    • [^] # Re: static ?

      Posté par (page perso) . Évalué à  2 .

      Je n'ai pas encore décidé ça. Des macros pourraient être très bien. En fait, depuis quelques jours, je me remet sur des micro-contrôleurs et je fais la liste de ce que j'aurais besoin comme "outils". Après je vais pondre le code, sans optimisation, et ensuite j'optimise.

      "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

      • [^] # Re: static ?

        Posté par . Évalué à  2 .

        les fonctions static font la même chose que les macros mais en plus propre (si le compilateur n'est pas moisi).

        "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

        • [^] # Re: static ?

          Posté par (page perso) . Évalué à  2 .

          Apparemment il y a un léger overhead pour les fonctions inline, ce n'es pas strictement identique. Mais ça te donne de la vérification statique de type, et je trouve ça largement acceptable comme contrepartie.

          • [^] # Re: static ?

            Posté par . Évalué à  2 .

            L'overhead des fonctions inline est en général dû à l'absence du mot clef "static". Sans ce mot, le symbol doit être visible de l'extérieur du .o et ainsi en plus des copies de la fonction en ligne, une fonction "normal" existe.

            Gcc demande juste "static", "static inline" n'est plus nécessaire.

            "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

  • # API perfectible

    Posté par . Évalué à  2 .

    A mon avis le push pourrait indiquer s'il y a eu overflow ou pas en retournant une valeur.

    Tu utilise quel version du C?
    Si c'est le C99, un bool est plus lisible que des valeurs "magiques" codés dans un char pour le code retour de sf_pop, après le bool est probablement codé sur un entier que sur un char, mais bon..

    • [^] # Re: API perfectible

      Posté par (page perso) . Évalué à  1 .

      A mon avis le push pourrait indiquer s'il y a eu overflow ou pas en retournant une valeur.

      Oui, ça pourrait être utile.

      Si c'est le C99, un bool est plus lisible que des valeurs "magiques" codés dans un char pour le code retour de sf_pop, après le bool est probablement codé sur un entier que sur un char, mais bon..

      C99 ou C89, quelle importance. La seul chose importante, dans ce cas, c'est d'avoir une valeur différente de 0 pour faire un while(...). Dans tous les cas, je préfère me dire que je code en C89 et faire ainsi.

      "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

      • [^] # Re: API perfectible

        Posté par . Évalué à  2 .

        Hum, la lisibilité c'est important, mais bon pas tant que ça sur du code aussi court..

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.