Como criar uma lista de strings em VHDL

As cadeias de texto em VHDL geralmente são limitadas a matrizes de caracteres de comprimento fixo. Isso faz sentido porque o VHDL descreve o hardware e as strings de comprimento genérico requerem memória dinâmica.

Para definir um array de strings, você precisa alocar espaço em tempo de compilação para o maior número de strings que deseja armazenar. E ainda pior, você deve decidir sobre o comprimento máximo das strings e preencher cada ocorrência para esse número de caracteres. O código abaixo mostra um exemplo de uso de tal construção.

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

Embora isso faça sentido do ponto de vista do hardware, torna-se complicado usar arrays de strings em testbenches VHDL. Por isso, decidi criar um pacote de lista de strings dinâmicas que explicarei neste artigo.

Você pode baixar o código completo usando o formulário abaixo.

Classe de lista do Python

Vamos modelar nossa lista VHDL dinâmica após uma implementação de lista bem conhecida. Nossa lista de strings VHDL imitará o comportamento da classe de lista interna do Python. Vamos adotar o append() , inserir() e pop() métodos da lista Python.

Para mostrar o que quero dizer, vou entrar e abrir um shell python interativo para executar alguns experimentos.

Primeiro, vamos começar declarando uma lista e anexando quatro strings a ela, conforme mostrado abaixo.

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

O anexar() método é direto; ele anexa um objeto ao final da lista.

Podemos verificar isso com o pop() método, que remove um elemento e o retorna ao chamador. O argumento especifica a posição do elemento a ser recuperado. Colocando 0 até que a lista fique vazia, obtemos o conteúdo ordenado do índice mais baixo para o mais alto:

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

OK, vamos reabastecer a lista. E desta vez, usaremos o insert() método para adicionar os elementos da lista fora de ordem:

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

A inserir() A função permite especificar em qual índice inserir o novo item. No exemplo acima, criamos a mesma lista de antes. Vamos verificar isso percorrendo a lista como um array:

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

O operador de lista de colchetes [] do Python não exclui o item; faz uma lista se comportar como um array. Você obtém o conteúdo do slot indexado pelo número entre colchetes, como você pode ver na lista acima.

Vamos esvaziar a lista aparecendo, mas desta vez a partir do final da lista. Uma peculiaridade das listas do Python é que você pode usar um índice negativo para contar a partir do último item em vez do início da lista. Funciona com o operador de colchetes e com o insert() ou pop() métodos.

Ao exibir o índice -1, você sempre obtém o último item da lista. Quando colocamos isso em um loop For, ele esvaziará a lista na ordem inversa:

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

Você também pode usar índices negativos para inserir. Na última linha do exemplo abaixo, estamos inserindo “Copenhague” no í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

Quando percorremos a lista, podemos ver que “Copenhague” é agora o penúltimo elemento:

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

Agora, aqui vem o ponto crucial (mas faz sentido).

Ao inserir em -1, o novo item se torna o penúltimo, mas ao sair de -1, obtemos o último item.

Faz sentido porque -1 se refere à posição do último elemento atualmente na lista. E quando estamos estourando, estamos pedindo o último elemento. Mas quando estamos inserindo, pedimos para inserir o novo item na posição do último elemento atualmente na lista. Assim, o novo item desloca o elemento final por um slot.

Podemos confirmar isso destacando o elemento -1, que retorna “Damasco” e não “Copenhague”:

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

A lista agora contém três elementos:

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

Também é possível contar o comprimento da lista assim:

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

E podemos esvaziar a lista chamando clear() :

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

Como você pode ver, as listas do Python são versáteis e muitos programadores as entendem. É por isso que vou basear minha implementação da lista VHDL nesta fórmula de sucesso.

Os protótipos de subprogramas VHDL da lista de strings

Para nos permitir trabalhar com a lista de strings como um objeto com métodos membros, devemos declará-la como um tipo protegido. E colocaremos o tipo protegido em um pacote com o mesmo nome:string_list .

O código abaixo mostra a parte “pública” do tipo protegido listando os protótipos do subprograma.

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;

Enquanto o append() , inserir() , e clear() procedimentos são idênticos aos seus equivalentes em Python, não podemos portar o pop() função diretamente para VHDL. O problema é que não podemos passar facilmente objetos dinâmicos de tipos protegidos em VHDL.

Para superar essa limitação, dividi o pop() funcionalidade em dois subprogramas:get() e excluir() . Isso nos permitirá indexar o elemento primeiro, como um array, e depois excluí-lo quando não precisarmos mais dele. Por exemplo, depois de imprimirmos a string no console do simulador.

O comprimento() A função impura se comportará como o len() embutido do Python função. Ele retornará o número de strings na lista.

A implementação do VHDL da lista de strings

Os tipos protegidos consistem em duas seções:a parte declarativa e o corpo. Enquanto a parte declarativa é visível para o usuário, o corpo contém as implementações do subprograma e quaisquer variáveis ​​privadas. Agora é hora de revelar o funcionamento interno da lista de strings.

Deixe seu endereço de e-mail no formulário abaixo para receber o código completo e o projeto ModelSim em sua caixa de entrada!





Usaremos uma lista vinculada individualmente como estrutura de dados interna.

Leia também:Como criar uma lista vinculada em VHDL

Como todo o código a seguir está no corpo do tipo protegido, essas construções não podem ser acessadas diretamente fora deste pacote. Toda comunicação deve passar pelos subprogramas listados na região declarativa que discutimos na seção anterior.

Tipos e variáveis ​​de armazenamento de dados

Como você pode ver no código abaixo, primeiro declaramos um tipo de acesso, um ponteiro VHDL para uma string na memória dinâmica. Quando falamos de memória dinâmica, não é DRAM no FPGA porque esse código não é sintetizável. A lista de strings é puramente um componente de simulação e usará a memória dinâmica do computador que executa a simulação.

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;

Após str_ptr , declaramos item como um tipo incompleto. Temos que fazer assim porque na próxima linha, referenciamos item ao criar item_ptr .

E, finalmente, especificamos a declaração completa do item type, um registro contendo um ponteiro de string e um ponteiro para o próximo elemento. Existe uma dependência circular entre os tipos item->item_ptr->item , e declarando primeiro o item incompleto type, evitamos um erro de compilação.

O tipo protegido contém duas variáveis, mostradas abaixo:root e comprimento_i . O item apontado por root será o primeiro elemento da lista, índice do array zero. E o comprimento_i variável sempre refletirá o número de strings na lista.

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

Anexar procedimento

O anexar() O procedimento mostrado abaixo é uma notação abreviada para inserir uma string na última posição da lista.

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

Conforme discutido no exemplo do Python, é fácil inserir na penúltima posição usando o índice -1:insert(-1, str) . Mas inserir na última posição requer o comprimento da lista como argumento de índice. Provavelmente é por isso que a lista do Python tem um append() dedicado método, e teremos um também.

Inserir procedimento

O procedimento de inserção, mostrado abaixo, funciona em quatro etapas.

Primeiro, criamos um objeto de item dinâmico usando o VHDL new palavra-chave. Primeiro criamos um objeto de item de lista e, em seguida, um objeto de string dinâmico para armazenar nele.

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;

O passo número dois é traduzir o argumento do índice para um índice que esteja de acordo com o intervalo da lista. list.insert() do Python implementação permite índices fora dos limites, e nossa lista VHDL também permitirá. Se o usuário fizer referência a um índice muito alto ou baixo, o padrão será o índice mais alto, ou elemento 0. Além disso, usamos o operador de módulo para traduzir quaisquer índices negativos dentro dos limites para uma posição positiva do array.

Na etapa número três, percorremos a lista para encontrar o nó a ser inserido depois. Como sempre, com listas vinculadas, devemos lidar explicitamente com o caso específico de inserção na raiz.

A quarta e última etapa é incrementar o length_i variável para garantir que a escrituração esteja em dia.

Funções get_index e get_node internas

Devido às limitações de passagem de objetos do VHDL, decidimos dividir pop() em dois subprogramas:get() e excluir() . A primeira função obterá o item e o segundo procedimento o removerá da lista.

Mas o algoritmo para procurar o índice ou objeto é idêntico para get() e excluir() , para que possamos implementá-lo separadamente em duas funções privadas:get_index() e get_node() .

Ao contrário de inserir() , pop() do Python A função não permite índices fora dos limites, nem nosso get_index() função. Para evitar erros do usuário, geraremos uma falha de asserção se o índice solicitado estiver fora dos limites, conforme mostrado abaixo.

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;

O get_node() A função, mostrada abaixo, leva um passo adiante e encontra o objeto real no índice especificado. Ele usa get_index() para procurar o nó correto e retorna um ponteiro para o item 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;

Obter função

Por causa do get_node() privado função, a função pública get() função torna-se bastante simples. É um one-liner que busca o nó correto, descompacta o conteúdo da string e o retorna ao chamador.

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

Excluir procedimento

O excluir() procedimento também usa get_index() e get_node() para simplificar o algoritmo. Primeiro, usamos get_index() para encontrar o índice do objeto a ser removido, conforme mostrado no index_c declaração constante abaixo.

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;

Em seguida, desvinculamos o nó da lista. Se for o objeto root, definimos o próximo item como root. Caso contrário, usamos get_node() para encontrar o pai e revincular a lista para desanexar o item em mãos.

E, finalmente, liberamos a memória chamando a palavra-chave VHDL deallocate e atualize o length_i variável de escrituração.

Limpar procedimento

Para excluir todos os itens, o clear() procedimento percorre a lista usando um loop While, chamando delete() em cada elemento até não sobrar nenhum.

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

Função de comprimento

Para cumprir as boas práticas de programação, fornecemos uma função getter em vez de permitir que o usuário acesse diretamente o length_i variável.

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

A diferença será imperceptível para o usuário, pois você não precisa de parênteses para chamar uma função sem parâmetros (my_list.length ). Mas o usuário não pode alterar a variável de contabilidade interna, e isso é uma proteção contra o uso indevido.

Usando a lista de strings em um testbench

Agora que a implementação da lista está completa, é hora de executá-la em um testbench. Primeiro, temos que importar o tipo protegido de um pacote, conforme mostrado na primeira linha do código abaixo.

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

O tipo protegido são as construções do tipo classe do VHDL, e podemos criar um objeto dele declarando uma variável compartilhada do tipo string_list , como mostrado na última linha acima. Vamos nomeá-lo 'l' para "lista" para replicar o exemplo Python que apresentei no início deste artigo.

A partir de agora, podemos usar uma abordagem de software para acessar os dados da lista. Conforme mostrado no processo testbench abaixo, podemos referenciar um subprograma público usando a notação de ponto na variável compartilhada (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");
...

Eu omiti o testbench completo e executei o script para reduzir o tamanho deste artigo, mas você pode solicitá-lo deixando seu endereço de e-mail no formulário abaixo. Você receberá um arquivo Zip com o código VHDL completo e um projeto ModelSim em sua caixa de entrada em poucos minutos.

Executando o testbench

Se você baixou o projeto de exemplo usando o formulário acima, poderá replicar a saída a seguir. Consulte “Como executar.txt” no arquivo Zip para obter instruções precisas.

É um testbench de verificação manual e fiz os casos de teste se assemelharem ao meu exemplo Python o mais próximo possível. Em vez do pop() Python, usamos o método get() da lista VHDL função seguida por uma chamada para delete() . Isso faz a mesma coisa.

Como podemos ver na impressão do console ModelSim mostrado abaixo, a lista VHDL se comporta de maneira semelhante à sua contraparte 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

Considerações finais

Acho que os recursos de programação de alto nível do VHDL são subestimados. Embora não seja útil para o design RTL porque não é sintetizável, pode ser benéfico para fins de verificação.

Embora possa ser complicado de implementar, será mais simples para o usuário final, a pessoa que escreve o testbench que usa o tipo protegido. O tipo protegido esconde toda a complexidade do usuário.

São necessárias apenas três linhas para usar um tipo protegido:importe o pacote, declare a variável compartilhada e chame um subprograma no processo testbench. Isso é mais simples do que instanciar um componente VHDL.

Veja também:Como criar uma lista vinculada em VHDL

Diga-me o que você pensa na seção de comentários abaixo do artigo!