Category Archives: Техдок

Техническая документация

Исправляем медленную работу 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/

Пишем бэкенд сервер на C++ FCGI

Краткая заметка о том как я писал серверную часть для 3д редактора Cube Art Project, сервер должен сохранять и выводить работы пользователей веб версии, отдавая им короткие URL по кнопке сохранения. Сначала я хотел использовать Swift/PHP/Ruby/JS или какой-то подобный современный язык для бэкэнда, но посмотрев на характеристики моей VPS было принято решение написать сервер на C/C++.
Для начала нужно установить на сервере libfcgi и модуль поддержки fcgi для вашего вебсервера, пример для Ubuntu и Apache:

sudo apt install libfcgi libapache2-mod-fcgid

Далее настраиваем модуль в конфиге:

FcgidMaxProcessesPerClass – максимальное количество процессов на класс, я поставил 1 процесс так как не расчитываю на большую нагрузку.
AddHandler fcgid-script .fcgi – расширение файла с которым должен стартовать модуль fcgi.
Добавляем в конфиг папку из которой будут запускаться cgi приложения:

Далее пишем приложение на C/C++ с поддержкой fcgi, собираем его, и копируем в папку /var/www/html/cgi-bin.
Примеры кода и скрипта сборки:
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/cubeArtProjectServer.cpp
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/build.sh
После этого нужно будет перезапустить ваш вебсервер:

systemctl restart apache2

Далее проставьте необходимые права на выполение папки cgi-bin через chmod.
После этого ваша cgi программа должна работать через браузер по ссылке, пример для сервера Cube Art Project:
http://192.243.103.70/cgi-bin/cubeArtProject/cubeArtProjectServer.fcgi
Если что-то не получается, то смотрите логи вебсервера, либо подключайтесь дебаггером к запущенному процессу, процесс отладки не должен отличаться от процесса отладки обычного клиентского приложения.

Источники

https://habr.com/ru/post/154187/
http://chriswu.me/blog/writing-hello-world-in-fcgi-with-c-plus-plus/

Исходный код

https://gitlab.com/demensdeum/cube-art-project-server

Портируем C++ SDL приложение на Android

В данной заметке я опишу свой опыт портирования прототипа 3D редактора Cube Art Project на Android.
Сначала посмотрим на результат, в эмуляторе запущен редактор с 3D курсором куба красного цвета:

Для успешной сборки нужно было сделать следующее:

  1. Установить последний Android SDK и NDK (версию ндк чем свежее тем лучше).
  2. Загрузить исходный код SDL2, взять оттуда шаблон для сборки андроид приложения.
  3. Добавить SDL Image, SDL Mixer к сборке.
  4. Добавить библиотеки моего игрового движка и тулкита, их зависимости (GLM, JSON for Modern C++)
  5. Адаптировать файлы сборок для Gradle.
  6. Адаптировать C++ код для совместимости с Android, изменения коснулись платформозависимых компонентов (OpenGL ES, инициализация графического контекста)
  7. Собрать и проверить проект на эмуляторе.

Шаблон проекта

Загружаем исходники SDL, SDL Image, SDL Mixer:
https://www.libsdl.org/download-2.0.php
В папке docs есть подробная инструкция по работе с шаблоном андроид проекта; скопируем директорию android-project в отдельную папку, сделаем симлинк или скопируем папку SDL в android-project/app/jni.
Подставляем правильный идентификатор для флага avd, запускаем эмулятор андроида из директории Sdk:

cd ~/Android/Sdk/emulator
./emulator -avd Pixel_2_API_24

Указываем пути в скрипте, собираем проект:

rm -rf app/build || true
export ANDROID_HOME=/home/demensdeum/Android/Sdk/
export ANDROID_NDK_HOME=/home/demensdeum/Android/android-ndk-r21-beta2/
./gradlew clean build
./gradlew installDebug

Должен собраться шаблон проекта SDL с кодом на Си из файла

android-sdl-test-app/cube-art-project-android/app/jni/src/YourSourceHere.c

Зависимости

Загружаем исходный код в архивах для SDL_image, SDL_mixer:
https://www.libsdl.org/projects/SDL_image/
https://www.libsdl.org/projects/SDL_mixer/

Загружаем зависимости вашего проекта, для примера мои shared библиотеки:
https://gitlab.com/demensdeum/FlameSteelCore/
https://gitlab.com/demensdeum/FlameSteelCommonTraits
https://gitlab.com/demensdeum/FlameSteelBattleHorn
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkit/
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
https://gitlab.com/demensdeum/FSGL
https://gitlab.com/demensdeum/cube-art-project

Все это выгружаем в app/jni, каждый “модуль” в отдельную папку, например app/jni/FSGL. Далее у вас есть вариант найти рабочие генераторы для файлов Application.mk и Android.mk, я не нашел, однако возможно есть простое решение на основе CMake. Переходим по ссылкам и начинаем знакомиться с форматом файлов сборки для Android NDK:
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk

Также следует прочитать про разные APP_STL реализации в NDK:
https://developer.android.com/ndk/guides/cpp-support.html

После ознакомления создаем для каждого “модуля” файл Android.mk, далее пример файл сборки shared библиотеки Cube-Art-Project:

LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)

APP_STL := c++_static
APP_CPPFLAGS := -fexceptions
LOCAL_MODULE := CubeArtProject
LOCAL_C_INCLUDES := $(LOCAL_PATH)/src $(LOCAL_PATH)/../include $(LOCAL_PATH)/../include/FlameSteelCommonTraits/src/FlameSteelCommonTraits
LOCAL_EXPORT_C_INCLUDES = $(LOCAL_PATH)/src/

define walk
$(wildcard $(1)) $(foreach e, $(wildcard $(1)/*), $(call walk, $(e)))
endef

ALLFILES = $(call walk, $(LOCAL_PATH)/src)
FILE_LIST := $(filter %.cpp, $(ALLFILES))
$(info CubeArtProject source code files list)
$(info $(FILE_LIST))
LOCAL_SRC_FILES := $(FILE_LIST:$(LOCAL_PATH)/%=%)

LOCAL_SHARED_LIBRARIES += FlameSteelCore
LOCAL_SHARED_LIBRARIES += FlameSteelBattleHorn
LOCAL_SHARED_LIBRARIES += FlameSteelCommonTraits
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkit
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkitFSGL
LOCAL_SHARED_LIBRARIES += FSGL
LOCAL_SHARED_LIBRARIES += SDL2
LOCAL_SHARED_LIBRARIES += SDL2_image

LOCAL_LDFLAGS := -static-libstdc++
include $(BUILD_SHARED_LIBRARY)

Любой опытный CMake пользователь поймет этот конфиг с первых строк, форматы очень похожи, в Android.mk отсутствует GLOB_RECURSIVE, поэтому приходится рекурсивно искать исходные файлы с помощью функции walk.

Меняем Application.mk, Android.mk со-но для сборки C++ а не Си кода:

APP_ABI := armeabi-v7a arm64-v8a x86 x86_64
APP_PLATFORM=android-16
APP_STL := c++_static
APP_CPPFLAGS := -fexceptions

Переименовываем YourSourceHere.c -> YourSourceHere.cpp, grep’аем по вхождениям, меняем путь в сборке, например:

app/jni/src/Android.mk:LOCAL_SRC_FILES := YourSourceHere.cpp

Далее попробуйте собрать проект, если вы увидете ошибки от компилятора об отсутствии хидеров, то проверьте корректность путей в Android.mk; если ошибки будут от линковщика вида “undefined reference”, то проверьте корректность указания файлов исходного кода в сборках, оттрейсить списки можно через указание $(info $(FILE_LIST)) в Android.mk файле. Не забудьте о двойном механизме линковки, с помощью модулей в ключе LOCAL_SHARED_LIBRARIES и корректной линковке через LD, например для FSGL:

LOCAL_LDLIBS := -lEGL -lGLESv2

Адаптация и запуск

Пришлось поменять некоторые вещи, например убрать GLEW из сборок для iOS и Android, переименовать часть вызовов OpenGL, добавив постфикс EOS (glGenVertexArrays -> glGenVertexArraysOES), включать макрос отсутствующих модерновых функций дебага, вишенка на торте это неявный инклуд GLES2 хидеров с указанием макроса GL_GLEXT_PROTOTYPES 1:

#define GL_GLEXT_PROTOTYPES 1
#include "SDL_opengles2.h"

Также наблюдал черный экран на первых запусках с ошибкой вида “E/libEGL: validate_display:255 error 3008 (EGL_BAD_DISPLAY)”, поменял инициализацию окна SDL, профайла OpenGL и все заработало:

SDL_DisplayMode mode;
SDL_GetDisplayMode(0,0,&mode);
int width = mode.w;
int height = mode.h;

window = SDL_CreateWindow(
            title,
            0,
            0,
            width,
            height,
            SDL_WINDOW_OPENGL | SDL_WINDOW_FULLSCREEN | SDL_WINDOW_RESIZABLE
        );

SDL_GL_SetAttribute( SDL_GL_CONTEXT_PROFILE_MASK, SDL_GL_CONTEXT_PROFILE_ES );

На эмуляторе приложение по умолчанию устанавливается с иконкой SDL и именем “Game”.

Мне осталось исследовать возможность автоматической генерации файлов сборки на основе CMake, либо же мигрировать сборки для всех платформ на Gradle; однако CMake остается выбором дефакто для текущей разработки на C++.

Исходный код

https://gitlab.com/demensdeum/android-sdl-test-app
https://gitlab.com/demensdeum/android-sdl-test-app/tree/master/cube-art-project-android

Источники

https://developer.android.com/ndk/guides/cpp-support.html
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk
https://lazyfoo.net/tutorials/SDL/52_hello_mobile/android_windows/index.php
https://medium.com/androiddevelopers/getting-started-with-c-and-android-native-activities-2213b402ffff

Перевернутый мир

Для разработки нового проекта Cube Art Project взял на вооружение методологию разработки Test Driven Development. В данном подходе сначала реализуется тест для определенного функционала приложения, а затем уже реализуется конкретный функционал. Большим плюсом в данном подходе я считаю реализацию финальных интерфейсов, максимально непосвященных в детали реализации, до начала разработки функционала. При таком подходе тест диктует дальнейшую реализацию, добавляются все преимущества контрактного программирования, когда интерфейсы являются контрактами для конкретной реализации.
Cube Art Project – 3D редактор в котором пользователь строит фигуры из кубов, не так давно этот жанр был очень популярен. Так как это графическое приложение, то я решил добавить тесты с валидацией скриншотов.
Для валидирования скриншотов нужно получить их из OpenGL контекста, делается это с помощью функции glReadPixels. Описание аргументов функции простейшие – начальная позиция, ширина, высота, формат (RGB/RGBA/проч.), указатель на выходной буфер, любому работавшему с SDL или имеющему опыт с буферами данных в Си будет просто подставить нужные аргументы. Однако считаю необходимым описать интересную особенность выходного буфера glReadPixels, пиксели в нем хранятся снизу вверх, а в SDL_Surface все базовые операции происходят сверху вниз.
То есть загрузив референсный скриншот из png файла, я не смог сравнить два буфера в лоб, так как один из них был перевернутым.
Чтобы перевернуть выходной буфер из OpenGL вам нужно заполнить его отнимая высоту скриншота для координаты Y. Однако стоить учесть что есть шансы выйти за пределы буфера, если не отнять единицу во время заполнения, что приведет к memory corruption.
Так как я повсеместно стараюсь использовать ООП парадигму “программирования интерфейсами”, вместо прямого Си-подобного доступа к памяти по указателю, то при попытке записать данные за пределами буфера объект мне об этом сообщил благодаря валидации границ в методе.
Итоговый код метода получения скриншота в стиле сверху-вниз:

    auto width = params->width;
    auto height = params->height;

    auto colorComponentsCount = 3;
    GLubyte *bytes = (GLubyte *)malloc(colorComponentsCount * width * height);
    glReadPixels(0, 0, width, height, GL_RGB, GL_UNSIGNED_BYTE, bytes);

    auto screenshot = make_shared(width, height);

    for (auto y = 0; y < height; y++) {
        for (auto x = 0; x < width; x++) {
            auto byteX = x * colorComponentsCount;
            auto byteIndex = byteX + (y * (width * colorComponentsCount));
            auto redColorByte = bytes[byteIndex];
            auto greenColorByte = bytes[byteIndex + 1];
            auto blueColorByte = bytes[byteIndex + 2];
            auto color = make_shared(redColorByte, greenColorByte, blueColorByte, 255);
            screenshot->setColorAtXY(color, x, height - y - 1);
        }
    }

    free(bytes);

Источники

https://community.khronos.org/t/glreadpixels-fliped-image/26561
https://stackoverflow.com/questions/8346115/why-are-bmps-stored-upside-down

Исходный код

https://gitlab.com/demensdeum/cube-art-project-bootstrap

Longest Common Substring

В данной заметке я опишу алгоритм решения задачи наибольшей общей подстроки. Допустим мы пытаемся расшифровать зашифрованные бинарные данные, для начала попробуем найти общие паттерны с помощью поиска наибольшей подстроки.
Входная строка для примера:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Мы ищем повторяющуюся дважды строку:
DATAHEADER??

Префиксы

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

        val lhs = "asdfWUKI"
        val rhs = "asdfIKUW"

Результирующая строка – asdf
Пример на Kotlin:

fun longestPrefix(lhs: String, rhs: String): String {
        val maximalLength = min(lhs.length-1, rhs.length -1)
        for (i in 0..maximalLength) {
            val xChar = lhs.take(i)
            val yChar = rhs.take(i)
                if (xChar != yChar) {
                    return lhs.substring(0, i-1)
                }
        }
        return lhs.substring(0,maximalLength)
}

Brute Force

Когда не получается по хорошему, стоит прибегнуть к грубой силе. Используя метод longestPrefix пройдем по строке двумя циклами, первый берет строку от i до конца, второй от i + 1 до конца, передает их в поиск наибольшего префикса. Временная сложность данного алгоритма примерно равна O(n^2) ~ O(n*^3).
Пример на Kotlin:

fun searchLongestRepeatedSubstring(searchString: String): String {
        var longestRepeatedSubstring = ""
        for (x in 0..searchString.length-1) {
            val lhs = searchString.substring(x)
            for (y in x+1..searchString.length-1) {
                val rhs = searchString.substring(y)
                val longestPrefix = longestPrefix(lhs, rhs)
                if (longestRepeatedSubstring.length < longestPrefix.length) {
                    longestRepeatedSubstring = longestPrefix
                }
            }
        }
        return longestRepeatedSubstring
}

Суффиксный массив

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

adasDATAHEADER??

Суффиксный массив выглядит так:

adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?

Решаем сортировкой

Отсортируем суффиксный массив, затем пройдем по всем элементам циклом где в левой руке (lhs) текущий элемент, в правой (rhs) следующий и вычислим самый длинный префикс с помощью метода longestPrefix.
Пример на Kotlin:

fun searchLongestRepeatedSubstring(searchString: String): String {
    val suffixTree = suffixArray(searchString)
    val sortedSuffixTree = suffixTree.sorted()

    var longestRepeatedSubstring = ""
    for (i in 0..sortedSuffixTree.count() - 2) {
        val lhs = sortedSuffixTree[i]
        val rhs = sortedSuffixTree[i+1]
        val longestPrefix = longestPrefix(lhs, rhs)
        if (longestRepeatedSubstring.length < longestPrefix.length) {
            longestRepeatedSubstring = longestPrefix
        }
    }
    return longestRepeatedSubstring
}

Временная сложность алгоритма O(N log N), что гораздо лучше решения в лоб.

Источники

https://en.wikipedia.org/wiki/Longest_common_substring_problem

Исходный код

https://gitlab.com/demensdeum/algorithms

Insertion Sort, Merge Sort

Insertion Sort

Сортировка вставками – каждый элемент сравнивается с предыдущими по списку и элемент меняется местами с большим, если таковой имеется, в ином случае внутренний цикл сравнения останавливается. Так как элементы сортируются с первого по последний, то каждый элемент сравнивается с уже отсортированным списком, что *возможно* уменьшит общее время работы. Временная сложность алгоритма O(n^2), то есть идентична баббл сорту.

Merge Sort

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

["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Вывод алгоритма для многопоточного выполнения:

["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Временная сложность алгоритма O(n*log(n)), что немного лучше чем O(n^2)

Источники

https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort

Исходный код

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/insertionSort
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/mergeSort

Сортировка пузырьком на Erlang

Сортировка пузырьком это достаточно скучно, но становится интереснее если попробовать реализовать его на функциональном языке для телекома – Erlang.

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

На практике его использовать не стоит из-за большой временной сложности алгоритма – O(n^2); я реализовал его на языке Erlang, в императивном стиле, но если вам интересно то можете поискать лучшие варианты:

-module(bubbleSort).
-export([main/1]).

startBubbleSort([CurrentHead|Tail]) ->
    compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).

compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->   
    if
        CurrentHead < NextHead ->
            compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
        true ->
            compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
    end;
    
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
    if
        CurrentHead < NextHead ->
            OutputList = OriginalOutputList ++ [CurrentHead],
            compareHeads(NextHead, Tail, OutputList, OriginalList);
        true ->
            OutputList = OriginalOutputList ++ [NextHead],
            compareHeads(CurrentHead, Tail, OutputList, OriginalList)
    end;
  
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
    OutputList = OriginalOutputList ++ [CurrentHead],
    if
        OriginalList == OutputList ->
            io:format("OutputList: ~w~n", [OutputList]);
        true ->
            startBubbleSort(OutputList)
    end.
  
main(_) ->
    UnsortedList = [69,7,4,44,2,9,10,6,26,1],
    startBubbleSort(UnsortedList).

Установка и запуск

В Ubuntu Эрланг установить очень просто, достаточно в терминале набрать команду sudo apt install erlang. В данном языке каждый файл должен представлять из себя модуль (module), со списком функций которые можно использовать извне – export. К интересным особенностям языка относится отсутствие переменных, только константы, отсутствие стандартного синтаксиса для ООП (что не мешает использовать ООП техники), и конечно же параллельные вычисления без блокировок на основе модели акторов.

Запустить модуль можно либо через интерактивную консоль erl, запуская одну команду за другой, либо проще через escript bubbleSort.erl; Для разных случаев файл будет выглядеть по разному, например для escript необходимо сделать функцию main, из которой он будет стартовать.

Источники

https://www.erlang.org/
https://habr.com/ru/post/197364/

Исходный код

https://gitlab.com/demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl

Алгоритм лексикографического сравнения

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

Пример для языка Си можно посмотреть здесь:
https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c

Следует учитывать что сравнивать символы нужно в единой статичной кодировке, например в Swift я использовал посимвольное сравнение на UTF-32. Вариант сортировки массива с использованием memcmp сработает точно для однобайтовых символов, в остальных случаях (кодировки переменной длины) возможно порядок будет некорректен. Не исключаю возможности реализации на основе кодировок переменной длины, но скорее всего будет на порядок сложнее.

Временная сложность алгоритма в лучшем случае O(1), среднем и худшем O(n)

Источники

https://ru.wikipedia.org/wiki/Лексикографический_порядок

Исходники

https://gitlab.com/demensdeum/algorithms/blob/master/lexiCompare/lexiCompare.swift

Разработка игры для ZX Spectrum на C

Эта непутевая заметка посвящена разработке игры для старого компьютера ZX Spectrum на C. Давайте взглянем на красавца:

Он начал производится в 1982 году, и выпускался до 1992 года. Технические характеристики машины: 8-битный процессор Z80, 16-128кб памяти и прочие экстеншены, например звуковой чип AY-3-8910.

В рамках конкурса Yandex Retro Games Battle 2019 для данной машины я написал игру под названием Interceptor 2020. Так как учить ассемблер для Z80 времени не было, я решил разработать ее на языке Си. В качестве тулчейна я выбрал готовый набор – z88dk, который содержит компиляторы Си, и много вспомогательных библиотек для ускорения реализации приложений для Спектрума. Он также поддерживает множество других Z80 машин, например MSX, калькуляторов Texas Instruments.

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

Особенности установки

Установку z88dk следует проводить по мануалу из репозитория, однако для пользователей Ubuntu я хотел бы отметить особенность – если у вас уже установлены компиляторы для Z80 из deb пакетов, то следует их удалить, так как z88dk по умолчанию будет обращаться к ним из папки bin, из-за несовместимости версий тулчейн-компилятор вы скорее всего ничего не сможете собрать.

Hello World

Написать Hello World очень просто:

#include 

void main()
{
    printf("Hello World");
}

Собрать в tap файл еще проще:

zcc +zx -lndos -create-app -o helloworld helloworld.c

Для запуска используйте любой эмулятор ZX Spectrum с поддержкой tap файлов, например онлайн:
http://jsspeccy.zxdemo.org/

Рисуем на картинку на весь экран

tl;dr Картинки рисуются тайлами, тайлами размера 8×8 пикселей, сами тайлы встраиваются в шрифт спектрума, затем строкой из индексов печатается картинка.

Библиотека вывода спрайтов и тайлов sp1 выводит тайлы с помощью UDG. Картинка переводится в набор отдельных UDG (тайлы), затем собирается на экране с помощью индексов. Следует помнить что UDG используется для вывода текста, и если ваша картинка содержит очень большой набор тайлов (например больше 128 тайлов), то придется выходить за границы набора и стирать дефолтный спектрумовский шрифт. Чтобы обойти это ограничение, я использовал базу от 128 – 255 с помощью упрощения изображений, оставляя оригинальный шрифт на месте. Об упрощении картинок ниже.

Для отрисовки полноэкранных картинок нужно вооружиться тремя утилитами:
Gimp
img2spec
png2c-z88dk

Есть путь настоящих ZX мужчин, настоящих ретро-воинов это открыть графический редактор, используя палитру спектрума, зная особенности вывода картинки, подготовить ее вручную и выгрузить с помощью png2c-z88dk или png2scr.

Путь попроще – взять 32 битное изображение, переключить в Gimp количество цветов до 3-4-х, слегка подредактировать, затем импортировать в img2spec для того чтобы не работать с цветовыми ограничениями вручную, экспортировать png и перевести в Си массив с помощью png2c-z88dk.

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

В результате вы получите h файл, который содержит количество уникальных тайлов, если их больше ~128, то упрощайте в Gimp картинку (увеличьте повторяемость) и проводите процедуру экспорта по новой.

После экспорта вы в прямом смысле загружаете “шрифт” из тайлов и печатаете “текст” из индексов тайлов на экране. Далее пример из “класса” рендера:

// грузим шрифт в память
    unsigned char *pt = fullscreenImage->tiles;

    for (i = 0; i < fullscreenImage->tilesLength; i++, pt += 8) {
            sp1_TileEntry(fullscreenImage->tilesBase + i, pt);
    }

    // ставим курсор в 0,0
    sp1_SetPrintPos(&ps0, 0, 0);

    // печатаем строку
    sp1_PrintString(&ps0, fullscreenImage->ptiles);

Рисуем спрайты на экране

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

Рисуем в Gimp монохромную png картинку 16×16, далее с помощью png2sp1sprite переводим ее в ассемблерный файл asm, в Си коде объявляем массивы из ассемблерного файла, добавляем файл на этапе сборки.

После этапа объявления ресурса спрайта, его надо добавить на экран в нужную позицию, далее пример кода “класса” игрового объекта:

    struct sp1_ss *bubble_sprite = sp1_CreateSpr(SP1_DRAW_MASK2LB, SP1_TYPE_2BYTE, 3, 0, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2,    SP1_TYPE_2BYTE, col2-col1, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2RB,  SP1_TYPE_2BYTE, 0, 0);
    sp1_IterateSprChar(bubble_sprite, initialiseColour);

По названиям функций можно примерно понять смысл – аллоцируем память для спрайта, добавляем две колонки 8×8, добавляем цвет для спрайта.

В каждом кадре проставляется позиция спрайта:

sp1_MoveSprPix(gameObject->gameObjectSprite, Renderer_fullScreenRect, gameObject->sprite_col, gameObject->x, gameObject->y);

Эмулируем ООП

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

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

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

Также стоит отметить упрощение решения вопросов связанных с архитектурой приложения, ведь 80% архитектурных проблем было решено компьютерными-учеными еще в прошлом веке и описано в литературе посвященной паттернам проектирования. Далее я опишу способы добавить похожий на ООП синтаксис в Си.

За основу хранения данных экземпляра класса удобнее взять структуры Си. Конечно можно использовать байтовый буфер, создать свою собственную структуру для классов, методов, но зачем переизобретать колесо? Ведь мы и так переизобретаем синтаксис.

Данные класса

Пример полей данных “класса” GameObject:

struct GameObjectStruct {
    struct sp1_ss *gameObjectSprite;
    unsigned char *sprite_col;
    unsigned char x;
    unsigned char y;
    unsigned char referenceCount;
    unsigned char beforeHideX;
    unsigned char beforeHideY;
};
typedef struct GameObjectStruct GameObject;

Сохраняем наш класс как “GameObject.h” делаем #include “GameObject.h” в нужном месте и пользуемся.

Методы класса

Возьмем на вооружение опыт разработчиков языка Objective-C, сигнатура метода класса будут представлять из себя функции в глобальном скопе, первым аргументом всегда будет передаваться структура данных, далее идут аргументы метода. Далее пример “метода” “класса” GameObject:

void GameObject_hide(GameObject *gameObject) {
    gameObject->beforeHideX = gameObject->x;
    gameObject->beforeHideY = gameObject->y;
    gameObject->y = 200;
}

Вызов метода выглядит так:

GameObject_hide(gameObject);

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

Работа с памятью

Ручное управление памятью вида с помощью malloc и free обернутых в макросы new и delete для соответствия с C++:

#define new(X) (X*)malloc(sizeof(X))
#define delete(X) free(X)

Для объектов которые используются несколькими классами сразу, реализовано полу-ручное управление памятью на основе подсчета ссылок, по образу и подобию старого механизма Objective-C Runtime ARC:

void GameObject_retain(GameObject *gameObject) {
    gameObject->referenceCount++;
}

void GameObject_release(GameObject *gameObject) {
    gameObject->referenceCount--;

    if (gameObject->referenceCount < 1) { sp1_MoveSprAbs(gameObject->gameObjectSprite, &Renderer_fullScreenRect, NULL, 0, 34, 0, 0);
        sp1_DeleteSpr(gameObject->gameObjectSprite);
        delete(gameObject);
    }
}

Таким образом каждый класс должен объявлять использование общего объекта с помощью retain, освобождать владение через release. В современном варианте ARC используется автоматическое проставление вызовов retain/release.

Звучим!

На Спектруме есть пищалка способная воспроизводить 1-битовую музыку, композиторы того времени умели воспроизводить на ней до 4-х звуковых каналов одновременно.

Spectrum 128k содержит отдельный звуковой чип AY-3-8910, на котором можно воспроизводить трекерную музыку.

Для использования пищалки в z88dk предлагается библиотека

Что предстоит узнать

Мне было интересно ознакомиться со Спектрумом, реализовать игру средствами z88dk, узнать много интересных вещей. Многое мне еще предстоит изучить, например ассемблер Z80, так как он позволяет использовать всю мощь Спектрума, работу с банками памяти, работу со звуковым чипом AY-3-8910. Надеюсь поучаствовать в конкурсе на следующий год!

Ссылки

https://rgb.yandex
https://vk.com/sinc_lair
https://www.z88dk.org/forum/

Исходный код

https://gitlab.com/demensdeum/zx-projects/tree/master/interceptor2020

Двоичный поиск

Допустим нам необходимо узнать относится ли адрес электронной почты “demensdeum@gmail.com”  к списку разрешенных email адресов для получения писем.

Переберем весь список от первого до последнего элемента, проверяя равен ли элемент указанному адресу – реализуем алгоритм линейного поиска. Но это же будет долго, или не будет?

Для ответа на этот вопрос используют “Временную сложность алгоритмов”, “О” нотацию. Время работы линейного поиска в худшем случае равно n-му количеству элементов массива, напишем это в “О” нотации – O(n). Далее нужно пояснить что для любого известного алгоритма есть три показателя производительности – время выполнения в лучшем, худшем и среднем случае. Например адрес почты “demensdeum@gmail.com” находится в первом индексе массива, тогда он будет найден за первый шаг алгоритма, из этого следует что время выполнения в лучшем случае – O(1); а если в конце списка, то это худший случай – O(n)

Но как же детали реализации ПО, производительность железа, они ведь должны влиять на big O? А теперь выдохните и представьте что расчет временной сложности рассчитывается для некой абстрактной идеальной машины, в которой есть только этот алгоритм и больше ничего.

Алгоритм

Ок, получается что линейный поиск достаточно медленный, попробуем использовать Бинарный поиск. Для начала следует пояснить что с бинарными данными мы работать не будем, такое название данному методу дано из-за особенностей его работы. Изначально мы сортируем массив в лексикографическом порядке, затем алгоритм берет диапазон всего массива, получает средний элемент диапазона, сравнивает его лексикографически, и в зависимости от результата сравнения решает какой диапазон брать для поиска дальше – верхнюю половину текущего или нижнюю. То есть на каждом шаге поиска принимается решение из двух возможных – бинарная логика. Этот шаг повторяется до тех пор, пока либо слово найдется, либо не найдется (произойдет пересечение нижнего и верхних индексов диапазона).

Производительность данного алгоритма – лучший случай когда сразу найден элемент в середине массива O(1), худший случай перебора O(log n)

Подводные камни

При реализации бинарного поиска я встретился мало того с интересной проблемой отсутствия стандартизации лексикографического сравнения в библиотеках языков программирования, но даже обнаружил отсутствие единого стандарта реализации localeCompare внутри JavaScript. Стандарт ECMAScript допускает разную реализацию данной функции, из-за этого при сортировке с помощью localeCompare, на разных движках JavaScript может наблюдаться абсолютно разный результат.

Поэтому для корректной работы алгоритма нужно обязательно сортировать и использовать в работе только один и тот же алгоритм лексикографического сравнения, иначе работать ничего не будет. Со-но если например попытаться сортировать массив в Scala, а искать с помощью nodejs, не реализуя собственную сортировку/сортировку одной реализации, то кроме разочарования в человечестве вас ничего не ждет.

Источники

Что такое лексикографическое сравнение и что оно собой представляет?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript

Исходный код

https://gitlab.com/demensdeum/algorithms

Паттерн Фасад


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

Источники

https://refactoring.guru/ru/design-patterns/facade
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612

Паттерн Абстрактная Фабрика

Абстрактная фабрика – предоставляет интерфейс создания связанных объектов, без указания конкретных классов.

Мне большие нравится альтернативное название данного паттерна – Набор (Kit)

Он очень похож на Фабричный Метод, однако Абстрактные Фабрики должны описывать связь между создаваемыми объектами, иначе это уже просто антипаттерн God Object, создающий бессистемно все подряд.

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

При этом нам нужна возможность кастомизировать внешний вид и поведение контролов AR окружения. Вот именно для этого случая нужно использовать паттерн Набор.

Напишем интерфейс Абстрактной Фабрики и Абстрактных Продуктов – родительских протоколов, элементов AR окружения:

protocol ARFactory {
    func arrow() -> ARArrow
    func icon() -> ARIcon
    func button() -> ARButton
    func window() -> ARWindow
}

protocol ARArrow {
    var image: { get }
    func handleSelection()
}

protocol ARIcon {
    var image: { get }
    var title: String
}

protocol ARButton {
    var title: String
    func handleSelection()
}

protocol ARWindow {
    var title: String
    var draw(canvas: Canvas)
}

Теперь разработчикам наборов нужно будет реализовать Конкретную Фабрику на основе интерфейса Абстрактной Фабрики, причем реализовать придется все элементы вместе, остальные части приложения смогут работать с фабрикой не меняя свой код.

Источники

https://refactoring.guru/ru/design-patterns/abstract-factory
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612

Фабричный Метод

Паттерн Фабричный Метод относится к порождающим паттернам проектирования.
Данный паттерн описывает создание интерфейса для создания объекта конкретного класса. Вроде просто да?

В теории

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

protocol Product {
 var name: String { get }
 var image: Image { get }
 var executablePath: String { get }
}

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

Напишем этот интерфейс – интерфейс Создателя, содержащий Фабричный Метод, отдающий массив Продуктов.

protocol Creator {
 func factoryMethod() -> [Product]
}

На практике

Первым клиентом нашего AR фреймворка стала компания 7Б – ведущий поставщик софта для кофеварок в Гондурасе. Они хотят продавать очки дополненной реальности с возможностью заваривать кофе, проверять заполненность воды/зерен, указывать дорогу к их ближайшей кофеварке в режиме indoor карт.

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

После передачи документации, компания 7Б используя интерфейс Создателя реализует Конкретного Создателя – класс возвращающий массив приложений-значков. Сами приложения-значки представляют из себя классы Конкретного Продукта имплементирующие интерфейс Продукта.

Пример кода Конкретных Продуктов:

class CoffeeMachineLocator: implements Product {
 let name = “7B Coffee Machine Locator v.3000”
 let image = Image.atPath(“images/locator.tga”)
 let executablePath = “CoffeeMachineLocator.wasm”
}

class iPuchinno: implements Product {
 let name = “iPuchinno 1.0.3”
 let image = Image.atPath(“images/puchino.pvrtc”)
 let executablePath = “neutron/ipuchBugFixFinalNoFreezeFixAlpha4.js”
}

Класс Конкретного Создателя, отдающий массив из двух приложений:

class 7BAppsCreator: implements Creator {
 func factoryMethod() -> [Product] {
  return [CoffeeMachineLocator(), iPuchinno()]
 }
}

После этого компания 7Б компилирует библиотеку Конкретных Продуктов, Конкретного Создателя и совмещает ее с нашим фреймворком, начинает продавать AR очки для своих кофеварок, доработок с нашей стороны не потребуется.

Источники

https://refactoring.guru/ru/design-patterns/command
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612

Паттерн Команда

Паттерн Команда относится к поведенческим паттернам проектирования.

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

Итак, в GoF применимость описывается достаточно лаконично и понятно:
Инкапсулирует запрос как объект, позволяя настраивать (parameterize) клиентов с разными запросами, использовать очереди, логировать запросы и осуществлять операции отмены.

Теперь реализуем простой вариант команды из описания:

string fakeTrumpsRequest = “SELECT * from Users where name beginsWith DonaldTrump”

Мы инкапсулировали запрос в объект класса строки, ей можно настраивать клиентов, добавлять команды в очередь, логировать, осуществлять отмену (с использованием паттерна “Снимок”)

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

Матчасть

Паттерн команда начинается с протокола Команды, который содержит единственный метод execute(). Дальше идет Конкретная Команда и Ресивер, КК реализует операцию над Ресивером, описывает связь между Ресивером и действием. Ничего непонятно? Мне тоже, но поехали дальше. Клиент создает экземпляр Конкретной Команды, связывает ее с Ресивером. Инвокер – объект который осуществляет процесс запуска Команды.

Теперь попробуем разобраться на примере, допустим мы хотим обновить myOS на телефоне myPhone, для этого мы запускаем приложение myOS_Update!, в нем нажимаем кнопку Update Now!, через 10 секунд система сообщит об успешном обновлении.

Клиентом в примере выше выступает приложение myOS_Update!, Инвокер это кнопка “Update Now!”, он запускает Конкретную Команду обновления системы с помощью метода execute(), которая обращается к Ресиверу – демону обновления операционной системы.

Пример использования

Допустим UI приложения myOS_Update! настолько хорош, что его решили продавать как отдельный продукт для предоставления интерфейса обновления других операционных систем. В таком случае мы реализуем приложение с поддержкой расширения через библиотеки, в библиотеках будут реализации Конкретных Команд, Ресиверов, оставим статичные/неизменяемые Инвокер, Клиент, протокол Команды.

Таким образом отпадает необходимость в осуществлении поддержки изменяемого кода, так как наш код останется неизменным, проблемы могут возникнут лишь при реализации на стороне клиентов, из-за ошибок в коде их Конкретных Команд и Ресиверов. Также в такой реализации отсутствует необходимость передавать исходный код основного приложения, то есть мы осуществили инкапсуляцию команд и взаимодействия UI с помощью паттерна Команда.

Источники

https://refactoring.guru/ru/design-patterns/command
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612

Сборка macOS приложений под Ubuntu OSXCross CMake

В этой заметке я опишу сборку кросплатформенных C++ приложений для macOS на сборочной машине Ubuntu с использованием CMake и osxcross.
Для начала устанавливаем тулчейн osxcross:
https://github.com/tpoechtrager/osxcross
Установка происходит в 3 этапа, загрузка зависимостей:

cd tools
./get_dependencies.sh

Загрузка XCode.xip с официального сайта Apple, далее выгрузка SDK из XCode:

./gen_sdk_package_pbzx.sh /media/demensdeum/2CE62A79E62A4404/LinuxSupportStorage/xcode111.xip

Надеюсь вы прочитали лицензионное соглашение XCode на прошлом шаге? Далее сборка тулчейна с нужным префиксом:

INSTALLPREFIX=/home/demensdeum/Apps/osxcross ./build.sh

Теперь можно пользоваться osxcross из директории-префикса прошлого шага. Добавим новый макрос сборки для CMake, пропишем все необходимо:

if (OSXCROSS)
SET(CMAKE_SYSTEM_NAME Darwin)
SET(CMAKE_C_COMPILER o64-clang)
SET(CMAKE_CXX_COMPILER o64-clang++)
SET(CMAKE_C_COMPILER_AR x86_64-apple-darwin19-ar)
SET(CMAKE_CXX_COMPILER_AR x86_64-apple-darwin19-ar)
SET(CMAKE_LINKER x86_64-apple-darwin19-ld)
SET(ENV{OSXCROSS_MP_INC} 1)
endif()

Динамическая линковка мне не удалась, поэтому экспортируем библиотеки статически:

if (OSXCROSS)
add_library(FlameSteelCore STATIC ${SOURCE_FILES})
else()

Далее вы можете столкнуться с фактом того что у вас нет необходимых библиотек для osxcross, с этим я встретился при использовании SDL2. osxcross поддерживает готовые пакеты библиотек – macports. Для примера установка SDL2-mixer:

osxcross-macports -v install libsdl2_mixer

После этого можно приступать к сборке библиотек/приложений как обычно в связке cmake-make, не забудьте прописать статическую линковку библиотек если необходимо.

Ручная сборка библиотек

На текущий момент я встретился с проблемой некорректной архивации библиотек при статической линковке, при сборке итогового приложения получаю ошибку:

file was built for archive which is not the architecture being linked (x86_64)

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

ar x ../libFlameSteelCore.a
rm ../libFlameSteelCore.a
x86_64-apple-darwin19-ar rcs ../libFlameSteelCore.a *.o

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

Источники

https://github.com/tpoechtrager/osxcross

Сборка для Windows под Ubuntu MinGW CMake

В данной заметке я опишу процесс сборки библиотек и приложений для Windows с помощью тулчейна MinGW32 на Ubuntu.
Установим wine, mingw:

sudo apt-get install wine mingw-w64

После этого уже можно собирать C/C++ приложения под Windows:

# C
i686-w64-mingw32-gcc helloWorld.c -o helloWorld32.exe      # 32-bit
x86_64-w64-mingw32-gcc helloWorld.c -o helloWorld64.exe    # 64-bit
 
# C++
i686-w64-mingw32-g++ helloWorld.cc -o helloWorld32.exe     # 32-bit
x86_64-w64-mingw32-g++ helloWorld.cc -o helloWorld64.exe   # 64-bit

Собранные exe можно проверить с помощью wine.

Далее рассмотрим изменения сборки CMake, файла CMakeLists.txt, добавляем MinGW специфичные вещи к файлу сборки:

if (MINGW32)
set(CMAKE_SYSTEM_NAME Windows)
SET(CMAKE_C_COMPILER i686-w64-mingw32-gcc)
SET(CMAKE_CXX_COMPILER i686-w64-mingw32-g++)
SET(CMAKE_RC_COMPILER i686-w64-mingw32-windres)
set(CMAKE_RANLIB i686-w64-mingw32-ranlib)
endif()

// для сборки shared dll
elseif (MINGW32)
add_library(FlameSteelEngineGameToolkit.dll SHARED ${SOURCE_FILES})
else()

// обязательно линкуем со всеми зависимостями
if (MINGW32)
target_link_libraries(
                        FlameSteelEngineGameToolkit.dll 
                        -static-libgcc
                        -static-libstdc++
                        SDL2 
                        SDL2_mixer 
                        /home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCore/FlameSteelCore.dll
                        /home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelBattleHorn/FlameSteelBattleHorn.dll
                        /home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCommonTraits/FlameSteelCommonTraits.dll)

set_target_properties(FlameSteelEngineGameToolkit.dll PROPERTIES
        PREFIX ""
        SUFFIX ""
        LINK_FLAGS "-Wl,--add-stdcall-alias"
        POSITION_INDEPENDENT_CODE 0 # this is to avoid MinGW warning; 
        # MinGW generates position-independent-code for DLL by default
)
else()

Собираем:

cmake -DMINGW32=1 .
make

На выходе будет dll или exe, смотря что вы собираете. За рабочим примером можете смотреть в репозиторий нового проекта Cube-Art-Project и его библиотеки:
https://gitlab.com/demensdeum/cube-art-project
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
https://gitlab.com/demensdeum/cube-art-project-bootstrap

Источники
https://arrayfire.com/cross-compile-to-windows-from-linux/

Простой Emscripten автотест для ChromeDriver

В данной заметке я опишу реализацию запуска автотеста для ChromeDriver браузера Chrome, который запускает транслированный из C++ автотест модуля с помощью Emscripten, считывает вывод консоли и возвращает результат проверки.
Для начала нужно установить selenium, для питона3-убунту это делается так:

pip3 install selenium

Далее скачиваем ChromeDriver с официального сайта, кладем chromedriver например в /usr/local/bin, после этого можно приступать к реализации автотеста.
Ниже я приведу код автотеста, который запускает браузер Chrome с открытой страницей автотеста на Emscripten, проверяет наличие текста “Window test succeded”:

import time
from selenium import webdriver
from selenium.webdriver.common.keys import Keys
from selenium.webdriver.common.desired_capabilities import DesiredCapabilities

capabilities = DesiredCapabilities.CHROME
capabilities['goog:loggingPrefs'] = { 'browser':'ALL' }
driver = webdriver.Chrome()
driver.get("http://localhost/windowInitializeTest/indexFullscreen.html")

time.sleep(2)

exitCode = 1

for entry in driver.get_log('browser'):
    if entry["source"] == "console-api":
        message = entry["message"]
        if "Window test succeded" in message:
            print("Test succeded")
            exitCode = 0

driver.close()
exit(exitCode)

Сохраняем тест как main.py и запускаем python3 main.py

Сборка проекта с зависимостями для Emscripten

В этой заметке я опишу сборку проекта состоящего из нескольких библиотек с помощью Emscripten.
На данный момент Emscripten не поддерживает сборку shared библиотек, поэтому первым делом переводим все библиотеки из Shared в Static. Emscripten работает со своими include файлами, поэтому нужно решить вопрос с видимостью заголовочных файлов, я решил это с помощью проброса симлинка из системной директории в тулчейн Emscripten:

ln -s /usr/local/include/FlameSteelFramework $EMSDK/fastcomp/emscripten/system/include/FlameSteelFramework

Если вы используете CMake, то нужно поменять SHARED->STATIC в CMakeLists.txt файле метода add_library. Собрать библиотеку/приложение для дальнейшей статической линковки можно с помощью команд:

emcmake cmake .
emmake make

Далее нужно будет собрать основное приложение с указанием *.a файлов библиотек на этапе линковки. Относительный путь указать мне не удалось, сборка завершилась корректно только после указания полных путей в файле CMakeLists.txt:

elseif(EMSCRIPTEN)
target_link_libraries(${FSEGT_PROJECT_NAME} GL GLEW 
/home/demensdeum/Sources/cube-art-project-bootstrap/cube-art-project/sharedLib/libCubeArtProject.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelEngineGameToolkitFSGL/libFlameSteelEngineGameToolkitFSGL.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelEngineGameToolkit/libFlameSteelEngineGameToolkit.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCore/libFlameSteelCore.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelBattleHorn/libFlameSteelBattleHorn.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FSGL/libFSGL.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCommonTraits/libFlameSteelCommonTraits.a)
else()

Источники

https://emscripten.org/docs/compiling/Building-Projects.html#using-libraries

Shared Library CMake C++

Недавно решил сделать все части FlameSteelFramework отдельными shared библиотеками, далее покажу пример CMakeLists.txt файла для FlameSteelCore:

cmake_minimum_required(VERSION 3.5)

project (FlameSteelCore)
set(CMAKE_BUILD_TYPE Release)

include_directories(${CMAKE_CURRENT_SOURCE_DIR}/src)

file(GLOB_RECURSE SOURCE_FILES
    "src/FlameSteelCore/*.cpp"
)

add_library(FlameSteelCore SHARED ${SOURCE_FILES})

install(DIRECTORY "${CMAKE_SOURCE_DIR}/src/FlameSteelCore"
        DESTINATION include/FlameSteelFramework
        FILES_MATCHING
        PATTERN "*.h"
)

install(TARGETS FlameSteelCore DESTINATION lib)

Команды которые выполняет CMake: собирает все файлы с расширением *.cpp из директории src/FlameSteelCore/ в shared library, копирует все хидеры с расширением *.h из src/FlameSteelCore в include/FlameSteelFramework (в моем случае это /usr/local/include/FlameSteelFramework), копирует shared lib в директорию lib (/usr/local/lib)
После установки возможно будет необходимо обновить кэш LD – sudo ldconfig.
Для сборки и установки на Ubuntu (при наличии корректного тулчейна сборки) достаточно выполнить команды:

cmake . && make && sudo make install

Для проверки процесса установки я передаю make prefix в локальную папку makeInstallTestPlayground:

cmake -DCMAKE_INSTALL_PREFIX:PATH=/home/demensdeum/makeInstallTestPlayground . && make && make install

References

https://stackoverflow.com/questions/17511496/how-to-create-a-shared-library-with-cmake
https://stackoverflow.com/questions/6003374/what-is-cmake-equivalent-of-configure-prefix-dir-make-all-install

Интерпретатор языка C++ – Cling

Не так давно наткнулся на один интересный проект под названием Cling, интерпретатор языка C++, который может работать в интерактивном режиме из консоли в том числе. Ознакомиться с проектом можно по ссылке: https://github.com/root-project/cling
Установка для Ubuntu простейшая – скачать архив для нужно версии, распаковать, зайти в папку bin и запустить cling в терминале.
Далее пример загрузки библиотеки FlameSteelCore, инициализация объекта, распечатка id:

Потерянные исключения Emscripten и проблемы regex

Потерянные exception

Интересная особенность Emscripten, при запуске игрового цикла через emscripten_set_main_loop, следует помнить о том что хэндлинг исключений должен быть заново добавлен через try catch прямо в методе цикла, т.к. рантайм теряет блок try catch извне.
Проще всего выводить текст ошибки силами браузера, используя javascript alert:

            catch (const std::exception &exc)
            {
                const char *errorText = exc.what();
                cout << "Exception: " << errorText << "; Stop execution" << endl;

                EM_ASM_(
                {
                    var errorText = UTF8ToString($0);
                    alert(errorText);

                }, errorText);

                abort();

Слишком сложный regexp

Релизация regex в std может кинуть исключение error_complexity, если посчитает регулярное выражение слишком сложным. Такое происходит в текущей реализации emscripten, так что предлагаю вам реализовать тесты для парсинга через регулярки, либо использовать сторонние реализации regex.

Паттерн Строитель

Паттерн Строитель относится к группе паттернов существование которых мне не особо понятно, отмечаю явную избыточность сего. Относится к группе порождающих паттернов проектирования. Используется для реализации простого интерфейса создания комплексных объектов.

Применимость

Упрощение интерфейса. Он может облегчить создание объекта в конструкторах с большим числом аргументов, объективно улучшить читаемость кода.

Пример на C++ без строителя:

auto weapon = new Weapon(“Claws”);
monster->weapon = weapon;
auto health = new MonsterHealth(100);
monster->health = health;

Пример со строителем на C++:

                  .addWeapon(“Claws”)
                  .addHealth(100)
                  .build();

Однако в языках поддерживающих именованные аргументы (named arguments), необходимость использовать именно для этого случая отпадает.

Пример на Swift с использованием named arguments:

let monster = Monster(weapon: “Claws”, health: 100)

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

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

Критика

Конечно нужно *хорошенько* подумать стоит ли налаживать повсеместное использование паттерна в своем проекте. Языки с современным синтаксисом и продвинутым IDE нивелируют необходимость в использовании Строителя, в плане улучшения читаемости кода (см, пункт про именованные аргументы)
Нужно ли было использовать данный паттерн в 1994 году, на момент выпуска книги GoF? Скорее всего да, однако, судя по Open source кодовой базе тех лет, мало кто им пользовался.

Источники

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

Паттерн Композит

Паттерн Композит относится к структурным паттернам проектирования, в отечественных источниках он известен как “Компоновщик”.
Допустим мы разрабатываем приложение – фотоальбом. Пользователь может создавать папки, добавлять туда фото, производить прочие манипуляции. Обязательно нужна возможность показывать количество файлов в папках, общее количество всех файлов и папок.
Очевидно что нужно использовать дерево, но как реализовать архитектуру древа, с простым и удобным интерфейсом? На помощь приходит паттерн Композит.

Sheila in Moonducks

Далее в Directory реализуем метод dataCount() – путем прохода по всем элементам лежащим в массиве компонентов, сложив все их dataCount’s.
Все готово!
Ниже пример на Go:
package main

import "fmt"

type component interface {

dataCount() int

}

type file struct {

}

type directory struct {

c []component

}

func (f file) dataCount() int {

return 1

}

func (d directory) dataCount() int {

var outputDataCount int = 0

for _, v := range d.c {
outputDataCount += v.dataCount()
}

return outputDataCount

}

func (d *directory) addComponent(c component) {

d.c = append(d.c, c)

}

func main() {

var f file
var rd directory
rd.addComponent(f)
rd.addComponent(f)
rd.addComponent(f)
rd.addComponent(f)

fmt.Println(rd.dataCount())

var sd directory
sd.addComponent(f)

rd.addComponent(sd)
rd.addComponent(sd)
rd.addComponent(sd)

fmt.Println(sd.dataCount())
fmt.Println(rd.dataCount())

}

Источники

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

Паттерн Адаптер

Benjamín Núñez González

Паттерн Адаптер относится к структурным паттернам проектирования.

Адаптер обеспечивает конвертацию данных/интерфейсов между двумя классами/интерфейсами.

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

Как все опытные разработчики, мы находим готовую нейросеть которая умеет классифицировать виды обезьян в клетке по видеопотоку, которую любезно выложил в свободный доступ зоологический институт берлинского зоопарка, переучиваем ее на видеопотоке из магазина и получаем рабочую state-of-the-art систему.

Есть лишь небольшая проблема – видеопоток закодирован в формате mpeg2, а наша система поддерживает только OGG Theora. Исходного кода системы у нас нет, единственное что мы можем делать – менять датасет и обучать нейросеть. Что же делать? Написать класс-адаптер, который будет переводит поток из mpeg2 -> OGG Theora и отдавать в нейросеть.

По классической схеме в паттерне участвуют client, target, adaptee и adapter. Клиент в данном случае это нейросеть, получающая видеопоток в OGG Theora, таргет – интерфейс с которым она взаимодействует, adaptee – интерфейс отдающий видеопоток в mpeg2, адаптер – конвертирует mpeg2 в OGG Theora и отдает по интерфейсу target.

Вроде все просто?

Источники

https://ru.wikipedia.org/wiki/Адаптер_(шаблон_проектирования)
https://refactoring.guru/ru/design-patterns/adapter

Паттерн Делегат

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


// псевдокод

class BarbershopScreen {
   let calendar: Calendar

   func showBarbersList(date: Date) {
      showSelectionSheet(barbers(forDate: date))
   }
}

class Calendar {
    let screen: BarbershopScreen

    func handleTap(on date: Date) {
        screen.showBarbersList(date: date)
    }
}

Через несколько дней требования меняются, перед выводом списка нужно показывать предложения с выбором услуг (стрижка бороды и т.п.) но не всегда, во все дни кроме субботы.
Добавляем в календарь проверку суббота сегодня или нет, в зависимости от нее вызываем метод списка барберов или списка услуг, для наглядности продемонстрирую:


// псевдокод

class BarbershopScreen {
   let calendar: Calendar

   func showBarbersList(date: Date) {
      showSelectionSheet(barbers(forDate: date))
   }

   func showOffersList() {
      showSelectionSheet(offers)
   }
}

class Calendar {
    let screen: BarbershopScreen

    func handleTap(on date: Date)  {
        if date.day != .saturday {
             screen.showOffersList()
        }
        else {
             screen.showBarbersList(date: date)
        }
    }
}

Через неделю нас просят добавить календарь на экран обратной связи, и в этот момент случается первое архитектурное ой!
Что же делать? Календарь ведь связан намертво с экраном записи на стрижку.
ух! уф! ой-ой
Если продолжить работать с такой бредовой архитектурой приложения, то следует сделать копию всего класса календаря и связать эту копию с экраном обратной связи.
Ок вроде хорошо, далее мы добавили еще несколько экранов и несколько копий календаря, и тут наступил момент икс. Нас попросили изменить дизайн календаря, тоесть теперь нужно найти все копии календаря и добавить одинаковые изменения во все. Такой “подход” очень сказывается на скорости разработки, увеличивает шанс допустить ошибку. В итоге такие проекты оказываются в состоянии разбитого корыта, когда уже даже автор оригинальной архитектуры не понимает как работают копии его классов, прочие хаки добавленные по пути разваливаются на лету.
Что же нужно было делать, а лучше что еще не поздно начать делать? Использовать паттерн делегирования!
Делегирование это способ передавать события класса через общий интерфейс. Далее пример делегата для календаря:

protocol CalendarDelegate {
   func calendar(_ calendar: Calendar, didSelect date: Date)
}

Теперь добавим код работу с делегатом в код примера:


// псевдокод

class BarbershopScreen: CalendarDelegate {
   let calendar: Calendar

   init() {
       calendar.delegate = self
   }

   func calendar(_ calendar: Calendar, didSelect date: Date) {
        if date.day != .saturday {
            showOffersList()
        }
        else {
             showBarbersList(date: date)
        }
   }

   func showBarbersList(date: Date) {
      showSelectionSheet(barbers(forDate: date))
   }

   func showOffersList() {
      showSelectionSheet(offers)
   }
}

class Calendar {
    weak var delegate: CalendarDelegate

    func handleTap(on date: Date)  {
        delegate?.calendar(self, didSelect: date)
    }
}

В итоге мы отвязали календарь от экрана совсем, при выборе даты из календаря он передает событие выбора даты – *делегирует* обработку события подписчику; подписчиком выступает экран.
Какие преимущества мы получаем в таком подходе? Теперь мы можем менять календарь и логику экранов независимо друг от друга, не дублируя классы, упрощая дальнейшую поддержку; таким образом реализуется “принцип единственной ответственности” реализации компонентов системы, соблюдается принцип DRY.
При использовании делегирования можно добавлять, менять логику вывода окошек, очередности чего угодно на экране и это совершенно не будет затрагивать календарь и прочие классы, которые объективно и не должны участвовать в несвязанных напрямую с ними процессами.
Альтернативно, не особо утруждающие себя программисты, используют отправку сообщений через общую шину, без написания отдельного протокола/интерфейса делегата, там где лучше было бы использовать делегирование. О недостатках такого подхода я написал в прошлой заметке – “Паттерн Наблюдатель”.

Источники

https://refactoring.guru/ru/replace-inheritance-with-delegation

Паттерн Наблюдатель

Паттерн Наблюдатель (Observer) относится к поведенческим паттернам проектирования.
Паттерн позволяет отправлять изменение состояния объекта подписчикам, с использованием общего интерфейса.
Допустим мы разрабатываем мессенджер для программистов, у нас в приложении есть экран чата. При получении сообщения с текстом “проблема” и “ошибка” или “что-то не так”, нужно красить экран списка ошибок и экран настроек в красный цвет.
Далее я опишу 2 варианта решения задачи, первый простой но крайне сложный в поддержке, и второй гораздо стабильнее в поддержке, но требует включать голову при начальной реализации.

Общая шина

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

  1. Объект отправляет абстрактное сообщение в общую шину
  2. Другой объект подписанный на общую шину, ловит сообщение и решает обработать его или нет.

Один из вариантов реализации доступный у Apple (подсистема NSNotificationCenter), добавлен матчинг заголовка сообщения на имя метода, который вызывается у получателя при доставке.
Самый большой минус такого подхода – при дальнейшем изменении сообщения нужно будет сначала вспомнить, а затем вручную отредактировать все места где оно обрабатывается, отправляется. Налицо случай быстрой первичной реализации, дальнейшей долгой, сложной поддержки, требующей базы знаний для корректной работы.

Мультикаст делегат

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

Источники

https://refactoring.gu/ru/design-patterns/observer

Паттерн Прокси

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

class InternetRouter {

    private let internet: Internet

    init(internet: Internet) {
        self.internet = internet
    }

    func handle(request: Request, from client: Client) -> Data {
        return self.internet.handle(request)
    }

}

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

Используя паттерн Прокси и антипаттерн синглтон, добавим функционал логирования имени клиента и URL:

class InternetRouterProxy {

    private let internetRouter: InternetRouter

    init(internet: Internet) {
        self.internetRouter = InternetRouter(internet: internet)
    }

    func handle(request: Request, from client: Client) -> Data {

        Logger.shared.log(“Client name: \(client.name), requested URL: \(request.URL)”)

        return self.internetRouter.handle(request: request, from: client)
    }

}

Из-за сохранения оригинального интерфейса InternetRouter в классе прокси InternetRouterProxy, достаточно заменить класс инициализации с InternerRouter на его прокси, больше изменений в кодовой базе не потребуется.

Источники

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

Паттерн Прототип

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

fun didPressOnCopyProfileButton() {
    let profileCopy = new Profile()
    profileCopy.name = generateRandomName()
    profileCopy.age = profile.age
    profileCopy.photos = profile.photos.randomize()
    storage.save(profileCopy)
}

Теперь представим что другие члены команды сделали copy-paste кода копирования или придумали его с нуля, и после этого добавилось новое поле – likes. В данном поле хранится количество лайков профиля, теперь нужно обновить *все* места где происходит копирование вручную, добавив новое поле. Это очень долго и сложно в поддержке кода, как и в тестировании.
Для решения этой проблемы придуман паттерн проектирования Прототип. Создадим общий протокол Copying, с методом copy() который возвращает копию объекта с необходимыми полями. После изменения полей сущности нужно будет обновить только один метод copy(), вместо того чтобы искать и обновлять вручную все места содержащие код копирования.

Источники

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

Стейт машина и паттерн Состояние

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

MEAACT PHOTO / STUART PRICE.

Повелитель флажков

Допустим мы разрабатываем экран видеоплеер для медиасистемы гражданского самолета, плеер должен уметь загружать видео поток, проигрывать его, позволять пользователю останавливать процесс загрузки, перематывать и производить прочие операции обыкновенные для плеера.
Допустим плеер закэшировал очередной чанк видеопотока, проверил что чанков достаточно для воспроизведения, начал воспроизводить пользователю фрагмент и одновременно продолжает загрузку следующего.
В этот момент пользователь перематывает в середину ролика, тоесть теперь нужно остановить проигрывание текущего фрагмента, и начать загрузку с новой позиции. Однако существуют ситуации в которых такое делать нельзя – пользователь не может управлять проигрыванием видеопотока, пока ему показывают видеоролик о безопасности в воздухе. Заведем флажок isSafetyVideoPlaying для проверки данной ситуации.
Также система должна уметь ставить на паузу текущее видео и транслировать оповещение от капитана судна и экипажа через плеер. Заведем еще один флажок isAnnouncementPlaying. Плюс ко всему появилось требование не приостанавливать воспроизведение во время вывода справки по работе с плеером, еще один флажок isHelpPresenting.

Псевдокод примера медиаплеера:

class MediaPlayer {

    public var isHelpPresenting = false
    public var isCaching = false
    public var isMediaPlaying: Bool = false
    public var isAnnouncementPlaying = false
    public var isSafetyVideoPlaying = false

    public var currentMedia: Media = null

    fun play(media: Media) {

        if isMediaPlaying == false, isAnnouncementPlaying == false, isSafetyVideoPlaying == false {

            if isCaching == false {
                if isHelpPresenting == false {
                    media.playAfterHelpClosed()
                }
                else {
                    media.playAfterCaching()
                }
            }
    }

    fun pause() {
        if isAnnouncementPlaying == false, isSafetyVideoPlaying == false {
            currentMedia.pause()
        }
    }
}

Приведенный выше пример плохо читаем, такой код сложно поддерживать из-за большой вариативности (энтропии) Данный пример основывается на моем опыте работы с кодовой базой *многих* проектов, где не использовалась стейт-машина.
Каждый флажок должен по особенному “управлять” элементами интерфейса, бизнес-логики приложения, разработчик, добавляя очередной флажок, должен уметь жонглировать ими, проверяя и перепроверяя все по нескольку раз со всеми возможными вариантами.
Подставляем в формулу “2 ^ количество флажков” можно получить 2 ^ 6 = 64 варианта поведения приложения для всего 6 флажков, все эти сочетания флажков нужно будет проверять и поддерживать вручную.
Со стороны разработчика добавление нового функционала при такой системе выглядит так:
– Нужно добавить возможность показывать страницу браузера авиакомпании, при этом она должна сворачиваться как с фильмами, если члены экипажа что-то объявляют.
– Ок, сделаю. (Ох чёрт придется добавить еще один флаг, и перепроверить все места где пересекаются флажки, это же сколько всего надо поменять!)

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

Enter The Machine

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

Псевдокод:

enum MediaPlayerState {
	mediaPlaying,
	mediaCaching,
	crewSpeaking,
	safetyVideoPlaying,
	presentingHelp
}

class MediaPlayer {
	fun play(media: Media) {
		media.play()
	}

	func pause() {
		media.pause()
	}
}

class MediaPlayerStateMachine {
	public state: MediaPlayerState
	public mediaPlayer: MediaPlayer
	public currentMedia: Media

	//.. init (mediaPlayer) etc

	public fun set(state: MediaPlayerState) {
		switch state {
			case mediaPlaying:
				mediaPlayer.play(currentMedia)
			case mediaCaching, crewSpeaking,
			safetyVideoPlaying, presentingHelp:
				mediaPlayer.pause()
		}
	}
}

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

Паттерн Состояние

Далее я покажу разницу между наивной имплементацией стейт машины и паттерном состояние. Представим что понадобилось добавить 10 стейтов, в итоге класс стейт-машины разрастется до размеров godobject, его будет сложно и затратно поддерживать. Конечно данная реализация лучше флажковой, (при флажковой системе застрелится сначала разработчик, а если и нет, то увидев 2 ^ 10 = 1024 вариаций повесится QA, однако если они оба *не заметят* сложности задачи, то ее заметит пользователь, у которого приложение просто откажется работать при определенном сочетании флажков)
При большом количестве состояний необходимо использовать паттерн Состояния.
Вынесем свод правил в протокол Состояния:

protocol State {
    func playMedia(media: Media, context: MediaPlayerContext)
    func shouldCacheMedia(context: MediaPlayerContext)
    func crewSpeaking(context: MediaPlayerContext)
    func safetyVideoPlaying(context:MediaPlayerContext)
    func presentHelp(context: MediaPlayerContext)
}

Вынесем реализацию свода правил в отдельные состояния, для примера код одного состояния:

class CrewSpeakingState: State {
	func playMedia(context: MediaPlayerContext) {
		showWarning(“Can’ t play media - listen to announce!”)
	}

	func mediaCaching(context: MediaPlayerContext) {
		showActivityIndicator()
	}

	func crewSpeaking(context: MediaPlayerContext) {
		set(volume: 100)
	}

	func safetyVideoPlaying(context: MediaPlayerContext) {
		set(volume: 100)
	}

	func presentHelp(context: MediaPlayerContext) {
		showWarning(“Can’ t present help - listen to announce!”)
	}
}

Далее создадим контекст с которым будет работать каждый стейт, интегрируем стейт-машину:

final class MediaPlayerContext {
	private
	var state: State

	public fun set(state: State) {
		self.state = state
	}

	public fun play(media: Media) {
		state.play(media: media, context: this)
	}

	…
	остальные возможные события
}

Компоненты приложения работают с контекстом через публичные методы, объекты стейты сами решают из какого стейта в какой осуществлять переход с помощью стейт-машины внутри контекста.
Таким образом мы реализовали декомпозицию God Object, поддерживать изменяющееся состояние будет гораздо проще, благодаря отслеживанию изменений в протоколе компилятором, уменьшения сложности понимания состояний из-за уменьшения количества строк кода и фокусе на решении конкретной задачи состояния. Также теперь можно разделять работу в команде, отдавая реализацию конкретного состояния членам команды, не беспокоясь о необходимости “разруливать” конфликты, что происходит при работе с одним большим классом стейт-машины.

Источники

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

Скелетная анимация (Часть 1 – шейдер)

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

Скелетная анимация после обсчета на CPU попадает в вертексный шейдер.
Напомню формулу вертекса без скелетной анимации:
gl_Position = projectionMatrix * viewMatrix * modelMatrix * vertex;
Для тех кто не понимает как возникла эта формула, может почитать мою статью описывающую принцип работы с матрицами для отображения 3D контента в контексте OpenGL.
Для остальных – формула реализации скелетной анимации:
” vec4 animatedVertex = bone0matrix * vertex * bone0weight +”
“bone1matrix * vertex * bone1weight +”
“bone2matrix * vertex * bone2weight +”
“bone3matrix * vertex * bone3weight;\n”
” gl_Position = projectionMatrix * viewMatrix * modelMatrix * animatedVertex;\n”

Тоесть конечную матрицу трансформации кости умножаем на вертекс и на вес этой матрицы относительно вертекса. Каждый вертекс может быть анимирован 4-мя костями, сила воздействия регулируется параметром веса кости, сумма воздействий должна равняться единице.
Что делать если на вертекс воздействуют меньше 4-х костей? Нужно поделить вес между ними, воздействие остальных сделать равным нулю.
Математически умножение веса на матрицу называется “Умножение матрицы на скаляр”. Умножение на скаляр позволяет суммировать воздействие матриц на итоговый вертекс.

Сами матрицы трансформации костей передаются массивом. Причем массив содержит матрицы для всей модели в целом, а не для каждого меша по отдельности.

А вот для каждого вертекса отдельно передается следующая информация:
– Индекс матрицы которая воздействует на вертекс
– Вес матрицы которая воздействует на вертекс
Передается не одна кость, обычно используется воздействие 4 костей на вертекс.
Также сумма весов 4-х костей должна всегда быть равна единице.
Далее рассмотрим как это выглядит в шейдере.
Массив матриц:
“uniform mat4 bonesMatrices[kMaxBones];”

Информация о воздействии 4 костей на каждый вертекс:
“attribute vec2 bone0info;”
“attribute vec2 bone1info;”
“attribute vec2 bone2info;”
“attribute vec2 bone3info;”

vec2 – в координате X храним индекс кости (и переводим в int в шейдере), в координате Y вес воздействия кости на вертекс. Почему приходится передавать эти данные в двухмерном векторе? Потому что GLSL не поддерживает передачу читаемых C структур с корректными полями в шейдер.

Ниже приведу пример получения необходимой информации из вектора, для дальнейшей подстановки в формулу animatedVertex:

“int bone0Index = int(bone0info.x);”
“float bone0weight = bone0info.y;”
“mat4 bone0matrix = bonesMatrices[bone0Index];”

“int bone1Index = int(bone1info.x);”
“float bone1weight = bone1info.y;”
“mat4 bone1matrix = bonesMatrices[bone1Index];”

“int bone2Index = int(bone2info.x);”
“float bone2weight = bone2info.y;”
“mat4 bone2matrix = bonesMatrices[bone2Index];”

“int bone3Index = int(bone3info.x);”
“float bone3weight = bone3info.y;”
“mat4 bone3matrix = bonesMatrices[bone3Index];”

Теперь структура вертекса, заполняющаяся на CPU, должна выглядеть так:
x, y, z, u, v, bone0index, bone0weight, bone1index, bone1weight, bone2index, bone2weight, bone3index, bone3weight

Структура вертексного буфера заполняется один раз во время загрузки модели, а вот матрицы трансформации передаются из CPU в шейдер при каждом кадре рендеринга.

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

Источники

http://ogldev.atspace.co.uk/www/tutorial38/tutorial38.html

Исходный код

https://gitlab.com/demensdeum/skeletal-animation