1984 erschien Steven Levys Kultbuch Hackers: Heroes of the Computer Revolution . Es gibt eine russische Amateurübersetzung, die jedoch alles andere als ideal ist. Ich habe mich verpflichtet, Ungenauigkeiten darin zu korrigieren, indem ich das englische Original daneben gestellt habe (übrigens, und es ist nicht ohne Sünde), habe es aber nach dem zweiten Kapitel aufgegeben. Auf die eine oder andere Weise möchte ich Ihre Aufmerksamkeit auf ein Fragment lenken (Sie können es in einem separaten Artikel lesen ), das der Unterroutine zum Drucken einer Zahl in einem Dezimalsystem gewidmet ist. Wie viel kann ein solches Programm reduziert werden? Was ist die Grenze?Im August 2018 schrieb ich ein Programm zur Messung der genauen Ausführungszeit von Anweisungen des sowjetischen Prozessors 1801BM1 (es enthält einen Satz von PDP-11-Anweisungen ). Bei der Arbeit an der Demo „ Good Apple “ für den Computer BK 0011M war es erforderlich, die genaue Zeit (in Prozessorzyklen) zu kennen. Ich wollte die Messergebnisse dezimal sehen. Dazu musste ich meine eigene Routine schreiben - Systemfunktionen waren aufgrund der Besonderheiten des Tests nicht verfügbar.Als erstes habe ich ein TEN-Array mit Potenzen von 10 erstellt. Die Prozedur nimmt eine Zahl in Register R0, die Ausgabe ist eine Textzeichenfolge bei NUMBER. Wichtig: Es gibt keine Teilungsanweisung im Prozessor ! 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
Um den PDP-11-Assembler zu verstehen, genügt es, sich daran zu erinnern, dass die Argumente von links nach rechts geschrieben werden (zuerst die Quelle, dann der Empfänger) und bedingte Verzweigungsbefehle mit dem Buchstaben B (vom Wort Verzweigung - Verzweigung) beginnen. Ich werde den Algorithmus nicht beschreiben, er ist nicht von Interesse und wird hier nur als Ausgangspunkt angegeben. Die Größe dieser Routine beträgt 22 Wörter (ohne Daten).Nachdem alles funktioniert hatte, erinnerte ich mich plötzlich an eine Geschichte aus Stephen Levys Buch: Hacker hatten Mühe, die Größe eines ähnlichen Programms und auch die PDP-Architektur zu reduzieren. Sie hatten zwar PDP-1, aber einige Jahre später bekamen sie PDP-11.
Als ich das Buch öffnete, fand ich eine äußerst vage Beschreibung. Hacker vom MIT haben angefangengenau wie ich aus der Liste der Dezimalstellen. Aber was als nächstes geschah, geht aus dem Text nicht hervor. Offensichtlich war dies auch dem Autor des Buches nicht klar, er schrieb einfach allgemeine Worte von den Lippen der Augenzeugen dieses Hacking-Wettbewerbs auf.Ich musste mich mit dem Internetarchiv der Programme für PDP-1 befassen . Es gibt viele interessante Dinge: Minskytron, Munching Squares und andere sogenannte "Display Hacks" (übrigens ist es bemerkenswert, dass MIT-Hacker schon damals - in den frühen 60er Jahren - den Begriff " Demo " in dem Sinne verwendeten, in dem wir ihn jetzt verwenden auf der Demoszene). Es gibt viele Systemroutinen im Archiv, aber leider gibt es keine Dezimalzahl unter ihnen.Dann entschied ich mich mit einem Debugger bewaffnet zu sehen, wie dieses Verfahren im MKDOS-Betriebssystem implementiert wurde, das ich auf dem BK 0010 und dem BK 0011M verwende. Oh Wunder! - Bei genauem Hinsehen stellte ich fest, dass das Unterprogramm sehr gut zur nebligen Beschreibung aus dem Buch „Hacker“ passt. Hier ist ihr Code: 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
Das Programm bildet eine Textzeichenfolge auf dem Stapel und ruft dann die Druckprozedur für jedes gespeicherte Zeichen auf. Anscheinend ist dies genau das, was Stephen Levy in dem Buch unter dem Satz "Konvertiert in umgekehrter Weise und mit Hilfe eines gerissenen Software-Fokus druckt es in der richtigen Reihenfolge" gemeint hat. Andere Merkmale des Algorithmus sollten aus den Kommentaren zum Code ersichtlich sein.Die Größe des Unterprogramms beträgt 23 Wörter , aber Sie können es nicht direkt mit meinem Unterprogramm vergleichen: Die Bedingungen sind zu unterschiedlich. Ich beschloss, das Programm von MKDOS an meine Bedingungen anzupassen: die Bildung einer Textzeichenfolge im Speicher.Am Ende wurde mir klar, dass es besser ist, nur die Idee zu lassen, die Zahl 10 zu subtrahieren und den Rest von Grund auf neu zu schreiben. Nach mehreren Runden der Sansara- Optimierung erhielt ich Folgendes: 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 Wörter , die Grenze ist erreicht (dachte ich), hier ist es - Nirvana, über das Stephen Levy so emotional geschrieben hat!Welche Tricks werden hier angewendet:- Der erste Befehl setzt den Zeiger nicht auf den Anfang, sondern auf das Ende der Textzeile. Der Text wird von rechts nach links gefüllt - dies ist auch praktisch, da wir bei der Ausgabe die Adresse des Zeilenanfangs erhalten, die zum Senden an den Textdruck bereit ist.
- , . (INC R5) 1. 0, , ?.. , 10 – , . , . . – . : 1 , , 1 ( ). , , . . -1.
- 10, , , . – ( ). , – . , , . ( 10 10 ) . : ASCII- 0, ! , , . ADD #58.,R0 (48+10).
Ich war so zufrieden mit dem Programm, dass ich mich entschied, es im zx-pk.ru- Forum zu teilen (ohne zu vermuten, dass lokale Traditionen ohne Argumente kritisiert werden könnten). Die Reaktion der Community war ungefähr so: "Man musste nur sehen, wie sie es bei DEC gemacht haben, es ist ein Klassiker."Nun, hier ist ein Programm von DEC , dem Unternehmen, das PDP-11 entwickelt und einige der Hacker vom MIT in seine Reihen aufgenommen hat:; 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 Wörter , cool! Oder nicht? Ich wurde besiegt, aber schauen wir uns das genauer an:- Das Hinzufügen des ASCII-Codes von Zeichen 0 und Nummer 10 erfolgt in einem Arbeitsgang. Es stellt sich heraus, dass ein solcher Trick bereits in den 70er Jahren angewendet wurde. Cool.
- Das Programm nennt sich rekursiv - eine schöne Lösung!
- – , . – .
- R1 . , , .
- , ! ?.. , . , zx-pk.ru MOV #NUMBER,R1 !
Insgesamt beträgt die tatsächliche Größe 16 Wörter . Genau wie meine. Beide Programme bestehen aus 12 Anweisungen. Also was ist besser?Selbst wenn Sie Stapelaufrufe durch Registeraufrufe ersetzen, ist das DEC-Programm aufgrund der Anweisungen DEC R0 und CALL in der Schleife langsamer.Aber das ist nicht alles. Als ich anfing, diesen Artikel zu schreiben, bemerkte ich, dass in meinem Programm eine rudimentäre (von MKDOS) Anweisung MOV # 10., R4 blieb - es macht keinen anderen Sinn als die Beschleunigung der inneren Schleife. Es ist Zeit, sie loszuwerden. 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 Wörter . 11 Anweisungen. Nun, es scheint, das ist alles.Nun, meine Optimierungsideen sind vorbei. Es war eine inspirierende, sogar spielerische Herausforderung. Es ist bemerkenswert, dass die Idee, die ein studentischer Hacker in den frühen 60er Jahren für PDP-1 vorschlug, zehn und sogar zwanzig Jahre später von DEC verwendet wurde und bis Anfang der 2000er Jahre auf dem sowjetischen Computer BK 0011M angewendet wurde. Überraschenderweise war es im Jahr 2018 möglich, den Algorithmus teilweise neu zu erfinden und zu optimieren. Bezeichnenderweise hielten viele dies für unmöglich.Hier ist also der Heilige Gral (laut Stephen Levy), den die Hacker der 60er Jahre zu finden versuchten - das kürzeste Dezimalprogramm für PDP. Oder ... vielleicht noch kürzer?Aktualisieren: Ich wusste, dass dieser Tag kommen würde, aber ich dachte nicht so schnell :) Es stellte sich heraus, dass das Programm um ein weiteres Wort reduziert werden kann! Die Idee wurde in den Kommentaren von Mr_Rm vorgeschlagen : 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 Wörter . 11 Anweisungen.Der Trick ist dies. Denken Sie daran, ich habe geschrieben, dass mit der „falschen“ Organisation des R5-Zyklus mehr erreicht wird als nötig? Nun, lass! Wir werden es ganz am Ende des Programms reduzieren. In der vorherigen Version wurde R5 nach R0 kopiert, wonach der Befehl BNE (Verzweigen, wenn nicht gleich Null) R0 prüfte, und wenn er nicht gleich Null ist, ging er zum Beginn des Zyklus. Wir möchten zuerst R0 um eins reduzieren und dann (wenn sie nicht null sind) zum Anfang gehen ... Warten Sie eine Minute, aber dies ist ein normaler SOB-Zyklusbefehl (Subtrahieren von Eins und Verzweigen). Es stimmt, hier wurde es nicht kanonisch verwendet: Es erfüllt sich einmal, und dann ist der Zykluszähler ausgefranst. Das sieht entmutigend aus, aber wenn Sie sich die vorherige Version des Unterprogramms ansehen, wird klar, wie ein neues daraus verkürzt wird.Nützliche Links: