Пишем на Ассемблере для Sega Genesis #1

Первая статья посвященная написанию игр для классической приставки Sega Genesis на Ассемблере Motorola 68000.

Напишем простейший бесконечный цикл для Сеги. Для этого нам понадобятся: ассемблер, эмулятор с дизассемблером, любимый текстовый редактор, базовое понимание строения рома Сеги.

Для разработки я использую собственный ассемблер/дизассемблер Gen68KryBaby:

https://gitlab.com/demensdeum/gen68krybaby/

Тул разработан на языке Python 3, для сборки на вход подается файл с расширением .asm либо .gen68KryBabyDisasm, на выходе получается файл с расширением.gen68KryBabyAsm.bin, который можно запустить в эмуляторе, либо на реальной приставке (осторожно, отойдите подальше, приставка может взорваться!)

Также поддерживается дизассемблинг ромов, для этого на вход надо подать файл рома, вне расширений .asm или .gen68KryBabyDisasm. Поддержка опкодов будет увеличиваться или уменьшаться в зависимости от моего интереса к теме, участия контрибьютеров.

Структура

Заголовок рома Сеги занимает первые 512 байт. В нем содержится информация об игре, название, поддерживаемая периферия, чексумма, прочие системные флаги. Предполагаю, что без заголовка приставка даже не будет смотреть на ром, подумав, что он некорректный, мол “что вы мне тут даете?”

После заголовка идет сабрутина/подпрограмма Reset, с нее начинается работа процессора m68K. Хорошо, дело за малым – найти опкоды (коды операций), а именно выполнение ничего(!) и переход на сабрутину по адресу в памяти. Погуглив, можно найти опкод NOP, которые не делает ничего и опкод JSR который осуществляет безусловный переход на адрес аргумент, то есть просто двигает каретку туда куда мы его просим, без всяких капризов.

Собираем все вместе

Донором заголовка для рома выступила одна из игр в Beta версии, на данный момент записывается в виде hex данных.

ROM HEADER: 

 00 ff 2b 52 00 00 02 00 00 00 49 90 00 00 49 90 00 00 49 90 00...и т.д. 

Код программы со-но представляет из себя объявление сабрутины Reset/EntryPoint в 512 (0x200) байте, NOP, возврат каретки к 0x00000200, таким образом мы получим бесконечный цикл.

Ассемблерный код сабрутины Reset/EntryPoint:

SUBROUTINE_EntryPoint:
    NOP
    NOP
    NOP 
    NOP
    NOP
    JSR 0x00000200  

Полный пример вместе с заголовком рома:

https://gitlab.com/demensdeum/segagenesissamples/-/blob/main/1InfiniteLoop/1infiniteloop.asm

Далее собираем:

python3 gen68krybaby.py 1infiniteloop.asm

Запускаем ром 1infiniteloop.asm.gen68KryBabyAsm.bin в режиме дебаггера эмулятора Exodus/Gens, смотрим что m68K корректно считывает NOP, и бесконечно прыгает к EntryPoint в 0x200 на JSR

Здесь должен быть Соник показывающий V, но он уехал на Вакен.

Ссылки

https://gitlab.com/demensdeum/gen68krybaby/

https://gitlab.com/demensdeum/segagenesissamples

https://www.exodusemulator.com/downloads/release-archive

Источники

ROM Hacking Demo – Genesis and SNES games in 480i

http://68k.hax.com/

https://www.chibiakumas.com/68000/genesis.php

https://plutiedev.com/rom-header

https://blog.bigevilcorporation.co.uk/2012/02/28/sega-megadrive-1-getting-started/

https://opensource.apple.com/source/cctools/cctools-836/as/m68k-opcode.h.auto.html

Как я не попал в мужика на шесте или история об удивительной изобретательности

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

Самодействующая салфетка профессора Люцифера Горгонзолы. Руб Голдберг

Во времена своей юности я работал над приложением для заказа такси. В проге можно было выбирать точку пикапа, точку дропа, рассчитывать стоимость поездки, тип тарифа, и собственно говоря, заказать такси. Приложение мне досталось на последнем этапе пред-запуска, после добавления нескольких фиксов приложение было выпущено в AppStore. Уже на том этапе вся команда понимала что реализована она очень плохо, паттерны проектирования не использовались, все компоненты системы были связаны намертво, в общем и целом, можно было ее записать в один большой сплошной класс (God object), ничего бы не изменилось, так как классы смешивали свои границы ответственности и в общей своей массе перекрывали друг друга мертвой сцепкой. Позже руководством было принято решение написать приложение с нуля, с использованием корректной архитектуры, что было выполнено и итоговый продукт был внедрен нескольким десяткам B2B клиентов.

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

Это был обычный рабочий день, от одного из заказчиков пришло задание немного доработать дизайн приложения – банально подвинуть на несколько пикселей вверх иконку в центре экрана выбора адреса пикапа. Что ж, профессионально оценив задачу в 10 минут я поднял иконку на 20 пикселей вверх, совершенно ничего не подозревая, я решил проверить заказ такси.

Что? Приложение больше не показывает кнопку заказа? Как это получилось?

Я не мог поверить своим глазам, после поднятия иконки на 20 пикселей приложение перестало показывать кнопку продолжения заказа. Откатив изменение я увидел кнопку снова. Что-то здесь было не так. Просидев 20 минут в дебаггере я немного устал от разматывания спагетти из вызовов перекрывающих друг друга классов, но обнаружил что *сдвигание картинки действительно меняет логику приложения*

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

Как это может происходить? Неужели *состояние* экрана зависит не от паттерна машины состояния, а от *представления* позиции мужика на шесте?

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

В примере выше прекрасно все, во первых это пример Машины Голдберга (заумные машины), во вторых пример нежелания разработчика как-то взаимодействовать с другими разработчиками в команде (попробуй разберись без меня), в третьих можно перечислить все проблемы по SOLID, паттернам (запахи кода), нарушение MVC и многое многое другое.

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

Ссылки

https://ru.wikipedia.org/wiki/Машина_Голдберга

https://ru.wikipedia.org/wiki/SOLID

https://refactoring.guru/ru/refactoring/smells

https://ru.wikipedia.org/wiki/Model-View-Controller

https://refactoring.guru/ru/design-patterns/state

Угадай группу

В данной заметке я опишу работу с текстовым классификатором fasttext.

Fasttext – библиотека машинного обучения для классификации текстов. Попробуем научить ее определять метал группу по названию песни. Для этого используем обучение с учителем при помощи датасета.

Создадим датасет песен с названиями групп:

__label__metallica the house jack built
__label__metallica fuel
__label__metallica escape
__label__black_sabbath gypsy
__label__black_sabbath snowblind
__label__black_sabbath am i going insane
__label__anthrax anthrax
__label__anthrax i'm alive
__label__anthrax antisocial
[и т.д.]

Формат обучающей выборки:

{__label__класс} {пример из класса}

Обучим fasttext и сохраним модель:

model = fasttext.train_supervised("train.txt")
model.save_model("model.bin")

Загрузим обученную модель и попросим определить группу по названию песни:

model = fasttext.load_model("model.bin")
predictResult = model.predict("Bleed")
print(predictResult)

В результате мы получим список классов на которые похож данный пример, с указанием уровня похожести цифрой, в нашем случае похожесть названия песни Bleed на одну из групп датасета.
Для того чтобы модель fasttext умела работать с датасетом выходящим за границы обучающей выборки, используют режим autotune с использованием файла валидации (файл тест). Во время автотюна fasttext подбирает оптимальные гиперпараметры модели, проводя валидацию результата на выборке из тест файла. Время автотюна ограничивается пользователем в самостоятельно, с помощью передачи аргумента autotuneDuration.
Пример создания модели с использованием файла тест:

model = fasttext.train_supervised("train.txt", autotuneValidationFile="test.txt", autotuneDuration=10000)

Источники

https://fasttext.cc
https://gosha20777.github.io/tutorial/2018/04/12/fasttext-for-windows

Исходный код

https://gitlab.com/demensdeum/MachineLearning/-/tree/master/6bandClassifier

x86_64 Assembler + C = One Love

В данной заметке я опишу процесс вызова функций Си из ассемблера.
Попробуем вызвать printf(“Hello World!\n”); и exit(0);

section .rodata
    message: db "Hello, world!", 10, 0

section .text
    extern printf
    extern exit
    global main

main:
    xor	rax, rax
    mov	rdi, message    
    call printf
    xor rdi, rdi
    call exit

Все гораздо проще чем кажется, в секции .rodata мы опишем статичные данные, в данном случае строку “Hello, world!”, 10 это символ новой строки, также не забудем занулить ее.

В секции кода объявим внешние функции printf, exit библиотек stdio, stdlib, также объявим функцию входа main:

section .text
    extern printf
    extern exit
    global main

В регистр возврата из функции rax передаем 0, можно использовать mov rax, 0; но для ускорения используют xor rax, rax; Далее в первый аргумент передаем указатель на строку:

rdi, message

Далее вызываем внешнюю функцию Си printf:

main:
    xor	rax, rax
    mov	rdi, message    
    call printf
    xor rdi, rdi
    call exit

По аналогии делаем передачу 0 в первый аргумент и вызов exit:

    xor rdi, rdi
    call exit

Как говорят американцы:
Кто никого не слушает
Тот плов кушает @ Александр Пелевин

Источники

https://www.devdungeon.com/content/how-mix-c-and-assembly
https://nekosecurity.com/x86-64-assembly/part-3-nasm-anatomy-syscall-passing-argument
https://www.cs.uaf.edu/2017/fall/cs301/reference/x86_64.html

Исходный код

https://gitlab.com/demensdeum/assembly-playground

Hello World x86_64 ассемблер

В данной заметке я опишу процесс настройки IDE, написание первого Hello World на ассемблере x86_64 для операционной системы Ubuntu Linux.
Начнем с установки IDE SASM, ассемблера nasm:

sudo apt install sasm nasm

Далее запустим SASM и напишем Hello World:

global main

section .text

main:
    mov rbp, rsp      ; for correct debugging
    mov rax, 1        ; write(
    mov rdi, 1        ;   STDOUT_FILENO,
    mov rsi, msg      ;   "Hello, world!\n",
    mov rdx, msglen   ;   sizeof("Hello, world!\n")
    syscall           ; );

    mov rax, 60       ; exit(
    mov rdi, 0        ;   EXIT_SUCCESS
    syscall           ; );

section .rodata
    msg: db "Hello, world!"
    msglen: equ $-msg

Код Hello World взят из блога Джеймса Фишера, адаптирован для сборки и отладки в SASM. В документации SASM указано что точкой входа должна быть функция с именем main, иначе отладка и компиляция кода будет некорректной.
Что мы сделали в данном коде? Произвели вызов syscall – обращение к ядру операционной системы Linux с корректными аргументами в регистрах, указателем на строку в секции данных.

Под лупой

Рассмотрим код подробнее:

global main

global – директива ассемблера позволяющая задавать глобальные символы со строковыми именами. Хорошая аналогия – интерфейсы заголовочных файлов языков C/C++. В данном случае мы задаем символ main для функции входа.

section .text

section – директива ассемблера позволяющая задавать секции (сегменты) кода. Директивы section или segment равнозначны. В секции .text помещается код программы.

main:

Обьявляем начало функции main. В ассемблере функции называются подпрограммами (subroutine)

mov rbp, rsp

Первая машинная команда mov – помещает значение из аргумента 1 в аргумент 2. В данном случае мы переносим значение регистра rbp в rsp. Из комментария можно понять что эту строку добавил SASM для упрощения отладки. Видимо это личные дела между SASM и дебаггером gdb.

Далее посмотрим на код до сегмента данных .rodata, два вызова syscall, первый выводит строку Hello World, второй обеспечивает выход из приложения с корректным кодом 0.

Представим себе что регистры это переменные с именами rax, rdi, rsi, rdx, r10, r8, r9. По аналогии с высокоуровневыми языками, перевернем вертикальное представление ассемблера в горизонтальное, тогда вызов syscall будет выглядеть так:

syscall(rax, rdi, rsi, rdx, r10, r8, r9)

Тогда вызов печати текста:

syscall(1, 1, msg, msglen)

Вызов exit с корректным кодом 0:

syscall(60, 0)

Рассмотрим аргументы подробнее, в заголовочном файле asm/unistd_64.h находим номер функции __NR_write – 1, далее в документации смотрим аргументы для write:
ssize_t write(int fd, const void *buf, size_t count);

Первый аргумент – файловый дескриптор, второй – буфер с данными, третий – счетчик байт для записи в дескриптор. Ищем номер файлового дескриптора для стандартного вывода, в мануале по stdout находим код 1. Далее дело за малым, передать указатель на буфер строки Hello World из секции данных .rodata – msg, счетчик байт – msglen, передать в регистры rax, rdi, rsi, rdx корректные аргументы и вызвать syscall.

Обозначение константных строк и длины описывается в мануале nasm:

message db 'hello, world'
msglen equ $-message

Достаточно просто да?

Источники

https://github.com/Dman95/SASM
https://www.nasm.us/xdoc/2.15.05/html/nasmdoc0.html
http://acm.mipt.ru/twiki/bin/view/Asm/HelloNasm
https://jameshfisher.com/2018/03/10/linux-assembly-hello-world/
http://www.ece.uah.edu/~milenka/cpe323-10S/labs/lab3.pdf
https://c9x.me/x86/html/file_module_x86_id_176.html
https://www.recurse.com/blog/7-understanding-c-by-learning-assembly
https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%BB%D0%BE%D0%B3_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D0%B4%D1%83%D1%80%D1%8B
https://www.tutorialspoint.com/assembly_programming/assembly_basic_syntax.html
https://nekosecurity.com/x86-64-assembly/part-3-nasm-anatomy-syscall-passing-argument
https://man7.org/linux/man-pages/man2/syscall.2.html
https://en.wikipedia.org/wiki/Write_(system_call)

Исходный код

https://gitlab.com/demensdeum/assembly-playground

Хеш таблица

Хеш таблица позволяет реализовать структуру данных ассоциативный массив (словарь), со средней производительностью O(1) для операций вставки, удаления, поиска.

Ниже пример простейшей реализации хэш мапы на nodeJS:

Как это работает? Следим за руками:

  • Внутри хеш мапы находится массив
  • Внутри элемента массива находится указатель на первую ноду связанного списка
  • Размечается память для массива указателей (например 65535 элементов)
  • Реализуют хеш функцию, на вход идет ключ словаря, а на выходе она может делать что угодно, но в итоге возвращает индекс элемента массива

Как работает запись:

  • На вход идет пара ключ – значение
  • Хэш функция возвращает индекс по ключу
  • Получаем ноду связанного списка из массива по индексу
  • Проверяем соответствует ли он ключу
  • Если соответствует, то заменяем значение
  • Если не соответствует, то переходим к следующей ноде, пока найдем либо, не найдем ноду с нужным ключом.
  • Если ноду так и не нашли, то создаем ее в конце связанного списка

Как работает поиск по ключу:

  • На вход идет пара ключ – значение
  • Хэш функция возвращает индекс по ключу
  • Получаем ноду связанного списка из массива по индексу
  • Проверяем соответствует ли он ключу
  • Если соответствует, то возвращаем значение
  • Если не соответствует, то переходим к следующей ноде, пока найдем либо, не найдем ноду с нужным ключом.

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

Источники

https://ru.wikipedia.org/wiki/Хеш-таблица
https://www.youtube.com/watch?v=wg8hZxMRwcw

Исходный код

https://gitlab.com/demensdeum/datastructures

Работа с ресурсами в Android C++

Для работы с ресурсами в Android через ndk – C++ существует несколько вариантов:

  1. Использовать доступ к ресурсам из apk файла, с помощью AssetManager
  2. Загружать ресурсы из интернета и распаковав их в директорию приложения, использовать с помощью стандартных методов C++
  3. Комбинированный способ – получить доступ к архиву с ресурсами в apk через AssetManager, распаковать их в директорию приложения, далее использовать с помощью стандартных методов C++

Далее я опишу комбинированный способ доступа, использующийся в игровом движке Flame Steel Engine.
При использовании SDL можно упростить доступ к ресурсам из apk, библиотека оборачивает вызовы к AssetManager, предлагая схожие с stdio интерфейсы (fopen, fread, fclose и т.д.)


SDL_RWops *io = SDL_RWFromFile("files.fschest", "r");

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


chdir(SDL_AndroidGetInternalStoragePath());

Далее записываем архив из буфера в текущую рабочую директорию с помощью fopen, fwrite, fclose. После того как архив окажется в доступной для C++ директории, распакуем его. Архивы zip можно распаковывать с помощью комбинации двух библиотек – minizip и zlib, первая умеет работать со структурой архивов, вторая же распаковывает данные.
Для получения более полного контроля, простоты портирования, я реализовал собственный формат архивов с нулевым сжатием под названием FSChest (Flame Steel Chest). Данный формат поддерживает архивацию директории с файлами, и распаковку; Поддержка иерархии папок отсутствует, возможна работа только с файлами.
Подключаем header библиотеки FSChest, распаковываем архив:


#include "fschest.h" 
FSCHEST_extractChestToDirectory(archivePath, SDL_AndroidGetInternalStoragePath()); 

После распаковки интерфейсам C/C++ будут доступны файлы из архива. Таким образом мне не пришлось переписывать всю работу с файлами в движке, а лишь добавить распаковку файлов на этапе запуска.

Источники

https://developer.android.com/ndk/reference/group/asset

Исходный Код

https://gitlab.com/demensdeum/space-jaguar-action-rpg
https://gitlab.com/demensdeum/fschest

Стек машина и RPN

Допустим нам необходимо реализовать простой интерпретатор байткода, какой подход к реализации этой задачи выбрать?

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

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


пMVkcatS olleHП
 

На выходе мы получим строку “Hello StackVM”. Стэк машина прочитывает программу слева-направо, загружая посимвольно данные в стек, при появлении опкода в символе – выполняет реализацию команды с использованием стека.

Пример реализации стековой машины на nodejs:

Обратная польская запись (RPN)

Также стековые машины легко использовать для реализации калькуляторов, для этого используют Обратную польскую запись (постфиксную запись).
Пример обычной инфиксной записи:
2*2+3*4

Конвертируется в RPN:
22*34*+

Для подсчета постфиксной записи используем стек машину:
2 – на вершину стека (стек: 2)
2 – на вершину стека (стек: 2,2)
* – получаем вершину стека два раза, перемножаем результат, отправляем на вершину стека (стек: 4)
3 – на вершину стека (стек: 4, 3)
4 – на вершину стека (стек: 4, 3, 4)
* – получаем вершину стека два раза, перемножаем результат, отправляем на вершину стека (стек: 4, 12)
+ – получаем вершину стека два раза, складываем результат, отправляем на вершину стека (стек: 16)

Как можно заметить – результат операций 16 остается в стеке, его можно вывести реализовав опкоды печати стека, например:
п22*34*+П

П – опкод начала печати стека, п – опкод окончания печати стека и отправки итоговой строки на рендеринг.
Для конвертации арифметических операций из инфиксной в постфикснуют используют алгоритм Эдсгера Дейкстры под названием “Сортировочная станция”. Пример реализации можно посмотреть выше, либо в репозитории проекта стек машины на nodejs ниже.

Источники

https://tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись

Исходный код

https://gitlab.com/demensdeum/stackvm/