String-Listen in VHDL erstellen: Best Practices & Beispiel

Textstrings in VHDL sind grundsätzlich auf Arrays fester Länge beschränkt. Das ist sinnvoll, da VHDL Hardware beschreibt und Strings variabler Länge dynamischen Speicher erfordern würden.

Um ein Array von Strings zu definieren, muss man zur Compile-Zeit Platz für die maximale Anzahl der zu speichernden Strings reservieren. Und noch schlimmer: Man muss sich auf eine maximale Stringlänge festlegen und jeden String auf diese Zeichenanzahl auffüllen. Der folgende Code zeigt ein Beispiel für ein solches Konstrukt.

 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) <= "Kopenhagen"; arr(3) <= "Damaskus "; 

Zwar macht dies aus Hardwaresicht Sinn, wird aber in VHDL-Testbenches schnell umständlich. Daher habe ich ein dynamisches String-Listen-Paket erstellt, das ich in diesem Artikel erläutere.

Den vollständigen Code können Sie über das untenstehende Formular herunterladen.

Pythons List-Klasse

Lassen Sie uns unsere dynamische VHDL-Liste an einer bekannten Listen-Implementierung orientieren. Unsere VHDL-String-Liste wird das Verhalten von Pythons eingebauter List-Klasse nachahmen. Wir übernehmen die Methoden append(), insert() und pop() von der Python-Liste.

Um zu zeigen, was ich meine, springe ich direkt in eine interaktive Python-Shell und führe einige Experimente durch.

Beginnen wir damit, eine Liste zu deklarieren und vier Strings anzuhängen, wie unten gezeigt.

 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("Kopenhagen") In [5]: l.append("Damaskus") 

Die append()-Methode ist selbsterklärend; sie fügt ein Objekt am Ende der Liste an.

Wir können dies mit der pop()-Methode überprüfen, die ein Element entfernt und an den Aufrufer zurückgibt. Das Argument spezifiziert die Position des zu entnehmenden Elements. Durch Poppen von Index 0 bis die Liste leer ist, erhalten wir den Inhalt geordnet von niedrigstem zu höchstem Index:

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

OK, füllen wir die Liste wieder. Diesmal nutzen wir die insert()-Methode, um die Elemente in veränderter Reihenfolge hinzuzufügen:

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

Die insert()-Funktion erlaubt die Angabe des Index, an den das neue Element eingefügt wird. Im obigen Beispiel haben wir dieselbe Liste wie zuvor erstellt. Prüfen wir das, indem wir die Liste wie ein Array durchlaufen:

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

Der Python-Klammer-Operator [] löscht das Element nicht; er lässt eine Liste wie ein Array verhalten. Man erhält den Inhalt des Slots, indiziert durch die Zahl in den Klammern, wie aus der Ausgabe ersichtlich.

Leeren wir die Liste durch Poppen, diesmal vom Ende der Liste. Eine Besonderheit von Python-Listen ist, dass man negative Indizes verwenden kann, um vom letzten Element anstatt vom Anfang zu zählen. Das funktioniert mit dem Klammer-Operator und den Methoden insert() oder pop().

Durch Poppen von Index -1 erhält man immer das letzte Element der Liste. In einer For-Schleife leert dies die Liste in umgekehrter Reihenfolge:

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

Negative Indizes können auch zum Einfügen verwendet werden. In der letzten Zeile des folgenden Beispiels fügen wir „Kopenhagen“ an Index -1 ein:

 In [13]: l.append("Amsterdam") In [14]: l.append("Bangkok") In [15]: l.append("Damaskus") In [16]: l.insert(-1, "Kopenhagen") # an vorletzter Position einfügen 

Beim Durchlaufen der Liste sehen wir, dass „Kopenhagen“ nun das vorletzte Element ist:

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

Nun kommt der Knackpunkt (der aber Sinn ergibt).

Beim Einfügen an -1 wird das neue Element zum vorletzten, beim Poppen von -1 erhält man das letzte Element.

Das ergibt Sinn, weil -1 die Position des aktuell letzten Elements in der Liste bezeichnet. Beim Poppen fragt man nach dem letzten Element. Beim Einfügen bittet man, das neue Element an der Position des aktuell letzten Elements einzufügen. Damit verdrängt das neue Element das letzte um einen Slot.

Wir können dies bestätigen, indem wir Element -1 poppen, was „Damaskus“ zurückgibt, nicht „Kopenhagen“:

 In [18]: l.pop(-1) # vom letzten Position poppen Out[18]: 'Damaskus' 

Die Liste enthält nun drei Elemente:

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

Die Listenlänge lässt sich so ermitteln:

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

Und die Liste lässt sich durch Aufruf von clear() leeren:

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

Wie man sieht, sind Python-Listen vielseitig und vielen Programmierern vertraut. Deshalb basiere ich meine VHDL-Listen-Implementierung auf diesem Erfolgsrezept.

VHDL-Subprogramm-Prototypen der String-Liste

Um mit der String-Liste wie mit einem Objekt mit Mitgliedsmethoden arbeiten zu können, müssen wir sie als Protected Type deklarieren. Und wir platzieren den Protected Type in einem Paket mit demselben Namen: string_list.

Der folgende Code zeigt den „öffentlichen“ Teil des Protected Types mit den Subprogramm-Prototypen.

 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; 

Während die Prozeduren append(), insert() und clear() identisch zu ihren Python-Pendants sind, können wir die pop()-Funktion nicht direkt nach VHDL portieren. Das Problem: Dynamische Objekte lassen sich nicht einfach aus Protected Types in VHDL herausgeben.

Um diese Einschränkung zu umgehen, habe ich die pop()-Funktionalität in zwei Subprogramme aufgeteilt: get() und delete(). Das erlaubt uns, das Element erst wie bei einem Array zu indexieren und es dann zu löschen, wenn wir es nicht mehr brauchen – beispielsweise nachdem wir den String auf der Simulator-Konsole ausgegeben haben.

Die length()-Impure-Funktion verhält sich wie Pythons eingebaute len()-Funktion. Sie gibt die Anzahl der Strings in der Liste zurück.

VHDL-Implementierung der String-Liste

Protected Types bestehen aus zwei Abschnitten: dem deklarativen Teil und dem Body. Während der deklarative Teil für den Benutzer sichtbar ist, enthält der Body die Subprogramm-Implementierungen und privaten Variablen. Nun enthüllen wir die inneren Abläufe der String-Liste.

Hinterlassen Sie Ihre E-Mail-Adresse im untenstehenden Formular, um den vollständigen Code und das ModelSim-Projekt per E-Mail zu erhalten!

Wir verwenden eine einfach verkettete Liste als interne Datenstruktur.

Lesen Sie auch: Wie man eine verkettete Liste in VHDL erstellt

Da der gesamte folgende Code im Body des Protected Types steht, sind diese Konstrukte nicht direkt von außen zugänglich. Die gesamte Kommunikation muss über die im vorherigen Abschnitt besprochenen Subprogramme im deklarativen Bereich laufen.

Datenspeicher-Typen und Variablen

Wie aus dem folgenden Code ersichtlich, deklarieren wir zuerst einen Access-Typ, einen VHDL-Zeiger auf einen String im dynamischen Speicher. Bei dynamischem Speicher handelt es sich nicht um DRAM auf dem FPGA, da dieser Code nicht synthetisierbar ist. Die String-Liste ist reine Simulationskomponente und nutzt den dynamischen Speicher des Rechners, der die Simulation ausführt.

 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; 

Nach str_ptr deklarieren wir item als unvollständigen Typ. Das ist nötig, weil wir in der nächsten Zeile item referenzieren, wenn wir item_ptr erstellen.

Schließlich spezifizieren wir die vollständige Deklaration des item-Typs, ein Record mit einem String-Zeiger und einem Zeiger auf das nächste Element. Es besteht eine zirkuläre Abhängigkeit zwischen den Typen item->item_ptr->item, und durch die vorherige Deklaration des unvollständigen item-Typs vermeiden wir einen Kompilierfehler.

Der Protected Type enthält zwei Variablen, wie unten gezeigt: root und length_i. Das von root referenzierte Item wird das erste Element der Liste sein, Array-Index null. Und die Variable length_i spiegelt stets die Anzahl der Strings in der Liste wider.

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

Append-Prozedur

Die unten gezeigte append()-Prozedur ist eine Kurzschreibweise für das Einfügen eines Strings an der letzten Position der Liste.

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

Wie im Python-Beispiel besprochen, ist es einfach, an der vorletzten Position mit Index -1 einzufügen: insert(-1, str). Aber das Einfügen an der letzten Position erfordert die Listenlänge als Index-Argument. Das ist wahrscheinlich der Grund, warum Pythons Liste eine dedizierte append()-Methode hat, und wir werden auch eine haben.

Insert-Prozedur

Die Insert-Prozedur, unten gezeigt, arbeitet in vier Schritten.

Zuerst erstellen wir ein dynamisches Item-Objekt mittels des VHDL-Schlüsselworts new. Wir erstellen zuerst ein List-Item-Objekt und dann ein dynamisches String-Objekt, um es darin zu speichern.

 procedure insert(index : integer; str : string) is variable new_item : item_ptr; variable node : item_ptr; variable index_v : integer; begin -- Neues Objekt erstellen new_item := new item; new_item.str := new string'(str); -- Index auf Listenbereich beschränken 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 -- Das neue Objekt wird Root beim Einfügen an Position 0 new_item.next_item := root; root := new_item; else -- Knoten finden, nach dem eingefügt wird node := root; for i in 2 to index_v loop node := node.next_item; end loop; -- Neues Item einfügen new_item.next_item := node.next_item; node.next_item := new_item; end if; length_i := length_i + 1; end procedure; 

Schritt zwei ist die Übersetzung des Index-Arguments in einen Index, der dem Listenbereich entspricht. Pythons list.insert()-Implementierung erlaubt Out-of-Bounds-Indizes, und unsere VHDL-Liste wird dies ebenfalls erlauben. Referenziert der Nutzer einen zu hohen oder niedrigen Index, wird standardmäßig auf den höchsten Index bzw. Element 0 gesetzt. Zudem nutzen wir den Modulo-Operator, um negative In-Bounds-Indizes in eine positive Array-Position zu übersetzen.

Im Schritt drei durchlaufen wir die Liste, um den Knoten zu finden, nach dem eingefügt wird. Wie bei verketteten Listen üblich, müssen wir den Spezialfall des Einfügens an der Wurzel explizit behandeln.

Der vierte und letzte Schritt inkrementiert die Variable length_i, um die Buchführung aktuell zu halten.

Interne get_index- und get_node-Funktionen

Wegen VHDLs Objekt-Übergabe-Beschränkungen haben wir entschieden, pop() in zwei Subprogramme aufzuteilen: get() und delete(). Die erste Funktion holt das Item, die zweite Prozedur entfernt es aus der Liste.

Da der Algorithmus für das Nachschlagen des Index oder Objekts für get() und delete() identisch ist, können wir ihn in zwei privaten Funktionen separat implementieren: get_index() und get_node().

Im Gegensatz zu insert() erlaubt Pythons pop()-Funktion keine Out-of-Bounds-Indizes, und unsere get_index()-Funktion wird dies ebenfalls nicht tun. Zum Schutz vor Benutzerfehlern lösen wir einen Assertion-Fehler aus, wenn der angeforderte Index out-of-bounds ist, wie unten gezeigt.

 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; 

Die get_node()-Funktion, unten gezeigt, geht einen Schritt weiter und findet das eigentliche Objekt am angegebenen Index. Sie nutzt get_index(), um den korrekten Knoten zu finden, und gibt einen Zeiger auf das item-Objekt zurück.

 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; 

Get-Funktion

Dank der privaten get_node()-Funktion wird die öffentliche get()-Funktion recht simpel. Es ist ein Einzeiler, der den korrekten Knoten holt, den String-Inhalt entpackt und an den Aufrufer zurückgibt.

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

Delete-Prozedur

Die delete()-Prozedur nutzt ebenfalls get_index() und get_node(), um den Algorithmus zu vereinfachen. Zuerst verwenden wir get_index(), um den Index des zu entfernenden Objekts zu finden, wie in der Konstantendeklaration index_c unten gezeigt.

 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; 

Dann entkoppeln wir den Knoten von der Liste. Handelt es sich um das Root-Objekt, setzen wir das nächste Item als Root. Andernfalls nutzen wir get_node(), um den Elternknoten zu finden und die Liste so umzuverketten, dass das betreffende Item abgetrennt wird.

Schließlich geben wir den Speicher durch Aufruf des VHDL-Schlüsselworts deallocate frei und aktualisieren die Buchführungsvariable length_i.

Clear-Prozedur

Um alle Items zu löschen, durchläuft die clear()-Prozedur die Liste mittels While-Schleife und ruft delete() für jedes Element auf, bis keine mehr übrig sind.

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

Length-Funktion

Um guter Programmierpraxis zu genügen, stellen wir eine Getter-Funktion bereit, anstatt dem Nutzer direkten Zugriff auf die Variable length_i zu gewähren.

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

Der Unterschied ist für den Nutzer nicht spürbar, da man für einen parameterlosen Funktionsaufruf keine Klammern benötigt (my_list.length). Aber der Nutzer kann die interne Buchführungsvariable nicht ändern – ein Schutz vor Missbrauch.

String-Liste in einem Testbench verwenden

Nun, da die Listen-Implementierung komplett ist, ist es an der Zeit, sie in einem Testbench auszuführen. Zuerst müssen wir den Protected Type aus einem Paket importieren, wie in der ersten Zeile des folgenden Codes gezeigt.

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

Der Protected Type ist VHDLs klassenähnliches Konstrukt, und wir können ein Objekt davon erstellen, indem wir eine Shared Variable vom Typ string_list deklarieren, wie in der letzten Zeile oben gezeigt. Wir nennen es ‘l’ für „list“, um das Python-Beispiel vom Artikelanfang nachzubilden.

Ab jetzt können wir mit einem Software-Ansatz auf die Daten der Liste zugreifen. Wie im folgenden Testbench-Prozess gezeigt, können wir ein öffentliches Subprogramm referenzieren, indem wir die Punktnotation auf der Shared Variable verwenden (l.append("Amsterdam")).

 begin SEQUENCER_PROC : process begin print("* Vier Strings anhängen"); print(" l.append(Amsterdam)"); l.append("Amsterdam"); print(" l.append(Bangkok)"); l.append("Bangkok"); print(" l.append(Kopenhagen)"); l.append("Kopenhagen"); print(" l.append(Damaskus)"); l.append("Damaskus"); ... 

Ich habe den vollständigen Testbench und das Run-Skript weggelassen, um die Artikellänge zu reduzieren, aber Sie können ihn anfordern, indem Sie Ihre E-Mail-Adresse im untenstehenden Formular hinterlassen. Sie erhalten innerhalb von Minuten eine ZIP-Datei mit dem vollständigen VHDL-Code und einem ModelSim-Projekt in Ihrem Posteingang.

Testbench ausführen

Falls Sie das Beispielprojekt über das obige Formular heruntergeladen haben, sollten Sie die folgende Ausgabe reproduzieren können. Beachten Sie „How to run.txt“ in der ZIP-Datei für genaue Anweisungen.

Es handelt sich um einen manuell zu prüfenden Testbench, und ich habe die Testfälle so gestaltet, dass sie meinem Python-Beispiel so weit wie möglich ähneln. Anstelle der Python-Methode pop() verwenden wir die VHDL-Listen-get()-Funktion gefolgt von einem Aufruf von delete(). Das bewirkt dasselbe.

Wie aus dem Ausdruck auf der ModelSim-Konsole unten ersichtlich, verhält sich die VHDL-Liste ähnlich wie ihr Python-Pendant.

 # * Vier Strings anhängen # l.append(Amsterdam) # l.append(Bangkok) # l.append(Kopenhagen) # l.append(Damaskus) # * Alle Strings vom Listenanfang poppen # l.get(0): Amsterdam # l.get(1): Bangkok # l.get(2): Kopenhagen # l.get(3): Damaskus # * Vier Strings in gemischter Reihenfolge einfügen # l.insert(0, Bangkok) # l.insert(1, Kopenhagen) # l.insert(0, Amsterdam) # l.insert(3, Damaskus) # * Liste wie ein Array durchlaufen # l.get(0): Amsterdam # l.get(1): Bangkok # l.get(2): Kopenhagen # l.get(3): Damaskus # * Alle Strings vom Listenende poppen # l.get(0): Damaskus # l.get(1): Kopenhagen # l.get(2): Bangkok # l.get(3): Amsterdam # * Anhängen und Einfügen an vorletzter Position # l.append(Amsterdam) # l.append(Bangkok) # l.append(Damaskus) # l.insert(-1, Kopenhagen) # * Vom letzten Position poppen # l.get(-1): Damaskus # * Liste wie ein Array durchlaufen # l.get(0): Amsterdam # l.get(1): Bangkok # l.get(2): Kopenhagen # * Listenlänge prüfen # l.length: 3 # * Liste leeren # * Listenlänge prüfen # l.length: 0 # * Fertig 

Abschließende Gedanken

Ich finde, die höheren Programmierfeatures von VHDL werden unterschätzt. Zwar sind sie für RTL-Design nicht nützlich, da sie nicht synthetisierbar sind, aber für Verifikationszwecke können sie sehr hilfreich sein.

Auch wenn die Implementierung komplex sein mag, wird es für den Endnutzer – die Person, die den Testbench schreibt, der den Protected Type nutzt – einfacher. Der Protected Type verbirgt die gesamte Komplexität vor dem Nutzer.

Es braucht nur drei Zeilen, um einen Protected Type zu nutzen: Paket importieren, Shared Variable deklarieren, und ein Subprogramm im Testbench-Prozess aufrufen. Das ist simpler als die Instanziierung einer VHDL-Komponente.

Siehe auch: Wie man eine verkettete Liste in VHDL erstellt

Schreiben Sie Ihre Meinung in den Kommentarbereich unter dem Artikel!