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

В данной заметке я опишу работу с текстовым классификатором 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

0

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

0

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

0

Хеш таблица

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

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

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

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

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

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

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

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

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

Источники

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

Исходный код

https://gitlab.com/demensdeum/datastructures

0

Работа с ресурсами в 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

0

Стек машина и 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/

0

Скелетная анимация (Часть 2 – иерархия нод, интерполяция)

Продолжаю описывать алгоритм скелетной анимации, по мере его реализации в игровом движке Flame Steel Engine.

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

Иерархия нод

Для корректной работы алгоритма необходимо чтобы модель содержала в себе связь костей друг с другом (граф). Представим себе ситуацию при которой проигрываются одновременно две анимации – прыжок и поднятие правой руки. Анимация прыжка должна поднимать модель по оси Y, при этом анимация поднятия руки должна учитывать это и подниматься вместе с моделью в прыжке, иначе рука останется сама по себе на месте.

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

Интерполяция на CPU

В прошлой статья я описал принцип рендеринга скелетной анимации – “матрицы трансформации передаются из CPU в шейдер при каждом кадре рендеринга.”

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

Для интерполяции позиции и увеличения используют вектора, для поворота используются кватернионы, т.к. они очень легко интерполируются (SLERP) в отличии от углов Эйлера, также их очень просто представить в виде матрицы трансформации.

Как упростить реализацию

Чтобы упростить отладку работы вертексного шейдера, я добавил симуляцию работы вертексного шейдера на CPU с помощью макроса FSGLOGLNEWAGERENDERER_CPU_BASED_VERTEX_MODS_ENABLED. У производителя видеокарт NVIDIA есть утилита для отладки шейдерного кода Nsight, возможно она тоже может упростить разработку сложных алгоритмов вертексного/пиксельных шейдеров, однако проверить работоспособность мне так и не довелось, хватило симуляции на CPU.

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

Источники

https://www.youtube.com/watch?v=f3Cr8Yx3GGA

0

Добавляем поддержку скриптов JavaScript в C++

В данной заметке я опишу способ добавления поддержки JavaScript скриптов в приложение на C++ с помощью библиотеки Tiny-JS.

Tiny-JS представляет из себя библиотеку для встраивания в C++, обеспечивающая выполнение JavaScript кода, с поддержкой биндингов (возможность вызывать код C++ из скриптов)

Сначала я хотел использовать популярные библиотеки ChaiScript, Duktape или подключить Lua, но из-за зависимостей и возможных сложностей в портируемости на разные платформы, было принято решение найти простую, минимальную, но мощную MIT JS либу, этим критериям отвечает Tiny-JS. Единственный минус этой библиотеки в отсутствии поддержки/развития автором, однако ее код достаточно прост, что позволяет взять поддержку на себя, если это потребуется.

Загрузите Tiny-JS из репозитория:
https://github.com/gfwilliams/tiny-js

Далее добавьте в код который отвечает за скрипты хидеры Tiny-JS:


#include "tiny-js/TinyJS.h"
#include "tiny-js/TinyJS_Functions.h"

На этап сборки добавьте .cpp файлы TinyJS, далее можно приступать к написанию загрузки и запуска скриптов.

Пример использования библотеки доступен ее в репозитории:
https://github.com/gfwilliams/tiny-js/blob/master/Script.cpp
https://github.com/gfwilliams/tiny-js/blob/wiki/CodeExamples.md

Пример имплементации класса-обработчика можно посмотреть в проекте SpaceJaguar:
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/src/Controllers/SpaceJaguarScriptController/SpaceJaguarScriptController.h
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/src/Controllers/SpaceJaguarScriptController/SpaceJaguarScriptController.cpp

Пример игрового скрипта добавленного  в приложение:
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/resources/com.demensdeum.spacejaguaractionrpg.scripts.sceneController.js

Источники

https://github.com/gfwilliams/tiny-js
https://github.com/dbohdan/embedded-scripting-languages
https://github.com/AlexKotik/embeddable-scripting-languages

0