Как создать список строк в 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 становится громоздким. Поэтому я решил создать пакет динамического списка строк, который я объясню в этой статье.

Вы можете загрузить полный код, используя форму ниже.

Класс списка Python

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

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

Во-первых, давайте начнем с объявления списка и добавления к нему четырех строк, как показано ниже.

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

добавить() метод прост; он добавляет объект в конец списка.

Мы можем проверить это с помощью 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 скобка [] не удаляет элемент; он заставляет список вести себя как массив. Вы получаете содержимое слота, проиндексированное номером в скобках, как видно из приведенного выше списка.

Давайте очистим список, выталкивая, но на этот раз с конца списка. Особенность списков Python заключается в том, что вы можете использовать отрицательный индекс для подсчета с последнего элемента, а не с начала списка. Он работает с оператором квадратных скобок и с insert(). или поп() методы.

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

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

Вы также можете использовать отрицательные индексы для вставки. В последней строке примера ниже мы вставляем «Копенгаген» с индексом -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

Когда мы проходим по списку, мы видим, что «Копенгаген» теперь предпоследний элемент:

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

Теперь самое главное (но в этом есть смысл).

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

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

Мы можем подтвердить это, вытащив элемент -1, который вернет «Дамаск», а не «Копенгаген»:

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

Чтобы мы могли работать со списком строк, как с объектом с методами-членами, мы должны объявить его как защищенный тип. И поместим защищенный тип в пакет с таким же именем: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() , вставить() и очистить() процедуры идентичны своим аналогам Python, мы не можем портировать pop() работать непосредственно с VHDL. Проблема в том, что мы не можем легко передавать динамические объекты из защищенных типов в VHDL.

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

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

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

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

Оставьте свой адрес электронной почты в форме ниже, чтобы получить полный код и проект 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 будет первым элементом списка, нулевой индекс массива. И length_i всегда будет отражать количество строк в списке.

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

Процедура добавления

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

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

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

Вставить процедуру

Процедура вставки, показанная ниже, состоит из четырех шагов.

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

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;

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

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

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

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

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

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

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

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() для поиска правильного узла и возвращает указатель на элемент объект.

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

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

Процедура удаления

удалить() процедура также использует 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() Процедура проходит по списку, используя цикл While, вызывая delete() на каждый элемент, пока не останется ни одного.

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

Функция длины

В соответствии с передовой практикой программирования мы предоставляем функцию получения, а не позволяем пользователю напрямую обращаться к 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, и мы можем создать его объект, объявив общую переменную типа string_list. , как показано в последней строке выше. Мы назовем его «l» для «списка», чтобы воспроизвести пример 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");
...

Я опустил полный тестовый стенд и сценарий запуска, чтобы сократить объем этой статьи, но вы можете запросить его, оставив свой адрес электронной почты в форме ниже. Вы получите Zip-файл с полным кодом VHDL и проектом ModelSim на свой почтовый ящик в течение нескольких минут.

Запуск тестового стенда

Если вы загрузили пример проекта, используя приведенную выше форму, вы сможете воспроизвести следующий вывод. Точные инструкции см. в разделе «Как запустить.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

Расскажите мне, что вы думаете, в разделе комментариев под статьей!