Qu'est-ce qu'une table à sauter ?

https://stackoverflow.com/questions/48017

09-06-2019
|

Question

Quelqu'un peut-il expliquer le mécanisme d'une table de saut et pourquoi elle serait nécessaire dans les systèmes embarqués ?

La solution

Une table de sauts peut être soit un tableau de pointeurs vers des fonctions, soit un tableau d’instructions de saut de code machine.Si vous disposez d'un ensemble de fonctions relativement statiques (telles que des appels système ou des fonctions virtuelles pour une classe), vous pouvez créer cette table une fois et appeler les fonctions à l'aide d'un simple index dans le tableau.Cela signifierait récupérer le pointeur et appeler une fonction ou passer au code machine en fonction du type de table utilisé.

Les avantages de faire cela dans la programmation embarquée sont :

Les index sont plus efficaces en mémoire que le code machine ou les pointeurs, il existe donc un potentiel d'économie de mémoire dans des environnements contraints.
Pour toute fonction particulière, l'index restera stable et la modification de la fonction nécessite simplement de remplacer le pointeur de fonction.

Cela vous coûte un tout petit peu de performances pour accéder à la table, mais ce n'est pas pire que n'importe quel autre appel de fonction virtuelle.

Autres conseils

Une table de sauts, également connue sous le nom de table de branchement, est une série d'instructions, toutes bifurquées de manière inconditionnelle vers un autre point du code.

Vous pouvez les considérer comme une instruction switch (ou select) où tous les cas sont remplis :

MyJump(int c)
{
   switch(state)
   {
      case 0:
         goto func0label;
      case 1:
         goto func1label;
      case 2:
         goto func2label;
   }
}

Notez qu'il n'y a pas de retour - le code vers lequel il saute exécutera le retour et il reviendra là où myjump a été appelé.

Ceci est utile pour les machines à états dans lesquelles vous exécutez certains codes basés sur la variable d'état.Il existe de très nombreuses autres utilisations, mais celle-ci est l’une des principales utilisations.

Il est utilisé lorsque vous ne voulez pas perdre de temps à manipuler la pile et que vous souhaitez économiser de l'espace de code.Il est particulièrement utile dans les gestionnaires d'interruptions où la vitesse est extrêmement importante et où le périphérique qui a provoqué l'interruption n'est connu que par une seule variable.Ceci est similaire à la table vectorielle des processeurs dotés de contrôleurs d'interruption.

Une utilisation consisterait à prendre un microcontrôleur à 0,60 $ et à générer un signal composite (TV) pour les applications vidéo.le micro n'est pas puissant - en fait, il est à peine assez rapide pour écrire chaque ligne de numérisation.Une table de saut serait utilisée pour dessiner des caractères, car cela prendrait trop de temps pour charger un bitmap depuis la mémoire et utiliserait une boucle for() pour extraire le bitmap.Au lieu de cela, il y a un saut séparé vers la lettre et la ligne de numérisation, puis environ 8 instructions qui écrivent les données directement sur le port.

-Adam

Une table de saut est décrite ici, mais brièvement, il s'agit d'un tableau d'adresses vers lesquelles le processeur doit accéder en fonction de certaines conditions.À titre d'exemple, une instruction switch C est souvent implémentée sous la forme d'une table de sauts dans laquelle chaque entrée de saut ira vers une étiquette "case" particulière.

Dans les systèmes embarqués, où l'utilisation de la mémoire est primordiale, de nombreuses constructions sont mieux servies en utilisant une table de saut au lieu de méthodes plus gourmandes en mémoire (comme un if-else-if massif).

Wikipédia ça résume assez bien :

Dans la programmation informatique, une table de branche (parfois connue sous le nom de table de saut) est un terme utilisé pour décrire une méthode efficace de transfert de contrôle du programme (branchement) vers une autre partie d'un programme (ou un programme différent qui peut avoir été chargé dynamiquement) en utilisant une table d'instructions de branche.La construction de la table de branche est couramment utilisée lors de la programmation dans le langage d'assemblage, mais peut également être générée par un compilateur.

...L'utilisation de tables de branche et d'autres codages de données brutes était courante au début du calcul lorsque la mémoire était coûteuse, les CPU étaient plus lents et la représentation des données compactes et le choix efficace des alternatives étaient importants.De nos jours, ils sont couramment utilisés dans la programmation intégrée et le développement du système d'exploitation.

En d’autres termes, il s’agit d’une construction utile à utiliser lorsque votre système est extrêmement limité en mémoire et/ou en CPU, comme c’est souvent le cas dans une plate-forme embarquée.

De Wikipédia:

Dans la programmation informatique, une table de branche (parfois connue sous le nom de table de saut) est un terme utilisé pour décrire une méthode efficace de transfert de contrôle du programme (branchement) vers une autre partie d'un programme (ou un programme différent qui peut avoir été chargé dynamiquement) en utilisant une table d'instructions de branche.La construction de la table de branche est couramment utilisée lors de la programmation dans le langage d'assemblage, mais peut également être générée par un compilateur.

Une table de branche se compose d'une liste série d'instructions de branche inconditionnelles qui est ramifiée en utilisant un décalage créé en multipliant un index séquentiel par la longueur d'instruction (le nombre d'octets dans la mémoire occupé par chaque instruction de branche).Il utilise le fait que les instructions de code machine pour la branche ont une longueur fixe et peuvent être exécutées extrêmement efficacement par la plupartCompte tenu de ces données, une table de branche peut être extrêmement efficace;Il se compose généralement des étapes suivantes:Valider éventuellement les données d'entrée pour s'assurer qu'elle est acceptable;Transformer les données en un décalage en table de branche, cela implique généralement de le multiplier ou de le déplacer pour prendre en compte la longueur de l'instruction;et se ramifiant à une adresse composée de la base de la table et du décalage généré:Cela implique souvent un ajout du décalage sur le registre du compteur du programme.

Les tables de saut, plus souvent appelées tables de branchement, sont généralement utilisées uniquement par la machine.

Le compilateur crée une liste de toutes les étiquettes dans un programme assembleur et lie toutes les étiquettes à un emplacement mémoire.Une table de sauts est en quelque sorte une carte de référence indiquant où une fonction ou une variable ou quelle que soit l'étiquette, est stockée en mémoire.

Ainsi, lorsqu'une fonction s'exécute, une fois terminée, elle revient à son emplacement mémoire précédent ou passe à la fonction suivante, etc.

Et si vous parlez de ce que je pense que vous êtes, vous n'en avez pas seulement besoin dans les systèmes embarqués mais dans tout type d'environnement compilé/interprété.

Brian Gianforcaro

Les tables de saut sont couramment (mais pas exclusivement) utilisées dans machines à états finis pour les rendre axés sur les données.

Au lieu d'un commutateur/boîtier imbriqué

  switch (state)
     case A:
       switch (event):
         case e1: ....
         case e2: ....
     case B:
       switch (event):
         case e3: ....
         case e1: ....

vous pouvez créer un tableau 2D ou des pointeurs de fonction et simplement appeler handleEvent[state][event]

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow