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

Скелетная анимация (Часть 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

Добавляем поддержку скриптов 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

Сборка C++ SDL приложения для iOS на Linux

В данной заметке я опишу процедуру сборки C++ SDL приложения для iOS на Linux, подпись ipa архива без платной подписки Apple Developer и установку на чистое устройство (iPad) с помощью macOS без Jailbreak.

Для начала установим тулчейн сборки для Linux:
https://github.com/tpoechtrager/cctools-port

Тулчейн нужно выгрузить из репозитория, далее по инструкции на сайте Godot Engine закончить установку:
https://docs.godotengine.org/ru/latest/development/compiling/cross-compiling_for_ios_on_linux.html

На данный момент требуется скачать Xcode dmg и скопировать оттуда sdk для сборки cctools-port. Данный этап проще проходить на macOS, достаточно скопировать из установленного Xcode необходимые файлы sdk. После успешной сборки, в терминале будет путь к тулчейну кросскомпилятора.

Далее можно приступать к сборке SDL приложения для iOS. Откроем cmake и добавим необходимые изменения для сборки C++ кода:


SET(CMAKE_SYSTEM_NAME Darwin)
SET(CMAKE_C_COMPILER arm-apple-darwin11-clang)
SET(CMAKE_CXX_COMPILER arm-apple-darwin11-clang++)
SET(CMAKE_LINKER arm-apple-darwin11-ld)

Теперь можно собирать с помощью cmake и make, но не забудьте прописать $PATH к тулчейну кросскомпилятора:



PATH=$PATH:~/Sources/cctools-port/usage_examples/ios_toolchain/target/bin

Для корректной линковки с фреймворками и SDL прописываем их в cmake, зависимости игры Space Jaguar для примера:



target_link_libraries(
${FSEGT_PROJECT_NAME}
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libclang_rt.ios.a
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2.a
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2_mixer.a
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2_image.a
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreServices.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/ImageIO.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/Metal.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/AVFoundation.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/GameController.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreMotion.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreGraphics.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/AudioToolbox.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreAudio.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/QuartzCore.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/OpenGLES.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/UIKit.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/Foundation.framework"
)

В моем случае библиотеки SDL, SDL_Image, SDL_mixer скомпилированы в Xcode на macOS заранее для статичной линковки; Фреймворки скопированы из Xcode. Также добавлена библиотека libclang_rt.ios.a, которая включает в себя специфические рантайм вызовы iOS, например isOSVersionAtLeast. Включен макрос для работы с OpenGL ES, отключение неподдерживаемых функций в мобильной версии, по аналогии с Android.

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

На macOS произведите установку Xcode, зарегистрируйтесь на портале Apple, без оплаты программы для разработчиков. Добавьте аккаунт в Xcode -> Preferences -> Accounts, создайте пустое приложение и соберите на реальном устройстве. Во время сборки устройство будет добавлено к бесплатному аккаунту разработчика. После сборки и запуска, нужно произвести сборку архива, для этого выберете Generic iOS Device и Product -> Archive. По окончанию сборки архива достаньте из него файлы embedded.mobileprovision, PkgInfo. Из лога сборки на устройство найдите строку codesign с корректным ключом подписи, путь к файлу entitlements с расширением app.xcent, скопируйте его.

Скопируйте папку .app из архива, замените бинарик в архиве на собранный кросскомпилятором в линуксе (например SpaceJaguar.app/SpaceJaguar), далее добавляем в .app необходимые ресурсы, проверьте сохранность PkgInfo и embedded.mobileprovision файлов в .app из архива, скопируйте заново если необходимо. Переподписываем .app с помощью команды codesign – codesign требует на вход ключ для sign, путь к файлу entitlements (можно переименовать с расширением .plist)

После переподписывания создайте папку Payload, перенесите туда папку с расширением .app, создайте zip архив с Payload в корне, переименуйте архив с расширением .ipa. После этого в Xcode откройте список устройств и сделайте Drag’n’Drop нового ipa в список приложений устройства; Установка через Apple Configurator 2 для данного способа не работает. Если переподписывание произведено корректно, то приложение с новым бинариком будет установлено на iOS устройство (например iPad) с 7 дневным сертификатом, на период тестирования этого достаточно.

Источники

https://github.com/tpoechtrager/cctools-port
https://docs.godotengine.org/ru/latest/development/compiling/cross-compiling_for_ios_on_linux.html
https://jonnyzzz.com/blog/2018/06/13/link-error-3/
https://stackoverflow.com/questions/6896029/re-sign-ipa-iphone
https://developer.apple.com/library/archive/documentation/Security/Conceptual/CodeSigningGuide/Procedures/Procedures.html

Games Vision #4

Четвертый выпуск очень непостоянной рубрики об играх Games Vision.

World Of Horror (кроссплатформа, panstasz) – roguelike игра раннего доступа в стиле эээ чего? Текстовой хоррор адвенчюры с элементами рпг? Графически напоминает игры 80-х, доступен выбор из 1-битной или 2-битной палитры с вариациями.

Управление по началу кажется странным, но со временем привыкаешь, ведь на то оно и roguelike чтобы удивлять и быть оригинальным в каждом аспекте. Потрясающая чиптюн музыка, эстетика Японии конца 80-х, визуал вдохновленный творчеством Дзюндзи Ито, странные истории в стиле Лавкрафта, почти бесконечная реиграбельность.
Что вам еще нужно?
Оценка: 9/10

Eternal Castle [REMASTERED] (PC, Daniele Vicinanzo, Giulio Perrone, Leonard Menchiari) – современная игра в стиле Another World, Flashback. Палитра специально уменьшена до цветов CGA. Описание данной игры нужно начинать с легенды ее создания: примерно в 1987 один из детей разработчиков Eternal Castle увидел игру и запомнил ее на всю жизнь, в итоге игра так и не вышла, но исходники удалось найти и восстановить в 2019 году, выпустив улучшенную версию. Однако описание в Steam содержит информацию что это ремастер бестселлера 1987 года, однако в том году игра с таким названием не выходила, что правда а что нет решать вам.

Графика и геймплей явно заточены под любителей поностальгировать по старым добрым временам, очень часто бывают моменты когда кажется что игра зависла, но а самом деле нужно просто нажимать кнопки перемещения или действия чтобы увидеть что происходит на экране. Данная уловка порождает ощущение неловкости и потерю контроля, что часто использовалось в старых играх, от чего отказались полностью в современных.
Оценка: 8/10

Death & Taxes (PC, Placeholder Gameworks) – вы когда-нибудь мечтали работать судьей и палачом в одно лице? Любите длинные черные балахоны, металлические косы, хрустеть костяшками? Тогда это идеальная игра для вас ведь “Невозможно избежать только двух вещей — смерти и налогов”.

Это единственный в своем роде симулятор ангела смерти, предстоит выбирать кому жить а кому умереть. Помимо убийств или дарования жизни, можно читать ленту новостей в своем смартфоне, видеть как выбор влияет на мир земли. Также нужно общаться с непосредственным начальником по имени Фейт (Судьба), покупать предметы и всякую утварь для стола, я например купил себе брутальный кактус. Не забудьте поговорить с зеркалом, очень увлекательно. Из минусов стоит отметить общую камерность происходящего, через несколько игровых дней игра становится немного монотонной.
Оценка: 8/10

Исправляем медленную работу HDD в Windows 10

Данная заметка посвящается всем, не сдающим позиции, пользователям жестких дисков.


Original (Mae Mu)

Через 1.5 года использования ноутбука HP Pavilion в дуалбуте HDD (Windows 10) и SSD (Ubuntu) я стал замечать очень долгую загрузку приложений, общую неотзывчивость интерфейса, зависания на простейших операциях в Windows 10. Проблема была минимизирована до той степени, что пользоваться ноутбуком стало возможно снова. Далее опишу действия которые я предпринял для устранения проблемы.

Диагностика

Для начала исследования нужно устранить мистификацию любого порядка, для начала определим основные причины поломок жестких дисков. Что может пойти не так при работе с жестким диском? Проблемы могут возникать на физическом уровне электроники и на логическом, программном уровне данных.
К проблемам электроники относятся такие вещи как: нерабочий блок питания компьютера/ноутбука, проблемы с аккумулятором ноутбука; износ компонентов жесткого диска, неполадки в схемах и чипах внутренних компонентов диска, программные ошибки прошивки, последствия ударов/падений диска, либо аналогичные проблемы с другими устройствами которые влияют на его работу.
Критическим износом жесткого диска считается момент появления количества такого количества сбойных секторов (bad block) при котором дальнейшая эксплуатация диска невозможна. Данные блоки блокируются прошивкой жесткого диска, данные переносятся на другие сектора автоматически и не должны влиять на работу диска до определенного критического момента.
К проблемам программной логики относятся ошибки в файловой системе из-за некорректной работы приложений, действий пользователя: отключение устройства по горячему, завершение процессов записи без корректной остановки приложений, ошибки в драйверах, сервисах операционной системы.
Не имея специализированных средств диагностики электроники, нам остается только проверять корректность программного уровня, уже в процессе могут обнаружиться неполадки электроники, которые обычно устраняют методом блочного ремонта (замена компонентов/чипов); Далее рассмотрим методы программной диагностики с помощью диагностических утилит. Стоит заметить что все утилиты должны запускаться на системе с максимальным приоритетом, т.к. другие приложения могут помешать замерам производительности, блокировать диск на чтение/запись, что приведет к некорректным результатам диагностики.

SMART

S.M.A.R.T. система мониторинга состояния устройств хранения данных – HDD, SDD, eMMC и пр. Позволяет оценить износ устройства, просматривать количество сбойных блоков (bad block), опираясь на данные предпринять дальнейшие действия. Просматривать SMART можно в разных приложениях для работы с дисками, я предпочитаю использовать утилиты от производителя. Для своего жесткого диска Seagate я использовал утилиту SeaTools, для него состояние выводилось как GOOD, то есть прошивка диска считает что все хорошо.

Утилиты производителя

Утилиты производителя диска предоставляют тесты для проверки его работы. SeaTools имеет несколько видов тестов, можно использовать их все для локализации проблемы. Быстрые и простые тесты могут не выявить каких-либо проблем, поэтому предпочитайте долгие тесты. В моем случае только на Long Test были найдены ошибки.

Slowride

Для проверки корректности чтения, нахождения медленных или мертвых блоков, я написал приложение slowride, оно работает по очень простому принципу – открывает дескриптор блочного устройства, с заданными настройками пользователя производит чтения данных всего устройства, с замерами времени, выводом медленных блоков. Программа останавливается на первой же ошибке, в таком случае придется перейти к более серьезным утилитам для снятия данных, так как простыми методами данные диска прочитать не представляется возможным.
В моем случае чтение всего диска осуществлялось корректно, с небольшой просадкой по скорости – 90мб/сек (5400rpm) за одну секунду, на некоторых областях диска. Из чего можно было сделать вывод что я имею дело с программной проблемой.

Акустический анализ

Данный метод не относится к программным методам диагностики, однако является достаточно важным для устранения проблемы. Например при частично рабочем блоке питания, жесткий диск может подвисать/зависать издавая громкий щелчок.
В моем случае при работе с диском в Windows 10 я слышал знакомый всем владельцам HDD, громкий треск бегающей туда-сюда головки диска при попытке сделать что-либо в операционной системе, однако звук был почти постоянным, это навело меня на мысль о слишком большой фрагментации диска, перегрузе диска фоновыми сервисами.

Исправляем

Проблемы электроники во время программной диагностики обнаружены не были, поблочное чтение всего диска завершалось корректно, однако SeaTools показал ошибки на проверке Long Test.

Утилиты производителя

Софт производителя диска помимо диагностики предоставляет процедуры исправления ошибок. В SeaTools за это отвечает кнопка Fix All, после подтверждения согласия с потенциальной потерей данных, запустится процесс исправления. Помог ли в моем случае этот фикс? Нет, диск продолжил работать также громко и медленно, однако ошибок Long Test больше не показывал.

CHKDSK

CHKSDK это утилита компании Microsoft для устранения программных ошибок для файловых систем Windows. Со временем такие ошибки накапливаются на диске и могут очень сильно мешать работе, в том числе приводить к невозможности читать/писать какие-либо данные вообще. Инструкцию по использованию утилиты вы можете найти на сайте Microsoft, я же порекомендую использовать все возможные флаги для исправления ошибок (на момент написания заметки это /r /b /f); Запускать проверку нужно с правами администратора через терминал Windows (cmd), для системного раздела она будет проходить на загрузке системы, может проходить очень долгое время, в моем случае заняло 12 часов.
Помог ли этот фикс в моем случае? Нет.

Дефрагментация диска

Работа с данными на диске осуществляется блоками, большие файлы обычно записываются в несколько блоков/фрагментов. Со временем, множество удаленных файлов создают пустые блоки которые не находятся рядом, из-за этого при записи файлы заполняют эти пустоты, и головке диска приходится физически преодолевать большие расстояния. Данная проблема называется фрагментацией, и с ней сталкиваются только пользователи жестких дисков. На момент нескольких фиксов фрагментация моего жесткого диска составляла 41%, визуально это выглядело так:

То есть все плохо. Увидеть фрагментацию, провести дефрагментацию можно с помощью утилиты Defragger, либо встроенным дефрагментатором. Также можно включить сервис “Optimize drives” в Windows 10, проставить дефрагментацию по расписанию в контрольной панели. Дефрагментацию нужна только HDD дискам, включать для SSD дисков нежелательно, так как это приведет к ускоренному износу диска, видимо по этой причине фоновая дефрагментация отключена по умолчанию.

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

Отключаем сервисы

С помощью утилиты Марка Руссиновича Process Monitor можно отследить процессы которые загружают жесткий диск своими делами, достаточно включить колонки IO Write/Read. После исследования данной колонки я отключил сервис Xbox Game Bar, известный сервис фонового ускорения программ Superfetch под новым названием SysMain, через панель сервисов контрольной панели. Superfetch должен постоянно анализировать приложения которыми пользуется юзер и ускорять их запуск с помощью кэширования в оперативную память, в моем случае это приводило к фоновой загрузке всего диска и невозможности работы.

Чистим диск

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

Итог

Что помогло больше всего? Заметная разница в производительности была достигнута после дефрагментации диска, спонтанные зависания удалось устранить с помощью отключения сервисов Xbox и Superfetch. Не было бы этих проблем, если бы я пользовался SSD? Проблем с медленной работой при фрагментацией определенно не было бы, проблемы с сервисами устранять пришлось бы в любом случае, а программные ошибки не зависят от типа накопителя. В ближайшем будущем планирую полный переход на SSD, ну а пока “Да здравствуют блины, блины навсегда!”

Ссылки

http://www.outsidethebox.ms/why-windows-8-defragments-your-ssd-and-how-you-can-avoid-this/
https://channel9.msdn.com/Shows/The-Defrag-Show
https://www.seagate.com/ru/ru/support/downloads/seatools/
https://www.ccleaner.com/defraggler/download
https://docs.microsoft.com/en-us/windows-server/administration/windows-commands/chkdsk
https://gitlab.com/demensdeum/slowride/