Cómo crear una lista de cadenas en VHDL

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

Para definir una matriz de cadenas, debe asignar espacio en tiempo de compilación para la mayor cantidad de cadenas que desea almacenar. Y lo que es peor, debe decidir la longitud máxima de las cadenas y rellenar cada ocurrencia con esa cantidad de caracteres. El siguiente código 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  ";

Si bien eso tiene sentido desde la perspectiva del hardware, se vuelve engorroso usar arreglos de cadenas en los bancos de pruebas de VHDL. Por lo tanto, decidí crear un paquete de lista de cadenas dinámicas que explicaré en este artículo.

Puedes descargar el código completo utilizando el siguiente formulario.

Clase de lista de Python

Modelemos nuestra lista VHDL dinámica después de una implementación de lista conocida. Nuestra lista de cadenas VHDL imitará el comportamiento de la clase de lista integrada de Python. Adoptaremos el append() , insertar() y pop() métodos de la lista de Python.

Para mostrarle lo que quiero decir, entraré directamente y abriré un shell de python interactivo para ejecutar algunos experimentos.

Primero, comencemos por declarar una lista y agregarle 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 añadir() el método es sencillo; agrega un objeto al final de la lista.

Podemos verificar eso con el pop() método, que elimina un elemento y lo devuelve a la persona que llama. El argumento especifica la posición del elemento a recuperar. Al mostrar 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, rellenemos la lista. Y esta vez, usaremos insert() método para agregar los elementos de la lista 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")

El insertar() La función le permite especificar en qué índice insertar el nuevo elemento. En el ejemplo anterior, creamos la misma lista que antes. Comprobemos eso recorriendo la lista como una matriz:

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

El operador de lista de corchetes [] de Python no elimina el elemento; hace que una lista se comporte como una matriz. Obtiene el contenido de la ranura indexado por el número entre paréntesis, como puede ver en la lista anterior.

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

Al abrir el índice -1, siempre obtiene el último elemento de la lista. Cuando 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 puede usar índices negativos para insertar. En la última línea del siguiente ejemplo, estamos insertando "Copenhague" 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") # insert at the second last position

Cuando recorremos la lista, podemos ver que "Copenhague" es ahora el penúltimo elemento:

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

Ahora, aquí viene el quid (pero tiene sentido).

Al insertar a -1, el nuevo elemento se convierte en el penúltimo, pero al saltar 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 estallar, estamos pidiendo el último elemento. Pero cuando estamos insertando, pedimos insertar el nuevo elemento en la posición del último elemento actualmente en la lista. Por lo tanto, el nuevo elemento desplaza al elemento final en un espacio.

Podemos confirmar esto haciendo estallar el elemento -1, que devuelve "Damasco" y no "Copenhague":

In [18]: l.pop(-1) # pop from the last position
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 de esta manera:

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. Es por eso que basaré la implementación de mi lista VHDL en esta fórmula de éxito.

La lista de cadenas de prototipos de subprogramas VHDL

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

El siguiente código muestra la parte "pública" del tipo protegido que enumera 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 append() , insertar() y borrar() los procedimientos son idénticos a sus contrapartes de Python, no podemos portar el pop() función directamente a VHDL. El problema es que no podemos pasar fácilmente objetos dinámicos fuera de los tipos protegidos en VHDL.

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

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

Implementación VHDL de la lista de cadenas

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 del subprograma y cualquier variable privada. Ahora es el momento de revelar el funcionamiento interno de la lista de cadenas.

¡Deje su dirección de correo electrónico en el siguiente formulario para recibir el código completo y el proyecto ModelSim en su bandeja de entrada!

Usaremos una lista enlazada individualmente como estructura de datos interna.

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

Debido a que todo el código que sigue está en el cuerpo del tipo protegido, no se puede acceder directamente a estas construcciones fuera de este paquete. Toda comunicación debe pasar por los subprogramas enumerados en la región declarativa que discutimos en la sección anterior.

Tipos de almacenamiento de datos y variables

Como puede ver en el código siguiente, primero declaramos un tipo de acceso, un puntero VHDL a una cadena en la memoria dinámica. Cuando hablamos de memoria dinámica, no es DRAM en la FPGA porque este código no se puede sintetizar. La lista de cadenas es puramente un componente de simulación y utilizará la memoria dinámica de la computadora 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 un tipo incompleto. Tenemos que hacerlo así porque en la siguiente línea, hacemos referencia a item al crear item_ptr .

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

El tipo protegido contiene dos variables, que se muestran a continuación:raíz y longitud_i . El elemento apuntado por root será el primer elemento de la lista, matriz índice cero. Y la longitud_i La variable siempre reflejará el número de cadenas en la lista.

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

Anexar procedimiento

El añadir() El procedimiento que se muestra 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 el í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 append() dedicado método, y tendremos uno también.

Insertar procedimiento

El procedimiento de inserción, que se muestra a continuación, funciona en cuatro pasos.

Primero, creamos un objeto de elemento dinámico usando el VHDL nuevo palabra clave. Primero creamos un objeto de elemento de lista y luego un objeto de cadena dinámica para almacenarlo.

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;

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

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

El cuarto y último paso es incrementar la longitud_i variable para asegurar que la contabilidad esté al día.

Funciones internas get_index y get_node

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

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

A diferencia de insertar() , pop() de Python La función no permite índices fuera de los límites, y tampoco lo hará nuestro get_index() función. Para evitar errores del usuario, generaremos un error de aserción si el índice solicitado está fuera de los límites, 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;

El get_node() La función, que se muestra a continuación, va un paso más allá y encuentra el objeto real en el índice especificado. Utiliza get_index() para buscar el nodo correcto y devuelve un puntero al elemento objeto.

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;

Obtener función

Debido al get_node() privado la función pública get() función se vuelve bastante simple. Es una sola línea que obtiene el nodo correcto, desempaqueta el contenido de la cadena y se lo devuelve a la persona que llama.

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

Borrar procedimiento

El eliminar() el procedimiento 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 el index_c declaración constante 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, desvinculamos el nodo de la lista. Si es el objeto raíz, establecemos el siguiente elemento como raíz. De lo contrario, usamos get_node() para encontrar el padre y volver a vincular la lista para separar el elemento en cuestión.

Y finalmente, liberamos la memoria llamando a la palabra clave VHDL desasignar y actualice la longitud_i variable contable.

Procedimiento claro

Para eliminar todos los elementos, clear() El procedimiento recorre la lista usando un ciclo 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 de longitud

Para cumplir con las buenas prácticas de programación, proporcionamos una función getter en lugar de permitir que el usuario acceda directamente a length_i variables.

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 de contabilidad interna, y eso es una protección contra el mal uso.

Uso de la lista de cadenas en un banco de pruebas

Ahora que la implementación de la lista está completa, es hora de que la ejecutemos en un banco de pruebas. Primero, tenemos que importar el tipo protegido desde un paquete, como se muestra en la primera línea del código a continuación.

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 una construcción similar a una clase de VHDL, y podemos crear un objeto declarando una variable compartida de tipo string_list , como se muestra en la última línea de arriba. Lo llamaremos 'l' por "lista" para replicar el ejemplo de Python que presenté al comienzo de este artículo.

A partir de ahora, podemos utilizar un enfoque de software para acceder a los datos de la lista. Como se muestra en el proceso del banco de pruebas a continuación, podemos hacer referencia a un subprograma público usando la notación de puntos en la variable compartida (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 banco de pruebas completo y el script de ejecución para reducir la longitud de este artículo, pero puede solicitarlo dejando su dirección de correo electrónico 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 cuestión de minutos.

Ejecutar el banco de pruebas

Si descargó el proyecto de ejemplo utilizando el formulario anterior, debería poder replicar el siguiente resultado. Consulte "Cómo ejecutar.txt" en el archivo Zip para obtener instrucciones precisas.

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

Como podemos ver en la impresión de la consola ModelSim que se muestra 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 funciones de programación de alto nivel de VHDL están subestimadas. Si bien no es útil para el diseño RTL porque no es sintetizable, puede ser beneficioso para fines de verificación.

Aunque puede ser complicado de implementar, será más simple para el usuario final, la persona que escribe el banco de pruebas que usa el tipo protegido. El tipo protegido oculta toda la complejidad del usuario.

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

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

¡Dime lo que piensas en la sección de comentarios debajo del artículo!