Een lijst met strings maken in VHDL

Tekstreeksen in VHDL zijn over het algemeen beperkt tot tekenreeksen met een vaste lengte. Dat is logisch omdat VHDL hardware beschrijft, en strings van generieke lengte vereisen dynamisch geheugen.

Om een ​​reeks tekenreeksen te definiëren, moet u tijdens het compileren ruimte toewijzen voor het hoogste aantal tekenreeksen dat u wilt opslaan. En erger nog, je moet beslissen over de maximale lengte van de snaren en elke keer dat ze voorkomen op dat aantal tekens. De onderstaande code toont een voorbeeld van het gebruik van een dergelijke constructie.

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

Hoewel dat vanuit hardwareperspectief logisch is, wordt het omslachtig om stringarrays in VHDL-testbanken te gebruiken. Daarom heb ik besloten om een ​​dynamisch stringlist-pakket te maken dat ik in dit artikel zal uitleggen.

Je kunt de volledige code downloaden via het onderstaande formulier.

Python's lijstklasse

Laten we onze dynamische VHDL-lijst modelleren naar een bekende lijstimplementatie. Onze VHDL-tekenreekslijst zal het gedrag van de ingebouwde lijstklasse van Python nabootsen. We gebruiken de append() , insert() , en pop() methoden uit de Python-lijst.

Om je te laten zien wat ik bedoel, spring ik er meteen in en open ik een interactieve python-shell om wat experimenten uit te voeren.

Laten we eerst beginnen met het declareren van een lijst en er vier strings aan toevoegen, zoals hieronder weergegeven.

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

De append() methode is eenvoudig; het voegt een object toe aan het einde van de lijst.

We kunnen dat verifiëren met de pop() methode, die een element verwijdert en teruggeeft aan de aanroeper. Het argument specificeert de positie van het op te halen element. Door op 0 te drukken totdat de lijst leeg is, krijgen we de inhoud gerangschikt van de laagste naar de hoogste index:

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

Oké, laten we de lijst aanvullen. En deze keer gebruiken we de insert() methode om de lijstelementen in de verkeerde volgorde toe te voegen:

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

De insert() functie laat u specificeren bij welke index het nieuwe item moet worden ingevoegd. In het bovenstaande voorbeeld hebben we dezelfde lijst gemaakt als voorheen. Laten we dat controleren door de lijst als een array te doorlopen:

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

De Python-haak [] list-operator verwijdert het item niet; het zorgt ervoor dat een lijst zich als een array gedraagt. U krijgt de inhoud van de slots geïndexeerd door het getal tussen de haakjes, zoals u kunt zien in de bovenstaande lijst.

Laten we de lijst leegmaken door te knallen, maar deze keer vanaf het einde van de lijst. Een bijzonderheid van Python-lijsten is dat je een negatieve index kunt gebruiken om vanaf het laatste item te tellen in plaats van vanaf het begin van de lijst. Het werkt met de vierkante operator en met de insert() of pop() methoden.

Door index -1 te laten knappen, krijgt u altijd het laatste item uit de lijst. Als we dat in een For-lus plaatsen, wordt de lijst in omgekeerde volgorde leeggemaakt:

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

U kunt ook negatieve indexen gebruiken om in te voegen. In de laatste regel van het onderstaande voorbeeld voegen we "Kopenhagen" in bij 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

Wanneer we de lijst doorkruisen, kunnen we zien dat "Kopenhagen" nu het op één na laatste element is:

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

Nu komt hier de crux (maar het is logisch).

Bij het invoegen naar -1 wordt het nieuwe item het op één na laatste, maar als we vanaf -1 knallen, krijgen we het laatste item.

Het is logisch omdat -1 verwijst naar de positie van het laatste element dat momenteel in de lijst staat. En als we knallen, vragen we om het laatste element. Maar wanneer we invoegen, vragen we om het nieuwe item in te voegen op de positie van het laatste element dat momenteel in de lijst staat. Het nieuwe item verplaatst het laatste element dus met één slot.

We kunnen dit bevestigen door element -1 te gebruiken, dat "Damascus" retourneert, en niet "Kopenhagen":

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

De lijst bevat nu drie elementen:

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

Het is ook mogelijk om de lengte van de lijst als volgt te tellen:

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

En we kunnen de lijst leegmaken door clear() . aan te roepen :

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

Zoals je kunt zien, zijn Python-lijsten veelzijdig en veel programmeurs begrijpen ze. Daarom zal ik mijn VHDL-lijstimplementatie op deze succesformule baseren.

De tekenreekslijst VHDL-subprogramma-prototypes

Om ons in staat te stellen om met de stringlijst te werken als een object met lidmethoden, moeten we het als een beveiligd type declareren. En we plaatsen het beschermde type in een pakket met dezelfde naam:string_list .

De onderstaande code toont het "openbare" deel van het beschermde type met de prototypes van het subprogramma.

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;

Terwijl de append() , insert() , en clear() procedures zijn identiek aan hun Python-tegenhangers, we kunnen de pop() . niet overzetten direct naar VHDL. Het probleem is dat we dynamische objecten niet gemakkelijk kunnen doorgeven aan beschermde typen in VHDL.

Om deze beperking te omzeilen, heb ik de pop() . gesplitst functionaliteit in twee subprogramma's:get() en delete() . Dat stelt ons in staat om het element eerst te indexeren, zoals een array, en het vervolgens te verwijderen wanneer we het niet meer nodig hebben. Bijvoorbeeld nadat we de string naar de simulatorconsole hebben afgedrukt.

De lengte() onzuivere functie zal zich gedragen als Python's ingebouwde len() functie. Het geeft het aantal strings in de lijst terug.

De tekenreekslijst VHDL-implementatie

Beschermde typen bestaan ​​uit twee delen:het declaratieve deel en het lichaam. Terwijl het declaratieve deel zichtbaar is voor de gebruiker, bevat de body de subprogramma-implementaties en eventuele privévariabelen. Nu is het tijd om de innerlijke werking van de snarenlijst te onthullen.

Laat je e-mailadres achter in het onderstaande formulier om de volledige code en het ModelSim-project in je inbox te ontvangen!

We zullen een enkelvoudig gekoppelde lijst gebruiken als de interne gegevensstructuur.

Lees ook:Een gekoppelde lijst maken in VHDL

Omdat alle code die volgt zich in de body van het beschermde type bevindt, zijn deze constructies niet direct toegankelijk buiten dit pakket. Alle communicatie moet via de subprogramma's die worden vermeld in de declaratieve regio die we in de vorige sectie hebben besproken.

Typen gegevensopslag en variabelen

Zoals je aan de onderstaande code kunt zien, declareren we eerst een toegangstype, een VHDL-aanwijzer naar een string in dynamisch geheugen. Als we het hebben over dynamisch geheugen, is het geen DRAM op de FPGA omdat deze code niet kan worden gesynthetiseerd. De stringlijst is puur een simulatiecomponent en gebruikt het dynamische geheugen van de computer die de simulatie uitvoert.

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;

Na str_ptr , verklaren we item als een onvolledig type. We moeten het zo doen, want op de volgende regel verwijzen we naar item bij het maken van item_ptr .

En tot slot specificeren we de volledige aangifte van het item type, een record met een tekenreeksaanwijzer en een aanwijzer naar het volgende element. Er is een circulaire afhankelijkheid tussen de typen item->item_ptr->item , en door eerst het onvolledige item . te declareren type, vermijden we een compilatiefout.

Het beveiligde type bevat twee variabelen, hieronder weergegeven:root en length_i . Het item waarnaar wordt verwezen door root zal het eerste element van de lijst zijn, array index nul. En de length_i variabele geeft altijd het aantal strings in de lijst weer.

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

Procedure toevoegen

De append() onderstaande procedure is een verkorte notatie voor het invoegen van een string op de laatste positie van de lijst.

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

Zoals besproken in het Python-voorbeeld, is het gemakkelijk om op de een na laatste positie in te voegen met index -1:insert(-1, str) . Maar voor het invoegen op de laatste positie is de lengte van de lijst vereist als het indexargument. Dat is waarschijnlijk de reden waarom Python's lijst een speciale append() heeft methode, en we zullen er ook een hebben.

Invoegprocedure

De invoegprocedure, hieronder weergegeven, werkt in vier stappen.

Eerst maken we een dynamisch itemobject met behulp van de VHDL new trefwoord. We maken eerst een lijstitemobject en vervolgens een dynamisch tekenreeksobject om erin op te slaan.

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;

Stap nummer twee is om het indexargument te vertalen naar een index die overeenkomt met het bereik van de lijst. Python's list.insert() implementatie staat out-of-bounds indexen toe, en onze VHDL-lijst zal dit ook toestaan. Als de gebruiker verwijst naar een te hoge of lage index, wordt standaard de hoogste index of element 0 gebruikt. We gebruiken ook de modulo-operator om eventuele negatieve indexen binnen het bereik te vertalen naar een positieve arraypositie.

In stap nummer drie lopen we door de lijst om het knooppunt te vinden dat daarna moet worden ingevoegd. Zoals altijd moeten we bij gelinkte lijsten expliciet omgaan met het specifieke geval van invoegen bij de root.

De vierde en laatste stap is het verhogen van de length_i variabel om ervoor te zorgen dat de boekhouding up-to-date is.

Interne functies get_index en get_node

Vanwege de beperkingen voor het doorgeven van objecten in VHDL, hebben we besloten om pop() te splitsen in twee subprogramma's:get() en delete() . De eerste functie haalt het item op en de tweede procedure verwijdert het uit de lijst.

Maar het algoritme voor het opzoeken van de index of het object is identiek voor get() en delete() , zodat we het afzonderlijk in twee privéfuncties kunnen implementeren:get_index() en get_node() .

In tegenstelling tot insert() , Python's pop() functie staat geen indexen buiten de grenzen toe, en onze get_index() . ook niet functie. Om gebruikersfouten te voorkomen, zullen we een beweringfout melden als de gevraagde index buiten de grenzen valt, zoals hieronder wordt weergegeven.

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;

De get_node() functie, hieronder weergegeven, gaat nog een stap verder en vindt het werkelijke object in de opgegeven index. Het gebruikt get_index() om het juiste knooppunt op te zoeken en een pointer terug te sturen naar het item voorwerp.

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;

Functie ophalen

Vanwege de privé get_node() functie, de openbare get() functie wordt vrij eenvoudig. Het is een one-liner die het juiste knooppunt ophaalt, de string-inhoud uitpakt en terugstuurt naar de beller.

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

Verwijder procedure

De delete() procedure gebruikt ook get_index() en get_node() om het algoritme te vereenvoudigen. Eerst gebruiken we get_index() om de index van het te verwijderen object te vinden, zoals getoond in de index_c constante declaratie hieronder.

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;

Vervolgens ontkoppelen we het knooppunt van de lijst. Als dit het root-object is, stellen we het volgende item in als root. Anders gebruiken we get_node() om de ouder te vinden en de lijst opnieuw te koppelen om het betreffende item los te koppelen.

En tot slot maken we het geheugen vrij door het VHDL-sleutelwoord deallocate . aan te roepen en update de length_i boekhoudvariabele.

Duidelijke procedure

Om alle items te verwijderen, gebruikt u de clear() procedure doorloopt de lijst met behulp van een While-lus, waarbij delete() . wordt aangeroepen op elk element totdat er geen meer over is.

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

Lengtefunctie

Om te voldoen aan goede programmeerpraktijken, bieden we een getter-functie in plaats van de gebruiker rechtstreeks toegang te geven tot de length_i variabel.

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

Het verschil zal voor de gebruiker niet opvallen, aangezien je geen haakjes nodig hebt om een ​​functie zonder parameters aan te roepen (my_list.length ). Maar de gebruiker kan de interne boekhoudvariabele niet wijzigen en dat is een beveiliging tegen misbruik.

De stringlijst gebruiken in een testbench

Nu de lijstimplementatie is voltooid, is het tijd voor ons om deze in een testbench uit te voeren. Eerst moeten we het beschermde type uit een pakket importeren, zoals weergegeven op de eerste regel van de onderstaande code.

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

Het beschermde type is de klasse-achtige constructie van VHDL en we kunnen er een object van maken door een gedeelde variabele van het type string_list te declareren , zoals weergegeven op de laatste regel hierboven. We noemen het 'l' voor 'lijst' om het Python-voorbeeld te repliceren dat ik aan het begin van dit artikel heb gepresenteerd.

Vanaf nu kunnen we een softwarebenadering gebruiken om toegang te krijgen tot de gegevens van de lijst. Zoals getoond in het testbench-proces hieronder, kunnen we verwijzen naar een openbaar subprogramma door de puntnotatie op de gedeelde variabele te gebruiken (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");
...

Ik heb de volledige testbench weggelaten en het script uitgevoerd om de lengte van dit artikel te verkorten, maar je kunt het aanvragen door je e-mailadres in het onderstaande formulier achter te laten. Je ontvangt binnen enkele minuten een Zip-bestand met de volledige VHDL-code en een ModelSim-project in je inbox.

De testbank draaien

Als u het voorbeeldproject hebt gedownload met behulp van het bovenstaande formulier, zou u de volgende uitvoer moeten kunnen repliceren. Raadpleeg "How to run.txt" in het zip-bestand voor precieze instructies.

Het is een testbank met handmatige controle en ik heb de testgevallen zo goed mogelijk op mijn Python-voorbeeld laten lijken. In plaats van de pop() Python-methode, we gebruiken de VHDL-lijst get() functie gevolgd door een aanroep tot delete() . Dat doet hetzelfde.

Zoals we kunnen zien op de afdruk naar de ModelSim-console die hieronder wordt getoond, gedraagt ​​de VHDL-lijst zich op dezelfde manier als zijn Python-tegenhanger.

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

Laatste gedachten

Ik denk dat de programmeerfuncties op een hoger niveau van VHDL worden onderschat. Hoewel het niet handig is voor RTL-ontwerp omdat het niet synthetiseert, kan het nuttig zijn voor verificatiedoeleinden.

Ook al is het misschien ingewikkeld om te implementeren, het zal eenvoudiger zijn voor de eindgebruiker, de persoon die de testbench schrijft die het beschermde type gebruikt. Het beschermde type verbergt alle complexiteit voor de gebruiker.

Er zijn slechts drie regels nodig om een ​​beveiligd type te gebruiken:importeer het pakket, declareer de gedeelde variabele en roep een subprogramma aan in het testbench-proces. Dat is eenvoudiger dan het instantiëren van een VHDL-component.

Zie ook:Een gekoppelde lijst maken in VHDL

Vertel me wat je denkt in het commentaargedeelte onder het artikel!