Самая короткая программа вывода десятичного числа
В 1984-ом году вышла культовая книга Стивена Леви «Хакеры: герои компьютерной революции». Существует любительский русский перевод, но он далёк от идеала. Я было взялся исправлять неточности в нём, положив рядом английский оригинал (кстати, и он не без греха), да забросил после второй главы. Так или иначе, хочу обратить ваше внимание на фрагмент (можно прочитать его в виде отдельной статьи), посвящённый подпрограмме печати числа в десятичной системе. Насколько можно уменьшить такую программу? Каков предел?
В августе 2018-го года я писал программу для измерения точного времени исполнения команд советского процессора 1801ВМ1 (он обладает набором инструкций PDP-11). Знание точного времени (в тактах процессора) было необходимо при работе над демо «Good Apple» для компьютера БК 0011М. Результаты измерений я хотел видеть в десятичной системе счисления. Для этого пришлось написать свою подпрограмму — системные функции были недоступны в силу специфики теста.
Первое, что я сделал — составил массив TEN со степенями числа 10. Процедура принимает число в регистре R0, на выходе текстовая строка по адресу NUMBER. Важно: в процессоре нет инструкции деления!
MOV #NUMBER,R1 ; pointer to output text string
MOV #TEN,R5
1: CMP (R5)+,R0 ; skip leading zeros
BHI 1 ; branch if higher, for 16-bit not signed
MOV -(R5),R3
BEQ 4 ; if less then 10
2: MOV #47.,R4 ; 0 symbol in ASCII codepage - 1
3: INC R4 ; count digits
SUB R3,R0
BHIS 3 ; branch if higher or same, for 16-bit not signed
MOVB R4,(R1)+ ; print R4
ADD (R5)+,R0
MOV (R5),R3
BNE 2
4: ADD #48.,R0 ; 0 symbol in ASCII codepage
MOVB R0,(R1)+ ; print R0
CLRB (R1) ; end of text marker
RET
TEN: .WORD 10000.,1000.,100.,10.,0
Чтобы понимать ассемблер PDP-11, достаточно помнить, что аргументы записывают слева направо (сначала источник, затем приёмник), а команды условных переходов начинаются с буквы B (от слова branch — ветвление). Описывать алгоритм не стану, он ничем не интересен и приведён здесь лишь в качестве отправной точки. Размер этой подпрограммы — 22 слова.
После того, как всё заработало, я вдруг вспомнил историю из книги Стивена Леви: хакеры бились над уменьшением размера аналогичной программы, причём тоже на архитектуре PDP. Правда, у них была PDP-1, но через несколько лет они заполучили и PDP-11.
Открыв книгу, я обнаружил крайне туманное описание. Начинали хакеры из MIT так же, как и я — со списка десятичных разрядов. Но что произошло дальше, из текста непонятно. Очевидно, это не было понятно и автору книги, он просто записал общие слова из уст очевидцев того хакерского состязания.
Пришлось покопаться в Интернет-архиве программ для PDP-1. Там много интересного: Minskytron, Munching squares и другие так называемые «дисплейные хаки» (кстати, примечательно, что уже тогда — в начале 60-ых — хакеры из MIT использовали термин «демо» в том же смысле, в котором мы используем его сейчас на демосцене). В архиве много системных подпрограмм, но вывода десятичного числа среди них, увы, нет.
Тогда, вооружившись отладчиком, я решил посмотреть, как реализована эта процедура в операционной системе MKDOS, которой я пользуюсь на БК 0010 и БК 0011М. О, чудо! — присмотревшись, я понял, что подпрограмма очень хорошо подходит под туманное описание из книги «Хакеры». Вот её код:
MOV #10.,R4
CLR R2
1: CLR R1
2: SUB R4,R0 ; вычитаем из числа 10, пока ничего не останется
BLO 3
INC R1 ; счётчик - сколько вычитаний сделали
BR 2
3: ADD R4,R0
ADD #48.,R0 ; ASCII-код числа 0
INC R2 ; счётчик - сколько символов сохранили
MOVB R0,-(SP)
MOV R1,R0 ; теперь число вычитаний - наш новый аргумент
BNE 1
INC R2
MOVB #32.,-(SP) ; ASCII-код пробела
4: MOVB (SP)+,R0
CALL PRINT
SOB R2,4 ; цикл по числу сохранённых символов
RET
Программа формирует текстовую строку в стеке, затем вызывает процедуру печати каждого сохранённого символа. Судя по всему, именно это имелось в виду в книге Стивена Леви под фразой «конвертирует обратным образом, а при помощи хитрого программного фокуса печатает в нужном порядке». Остальные особенности алгоритма должны быть понятны по комментариям к коду.
Размер подпрограммы — 23 слова, но сравнивать ей с моей подпрограммой напрямую нельзя: слишком разные условия. Я решил переделать программу из MKDOS под свои условия: формирование текстовой строки в памяти.
В конечном итоге я понял, что лучше оставить только идею вычитания числа 10, а всё остальное написать с нуля. После нескольких кругов Сансары оптимизации у меня получилось следующее:
MOV #NUMBER,R1 ; pointer to output text string
CLRB -(R1) ; end of text marker
MOV #10.,R4
1: MOV #-1.,R5
2: INC R5 ; counter of 10s
SUB R4,R0
BHIS 2 ; branch if higher or same
ADD #58.,R0 ; #10. + '0' ASCII code
MOVB R0,-(R1) ; store R0 to text string
MOV R5,R0 ; let's count next how many 10s in number of 10s
BNE 1
RET ; returns text string pointer in R116 слов, предел достигнут (думал я), вот она — Нирвана, о которой так эмоционально писал Стивен Леви!
Какие трюки здесь применены:
- Первая команда устанавливает указатель не в начало, а в конец текстовой строки. Текст заполняется справа налево — это удобно ещё и тем, что на выходе мы получаем адрес начала строки, готовый к передаче в процедуру печати текста.
- Счётчик вычитаний начинается не с нуля, а с минус единицы. Первая команда внутри цикла (INC R5) увеличивает счётчик на 1. Всё равно получается 0, так почему бы сразу не очищать счётчик, зачем всё это?… Дело в том, что при первом же вычитании 10 можно получить отрицательный результат — тогда нужно выйти из цикла, при этом счётчик должен равняться нулю. Значит, увеличение счётчика придётся делать уже после проверки. А следом нужна команда перехода в начала цикла. Итого — на одну команду больше. С точки зрения размера разницы нет: мы потеряем 1 слово, добавив команду перехода, но сэкономим 1 слово на записи минус единицы (очистка регистра короче). И всё же, имеет смысл уменьшить количество команд внутри цикла, так он будет исполняться быстрей. Да и программа в целом визуально сократится. Поэтому я пришёл к решению с -1.
- Вычитая число 10, мы могли бы не дожидаться отрицательного результата, а выходить из цикла раньше, когда аргумент станет меньше десяти. Но сравнение с числом — отдельная операция (и дополнительное время). В противовес этому, сравнение с нулём производится процессором автоматически после любой арифметической операции — можно сразу совершать условный переход. Однако, потом всё же придётся прибавить десятку, несправедливо отнятую у входного аргумента. Оба варианта (сравнивать с числом 10 в цикле или прибавлять 10 в конце) одинаковы по размеру. Но вот что я заметил: поскольку потом всё равно нужно прибавить к аргументу ASCII-код символа 0, можно сразу прибавлять и десятку! Этот трюк, пожалуй, стал самым большим откровением для меня. Инструкция ADD #58., R0 делает именно это (48+10).
Я был настолько доволен программой, что решил поделиться ей на форуме zx-pk.ru (ничего не подозревая о местных традициях критиковать без аргументов). Реакция сообщества была примерно такой: «надо было просто посмотреть, как сделали в DEC, это же классика».
Что ж, вот программа от DEC — компании, создавшей PDP-11 и вобравшей в свои ряды некоторых хакеров из MIT:
; RETURNS:
; R0 = 0
; R1 -> byte following last digit in converted number
CVBTOD: MOV R0,-(SP) ;SAVE THE NUMBER PASSED TO US
CLR R0 ;SET FOR CRUDE DIVIDE BY 10.
10$: INC R0 ;BUMP QUOTIENT
SUB #10.,(SP) ;REDUCE NUMBER BY 10.
BHIS 10$ ;IF SIGN DIDN'T CHANGE...
ADD #10.+48.,(SP) ;MAKE REMAINDER PRINTABLE
DEC R0 ;REDUCE QUOTIENT
BEQ 20$ ;IF ZERO, TIME TO PRINT
CALL CVBTOD ;OTHERWISE, RECURSE !
20$: MOVB (SP)+,(R1)+ ;STORE A CONVERTED DIGIT
RETURN ;UNWIND THE RECURSION14 слов, круто! Или… нет? Мне засчитали поражение, но давайте посмотрим внимательней:
- Прибавление ASCII-кода символа 0 и числа 10 сделано одной операцией. Оказывается, такой трюк применяли ещё в 70-ых. Классно.
- Программа вызывает сама себя рекурсивно — красивое решение!
- Вычисления проводятся в стеке — это медленней, зато экономится один регистр. Хорошо это или плохо — зависит от контекста применения процедуры.
- После выхода R1 указывает на конец строки. Это неудобно, так как перед печатью придётся заново указывать адрес строки, а это лишняя команда.
- Ой, подождите! А где исходный адрес строки?… Оказывается, он задаётся за пределами подпрограммы. Таким образом, критики с zx-pk.ru не досчитались команды MOV #NUMBER, R1 из двух слов!
Итого, реальный размер — 16 слов. Ровно как у моей. Обе программы состоят из 12 инструкций. Так какая лучше?
Даже если заменить обращения к стеку на обращения к регистру, программа DEC окажется медленней из-за инструкций DEC R0 и CALL внутри цикла.
Но это ещё не всё. Начав писать эту статью, я заметил, что в моей программе осталась рудиментарная (от MKDOS) инструкция MOV #10., R4 — она не несёт никакого смысла, кроме ускорения внутреннего цикла. Пора избавиться от неё.
MOV #NUMBER,R1 ; pointer to output text string
CLRB -(R1) ; end of text marker
1: MOV #-1.,R5
2: INC R5 ; counter of 10s
SUB #10.,R0
BHIS 2 ; branch if higher or same
ADD #58.,R0 ; #10. + '0' ASCII code
MOVB R0,-(R1) ; store R0 to text string
MOV R5,R0 ; let's count next how many 10s in number of 10s
BNE 1
RET ; returns text string pointer in R115 слов. 11 инструкций. Вот теперь, похоже, всё.
Что ж, у меня идеи по оптимизации закончились. Это был вдохновляющий, даже азартный, челлендж. Замечательно, что идея, предложенная студентом-хакером в начале 60-ых для PDP-1, использовалась компанией DEC десять и даже двадцать лет спустя, а на советском компьютере БК 0011М она применялась до начала 2000-ых годов. Удивительно, что в 2018-ом году оказалось возможным частично переизобрести и оптимизировать алгоритм. Характерно, что многие считали это невозможным.
Итак, перед вами Святой Грааль (по выражению Стивена Леви), найти который пытались хакеры 60-ых — самая короткая программа вывода десятичного числа для PDP. Или… можно ещё короче?
Полезные ссылки:
