Créer des listes de chaînes en VHDL : Bonnes pratiques et exemple

Les chaînes de caractères en VHDL sont généralement limitées à des tableaux de caractères de longueur fixe. Cela est logique car le VHDL décrit du matériel, et les chaînes de longueur générique nécessitent de la mémoire dynamique.

Pour définir un tableau de chaînes, il faut allouer de l'espace à la compilation pour le nombre maximal de chaînes à stocker. Pire encore, il faut décider de la longueur maximale des chaînes et remplir chaque occurrence jusqu'à ce nombre de caractères. Le code ci-dessous montre un exemple d'utilisation d'une telle construction.

 type arr_type is array (0 to 3) of string(1 to 10); signal arr : arr_type; begin arr(0) <= "Amsterdam "; arr(1) <= "Bangkok "; arr(2) <= "Copenhagen"; arr(3) <= "Damascus "; 

Bien que cela ait du sens d'un point de vue matériel, cela devient fastidieux d'utiliser des tableaux de chaînes dans les bancs de test VHDL. C'est pourquoi j'ai décidé de créer un paquet de liste de chaînes dynamique que j'expliquerai dans cet article.

Vous pouvez télécharger le code complet en utilisant le formulaire ci-dessous.

La classe list de Python

Modélisons notre liste VHDL dynamique sur une implémentation de liste bien connue. Notre liste de chaînes VHDL imitera le comportement de la classe list intégrée de Python. Nous adopterons les méthodes append(), insert() et pop() de la liste Python.

Pour vous montrer ce que je veux dire, je vais directement ouvrir un shell Python interactif pour faire quelques expériences.

Commençons par déclarer une liste et y ajouter quatre chaînes, comme indiqué ci-dessous.

 IPython 7.19.0 -- An enhanced Interactive Python. Type '?' for help. In [1]: l = [] In [2]: l.append("Amsterdam") In [3]: l.append("Bangkok") In [4]: l.append("Copenhagen") In [5]: l.append("Damascus") 

La méthode append() est simple ; elle ajoute un objet à la fin de la liste.

Nous pouvons vérifier cela avec la méthode pop(), qui supprime un élément et le retourne à l'appelant. L'argument spécifie la position de l'élément à récupérer. En dépilant 0 jusqu'à ce que la liste soit vide, nous obtenons le contenu ordonné de l'index le plus bas au plus haut :

 In [6]: for _ in range(len(l)): print(l.pop(0)) Amsterdam Bangkok Copenhagen Damascus 

OK, remplissons à nouveau la liste. Et cette fois, nous utiliserons la méthode insert() pour ajouter les éléments dans le désordre :

 In [7]: l.insert(0, "Bangkok") In [8]: l.insert(1, "Copenhagen") In [9]: l.insert(0, "Amsterdam") In [10]: l.insert(3, "Damascus") 

La fonction insert() permet de spécifier à quel index insérer le nouvel élément. Dans l'exemple ci-dessus, nous avons créé la même liste qu'avant. Vérifions en parcourant la liste comme un tableau :

 In [11]: for i in range(len(l)): print(l[i]) Amsterdam Bangkok Copenhagen Damascus 

L'opérateur de liste Python [] ne supprime pas l'élément ; il fait comporter une liste comme un tableau. Vous obtenez le contenu de l'emplacement indexé par le nombre entre crochets, comme on peut le voir dans la liste ci-dessus.

Videz la liste en dépilant, mais cette fois depuis la fin de la liste. Une particularité des listes Python est qu'on peut utiliser un index négatif pour compter à partir du dernier élément au lieu du début. Cela fonctionne avec l'opérateur crochet et avec les méthodes insert() ou pop().

En dépilant l'index -1, vous obtenez toujours le dernier élément de la liste. Quand on met cela dans une boucle For, cela vide la liste dans l'ordre inverse :

 In [12]: for _ in range(len(l)): print(l.pop(-1)) Damascus Copenhagen Bangkok Amsterdam 

Vous pouvez utiliser des indexes négatifs pour insérer également. Dans la dernière ligne de l'exemple ci-dessous, nous insérons "Copenhagen" à l'index -1 :

 In [13]: l.append("Amsterdam") In [14]: l.append("Bangkok") In [15]: l.append("Damascus") In [16]: l.insert(-1, "Copenhagen") # insère à la position avant-dernière 

Quand on parcourt la liste, on voit que "Copenhagen" est maintenant l'avant-dernier élément :

 In [17]: for i in range(len(l)): print(l[i]) Amsterdam Bangkok Copenhagen Damascus 

Voici maintenant le point crucial (mais cela a du sens).

Lorsqu'on insère à -1, le nouvel élément devient l'avant-dernier, mais lorsqu'on dépile depuis -1, on obtient le dernier élément.

Cela a du sens car -1 fait référence à la position du dernier élément actuellement dans la liste. Et quand on dépile, on demande le dernier élément. Mais quand on insère, on demande d'insérer le nouvel élément à la position du dernier élément actuellement dans la liste. Ainsi, le nouvel élément décale l'élément final d'un cran.

On peut le confirmer en dépilant l'élément -1, qui retourne "Damascus", et non "Copenhagen" :

 In [18]: l.pop(-1) # dépile depuis la dernière position Out[18]: 'Damascus' 

La liste contient maintenant trois éléments :

 In [19]: for i in range(len(l)): print(l[i]) Amsterdam Bangkok Copenhagen 

Il est aussi possible de compter la longueur de la liste ainsi :

 In [20]: len(l) Out[20]: 3 

Et on peut vider la liste en appelant clear() :

 In [21]: l.clear() In [22]: len(l) Out[22]: 0 

Comme vous pouvez le voir, les listes Python sont polyvalentes et de nombreux programmeurs les comprennent. C'est pourquoi je baserai mon implémentation de liste VHDL sur cette formule réussie.

Les prototypes de sous-programmes de la liste de chaînes VHDL

Pour nous permettre de travailler avec la liste de chaînes comme un objet avec des méthodes membres, nous devons la déclarer comme un type protégé. Et nous placerons le type protégé dans un paquet du même nom : string_list.

Le code ci-dessous montre la partie « publique » du type protégé listant les prototypes de sous-programmes.

 package string_list is type string_list is protected procedure append(str : string); procedure insert(index : integer; str : string); impure function get(index : integer) return string; procedure delete(index : integer); procedure clear; impure function length return integer; end protected; end package; 

Bien que les procédures append(), insert() et clear() soient identiques à leurs homologues Python, nous ne pouvons pas porter la fonction pop() directement en VHDL. Le problème est qu'on ne peut pas facilement passer des objets dynamiques hors des types protégés en VHDL.

Pour surmonter cette limitation, j'ai divisé la fonctionnalité pop() en deux sous-programmes : get() et delete(). Cela nous permettra d'indexer l'élément d'abord, comme un tableau, puis de le supprimer quand nous n'en avons plus besoin. Par exemple, après avoir affiché la chaîne sur la console du simulateur.

La fonction impure length() se comportera comme la fonction intégrée len() de Python. Elle retournera le nombre de chaînes dans la liste.

L'implémentation de la liste de chaînes VHDL

Les types protégés se composent de deux sections : la partie déclarative et le corps. Alors que la partie déclarative est visible par l'utilisateur, le corps contient les implémentations des sous-programmes et les variables privées. Il est temps de révéler le fonctionnement interne de la liste de chaînes.

Laissez votre adresse e-mail dans le formulaire ci-dessous pour recevoir le code complet et le projet ModelSim dans votre boîte de réception !

Nous utiliserons une liste simplement chaînée comme structure de données interne.

Lisez aussi : Comment créer une liste chaînée en VHDL

Comme tout le code qui suit se trouve dans le corps du type protégé, ces constructions ne sont pas directement accessibles depuis l'extérieur de ce paquet. Toute communication doit passer par les sous-programmes listés dans la région déclarative que nous avons discutée dans la section précédente.

Types et variables de stockage des données

Comme vous pouvez le voir dans le code ci-dessous, nous déclarons d'abord un type d'accès, un pointeur VHDL vers une chaîne en mémoire dynamique. Quand on parle de mémoire dynamique, ce n'est pas de la DRAM sur le FPGA car ce code n'est pas synthétisable. La liste de chaînes est purement un composant de simulation, et elle utilisera la mémoire dynamique de l'ordinateur exécutant la simulation.

 type str_ptr is access string; type item; type item_ptr is access item; type item is record str : str_ptr; next_item : item_ptr; end record; 

Après str_ptr, nous déclarons item comme un type incomplet. Nous devons le faire ainsi car à la ligne suivante, nous référençons item lors de la création de item_ptr.

Et enfin, nous spécifions la déclaration complète du type item, un enregistrement contenant un pointeur de chaîne et un pointeur vers l'élément suivant. Il y a une dépendance circulaire entre les types item->item_ptr->item, et en déclarant d'abord le type item incomplet, on évite une erreur de compilation.

Le type protégé contient deux variables, montrées ci-dessous : root et length_i. L'élément pointé par root sera le premier élément de la liste, index de tableau zéro. Et la variable length_i reflétera toujours le nombre de chaînes dans la liste.

 variable root : item_ptr; variable length_i : integer := 0; 

Procédure Append

La procédure append() montrée ci-dessous est une notation raccourcie pour insérer une chaîne à la dernière position de la liste.

 procedure append(str : string) is begin insert(length_i, str); end procedure; 

Comme discuté dans l'exemple Python, il est facile d'insérer à la position avant-dernière en utilisant l'index -1 : insert(-1, str). Mais insérer à la dernière position nécessite la longueur de la liste comme argument d'index. C'est probablement pourquoi la liste de Python a une méthode dédiée append(), et nous en aurons une aussi.

Procédure Insert

La procédure insert, montrée ci-dessous, fonctionne en quatre étapes.

Premièrement, nous créons un objet item dynamique en utilisant le mot-clé VHDL new. Nous créons d'abord un objet item de liste, puis un objet chaîne dynamique pour le stocker.

 procedure insert(index : integer; str : string) is variable new_item : item_ptr; variable node : item_ptr; variable index_v : integer; begin -- Créer le nouvel objet new_item := new item; new_item.str := new string'(str); -- Restreindre l'index à l'étendue de la liste if index >= length_i then index_v := length_i; elsif index <= -length_i then index_v := 0; else index_v := index mod length_i; end if; if index_v = 0 then -- Le nouvel objet devient root lors de l'insertion à la position 0 new_item.next_item := root; root := new_item; else -- Trouver le nœud après lequel insérer node := root; for i in 2 to index_v loop node := node.next_item; end loop; -- Insérer le nouvel item new_item.next_item := node.next_item; node.next_item := new_item; end if; length_i := length_i + 1; end procedure; 

L'étape numéro deux consiste à traduire l'argument index en un index conforme à l'étendue de la liste. L'implémentation list.insert() de Python autorise les indexes hors limites, et notre liste VHDL le permettra aussi. Si l'utilisateur référence un index trop haut ou trop bas, il sera par défaut à l'index le plus haut, ou à l'élément 0. De plus, nous utilisons l'opérateur modulo pour traduire tout index négatif valide en une position de tableau positive.

À l'étape numéro trois, nous parcourons la liste pour trouver le nœud après lequel insérer. Comme toujours avec les listes chaînées, nous devons gérer explicitement le cas particulier de l'insertion à la racine.

La quatrième et dernière étape consiste à incrémenter la variable length_i pour garantir que la comptabilité est à jour.

Fonctions internes get_index et get_node

En raison des limitations de passage d'objets de VHDL, nous avons décidé de diviser pop() en deux sous-programmes : get() et delete(). La première fonction récupérera l'item, et la seconde procédure le supprimera de la liste.

Mais l'algorithme pour rechercher l'index ou l'objet est identique pour get() et delete(), nous pouvons donc l'implémenter séparément dans deux fonctions privées : get_index() et get_node().

Contrairement à insert(), la fonction pop() de Python n'autorise pas les indexes hors limites, et notre fonction get_index() non plus. Pour se prémunir contre les erreurs de l'utilisateur, nous déclencherons un échec d'assertion si l'index demandé est hors limites, comme montré ci-dessous.

 impure function get_index(index : integer) return integer is begin assert index >= -length_i and index < length_i report "get index out of list range" severity failure; return index mod length_i; end function; 

La fonction get_node(), montrée ci-dessous, va plus loin et trouve l'objet réel à l'index spécifié. Elle utilise get_index() pour rechercher le nœud correct et retourne un pointeur vers l'objet item.

 impure function get_node(index : integer) return item_ptr is variable node : item_ptr; begin node := root; for i in 1 to get_index(index) loop node := node.next_item; end loop; return node; end function; 

Fonction Get

Grâce à la fonction privée get_node(), la fonction publique get() devient plutôt simple. C'est une one-liner qui récupère le nœud correct, dépaquette le contenu de la chaîne, et le retourne à l'appelant.

 impure function get(index : integer) return string is begin return get_node(index).str.all; end function; 

Procédure Delete

La procédure delete() utilise également get_index() et get_node() pour simplifier l'algorithme. Premièrement, nous utilisons get_index() pour trouver l'index de l'objet à supprimer, comme montré dans la déclaration de la constante index_c ci-dessous.

 procedure delete(index : integer) is constant index_c : integer := get_index(index); variable node : item_ptr; variable parent_node : item_ptr; begin if index_c = 0 then node := root; root := root.next_item; else parent_node := get_node(index_c - 1); node := parent_node.next_item; parent_node.next_item := node.next_item; end if; deallocate(node.str); deallocate(node); length_i := length_i - 1; end procedure; 

Ensuite, nous détachons le nœud de la liste. S'il s'agit de l'objet racine, nous définissons l'élément suivant comme racine. Sinon, nous utilisons get_node() pour trouver le parent et relions la liste pour détacher l'élément en question.

Et enfin, nous libérons la mémoire en appelant le mot-clé VHDL deallocate et mettons à jour la variable de comptabilité length_i.

Procédure Clear

Pour supprimer tous les éléments, la procédure clear() parcourt la liste à l'aide d'une boucle While, appelant delete() sur chaque élément jusqu'à ce qu'il n'en reste plus.

 procedure clear is begin while length_i > 0 loop delete(0); end loop; end procedure; 

Fonction Length

Pour respecter les bonnes pratiques de programmation, nous fournissons une fonction d'accès plutôt que de permettre à l'utilisateur d'accéder directement à la variable length_i.

 impure function length return integer is begin return length_i; end function; 

La différence sera imperceptible pour l'utilisateur car vous n'avez pas besoin de parenthèses pour appeler une fonction sans paramètres (my_list.length). Mais l'utilisateur ne peut pas modifier la variable de comptabilité interne, ce qui est une protection contre les abus.

Utiliser la liste de chaînes dans un banc de test

Maintenant que l'implémentation de la liste est terminée, il est temps de l'exécuter dans un banc de test. D'abord, nous devons importer le type protégé depuis un paquet, comme indiqué sur la première ligne du code ci-dessous.

 use work.string_list.string_list; entity string_list_tb is end string_list_tb; architecture sim of string_list_tb is shared variable l : string_list; ... 

Le type protégé est la construction de type classe de VHDL, et nous pouvons créer un objet de ce type en déclarant une variable partagée de type string_list, comme indiqué sur la dernière ligne ci-dessus. Nous l'appellerons 'l' pour « list » afin de reproduire l'exemple Python présenté au début de cet article.

À partir de maintenant, nous pouvons utiliser une approche logicielle pour accéder aux données de la liste. Comme montré dans le processus de banc de test ci-dessous, nous pouvons référencer un sous-programme public en utilisant la notation pointée sur la variable partagée (l.append("Amsterdam")).

 begin SEQUENCER_PROC : process begin print("* Append four strings"); print(" l.append(Amsterdam)"); l.append("Amsterdam"); print(" l.append(Bangkok)"); l.append("Bangkok"); print(" l.append(Copenhagen)"); l.append("Copenhagen"); print(" l.append(Damascus)"); l.append("Damascus"); ... 

J'ai omis le banc de test complet et le script d'exécution pour réduire la longueur de cet article, mais vous pouvez le demander en laissant votre adresse e-mail dans le formulaire ci-dessous. Vous recevrez un fichier Zip avec le code VHDL complet et un projet ModelSim dans votre boîte de réception dans les minutes qui suivent.

Exécution du banc de test

Si vous avez téléchargé le projet exemple en utilisant le formulaire ci-dessus, vous devriez pouvoir reproduire la sortie suivante. Reportez-vous à « How to run.txt » dans le fichier Zip pour les instructions précises.

C'est un banc de test à vérification manuelle, et j'ai fait en sorte que les cas de test ressemblent le plus possible à mon exemple Python. Au lieu de la méthode pop() de Python, nous utilisons la fonction get() de la liste VHDL suivie d'un appel à delete(). Cela fait la même chose.

Comme on peut le voir dans l'affichage sur la console ModelSim ci-dessous, la liste VHDL se comporte de manière similaire à son homologue Python.

 # * Append four strings # l.append(Amsterdam) # l.append(Bangkok) # l.append(Copenhagen) # l.append(Damascus) # * Pop all strings from the beginning of the list # l.get(0): Amsterdam # l.get(1): Bangkok # l.get(2): Copenhagen # l.get(3): Damascus # * Insert four strings in shuffled order # l.insert(0, Bangkok) # l.insert(1, Copenhagen) # l.insert(0, Amsterdam) # l.insert(3, Damascus) # * Traverse the list like an array # l.get(0): Amsterdam # l.get(1): Bangkok # l.get(2): Copenhagen # l.get(3): Damascus # * Pop all strings from the end of the list # l.get(0): Damascus # l.get(1): Copenhagen # l.get(2): Bangkok # l.get(3): Amsterdam # * Append and insert at the second last position # l.append(Amsterdam) # l.append(Bangkok) # l.append(Damascus) # l.insert(-1, Copenhagen) # * Pop from the last position # l.get(-1): Damascus # * Traverse the list like an array # l.get(0): Amsterdam # l.get(1): Bangkok # l.get(2): Copenhagen # * Check the list length # l.length: 3 # * Clear the list # * Check the list length # l.length: 0 # * Done 

Réflexions finales

Je pense que les fonctionnalités de programmation de haut niveau de VHDL sont sous-estimées. Bien qu'elles ne soient pas utiles pour la conception RTL car non synthétisables, elles peuvent être bénéfiques pour la vérification.

Même si l'implémentation peut être complexe, elle sera plus simple pour l'utilisateur final, la personne qui écrit le banc de test utilisant le type protégé. Le type protégé cache toute la complexité à l'utilisateur.

Il ne faut que trois lignes pour utiliser un type protégé : importer le paquet, déclarer la variable partagée, et appeler un sous-programme dans le processus du banc de test. C'est plus simple qu'instancier un composant VHDL.

Voir aussi : Comment créer une liste chaînée en VHDL

Dites-moi ce que vous en pensez dans la section commentaires sous l'article !