Паттерны 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#

class Application {
        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#

interface IExpression
{
    String interpret(Context context);
}

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

class ConstantExpression : TerminalExpression
{
    private String constant;

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

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

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

class PerformExpression : NonTerminalExpression
{
    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:

run input = 
  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: ParseLeafsState -> ParseLeafsState
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).
А делается это довольно просто, каждый пиксель цветовой канал буфера преобразуется по определенной формуле и на выходе получается изображение серого цвета.
Метод среднего:

const average = (red + green + blue) / 3;
red = average;
green = average;
blue = average;

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

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

const luminance = 0.2126 * red + 0.7152 * green + 0.0722 * blue;
red = luminance;
green = luminance;
blue = luminance;

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

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

function rgb2grayscale(
    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 году ученый Алан Тьюринг в своей публикации “On Computable Numbers, With An Application to Entscheidungsproblem” описывает использование универсальной вычислительной машины которая смогла бы поставить точку в вопросе проблемы разрешимости в математике. По итогу он приходит к выводу что такая машина ничего бы не смогла решить корректно, если бы результат ее работы инвертировали и зациклили бы на саму себя. Получается что *идеальный* антивирус невозможно создать, *идеальный* плиткоукладчик тоже, программу которая подсказывает идеальные фразы для твоего краша и т.д. Парадокс-с!

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

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

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

class MapInfiniteTape implements InfiniteTape { 
final _map = Map<int, String>(); 

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

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

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

class TapeHead { 
  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-конфигурации” по которым может решать что делать дальше. На современном языке – состояния и обработчики состояний. Пример обработчика состояний:

class FiniteStateControl { 
  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_STOP = "stop"; 
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

print 
hello world 
stop

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

increment next
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, до сих пор люди не придумали ничего лучше. Объявим адреса переменных, изменим код отрисовки:

skeletonXpos = $FF0000
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, пример далее:

ReadJoypad: 
  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

HandleJoypad:  
    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, и запускаем процедуру перерисовки.

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

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

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

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

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

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

StartWaitFrame: 
  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 файле спрайта:

Sprite: 
	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 
	и т.д. 

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

SpriteVRAM: 
  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:

dc.b $78 ; 0x05:  Sprite table at VRAM 0xF000 (bits 0-6 = bits 9-15) 

Ок, теперь запишем наш спрайт в таблицу. Для этого нужно заполнить “структуру” данных состоящую из четырех 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)

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

SpriteTable: 
  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 сплэш скрина:

 Colors: 
  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 

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

 Tiles: 
	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); Проще всего понять загрузку на примере ниже:

VDPCRAMFillLoop: 
    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)

TilesVRAM: 
  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, поэтому отрисовав экранное пространство, ваш рендер должен остановить отрисовку и продолжить заново когда курсор перейдет на новую строку. Вариантов как реализовать это множество, я использовал простейший вариант подсчета на двух регистрах счетчика ширины изображения, счетчика позиции курсора.

Пример кода:

 FillBackground: 
  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/