Как программист 6809 обхитрил железо, чтобы игра летала

В те времена MS-DOS мой друг Уорд Кристенсен работал в IBM в отделе технической поддержки продаж. У них был неофициально поддерживаемый файл, в котором перечислялись все продукты, которые они продавали, в формате, который можно было прочитать на ПК. Он очень хорошо умел искать по нему в своём текстовом редакторе, но хотел отдельную программу для MS-DOS, чтобы его коллегам было легко искать. Так родился PCxREF — программа на Turbo Pascal, которую написал я и которая включала поиск.

Моя первая версия была наивным поиском с использованием встроенного сопоставления строк. Из-за размера файла и скорости ПК поиск иногда занимал более 30 секунд. Уорд хотел быстрее, намного быстрее.

В конце концов я придумал алгоритм, который брал текст, который вы хотели найти, и превращал его в специальную битовую маску, таблицу. Это была таблица длиной 256 байт, инициализированная нулями. Если первый символ искомой строки был D, то первый бит маски для $44 и $64 устанавливался, чтобы учитывать регистр. Подстановочный знак * был длиной всего в 1 символ, но устанавливал все биты для этого символа. Затем я использовал инструкцию 8088 XLAT и очень маленький цикл, чтобы принять символ из текста, использовать его как индекс в таблице масок, выполнить AND с существующим флагом в другом регистре, затем сдвинуть его, проверяя CARRY (совпадение!) и повторяя цикл, если не ноль.

Это сократило поиск до менее чем 3 секунд, если весь файл был загружен в RAM. Тонкий […]

Несколько связано [1]:

> Много лет назад я работал в Video Seven, ныне исчезнувшем производителе видеокарт, помогая разрабатывать клон VGA. Парень, который проектировал чип VGA для Video Seven, Том Уилсон, месяцами работал круглосуточно, чтобы его VGA работал как можно быстрее, и был уверен, что почти выжал из него максимум. Однако, когда Том заканчивал отделку дизайна своего чипа, из четвёртых рук пришла новость, что конкурент, Paradise, поднял производительность разрабатываемого ими клона, добавив FIFO.

> Это было всё, что он знал; не было информации о том, что за FIFO, насколько это помогло, или о чём-либо ещё. Тем не менее, Том, обычно приветливый и расслабленный, приобрёл бодрствующий, затравленный вид человека, в котором слишком много кофеина и нет ответов, пока пытался выяснить по безнадёжно скудной информации, что сделал Paradise. Наконец он заключил, что Paradise, должно быть, поставил FIFO записи между системной шиной и VGA, так что когда CPU писал в видеопамять, запись немедленно попадала в FIFO, позволяя CPU продолжать обработку вместо простоя при каждой записи в память дисплея.

> Том не мог пожертвовать вентилями или временем на полный FIFO, но мог реализовать FIFO глубиной в один элемент, позволяя CPU опережать VGA на одну запись. Он не был уверен, насколько хорошо это сработает, но это было всё, что он мог сделать, поэтому он вставил это и отправил чип в производство.

> FIFO глубиной в один элемент оказался работающим […]

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

Пытаюсь выяснить, в каком компьютере на самом деле был 6509; кандидаты, похоже, Dragon или Tandy?

Именно из-за такого Amiga была настолько массово успешной, добавив набор сопроцессоров: https://en.wikipedia.org/wiki/Amiga_Original_Chip_Set

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