Criando Listas de Strings em VHDL: Boas Práticas e Exemplo

Strings de texto em VHDL geralmente são limitadas a arrays de caracteres de comprimento fixo. Isso faz sentido porque VHDL descreve hardware, e strings de comprimento genérico exigiriam memória dinâmica.

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

 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 de hardware, torna-se incômodo usar arrays de strings em testbenches VHDL. Por isso, decidi criar um pacote de lista de strings dinâmica que explicarei neste artigo.

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

A classe list do Python

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

Para mostrar o que quero dizer, entrarei direto e abrirei um shell interativo do Python para executar alguns experimentos.

Primeiro, vamos começar declarando uma lista e anexando quatro strings a ela, como 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 método append() é direto; ele anexa um objeto ao final da lista.

Podemos verificar isso com o método pop(), que remove um elemento e o retorna ao chamador. O argumento especifica a posição do elemento a recuperar. Ao dar pop no índice 0 até a lista ficar vazia, obtemos o conteúdo ordenado do menor para o maior índice:

 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 método insert() 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 função insert() 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 colchetes [] da lista Python não apaga o item; ele faz a lista se comportar como um array. Você obtém o conteúdo do slot indexado pelo número entre colchetes, como pode ver na listagem acima.

Vamos esvaziar a lista dando pop, mas desta vez do final da lista. Uma particularidade das listas 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 os métodos insert() ou pop().

Ao dar pop no índice -1, você sempre obtém o último item da lista. Quando colocamos isso em um loop For, ele esvazia a lista em ordem reversa:

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

Você pode usar índices negativos para inserir também. Na última linha do exemplo abaixo, estamos inserindo "Copenhagen" 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, vemos que "Copenhagen" 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 torna-se o penúltimo, mas ao dar pop de -1, obtemos o último item.

Faz sentido porque -1 refere-se à posição do último elemento atualmente na lista. E quando estamos dando pop, 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 em um slot.

Podemos confirmar isso dando pop no elemento -1, que retorna "Damascus", e não "Copenhagen":

 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, listas Python são versáteis, e muitos programadores as entendem. É por isso que basearei minha implementação de lista VHDL nesta fórmula de sucesso.

Os protótipos de subprogramas da lista de strings VHDL

Para nos permitir trabalhar com a lista de strings como um objeto com métodos de membro, 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 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; 

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

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

A função impura length() se comportará como a função embutida len() do Python. Ela retornará o número de strings na lista.

A implementação da lista de strings VHDL

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 dos subprogramas 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 na sua caixa de entrada!

Usaremos uma lista simplesmente encadeada como estrutura de dados interna.

Leia também: Como criar uma Lista Encadeada em VHDL

Como todo o código a seguir está no corpo do tipo protegido, esses construtos não são diretamente acessíveis 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 em memória dinâmica. Quando falamos de memória dinâmica, não é DRAM no FPGA porque este 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 isso porque na próxima linha referenciamos item ao criar item_ptr.

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

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

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

Procedimento Append

O procedimento append() 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; 

Como discutido no exemplo Python, é fácil inserir na penúltima posição usando í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 método append() dedicado, e nós teremos um também.

Procedimento Insert

O procedimento insert, mostrado abaixo, funciona em quatro passos.

Primeiro, criamos um objeto de item dinâmico usando a palavra-chave new do VHDL. Primeiro criamos um objeto de item de lista e depois 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 de índice para um índice que esteja em conformidade com o intervalo da lista. A implementação list.insert() do Python permite índices fora dos limites, e nossa lista VHDL permitirá também. Se o usuário referenciar um índice muito alto ou baixo, ele será padronizado para o índice mais alto, ou elemento 0. Além disso, usamos o operador módulo para traduzir quaisquer índices negativos dentro dos limites para uma posição de array positiva.

No passo número três, percorremos a lista para encontrar o nó após o qual inserir. Como sempre, com listas encadeadas, devemos lidar explicitamente com o caso particular de inserção na raiz.

O quarto e último passo é incrementar a variável length_i para garantir que a contabilidade esteja atualizada.

Funções internas get_index e get_node

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

Mas o algoritmo para buscar o índice ou objeto é idêntico para get() e delete(), então podemos implementá-lo separadamente em duas funções privadas: get_index() e get_node().

Diferente do insert(), a função pop() do Python não permite índices fora dos limites, e nossa função get_index() também não permitirá. Para proteger contra erro do usuário, levantaremos uma falha de asserção se o índice solicitado estiver fora dos limites, como 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; 

A função get_node(), mostrada abaixo, vai um passo além e encontra o objeto real no índice especificado. Ela usa get_index() para buscar o nó correto e retorna um ponteiro para o 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; 

Função Get

Devido à função privada get_node(), a função pública get() se torna bastante simples. É uma one-liner que busca o nó correto, desempacota 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; 

Procedimento Delete

O procedimento delete() também usa get_index() e get_node() para simplificar o algoritmo. Primeiro, usamos get_index() para encontrar o índice do objeto a remover, como mostrado na declaração da constante index_c 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; 

Então, desvinculamos o nó da lista. Se for o objeto raiz, definimos o próximo item como raiz. Caso contrário, usamos get_node() para encontrar o pai e relinkar a lista para desanexar o item em questão.

E finalmente, liberamos a memória chamando a palavra-chave VHDL deallocate e atualizamos a variável de contabilidade length_i.

Procedimento Clear

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

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

Função Length

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

 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 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, como 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 é o construto semelhante a 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 chamá-lo de 'l' para "list" 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. Como mostrado no processo do 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"); ... 

Omiti o testbench completo e o script de execução 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 na sua caixa de entrada em minutos.

Executando o testbench

Se você baixou o projeto de exemplo usando o formulário acima, deve ser capaz de replicar a saída a seguir. Consulte "How to run.txt" no arquivo Zip para instruções precisas.

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

Como podemos ver na impressão no console do ModelSim mostrada abaixo, a lista VHDL se comporta de forma 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 sejam úteis para projeto RTL porque não são sintetizáveis, podem ser benéficos para fins de verificação.

Mesmo que possa ser complicado 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.

Leva apenas três linhas para usar um tipo protegido: importar o pacote, declarar a variável compartilhada e chamar um subprograma no processo do testbench. Isso é mais simples do que instanciar um componente VHDL.

Veja também: Como criar uma Lista Encadeada em VHDL

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