[Перевод] Программа вывода лабиринта в 13… нет. 10 байт!
В прошлом, найдя интересное решение при написании демки, я тихо его использовал или же хвастался узкому кругу друзей на демосцене. Но теперь мои возможности достигнуть чего-либо на демосцене подошли к концу, а турниры по минималистскому программированию не проводятся, поэтому я решил написать в блог о своём достижении: генераторе лабиринтов объёмом всего в 13 байт машинного кода x86.Чтобы понять суть достижения, вам надо знать о команде 10 PRINT. Это строчка кода Commodore 64 BASIC, которая при запуске создаёт бесконечный лабиринт. Конечно, её вывод — это не настоящий лабиринт, входа и выхода там нет, и полно закрытых помещений и тупиков. Но выглядит он как лабиринт. Поражает то, как простая команда выдаёт бесконечно сложный шаблон.Также под названием »10 PRINT» издана книга на 324 страницы. Она рассказывает про код, искусство, восприятие, культуру, случайности, лабиринты и всё остальное. Рекомендуется к прочтению всем, кто интересуется программированием — там для каждого найдутся интересные темы, которые к тому же очень хорошо освещены и оформлены.
42 bytesВернёмся к коду. В книжке »10 PRINT» я прочёл, что код из BASIC можно представить в более компактном виде в машинном коде C64. Там же была задачка для читателей. Рекорд был поставлен товарищами 4-Mat и Wisdom, которые впихнули решение в 15 байт. Мне стало интересно, а как это можно сделать на x86. Вот я и написал первую версию этой программы: ; Простая программа, имитирующая вывод команды »10 PRINT» ; В этой версии используется «настоящий» рандом и не делается ; никаких предположений о содержимом регистров. ; Также мы переходим в режим низкого разрешения ; чтобы добиться более приемлемого соотношения сторон ; и выходим из программы по окончанию вывода лабиринта.
init: mov ax,0001h int 10h; выставляем цветной режим 40×25 xor bh, bh; видео задали, поэтому vidpage=0 mov cx,(40×23) ; количество символов для вывода getrnd: xor ax, ax; чтобы получить al=0 pushf cli; запрещаем прерывания, чтение таймера должно быть атомарным out 43h, al; запираем регистр счётчика in al,40h; читаем lobyte счётчика mov ah, al in al,40h; читаем hibyte счётчика popf; включаем прерывания xchg ah, al; теперь содержит 8253 raw 16-bit word pickch: shr ax,1; BIOS инициализируется в count-by-2, первый бит всегда lo shr ax,1; carry = «случайный» бит mov al,'\' jc writec; если бит взведён, сразу пишем mov al,'/' ; иначе выбираем другой символ writec: mov ah,0eh; выводим символ в режиме телетайпа int 10h loop getrnd int 20h; выходим в DOS Этот код ведёт себя «прилично», не делает предположений о состоянии процессора и завершает работу (оригинальная версия 10 PRINT работала бесконечно). Случайное число более-менее неплохо генерится из железячного таймера, который каждую секунду отсчитывает от 65535 до 0. При компиляции a86 выходит 42-байтовый файл .COM
Размер сильно отличается от C64 в двух местах: генератор случайных чисел и выбор символа. У C64 преимущество в символах, т.к. оба слеша находятся рядом в PETSCII. Если у вас есть рандомный бит, его можно просто добавить к первому слэшу, и получить либо его, либо второй слэш. При использовании ASCII это не прокатит, приходится использовать условие.
Затем для оптимизации я решил убрать условие выбора. При сдвиге кода одного из слэшей оба слэша начинают отличаться всего одним битом.
»/»=2f и »\»=5c 2f=00101111 5c=01011100 Поэтому можно заменить кусок «pickch»:
pickch: shr ax,1; BIOS инициализируется в count-by-2, первый бит всегда lo push cx; Сохраняем счётчик цикла mov cl, al; копируем случайное число в cl and cl,1; cl теперь 0 или 1 mov al,'\' ; задаём символ '\' shr al, cl or al, cl; если cl=1, то '\' превращается в '/', иначе — без изменений Это было круто, но размер в результате увеличился до 48 байт. Пришлось отбросить идею.
Ещё одна оптимизация — убрать процедуру вывода writec, и просто пихать байты в видеопамять. Это убирало два байта с процедуры вывода, но добавляло 4 байта на настройку (и 5, если оставаться в пределах стандарта 8086), поэтому это тоже пришлось отбросить.
25 байт Я внимательнее посмотрел на самый большой отрезок программы — генератор случайных чисел. Очевидно, что качество генератора нас не особо заботит — главное, чтобы не было очевидных повторений. Поэтому я заменил блок «getrnd» одной инструкцией LODSB. Она вынимает байт из памяти и переходит на следующий, поэтому можно читать последовательность из памяти. А место, с которого я начал читать — то, куда показывает DS: SI при старте программы. Для COM-файла в DOS он показывает на начало самой программы. Поэтому мой «случайный» поток определялся самим скомпилированным кодом, и всяким мусором от других программ. В результате код сильно уменьшился до 25 байт15 байт Тут я уже раззадорился — появилась возможность приблизиться к размеру версии C64. Я избавился от всяких телодвижений типа смены видеорежима, чистого выхода (теперь программа работает вечно) и инициализации регистров. В конце это выглядело так: init: mov ah,0eh;10h для вывода символов в режиме телетайпа getrnd: lodsb; прочтём байт с того места, куда указывает DS: SI pickch: shr al,1; carry = «случайный» бит mov al,'\' jc writec; если бит взведён, сразу пишем mov al,'/' ; иначе выбираем другой символ writec: int 10h; выводим символ jmp getrnd; бесконечный цикл 15 байт — это успех!
13 байт Мне всё казалось, что я могу улучшить блок «pickch». Блок начинается с присваивания случайной величины в флаг carry, но у 8086 есть флаг чётности, который взводится автоматически в некоторых случаях. К сожалению, LODSB флаги не взводил. Математическая операция взвела бы флаг чётности, но такая операция заняла бы больше места. Если бы найти однобайтовую инструкцию, которая делает то же, что LODSB, и взводит флаг чётности в зависимости от входных данных…Есть такая инструкция! SCAS — загружает байт, сравнивает его с AL, и взводит флаг по результатам сравнения. Она предназначена для использования в цикле, но никто не мешает использовать её без цикла. И что в результате:
init: mov ah,0eh;10h для вывода символов в режиме телетайпа getrnd: scasb; прочесть с места ES: DI и сравнить с AL ; взводит флаг вместо вычитания pickch: mov al,'\' ; выбрать символ jc writec; если бит взведён, сразу пишем mov al,'/' ; иначе выбираем другой символ writec: int 10h; выводим символ jmp getrnd; бесконечный цикл И вот вам 13 байт. Работает даже на старых IBM PC, поскольку не использует инструкций от 80186+. Примерный вывод:
12 байт Читатель Питер Ферье умудрился улучшить моё достижение на один байт init: mov ax,0e5ch; загрузим AH с cmd «запись символа» и AL с '\' scasb; прочесть с места ES: DI и сравнить с AL ; this sets flags similar to a subtraction pickch: jp writec; Если флаг чётности взведён, переходим к выводу символа из AL mov al,»/» ; иначе выбираем другой символ writec: int 10h; вывести символ из AL jmp init; бесконечный цикл Брависсимо. Однако ж, читатель herm1t отметил, что если мы используем int 29h для вывода символа, то код сокращается до
11 байт init: mov al, '\' scasb jp writec mov al, '/' writec: int 29h jmp init Хитро. Но погодите-ка, это ещё не всё!
10 байт init: scasb salc and al,'\'-'/' add al,'/' int 29h jmp init Питер нанёс ответный удар и стесал ещё один байт (этот код не будет работать на не-интеловских процессорах типа NEC V20 или V30).
