Creación de listas de cadenas en VHDL: Buenas prácticas y ejemplo

Las cadenas de texto en VHDL generalmente se limitan a arrays de caracteres de longitud fija. Esto tiene sentido porque VHDL describe hardware, y las cadenas de longitud genérica requieren memoria dinámica.

Para definir un array de cadenas, debe asignar espacio en tiempo de compilación para el mayor número de cadenas que desee almacenar. Y aún peor, debe decidir la longitud máxima de las cadenas y rellenar cada ocurrencia hasta ese número de caracteres. El código siguiente muestra un ejemplo de uso de dicha construcción.

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

Aunque esto tiene sentido desde una perspectiva de hardware, resulta engorroso usar arrays de cadenas en testbenches VHDL. Por eso decidí crear un paquete de lista de cadenas dinámica que explicaré en este artículo.

Puede descargar el código completo usando el formulario a continuación.

La clase list de Python

Modelaremos nuestra lista dinámica en VHDL basándonos en una implementación de lista conocida. Nuestra lista de cadenas en VHDL imitará el comportamiento de la clase list integrada de Python. Adoptaremos los métodos append(), insert() y pop() de la lista de Python.

Para mostrar lo que quiero decir, entraré directamente y abriré un shell interactivo de Python para realizar algunos experimentos.

Primero, declaremos una lista y añadamos cuatro cadenas, como se muestra a continuación.

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

El método append() es sencillo; añade un objeto al final de la lista.

Podemos verificarlo con el método pop(), que elimina un elemento y lo devuelve al llamador. El argumento especifica la posición del elemento a recuperar. Al hacer pop(0) hasta que la lista esté vacía, obtenemos el contenido ordenado de menor a mayor índice:

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

Bien, volvamos a llenar la lista. Esta vez usaremos el método insert() para añadir los elementos fuera de orden:

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

La función insert() permite especificar en qué índice insertar el nuevo elemento. En el ejemplo anterior, creamos la misma lista que antes. Comprobémoslo recorriendo la lista como un array:

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

El operador de corchetes [] de Python no elimina el elemento; hace que la lista se comporte como un array. Obtienes el contenido del slot indexado por el número entre corchetes, como se ve en el listado anterior.

Vaciemos la lista haciendo pop, pero esta vez desde el final. Una particularidad de las listas de Python es que se puede usar un índice negativo para contar desde el último elemento en lugar del principio. Funciona con el operador de corchetes y con los métodos insert() o pop().

Al hacer pop en el índice -1, siempre se obtiene el último elemento de la lista. Si ponemos eso en un bucle For, vaciará la lista en orden inverso:

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

También se pueden usar índices negativos para insertar. En la última línea del ejemplo siguiente, insertamos "Copenhagen" en el índice -1:

 In [13]: l.append("Amsterdam") In [14]: l.append("Bangkok") In [15]: l.append("Damascus") In [16]: l.insert(-1, "Copenhagen") # insertar en la penúltima posición 

Al recorrer la lista, vemos que "Copenhagen" es ahora el penúltimo elemento:

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

Ahora viene el punto crucial (pero tiene sentido).

Al insertar en -1, el nuevo elemento se convierte en el penúltimo, pero al hacer pop desde -1, obtenemos el último elemento.

Tiene sentido porque -1 se refiere a la posición del último elemento actualmente en la lista. Y cuando hacemos pop, pedimos el último elemento. Pero cuando insertamos, pedimos insertar el nuevo elemento en la posición del último elemento actual. Así, el nuevo elemento desplaza al final en una posición.

Podemos confirmarlo haciendo pop del elemento -1, que devuelve "Damascus", y no "Copenhagen":

 In [18]: l.pop(-1) # pop desde la última posición Out[18]: 'Damascus' 

La lista ahora contiene tres elementos:

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

También es posible contar la longitud de la lista así:

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

Y podemos vaciar la lista llamando a clear():

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

Como puede ver, las listas de Python son versátiles y muchos programadores las entienden. Por eso basaré mi implementación de lista en VHDL en esta fórmula de éxito.

Prototipos de subprogramas de la lista de cadenas en VHDL

Para permitirnos trabajar con la lista de cadenas como un objeto con métodos miembro, debemos declararla como un tipo protegido. Y colocaremos el tipo protegido en un paquete con el mismo nombre: string_list.

El código siguiente muestra la parte "pública" del tipo protegido listando los prototipos de subprogramas.

 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; 

Mientras que los procedimientos append(), insert() y clear() son idénticos a sus homólogos de Python, no podemos portar la función pop() directamente a VHDL. El problema es que no podemos pasar fácilmente objetos dinámicos fuera de tipos protegidos en VHDL.

Para superar esta limitación, he dividido la funcionalidad de pop() en dos subprogramas: get() y delete(). Eso nos permitirá indexar el elemento primero, como un array, y luego eliminarlo cuando ya no lo necesitemos. Por ejemplo, después de haber impreso la cadena en la consola del simulador.

La función impura length() se comportará como la función integrada len() de Python. Devolverá el número de cadenas en la lista.

Implementación de la lista de cadenas en VHDL

Los tipos protegidos constan de dos secciones: la parte declarativa y el cuerpo. Mientras que la parte declarativa es visible para el usuario, el cuerpo contiene las implementaciones de subprogramas y cualquier variable privada. Ahora es momento de revelar el funcionamiento interno de la lista de cadenas.

Deje su dirección de correo en el formulario a continuación para recibir el código completo y el proyecto ModelSim en su bandeja de entrada.

Utilizaremos una lista simplemente enlazada como estructura de datos interna.

Lea también: Cómo crear una lista enlazada en VHDL

Como todo el código que sigue está en el cuerpo del tipo protegido, estos constructos no son directamente accesibles desde fuera de este paquete. Toda comunicación debe realizarse a través de los subprogramas listados en la región declarativa que discutimos en la sección anterior.

Tipos y variables de almacenamiento de datos

Como puede verse en el código siguiente, primero declaramos un tipo de acceso, un puntero VHDL a una cadena en memoria dinámica. Cuando hablamos de memoria dinámica, no es DRAM en el FPGA porque este código no es sintetizable. La lista de cadenas es puramente un componente de simulación, y usará la memoria dinámica del ordenador que ejecuta la simulación.

 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; 

Después de str_ptr, declaramos item como tipo incompleto. Tenemos que hacerlo así porque en la siguiente línea referenciamos item al crear item_ptr.

Y finalmente, especificamos la declaración completa del tipo item, un registro que contiene un puntero a cadena y un puntero al siguiente elemento. Hay una dependencia circular entre los tipos item->item_ptr->item, y al declarar primero el tipo item incompleto, evitamos un error de compilación.

El tipo protegido contiene dos variables, mostradas a continuación: root y length_i. El elemento apuntado por root será el primer elemento de la lista, índice de array cero. Y la variable length_i reflejará siempre el número de cadenas en la lista.

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

Procedimiento Append

El procedimiento append() mostrado a continuación es una notación abreviada para insertar una cadena en la última posición de la lista.

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

Como se discutió en el ejemplo de Python, es fácil insertar en la penúltima posición usando índice -1: insert(-1, str). Pero insertar en la última posición requiere la longitud de la lista como argumento de índice. Probablemente por eso la lista de Python tiene un método dedicado append(), y nosotros también tendremos uno.

Procedimiento Insert

El procedimiento insert, mostrado a continuación, funciona en cuatro pasos.

Primero, creamos un objeto item dinámico usando la palabra clave new de VHDL. Primero creamos un objeto item de lista y luego un objeto string dinámico para almacenar en él.

 procedure insert(index : integer; str : string) is variable new_item : item_ptr; variable node : item_ptr; variable index_v : integer; begin -- Crear el nuevo objeto new_item := new item; new_item.str := new string'(str); -- Restringir el índice al rango de la lista 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 -- El nuevo objeto se convierte en root al insertar en posición 0 new_item.next_item := root; root := new_item; else -- Encontrar el nodo después del cual insertar node := root; for i in 2 to index_v loop node := node.next_item; end loop; -- Insertar el nuevo item new_item.next_item := node.next_item; node.next_item := new_item; end if; length_i := length_i + 1; end procedure; 

El paso número dos es traducir el argumento índice a un índice que se ajuste al rango de la lista. La implementación list.insert() de Python permite índices fuera de rango, y nuestra lista VHDL también lo permitirá. Si el usuario referencia un índice demasiado alto o bajo, se establecerá por defecto en el índice más alto, o elemento 0. Además, usamos el operador módulo para traducir cualquier índice negativo dentro del rango a una posición de array positiva.

En el paso número tres, recorremos la lista para encontrar el nodo después del cual insertar. Como siempre con listas enlazadas, debemos manejar explícitamente el caso particular de insertar en la raíz.

El cuarto y último paso es incrementar la variable length_i para asegurar que la contabilidad esté actualizada.

Funciones internas get_index y get_node

Debido a las limitaciones de paso de objetos en VHDL, decidimos dividir pop() en dos subprogramas: get() y delete(). La primera función obtendrá el elemento, y el segundo procedimiento lo eliminará de la lista.

Pero el algoritmo para buscar el índice u objeto es idéntico para get() y delete(), así que podemos implementarlo por separado en dos funciones privadas: get_index() y get_node().

A diferencia de insert(), la función pop() de Python no permite índices fuera de rango, y nuestra función get_index() tampoco lo permitirá. Para protegernos contra errores del usuario, lanzaremos una aserción de fallo si el índice solicitado está fuera de rango, como se muestra a continuación.

 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; 

La función get_node(), mostrada a continuación, va un paso más allá y encuentra el objeto real en el índice especificado. Usa get_index() para buscar el nodo correcto y devuelve un puntero al objeto item.

 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; 

Función Get

Gracias a la función privada get_node(), la función pública get() se vuelve bastante simple. Es una one-liner que obtiene el nodo correcto, desempaqueta el contenido de la cadena y lo devuelve al llamador.

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

Procedimiento Delete

El procedimiento delete() también usa get_index() y get_node() para simplificar el algoritmo. Primero, usamos get_index() para encontrar el índice del objeto a eliminar, como se muestra en la declaración de la constante index_c a continuación.

 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; 

Luego, desenlazamos el nodo de la lista. Si es el objeto root, establecemos el siguiente elemento como root. De lo contrario, usamos get_node() para encontrar el padre y reenlazar la lista para desprender el elemento en cuestión.

Y finalmente, liberamos la memoria llamando a la palabra clave deallocate de VHDL y actualizamos la variable de contabilidad length_i.

Procedimiento Clear

Para eliminar todos los elementos, el procedimiento clear() recorre la lista usando un bucle While, llamando a delete() en cada elemento hasta que no quede ninguno.

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

Función Length

Para cumplir con buenas prácticas de programación, proporcionamos una función getter en lugar de permitir al usuario acceder directamente a la variable length_i.

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

La diferencia será imperceptible para el usuario ya que no necesita paréntesis para llamar a una función sin parámetros (my_list.length). Pero el usuario no puede cambiar la variable interna de contabilidad, y eso es una salvaguardia contra mal uso.

Uso de la lista de cadenas en un testbench

Ahora que la implementación de la lista está completa, es hora de ejecutarla en un testbench. Primero, debemos importar el tipo protegido desde un paquete, como se muestra en la primera línea del código siguiente.

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

El tipo protegido es la construcción tipo clase de VHDL, y podemos crear un objeto de él declarando una variable shared de tipo string_list, como se muestra en la última línea anterior. Lo llamaremos 'l' por "list" para replicar el ejemplo de Python que presenté al inicio de este artículo.

A partir de ahora, podemos usar un enfoque de software para acceder a los datos de la lista. Como se muestra en el proceso del testbench a continuación, podemos referenciar un subprograma público usando la notación de punto en la variable shared (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"); ... 

He omitido el testbench completo y el script de ejecución para reducir la longitud de este artículo, pero puede solicitarlo dejando su dirección de correo en el formulario a continuación. Recibirá un archivo Zip con el código VHDL completo y un proyecto ModelSim en su bandeja de entrada en pocos minutos.

Ejecución del testbench

Si descargó el proyecto de ejemplo usando el formulario anterior, debería poder replicar la siguiente salida. Consulte "How to run.txt" en el archivo Zip para instrucciones precisas.

Es un testbench de comprobación manual, y he hecho que los casos de prueba se asemejen lo más posible a mi ejemplo de Python. En lugar del método pop() de Python, usamos la función get() de la lista VHDL seguida de una llamada a delete(). Eso hace lo mismo.

Como podemos ver en la impresión en la consola de ModelSim mostrada a continuación, la lista VHDL se comporta de manera similar a su contraparte de 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 

Reflexiones finales

Creo que las características de programación de alto nivel de VHDL son infravaloradas. Aunque no son útiles para diseño RTL porque no son sintetizables, pueden ser beneficiosas para propósitos de verificación.

Aunque su implementación sea complicada, será más simple para el usuario final, la persona que escribe el testbench que usa el tipo protegido. El tipo protegido oculta toda la complejidad al usuario.

Solo se necesitan tres líneas para usar un tipo protegido: importar el paquete, declarar la variable shared, y llamar a un subprograma en el proceso del testbench. Eso es más simple que instanciar un componente VHDL.

Ver también: Cómo crear una lista enlazada en VHDL

¡Dígame qué piensa en la sección de comentarios debajo del artículo!