- PVSM.RU - https://www.pvsm.ru -
В 1984-ом году вышла культовая книга Стивена Леви “Хакеры: герои компьютерной революции [1]”. Существует любительский русский перевод, но он далёк от идеала. Я было взялся исправлять неточности в нём, положив рядом английский оригинал (кстати, и он не без греха), да забросил после второй главы. Так или иначе, хочу обратить ваше внимание на фрагмент (можно прочитать его в виде отдельной статьи [2]), посвящённый подпрограмме печати числа в десятичной системе. Насколько можно уменьшить такую программу? Каков предел?
В августе 2018-го года я писал программу для измерения точного времени исполнения команд советского процессора 1801ВМ1 (он обладает набором инструкций PDP-11 [3]). Знание точного времени (в тактах процессора) было необходимо при работе над демо “Good Apple [4]” для компьютера БК 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 [5] так же, как и я — со списка десятичных разрядов. Но что произошло дальше, из текста непонятно. Очевидно, это не было понятно и автору книги, он просто записал общие слова из уст очевидцев того хакерского состязания.
Пришлось покопаться в Интернет-архиве программ для PDP-1 [6]. Там много интересного: Minskytron, Munching squares и другие так называемые “дисплейные хаки” (кстати, примечательно, что уже тогда – в начале 60-ых – хакеры из MIT использовали термин “демо [7]” в том же смысле, в котором мы используем его сейчас на демосцене). В архиве много системных подпрограмм, но вывода десятичного числа среди них, увы, нет.
Тогда, вооружившись отладчиком, я решил посмотреть, как реализована эта процедура в операционной системе 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 R1
16 слов, предел достигнут (думал я), вот она – Нирвана, о которой так эмоционально писал Стивен Леви!
Какие трюки здесь применены:
Я был настолько доволен программой, что решил поделиться ей на форуме zx-pk.ru [8] (ничего не подозревая о местных традициях критиковать без аргументов). Реакция сообщества была примерно такой: “надо было просто посмотреть, как сделали в DEC, это же классика”.
Что ж, вот программа от DEC [9] – компании, создавшей 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 RECURSION
14 слов, круто! Или… нет? Мне засчитали поражение, но давайте посмотрим внимательней:
Итого, реальный размер – 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 R1
15 слов. 11 инструкций. Вот теперь, похоже, всё.
Что ж, у меня идеи по оптимизации закончились. Это был вдохновляющий, даже азартный, челлендж. Замечательно, что идея, предложенная студентом-хакером в начале 60-ых для PDP-1, использовалась компанией DEC десять и даже двадцать лет спустя, а на советском компьютере БК 0011М она применялась до начала 2000-ых годов. Удивительно, что в 2018-ом году оказалось возможным частично переизобрести и оптимизировать алгоритм. Характерно, что многие считали это невозможным.
Итак, перед вами Святой Грааль (по выражению Стивена Леви), найти который пытались хакеры 60-ых — самая короткая программа вывода десятичного числа для PDP. Или… можно ещё короче?
Полезные ссылки:
Автор: Александр Мачуговский
Источник [15]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/staroe-zhelezo/352097
Ссылки в тексте:
[1] Хакеры: герои компьютерной революции: https://en.wikipedia.org/wiki/Hackers:_Heroes_of_the_Computer_Revolution
[2] отдельной статьи: http://demoscene.ru/info/article.php3?03411
[3] набором инструкций PDP-11: https://en.wikipedia.org/wiki/PDP-11_architecture
[4] Good Apple: https://www.pouet.net/prod.php?which=78066
[5] MIT: https://en.wikipedia.org/wiki/MIT_Computer_Science_and_Artificial_Intelligence_Laboratory
[6] программ для PDP-1: http://bitsavers.org/bits/DEC/pdp1/
[7] демо: https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BC%D0%BA%D0%B0
[8] zx-pk.ru: https://zx-pk.ru/threads/11381-napisanie-programm-dlya-bk0010.html?p=1015403&viewfull=1#post1015403
[9] DEC: https://ru.wikipedia.org/wiki/Digital_Equipment_Corporation
[10] Журнал Downgrade: http://dgmag.in
[11] Программирование под БК 0010 в 2019-ом году: https://habr.com/ru/post/469117/
[12] Демки для БК 0010 и БК 0011М: https://www.pouet.net/prodlist.php?platform%5B0%5D=BK-0010/11M&order=views
[13] Хакерские корни демосцены: https://youtu.be/ozfYW1EKuuI
[14] Hackers: Wizards of the Electronic Age: https://youtu.be/zOP1LNr70aU
[15] Источник: https://habr.com/ru/post/496914/?utm_source=habrahabr&utm_medium=rss&utm_campaign=496914
Нажмите здесь для печати.