1984年,史蒂文·利维(Steven Levy)的邪教书籍《黑客:计算机革命的英雄》(Hackers:Computer Revolutions of Heroes)发行。有俄文的业余翻译,但远非理想。我承诺纠正其中的不正确之处,将英语原件放在旁边(顺便说一句,它并非没有罪过),但在第二章之后放弃了。一种或另一种方式,我想引起您的注意是一个片段(可以在另一篇文章中阅读),该片段专用于在十进制系统中打印数字的子例程。这样的程序可以减少多少?有什么限制?在2018年8月,我编写了一个程序来测量苏联处理器1801BM1的确切执行时间(它具有一组PDP-11指令)。在为BK 0011M计算机制作“ Good Apple ” 演示时,需要知道准确的时间(以处理器周期为单位)。我想以十进制查看测量结果。为此,我必须编写自己的子例程-由于测试的细节,系统功能不可用。我做的第一件事是组成一个功率为10的TEN数组。该过程在寄存器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-branching)开始。我将不描述该算法,它没有意义,在这里仅作为起点。该例程的大小为22个字(不包括数据)。在一切正常之后,我突然想起了斯蒂芬·列维(Stephen Levy)的书中的故事:黑客们努力减少类似程序的大小以及PDP体系结构的大小。没错,他们有PDP-1,但几年后他们有了PDP-11。
打开这本书,我发现了一个非常模糊的描述。麻省理工学院的黑客开始就像我从小数位列表中一样但是接下来发生的事情从文本中还不清楚。显然,这本书的作者也不清楚;他只是从黑客大赛的目击者的口中写下了一些常用的词语。我不得不深入研究PDP-1程序的Internet档案。有很多有趣的东西:Minskytron,Munching广场和其他所谓的“展示骇客”(顺便说一句,值得注意的是,即使在那时-60年代初期,麻省理工学院的黑客也使用了“ 演示 ”一词,其含义与我们现在所使用的一样)在恶魔上)。归档中有许多系统例程,但是不幸的是,其中没有十进制数。然后,我配备了调试器,决定查看如何在BK 0010和BK 0011M上使用的MKDOS操作系统中实现此过程。哦,奇迹! -仔细查看后,我意识到该子程序非常适合《黑客》一书中的模糊描述。这是她的代码: 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
该程序在堆栈上形成一个文本字符串,然后为每个保存的字符调用打印过程。显然,这正是斯蒂芬·利维(Stephen Levy)在书中所说的“以相反的方式转换,并借助狡猾的软件聚焦以正确的顺序打印”。该算法的其他功能应从代码注释中清楚看出。子例程的大小为23个字,但是您不能直接将其与我的子例程进行比较:条件太不同了。我决定将程序从MKDOS修改为我的条件:在内存中形成文本字符串。最后,我意识到最好只留下减去数字10的想法,然后从头开始写其余的想法。经过Sansara优化几圈后,我得到了以下信息: 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个单词,达到了极限(我认为),这就是-涅rv乐队,史蒂芬·利维(Steven Levy)如此感动!这里有什么技巧:- 第一个命令将指针设置为不指向文本行的开头,而是指向文本行的结尾。文本从右到左填充-这也很方便,因为在输出处,我们获得了行首的地址,准备发送到文本打印过程。
- , . (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 RECURSION
14个字,太酷了!或不?我被击败了,但让我们仔细看看:- 一次添加字符0和数字10的ASCII码。事实证明,这种技巧是在70年代使用的。凉。
- 该程序以递归方式调用自己-一个漂亮的解决方案!
- – , . – .
- R1 . , , .
- , ! ?.. , . , zx-pk.ru MOV #NUMBER,R1 !
总计,实际大小为16个字。就像我的一样。这两个程序都包含12条指令。那么哪个更好呢?即使将堆栈调用替换为寄存器调用,由于循环内的DEC R0和CALL指令,DEC程序也会变慢。但这还不是全部。当我开始写这篇文章时,我注意到在我的程序中有一个基本的(来自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中就得到了应用,直到2000年代初,它一直在苏联计算机BK 0011M上得到应用。令人惊讶的是,在2018年,可以部分地重新发明和优化算法。具有特征的是,许多人认为这是不可能的。因此,这就是圣杯(根据Stephen Levy的说法),这是60年代的黑客试图找到的-PDP的最短十进制程序。或者...也许更短?更新资料:我知道这一天将会到来,但是我没有这么快就想:)原来,该程序可以再减少一个字!在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(如果不等于零则分支)命令检查R0,如果不等于零,则转到循环的开始。我们想先将R0减一,然后(如果它们不为零)转到开头...请稍等,但这是一个正常的SOB(减一和分支)循环命令。的确,这里没有以规范的方式使用它:它只完成一次,然后循环计数器磨损了。这看起来很令人沮丧,但是如果您查看该子例程的先前版本,则会很清楚如何从中缩短一个新子例程。有用的链接: