Pull to refresh

Программа вывода лабиринта в 13… нет. 10 байт!

Reading time 5 min
Views 44K
Original author: Trixter
В прошлом, найдя интересное решение при написании демки, я тихо его использовал или же хвастался узкому кругу друзей на демосцене. Но теперь мои возможности достигнуть чего-либо на демосцене подошли к концу, а турниры по минималистскому программированию не проводятся, поэтому я решил написать в блог о своём достижении: генераторе лабиринтов объёмом всего в 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             ;выставляем цветной режим 40x25 
        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).
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
+72
Comments 34
Comments Comments 34

Articles