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

Автор оригинала: 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).

Комментарии 34

    +6
    Вывод программы?
      +27
      /\\\\\/\\\
      /\\\//\///
      //\/\\\/\\
      \\/\/\/\\\
      /\\/\/\\//
      /\/\////\\
      \//\\\////
      //\/\//\/\
      \\//\/\\\\
      ///\///\/\
      
        +6
        А за что минусы?
        Примерно такой и будет, но только 80 символов в строке.
          +23
          Потому что бо́льшая часть людей ничего длиннее твита вдумчиво прочесть не способна. Статью они не прочли, вот им и кажется, что выше — бред.
            +6
            Я думаю, все же на хабре таких людей нет, потому что тут, как ни странно, все статьи несколько длиннее твитов.

            А минусы, наверное, потому что не все способны мысленно убрать слишком большой промежуток между строками, из-за которого лабиринт не воспринимается как лабиринт. Наверное, надо было мне не лениться и картинкой сделать.
              +31
              и картинкой
              image
              0
              Зачем же за других отвечать? Кому захочется ответить — ответят, почему поставили минус. «Потому что все вокруг идиоты» — слишком поверхностное и часто неправильное объяснение.
                0
                Потому что делать выводы и прогнозы — можно и нужно.
                  –1
                  Так это был вопрос к тем людям, которые поставили минус. Я вообще сначала подумал, что ты про себя отвечаешь.
        +8
        Няя, int 10h!
        Ах, как молоды мы были!
          +1
          турниры по минималистскому программированию не проводятся


          ностальжи. В самих турах не участвовал, но помню красноглазые вечера… На wasme помню полноценный viewer в сотню байт, сам как то уложил md5 в сто восемьдесят, вместе с таблицей констант. Были времена. Может возродить традиции? Я бы поучаствовал.
          +1
          А лабиринт будет иметь решение? :)
            +1
            О каком решении вообще речь, если у него нет ни стартовой точки, ни границ?.. Ну хорошо, границы — это границы экрана. А начинать из какой точки?
              0
              Из (0, 0) конечно же!
              +2
              Нет, потому что этот лабиринт представляет из себя несколько независимых колец: по ним можно ходить кругами. Посмотрите на картинки лабиринта: из каждой клетки там ровно два пути. Когда выбор куда идти дальше всего один, то это не лабиринт.
                +5
                Если применить к картинке размытие+контрастность, то можно в графических редакторах заливать цветом пути — так нагляднее.
                image
                По чёрным фигуры получаются похожими.
                  +4
                  Заливка по чёрным
                  image
                    +2
                    Ну и где тут хоть одно разветвление?
                      +4
                      Её можно оптимизировать до 4 красок )
                        0
                        А где тут лабиринт, кроме похожего узора я не вижу никакого челенджа для человека входящего вон там вот снизу к примеру на голубую тропу?
                        +1
                        О! нескучные обои!
                      +1
                      '\'-'/'
                        0
                        Praise the Sun?
                        +15
                        Как-то слегка странно вы сократили оригинальную программу, равно как и название книги. «10 PRINT» на Бейсике выведет пустую строку и завершится.

                        А вот оригинальная программа, она нарисует лабиринт. А то получается вообще непонятна связь между тем, что написали вы на ассемблере и коммодоровской программой.

                        Программа:

                        10 PRINT CHR$(205.5+RND(1));: GOTO 10

                        Демонстрация на C64:

                        www.youtube.com/watch?v=m9joBLOZVEo

                        Книга:

                        mitpress.mit.edu/books/10-print-chr2055rnd1-goto-10-0
                        –1
                        x86??? МК-61!!!
                          +1
                          Самой короткой и самой полезной в моей личной практике была программа для «Нейрона» из 15 байт. Она поднимала производительность в тесте PCTOOLS с 0.6 до 0.95 оригинальной ХТ. Одногруппники жены удивлялись на лабораторных, почему у нее в классе комп работал заметно быстрее :-)
                            0
                            Поди, регенерацией памяти играли? Было приятно, но индивидуально для каждой железки.
                              +1
                              Именно. Перепрограммировал канал таймера, ответственный за ПДП, имея в руках стопку заводской документации :)
                                0
                                Э… все же рискну спросить: какое отношение ПДП имеет к регенерации памяти?
                                  0
                                  Контроллер ПДП в Нейроне использовался для регенерации памяти. Стояли К565РУ3 и цикл обновления 32 микросекунды. Я поставил 128, за счёт этого резко уменьшилось число конфликтов с процессором.
                            +2
                            Спектрум, фреймовые бегущие строки, нулевая строка в бейсике… Эх, ностальгия ща опять заставит эмулятор на мобилке запустить и перепройти какую-нибудь Диззи :)
                              +2
                              Было дело. Разбирался на антресолях, нашел свой старый самопайный спектрум.
                              И накатило… И повод придумал — дай думаю сынуле ретруху покажу. Восстановил отсохшее от времени, подключил к телеку, нашел (чудом не развинченный тем же сынулей) флопповод на 5.25". Позапускал игрушек — как же долго они грузятся… Вот, говорю, сынуля смотри, какая классная штуковина!
                              Сынуля сказал:
                              «Ну что, прикольно… Пап, пока ты тут развлекаешься, можно я возьму твой планшет?»…
                              Разобрал я все аккуратненько и уложил обратно в дальний угол антресоли.
                              Так! Кто взял мой планшет?

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое