На третьем курсе некоторые направления в МИЭТ проходят лабораторный практикум, на котором им даётся возможность спроектировать собственную систему архитектуры RISC-V и написать под неё программу на С или C++.
В качестве затравки и повышения мотивации, хотелось показать им на что будет способна их процессорная система, и для этого было решено написать какую-нибудь простенькую игру, не требующую особых требований к ресурсам и графике. Так выбор пал на Змейку.
В этой статье я расскажу о том, как была написана данная игра под платформу, поддерживающую символьный вывод. Текст получился довольно объёмным, поэтому приготовьте пару кружек чая.
TLDR;
С исходным кодом можно ознакомиться здесь.
Реализация платформозависимой части начинается здесь
Результат можно посмотреть здесь
Содержание
Обзор целевой архитектуры
Прежде чем приступить к проектированию Змейки, давайте пройдемся по спецификации системы, под которую она проектируется:
Однотактный RISC-V процессор;
Тактовая частота: 10МГц;
Графика: символьное VGA-устройство разрешением 80х30 символов;
Устройство ввода: Клавиатура PS/2
Источник прерываний: внутренний таймер
Размер памяти инструкций: в пределах 32KiB
Размер памяти данных: в пределах 32KiB
Отладчик: отсутствует
Поскольку процессорная система реализуется в ПЛИС, размер памяти инструкций и данных можно настраивать (в общем-то можно сделать и 64KiB), но в конечном итоге, нам хватит и 8.
План проекта
Проектирование игры, мы разделим на 2 этапа:
объявление прототипов функций и классов,
реализация определений функций и классов.
Объявления и определения также стоит разделить на две части:
платформозависимую,
платформонезависимую.
Зачем сперва описывать прототипы функций? Это позволит построить архитектуру игры, не привязанную к конкретной реализации. Проектировать игру на уровне абстрактных понятий вроде: "Передвинуть голову", "Разместить пищу", "Проверить, что не произошло столкновение". Это позволяет сразу же построить карту дальнейшей разработки, сохраняя в голове ясную картину того, что из себя будет представлять игра.
Всё что остаётся после — это просто методично реализовать каждую из объявленных функций. И вот здесь как раз наоборот, можно практически не задумываться о том, что будут делать остальные функции, сместив вместо этого фокус на конкретную реализуемую функцию.
Такой подход можно называть "Проектирование с упором на интерфейс" (Interface first design). Минусом такого подхода может быть то, что описывая интерфейсы, не имея в основании какого-либо кода может привести к тому, что в процессе реализации функций могут возникнуть проблемы, в результате которых потребуется переписывать интерфейсную часть программы.
Итак, прежде чем кидаться к проектированию интерфейсов, давайте быстро пробежимся по тому, что мы знаем о данной игре:
Игрок управляет змейкой, которая через регулярные промежутки времени перемещается в последнем указанном игроком направлении.
Если змейка сталкивается с краями картами (стенами) или сама с собой — игра заканчивается.
В случайном месте карты (где не находится стена или змейка) появляется пища.
Съев пищу, змейка вырастает на одну условную единицу. После этого, генерируется новый объект пищи.
Получается, змейка представляет собой цепь секций хвоста, в самом начале которой находится голова.
Для перемещения змейки нет нужды перемещать все звенья этой цепи, достаточно переместить только голову и конец хвоста — остальные звенья могут оставаться неизменными.
Рост змейки после поедания пищи можно организовать, если не переместить конец хвоста после перемещения головы.
Требуется минимальная графика, змейку можно рисовать просто в виде ASCII-арта, например вот так:
--- |---oЭто значит, что по сути карта игры будет строиться в виде двумерного массива символов. Как этот массив будет отображаться — это уже детали реализации под конкретную платформу, логике игры достаточно работать просто с массивом символов.
Ввод будет осуществляться с клавиатуры PS/2, но теоретически его можно осуществлять и внешний источник ввода с помощью ASCII-символов, поэтому лучше абстрагироваться от конкретных кодов ввода и перейти к понятиям "вверх", "вниз", "влево", "вправо".
Было бы полезно, чтобы была возможность начать игру сначала, после её завершения, а также ставить игру на паузу.
Объявление прототипов функций
Основной цикл игры
Давайте опишем прототип функции, которая будет вызываться перед отрисовкой очередного фрейма. На целевой платформе это будет сделано посредством прерываний от встроенного таймера. Ход игрового цикла видится следующим:
Таким образом, нам нужно описать прототип функции game_cycle и ещё шесть прототипов других функций.
Можно заметить, что большая часть логики так или иначе связана с самой змейкой. Поэтому кажется разумным инкапсулировать эту часть логики в виде методов отдельного класса Snake:
class Snake
{
public:
Snake();
void get_input();
void move_head();
void move_tail();
bool has_head_accident();
bool is_eating();
};
Остаётся описать прототип функции, вызываемой обработчиком прерывания от таймера, а также прототип функции размещения очередной порции пищи и функции завершения игры:
void game_cycle();
void place_snack();
void do_game_over();
Кроме того, раз мы уже начали описывать функцию, отвечающую за завершения игры, было бы неплохо сразу же описать и функцию, инициализирующую карту, а также, постановку и снятие игры с паузы:
void do_new_game();
void do_game_pause();
void do_game_unpause();
Взаимодействие с платформой
Для того, чтобы разместить пищу в случайном месте на карте, нам потребуется генерация случайных чисел. А чтобы игра не шла по одной и той же канве, этот генератор нам потребуется засеивать разными зёрнами. Генерация случайных чисел может различаться в зависимости от используемой платформы, поэтому эти функции описываются в данном разделе.
Кроме того, хоть мы и ввели метод get_input, он отвечает скорее платформонезависимую логику. Нам также необходима платформозависимая функция, получающая значение конкретной нажатой клавиши. За это будет отвечать отдельная функция.
Кроме того, перед запуском игры скорее всего потребуется как-то настроить платформу. Таким образом, нам нужны следующие прототипы:
extern void config_periph();
// С помощью возвращаемого значения мы будем узнать, что пользователь нажал
// на клавишу.
extern bool get_key(uint8_t &key);
extern size_t get_random_value();
extern void seed_rng(size_t seed = 0);
С помощью ключевого слова extern мы сообщаем компилятору, что хоть мы и будем использовать описанные здесь функции, их реализация будет расположена в каком-то другом объектном файле. Связь адресов, по которым будут вызываться функции и их реализаций произойдёт на этапе компоновки.
Строковый вывод
Поскольку у целевой системы отсутствует отладчик, на протяжении всей разработки нам нужно будет выводить какие-то отладочные сообщения. Самым простым способом будет объявить функцию, которая бы посимвольно выводила переданную строку по указанным координатам:
void print_string(size_t row, size_t column, const char *str, size_t size);
Кроме того, наверняка нам потребуется выводить значение каких-либо объектов. Для этого нужно либо добавлять поддержку форматированных строк, либо просто отдельную функцию, выводящую значение числа. В следующем абзаце я расскажу свои мысли про добавление поддержи форматных строк, пока же просто добавим функцию, выводящую 32-битное число в шестнадцатеричном формате:
void print_uint32(size_t row, size_t column, uint32_t number);
На самом деле, добавить printf-like функцию, пишущую в видео-память не так сложно. Сделать это можно например вот так:
#include <cstdarg>
#include <cstdio>
#include <cstring>
constexpr size_t SCREEN_AREA = WIDTH * HEIGHT;
char printf_buffer[WIDTH];
void screen_printf(char* video_memory, size_t offset, const char* format, ...) {
if (offset >= SCREEN_AREA) return;
va_list args;
va_start(args, format);
vsnprintf(printf_buffer, sizeof(printf_buffer), format, args);
va_end(args);
size_t max_copy = SCREEN_AREA - offset;
strncpy(&video_memory[offset], printf_buffer, max_copy);
}
Здесь ... — это не фигура речи, а специальный аргумент, который говорит, что дальше у функции может быть произвольное (вариативное) количество аргументов. Функции, которые содержат такой аргумент называются вариативными (wiki, cppreference). Именно поэтому, когда вы используете printf, вы можете передать на вывод сколько угодно аргументов (число которых тем не менее должно совпадать тем, что используется в форматной строке, т.к. именно по ней printf понимает сколько дополнительных аргументов вы собираетесь передать).
Для взаимодействия с дополнительными аргументами вариативных функций, используются специальные макросы: va_list, va_start, va_end, va_arg, va_copy.
Единственная проблема данного решения заключается в том, что оно тянет порядка 50KiB кода. При желании, на целевой системе можно было бы конечно выделить такое количество дополнительного места в памяти инструкций, но учитывая что вся игра будет весить единицы кибибайт, использование такой раздутой функции, как бы элегантно она не выглядела, кажется нецелесообразным.
Таким образом, на этапе планирования прототипов мы получили следующий заголовочный файл:
void do_new_game();
void do_game_pause();
void do_game_unpause();
void do_game_over();
void game_cycle();
void place_snack();
void print_string(size_t row, size_t column, const char *str, size_t size);
void print_uint32(size_t row, size_t column, uint32_t number);
/*
========================================================================
Функции, которые должны быть определены в платформозависимой части игры.
========================================================================
*/
extern void config_periph();
// С помощью возвращаемого значения мы будем узнать, что пользователь
// нажал на клавишу.
extern bool get_key(uint8_t &key);
extern size_t get_random_value();
extern void seed_rng(size_t seed = 0);
//======================================================================
class Snake
{
public:
Snake();
void get_input();
void move_head();
void move_tail();
bool has_head_accident();
bool is_eating();
};
Реализация платформонезависимой части
Глобальные переменные
В данной реализации необходимо сохранять состояние игры между вызовами обработчика прерываний от таймера, поэтому без глобальных переменных нам не обойтись. Давайте подумаем, что именно нам потребуется.
В первую очередь, нам точно потребуется объект класса Snake. Кроме того, если игра может находиться в состоянии паузы, а также завершения игры, было бы неплохо реализовать переменную, отвечающую за её состояние. Кроме того, нам необходимо хранить координаты пищи, иметь доступ к нашему массиву, представляющему собой абстракцию над реализуемой на платформе графикой.
Таким образом, мы получаем следующие глобальные переменные:
enum game_state
{
ACTIVE,
PAUSED,
IDLE
};
game_state state = IDLE;
volatile uint8_t (*video_memory_2d)[WIDTH];
volatile uint8_t *video_memory_1d;
Snake snake;
size_t snack_coord = 0;
Для реализации состояния игры было введено перечисление, характеризующие возможные состояния игры:
активное,
приостановленное,
неактивное.
Кроме того, представлены две формы абстракции видео-памяти: одномерный и двумерный массив. Круглые скобки в объявлении необходимы, чтобы показать, что данный тип является именно указателем на массив из WIDTH элементов. Без скобок это будет объявлением массива из WIDTH указателей. Текущее объявление позволит работать с video_memory_2d как с двумерным массивом в виде:
video_memory_2d[row][col]
Избегая вычисления индекса через умножение, как это требуется для одномерного массива:
video_memory_1d[row * WIDTH + col]
В зависимости от ситуации может быть удобней работать как с одним, так и с другим представлением массива, поэтому здесь объявлено оба варианта. Оба эти варианта в конечном итоге будут отображены на одно и то же устройство вывода. Пока же мы можем представлять вывод в игре как простую запись в данный массив, не заботясь о том, каким именно образом записанные в массив значения окажутся перед глазами у игрока.
Важно отметить, что при создании оба этих массива не являются инициализированными. Запись и чтение из этих массив возможно только после того, как завершится вызов
config_periphв функцииmain.
Класс Snake
Перейдем к реализации класса Snake. Пока что мы объявили только методы этого класса, но нам стоит подумать над тем, какие поля будет хранить объект данного класса. Первое что приходит на ум — это какой-то контейнер, который будет хранить координаты всех звеньев хвоста змейки и её головы.
Если бы мы проектировали змейку под систему общего назначения — нам бы подошла двусторонняя очередь (deque) из стандартной библиотеки шаблонов (STL). Это позволило бы без проблем добавлять и удалять элементы как из начала контейнера, так и из его конца.
Однако поскольку мы пишем змейку под встраиваемую систему, нам стоит избегать STL-контейнеров, равно как и использования динамической памяти — ведь иначе нам придется реализовывать логику управления этой памятью (аллокатор). Для нашей задачи будет достаточно реализовать кольцевой буфер поверх выделенного заранее статического массива.
Кольцевой (циклический) буфер — это структура данных, использующая единственный буфер фиксированного размера таким образом, как будто бы после последнего элемента сразу же снова идет первый. У данной структуры имеется два итератора:
begin— указатель на начало буфера;end—указатель на конец буфера;
При создании кольцевого буфера, оба этих итератора ведут на начало массива. При добавлении элементов в конец буфера мы записываем значение по итератору end с последующей его инкрементацией. Если в результате итератор выходит за границу статического массива, мы переносим его обратно на начало, замыкая кольцо буфера (для этого увеличение значения итератора происходит с вычислением остатка от деления на размер массива). Обратите внимание на то, что итератор end указывает не на последний элемент массива, а "за него" — это стандартное поведение данного итератора для всех STL-контейнеров (и не только их).
Удаление элемента происходит путём увеличения итератора begin по тем же самым правилам. При этом в реальности элементы не удаляются из массива, просто они оказываются позади итератора begin.
Предположим, мы имеем кольцевой буфер на 8 элементов. В начале оба итератора указывают на начало массива. Затем, выполним следующие шаги.
Добавим в массив элемент со значением
D. Итераторendперемещается на 1 позицию вправо. Размер массива — 1.Добавим 6 элементов:
EADBEE. Итераторendперемещается на 6 позиций вперёд. Размер массива — 7.Удалим из массива 4 элемента. Итератор
beginперемещается на 4 позиции вперёд. Размер массива становится равен трём.Добавим в массив элемент
F. Итераторendперемещается на 1 элемент вперёд, но, поскольку итераторendуже был на конце массива, теперь он указывает на самое его начало. Размер массива становится равен 4.Добавив ещё 4 элемента
FA11в массив, мы перезаписываем значение удалённых элементов и заполняем массив до конца. Его размер становится равен 8, а итераторendуказывает туда же, куда иbegin.
Линейное представление буфера.
То же самое представление буфера, замкнутое для удобства восприятия в кольцо.
К сожалению, не получилось разместись анимации внутри таблицы, чтобы они были на одной строке.
Учитывая, что кольцевой буфер будет создан в единственном экземпляре, находиться внутри класса змейка, а добавление и удаление элементов будет осуществляться в отдельных методах этого класса, реализовывать буфер в виде отдельного типа нет особой нужды, можно описывать его в "сыром" виде, создав массив статической памяти и два итератора в виде индексов этого массива. Кроме того, для наших задач будет удобно реализовать итератор end таким образом, чтобы он указывал именно на последний элемент массива, а не за него.
Определимся с размером статической памяти. Учитывая, что разрешение целевой платформы: 80х30 символов, максимальный размер, которого может достичь змейка:
80*30 - ((80+30)*2 - 4) = 2184 (площадь сетки, минус её периметр). Каждая координата змейки на такой карте будет требовать 2 байта, а значит на массив потребуется порядка 4KiB. Не хочется быть скрягой, но это кажется перебором, учитывая, что никто не станет выращивать змейку на такой большой карте до её предела. Лучше ограничить размер массива каким-то на порядок меньшим числом (например, 256 элементами) и, в случае, если змейка достигнет предела массива — завершить игру с победой. А в случае, если система будет запускаться на платформах с меньшим количеством символов, победным можно будет считать размер змейки, равный половине сетки доступных ячеек. Таким образом, объявим следующие константные выражения:
constexpr size_t WIDTH = 80;
constexpr size_t HEIGHT = 30;
constexpr size_t SCREEN_AREA = WIDTH * HEIGHT;
constexpr size_t WIN_LENGTH = SCREEN_AREA / 2 < 256 ? SCREEN_AREA / 2 : 256;
Вернёмся к полям нашей змейки. Помимо полей, реализующих кольцевой буфер, нам нужно ещё одно: направление движения змейки. Его можно реализовать в виде ещё одного перечисления. Однако перед этим хотелось бы необходимо решить один вопрос: в каком формате мы хотим хранить координаты звеньев хвоста змейки?
Варианта два:
вектором,
скаляром.
Если хранить координаты в виде вектора [row, col], их можно будет достаточно легко прочитать, и передавать в видео-память, представленную в виде одномерного массива. Проблема заключается в том, что для хранения координат придется создавать либо отдельный тип, либо хранить их в виде двух отдельных полей.
Если хранить координаты в виде скаляра, каждая координата будет представлена одним числом — координатой видео-памяти, представленной в виде одномерного массива (row * WIDTH + col). В этом случае не придётся создавать новых типов, для работы с данным видом координаты можно будет использовать одномерное представление видео-памяти, однако чтение координат будет усложнено.
Воспользуемся вторым вариантом, чтобы не усложнять код дополнительными типами. Возвращаясь к перечислению, используемому для описания направления движения змейки. Учитывая, что будет использован скалярный тип координат, перечисление можно реализовать следующим образом:
enum direction
{
UP = -static_cast<int>(WIDTH),
DOWN = static_cast<int>(WIDTH),
RIGHT = 1,
LEFT = -1
};
Описанное таким образом перечисление можно будет без каких либо преобразований использовать при вычислений новой координаты головы змейки: в случае, если ей нужно переместиться вверх (т.е. на одну строку длиной WIDTH назад) — мы вычтем WIDTH, если нужно переместиться вправо — прибавим единицу и т.п. Таким образом, для вычисления новой координаты потребуется всего лишь прибавить значение направления змейки.
Объявление класса примет следующий вид:
class Snake
{
private:
size_t head_index;
size_t tail_index;
uint16_t snake_coords[WIN_LENGTH];
direction dir;
public:
Snake();
void get_input();
// метод, возвращающий количество элементов в кольцевом буфере
size_t size();
void move_head();
void move_tail();
bool has_collided(const size_t coord);
bool has_head_accident();
bool is_eating(const size_t coord);
};
Реализуем объявленные выше методы. Однако начнём не с конструктора, а с методов, связанных с кольцевым буфером: size, move_head, move_tail.
Реализация кольцевого буфера
Количество элементов, размещённых в кольцевом буфере можно вычислить следующим образом:
size_t size()
{
constexpr size_t N = WIN_LENGTH; // Размер статического массива
size_t num_of_elements = ((head_index+1) - tail_index + N) % N;
return num_of_elements == 0 ? N : num_of_elements;
}
где:
head_index— это аналог итератораendкольцевого буфера, который указывает на последний элемент буфера, а не за него;tail_index— это аналог итератораbeginкольцевого буфера.
Почему мы используем тернарный оператор возвращая количество элементов? Дело в том, что заполненный кольцевой буфер нельзя отличить от пустого, оперируя одними лишь его итераторами (первый и последний кадр представленных ранее анимаций по сути описывают одно и тоже состояние буфера, только с разными значениями, записанными в массив). Эти состояния можно различить, если завести отдельную переменную, которая хранит размер и изменяется при каждом добавлении/удалении элемента из буфера. Нам же однако не обязательно заводить такую переменную. В нашем случае массив в принципе не может быть пустым, т.к. мы будем создавать змейку ненулевого размера, и её длина не может уменьшаться. Поэтому ситуация, когда вычисленное по модулю значение количества элементов равно нулю — это может значить только то, что буфер полностью заполнен.
Реализуем move_head — метод, который перемещает голову змейки на 1 шаг вперед. Однако перед этим необходимо заменить символ головы змеи на символ её хвоста — иначе вся змейка будет состоять из одинаковых символов головы. Не то чтобы это было плохо — в той змейке на Nokia что я играл так и было, но как душа лежит к тому, чтобы голова все-таки выглядела отлично от хвоста.
Где тут начало, где конец? Кто ж теперь разберёт.
Итак, сперва нужно заменить символ головы змейки на символ её хвоста. Затем, добавить в кольцевой буфер новый элемент — новую координату головы змейки, после чего отрисовать её в новом месте. Обратите внимание на то, что добавление элемента в кольцевой буфер будет происходить вне зависимости от того съела змейка пищу или нет. От поедания пищи будет зависит удалим ли мы крайний элемент хвоста из кольцевого буфера — именно это будет определять рост длины змейки.
Чтобы отрисовать голову или хвост, нужно договориться какие символы мы хотим для использовать. В общем-то я уже вскрыл все карты на этапе планирования, поэтому опишем сразу и все остальные используемые в игре символы:
голова отображается символом
o,вертикальная часть хвоста отображается символом
|,горизонтальная часть хвоста отображается символом
-пища отображается символом:
@стена отображается символом
|пустое пространство за змейкой будет затираться с помощью символа
Определим эти символы в виде констант:
constexpr uint8_t WALL_CHAR = '|';
constexpr uint8_t HEAD_CHAR = 'o';
constexpr uint8_t HOR_TAIL_CHAR = '-';
constexpr uint8_t VER_TAIL_CHAR = '|';
constexpr uint8_t SNACK_CHAR = '@';
constexpr uint8_t SPACE_CHAR = ' ';
Реализуем метод move_head:
void Snake::move_head()
{
size_t cur_pos = snake_coords[head_index];
size_t new_pos = cur_pos + dir;
uint8_t tail_char = (dir == UP) || (dir == DOWN) ?
VER_TAIL_CHAR : HOR_TAIL_CHAR;
video_memory_1d[cur_pos] = tail_char;
head_index = (head_index + 1) % WIN_LENGTH;
snake_coords[head_index] = new_pos;
video_memory_1d[new_pos] = HEAD_CHAR;
}
Остался последний метод, связанный с кольцевым буфером: move_tail. Логика данного метода сводится лишь к затиранию крайнего элемента хвоста в видео-памяти и удалению его координат из кольцевого буфера:
void Snake::move_tail()
{
video_memory_1d[snake_coords[tail_index]] = SPACE_CHAR;
tail_index = (tail_index + 1) % WIN_LENGTH;
}
Реализация конструктора
Вернёмся к конструктору класса. При создании змейки, необходимо предварительно заполнить кольцевой буфер начальным положением секций её хвоста. Для этого было бы неплохо задать ее начальную длину отдельной константой START_TAIL_WIDTH. А для того, чтобы заполнить кольцевой буфер начальными значениями всех звеньев хвоста, можно воспользоваться последовательным вызовом метода move_head. В отсутствии вызова move_tail этот метод сможет "растянуть" змейку до нужной нам длины:
constexpr size_t START_TAIL_WIDTH = 3;
constexpr size_t START_TAIL_COORD = 15 * WIDTH + 10; // средняя строка
void Snake::reset()
{
head_index = 0;
tail_index = 0;
dir = RIGHT;
snake_coords[tail_index] = START_TAIL_COORD;
for (size_t i = 0; i < START_TAIL_WIDTH; i++)
{
move_head();
}
}
Вроде бы все хорошо, но есть проблема. Дело в том, что мы собираемся использовать объект класса Snake в качестве глобальной переменной, которая создаётся на этапе запуска программы, ещё до вызова main. А это значит, что ещё до вызова main будет вызван конструктор этого класса, и, следовательно, метод move_head. Поскольку данный метод активно записывает в видео-память которая будет проинициализирована только после запуска main, мы получим обращение в неинициализированную область памяти, с неопределенным поведением. Отложить вызов конструктора мы не можем, но мы можем перенести логику инициализации объекта в отдельный метод, тем более что при перезапусках игры нам нужно возвращать змейку в исходное состояние. Для этого, создадим новый метод: reset:
Snake::Snake(){}
void Snake::reset()
{
head_index = 0;
tail_index = 0;
dir = RIGHT;
snake_coords[tail_index] = START_TAIL_COORD;
for (size_t i = 0; i < START_TAIL_WIDTH; i++)
{
move_head();
}
}
Остаётся реализовать логику обработки ввода от пользователя, а также методы проверки змейки на коллизии со стенами, самой собой и пищей.
Обработка пользовательского ввода
Прежде чем описывать логику обработки ввода, давайте ещё раз пробежимся по возможным состояниям игры.
Активное — когда игра начата и не приостановлена. В этом состоянии пользователь нажал на клавишу:
паузы — приостанавливаем игру,
направления — меняем направление движения змейки.
Приостановленное — когда игра начата, но поставлена на паузу. В этом состоянии пользователь нажал на клавишу, снимающую игру с паузы, возобновляем игру.
Завершённое — когда игра ещё не начиналась, либо уже завершилась. Нажатие на любую клавишу в данном состоянии приводит к активации игры.
Таким образом, логика обработки ввода принимает следующий вид:
void Snake::get_input()
{
uint8_t key;
if (get_key(key))
{
if(state == PAUSED)
{
if(key == UNPAUSE_KEY)
{
do_game_unpause();
}
return;
}
state = ACTIVE;
direction new_dir;
new_dir = dir;
switch (key)
{
case UP_KEY:
new_dir = UP;
break;
case LEFT_KEY:
new_dir = LEFT;
break;
case DOWN_KEY:
new_dir = DOWN;
break;
case RIGHT_KEY:
new_dir = RIGHT;
break;
case PAUSE_KEY:
do_game_pause();
break;
}
if(new_dir != -dir)
{
dir = new_dir;
}
}
}
В разделе планирования упоминалось, что поскольку на разных платформах ввод может быть осуществлён разными средствами, коды клавиш, меняющих направление змейки могут быть разными, поэтому лучше перейти к константным выражениям вида UP/DOWN/LEFT/RIGHT. ОБъявить их можно например так:
#define PS2 0
#define ASCII 1
#ifndef INPUT_TYPE
#define INPUT_TYPE PS2
#endif
#if INPUT_TYPE == PS2
constexpr uint8_t UP_KEY = 0x1D; // W
constexpr uint8_t LEFT_KEY = 0x1C; // A
constexpr uint8_t DOWN_KEY = 0x1B; // S
constexpr uint8_t RIGHT_KEY = 0x23; // D
constexpr uint8_t PAUSE_KEY = 0x76; // ESC
constexpr uint8_t UNPAUSE_KEY = 0x5a; // Enter
#elif INPUT_TYPE == ASCII
constexpr uint8_t UP_KEY = 'w' ; // W
constexpr uint8_t LEFT_KEY = 'a' ; // A
constexpr uint8_t DOWN_KEY = 's' ; // S
constexpr uint8_t RIGHT_KEY = 'd' ; // D
constexpr uint8_t PAUSE_KEY = 0x1B; // ESC
#if defined(_WIN32)
constexpr uint8_t UNPAUSE_KEY = '\r'; // Enter
#else
constexpr uint8_t UNPAUSE_KEY = '\n'; // Enter
#endif
#else
#error "You must define INPUT_TYPE as either PS2 or ASCII"
#endif
Проверка змейки на коллизии
Для проверки того, что змейка столкнулась с препятствием или едой, нам нужно два метода:
bool has_head_accident();bool is_eating(const size_t coord);
Для проверки того, что голова змейки столкнулась с препятствием необходимо проверить, что координата головы не совпадает с координатой любой секции :
хвоста,
стены.
Забегая вперёд, замечу, что такая же проверка нам потребуется и при генерации новой порции пищи (мы бы не хотели, чтобы закуска оказалась внутри стены, равно как и посреди хвоста змейки). Поэтому было бы неплохо вынести общую логику в отдельную функцию, проверяющую что некоторая, переданная в качестве аргумента, координата не оказалась ни в хвосте ни в стене:
bool Snake::has_collided_with(const size_t coord)
{
bool top_collide = coord < WIDTH;
bool bottom_collide = coord >= WIDTH * (HEIGHT-1);
bool left_collide = false;
bool right_collide = false;
bool tail_collide = false;
size_t wrapped_coord = coord % WIDTH;
left_collide = wrapped_coord == 0;
right_collide = wrapped_coord == WIDTH - 1;
for (size_t i = tail_index; i != head_index; i = (i + 1) % WIN_LENGTH)
{
tail_collide |= coord == snake_coords[i];
}
return top_collide || bottom_collide || left_collide || right_collide || tail_collide;
}
bool Snake:: has_head_accident()
{
return has_collided_with(snake_coords[head_index]);
}
Остаётся проверить, что голова змейки пересеклась с координатой пищи:
bool Snake::is_eating(const size_t coord)
{
return snake_coords[head_index] == coord;
}
На этом класс Snake принимает свой окончательный вид:
Класс змейки
class Snake
{
public:
size_t length;
size_t head_index;
size_t tail_index;
direction dir;
uint16_t snake_coords[WIN_LENGTH];
Snake();
void reset();
void get_input();
void move_head();
void move_tail();
bool has_collided_with(const size_t coord);
bool has_head_accident();
bool is_eating(const size_t coord);
};
Snake::Snake(){}
void Snake::reset()
{
head_index = 0;
tail_index = 0;
dir = RIGHT;
snake_coords[tail_index] = START_TAIL_COORD;
for (size_t i = 0; i < START_TAIL_WIDTH; i++)
{
move_head();
}
}
void Snake::get_input()
{
uint8_t key;
if (get_key(key))
{
if(state == PAUSED)
{
if(key == UNPAUSE_KEY)
{
do_game_unpause();
}
return;
}
state = ACTIVE;
direction new_dir;
new_dir = dir;
switch (key)
{
case UP_KEY:
new_dir = UP;
break;
case LEFT_KEY:
new_dir = LEFT;
break;
case DOWN_KEY:
new_dir = DOWN;
break;
case RIGHT_KEY:
new_dir = RIGHT;
break;
case PAUSE_KEY:
do_game_pause();
break;
}
if(new_dir != -dir)
{
dir = new_dir;
}
}
}
void Snake::move_head()
{
size_t cur_pos = snake_coords[head_index];
size_t new_pos = cur_pos + dir;
uint8_t tail_char = (dir == UP) || (dir == DOWN) ?
VER_TAIL_CHAR : HOR_TAIL_CHAR;
video_memory_1d[cur_pos] = tail_char;
head_index = (head_index + 1) % std::size(snake_coords);
snake_coords[head_index] = new_pos;
video_memory_1d[new_pos] = HEAD_CHAR;
}
void Snake::move_tail()
{
video_memory_1d[snake_coords[tail_index]] = SPACE_CHAR;
tail_index = (tail_index + 1) % WIN_LENGTH;
}
bool Snake::is_eating(const size_t coord)
{
return snake_coords[head_index] == coord;
}
bool Snake::has_collided_with(const size_t coord)
{
size_t row = coord / WIDTH;
if (row == 0 || row == HEIGHT - 1)
{
return true;
}
size_t col = coord % WIDTH;
if (col == 0 || col == WIDTH - 1)
{
return true;
}
for (size_t i = tail_index; i != head_index; i = (i + 1) % WIN_LENGTH)
{
if (snake_coords[i] == coord)
{
return true;
}
}
return false;
}
bool Snake:: has_head_accident()
{
return has_collided_with(snake_coords[head_index]);
}
Перейдем к реализации функций вывода
Функции вывода строк и чисел
Как уже писалось ранее, реализовывать функцию с поддержкой форматной строки для данной игры нет особой нужды. Вывод строк и чисел нам нужен для двух ситуаций:
вывода игровых сообщений (начало игры, пауза, конец игры и счёт),
вывода отладочных сообщений в процессе проектирования игры.
Для обоих случаев нам достаточно уметь вывести посимвольно переданную строку и число по заданным координатам:
void print_string(size_t row, size_t column, const char *str, size_t size);
void print_uint32(size_t row, size_t column, uint32_t number);
Для данной задачи нам будет удобней использовать двумерный массив, для упрощения позиционирования. Реализуем print_string:
void print_string(size_t row, size_t column, const char *str, size_t size)
{
for (size_t i = 0; i < size; i++)
{
video_memory_2d[row][column + i] = str[i];
}
}
В общем-то, ничего особенного, просто побайтовое копирование по заданным координатам. Проверка на выход за границы массива опущена (она появится чуть позже). Реализация print_uint32 уже интересней:
void print_uint32(size_t row, size_t column, uint32_t number)
{
video_memory_2d[row][column ] = '0';
video_memory_2d[row][column + 1] = 'x';
uint8_t cur_digit;
uint8_t cur_nibble;
for (size_t i = 0; i < 8; i++)
{
cur_nibble = (number >> (i * 4)) & 0xF;
cur_digit = cur_nibble < 10 ? cur_nibble + '0' : cur_nibble + 'A' - 0xA;
video_memory_2d[row][column + 9 - i] = cur_digit;
}
}
Идея та же самая, только теперь нам нужно представить "сырое" число в виде массива символов. Начнём с символов 0x — это обозначит что мы выводим число в шестнадцатеричном виде, благодаря чему можно будет уже не заботиться о вопросах знака. Далее необходимо преобразовать каждый ниббл (полбайта) в шестнадцатиричное число. Его значение можно получить наложением маски и сдвигом, а преобразование в число можно получить путём смещения от ASCII-кода '0' для цифр, меньших 10 и ASCII-кода 'A', для больших 10. Вычитание 0xA осуществляется по причине того, что если число больше 10, нам нужно смещаться не на всё число, а на то, насколько оно превышает 10:
если число равно 10 (превышает 10 на 0), мы хотим сместиться от 'A' на 0 символов,
если число равно 15 (превышает 10 на 5), мы хотим сместиться от 'A' на 5 символов к 'F.'
Мы закончили реализацию запланированных функций вывода, но вот что интересно за исключением вывода отладки мы ведь будем выводить игровые сообщения прямо посреди экрана. Было бы удобно не вычислять координаты вывода руками, а написать функцию, которая бы делала это за нас.
Расчёт номера центральной строки не так сложен — это HEIGHT/2. Кроме того, нам потребуется выводить двухстрочные сообщения, поэтому номер строки лучше оставить в качестве параметра. Другое дело — вычисление номера столбца. Если мы применим такой же трюк, сообщение начнется выводится ровно из центра экрана, а весь текст сместится в его правую половину. Вместо этого нужно отступить от центра экрана на половину длины строки, именно в этом случае произойдет выравнивание по центру. Давайте добавим в наш проект новую функцию:
template <size_t N>
size_t print_string_at_center(size_t row, const char (&str)[N])
{
static constexpr size_t len = N-1;
static_assert(len <= static_cast<size_t>(WIDTH),
"String greater than current WIDTH");
static constexpr size_t col = (WIDTH - len) / 2;
print_string(row, col, str, len);
return col+len;
}
Это шаблонная функция, поведение которой подстраивается под размер переданного массива, но этот размер должен быть известен на этапе компиляции. Благодаря этому, по вычисленному размеру (всё ещё на этапе компиляции) определяется координата столбца, откуда нужно вывести отцентрированную строку. Вычисленные координаты передаются в описанную выше функцию print_string. Для того, чтобы иметь возможность продолжить вывод после переданной строки, функция возвращает номер столбца, на котором завершился вывод.
Основной игровой цикл и обработчики смены режимов
В платформонезависимой части осталось реализовать следующие функции:
void game_cycle();
void place_snack();
void do_game_over();
void do_new_game();
void do_game_pause();
void do_game_unpause();
А также саму функцию main.
Реализуем их в представленном здесь порядке. Логика game_cycle была описана в виде блок-схемы на этапе планирования, за одним исключением. На этапе планирования мы не думали об ограничении на размер кольцевого буфера (а следовательно, и досрочном завершении игры по достижению максимального размера змейки), уточненная блок-схема выглядит следующим образом:
Это значит, что в список реализуемых функций, необходимо добавить и do_game_finish.
Опишем представленный алгоритм в виде кода:
void game_cycle()
{
snake.get_input();
if(state == ACTIVE)
{
snake.move_head();
if (snake.is_eating(snack_coord))
{
if(snake.size() == WIN_LENGTH)
{
do_game_finish();
}
else
{
place_snack();
}
}
else
{
snake.move_tail();
if (snake.has_head_accident())
{
do_game_over();
}
}
}
}
Далее реализуем функцию place_snack. По сути, её реализация сводится к цикличному вызову платформозависимой функции get_random_value до тех пор, пока не будет получена координата, которая не пересекается со стеной и телом змейки. На случай, если в логике игры что-то сломается лучше поставить счётчик, предотвращающий бесконечный цикл.
void place_snack()
{
size_t try_count = 0;
do
{
if (try_count > SNACK_ATTEMPTS_LIMIT)
{
size_t column = print_string_at_center(0,
"Stuck at generating snack. It's coord is: ");
print_uint32(0, column, snack_coord);
}
snack_coord = get_random_value();
try_count++;
}
while(snake.has_collided_with(snack_coord) || snake.is_eating(snack_coord));
video_memory_1d[snack_coord] = SNACK_CHAR;
}
Функции do_new_game, do_game_over и do_game_finish делают примерно одно и то же: выводят сообщение в центре экрана, переводят игру в неактивное состояние:
void do_new_game()
{
state = IDLE;
snake.reset();
print_string_at_center(HEIGHT/2, "Press any key to start new game");
}
void do_game_over()
{
state = IDLE;
size_t col = print_string_at_center(HEIGHT/2-1, "Game over. Your score is: ");
print_uint32(HEIGHT/2-1, col, snake.size() - (START_TAIL_WIDTH+1));
return;
}
void do_game_finish()
{
state = IDLE;
size_t col = print_string_at_center(HEIGHT/2-1, "You won. Your score is: ");
print_uint32(HEIGHT/2-1, col, snake.size() - (START_TAIL_WIDTH+1));
}
Функции do_game_pause и do_game_unpause делают нечто похожее, но интереснее.
Дело в том, что перед тем как вывести сообщение о паузе, необходимо сохранить в буфер содержимое видео-памяти, которое будет перезаписано нашим выводом. Это нужно для того, чтобы после снятия паузы, можно было восстановить содержимое, а не просто стереть все что было в центре экрана (потенциально стерев часть змейки или пищу).
Здесь не получится особо выжать преимущества из нашей функции, поэтому придется подготовить все размеры и координаты вручную:
const uint8_t pause_str1[] = "Game paused";
const uint8_t pause_str2[] = "Press Enter to continue";
constexpr size_t pause_len1 = std::size(pause_str1);
constexpr size_t pause_len2 = std::size(pause_str2);
uint8_t backup_array1[pause_len1];
uint8_t backup_array2[pause_len2];
void do_game_pause()
{
for (size_t i = 0; i < pause_len1; i++)
{
backup_array1[i] = video_memory_2d[HEIGHT/2-1][WIDTH/2 - pause_len1/2 + i];
}
for (size_t i = 0; i < pause_len2; i++)
{
backup_array2[i] =
video_memory_2d[HEIGHT/2][WIDTH/2 - pause_len2/2 + i];
}
print_string_at_center(HEIGHT/2-1, pause_str1);
print_string_at_center(HEIGHT/2, pause_str2);
state = PAUSED;
}
void do_game_unpause()
{
for (size_t i = 0; i < pause_len1; i++)
{
video_memory_2d[HEIGHT/2-1][WIDTH/2 - pause_len1/2 + i] = backup_array1[i];
}
for (size_t i = 0; i < pause_len2; i++)
{
video_memory_2d[HEIGHT/2][WIDTH/2 - pause_len2/2 + i] = backup_array2[i];
}
state = ACTIVE;
}
Осталось описать main и её вспомогательные функции. По сути, это бесконечный чисел, который при завершении игры начинает её сначала:
int main()
{
config_periph();
clear_screen();
while(true)
{
do_new_game();
while (state != ACTIVE);
prepare_game();
while (state != IDLE);
}
return 0;
}
void clear_screen()
{
for (size_t i = 0; i < WIDTH * HEIGHT; i++)
{
video_memory_1d[i] = ' ';
}
}
void place_walls()
{
for(size_t i = 0; i < WIDTH; i++)
{
video_memory_2d[ 0][i] = WALL_CHAR;
video_memory_2d[HEIGHT - 1][i] = WALL_CHAR;
}
for (size_t i = 1; i < HEIGHT - 1; i++)
{
video_memory_2d[i][ 0] = WALL_CHAR;
video_memory_2d[i][WIDTH - 1] = WALL_CHAR;
}
}
void prepare_game()
{
seed_rng();
clear_screen();
place_walls();
place_snack();
snake.reset();
}
clear_screen— это функция очистки экрана,place_walls— функция отрисовки границ карты,prepare_game— функция, сбрасывающая игру в исходное состояние.
На этом реализация платформонезависимой части завершена!
Реализация платформозависимой части
При описании игры, мы изолировали часть логики, т.к. её реализация зависит от конкретной платформы, на которой будет запущена игра. В частности:
мы ввели абстракцию
video_memory, которая с точки зрения игры выглядит как обычный массив, но за этим массивом должно стоять какое-то устройство вывода — нам необходимо связать одно с другим;для того, чтобы обработать пользовательский ввод, мы полагаемся на функцию
get_key, которая возвращаетtrue, если была нажата клавиша, значение которой можно получить из переданного по ссылке аргумента;необходимо обеспечить реализацию генерации случайных чисел;
необходимо проинициализировать периферию платформы, настроить таймеры и обработчик прерываний.
За это отвечают данные функции:
void config_periph();
bool get_key(uint8_t &key);
size_t get_random_value();
size_t seed_rng(size_t seed);
Давайте реализуем их для целевой платформы.
RISC-V baremetal VGA/PS2
Прежде чем приступить к реализации функций, давайте разберемся, какие глобальные переменные необходимы для их работы. К платформе поставляется заголовочный файл, описывающий структуры, через которые можно получить доступ к устройствам ввода и вывода:
#include <stdint.h>
#ifdef __cplusplus
#define CAST(type, addr) reinterpret_cast<type>(addr)
#elif
#define CAST(addr) (type)(addr)
#endif
struct PS2_HANDLE
{
volatile const uint32_t scan_code;
volatile const uint32_t unread_data;
volatile const uint32_t __unused__[7];
volatile uint32_t rst;
};
volatile PS2_HANDLE *ps2_ptr = CAST(struct PS2_HANDLE *, 0x03000000);
struct VGA_HANDLE
{
volatile uint8_t *char_map;
volatile uint8_t *color_map;
volatile uint8_t *tiff_map;
};
volatile VGA_HANDLE vga = {
CAST(uint8_t *, 0x07000000),
CAST(uint8_t *, 0x07001000),
CAST(uint8_t *, 0x07002000)
};
struct TIMER_HANDLE
{
volatile const uint32_t system_counter_low_bits;
volatile const uint32_t system_counter_high_bits;
volatile uint32_t delay_low_bits;
volatile uint32_t delay_high_bits;
volatile uint32_t mode;
volatile uint32_t repeat_counter;
volatile const uint32_t __unused2__[3];
volatile uint32_t rst;
};
volatile TIMER_HANDLE *timer_ptr = CAST(struct TIMER_HANDLE *, 0x08000000);
Из этого файла можно понять, что мы имеем доступ к нескольким периферийным устройствам, среди которых есть клавиатура PS/2, VGA-контроллер и таймер. Базовый адрес клавиатуры — 0x03000000, откуда по смещению 0x0 можно получить данные скан-кода нажатой клавиши, а по смещению 0x4 — узнать есть ли непрочитанные данные из клавиатуры. При этом для удобства взаимодействия с периферийным устройством предоставлена готовая структура, поэтому обращение к статусным регистрам возможно через:
ps2_ptr->scan_code;
ps2_ptr->unread_data;
Аналогичным образом работают и структуры других периферийных устройств. Подробнее ознакомиться с периферийными устройствами можно в учебных материалах по разработке данной процессорной системы.
Что до VGA-контроллера — он представляет собой объект структуры, а не указатель. Эта структура хранит 3 указателя, управляющих видео-памятью:
char_map— память выводимых символов,col_map— цветовая палитра каждого знако-места на экране,tiff_map— память шрифтов видео-адаптера.
По сути, char_map — это как раз тот массив, связь которого с video_memory приведёт реализации вывода на этой платформе. Мы сможем связать эти массивы в функции config_periph, но осталась ещё пара глобальных переменных, которые нам нужны: генератор случайных чисел и обёртка к нему.
Для генерации случайных чисел, стандартная библиотека C++ имеет заголовочный файл <random>. В нём есть множество движков для генератора псевдослучайных чисел. Учитывая, что мы будем запускаться на достаточно слабой системе, и что мы не пытаемся генерировать ключи симметричного шифрования, нам достаточно взять самый простой из имеющихся в библиотеке генераторов: minstd_rand. Для того, чтобы задать параметры распределения генерируемых случайных чисел, можно создать объект uniform_int_distribution:
#include <random>
std::minstd_rand rng;
std::uniform_int_distribution<size_t> uniform_dist(WIDTH, WIDTH *(HEIGHT - 1));
Диапазон [WIDTH:WIDTH *(HEIGHT - 1)] выбран по той причине, что нам нужно генерировать такие координаты, которые бы находились внутри нашей карты. При этом, отсекая от начала диапазон WIDTH значений, мы избавляемся от всех координат, которые бы пересеклись с верхней границей карты. Аналогичным образом мы сокращаем область и в конце диапазона. Теперь единственные коллизии которые могут произойти — это боковые границы и сама змейка.
Остаётся реализовать объявленные выше функции. В функции config_periph мы связываем нашу video_memory с char_map, а также настраиваем таймер:
void config_periph()
{
video_memory_1d = vga.char_map;
video_memory_2d = reinterpret_cast<volatile uint8_t (*)[WIDTH]>(vga.char_map);
config_timer();
}
void config_timer()
{
timer_ptr->delay_low_bits = 2000000; // 1/5s
timer_ptr->mode = 2; // forever
}
Функция get_key сводится к чтению двух статусных регистров:
bool get_key(uint8_t &key)
{
bool res = ps2_ptr->unread_data;
key = ps2_ptr->scan_code;
return res;
}
На самом деле, в реализации под данную платформу есть подвох. Нажатие на клавишу клавиатуры PS/2 приводит к отправки на устройство ввода скан-кода этой клавиши. Однако ещё есть отпускание клавиши — в этом случае, клавиатура пришлет два скан-кода: 0xF0 и скан-код отпущенной клавиши. С точки зрения управления змейкой это почти не скажется — все равно чтобы мы вместо обычного нажатия на клавишу жали бы быстро два раза, это никак не сказывается на направлении движения. Однако, если бы мы хотели чтобы игра ставилась и снималась с паузы одной и той же клавиши возникает проблема: когда вы нажимаете на клавишу, игра ставится на паузу, а когда отпускаете — снимается с неё.
Можно было бы попробовать игнорировать вторую посылку с помощью специального флага: взводить его по приему кода отпускания клавиши 0xF0, и опускать после пропуска второго кода.
Проблема в том, мы работаем с клавиатурой по опросу от таймера, который настроен на достаточно большой период в 200мс. За это время успевает прийти несколько посылок от клавиатуры, и, поскольку данный контроллер клавиатуры не буферизирует данные, код 0xF0 тут успевает быть переписан.
В качестве заплатки для данной платформы было принято решение разделить управление паузой на две разные клавиши: ESC для постановки на паузу, Enter для снятия с неё.
Реализуем функции, связанные с генерацией случайных чисел:
size_t get_random_value()
{
return WIDTH + 1 + rng() % (WIDTH * (HEIGHT - 2) - 2);
}
size_t get_tick_number()
{
return timer_ptr->system_counter_low_bits;
}
void seed_rng(size_t seed)
{
if(seed == 0)
{
seed = get_tick_number();
}
rng.seed(seed);
}
Как говорилось выше, для генерации случайных чисел в заданном диапазоне, было бы удобно использовать uniform_dist. Однако, на целевой платформе это приводило к поломке игры. Пока что не смог разобраться в причине, поэтому диапазон задается путём суммы и взятия остатка от деления.
Функция get_tick_number возвращает значение счётчика, расположенного внутри таймера. Это значение можно использовать, чтобы посеять зерно генератора псевдо-случайных чисел.
Осталось разобраться с последним вопросом: как сделать так, чтобы по каждому прерыванию от таймера происходил вызов функции game_cycle?
Для этого обратимся к файлу первичных инструкций (startup.S), поставляемому к данной платформе:
startup.S
.section .boot
.global _start
_start:
la gp, _gbl_ptr # Инициализация глобального указателя
la sp, _stack_ptr # Инициализация указателя на стек
# Инициализация (зануление) сегмента bss
la t0, _bss_start
la t1, _bss_end
_bss_init_loop:
blt t1, t0, _irq_config
sw zero, 0(t0)
addi t0, t0, 4
j _bss_init_loop
# Настройка вектора (mtvec) и маски (mie) прерываний, а также указателя на стек
# прерываний (mscratch).
_irq_config:
la t0, _int_handler
li t1, -1 # -1 (все биты равны 1) означает, что разрешены все прерывания
la t2, _trap_stack_ptr
csrw mtvec, t0
csrw mscratch, t2
csrw mie, t1
# Вызов функции main
_main_call:
li a0, 0 # Передача аргументов argc и argv в main. Формально, argc должен
li a1, 0 # быть больше нуля, а argv должен указывать на массив строк,
# нулевой элемент которого является именем исполняемого файла,
# Но для простоты реализации оба аргумента всего лишь обнулены.
# Это сделано для детерминированного поведения программы в случае,
# если программист будет пытаться использовать эти аргументы.
# Вызов main.
# Для того чтобы программа скомпоновалась, где-то должна быть описана
# функция именно с таким именем.
call main
# Зацикливание после выхода из функции main
_endless_loop:
j _endless_loop
# Низкоуровневый обработчик прерывания отвечает за:
# * Сохранение и восстановление контекста;
# * Вызов высокоуровневого обработчика с передачей id источника прерывания в
# качестве аргумента.
# В основе кода лежит обработчик из репозитория urv-core:
# https://github.com/twlostow/urv-core/blob/master/sw/common/irq.S
# Из реализации убраны сохранения нереализованных CS-регистров. Кроме того,
# в реализации сохраняются только необерегаемые регистры регистрового файла.
# Это сделано по причине того, что при вызове высокоуровневого обработчика
# прерываний, тот будет обязан сохранить оберегаемые регистры в соответствии
# с соглашением о вызовах.
_int_handler:
# Данная операция меняет местами регистры sp и mscratch.
# В итоге указатель на стек прерываний оказывается в регистре sp, а вершина
# программного стека оказывается в регистре mscratch.
csrrw sp, mscratch,sp
# Далее мы поднимаемся по стеку прерываний и сохраняем все регистры.
addi sp, sp, -80 # Указатель на стек должен быть выровнен до 16 байт, поэтому
# поднимаемся вверх не на 76, а на 80.
sw ra, 4(sp)
# Мы хотим убедиться, что очередное прерывание не наложит стек прерываний на
# программный стек, поэтому записываем в освободившийся регистр низ
# программного стека, и проверяем что приподнятый указатель на верхушку
# стека прерываний не залез в программный стек.
# В случае, если это произошло (произошло переполнение стека прерываний),
# мы хотим остановить работу процессора, чтобы не потерять данные, которые
# могут помочь нам в отладке этой ситуации.
la ra, _stack_ptr
blt sp, ra, _endless_loop
sw t0, 12(sp) # Мы перепрыгнули через смещение 8, поскольку там должен
# лежать регистр sp, который ранее сохранили в mscratch.
# Мы запишем его на стек чуть позже.
sw t1, 16(sp)
sw t2, 20(sp)
sw a0, 24(sp)
sw a1, 28(sp)
sw a2, 32(sp)
sw a3, 36(sp)
sw a4, 40(sp)
sw a5, 44(sp)
sw a6, 48(sp)
sw a7, 52(sp)
sw t3, 56(sp)
sw t4, 60(sp)
sw t5, 64(sp)
sw t6, 68(sp)
# Кроме того, мы сохраняем состояние регистров прерываний на случай, если
# произойдет ещё одно прерывание.
csrr t0, mscratch
csrr t1, mepc
csrr a0, mcause
sw t0, 8(sp)
sw t1, 72(sp)
sw a0, 76(sp)
# Вызов высокоуровневого обработчика прерываний.
# Для того чтобы программа скомпоновалась, где-то должна быть описана
# функция именно с таким именем.
call int_handler
# Восстановление контекста. В первую очередь мы хотим восстановить CS-регистры,
# на случай, если происходило вложенное прерывание. Для этого, мы должны
# вернуть исходное значение указателя стека прерываний. Однако его нынешнее
# значение нам ещё необходимо для восстановления контекста, поэтому мы
# сохраним его в регистр a0, и будем восстанавливаться из него.
mv a0,sp
lw t1, 72(a0)
lw t2, 76(a0)
addi sp, sp, 80
csrw mscratch, sp
csrw mepc, t1
csrw mcause, t2
lw ra, 4(a0)
lw sp, 8(a0)
lw t0, 12(a0)
lw t1, 16(a0)
lw t2, 20(a0)
lw a1, 28(a0) # Мы пропустили a0, потому что сейчас он используется в
# качестве указателя на верхушку стека и не может быть
# восстановлен.
lw a2, 32(a0)
lw a3, 36(a0)
lw a4, 40(a0)
lw a5, 44(a0)
lw a6, 48(a0)
lw a7, 52(a0)
lw t3, 56(a0)
lw t4, 60(a0)
lw t5, 64(a0)
lw t6, 68(a0)
lw a0, 40(a0)
# Выход из обработчика прерывания
mret
Из механизма обработки прерываний следует, что после его срабатывания (и выполнения сервисной работы по сохранению контекста) вызывается высокоуровневый обработчик int_handler. Причём, чтобы обеспечить корректный вызов этого обработчика, его необходимо реализовать следующим образом:
extern "C" void int_handler()
{
game_cycle();
}
Для того чтобы связать адреса функций и их вызовы между различными объектными файлами, создаётся специальная таблица — таблица символов. Символ — это название функции или глобальной переменной. При компиляции функций на C++ их символы получают вид, отличающийся от их исходных названий (добавляется так называемое манглирование — модификация имени на основе прототипа функции, например так будет выглядеть символ для функции do_game_over: _Z12do_game_overv). Вы можете посмотреть как выглядит таблица символов, выполнив nm filename. Низкоуровневый обработчик платформы ожидает, что символ функции будет без манглирования, как это принято в языке C. В языке C++ предусмотрен механизм, позволяющий отключить манглирование имён — для этого используется спецификатор extern "C".
На этом портирование под данную платформу завершено — Остаётся только собрать код и наслаждаться игрой!
Для сборки требуется скрипт компоновщика, описанный в материалах по проектированию процессорной системы:
linker_script.ld
OUTPUT_FORMAT("elf32-littleriscv") /* Указываем порядок следования байт */
ENTRY(_start) /* мы сообщаем компоновщику, что первая
исполняемая процессором инструкция
находится у метки "_start"
*/
/*
В данном разделе указывается структура памяти:
Сперва идёт регион "instr_mem", являющийся памятью с исполняемым кодом
(об этом говорит аттрибут 'x'). Этот регион начинается
с адреса 0x00000000 и занимает 1024 байта.
Далее идет регион "data_mem", начинающийся с адреса 0x00000000 и занимающий
2048 байт. Этот регион является памятью, противоположной региону "instr_mem"
(в том смысле, что это не память с исполняемым кодом).
*/
MEMORY
{
instr_mem (x) : ORIGIN = 0x00000000, LENGTH = 8K
data_mem (!x) : ORIGIN = 0x00000000, LENGTH = 8K
}
_trap_stack_size = 800; /* Размер стека обработчика перехватов.
Данный размер позволяет выполнить
до 10 вложенных вызовов при обработке
перехватов.
*/
_stack_size = 800; /* Размер программного стека.
Данный размер позволяет выполнить
от 10 вложенных вызовов.
*/
/*
В данном разделе описывается размещение программы в памяти.
Программа разделяется на различные секции:
- секции исполняемого кода программа;
- секции статических переменных и массивов, значение которых должно быть
"вшито" в программу;
и т.п.
*/
SECTIONS
{
/*
В скриптах компоновщика есть внутренняя переменная, записываемая как '.'
Эта переменная называется "счётчиком адресов". Она хранит текущий адрес в
памяти.
В начале файла она инициализируется нулём. Добавляя новые секции, эта
переменная будет увеличиваться на размер каждой новой секции.
Если при размещении секций не указывается никакой адрес, они будут размещены
по текущему значению счётчика адресов.
Этой переменной можно присваивать значения, после этого, она будет
увеличиваться с этого значения.
Подробнее:
https://home.cs.colorado.edu/~main/cs1300/doc/gnu/ld_3.html#IDX338
*/
/*
Следующая команда сообщает, что начиная с адреса, которому в данных момент
равен счётчик адресов (в данный момент, начиная с нуля) будет находиться
секция .text итогового файла, которая состоит из секций .boot, а также всех
секций, начинающихся на .text во всех переданных компоновщику двоичных
файлах.
Дополнительно мы указываем, что данная секция должна быть размещена в
регионе "instr_mem".
*/
.text : {
PROVIDE(_start = .);
*(.boot)
*(.text*)
} > instr_mem
/*
Секция данных размещается аналогично секции инструкций за исключением
адреса загрузки в памяти (Load Memory Address, LMA). Поскольку память
инструкций и данных физически разделены, у них есть пересекающееся адресное
пространство, которое мы бы хотели использовать (поэтому в разделе MEMORY мы
указали что стартовые адреса обоих памятей равны нулю). Однако компоновщику
это не нравится, ведь как он будет размещать две разные секции в одно и то же
место. Поэтому мы ему сообщаем, с помощью оператора "AT", что загружать секцию
данных нужно на самом деле не по нулевому адресу, а по какому-то другому,
заведомо большему чем размер памяти инструкций, но процессор будет
использовать адреса, начинающиеся с нуля. Такой вариант компоновщика
устраивает и он собирает исполняемый файл без ошибок. Наша же задача,
загрузить итоговую секцию данных по нулевым адресам памяти данных.
*/
.data : AT (0x00800000) {
/*
Общепринято присваивать GP значение равное началу секции данных, смещённое
на 2048 байт вперёд.
Благодаря относительной адресации со смещением в 12 бит, можно адресоваться
на начало секции данных, а также по всему адресному пространству вплоть до
4096 байт от начала секции данных, что сокращает объем требуемых для
адресации инструкций (практически не используются операции LUI, поскольку GP
уже хранит базовый адрес и нужно только смещение).
Подробнее:
https://groups.google.com/a/groups.riscv.org/g/sw-dev/c/60IdaZj27dY/m/s1eJMlrUAQAJ
*/
_gbl_ptr = . + 2048;
*(.*data*)
*(.sdata*)
} > data_mem
/*
Поскольку мы не знаем суммарный размер всех используемых секций данных,
перед размещением других секций, необходимо выровнять счётчик адресов по
4х-байтной границе.
*/
. = ALIGN(4);
/*
BSS (block started by symbol, неофициально его расшифровывают как
better save space) — это сегмент, в котором размещаются неинициализированные
статические переменные. В стандарте Си сказано, что такие переменные
инициализируются нулём (или NULL для указателей). Когда вы создаёте
статический массив — он должен быть размещён в исполняемом файле.
Без bss-секции, этот массив должен был бы занимать такой же объем
исполняемого файла, какого объёма он сам. Массив на 1000 байт занял бы
1000 байт в секции .data.
Благодаря секции bss, начальные значения массива не задаются, вместо этого
здесь только записываются названия переменных и их адреса.
Однако на этапе загрузки исполняемого файла теперь необходимо принудительно
занулить участок памяти, занимаемый bss-секцией, поскольку статические
переменные должны быть проинициализированы нулём.
Таким образом, bss-секция значительным образом сокращает объем исполняемого
файла (в случае использования неинициализированных статических массивов)
ценой увеличения времени загрузки этого файла.
Для того, чтобы занулить bss-секцию, в скрипте заводятся две переменные,
указывающие на начало и конец bss-секции посредством счётчика адресов.
Подробнее:
https://en.wikipedia.org/wiki/.bss
Дополнительно мы указываем, что данная секция должна быть размещена в
регионе "data_mem".
*/
_bss_start = .;
.bss : {
*(.bss*)
*(.sbss*)
} > data_mem
_bss_end = .;
/*=================================
Секция аллоцированных данных завершена, остаток свободной памяти отводится
под программный стек, стек прерываний и (возможно) кучу. В соглашении о
вызовах архитектуры RISC-V сказано, что стек растёт снизу вверх, поэтому
наша цель разместить его в самых последних адресах памяти.
Поскольку стеков у нас два, в самом низу мы разместим стек прерываний, а
над ним программный стек. При этом надо обеспечить защиту программного
стека от наложения на него стека прерываний.
Однако перед этим, мы должны убедиться, что под оба стека хватит места.
=================================
*/
/* Мы хотим гарантировать, что под стек останется место */
ASSERT(. < (LENGTH(data_mem) - _trap_stack_size - _stack_size),
"Program size is too big")
/* Перемещаем счётчик адресов над стеком прерываний (чтобы после мы могли
использовать его в вызове ALIGN) */
. = LENGTH(data_mem) - _trap_stack_size;
/*
Размещаем указатель программного стека так близко к границе стека
прерываний, насколько можно с учетом требования о выравнивании адреса
стека до 16 байт.
Подробнее:
https://riscv.org/wp-content/uploads/2015/01/riscv-calling.pdf
*/
_stack_ptr = ALIGN(16) <= LENGTH(data_mem) - _trap_stack_size?
ALIGN(16) : ALIGN(16) - 16;
ASSERT(_stack_ptr <= LENGTH(data_mem) - _trap_stack_size,
"SP exceed memory size")
/* Перемещаем счётчик адресов в конец памяти (чтобы после мы могли
использовать его в вызове ALIGN) */
. = LENGTH(data_mem);
/*
Обычно память имеет размер, кратный 16, но на случай, если это не так, мы
делаем проверку, после которой мы либо остаёмся в самом конце памяти (если
конец кратен 16), либо поднимаемся на 16 байт вверх от края памяти,
округлённого до 16 в сторону большего значения
*/
_trap_stack_ptr = ALIGN(16) <= LENGTH(data_mem) ? ALIGN(16) : ALIGN(16) - 16;
ASSERT(_trap_stack_ptr <= LENGTH(data_mem), "ISP exceed memory size")
}
Итоговый результат:
Для того, чтобы убедиться что спроектированные абстракции жизнеспособны, было бы неплохо осуществить порт под какую-нибудь другую платформу. Например под запуск в терминале на десктопном компьютере. Сказано — сделано. Вот только превью текста в моём редакторе говорит, что в статье набежало уже 40 минут на чтение. Думаю лучше отложить это на следующий раз. Заодно расскажу и о том, как портировать игру под встраиваемую систему с UART.
Если вдруг вас заинтересовала процессорная система, под которую велась разработка игры: приглашаю взглянуть на открытые материалы лабораторного практикума.
