Category Archives: Техдок

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

Binary Insertion Sort

Binary Insertion Sort – вариант сортировки вставками, в котором позицию для вставки определяют с помощью двоичного поиска. Временная сложность алгоритма O(n2)

Алгоритм работает так:

  1. Запускается цикл от нуля до конца списка
  2. В цикле выбирается число для сортировки, число сохраняется в отдельную переменную
  3. Бинарным поиском ищется индекс для вставки этого числа по сравнению с числами слева
  4. После нахождения индекса, числа слева сдвигаются на одну позицию вправо, начиная с индекса вставки. В процессе будет стерто число которое нужно отсортировать.
  5. Сохраненное ранее число вставляется по индексу вставки
  6. По окончанию цикла весь список будет отсортирован

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

Код на Go:


import (
	"fmt"
	"math/rand"
	"time"
)

const numbersCount = 20
const maximalNumber = 100

func binarySearch(numbers []int, item int, low int, high int) int {
	for high > low {
		center := (low + high) / 2
		if numbers[center] < item { low = center + 1 } else if numbers[center] > item {
			high = center - 1
		} else {
			return center
		}
	}

	if numbers[low] < item {
		return low + 1
	} else {
		return low
	}
}

func main() {
	rand.Seed(time.Now().Unix())
	var numbers [numbersCount]int
	for i := 0; i < numbersCount; i++ {
		numbers[i] = rand.Intn(maximalNumber)
	}
	fmt.Println(numbers)

	for i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {
			numbers[x+1] = numbers[x]
		}
		numbers[insertIndex] = insertNumber
	}
	fmt.Println(numbers)
}

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/binaryInsertionSort/binaryInsertionSort.go

Источники

https://www.geeksforgeeks.org/binary-insertion-sort/
https://www.youtube.com/watch?v=-OVB5pOZJug

Shell Sort

Shell Sort – вариант сортировки вставками с предварительным причесыванием массива чисел.

Надо вспомнить как работает сортировка вставками:

1. Запускается цикл от нуля до конца цикла, таким образом массив разделяется на две части
2. Для левой части запускается второй цикл, сравнение элементов справа налево, меньший элемент справа опускается пока не найдется меньший элемент слева
3. По окончанию обоих циклов, получим отсортированный список

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

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

Таблицу известных вариантов и временную сложность можно посмотреть здесь: https://en.wikipedia.org/wiki/Shellsort#Gap_sequences

Вычислением идеальной дистанции занимались разные люди, настолько, видимо, была им эта тема интересна. Неужели они не могли просто запустить Ruby, вызвать самый быстрый алгоритм sort()?

В общем эти странные люди писали диссертации на тему вычисления дистанции/зазора «расчески» для алгоритма Шелла. Я же просто воспользовался результатами их труда и проверил 5 типов последовательностей, Хиббарда, Кнута-Пратта, Чиуры, Седжвика.

import time
import random
from functools import reduce
import math

DEMO_MODE = False

if input("Demo Mode Y/N? ").upper() == "Y":
    DEMO_MODE = True

class Colors:
    BLUE = '\033[94m'
    RED = '\033[31m'
    END = '\033[0m'

def swap(list, lhs, rhs):
    list[lhs], list[rhs] = list[rhs], list[lhs]
    return list

def colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):
    for index, number in enumerate(numbers):
        if index == lhs:
            print(f"{Colors.BLUE}", end = "")
        elif index == rhs:
            print(f"{Colors.RED}", end = "")
        print(f"{number},", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
    print("\n")
    input(">")

def ShellSortLoop(numbers: List[int], distanceSequence: List[int]):
    distanceSequenceIterator = reversed(distanceSequence)
    while distance:= next(distanceSequenceIterator, None):
        for sortArea in range(0, len(numbers)):
            for rhs in reversed(range(distance, sortArea + 1)):
                lhs = rhs - distance
                if DEMO_MODE:
                    print(f"Distance: {distance}")
                    colorPrintoutStep(numbers, lhs, rhs)
                if numbers[lhs] > numbers[rhs]:
                    swap(numbers, lhs, rhs)
                else:
                    break

def ShellSort(numbers: List[int]):
    global ShellSequence
    ShellSortLoop(numbers, ShellSequence)

def HibbardSort(numbers: List[int]):
    global HibbardSequence
    ShellSortLoop(numbers, HibbardSequence)

def ShellPlusKnuttPrattSort(numbers: List[int]):
    global KnuttPrattSequence
    ShellSortLoop(numbers, KnuttPrattSequence)

def ShellPlusCiuraSort(numbers: List[int]):
    global CiuraSequence
    ShellSortLoop(numbers, CiuraSequence)

def ShellPlusSedgewickSort(numbers: List[int]):
    global SedgewickSequence
    ShellSortLoop(numbers, SedgewickSequence)

def insertionSort(numbers: List[int]):
    global insertionSortDistanceSequence
    ShellSortLoop(numbers, insertionSortDistanceSequence)

def defaultSort(numbers: List[int]):
    numbers.sort()

def measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):
    if DEMO_MODE:
        print(f"{algorithmName} started")
    numbers = inputNumbers.copy()
    startTime = time.perf_counter()
    algorithm(numbers)
    endTime = time.perf_counter()
    print(f"{algorithmName} performance: {endTime - startTime}")

def sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:
    numbers = inputNumbers.copy()
    algorithm(numbers)
    return str(numbers)

if DEMO_MODE:
    maximalNumber = 10
    numbersCount = 10
else:
    maximalNumber = 10
    numbersCount = random.randint(10000, 20000)

randomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]

ShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount / 2)])
ShellSequence = ShellSequenceGenerator(randomNumbers)
ShellSequence.reverse()
ShellSequence.pop()

HibbardSequence = [
    0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,
    8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,
    2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,
    268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
]

KnuttPrattSequence = [
    1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 
    797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 
    1743392200, 5230176601, 15690529804, 47071589413
]

CiuraSequence = [
            1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376, 
            10941, 27353, 68383, 170958, 427396, 1068491, 
            2671228, 6678071, 16695178, 41737946, 104344866, 
            260862166, 652155416, 1630388541
]

SedgewickSequence = [
            1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
            8929, 16001, 36289, 64769, 146305, 260609, 587521, 
            1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 
            67084289, 150958081, 268386305, 603906049, 1073643521, 
            2415771649, 4294770689, 9663381505, 17179475969
]

insertionSortDistanceSequence = [1]

algorithms = {
    "Default Python Sort": defaultSort,
    "Shell Sort": ShellSort,
    "Shell + Hibbard" : HibbardSort,
    "Shell + Prat, Knutt": ShellPlusKnuttPrattSort,
    "Shell + Ciura Sort": ShellPlusCiuraSort,
    "Shell + Sedgewick Sort": ShellPlusSedgewickSort,
    "Insertion Sort": insertionSort
}

for name, algorithm in algorithms.items():
    measureExecution(randomNumbers, name, algorithm)

reference = sortedNumbersAsString(randomNumbers, defaultSort)

for name, algorithm in algorithms.items():
    if sortedNumbersAsString(randomNumbers, algorithm) != reference:
        print("Sorting validation failed")
        exit(1)

print("Sorting validation success")
exit(0)

В моей реализации, для случайного набора числем самыми быстрыми оказываются зазоры Седжвика и Хиббарда.

mypy

Также хочется упомянуть анализатор статической типизации для Python 3 – mypy. Помогает справиться с проблемами присущими языкам с динамической типизацией, а именно устраняет возможность просунуть что-то куда не надо.

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

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/shellSort
http://mypy-lang.org/

Источники

https://dl.acm.org/doi/10.1145/368370.368387
https://en.wikipedia.org/wiki/Shellsort
http://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
https://ru.wikipedia.org/wiki/Сортировка_Шелла
https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_Шелла
https://twitter.com/gvanrossum/status/700741601966985216

Double Selection Sort

Double Selection Sort – подвид сортировки выбором, вроде как должен ускоряться в два раза. Ванильный алгоритм проходит двойным циклом по списку чисел, находит минимальное число и меняет местами с текущей цифрой на которую указывает цикл на уровне выше. Двойная сортировка выбором же ищет минимальное и максимальное число, далее происходит замена двух цифр, на которые указывает цикл на уровне выше – два числа слева и справа. Заканчивается вся эта вакханалия когда курсоры чисел для замены встречаются в середине списка, по итогу слева и справа от визуального центра получаются отсортированные числа.
Временная сложность алгоритма аналогична Selection Sort – O(n2), но якобы есть ускорение на 30%.

Пограничное состояние

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

  maximalNumberIndex = minimalNumberIndex;
}

Реализация на Cito

Cito – язык либ, язык транслятор. На нем можно писать для C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, при этом совершенно ничего не зная про эти языки. Исходный код на языке Cito транслируется в исходный код на поддерживаемых языках, далее можно использовать как библиотеку, либо напрямую, исправив сгенеренный код руками. Эдакий Write once – translate to anything.
Double Selection Sort на cito:

{
    public static int[] sort(int[]# numbers, int length)
    {
        int[]# sortedNumbers = new int[length];
        for (int i = 0; i < length; i++) {
            sortedNumbers[i] = numbers[i];
        }
        for (int leftCursor = 0; leftCursor < length / 2; leftCursor++) {
            int minimalNumberIndex = leftCursor;
            int minimalNumber = sortedNumbers[leftCursor];

            int rightCursor = length - (leftCursor + 1);
            int maximalNumberIndex = rightCursor;
            int maximalNumber = sortedNumbers[maximalNumberIndex];

            for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {
                    minimalNumber = cursorNumber;
                    minimalNumberIndex = cursor;
                }
                if (maximalNumber < cursorNumber) {
                    maximalNumber = cursorNumber;
                    maximalNumberIndex = cursor;
                }
            }

            if (leftCursor == maximalNumberIndex) {
                maximalNumberIndex = minimalNumberIndex;
            }

            int fromNumber = sortedNumbers[leftCursor];
            int toNumber = sortedNumbers[minimalNumberIndex];
            sortedNumbers[minimalNumberIndex] = fromNumber;
            sortedNumbers[leftCursor] = toNumber;

            fromNumber = sortedNumbers[rightCursor];
            toNumber = sortedNumbers[maximalNumberIndex];
            sortedNumbers[maximalNumberIndex] = fromNumber;
            sortedNumbers[rightCursor] = toNumber;
        }
        return sortedNumbers;
    }
}

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/doubleSelectionSort
https://github.com/pfusik/cito

Источники

https://www.researchgate.net/publication/330084245_Improved_Double_Selection_Sort_using_Algorithm
http://algolab.valemak.com/selection-double
https://www.geeksforgeeks.org/sorting-algorithm-slightly-improves-selection-sort/

Cocktail Shaker Sort

Cocktail Shaker Sort – сортировка в шейкере, вариант двунаправленной сортировки пузырьком.
Алгоритм работает следующим образом:

  1. Выбирается начальное направление перебора в цикле (обычно слева-направо)
  2. Далее в цикле попарно проверяются цифры
  3. Если следующий элемент больше, то они меняются местами
  4. По окончанию, процесс перебора запускается заново с инвертированием направления
  5. Перебор повторяется до тех пор, пока не закончатся перестановки

Временная сложность алгоритма аналогична пузырьковой – O(n2).

Пример реализации на языке PHP:

<?php

function cocktailShakeSort($numbers)
{
    echo implode(",", $numbers),"\n";
    $direction = false;
    $sorted = false;
    do {
        $direction = !$direction;        
        $firstIndex = $direction == true ? 0 : count($numbers) - 1;
        $lastIndex = $direction == true ? count($numbers) - 1 : 0;
        
        $sorted = true;
        for (
            $i = $firstIndex;
            $direction == true ? $i < $lastIndex : $i > $lastIndex;
            $direction == true ? $i++ : $i--
        ) {
            $lhsIndex = $direction ? $i : $i - 1;
            $rhsIndex = $direction ? $i + 1 : $i;

            $lhs = $numbers[$lhsIndex];
            $rhs = $numbers[$rhsIndex];

            if ($lhs > $rhs) {
                $numbers[$lhsIndex] = $rhs;
                $numbers[$rhsIndex] = $lhs;
                $sorted = false;
            }
        }
    } while ($sorted == false);

    echo implode(",", $numbers);
}

$numbers = [2, 1, 4, 3, 69, 35, 55, 7, 7, 2, 6, 203, 9];
cocktailShakeSort($numbers);

?>

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/cocktailShakerSort/cocktailShakerSort.php

Источники

https://www.youtube.com/watch?v=njClLBoEbfI
https://www.geeksforgeeks.org/cocktail-sort/
https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort

Починяем Primus

В этой заметке опишу запуск Steam игр на дистрибутиве Линукса Arch Linux в конфигурации ноутбука Intel + Nvidia

Counter-Strike: Global Offensive

Единственная конфигурация которая у меня заработала – Primus-vk + Vulkan.

Установим нужные пакеты:
pacman -S vulkan-intel lib32-vulkan-intel nvidia-utils lib32-nvidia-utils vulkan-icd-loader lib32-vulkan-icd-loader primus_vk

Далее добавляем параметры запуска для Counter-Strike: Global Offensive:
pvkrun %command% -vulkan -console -fullscreen

Должно работать!

Sid Meier’s Civilization VI

Работает в связке – Primus + OpenGL + LD_PRELOAD.

Установим пакет Primus:
pacman -S primus

Далее добавляем параметры запуска для Sid Meier’s Civilization VI:
LD_PRELOAD='/usr/lib/libfreetype.so.6:/usr/lib/libbrotlicommon.so.1:/usr/lib/libbrotlidec.so.1' primusrun %command%

С помощью LD_PRELOAD подпихиваются библиотеки сжатия и шрифтов Freetype.

Dota 2

Работает в связке – Primus + OpenGL + удаление локов на запуске.

Установим пакет Primus:
pacman -S primus

Далее добавляем параметры запуска для Dota 2:
primusrun %command% -gl -console

Если игра не стартует с ошибкой fcntl(5) for /tmp/source_engine_2808995433.lock failed, то попробуйте удалить файл/tmp/source_engine_2808995433.lock
rm /tmp/source_engine_2808995433.lock
Обычно файл лока остается от прошлой игровой сессии, если игра не была закрыта естественным образом.

Как проверить?

Проще всего проверить запуск приложений на дискретной видеокарте Nvidia через утилиту nvidia-smi:

Для игр на движке Source проверить можно через игровую консоль с помощью команды mat_info:

Источники

https://wiki.archlinux.org/title/Steam/Game-specific_troubleshooting
https://help.steampowered.com/en/faqs/view/145A-FE54-F37B-278A
https://bbs.archlinux.org/viewtopic.php?id=277708

Sleep Sort

Sleep Sort – сортировка сном, еще один представитель детерменированных странных алгоритмов сортировки.

Работает следующим образом:

  1. Проходит циклом по списку элементов
  2. Для каждого цикла запускается отдельный поток
  3. В потоке шедулится сон (sleep) потока на время – значение элемента и вывод значения после сна
  4. По окончанию цикла, ждем ожидания завершения самого долгого сна потока, выводим отсортированный список

Пример кода алгоритма сортировки сном на C:

#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

typedef struct {
    int number;
} ThreadPayload;

void *sortNumber(void *args) {
    ThreadPayload *payload = (ThreadPayload*) args;
    const int number = payload->number;
    free(payload);
    usleep(number * 1000);
    printf("%d ", number);
    return NULL;
}

int main(int argc, char *argv[]) {
    const int numbers[] = {2, 42, 1, 87, 7, 9, 5, 35};
    const int length = sizeof(numbers) / sizeof(int);

    int maximal = 0;
    pthread_t maximalThreadID;

    printf("Sorting: ");
    for (int i = 0; i < length; i++) { pthread_t threadID; int number = numbers[i]; printf("%d ", number); ThreadPayload *payload = malloc(sizeof(ThreadPayload)); payload->number = number;
        pthread_create(&threadID, NULL, sortNumber, (void *) payload);
        if (maximal < number) {
            maximal = number;
            maximalThreadID = threadID;
        }
    }
    printf("\n");
    printf("Sorted: ");
    pthread_join(maximalThreadID, NULL);
    printf("\n");
    return 0;
}

В этой реализации я использовал функцию usleep на микросекундах с умножением значения на 1000, т.е. на миллисекундах.
Временная сложность алгоритма – O(оч. долго)

Ссылки

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

Источники

https://codoholicconfessions.wordpress.com/2017/05/21/strangest-sorting-algorithms/
https://twitter.com/javascriptdaily/status/856267407106682880?lang=en
https://stackoverflow.com/questions/6474318/what-is-the-time-complexity-of-the-sleep-sort

Stalin Sort

Stalin Sort – сортировка навылет, один из алгоритмов сортировки с потерей данных.
Алгоритм очень производительный и эффективный, временная сложность O(n).

Работает следующим образом:

  1. Проходим циклом по массиву, сравнивая текущий элемент со следующим
  2. Если следующий элемент меньше текущего, то удаляем его
  3. В итоге получаем отсортированный массив за O(n)

Пример вывода работы алгоритма:

Gulag: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Element 2 sent to Gulag
Element 4 sent to Gulag
Element 8 sent to Gulag
Element 5 sent to Gulag
Element 0 sent to Gulag
Element 35 sent to Gulag
Element 10 sent to Gulag
Numbers: [1, 3, 4, 6, 42]
Gulag: [2, 4, 8, 5, 0, 35, 10]

Код на Питоне 3:

gulag = []

print(f"Numbers: {numbers}")
print(f"Gulag: {numbers}")

i = 0
maximal = numbers[0]

while i < len(numbers):
    element = numbers[i]
    if maximal > element:
        print(f"Element {element} sent to Gulag")
        gulag.append(element)
        del numbers[i]
    else:
        maximal = element        
        i += 1

print(f"Numbers: {numbers}")
print(f"Gulag: {gulag}")

Из недостатков можно отметить потерю данных, но если двигаться к утопичному, идеальному, отсортированному списку за O(n), то как иначе?

Ссылки

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

Источники

https://github.com/gustavo-depaula/stalin-sort
https://www.youtube.com/shorts/juRL-Xn-E00
https://www.youtube.com/watch?v=L78i2YcyYfk

Selection Sort

Selection Sort – алгоритм сортировки выбором. Выбором чего? А вот минимального числа!!!
Временная сложность алгоритма – О(n2)

Алгоритм работает следующим образом:

  1. Проходим массив циклом слева-направо, запоминаем текущий стартовый индекс и число по индексу, назовем числом A
  2. Внутри цикла запускаем еще один для прохода слева-направо в поисках меньшего чем A
  3. Когда находим меньший, запоминаем индекс, теперь меньший становится числом А
  4. Когда внутренний цикл заканчивается, меняем местами число по стартовому индексу и число А
  5. После полного прохода верхнего цикла, получаем отсортированный массив

Пример выполнения алгоритма:

(29, 49, 66, 35, 7, 12, 80)
29 > 7
(7, 49, 66, 35, 29, 12, 80)
Round 1 ENDED
Round 2
(7, 49, 66, 35, 29, 12, 80)
49 > 35
35 > 29
29 > 12
(7, 12, 66, 35, 29, 49, 80)
Round 2 ENDED
Round 3
(7, 12, 66, 35, 29, 49, 80)
66 > 35
35 > 29
(7, 12, 29, 35, 66, 49, 80)
Round 3 ENDED
Round 4
(7, 12, 29, 35, 66, 49, 80)
(7, 12, 29, 35, 66, 49, 80)
Round 4 ENDED
Round 5
(7, 12, 29, 35, 66, 49, 80)
66 > 49
(7, 12, 29, 35, 49, 66, 80)
Round 5 ENDED
Round 6
(7, 12, 29, 35, 49, 66, 80)
(7, 12, 29, 35, 49, 66, 80)
Round 6 ENDED
Sorted: (7, 12, 29, 35, 49, 66, 80)

Не найдя Objective-C реализации на Rosetta Code, написал его сам:

#include <Foundation/Foundation.h>

@implementation SelectionSort
- (void)performSort:(NSMutableArray *)numbers
{
   NSLog(@"%@", numbers);   
   for (int startIndex = 0; startIndex < numbers.count-1; startIndex++) {
      int minimalNumberIndex = startIndex;
      for (int i = startIndex + 1; i < numbers.count; i++) {
         id lhs = [numbers objectAtIndex: minimalNumberIndex];
         id rhs = [numbers objectAtIndex: i];
         if ([lhs isGreaterThan: rhs]) {
            minimalNumberIndex = i;
         }
      }
      id temporary = [numbers objectAtIndex: minimalNumberIndex];
      [numbers setObject: [numbers objectAtIndex: startIndex] 
               atIndexedSubscript: minimalNumberIndex];
      [numbers setObject: temporary
               atIndexedSubscript: startIndex];
   }
   NSLog(@"%@", numbers);
}

@end

Собрать и запустить можно либо на MacOS/Xcode, либо на любой операционной системе поддерживающей GNUstep, например у меня собирается Clang на Arch Linux.
Скрипт сборки:

        main.m \
        -lobjc \
        `gnustep-config --objc-flags` \
        `gnustep-config --objc-libs` \
        -I /usr/include/GNUstepBase \
        -I /usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/include/ \
        -lgnustep-base \
        -o SelectionSort \

Links

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

Sources

https://rosettacode.org/wiki/Sorting_algorithms/Selection_sort
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://en.wikipedia.org/wiki/Selection_sort
https://www.youtube.com/watch?v=LJ7GYbX7qpM

Counting Sort

Counting sort – алгоритм сортировки подсчетом. Всмысле? Да! Прям так!

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

После получения второго массива, перебираем его и записываем отсортированный вариант числа по индексу, декрементируя счетчик до нуля. Изначально нулевой счетчик игнорируется.

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

  1. Входой массив 1,9,1,4,6,4,4
  2. Тогда массив для подсчета будет 0,1,2,3,4,5,6,7,8,9 (минимальное число 0, максимальное 9)
  3. С итоговыми счетчиками 0,2,0,0,3,0,1,0,0,1
  4. Итого отсортированный массив 1,1,4,4,4,6,9

Код алгоритма на языке Python 3:


numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]

minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange

print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximal number: {maximal}")
print(f"Count list size: {countListRange}")

for number in numbers:
    index = number - minimal
    countList[index] += 1

replacingIndex = 0
for index, count in enumerate(countList):
    for i in range(count):
        outputNumber = minimal + index
        numbers[replacingIndex] = outputNumber
        replacingIndex += 1

print(numbers)

Из-за использования двух массивов, временная сложность алгоритма O(n + k)

Ссылки

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

Источники

https://www.youtube.com/watch?v=6dk_csyWif0
https://www.youtube.com/watch?v=OKd534EWcdk
https://en.wikipedia.org/wiki/Counting_sort
https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort
https://pro-prof.com/forums/topic/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%BE%D0%BC

Bogosort

Псевдо-сортировка или болотная сортировка, один из самых бесполезных алгоритмов сортировки.

Работает он так:
1. На вход подается массив из чисел
2. Массив из чисел перемешивается случайным образом (shuffle)
3. Проверяется отсортирован ли массив
4. Если не отсортирован, то массив перемешивается заново
5. Все это действо повторяется до тех пор, пока массив не отсортируется случайным образом.

Как можно увидеть – производительность этого алгоритма ужасна, умные люди считают что даже O(n * n!) т.е. есть шанс завязнуть кидая кубики во славу бога хаоса очень много лет, массив так и не отсортируется, а может отсортируется?

Реализация

Для реализации на TypeScript мне понадобилось реализовать следующие функции:
1. Перемешивание массива объектов
2. Сравнение массивов
3. Генерация случайного числа в диапазоне от нуля до числа (sic!)
4. Печать прогресса, т.к. кажется что сортировка выполняется бесконечно

Ниже код реализации на TypeScript:

const randomInteger = (maximal: number) => Math.floor(Math.random() * maximal);
const isEqual = (lhs: any[], rhs: any[]) => lhs.every((val, index) => val === rhs[index]);
const shuffle = (array: any[]) => {
    for (var i = 0; i < array.length; i++) { var destination = randomInteger(array.length-1); var temp = array[i]; array[i] = array[destination]; array[destination] = temp; } } let numbers: number[] = Array.from({length: 10}, ()=>randomInteger(10));
const originalNumbers = [...numbers];
const sortedNumbers = [...numbers].sort();

let numberOfRuns = 1;

do {
    if (numberOfRuns % 1000 == 0) {
        printoutProcess(originalNumbers, numbers, numberOfRuns);
    }
    shuffle(numbers);
    numberOfRuns++;
} while (isEqual(numbers, sortedNumbers) == false)

console.log(`Success!`);
console.log(`Run number: ${numberOfRuns}`)
console.log(`Original numbers: ${originalNumbers}`);
console.log(`Current numbers: ${originalNumbers}`);
console.log(`Sorted numbers: ${sortedNumbers}`);

Для отладки можно использовать VSCode и плагин TypeScript Debugger от kakumei.

Как долго

Вывод работы алгоритма:

src/bogosort.ts:1
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 8,7,0,2,4,7,2,5,9,5, try number: 145000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 7,5,2,4,9,8,0,5,2,7, try number: 146000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 0,2,7,4,9,5,7,5,8,2, try number: 147000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 5,9,7,8,5,4,2,7,0,2, try number: 148000
src/bogosort.ts:2
Success!
src/bogosort.ts:24
Run number: 148798
src/bogosort.ts:25
Original numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:26
Current numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:27
Sorted numbers: 0,2,2,4,5,5,7,7,8,9

Для массива из 10 чисел Богосорт перемешивал исходный массив 148798 раз, многовато да?
Алгоритм можно использовать как учебный, для понимания возможностей языка с которым предстоит работать на рынке. Лично я был удивлен узнав что в ванильных JS и TS до сих пор нет своего алгоритма перемешивания массивов, генерации целого числа в диапазоне, доступа к хэшам объектов для быстрого сравнения.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bogosort
https://www.typescriptlang.org/
https://marketplace.visualstudio.com/items?itemName=kakumei.ts-debug

Источники

https://www.youtube.com/watch?v=r2N3scbd_jg
https://en.wikipedia.org/wiki/Bogosort

Паттерны GoF

Список паттернов банды четырех – те самые паттерны из-за которых вас могут валить на собеседовании.

Порождающие паттерны

Структурные паттерны

Паттерны поведения

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

Что входит

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

  • Терминальное выражение – например константа строки – “Hello World”
  • Нетерминальное выражение – например Print(“Hello World”), содержит Print и аргумент из Терминального выражения “Hello World”

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

Пример AST древа ниже:


Dcoetzee, CC0, via Wikimedia Commons

Как можно увидеть, терминальные выражения – constant и variable, нетерминальные – остальные.

Что не входит

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

Реализация

В паттерне участвуют:

  • Клиент – отдает AST-древо и запускает Interpret(context) для корневой вершины (Client)
  • Контекст – содержит состояние приложения, передается выражениям при интерпретации (Context)
  • Абстрактное выражение – абстрактный класс содержащий метод Interpret(context) (Expression)
  • Терминальное выражение – конечное выражение, потомок абстрактного выражения (TerminalExpression)
  • Нетерминальное выражение – не конечное выражение, содержит указатели на вершины вглубь AST-древа, подчиненные вершины обычно влияют на результат интерпретации нетерминального выражения (NonTerminalExpression)

Пример Клиента на C#

        static void Main(string[] args)
        {
            var context = new Context();
            var initialProgram = new PerformExpression(
                new IExpression[] {
                    new SetExpression("alpha", "1"),
                    new GetExpression("alpha"),
                    new PrintExpression(
                        new IExpression[] {
                            new ConstantExpression("Hello Interpreter Pattern")
                        }
                    )
                }
            );
            System.Console.WriteLine(initialProgram.interpret(context));
        }
}

Пример Абстрактного выражения на C#

{
    String interpret(Context context);
}

Пример Терминального выражения на C# (Строковая константа)

{
    private String constant;

    public ConstantExpression(String constant) {
        this.constant = constant;
    }

    override public String interpret(Context context) {
        return constant;
    }
}

Пример Нетерминального выражения на C# (Запуск и конкатенация результатов подчиненных вершин, с использованием разделителя «;»

{
    public PerformExpression(IExpression[] leafs) : base(leafs) {
        this.leafs = leafs;
    }
    
    override public String interpret(Context context) {
        var output = "";
        foreach (var leaf in leafs) {
            output += leaf.interpret(context) + ";";
        }
        return output;
    }
}

Функционально сможешь?

Как известно все Тьюринг-полные языки эквивалентны. Можно ли перенести Объектно-Ориентированный паттерн на язык Функционального программирования?

Можно, для эксперимента возьмем ФП язык для веба под названием Elm. В Elm нет классов, но есть Записи (Records) и Типы (Types) поэтому в реализации участвуют следующие записи и типы:

  • Выражение – перечисление всех возможных выражений языка (Expression)
  • Подчиненное выражение – выражение являющееся подчиненным по отношению к Нетерминальному выражению (ExpressionLeaf)
  • Контекст – запись хранящая состояние приложения (Context)
  • Функции реализующие методы Interpret(context) – все необходимые функции реализующие функционал Терминальных, Нетерминальных выражений
  • Вспомогательные записи состояния Интерпретатора – необходимы для корректной работы Интерпретатора, хранят состояние Интерпретатора, контекст

Пример функции реализующей интерпретацию для всего набора возможных выражений на Elm:

  case input.expression of
    Constant text ->
      { 
        output = text, 
        context = input.context 
      }
    Perform leafs ->
      let inputs = List.map (\leaf -> { expressionLeaf = leaf, context = input.context } ) leafs in
        let startLeaf = { expressionLeaf = (Node (Constant "")), context = { variables = Dict.empty } } in
          let outputExpressionInput = List.foldl mergeContextsAndRunLeafs startLeaf inputs in
            {
              output = (runExpressionLeaf outputExpressionInput).output,
              context = input.context
            }
    Print printExpression ->
      run 
      { 
        expression = printExpression, 
        context = input.context 
      }
    Set key value ->
      let variables = Dict.insert key value input.context.variables in
      {
        output = "OK",
        context = { variables = variables }
      }
    Get key ->
      {
        output = Maybe.withDefault ("No value for key: " ++ key) (Dict.get key input.context.variables),
        context = input.context
      }

А парсить?

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

parseLeafs state =
    let tokensQueue = state.tokensQueue in
        let popped = pop state.tokensQueue in
            let tokensQueueTail = tail state.tokensQueue in
                if popped == "Nothing" then
                    state
                else if popped == "Perform(" then
                    {
                        tokensQueue = tokensQueue,
                        result = (state.result ++ [Node (parse tokensQueue)])
                    }
                else if popped == ")" then
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = state.result
                    }
                else if popped == "Set" then
                    let key = pop tokensQueueTail in
                        let value = pop (tail tokensQueueTail) in
                            parseLeafs {
                                tokensQueue = tail (tail tokensQueueTail),
                                result = (state.result ++ [Node (Set key value)])
                            }
                else if popped == "Get" then
                    let key = pop tokensQueueTail in
                        parseLeafs {
                            tokensQueue = tail tokensQueueTail,
                            result = (state.result ++ [Node (Get key)])
                        }
                else 
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = (state.result ++ [Node (Constant popped)])
                    }

parse tokensQueue =
    let popped = pop tokensQueue in
        let tokensQueueTail = tail tokensQueue in
            if popped == "Perform(" then
                Perform (
                    parseLeafs {
                        tokensQueue = tokensQueueTail, 
                        result = []
                    }
                ).result
            else if popped == "Set" then
                let key = pop tokensQueueTail in
                    let value = pop (tail tokensQueueTail) in
                        Set key value
            else if popped == "Print" then
                Print (parse tokensQueueTail)
            else
                Constant popped

Ссылки

https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/elm
https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/csharp

Источники

https://en.wikipedia.org/wiki/Interpreter_pattern
https://elm-lang.org/
https://docs.microsoft.com/en-us/dotnet/csharp/

RGB изображение в серое

В этой заметке я опишу алгоритм перевода RGB буфера в серый (Grayscale).
А делается это довольно просто, каждый пиксель цветовой канал буфера преобразуется по определенной формуле и на выходе получается изображение серого цвета.
Метод среднего:

red = average;
green = average;
blue = average;

Складываем 3 цветовых канала и делим на 3.

Однако существует еще один метод – метод средневзвешенный, он учитывает цветовосприятие человека:

red = luminance;
green = luminance;
blue = luminance;

Какой метод лучше использовать? Да какой вам больше подходит для конкретной задачи. Далее сравнение методов с помощью тестовой цветовой сетки:

Пример реализации на JavaScript + HTML 5

    image,
    canvas,
    weightedAverage
) {
    const context = canvas.getContext('2d');

    const imageWeight = image.width;
    const imageHeight = image.height;

    canvas.width = imageWeight;
    canvas.height = imageHeight;

    context.drawImage(image, 0, 0);

    let pixels = context
        .getImageData(
            0,
            0,
            imageWeight,
            imageHeight
        );

    for (let y = 0; y & lt; pixels.height; y++) {
        for (let x = 0; x & lt; pixels.width; x++) {
            const i = (y * 4) * pixels.width + x * 4;

            let red = pixels.data[i];
            let green = pixels.data[i + 1];
            let blue = pixels.data[i + 2]

            const average = (red + green + blue) / 3;
            const luminance = 0.2126 * red +
                0.7152 * green +
                0.0722 * blue;

            red = weightedAverage ? luminance : average;
            green = weightedAverage ? luminance : average;
            blue = weightedAverage ? luminance : average;

            pixels.data[i] = red;
            pixels.data[i + 1] = green;
            pixels.data[i + 2] = blue;
        }
    }
    context
        .putImageData(
            pixels,
            0,
            0,
            0,
            0,
            pixels.width,
            pixels.height
        );
}

Источники

https://www.baeldung.com/cs/convert-rgb-to-grayscale
https://twitter.com/mudasobwa/status/1528046455587495940
https://rosettacode.org/wiki/Grayscale_image

Ссылки

http://papugi.demensdeum.repl.co/

Благодарности

Спасибо Aleksei Matiushkin (https://twitter.com/mudasobwa) за наводку на Rosetta Code

Как запустить CSGO на Macbook M1

Если у вас вылезает ошибка SDL_GetDesktopDisplayMode_REAL на Macbook M1 при запуске CSGO, то делайте как написано дальше.
1. Добавьте параметры запуска в Steam для CSGO:
-w 1440 -h 900 -fullscreen
2. Запустите CSGO через Steam
3. Нажмите Игнорировать или Всегда игорировать на ошибке SDL_GetDesktopDisplayMode_REAL
4. Наслаждайтесь

Вычислительные машины Тьюринга

Представляю вашему вниманию перевод первых страниц статьи Алана Тьюринга – “О ВЫЧИСЛИМЫХ ЧИСЛАХ С ПРИЛОЖЕНИЕМ К ПРОБЛЕМЕ РАЗРЕШЕНИЯ” 1936 года. Первые главы содержат описание вычислительных машин, которые в дальнейшем стали основой для современной вычислительной техники.

Полный перевод статьи и пояснение можно прочитать в книге американского популяризатора Чарлза Петцольда, под названием “Читаем Тьюринга. Путешествие по исторической статье Тьюринга о вычислимости и машинах Тьюринга” (ISBN 978-5-97060-231-7, 978-0-470-22905-7)

Оригинальная статья:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf

—

О ВЫЧИСЛИМЫХ ЧИСЛАХ С ПРИЛОЖЕНИЕМ К ПРОБЛЕМЕ РАЗРЕШЕНИЯ

А. М. ТЬЮРИНГ

[Получено 28 мая 1936 г. — Прочитано 12 ноября 1936 г.]

«Вычислимые» (computable) числа могут быть кратко описаны как действительные числа, выражения которых в виде десятичных дробей исчислимы (calculable) конечным числом средств. Хотя на первый взгляд в данной статье как вычислимые рассматриваются именно числа, почти так же легко определять и исследовать вычислимые функции целой переменной, действительной переменной, вычислимой переменной, вычислимые предикаты и тому подобное. Однако же, фундаментальные проблемы, связанные с указанными вычислимыми объектами, в каждом случае одни и те же. Для детального рассмотрения в качестве вычислимого объекта я выбрал именно вычислимые числа потому, что методика их рассмотрения наименее громоздкая. Надеюсь в скором времени описать взаимоотношения вычислимых чисел с вычислимыми функциями и так далее. При этом будут проведены исследования в области теории функций действительной переменной, выраженной в терминах вычислимых чисел. По моему определению, действительное число является вычислимым, если его представление в виде десятичной дроби может быть записано машиной.

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

Хотя класс вычислимых чисел очень велик и во многих отношениях похож на класс действительных чисел, он все же поддается перечислению, то есть является перечислимым (enumerable). В §8 я рассматриваю определенные доводы, которые, казалось бы, доказывают обратное предположение. При корректном применении одного из этих доводов делаются выводы, на первый взгляд, аналогичные выводам Геделя*. Данные результаты имеют чрезвычайно важные способы применения. В частности, как показано ниже (§11), не может иметь решения проблема разрешения.

В своей недавней статье Алонзо Черч** представил идею «способности поддаваться эффективному исчислению» (effective calculability), которая эквивалентна моей идее «вычислимости» (computability), но имеет совершенно иное определение. Черч также приходит к аналогичным выводам относительно проблемы разрешения. Доказательство эквивалентности «вычислимости» и «способности поддаваться эффективному исчислению» изложено в приложении к настоящей статье.

1. Вычислительные машины

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

Сопоставим человека в процессе вычисления действительного числа с машиной, которая способна выполнять только конечное число условий q1, q2, …, qR; назовем эти условия «m-конфигурациями». Данная (то есть так определенная) машина снабжена «лентой» (аналогом бумаги). Такая лента, проходящая через машину, разделена на секции. Назовем их «квадратами». Каждый такой квадрат может содержать какой-то «символ». В любой момент существует и при том только один такой квадрат, скажем, r-й, содержащий символ который находится «в данной машине». Назовем такой квадрат «отсканированным символом». «Отсканированный символ» — это единственный такой символ, о котором машина, образно выражаясь, «непосредственно осведомлена». Однако при изменении своей m-конфигурации машина может эффективно запоминать некоторые символы, которые она «увидела» (отсканировала) ранее. Возможное поведение машины в любой момент определяется m-конфигурацией qn и отсканированным символом***. Назовем данную пару символов qn, «конфигурацией». Обозначенная таким образом конфигурация определяет возможное поведение данной машины. В некоторых из таких конфигураций, в которых отсканированный квадрат является пустым (т. е. не содержит символа), данная машина записывает новый символ на отсканированном квадрате, а в других из таких конфигураций она стирает отсканированный символ. Данная машина также способна перейти к сканированию другого квадрата, но так она может переместиться лишь на соседний квадрат вправо или влево. В дополнение к любой из этих операций можно изменить m-конфигурацию машины. При этом некоторые из записанных символов сформируют последовательность цифр, являющуюся десятичной частью вычисляемого действительного числа. Остальные из них представят собой не более чем неточные отметки с тем, чтобы «помочь памяти». При этом стиранию могут подвергаться лишь вышеупомянутые неточные отметки.

Я утверждаю, что рассматриваемые здесь операции включают в себя все те операции, которые используются при вычислении. Обоснование данного утверждения легче понять читателю, имеющему представление о теории машин. Поэтому в следующем разделе я продолжу развивать рассматриваемую теорию, опираясь на понимание значения терминов «машина», «лента», «отсканированный» и т. д.

*Гедель «О формально неразрешимых предложениях «Принципов математики» (опубликованных Уайтехдом и Расселом в 1910, 1912 и 1913 гг.) и родственных систем, часть I», журнал по мат. физике, ежемесячный бюллетень на немецком языке № 38 (за 1931 год , стр. 173-198.
** Алонзо Черч, «Неразрешимая проблема элементарной теории чисел», American J. of Math., («Американский журнал математики»), № 58 (за 1936 год), стр. 345-363.
*** Алонсо Черч, «Замечание о проблеме разрешения», J. of Symbolic Logic («Журнал математической логики»), №1 (за 1936 год), стр. 40-41

Бомбе Тьюринга

В 1936 году ученый Алан Тьюринг в своей публикации “On Computable Numbers, With An Application to Entscheidungsproblem” описывает использование универсальной вычислительной машины которая смогла бы поставить точку в вопросе проблемы разрешимости в математике. По итогу он приходит к выводу что такая машина ничего бы не смогла решить корректно, если бы результат ее работы инвертировали и зациклили бы на саму себя. Получается что *идеальный* антивирус невозможно создать, *идеальный* плиткоукладчик тоже, программу которая подсказывает идеальные фразы для твоего краша и т.д. Парадокс-с!

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

Далее приводится ООП моделирование одноленточного вычислителя на языке Dart, с опорой на оригинальный документ.

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

final _map = Map<int, String>(); 

  String read({required int at}) { 
    return _map[at] ?? ""; 
  } 

  void write({required String symbol, required int at}) { 
    _map[at] = symbol; 
  } 
}

Также существует “сканирующий квадрат”, он может перемещаться по пленке, считывать или записывать информацию, на современном языке – магнитная головка. Пример класса магнитной головки:

  int _index = 0; 
  InfiniteTape _infiniteTape; 
  TapeHead(this._infiniteTape) {} 

  String next() { 
    _index += 1; 
    move(to: _index); 
    final output = read(); 
    return output; 
  } 

  String previous() { 
    _index -= 1; 
    move(to: _index); 
    final output = read(); 
    return output; 
  } 

  void move({required int to}) { 
    this._index = to; 
  } 

  String read() { 
    return _infiniteTape.read(at: this._index); 
  } 

  void write(String symbol) { 
    _infiniteTape.write(symbol: symbol, at: this._index); 
  } 

  int index() { 
    return _index; 
  } 
}

Машина содержит “m-конфигурации” по которым может решать что делать дальше. На современном языке – состояния и обработчики состояний. Пример обработчика состояний:

  FiniteStateControlDelegate? delegate = null; 

  void handle({required String symbol}) { 
    if (symbol == OPCODE_PRINT) { 
      final argument = delegate?.nextSymbol(); 
      print(argument);
    } 
    else if (symbol == OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER) { 
      final to = int.tryParse(delegate!.nextSymbol())!; 
      final value = new Random().nextInt(to); 
      delegate!.nextSymbol(); 
      delegate!.write(value.toString()); 
    } 
    else if (symbol == OPCODE_INPUT_TO_NEXT) { 
      final input = stdin.readLineSync()!; 
      delegate?.nextSymbol(); 
      delegate?.write(input); 
    } 
    else if (symbol == OPCODE_COPY_FROM_TO) { 
      final currentIndex = delegate!.index(); 

и т.д.

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

const OPCODE_PRINT = "print"; 
const OPCODE_INCREMENT_NEXT = "increment next"; 
const OPCODE_DECREMENT_NEXT = "decrement next"; 
const OPCODE_IF_PREVIOUS_NOT_EQUAL = "if previous not equal"; 
const OPCODE_MOVE_TO_INDEX = "move to index"; 
const OPCODE_COPY_FROM_TO = "copy from index to index"; 
const OPCODE_INPUT_TO_NEXT = "input to next"; 
const OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER = "generate random number from zero to next and write after";

Не забудьте создать опкод и обработчик останова, иначе не сможете доказать либо не доказать (sic!) проблему разрешения.

Теперь, используя паттерн “медиатор”, соединяем все классы в классе Машине Тьюринга, создаем экземпляр класса, записываем через магнитофон на пленку программы, загружаем кассету и можно пользоваться!

Лично для меня остался интересен вопрос, что было первично – создание универсального вычислителя или доказательство “Entscheidungsproblem” в результате которого, как побочный продукт, появился вычислитель.

Кассеты

Развлечения ради я записал несколько кассет-программ для своего варианты машины.

Hello World

hello world 
stop

Считаем до 16-ти

0
if previous not equal
16
copy from index to index
1
8
print
?
move to index
0
else
copy from index to index
1
16
print
?
print
Finished!
stop

Самой интересной задачей было написание Quine программы, которая печатает свой исходный код, для одноленточной машины. Первые 8 часов мне казалось что эта задача не решаема с таким малым количеством опкодов, однако всего через 16 часов оказалось что я был не прав.

Реализация и примеры кассет, источники ниже.

Ссылки

https://gitlab.com/demensdeum/turing-machine

Источники

https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf
https://kpolyakov.spb.ru/prog/turing.htm
https://www.youtube.com/watch?v=dNRDvLACg5Q
https://www.youtube.com/watch?v=jP3ceURvIYc
https://www.youtube.com/watch?v=9QCJj5QzETI
https://www.youtube.com/watch?v=HeQX2HjkcNo&t=0s

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

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

Чтение нажатий, обработка “событий” джойстика сеги происходит по следующей схеме:

  1. Запрос комбинации битов нажатых кнопок
  2. Считывание битов нажатых кнопок
  3. Обработка на уровне игровой логики

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

RAM

Переменные игровой логики хранятся в RAM, до сих пор люди не придумали ничего лучше. Объявим адреса переменных, изменим код отрисовки:

skeletonYpos = $FF0002 
frameCounter = $FF0004 
skeletonHorizontalFlip = $FF0006

    move.w #$0100,skeletonXpos 
    move.w #$0100,skeletonYpos 
    move.w #$0001,skeletonHorizontalFlip 

FillSpriteTable: 
    move.l #$70000003,vdp_control_port 
    move.w skeletonYpos,vdp_data_port  
    move.w #$0F00,vdp_data_port 
    move.w skeletonHorizontalFlip,vdp_data_port 
    move.w skeletonXpos,vdp_data_port

Как можно заметить, адрес доступный для работы начинается с 0xFF0000, а заканчивается в 0xFFFFFF, итого нам доступно 64 кбайта памяти. Позиции скелета объявлены по адресам skeletonXpos, skeletonYpos, горизонтальный флип по адресу skeletonHorizontalFlip.

Joypad

По аналогии с VDP, работа с джойпадами происходит через два порта по отдельности – порт контроля и порт данных, для первого этого 0xA10009 и 0xA10003 со-но. При работе с джойпадом есть одна интересная особенность – сначала нужно запросить комбинацию кнопок для поллинга, а затем, подождав обновления по шине, прочитать нужные нажатия. Для кнопок C/B и крестовины это 0x40, пример далее:

  move.b #$40,joypad_one_control_port; C/B/Dpad 
  nop ; bus sync 
  nop ; bus sync 
  move.b joypad_one_data_port,d2 
  rts

В регистре d2 останется состояние нажатых кнопок, либо не нажатых, в общем что просили через дата порт, то и останется. После этого идем в просмотрщик регистров Motorola 68000 вашего любимого эмулятора, смотрим чему равен регистр d2 в зависимости от нажатий. По-умному это можно узнать в мануале, но мы не верим наслово. Далее обработка нажатых кнопок в регистре d2

    cmp #$FFFFFF7B,d2; handle left 
    beq MoveLeft  
    cmp #$FFFFFF77,d2; handle right  
    beq MoveRight  
    cmp #$FFFFFF7E,d2; handle up  
    beq MoveUp  
    cmp #$FFFFFF7D,d2; handle down  
    beq MoveDown  
    rts

Проверять нужно конечно отдельные биты, а не целыми словами, но пока и так сойдет. Теперь осталось самое простое – написать обработчики всех событий перемещения по 4-м направлениям. Для этого меняем переменные в RAM, и запускаем процедуру перерисовки.

Пример для перемещения влево + изменение горизонтального флипа:

    move.w skeletonXpos,d0 
    sub.w #1,d0 
    move.w d0,skeletonXpos 
    move.w #$0801,skeletonHorizontalFlip 
    jmp FillSpriteTable

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

Не так быстро!

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

Пример замедляющего цикла и игрового цикла:

  move.w #512,frameCounter 
WaitFrame: 
  move.w frameCounter,d0 
  sub.w #1,d0 
  move.w d0,frameCounter 
  dbra d0,WaitFrame 
GameLoop: 
  jsr ReadJoypad 
  jsr HandleJoypad 
  jmp GameLoop

После этого скелет забегает медленее, что и требовалось. Как мне известно, наиболее распространенный вариант “замедления” это подсчет флага вертикальной синхронизации, можно подсчитывать сколько раз экран был отрисован, таким образом привязаться к конкретному fps.

Ссылки

https://gitlab.com/demensdeum/segagenesissamples/-/blob/main/8Joypad/vasm/main.asm

Источники

https://www.chibiakumas.com/68000/platform2.php
https://huguesjohnson.com/programming/genesis/tiles-sprites/

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

В этой заметке я опишу как рисовать спрайты с помощью VDP эмулятора приставки Sega Genesis.
Процесс отрисовки спрайтов очень схож с рендерингом тайлов:

  1. Загрузка цветов в CRAM
  2. Выгрузка частей спрайтов 8×8 в VRAM
  3. Заполнение Sprite Table в VRAM

Для примера возьмем спрайт скелета с мечом 32×32 пикселя

Skeleton Guy [Animated] by Disthorn

CRAM

С помощью ImaGenesis сконвертируем его в цвета CRAM и паттерны VRAM для ассемблера. После этого получим два файла а формате asm, далее переписываем цвета на размер word, а тайлы нужно положить в корректном порядке для отрисовки.
Интересная информация: можно переключить автоинкремент VDP через регистр 0xF на размер word, это позволит убрать инкремент адреса из кода заливки цветов CRAM.

VRAM

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

0 4 8 12

1 5 9 13

2 6 10 14

3 7 11 15

Почему все кверх ногами? А что вы хотите, ведь приставка японская! Могло быть вообще справа налево!
Поменяем вручную порядок в asm файле спрайта:

	dc.l	$11111111	; Tile #0 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111	; Tile #4 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111
	dc.l	$11111111	; Tile #8 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111122 
	dc.l	$11111122 
	dc.l	$11111166 
	dc.l	$11111166	; Tile #12 
	dc.l	$11111166 
	dc.l	$11111166 
	и т.д.

Прогрузим спрайт как обычные тайлы/паттерны:

  lea Sprite,a0 
  move.l #$40200000,vdp_control_port; write to VRAM command 
  move.w #128,d0 ; (16*8 rows of sprite) counter 
SpriteVRAMLoop: 
  move.l (a0)+,vdp_data_port; 
  dbra d0,SpriteVRAMLoop

Для отрисовки спрайта осталось заполнить таблицу спрайтов (Sprite Table)

Sprite Table

Таблица спрайтов заполняется в VRAM, адрес ее нахождения проставляется в VDP регистре 0x05, адрес опять хитрый, посмотреть можно в мануале, пример для адреса F000:

Ок, теперь запишем наш спрайт в таблицу. Для этого нужно заполнить “структуру” данных состоящую из четырех word. Бинарное описание структуры вы можете найти в мануале. Лично я сделал проще, таблицу спрайтов можно редактировать вручную в эмуляторе Exodus.
Параметры структуры очевидны из названия, например XPos, YPos – координаты, Tiles – номер стартового тайла для отрисовки, HSize, VSize – размеры спрайта путем сложения частей 8×8, HFlip, VFlip – аппаратные повороты спрайта по горизонтали и вертикали.

Очень важно помнить что спрайты могут находиться вне экрана, это корректное поведение, т.к. выгружать из памяти спрайты вне экрана – достаточно ресурсоемкое занятие.
После заполнения данных в эмуляторе, их нужно скопировать из VRAM по адресу 0xF000, Exodus также поддерживает эту возможность.
По аналогии с отрисовкой тайлов, сначала обращаемся в порт контроля VDP для начала записи по адресу 0xF000, затем в порт данных записываем структуру.
Напомню что описание адресации VRAM можно почитать в мануале, либо в блоге Nameless Algorithm.

Вкратце адресация VDP работает так:
[..DC BA98 7654 3210 …. …. …. ..FE]
Где hex это позиция бита в желаемом адресе. Первые два бита это тип запрашиваемой команды, например 01 – запись в VRAM. Тогда для адреса 0XF000 получается:
0111 0000 0000 0000 0000 0000 0000 0011 (70000003)

В итоге получаем код:

  move.l #$70000003,vdp_control_port 
  move.w #$0100,vdp_data_port 
  move.w #$0F00,vdp_data_port 
  move.w #$0001,vdp_data_port 
  move.w #$0100,vdp_data_port

После этого спрайт скелета отобразится в координатах 256, 256. Круто да?

Ссылки

https://gitlab.com/demensdeum/segagenesissamples/-/tree/main/7Sprite/vasm
https://opengameart.org/content/skeleton-guy-animated

Источники

https://namelessalgorithm.com/genesis/blog/vdp/
https://www.chibiakumas.com/68000/platform3.php#LessonP27
https://plutiedev.com/sprites

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

В этой заметке я опишу как выводить изображение из тайлов на эмуляторе Sega Genesis с помощью ассемблера.
Картинка сплэша Demens Deum в эмуляторе Exodus будет выглядеть так:

Процесс вывода PNG картинки с помощью тайлов делается по пунктам:

  1. Уменьшение изображения до размеров экрана Сеги
  2. Конвертация PNG в ассемблерный дата-код, с разделением на цвета и тайлы
  3. Загрузка палитры цветов в CRAM
  4. Загрузка тайлов/паттернов в VRAM
  5. Загрузка индексов тайлов по адресам Plane A/B в VRAM
  6. Уменьшить изображение до размеров экрана Сеги можно с помощью любимого графического редактора, например Blender.

Конвертация PNG

Для конвертации изображений можно использовать тул ImaGenesis, для работы под wine требуются библиотеки Visual Basic 6, их можно установить с помощью winetricks (winetricks vb6run), либу RICHTX32.OCX можно скачать в интернете и положить в папку приложения для корректной работы.

В ImaGenesis нужно выбрать 4 битную цветность, экспортировать цвета и тайлы в два файла формата ассемблера. Далее в файле с цветами нужно каждый цвет положить в слово (2 байта), для этого используется опкод dc.w.

Для примера CRAM сплэш скрина:

  dc.w $0000 
  dc.w $0000 
  dc.w $0222 
  dc.w $000A 
  dc.w $0226 
  dc.w $000C 
  dc.w $0220 
  dc.w $08AA 
  dc.w $0446 
  dc.w $0EEE 
  dc.w $0244 
  dc.w $0668 
  dc.w $0688 
  dc.w $08AC 
  dc.w $0200 
  dc.w $0000

Файл тайлов оставить как есть, он и так содержит корректный формат для загрузки. Пример части файла тайлов:

	dc.l	$11111111	; Tile #0 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111	; Tile #1 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111

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

Цвета в CRAM

Загрузка в CRAM производится с помощью выставления команды загрузки цвета по конкретному адресу CRAM в порт контроля (vdp control). Формат команды описан в Sega Genesis Software Manual (1989), добавлю лишь что достаточно прибавлять к адресу 0x20000 для перехода к следующему цвету.

Далее нужно загрузить цвет в порт данных (vdp data); Проще всего понять загрузку на примере ниже:

    lea Colors,a0 ; pointer to Colors label 
    move.l #15,d7; colors counter 
VDPCRAMFillLoopStep: 
    move.l  d0,vdp_control_port ;  
    move.w  (a0)+,d1; 
    move.w  d1,(vdp_data_port); 
    add.l #$20000,d0 ; increment CRAM address 
    dbra d7,VDPCRAMFillLoopStep

Тайлы в VRAM

Далее следует загрузка тайлов/паттернов в видеопамять VRAM. Для этого выберем адрес в VRAM, например 0x00000000. По аналогии с CRAM, обращаемся в порт контроля VDP с командой на запись в VRAM и стартовым адресом.

После этого можно заливать лонгворды в VRAM, по сравнению с CRAM не нужно указывать адрес для каждого лонгворда, так как есть режим автоинкремента VRAM. Включить его можно с помощью флага регистра VDP 0x0F (dc.b $02)

  lea Tiles,a0 
  move.l #$40200000,vdp_control_port; write to VRAM command 
  move.w #6136,d0 ; (767 tiles * 8 rows) counter 
TilesVRAMLoop: 
  move.l (a0)+,vdp_data_port; 
  dbra d0,TilesVRAMLoop

Индексы тайлов в Plane A/B

Теперь предстоит заполнение экрана тайлами по их индексу. Для этого заполняется VRAM по адресу Plane A/B который проставляется в регистрах VDP (0x02, 0x04). Подробнее об хитрой адресации есть в мануале Сеги, в моем примере проставлен адрес VRAM 0xC000, выгрузим индексы туда.

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

Пример кода:

  move.w #0,d0     ; column index 
  move.w #1,d1     ; tile index 
  move.l #$40000003,(vdp_control_port) ; initial drawing location 
  move.l #2500,d7     ; how many tiles to draw (entire screen ~2500) 

imageWidth = 31 
screenWidth = 64 

FillBackgroundStep: 
  cmp.w	#imageWidth,d0 
  ble.w	FillBackgroundStepFill 
FillBackgroundStep2: 
  cmp.w	#imageWidth,d0 
  bgt.w	FillBackgroundStepSkip 
FillBackgroundStep3: 
  add #1,d0 
  cmp.w	#screenWidth,d0 
  bge.w	FillBackgroundStepNewRow 
FillBackgroundStep4: 
  dbra d7,FillBackgroundStep    ; loop to next tile 

Stuck: 
  nop 
  jmp Stuck 

FillBackgroundStepNewRow: 
  move.w #0,d0 
  jmp FillBackgroundStep4 
FillBackgroundStepFill: 
  move.w d1,(vdp_data_port)    ; copy the pattern to VPD 
  add #1,d1 
  jmp FillBackgroundStep2 
FillBackgroundStepSkip: 
  move.w #0,(vdp_data_port)    ; copy the pattern to VPD 
  jmp FillBackgroundStep3

После этого остается только собрать ром с помощью vasm, запустив симулятор, увидеть картинку.

Отладка

Не все получится сразу, поэтому хочу посоветовать следующие инструменты эмулятора Exodus:

  1. Дебаггер процессора m68k
  2. Изменение количества тактов процессора m68k (для slow-mo режима в дебаггере)
  3. Вьюверы CRAM, VRAM, Plane A/B
  4. Внимательно читать документацию к m68k, используемым опкодам (не все так очевидно, как кажется на первый взгляд)
  5. Смотреть примеры кода/дизассемблинга игр на github
  6. Реализовать сабрутины эксепшенов процессора, обрабатывать их

Указатели на сабрутины эксепшенов процессора проставляются в заголовке рома, также на GitHub есть проект с интерактивным рантайм дебаггером для Сеги, под названием genesis-debugger.

Используйте все доступные инструменты, приятного олдскул-кодинга и да прибудет с вами Blast Processing!

Ссылки

https://gitlab.com/demensdeum/segagenesissamples/-/tree/main/6Image/vasm
http://devster.monkeeh.com/sega/imagenesis/
https://github.com/flamewing/genesis-debugger

Источники

https://www.chibiakumas.com/68000/helloworld.php#LessonH5
https://huguesjohnson.com/programming/genesis/tiles-sprites/

 

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

В этой заметке я опишу как загружать цвета в палитру Сеги на ассемблере.
Итоговый результат в эмуляторе Exodus будет выглядеть так:

Чтобы процесс происходил проще, найдите в интернете pdf под названием Genesis Software Manual (1989), в нем описывается весь процесс в мельчайших деталях, по сути, эта заметка является комментариями к оригинальному мануалу.

Для того чтобы записывать цвета в VDP чип эмулятора Сеги, нужно сделать следующие вещи:

  • Отключить систему защиты TMSS
  • Записать правильные параметры в регистры VDP
  • Записать нужные цвета в CRAM

Для сборки будем использовать vasmm68k_mot и любимый текстовый редактор, например echo. Сборка осуществляется командой:

Порты VDP


VDP чип общается с M68K через два порта в оперативной памяти – порт контроля и порт данных.

По сути:


    

  1. Через порт контроля можно выставлять значения регистрам VDP.
    2. 

  2. Также порт контроля является указателем на ту часть VDP (VRAM, CRAM, VSRAM etc.) через которую передаются данные через порт данных
    3. 



Интересная информация: Сега сохранила совместимость с играми Master System, на что указывает MODE 4 из мануала разработчика, в нем VDP переключается в режим Master System.


Объявим порты контроля и данных:


vdp_data_port        = $C00000


Отключить систему защиты TMSS


Защита от нелицензионных игр TMSS имеет несколько вариантов разблокировки, например требуется чтобы до обращения к VDP в адресном регистре A1 лежала строка “SEGA”.




MOVE.B A1,D0; Получаем версию хардвары цифрой из A1 в регистр D0 
ANDI.B 0x0F,D0; По маске берем последние биты, чтобы ничего не сломать 
BEQ.B SkipTmss; Если версия равна 0, скорее всего это японка или эмулятор без включенного TMSS, тогда идем в сабрутину SkipTmss 
MOVE.L "SEGA",A1; Или записываем строку SEGA в A1 





Записать правильные параметры в регистры VDP


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


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


Возьмем готовые параметры с комментариями из блога bigevilcorporation:





VDPReg0:   dc.b $14 ;  0: H interrupt on, palettes on 
VDPReg1:   dc.b $74 ;  1: V interrupt on, display on, DMA on, Genesis mode on 
VDPReg2:   dc.b $30 ;  2: Pattern table for Scroll Plane A at VRAM $C000 
                    ;     (bits 3-5 = bits 13-15) 
VDPReg3:   dc.b $00 ;  3: Pattern table for Window Plane at VRAM $0000 
                    ;     (disabled) (bits 1-5 = bits 11-15) 
VDPReg4:   dc.b $07 ;  4: Pattern table for Scroll Plane B at VRAM $E000 
                    ;     (bits 0-2 = bits 11-15) 
VDPReg5:   dc.b $78 ;  5: Sprite table at VRAM $F000 (bits 0-6 = bits 9-15) 
VDPReg6:   dc.b $00 ;  6: Unused 
VDPReg7:   dc.b $00 ;  7: Background colour - bits 0-3 = colour, 
                    ;     bits 4-5 = palette 
VDPReg8:   dc.b $00 ;  8: Unused 
VDPReg9:   dc.b $00 ;  9: Unused 
VDPRegA:   dc.b $FF ; 10: Frequency of Horiz. interrupt in Rasters 
                    ;     (number of lines travelled by the beam) 
VDPRegB:   dc.b $00 ; 11: External interrupts off, V scroll fullscreen, 
                    ;     H scroll fullscreen 
VDPRegC:   dc.b $81 ; 12: Shadows and highlights off, interlace off, 
                    ;     H40 mode (320 x 224 screen res) 
VDPRegD:   dc.b $3F ; 13: Horiz. scroll table at VRAM $FC00 (bits 0-5) 
VDPRegE:   dc.b $00 ; 14: Unused 
VDPRegF:   dc.b $02 ; 15: Autoincrement 2 bytes 
VDPReg10:  dc.b $01 ; 16: Vert. scroll 32, Horiz. scroll 64 
VDPReg11:  dc.b $00 ; 17: Window Plane X pos 0 left 
                    ;     (pos in bits 0-4, left/right in bit 7) 
VDPReg12:  dc.b $00 ; 18: Window Plane Y pos 0 up 
                    ;     (pos in bits 0-4, up/down in bit 7) 
VDPReg13:  dc.b $FF ; 19: DMA length lo byte 
VDPReg14:  dc.b $FF ; 20: DMA length hi byte 
VDPReg15:  dc.b $00 ; 21: DMA source address lo byte 
VDPReg16:  dc.b $00 ; 22: DMA source address mid byte 
VDPReg17:  dc.b $80 ; 23: DMA source address hi byte, 
                    ;     memory-to-VRAM mode (bits 6-7)  





Ок, теперь пойдем в порт контроля и запишем все флажки в регистры VDP:




    move.l  #VDPRegisters,a0 ; Пишем адрес таблицы параметров в A1 
    move.l  #$18,d0          ; Счетчик цикла - 24 = 18 (HEX) в D0 
    move.l  #$00008000,d1    ; Готовим команду на запись в регистр VDP по индексу 0, по мануалу - 1000 0000 0000 0000 (BIN) = 8000 (HEX) 

FillInitialStateForVDPRegistersLoop: 
    move.b  (a0)+,d1         ; Записываем в D1 итоговое значение регистра VDP из таблицы параметров, на отправку в порт контроля VDP  
    move.w  d1,vdp_control_port     ; Отправляем итоговую команду + значение из D1 в порт контроля VDP 
    add.w   #$0100,d1        ; Поднимаем индекс регистра VDP на 1 (бинарное сложение +1 к индексу по мануалу Сеги) 
    dbra    d0,FillInitialStateForVDPRegistersLoop ; Уменьшаем счетчик регистров, продолжаем цикл если необходимо


Самое сложное это прочитать мануал и понять в каком формате подаются данные на порт контроля, опытные разработчики разберутся сразу, а вот неопытные… Немного подумают и поймут, что синтаксис для записи регистров такой:


0B100(5 бит – индекс регистра)(8 бит/байт – значение)


0B1000001001000101 – записать в регистр VDP 2 (00010), значение флажков 01000101.


Записать нужные цвета в CRAM


Далее идем писать два цвета в память цветов CRAM (Color RAM). Для этого пишем в порт контроля команду на доступ к цвету по индексу 0 в CRAM и отправляем по дата порту цвет. Все!


Пример:




    move.l  #$C0000000,vdp_control_port ; Доступ к цвету по индексу 0 в CRAM через порт контроля  
    move.w  #228,d0; Цвет в D0 
    move.w  d0,vdp_data_port; Отправляем цвет в порт данных 





После сборки и запуска в эмуляторе в Exodus, у вас должен быть залит экран цветом 228.


Давайте зальем еще вторым цветом, по последнему байту 127.






  move.l  #$C07f0000,vdp_control_port ; Доступ к цвету по байту 127 в CRAM через порт контроля 
  move.w  #69,d0; Цвет в D0 
  move.w  d0,vdp_data_port; Отправляем цвет в порт данных 





Ссылки


https://gitlab.com/demensdeum/segagenesissamples
https://www.exodusemulator.com/

http://sun.hasenbraten.de/vasm/

https://tomeko.net/online_tools/bin_to_32bit_hex.php?lang=en


Источники


https://namelessalgorithm.com/genesis/blog/genesis/
https://plutiedev.com/vdp-commands

https://huguesjohnson.com/programming/genesis/palettes/

https://www.chibiakumas.com/68000/helloworld.php#LessonH5

https://blog.bigevilcorporation.co.uk/2012/03/09/sega-megadrive-3-awaking-the-beast/

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

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

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

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

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

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

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

Структура

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

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

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

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


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

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

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

    NOP
    NOP
    NOP 
    NOP
    NOP
    JSR 0x00000200

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

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

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



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




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


Ссылки


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


https://gitlab.com/demensdeum/segagenesissamples


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


Источники


ROM Hacking Demo – Genesis and SNES games in 480i


http://68k.hax.com/


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


https://plutiedev.com/rom-header


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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

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

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

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

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

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

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

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

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

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

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

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


model.save_model("model.bin")





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




predictResult = model.predict("Bleed")
print(predictResult)


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

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

Пример создания модели с использованием файла тест:






Источники


https://fasttext.cc

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


Исходный код


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

x86_64 Assembler + C = One Love

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

    message: db "Hello, world!", 10, 0

section .text
    extern printf
    extern exit
    global main

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

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

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

    extern printf
    extern exit
    global main

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

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


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





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




    call exit





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


Источники


https://www.devdungeon.com/content/how-mix-c-and-assembly
https://nekosecurity.com/x86-64-assembly/part-3-nasm-anatomy-syscall-passing-argument

https://www.cs.uaf.edu/2017/fall/cs301/reference/x86_64.html


Исходный код


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

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

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

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



section .text

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

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

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





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


Под лупой


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




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


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


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


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


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


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


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


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


Рассмотрим аргументы подробнее, в заголовочном файле asm/unistd_64.h находим номер функции __NR_write – 1, далее в документации смотрим аргументы для write:

ssize_t write(int fd, const void *buf, size_t count);


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


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


msglen equ $-message


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


Источники


https://github.com/Dman95/SASM

https://www.nasm.us/xdoc/2.15.05/html/nasmdoc0.html

http://acm.mipt.ru/twiki/bin/view/Asm/HelloNasm

https://jameshfisher.com/2018/03/10/linux-assembly-hello-world/

http://www.ece.uah.edu/~milenka/cpe323-10S/labs/lab3.pdf

https://c9x.me/x86/html/file_module_x86_id_176.html

https://www.recurse.com/blog/7-understanding-c-by-learning-assembly

https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%BB%D0%BE%D0%B3_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D0%B4%D1%83%D1%80%D1%8B

https://www.tutorialspoint.com/assembly_programming/assembly_basic_syntax.html

https://nekosecurity.com/x86-64-assembly/part-3-nasm-anatomy-syscall-passing-argument

https://man7.org/linux/man-pages/man2/syscall.2.html

https://en.wikipedia.org/wiki/Write_(system_call)


Исходный код


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

Хеш таблица

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

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

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

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

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

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

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

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

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

Источники

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

Исходный код

https://gitlab.com/demensdeum/datastructures

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

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

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

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

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

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

chdir(SDL_AndroidGetInternalStoragePath());

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

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

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

Источники

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

Исходный Код

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

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

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

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

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

пMVkcatS olleHП

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

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

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

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

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

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

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

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

Источники

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

Исходный код

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

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