13.04.2020 06:39
Manwe_SandS 29 13100 Источник
В 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.

image

Открыв книгу, я обнаружил крайне туманное описание. Начинали хакеры из 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 R1

16 слов, предел достигнут (думал я), вот она – Нирвана, о которой так эмоционально писал Стивен Леви!

Какие трюки здесь применены:

  1. Первая команда устанавливает указатель не в начало, а в конец текстовой строки. Текст заполняется справа налево – это удобно ещё и тем, что на выходе мы получаем адрес начала строки, готовый к передаче в процедуру печати текста.
  2. Счётчик вычитаний начинается не с нуля, а с минус единицы. Первая команда внутри цикла (INC R5) увеличивает счётчик на 1. Всё равно получается 0, так почему бы сразу не очищать счётчик, зачем всё это?.. Дело в том, что при первом же вычитании 10 можно получить отрицательный результат – тогда нужно выйти из цикла, при этом счётчик должен равняться нулю. Значит, увеличение счётчика придётся делать уже после проверки. А следом нужна команда перехода в начало цикла. Итого – на одну команду больше. С точки зрения размера разницы нет: мы потеряем 1 слово, добавив команду перехода, но сэкономим 1 слово на записи минус единицы (очистка регистра короче). И всё же, имеет смысл уменьшить количество команд внутри цикла, так он будет исполняться быстрей. Да и программа в целом визуально сократится. Поэтому я пришёл к решению с -1.
  3. Вычитая число 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 RECURSION

14 слов, круто! Или… нет? Мне засчитали поражение, но давайте посмотрим внимательней:

  1. Прибавление ASCII-кода символа 0 и числа 10 сделано одной операцией. Оказывается, такой трюк применяли ещё в 70-ых. Классно.
  2. Программа вызывает сама себя рекурсивно – красивое решение!
  3. Вычисления проводятся в стеке – это медленней, зато экономится один регистр. Хорошо это или плохо – зависит от контекста применения процедуры.
  4. После выхода R1 указывает на конец строки. Это неудобно, так как перед печатью придётся заново указывать адрес строки, а это лишняя команда.
  5. Ой, подождите! А где исходный адрес строки?.. Оказывается, он задаётся за пределами подпрограммы. Таким образом, критики с 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 		; loop if R0 is not zero
	RET		; returns text string pointer in R1

15 слов. 11 инструкций. Вот теперь, похоже, всё.

Что ж, у меня идеи по оптимизации закончились. Это был вдохновляющий, даже азартный, челлендж. Замечательно, что идея, предложенная студентом-хакером в начале 60-ых для PDP-1, использовалась компанией DEC десять и даже двадцать лет спустя, а на советском компьютере БК 0011М она применялась до начала 2000-ых годов. Удивительно, что в 2018-ом году оказалось возможным частично переизобрести и оптимизировать алгоритм. Характерно, что многие считали это невозможным.

Итак, перед вами Святой Грааль (по выражению Стивена Леви), найти который пытались хакеры 60-ых — самая короткая программа вывода десятичного числа для PDP. Или… можно ещё короче?

Update: я знал, что этот день наступит, но не думал, что так скоро :) Оказалось, программу можно сократить ещё на одно слово! Идею предложил в комментариях Mr_Rm:

	MOV #NUMBER,R1	; pointer to output text string
	CLRB -(R1)	; end of text marker
1:	CLR R5
2:	INC R5		; counter of 10s +1
	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 how many 10s in number of 10s
	SOB R0,1	; subtract 1 and loop if not zero
	RET		; returns text string pointer in R1

14 слов. 11 инструкций.
Фокус вот в чём. Помните, я писал, что при “неправильной” организации цикла R5 получается на единицу больше нужного? Ну и пусть! Мы уменьшим его в самом конце программы. В прошлом варианте R5 копировался в R0, после чего команда BNE (Branch if Not Equal to zero) проверяла R0, и если он не равен нулю, переходила в начало цикла. Вот бы нам сперва уменьшить R0 на единицу, а потом уже (если получили не ноль) переходить в начало… Минуточку, да ведь это обычная команда цикла SOB (Subtract One and Branch). Правда, здесь она использована не каноническим образом: отрабатывает один раз, а дальше счётчик цикла перетирается. Это выглядит обескураживающе, но если разобраться в предыдущей версии подпрограммы, становится понятно как из неё получилась новая, укороченная на одно слово.

Полезные ссылки: