Dynamische string-lijsten in VHDL: Best Practices & Voorbeeld

Tekststrings in VHDL zijn doorgaans beperkt tot fixed-length karakterarrays. Dat is logisch omdat VHDL hardware beschrijft, en variable-length strings dynamisch geheugen vereisen.

Om een array van strings te definiëren, moet je bij compilatie ruimte reserveren voor het maximale aantal strings dat je wilt opslaan. En nog erger, je moet de maximale lengte van de strings vastleggen en elke instantie aanvullen tot dat aantal karakters. De onderstaande code toont een voorbeeld van zo'n 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 dit vanuit een hardware-perspectief zinvol is, wordt het omslachtig om string-arrays in VHDL-testbenches te gebruiken. Daarom heb ik een dynamisch string-lijstpakket gemaakt dat ik in dit artikel uitleg.

Je kunt de complete code downloaden via het formulier hieronder.

Python's list-klasse

Laten we onze dynamische VHDL-lijst modelleren naar een bekende lijst-implementatie. Onze VHDL-stringlijst zal het gedrag nabootsen van Python's ingebouwde list-klasse. We adoptieren de append(), insert() en pop() methodes van de Python-lijst.

Om te laten zien wat ik bedoel, spring ik direct in en open een interactieve Python-shell voor een paar experimenten.

Eerst declareren we een lijst en voegen we vier strings toe met append, zoals hieronder getoond.

 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 aan het einde van de lijst toe.

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 0 te poppen tot de lijst leeg is, krijgen we de inhoud geordend van laagste naar hoogste index:

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

OK, laten we de lijst opnieuw vullen. En deze keer gebruiken we de insert() methode om de elementen in een willekeurige 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 je toe om de index op te geven waar het nieuwe item moet worden ingevoegd. In het bovenstaande voorbeeld creëerden we dezelfde lijst als eerder. Laten we 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-bracket [] lijstoperator verwijdert het item niet; het laat een lijst gedragen als een array. Je krijgt de inhoud van de slot geïndexeerd door het getal tussen de haakjes, zoals te zien is in de opsomming hierboven.

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

Door index -1 te poppen, krijg je altijd het laatste item uit de lijst. Als we dat in een for-lus zetten, leegt het de lijst in omgekeerde volgorde:

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

Je kunt negatieve indexes ook gebruiken om in te voegen. In de laatste regel van het onderstaande voorbeeld voegen we "Copenhagen" in op index -1:

 In [13]: l.append("Amsterdam") In [14]: l.append("Bangkok") In [15]: l.append("Damascus") In [16]: l.insert(-1, "Copenhagen") # invoegen op de voorlaatste positie 

Wanneer we de lijst doorlopen, zien we dat "Copenhagen" nu het voorlaatste element is:

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

Nu komt het cruciale punt (maar het is logisch).

Bij invoegen op -1 wordt het nieuwe item het voorlaatste, maar bij poppen van -1 krijgen we het laatste item.

Dat klopt omdat -1 verwijst naar de positie van het laatste element dat momenteel in de lijst zit. En wanneer we poppen, 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 zit. Dus het nieuwe item schuift het finale element één slot op.

We kunnen dit bevestigen door element -1 te poppen, wat "Damascus" oplevert, en niet "Copenhagen":

 In [18]: l.pop(-1) # poppen vanaf de laatste positie 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 lijstlengte op te vragen:

 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 ziet, zijn Python-lijsten veelzijdig, en veel programmeurs begrijpen ze. Daarom baseer ik mijn VHDL-lijstimplementatie op deze succesformule.

De VHDL-subprogramma-prototypen voor de string-lijst

Om met de string-lijst te werken als een object met lidmethodes, moeten we deze declareren als een protected type. En we plaatsen het protected type in een pakket met dezelfde naam: string_list.

De onderstaande code toont het "publieke" deel van het protected type met de subprogramma-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; 

Terwijl de append(), insert() en clear() procedures identiek zijn aan hun Python-counterparts, kunnen we de pop() functie niet direct naar VHDL porteren. Het probleem is dat we dynamische objecten niet eenvoudig uit protected types in VHDL kunnen doorgeven.

Om deze beperking te overwinnen, heb ik de pop() functionaliteit opgesplitst in twee subprogramma's: get() en delete(). Dat stelt ons in staat om het element eerst te indexeren, als een array, en het daarna te verwijderen wanneer we het niet meer nodig hebben. Bijvoorbeeld, nadat we de string naar de simulator-console hebben geprint.

De length() impure function gedraagt zich als Python's ingebouwde len() functie. Het retourneert het aantal strings in de lijst.

De VHDL-implementatie van de string-lijst

Protected types bestaan uit twee secties: het declaratieve deel en de body. Terwijl het declaratieve deel zichtbaar is voor de gebruiker, bevat de body de subprogramma-implementaties en eventuele private variabelen. Nu is het tijd om de binnenwerkingen van de string-lijst te onthullen.

Laat je e-mailadres in het formulier hieronder om de complete code en ModelSim-project in je inbox te ontvangen!

We zullen een enkelvoudig gekoppelde lijst als interne datastructuur gebruiken.

Lees ook: Hoe een Linked List in VHDL te maken

Omdat alle code die volgt in de body van het protected type zit, zijn deze constructies niet direct toegankelijk van buiten dit pakket. Alle communicatie moet verlopen via de subprogramma's die in het declaratieve gebied staan dat we in de vorige sectie bespraken.

Datastoragetypes en variabelen

Zoals je kunt zien in de onderstaande code, declareren we eerst een access type, een VHDL-pointer naar een string in dynamisch geheugen. Wanneer we over dynamisch geheugen praten, is het geen DRAM op de FPGA want deze code is niet synthetiseerbaar. De string-lijst is puur een simulatiecomponent en zal het dynamische geheugen van de computer gebruiken die de simulatie draait.

 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 declareren we item als een incompleet type. We moeten dat zo doen omdat we op de volgende regel item refereren bij het aanmaken van item_ptr.

En tenslotte specificeren we de volledige declaratie van het item type, een record met een string-pointer en een pointer naar het volgende element. Er is een circulaire afhankelijkheid tussen de types item->item_ptr->item, en door eerst het incompleete item type te declareren, vermijden we een compilatiefout.

Het protected type bevat twee variabelen, hieronder getoond: root en length_i. Het item waar root naar wijst, zal het eerste element van de lijst zijn, array-index nul. En de length_i variabele zal altijd het aantal strings in de lijst weerspiegelen.

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

Append-procedure

De append() procedure hieronder 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 eenvoudig om op de voorlaatste positie in te voegen met index -1: insert(-1, str). Maar invoegen op de laatste positie vereist de lengte van de lijst als index-argument. Dat is waarschijnlijk waarom Python's lijst een speciale append() methode heeft, en wij zullen er ook een hebben.

Insert-procedure

De insert-procedure, hieronder getoond, werkt in vier stappen.

Eerst creëren we een dynamisch item-object door het VHDL new keyword te gebruiken. We maken eerst een lijst-item-object en daarna een dynamisch string-object om daarin op te slaan.

 procedure insert(index : integer; str : string) is variable new_item : item_ptr; variable node : item_ptr; variable index_v : integer; begin -- Creëer het nieuwe object new_item := new item; new_item.str := new string'(str); -- Beperk de index tot het lijstbereik 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 -- Het nieuwe object wordt root bij invoegen op positie 0 new_item.next_item := root; root := new_item; else -- Zoek het node om na in te voegen node := root; for i in 2 to index_v loop node := node.next_item; end loop; -- Voeg het nieuwe item in new_item.next_item := node.next_item; node.next_item := new_item; end if; length_i := length_i + 1; end procedure; 

Stap twee is het vertalen van het index-argument naar een index die voldoet aan het bereik van de lijst. Python's list.insert() implementatie toestaat out-of-bounds indexes, en onze VHDL-lijst zal dat ook toestaan. Als de gebruiker een te hoge of lage index referentieert, zal het standaard naar de hoogste index gaan, of element 0. Ook gebruiken we de modulo-operator om elke in-bounds negatieve index te vertalen naar een positieve array-positie.

In stap drie lopen we de lijst af om het node te vinden waar na ingevoegd moet worden. Zoals altijd bij gekoppelde lijsten, moeten we het speciale geval van invoegen bij de root expliciet afhandelen.

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

Interne get_index en get_node functies

Vanwege VHDL's object-doorlaatbeperkingen, besloten we pop() op 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 object is identiek voor get() en delete(), dus we kunnen het apart implementeren in twee private functies: get_index() en get_node().

In tegenstelling tot insert(), toestaat Python's pop() functie geen out-of-bounds indexes, en onze get_index() functie ook niet. Om te beschermen tegen gebruikersfouten, zullen we een assertion-failure opwekken als de gevraagde index out-of-bounds is, zoals hieronder getoond.

 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 getoond, gaat een stap verder en vindt het daadwerkelijke object op de gespecificeerde index. Het gebruikt get_index() om het juiste node op te zoeken en retourneert een pointer naar het item object.

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

Vanwege de private get_node() functie, wordt de publieke get() functie vrij simpel. Het is een one-liner die het juiste node ophaalt, de string-inhoud uitpakt en aan de aanroeper retourneert.

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

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

Dan koppelen we het node los van de lijst. Als het het root-object is, stellen we het volgende item in als root. Anders gebruiken we get_node() om de parent te vinden en de lijst te herkoppelen om het item in kwestie los te koppelen.

En ten slotte vrijgeven we het geheugen door het VHDL keyword deallocate aan te roepen en de length_i boekhoudvariabele bij te werken.

Clear-procedure

Om alle items te verwijderen, doorloopt de clear() procedure de lijst met een While-lus, roept delete() aan op elk element tot er geen meer over zijn.

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

Length-functie

Om goede programmeerpraktijken te volgen, bieden we een getter-functie aan in plaats van de gebruiker direct toegang te geven tot de length_i variabele.

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

Het verschil is voor de gebruiker onmerkbaar omdat 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 bescherming tegen misbruik.

De string-lijst gebruiken in een testbench

Nu de lijstimplementatie compleet is, is het tijd om hem in een testbench te draaien. Eerst moeten we het protected type importeren uit een pakket, zoals getoond 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 protected type is VHDL's klasse-achtige constructen, en we kunnen een object ervan maken door een shared variable te declareren van type string_list, zoals getoond op de laatste regel hierboven. We noemen het 'l' voor "list" om het Python-voorbeeld dat ik aan het begin van dit artikel presenteerde na te bootsen.

Vanaf nu kunnen we een software-benadering gebruiken om toegang te krijgen tot de data van de lijst. Zoals getoond in het testbench-proces hieronder, kunnen we een publiek subprogramma benaderen door de dot-notatie te gebruiken op de shared variable (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 complete testbench en run-script weggelaten om de lengte van dit artikel te beperken, maar je kunt het aanvragen door je e-mailadres in het formulier hieronder te laten. Je ontvangt een Zip-bestand met de complete VHDL-code en een ModelSim-project in je inbox binnen enkele minuten.

De testbench draaien

Als je het voorbeeldproject hebt gedownload via het formulier hierboven, zou je de volgende output moeten kunnen reproduceren. Raadpleeg "How to run.txt" in het Zip-bestand voor nauwkeurige instructies.

Het is een handmatig-check testbench, en ik heb de testcases zo gemaakt dat ze mijn Python-voorbeeld zo nauwkeurig mogelijk nabootsen. In plaats van de pop() Python-methode, gebruiken we de VHDL-lijst's get() functie gevolgd door een aanroep naar delete(). Dat doet hetzelfde.

Zoals we uit de printuitvoer naar de ModelSim-console hieronder kunnen zien, gedraagt de VHDL-lijst zich vergelijkbaar met zijn Python-counterpart.

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

Eindgedachten

Ik vind dat de hogere programmeerfuncties van VHDL onderschat worden. Hoewel het niet nuttig is voor RTL-ontwerp omdat het niet synthetiseerbaar is, kan het nuttig zijn voor verificatie-doeleinden.

Hoewel de implementatie complex kan zijn, zal het voor de eindgebruiker, de persoon die de testbench schrijft die het protected type gebruikt, simpeler zijn. Het protected type verbergt alle complexiteit voor de gebruiker.

Het kost maar drie regels om een protected type te gebruiken: het pakket importeren, de shared variable declareren, en een subprogramma aanroepen in het testbench-proces. Dat is simpeler dan een VHDL-component instantieren.

Zie ook: Hoe een Linked List in VHDL te maken

Laat me weten wat je denkt in de reactiesectie onder het artikel!