Comment créer une liste de chaînes en VHDL

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

Pour définir un tableau de chaînes, vous devez allouer de l'espace au moment de la compilation pour le plus grand nombre de chaînes que vous souhaitez stocker. Et pire encore, vous devez décider de la longueur maximale des chaînes et remplir chaque occurrence avec 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 du point de vue matériel, il devient fastidieux d'utiliser des tableaux de chaînes dans les bancs de test VHDL. Par conséquent, j'ai décidé de créer un package de liste de chaînes dynamique que je vais expliquer dans cet article.

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

Classe de liste de Python

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

Pour vous montrer ce que je veux dire, je vais me lancer et ouvrir un shell python interactif pour exécuter quelques expériences.

Tout d'abord, 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")

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

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

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

OK, remplissons la liste. Et cette fois, nous allons utiliser le insert() méthode pour ajouter les éléments de la liste 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")

Le insert() La fonction vous 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'auparavant. Vérifions cela 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 crochet [] ne supprime pas l'élément ; cela fait qu'une liste se comporte comme un tableau. Vous obtenez le contenu de l'emplacement indexé par le nombre entre parenthèses, comme vous pouvez le voir dans la liste ci-dessus.

Vidons la liste en popping, mais cette fois à partir de la fin de la liste. Une particularité des listes Python est que vous pouvez utiliser un index négatif pour compter à partir du dernier élément au lieu du début de la liste. Cela fonctionne avec l'opérateur parenthèse et avec le insert() ou pop() méthodes.

En faisant apparaître l'index -1, vous obtenez toujours le dernier élément de la liste. Lorsque nous mettons cela dans une boucle For, cela videra la liste dans l'ordre inverse :

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

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

In [13]: l.append("Amsterdam")
In [14]: l.append("Bangkok")
In [15]: l.append("Damascus")
In [16]: l.insert(-1, "Copenhagen") # insert at the second last position

Lorsque nous parcourons la liste, nous pouvons voir que "Copenhague" est maintenant l'avant-dernier élément :

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

Maintenant, voici le point crucial (mais c'est logique).

Lors de l'insertion à -1, le nouvel élément devient l'avant-dernier, mais lors de la sortie de -1, nous obtenons 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 saute, on demande le dernier élément. Mais lorsque nous insérons, nous demandons d'insérer le nouvel élément à la position du dernier élément actuellement dans la liste. Ainsi, le nouvel élément déplace l'élément final d'un emplacement.

Nous pouvons le confirmer en faisant éclater l'élément -1, qui renvoie « Damas » et non « Copenhague » :

In [18]: l.pop(-1) # pop from the last 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 également possible de compter la longueur de la liste comme ceci :

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

Et nous pouvons vider la liste en appelant clear() :

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

Comme vous pouvez le constater, les listes Python sont polyvalentes et de nombreux programmeurs les comprennent. C'est pourquoi je vais baser l'implémentation de ma liste VHDL sur cette formule de réussite.

La chaîne liste les prototypes de sous-programmes 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 en tant que type protégé. Et nous placerons le type protégé dans un package portant le même nom :string_list .

Le code ci-dessous montre la partie "public" du type protégé répertoriant 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;

Alors que le append() , insérer() , et clear() procédures sont identiques à leurs homologues Python, nous ne pouvons pas porter le pop() fonctionner directement en VHDL. Le problème est que nous ne pouvons pas facilement passer des objets dynamiques hors des types protégés en VHDL.

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

La longueur() la fonction impure se comportera comme le len() intégré de Python fonction. Il renverra le nombre de chaînes dans la liste.

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

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 pour l'utilisateur, le corps contient les implémentations du sous-programme et toutes les variables privées. Il est maintenant 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 à liens simples comme structure de données interne.

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

Étant donné que tout le code qui suit se trouve dans le corps du type protégé, ces constructions ne sont pas directement accessibles en dehors de ce package. Toutes les communications doivent passer par les sous-programmes répertoriés dans la région déclarative dont nous avons parlé dans la section précédente.

Types et variables de stockage de 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 comme ça car sur la ligne suivante, nous référençons item lors de la création de item_ptr .

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

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

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

Procédure d'ajout

Le append() La procédure ci-dessous est une notation abrégée 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 indiqué dans l'exemple Python, il est facile d'insérer à l'avant-dernière position en utilisant l'index -1 :insert(-1, str) . Mais l'insertion à la dernière position nécessite la longueur de la liste comme argument d'index. C'est probablement pourquoi la liste de Python a un append() dédié méthode, et nous en aurons une aussi.

Insérer la procédure

La procédure d'insertion, illustrée ci-dessous, fonctionne en quatre étapes.

Tout d'abord, nous créons un objet d'élément dynamique en utilisant le VHDL nouveau mot-clé. Nous créons d'abord un objet d'élément de liste, puis un objet de chaîne dynamique à stocker dedans.

procedure insert(index : integer; str : string) is
  variable new_item : item_ptr;
  variable node : item_ptr;
  variable index_v : integer;
begin

  -- Create the new object
  new_item := new item;
  new_item.str := new string'(str);

  -- Restrict the index to the list range
  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

    -- The new object becomes root when inserting at position 0
    new_item.next_item := root;
    root := new_item;

  else

    -- Find the node to insert after
    node := root;
    for i in 2 to index_v loop
      node := node.next_item;
    end loop;

    -- Insert the new item
    new_item.next_item := node.next_item;
    node.next_item := new_item;

  end if;

  length_i := length_i + 1;

end procedure;

La deuxième étape consiste à traduire l'argument d'index en un index conforme à la plage de la liste. list.insert() de Python l'implémentation autorise les index hors limites, et notre liste VHDL le permettra également. Si l'utilisateur fait référence à un index trop élevé ou trop bas, il sera par défaut l'index le plus élevé, ou l'élément 0. De plus, nous utilisons l'opérateur modulo pour traduire tous les index négatifs dans les limites en une position de tableau positive.

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

La quatrième et dernière étape consiste à incrémenter le length_i variable pour s'assurer 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 supprimer() . La première fonction obtiendra l'élément et la seconde procédure le supprimera de la liste.

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

Contrairement à insert() , le pop() de Python la fonction n'autorise pas les index hors limites, et notre get_index() non plus fonction. 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 indiqué 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;

Le get_node() , illustrée ci-dessous, va encore plus loin et trouve l'objet réel à l'index spécifié. Il utilise get_index() pour rechercher le nœud correct et renvoie un pointeur vers l'item objet.

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;

Obtenir la fonction

À cause du privé get_node() fonction, le public get() fonction devient assez simple. C'est un one-liner qui récupère le bon nœud, décompresse le contenu de la chaîne et le renvoie à l'appelant.

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

Procédure de suppression

Le delete() la procédure utilise également get_index() et get_node() pour simplifier l'algorithme. Tout d'abord, nous utilisons get_index() pour trouver l'index de l'objet à supprimer, comme indiqué dans le index_c déclaration constante 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 dissocions 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 relier la liste pour détacher l'élément à portée de main.

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

Procédure claire

Pour supprimer tous les éléments, le clear() la procédure parcourt la liste à l'aide d'une boucle While, en 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 de longueur

Pour se conformer aux bonnes pratiques de programmation, nous fournissons une fonction getter plutôt que de permettre à l'utilisateur d'accéder directement au length_i variables.

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

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

Utiliser la liste de chaînes dans un testbench

Maintenant que l'implémentation de la liste est terminée, il est temps pour nous de l'exécuter dans un testbench. Tout d'abord, nous devons importer le type protégé à partir d'un package, 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 les constructions de type classe de VHDL, et nous pouvons en créer un objet 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 "liste" pour reproduire l'exemple Python que j'ai présenté au début de cet article.

Désormais, nous pouvons utiliser une approche logicielle pour accéder aux données de la liste. Comme indiqué dans le processus de banc d'essai ci-dessous, nous pouvons référencer un sous-programme public en utilisant la notation par points 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 testbench 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 en quelques minutes.

Exécuter le banc d'essai

Si vous avez téléchargé l'exemple de projet à l'aide du formulaire ci-dessus, vous devriez pouvoir répliquer la sortie suivante. Reportez-vous à "Comment exécuter.txt" dans le fichier Zip pour des 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 pop() Méthode Python, nous utilisons get() de la liste VHDL fonction suivie d'un appel à delete() . Cela fait la même chose.

Comme nous pouvons le voir sur l'impression de la console ModelSim illustrée ci-dessous, la liste VHDL se comporte de la même manière que 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 niveau supérieur de VHDL sont sous-estimées. Bien qu'il ne soit pas utile pour la conception RTL car il n'est pas synthétisable, il peut être bénéfique à des fins de vérification.

Même s'il peut être compliqué à mettre en œuvre, il sera plus simple pour l'utilisateur final, la personne qui écrit le testbench qui utilise le type protégé. Le type protégé cache toute la complexité à l'utilisateur.

Il suffit de trois lignes pour utiliser un type protégé :importez le package, déclarez la variable partagée et appelez un sous-programme dans le processus testbench. C'est plus simple que d'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 des commentaires sous l'article !