Создание списков строк в VHDL: лучшие практики и пример

Текстовые строки в VHDL обычно ограничены массивами символов фиксированной длины. Это логично, ведь VHDL описывает аппаратное обеспечение, а строки произвольной длины требуют динамической памяти.

Для определения массива строк нужно выделить место на этапе компиляции под максимальное количество строк. Что еще хуже, нужно заранее решить на максимальную длину строки и дополнять каждую строку до этого количества символов. Код ниже показывает пример такого подхода.

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

Хотя с аппаратной точки зрения это оправдано, использование массивов строк в VHDL-тестбенчах становится громоздким. Поэтому я решил создать пакет динамического списка строк, который объясню в этой статье.

Полный код можно скачать через форму ниже.

Класс list в Python

Давайте смоделируем наш динамический VHDL-список на основе известной реализации. Наш VHDL-список строк будет имитировать поведение встроенного класса list в Python. Мы переняем методы append(), insert() и pop() из списка Python.

Чтобы показать, что я имею в виду, сразу открою интерактивную оболочку Python и запущу несколько экспериментов.

Сначала объявим список и добавим четыре строки с помощью append():

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

Метод append() прост: он добавляет объект в конец списка.

Проверим это методом pop(), который удаляет элемент и возвращает его. Аргумент указывает позицию элемента. Извлекая элементы с индексом 0 до опустошения списка, получаем содержимое от низшего к высшему индексу:

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

Хорошо, наполним список снова. На этот раз используем insert() для добавления элементов в произвольном порядке:

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

Функция insert() позволяет указать индекс для вставки. В примере выше мы создали тот же список. Проверим, обходя список как массив:

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

Оператор скобок [] не удаляет элемент; он делает список похожим на массив. Вы получаете содержимое слота по индексу в скобках.

Опустошим список, извлекая элементы с конца. Особенность Python: можно использовать отрицательный индекс для отсчета от последнего элемента. Это работает и с оператором [], и с методами insert() или pop().

Извлекая индекс -1, всегда получаем последний элемент. В цикле это опустошает список в обратном порядке:

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

Отрицательные индексы можно использовать и для вставки. В последней строке примера ниже вставляем "Copenhagen" в индекс -1:

 In [13]: l.append("Amsterdam") In [14]: l.append("Bangkok") In [15]: l.append("Damascus") In [16]: l.insert(-1, "Copenhagen") # вставка на позицию перед последней 

При обходе списка видно, что "Copenhagen" теперь предпоследний элемент:

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

Теперь главное (но это логично).

При вставке в -1 новый элемент становится предпоследним, а при извлечении из -1 мы получаем последний элемент.

Это логично, потому что -1 ссылается на позицию текущего последнего элемента. При извлечении мы просим последний элемент. При вставке мы просим вставить новый элемент на позицию текущего последнего элемента. Таким образом, новый элемент сдвигает последний на один слот.

Подтвердим это, извлекая элемент -1, который вернет "Damascus", а не "Copenhagen":

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

Теперь список содержит три элемента:

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

Также можно получить длину списка:

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

И очистить список вызовом clear():

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

Как видите, списки Python универсальны и понятны многим программистам. Поэтому я буду строить свою VHDL-реализацию на этой успешной формуле.

Прототипы подпрограмм VHDL-списка строк

Чтобы работать со списком строк как с объектом с методами-членами, нужно объявить его как защищенный тип (protected type). И поместим его в пакет с тем же именем: string_list.

Код ниже показывает «публичную» часть защищенного типа со списком прототипов подпрограмм.

 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; 

Пока процедуры append(), insert() и clear() идентичны своим аналогам в Python, функцию pop() нельзя напрямую перенести в VHDL. Проблема в том, что динамические объекты нельзя легко возвращать из защищенных типов в VHDL.

Чтобы обойти это ограничение, я разделил функциональность pop() на две подпрограммы: get() и delete(). Это позволит сначала проиндексировать элемент как в массиве, а затем удалить его, когда он больше не нужен. Например, после вывода строки в консоль симулятора.

Нечистая функция length() будет вести себя как встроенная в Python функция len(). Она вернет количество строк в списке.

Реализация VHDL-списка строк

Защищенные типы состоят из двух разделов: декларативной части и тела. Декларативная часть видна пользователю, а тело содержит реализации подпрограмм и приватные переменные. Пришло время раскрыть внутреннюю кухню списка строк.

Оставьте свой email в форме ниже, чтобы получить полный код и проект ModelSim на почту!

Мы будем использовать односвязный список в качестве внутренней структуры данных.

Читайте также: Как создать связанный список в VHDL

Весь следующий код находится в теле защищенного типа, поэтому эти конструкции не доступны напрямую извне пакета. Вся коммуникация должна проходить через подпрограммы, перечисленные в декларативной области, которую мы обсуждали в предыдущем разделе.

Типы и переменные хранения данных

Как видите из кода ниже, сначала объявляется тип доступа — указатель VHDL на строку в динамической памяти. Когда мы говорим о динамической памяти, это не DRAM на FPGA, потому что этот код не синтезируем. Список строк — чисто симуляционный компонент, он использует динамическую память компьютера, на котором запущена симуляция.

 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; 

После str_ptr мы объявляем item как неполный тип. Это нужно, потому что на следующей строке мы ссылаемся на item при создании item_ptr.

И наконец, задаем полное объявление типа item — запись, содержащая указатель на строку и указатель на следующий элемент. Существует циклическая зависимость между типами item->item_ptr->item, и предварительное объявление неполного типа item позволяет избежать ошибки компиляции.

Защищенный тип содержит две переменные, показанные ниже: root и length_i. Элемент, на который указывает root, будет первым элементом списка (индекс массива 0). А переменная length_i всегда отражает количество строк в списке.

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

Процедура Append

Процедура append(), показанная ниже, является сокращенной записью для вставки строки в последнюю позицию списка.

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

Как обсуждалось в примере на Python, легко вставить на предпоследнюю позицию с индексом -1: insert(-1, str). Но вставка в последнюю позицию требует длины списка как аргумента индекса. Вероятно, поэтому в списке Python есть выделенный метод append(), и у нас тоже будет один.

Процедура Insert

Процедура insert, показанная ниже, работает в четыре этапа.

Сначала мы создаем динамический объект item с помощью ключевого слова VHDL new. Сначала создаем объект элемента списка, затем динамический строковый объект для хранения в нем.

 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; 

Второй шаг — преобразовать аргумент индекса в индекс, соответствующий диапазону списка. Реализация list.insert() в Python допускает индексы за пределами границ, и наш VHDL-список тоже это позволит. Если пользователь ссылается на слишком высокий или низкий индекс, он будет приведен к максимальному индексу или к элементу 0. Также используем оператор модуля для преобразования любых отрицательных индексов в допустимых границах в положительную позицию массива.

На третьем шаге мы проходим по списку, чтобы найти узел, после которого нужно вставить. Как всегда со связанными списками, нужно явно обрабатывать особый случай вставки в корень.

Четвертый и последний шаг — увеличить переменную length_i, чтобы бухгалтерия оставалась актуальной.

Внутренние функции get_index и get_node

Из-за ограничений VHDL на передачу объектов мы решили разделить pop() на две подпрограммы: get() и delete(). Первая функция получит элемент, вторая процедура удалит его из списка.

Но алгоритм поиска индекса или объекта идентичен для get() и delete(), поэтому мы можем реализовать его отдельно в двух приватных функциях: get_index() и get_node().

В отличие от insert(), функция pop() в Python не допускает индексы за пределами границ, и наша функция get_index() тоже не будет. Для защиты от ошибок пользователя мы вызовем сбой утверждения (assertion failure), если запрошенный индекс выходит за границы, как показано ниже.

 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; 

Функция get_node(), показанная ниже, идет дальше и находит сам объект по указанному индексу. Она использует get_index() для поиска правильного узла и возвращает указатель на объект 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; 

Функция Get

Благодаря приватной функции get_node(), публичная функция get() становится довольно простой. Это однострочник, который извлекает правильный узел, распаковывает строковое содержимое и возвращает его вызывающему.

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

Процедура Delete

Процедура delete() также использует get_index() и get_node() для упрощения алгоритма. Сначала используем get_index() для поиска индекса удаляемого объекта, как показано в объявлении константы index_c ниже.

 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; 

Затем мы исключаем узел из списка. Если это корневой объект, устанавливаем следующий элемент как корень. Иначе используем get_node() для поиска родителя и пересвязываем список, отсоединяя нужный элемент.

И наконец, освобождаем память вызовом ключевого слова VHDL deallocate и обновляем бухгалтерскую переменную length_i.

Процедура Clear

Для удаления всех элементов процедура clear() обходит список с помощью цикла While, вызывая delete() для каждого элемента, пока список не станет пустым.

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

Функция Length

Соблюдая хорошую практику программирования, мы предоставляем функцию-геттер вместо прямого доступа к переменной length_i.

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

Разница для пользователя незаметна, так как для вызова функции без параметров скобки не нужны (my_list.length). Но пользователь не может изменить внутреннюю бухгалтерскую переменную, что является защитой от неправильного использования.

Использование списка строк в тестбенче

Теперь, когда реализация списка завершена, пора запустить его в тестбенче. Сначала нужно импортировать защищенный тип из пакета, как показано в первой строке кода ниже.

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

Защищенный тип — это классоподобные конструкции VHDL, и мы можем создать его объект, объявив общую переменную (shared variable) типа string_list, как показано в последней строке выше. Назовем её 'l' для «list», чтобы воспроизвести пример на Python из начала статьи.

Отныне мы можем использовать программный подход для доступа к данным списка. Как показано в процессе тестбенча ниже, мы можем обращаться к публичной подпрограмме, используя точечную нотацию над общей переменной (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"); ... 

Я опустил полный тестбенч и скрипт запуска, чтобы сократить длину статьи, но вы можете запросить его, оставив свой email в форме ниже. Вы получите ZIP-файл с полным VHDL-кодом и проектом ModelSim в почте через несколько минут.

Запуск тестбенча

Если вы скачали пример проекта через форму выше, вы сможете воспроизвести следующий вывод. Обратитесь к «How to run.txt» в ZIP-файле для точных инструкций.

Это тестбенч с ручной проверкой, и я сделал тест-кейсы максимально похожими на мой пример на Python. Вместо метода pop() Python мы используем функцию get() VHDL-списка, за которой следует вызов delete(). Это делает то же самое.

Как видно из вывода в консоль ModelSim, показанного ниже, VHDL-список ведет себя аналогично своему 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 

Заключительные мысли

Я думаю, что высокоуровневые программные возможности VHDL недооценены. Хотя они бесполезны для RTL-проектирования, потому что не синтезируемы, они могут быть полезны для верификации.

Даже если реализация может быть сложной, для конечного пользователя — человека, пишущего тестбенч, использующий защищенный тип — это будет проще. Защищенный тип скрывает всю сложность от пользователя.

Для использования защищенного типа нужно всего три строки: импортировать пакет, объявить общую переменную и вызвать подпрограмму в процессе тестбенча. Это проще, чем инстанцировать VHDL-компонент.

Смотрите также: Как создать связанный список в VHDL

Делитесь своими мыслями в комментариях ниже статьи!