VHDL для начинающих. Brainfuck

Как известно, VHDL – высокоуровневый язык описания аппаратуры (если это вызывает сомнения, можно посмотреть здесь и здесь). Из всего разнообразия задач мне приглянулся именно brainfuck благодаря лёгкости в реализации с одной стороны и волшебству создания программируемого (пусть и весьма ограниченно) вычислителя с другой.
В рамках данной статьи я не буду углубляться в дебри синтаксиса и настройки среды, сконцентрировавшись на реализации конкретной задачи.
Испытательным стендом будет Altera Cyclone II Starter Kit (EP2C20F484C7)


Любителей мигающих лампочек прошу под кат.

Техническое задание

1. Память команд — 64 команды, ячейки памяти — 32 ячейки по 8 бит каждая;
2. Устройство должно поддерживать два режима: занесения программы и выполнения; смена режима должна осуществляться при помощи переключателя SW9;
3. В режиме занесения программы переключатели SW8 – SW3 определяют адрес в памяти программ, SW2 – SW0 — код команды; запись в память осуществлятся при нажатии кнопки KEY3; содержимое текущей ячейки памяти отображается на свтодиодах LEDR2 – LEDR0;
4. В режиме выполнения программы значения ячеек памяти должны отображаться на семисегментных индикаторах HEX1 – HEX0; адрес отображаемой ячейки должен задаваться при помощи переключателей SW4 – SW0;
5. В любом режиме работы по нажатию кнопки KEY3 значения всех ячеек памяти должны обнуляться.

Разметка фронта работ

Проект в Quartus II создан, самое время определиться с набором entity. Я решил не выделяться и, пусть это и не очень красиво, реализовать всё в одной сущности. Для вывода на семисегментные индикаторы понадобится специальный дешифратор, который выделим в отдельный entity.

Реализация

Дешифратор можно реализовать сразу, «в лоб». Он выполняет простейшее преобразование, задаваемое таблично, поэтому портов всего два:

entity dc7x is
	port(
		i: in std_logic_vector(3 downto 0);
		z: out std_logic_vector(6 downto 0)
		);
end dc7x;

Модель поведения задаётся просто:

with i select
		z <= "1000000" when "0000", --0
			  "1111001" when "0001", --1
			  "0100100" when "0010", --2
			  "0110000" when "0011", --3
			  "0011001" when "0100", 
			   ********
			  "0001110" when "1111", --F
			  "0111111" when others;

Перейдём непосредственно к интерпретатору.

Порты

Задействованные внешние устройства ввода и вывода показаны на рисунке:

Как видно, нужен доступ к тумблерам SW, кнопкам KEY, светодиодам LED и семисегментникам HEX. Сигнал синхронизации будет вырабатывать внутренний генератор 50Mhz.

entity brainfuck is
	port(
		RUN: in std_logic;
		SW: 	in std_logic_vector(8 downto 0);
		LED:	out std_logic_vector(2 downto 0);
		HEX1:	out std_logic_vector(6 downto 0);
		HEX2:	out std_logic_vector(6 downto 0);
		clk: in std_logic;
		RESET: in boolean
		);
end brainfuck;

RUN — тот самый переключатель режима работы SW9, RESET — кнопка KEY3.

Архитектура

Нам понадобится несколько внутренних элементов: массивы памяти команд и данных, а также указатели на конкретные ячейки в них.
Так как на индикаторах требуется показывать не только вывод программы, но и содержимое каждой конкретной ячейки памяти, использовано два вектора: out_result содержит вывод программы, а final_out_result подключён к дешифраторам семисегментных индикаторов.

type 		t_memory is array (31 downto 0) of std_logic_vector (7 downto 0); -- command memory
signal 	cell_memory: t_memory := (others => x"00");

type		d_memory is array (63 downto 0) of std_logic_vector (2 downto 0); -- cells memory
signal 	comm_memory: d_memory := (others => "000");

signal comm_number: std_logic_vector(6 downto 0) := (others => '0');
signal cell_number: std_logic_vector(5 downto 0) := (others => '0');

signal out_result: std_logic_vector(7 downto 0) := (others => '0');
signal final_out_result: std_logic_vector(7 downto 0) := (others => '0');

Process (clk, RESET)

Наконец подобрались к самому главному — модели поведения интерпретатора. Для начала объявим переменную-счётчик открытых скобок.

variable 	u: integer := 0; 

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

begin
		if rising_edge(clk) then
		if (not RESET) then
			cell_memory <= (others => x"00");
			out_result <= (others => '0');
			final_out_result <= cell_memory(conv_integer(unsigned(cell_number)));
			if (RUN = '0') then -- writing a programm
			     comm_memory(conv_integer(unsigned(SW(8 downto 3)))) <= SW(2 downto 0);
			end if;

По сигналу сброса (кнопки в Cyclone II инверсные, поэтому и условие инверсное) обнуляем значения ячеек памяти и выходной вектор, а если при этом ещё и идёт запись программы, заполняем соответствующую ячейку памяти команд.

else
			if (RUN = '0') then
				running_led <= false;
				LED <= comm_memory(conv_integer(unsigned(SW(8 downto 3))));	
				comm_number <= (others => '0');
				cell_number <= (others => '0');
				cell_memory <= (others => x"00");

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

else -- executing
			running_led <= true;
			LED <= (others => '0');
				if (SW(5) = '1') then final_out_result <= cell_memory(conv_integer(unsigned(SW(4 downto 0)))); -- out: user's or programm's cell
					else final_out_result <= out_result;
				end if;
				

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

			case comm_memory(conv_integer(unsigned(comm_number))) is 
				when "000" => 			-- next
					if (u = 0) then cell_number <= cell_number + 1;
						end if;
					if (u < 0 )then comm_number <= comm_number - 1;
						else comm_number <= comm_number + 1;
					end if;
				
				****************
				
				when "100" => 			-- [
					if ((cell_memory(conv_integer(unsigned(cell_number))) = x"00") or (u /= 0)) then
						u := u + 1;
					end if;
					if (u < 0 )then comm_number <= comm_number - 1;
						else comm_number <= comm_number + 1;
					end if;
				
				when "101" =>			 -- ]
					if ((cell_memory(conv_integer(unsigned(cell_number))) /= x"00") or (u /= 0)) then
						u := u - 1;
					end if;
					if (u < 0 )then comm_number <= comm_number - 1;
						else comm_number <= comm_number + 1;
					end if;
			
			when others =>			-- stop
				if (u = 0) then
					null;
				end if;

Программа на Brainfuck представляется как автомат: есть набор фиксированных состояний, перемещение между которыми осуществляется (за исключением циклов) линейно. Такая модель на VHDL (да и не только) реализуется switch-case конструкцией.
Как уже говорилось, u — счётчик открытых скобок. Команды выполняются только при (u = 0), в остальных случаях происходит поиск парной скобки. В нормальном режиме и при поиске закрывающей скобки указатель команд движется вперёд, иначе — назад. Здесь ясно видно, что если бы u была сигналом, при первой реакции на закрывающую скобку счётчик команд увеличился бы, только на следующем такте указатель пошёл бы назад, наткнулся на закрывающую скобку второй раз (u = -2), а такого количества парных открывающих скобок нет — программа никогда бы не выполнилась.
Условие (u /= 0) сделано для реализации вложенных циклов.

Testbench

Код готов и компилируется,

но перед прошивкой устройства надо протестировать алгоритм на адекватность. Текст тестбенча приводить не буду, он есть в прикреплённых файлах. Отмечу лишь, что тупой последовательный прогон всех значений здесь не подойдёт, поэтому проверяется корректность выполнения конкретной программы. Я использовал сложение двух чисел:
+++>++<[->+<]>.x
В качестве среды моделирования использовалась ModelSim-Altera.

Разводка платы

Последний этап перед прошивкой — задание соответствий сигналов модели реальным портам платы. Координаты выводов есть в приложении «Документация Cyclone II», ну а кому лень — вот готовая распиновка:

Заключение

Ну вот и всё, осталось только открыть Programmer, прошить плату, и… сидеть вбивать все команды и адреса вручную :) Я привёл не весь код, опустив стандартные части вроде секции use. Обещанное:

• Полностью готовый к прошивке (скомпилированный и разведённый по плате) проект
• Документация к Altera Cyclone II (с обозначением всех портов на координатной сетке)

P.S.

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