So erstellen Sie eine Liste von Zeichenfolgen in VHDL

Textzeichenfolgen in VHDL sind im Allgemeinen auf Zeichenarrays mit fester Länge beschränkt. Das ist sinnvoll, weil VHDL Hardware beschreibt und Zeichenfolgen generischer Länge dynamischen Speicher benötigen.

Um ein String-Array zu definieren, müssen Sie zur Kompilierzeit Speicherplatz für die höchste Anzahl von Strings zuweisen, die Sie speichern möchten. Und noch schlimmer, Sie müssen sich für die maximale Länge der Zeichenfolgen entscheiden und jedes Vorkommen mit dieser Anzahl von Zeichen auffüllen. Der folgende Code zeigt ein Beispiel für die Verwendung eines solchen Konstrukts.

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

Während dies aus Hardware-Sicht sinnvoll ist, wird es umständlich, String-Arrays in VHDL-Testbenches zu verwenden. Daher habe ich mich entschieden, ein dynamisches Zeichenfolgenlistenpaket zu erstellen, das ich in diesem Artikel erläutern werde.

Sie können den vollständigen Code mit dem untenstehenden Formular herunterladen.

Listenklasse von Python

Lassen Sie uns unsere dynamische VHDL-Liste nach einer bekannten Listenimplementierung modellieren. Unsere VHDL-String-Liste ahmt das Verhalten der integrierten Listenklasse von Python nach. Wir übernehmen das append() , Einfügen() und pop() Methoden aus der Python-Liste.

Um Ihnen zu zeigen, was ich meine, werde ich direkt hineinspringen und eine interaktive Python-Shell öffnen, um einige Experimente durchzuführen.

Lassen Sie uns zunächst damit beginnen, eine Liste zu deklarieren und vier Zeichenfolgen daran 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("Copenhagen")
In [5]: l.append("Damascus")

Das anhängen() Methode ist einfach; es fügt ein Objekt an das Ende der Liste an.

Wir können das mit dem pop() überprüfen -Methode, die ein Element entfernt und an den Aufrufer zurückgibt. Das Argument gibt die Position des abzurufenden Elements an. Indem wir 0 eingeben, bis die Liste leer ist, erhalten wir den Inhalt vom niedrigsten zum höchsten Index geordnet:

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

OK, füllen wir die Liste auf. Und dieses Mal verwenden wir insert() Methode, um die Listenelemente in der falschen Reihenfolge hinzuzufügen:

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

Die Einfügung() Mit der Funktion können Sie angeben, an welchem ​​Index das neue Element eingefügt werden soll. Im obigen Beispiel haben wir dieselbe Liste wie zuvor erstellt. Lassen Sie uns das überprüfen, indem wir die Liste wie ein Array durchlaufen:

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

Der Listenoperator in Python-Klammer [] löscht das Element nicht; Dadurch verhält sich eine Liste wie ein Array. Sie erhalten den Inhalt des Slots indexiert durch die Zahl in den Klammern, wie Sie der Auflistung oben entnehmen können.

Lassen Sie uns die Liste leeren, indem wir sie öffnen, diesmal jedoch vom Ende der Liste. Eine Besonderheit von Python-Listen ist, dass Sie einen negativen Index verwenden können, um vom letzten Element statt vom Anfang der Liste zu zählen. Es funktioniert mit dem Klammeroperator und mit insert() oder pop() Methoden.

Durch Popping von Index -1 erhalten Sie immer das letzte Element aus der Liste. Wenn wir das in eine For-Schleife einfügen, wird die Liste in umgekehrter Reihenfolge geleert:

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

Sie können auch negative Indizes zum Einfügen verwenden. In der letzten Zeile des folgenden Beispiels fügen wir „Kopenhagen“ bei Index -1 ein:

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

Wenn wir die Liste durchgehen, sehen wir, dass „Kopenhagen“ jetzt das vorletzte Element ist:

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

Jetzt kommt der springende Punkt (aber es macht Sinn).

Beim Einfügen in -1 wird das neue Element zum vorletzten, aber beim Einfügen von -1 erhalten wir das letzte Element.

Dies ist sinnvoll, da -1 sich auf die Position des letzten Elements bezieht, das sich derzeit in der Liste befindet. Und wenn wir knallen, fragen wir nach dem letzten Element. Aber wenn wir einfügen, bitten wir Sie, das neue Element an der Position des letzten Elements einzufügen, das sich derzeit in der Liste befindet. Somit verschiebt das neue Element das letzte Element um einen Platz.

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

In [18]: l.pop(-1) # pop from the last position
Out[18]: 'Damascus'

Die Liste enthält jetzt drei Elemente:

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

Es ist auch möglich, die Listenlänge wie folgt zu zählen:

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

Und wir können die Liste leeren, indem wir clear() aufrufen :

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

Wie Sie sehen können, sind Python-Listen vielseitig und viele Programmierer verstehen sie. Deshalb werde ich meine VHDL-Listenimplementierung auf dieser Erfolgsformel aufbauen.

Die VHDL-Unterprogramm-Prototypen der Zeichenfolgenliste

Damit wir mit der String-Liste wie mit einem Objekt mit Member-Methoden arbeiten können, müssen wir sie als geschützten Typ deklarieren. Und wir platzieren den geschützten Typ in einem Paket mit demselben Namen:string_list .

Der folgende Code zeigt den „öffentlichen“ Teil des geschützten Typs, der die Unterprogramm-Prototypen auflistet.

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 das append() , Einfügen() und clear() Prozeduren sind identisch mit ihren Python-Gegenstücken, wir können pop() nicht portieren Funktion direkt in VHDL. Das Problem ist, dass wir dynamische Objekte nicht einfach aus geschützten Typen in VHDL herausgeben können.

Um diese Einschränkung zu umgehen, habe ich pop() geteilt Funktionalität in zwei Unterprogramme:get() und löschen() . Dadurch können wir das Element zuerst wie ein Array indizieren und es dann löschen, wenn wir es nicht mehr benötigen. Zum Beispiel, nachdem wir den String an die Simulatorkonsole ausgegeben haben.

Die Länge() unreine Funktion verhält sich wie Pythons eingebautes len() Funktion. Es gibt die Anzahl der Strings in der Liste zurück.

Die VHDL-Implementierung der Zeichenfolgenliste

Geschützte Typen bestehen aus zwei Abschnitten:dem deklarativen Teil und dem Hauptteil. Während der deklarative Teil für den Benutzer sichtbar ist, enthält der Hauptteil die Unterprogrammimplementierungen und alle privaten Variablen. Jetzt ist es an der Zeit, das Innenleben der Stringliste zu enthüllen.

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

Als interne Datenstruktur verwenden wir eine einfach verkettete Liste.

Lesen Sie auch:So erstellen Sie eine verknüpfte Liste in VHDL

Da sich der gesamte folgende Code im Text des geschützten Typs befindet, sind diese Konstrukte außerhalb dieses Pakets nicht direkt zugänglich. Die gesamte Kommunikation muss durch die Unterprogramme laufen, die in der deklarativen Region aufgeführt sind, die wir im vorherigen Abschnitt besprochen haben.

Datenspeichertypen und Variablen

Wie Sie dem folgenden Code entnehmen können, deklarieren wir zunächst einen Zugriffstyp, einen VHDL-Zeiger auf eine Zeichenfolge im dynamischen Speicher. Wenn wir über dynamischen Speicher sprechen, ist es kein DRAM auf dem FPGA, da dieser Code nicht synthetisierbar ist. Die Zeichenfolgenliste ist eine reine Simulationskomponente und verwendet den dynamischen Speicher des Computers, auf dem die Simulation ausgeführt wird.

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ändiger Typ. Wir müssen es so machen, weil wir in der nächsten Zeile auf item verweisen beim Erstellen von item_ptr .

Und schließlich spezifizieren wir die vollständige Deklaration des Elements type, ein Datensatz, der einen String-Zeiger und einen Zeiger auf das nächste Element enthält. Zwischen den Typen item->item_ptr->item besteht eine zirkuläre Abhängigkeit , und indem zuerst das unvollständige Element deklariert wird type, vermeiden wir einen Kompilierungsfehler.

Der geschützte Typ enthält zwei Variablen, die unten gezeigt werden:root und Länge_i . Das Element, auf das root zeigt wird das erste Element der Liste, Array-Index Null. Und die Länge_i Die Variable spiegelt immer die Anzahl der Strings in der Liste wider.

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

Verfahren anhängen

Das anhängen() Das unten gezeigte Verfahren ist eine Kurzschreibweise zum Einfügen einer Zeichenfolge 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 dem Index -1 einzufügen:insert(-1, str) . Das Einfügen an der letzten Position erfordert jedoch die Länge der Liste als Indexargument. Das ist wahrscheinlich der Grund, warum Pythons Liste ein dediziertes append() hat Methode, und wir werden auch eine haben.

Prozedur einfügen

Das unten gezeigte Einfügeverfahren funktioniert in vier Schritten.

Zuerst erstellen wir ein dynamisches Elementobjekt, indem wir die VHDL new verwenden Stichwort. Wir erstellen zuerst ein Listenelementobjekt und dann ein dynamisches Zeichenfolgenobjekt, 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

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

Schritt Nummer zwei besteht darin, das Indexargument in einen Index zu übersetzen, der dem Bereich der Liste entspricht. Pythons list.insert() Die Implementierung erlaubt Out-of-Bounds-Indizes, und unsere VHDL-Liste wird dies auch zulassen. Wenn der Benutzer auf einen zu hohen oder zu niedrigen Index verweist, wird standardmäßig der höchste Index oder Element 0 verwendet. Außerdem verwenden wir den Modulo-Operator, um alle eingehenden negativen Indizes in eine positive Array-Position zu übersetzen.

In Schritt Nummer drei gehen wir die Liste durch, um den Knoten zu finden, nach dem eingefügt werden soll. Wie immer müssen wir bei verknüpften Listen den Sonderfall des Einfügens an der Wurzel explizit behandeln.

Der vierte und letzte Schritt besteht darin, die length_i zu erhöhen Variable, um sicherzustellen, dass die Buchhaltung auf dem neuesten Stand ist.

Interne get_index- und get_node-Funktionen

Aufgrund der Objektübergabebeschränkungen von VHDL haben wir uns entschieden, pop() aufzuteilen in zwei Unterprogramme:get() und löschen() . Die erste Funktion ruft das Element ab und die zweite Prozedur entfernt es aus der Liste.

Aber der Algorithmus zum Nachschlagen des Index oder Objekts ist identisch mit get() und löschen() , also können wir es separat in zwei privaten Funktionen implementieren:get_index() und get_node() .

Im Gegensatz zu insert() , Pythons pop() -Funktion erlaubt keine Out-of-Bounds-Indizes, und unser get_index() auch nicht Funktion. Um Benutzerfehlern vorzubeugen, lösen wir einen Assertion-Fehler aus, wenn der angeforderte Index außerhalb der zulässigen Grenzen liegt, 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;

Der get_node() Die unten gezeigte Funktion geht noch einen Schritt weiter und findet das eigentliche Objekt am angegebenen Index. Es verwendet get_index() um den richtigen Knoten nachzuschlagen und gibt einen Zeiger auf das Element zurück Objekt.

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

Wegen dem privaten get_node() Funktion, die öffentliche get() Funktion wird ziemlich einfach. Es ist ein Einzeiler, der den richtigen Knoten abruft, den Inhalt der Zeichenfolge entpackt und an den Aufrufer zurückgibt.

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

Vorgang löschen

Das delete() Prozedur verwendet auch get_index() und get_node() den Algorithmus zu vereinfachen. Zuerst verwenden wir get_index() um den Index des zu entfernenden Objekts zu finden, wie in index_c gezeigt konstante Deklaration unten.

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 trennen wir den Knoten von der Liste. Wenn es sich um das Root-Objekt handelt, legen wir das nächste Element als Root fest. Andernfalls verwenden wir get_node() um das übergeordnete Element zu finden und die Liste erneut zu verknüpfen, um das vorliegende Element zu trennen.

Und schließlich geben wir den Speicher frei, indem wir das VHDL-Schlüsselwort deallocate aufrufen und aktualisieren Sie die length_i Buchhaltungsvariable.

Klares Verfahren

Um alle Elemente zu löschen, clear() Prozedur durchläuft die Liste mit einer While-Schleife und ruft delete() auf auf jedem Element, bis keine mehr übrig sind.

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

Längenfunktion

Um der guten Programmierpraxis zu entsprechen, stellen wir eine Getter-Funktion bereit, anstatt dem Benutzer den direkten Zugriff auf length_i zu ermöglichen Variable.

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

Der Unterschied wird für den Benutzer nicht wahrnehmbar sein, da Sie keine Klammern benötigen, um eine Funktion ohne Parameter aufzurufen (my_list.length ). Aber der Benutzer kann die interne Buchhaltungsvariable nicht ändern, und das ist ein Schutz vor Missbrauch.

Verwendung der Stringliste in einer Testbench

Nachdem die Listenimplementierung abgeschlossen ist, ist es an der Zeit, sie in einer Testbench auszuführen. Zuerst müssen wir den geschützten Typ 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 geschützte Typ sind die klassenähnlichen Konstrukte von VHDL, und wir können daraus ein Objekt erstellen, indem wir eine gemeinsam genutzte Variable vom Typ string_list deklarieren , wie in der letzten Zeile oben gezeigt. Wir nennen es „l“ für „Liste“, um das Python-Beispiel zu replizieren, das ich zu Beginn dieses Artikels vorgestellt habe.

Von nun an können wir über einen Softwareansatz auf die Daten der Liste zugreifen. Wie im folgenden Testbench-Prozess gezeigt, können wir auf ein öffentliches Unterprogramm verweisen, indem wir die Punktnotation für die gemeinsam genutzte Variable verwenden (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");
...

Ich habe die vollständige Testbench weggelassen und das Skript ausgeführt, um die Länge dieses Artikels zu reduzieren, aber Sie können es anfordern, indem Sie Ihre E-Mail-Adresse im Formular unten hinterlassen. Innerhalb weniger Minuten erhalten Sie eine Zip-Datei mit dem vollständigen VHDL-Code und einem ModelSim-Projekt in Ihrem Posteingang.

Laufen der Testbench

Wenn Sie das Beispielprojekt über das obige Formular heruntergeladen haben, sollten Sie in der Lage sein, die folgende Ausgabe zu replizieren. Genaue Anweisungen finden Sie unter „How to run.txt“ in der Zip-Datei.

Es ist eine Testbench mit manueller Überprüfung, und ich habe die Testfälle meinem Python-Beispiel so ähnlich wie möglich gemacht. Anstelle des pop() Python-Methode verwenden wir get() der VHDL-Liste Funktion gefolgt von einem Aufruf von delete() . Das macht dasselbe.

Wie wir aus dem unten gezeigten Ausdruck auf der ModelSim-Konsole sehen können, verhält sich die VHDL-Liste ähnlich wie ihr Python-Pendant.

# * 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

Abschließende Gedanken

Ich denke, die übergeordneten Programmierfunktionen von VHDL werden unterschätzt. Obwohl es für das RTL-Design nicht nützlich ist, weil es nicht synthetisierbar ist, kann es für Verifizierungszwecke nützlich sein.

Auch wenn die Implementierung kompliziert sein mag, ist es für den Endbenutzer, die Person, die die Testbench schreibt, die den geschützten Typ verwendet, einfacher. Der geschützte Typ verbirgt die gesamte Komplexität vor dem Benutzer.

Es sind nur drei Zeilen erforderlich, um einen geschützten Typ zu verwenden:Importieren Sie das Paket, deklarieren Sie die gemeinsam genutzte Variable und rufen Sie ein Unterprogramm im Testbench-Prozess auf. Das ist einfacher als das Instanziieren einer VHDL-Komponente.

Siehe auch:So erstellen Sie eine verknüpfte Liste in VHDL

Sagen Sie mir Ihre Meinung im Kommentarbereich unter dem Artikel!