Author Archives: demensdeum

Как запустить 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, с опорой на оригинальный документ.

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

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