En 1984, le livre culte de Steven Levy, Hackers: Heroes of the Computer Revolution , est sorti. Il existe une traduction russe amateur, mais elle est loin d'être idéale. Je me suis engagé à y corriger des inexactitudes, en mettant l'original anglais à côté (au fait, et ce n'est pas sans péché), mais je l'ai abandonné après le deuxième chapitre. D'une manière ou d'une autre, je veux attirer votre attention sur un fragment (vous pouvez le lire dans un article séparé ) dédié au sous-programme pour imprimer un nombre dans un système décimal. Combien un tel programme peut-il être réduit? Quelle est la limite?En août 2018, j'ai écrit un programme pour mesurer le temps d'exécution exact des instructions du processeur soviétique 1801BM1 (il a un ensemble d'instructions PDP-11 ). Il était nécessaire de connaître l'heure exacte (en cycles de processeur) lorsque vous travailliez sur la démo « Good Apple » pour l'ordinateur BK 0011M. Je voulais voir les résultats de mesure en décimal. Pour ce faire, j'ai dû écrire mon propre sous-programme - les fonctions système n'étaient pas disponibles en raison des spécificités du test.La première chose que j'ai faite a été de créer un tableau TEN avec des puissances de 10. La procédure prend un nombre dans le registre R0, la sortie est une chaîne de texte à NUMBER. Important: il n'y a aucune instruction de division dans le processeur ! 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
Pour comprendre l'assembleur PDP-11, il suffit de se rappeler que les arguments sont écrits de gauche à droite (d'abord la source, puis le récepteur), et les commandes de branchement conditionnel commencent par la lettre B (du mot branch - branching). Je ne décrirai pas l'algorithme, il ne présente aucun intérêt et n'est donné ici qu'à titre de point de départ. La taille de cette routine est de 22 mots (sans les données).Après que tout a fonctionné, je me suis soudain souvenu d'une histoire du livre de Stephen Levy: les pirates ont eu du mal à réduire la taille d'un programme similaire, ainsi que sur l'architecture PDP. Certes, ils avaient PDP-1, mais quelques années plus tard, ils ont obtenu PDP-11.
En ouvrant le livre, j'ai trouvé une description extrêmement vague. Les pirates informatiques du MIT ont commencétout comme moi dans la liste des décimales. Mais ce qui s'est passé ensuite n'est pas clair dans le texte. De toute évidence, cela n'était pas clair non plus pour l'auteur du livre; il a simplement écrit des mots courants de la bouche des témoins oculaires de ce concours de piratage.J'ai dû me plonger dans l'archive Internet des programmes pour PDP-1 . Il y a beaucoup de choses intéressantes: Minskytron, Munching squares et autres soi-disant "display hacks" (à propos, il est à noter que déjà - au début des années 60 - les pirates du MIT utilisaient le terme " démo " dans le même sens dans lequel nous l'utilisons maintenant sur la demoscene). Il existe de nombreuses routines système dans l'archive, mais, malheureusement, il n'y a pas de nombre décimal parmi elles.Puis, armé d'un débogueur, j'ai décidé de voir comment cette procédure était implémentée dans le système d'exploitation MKDOS, que j'utilise sur les BK 0010 et BK 0011M. Oh miracle! - Après avoir regardé de près, j'ai réalisé que le sous-programme correspond très bien à la description brumeuse du livre "Hackers". Voici son 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
Le programme forme une chaîne de texte sur la pile, puis appelle la procédure d'impression pour chaque caractère enregistré. Apparemment, c'est exactement ce que l'on entendait dans le livre de Stephen Levy sous la phrase "convertit dans le sens opposé, et avec l'aide d'un focus logiciel astucieux, il imprime dans le bon ordre." Les autres caractéristiques de l'algorithme doivent être claires à partir des commentaires sur le code.La taille du sous-programme est de 23 mots , mais vous ne pouvez pas le comparer directement avec mon sous-programme: les conditions sont trop différentes. J'ai décidé de refaire le programme de MKDOS à mes conditions: la formation d'une chaîne de texte en mémoire.Au final, j’ai réalisé qu’il valait mieux ne laisser que l’idée de soustraire le nombre 10 et écrire le reste à partir de zéro. Après plusieurs tours d' optimisation Sansara , j'ai obtenu ce qui suit: 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 mots , la limite est atteinte (pensais-je), le voici - Nirvana, à propos duquel Stephen Levy a écrit avec émotion!Quelles astuces sont appliquées ici:- La première commande définit le pointeur non pas au début, mais à la fin de la ligne de texte. Le texte est rempli de droite à gauche - cela est également pratique car à la sortie, nous obtenons l'adresse du début de la ligne, prête à être envoyée à la procédure d'impression de texte.
- , . (INC R5) 1. 0, , ?.. , 10 – , . , . . – . : 1 , , 1 ( ). , , . . -1.
- 10, , , . – ( ). , – . , , . ( 10 10 ) . : ASCII- 0, ! , , . ADD #58.,R0 (48+10).
J'étais tellement content du programme que j'ai décidé de le partager sur le forum zx-pk.ru (ne soupçonnant rien de traditions locales à critiquer sans argument). La réaction de la communauté a été quelque chose comme ceci: "il fallait juste voir comment ils l'ont fait au DEC, c'est un classique."Eh bien, voici un programme de DEC , la société qui a créé PDP-11 et incorporé certains des pirates du MIT dans ses rangs:; 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 mots , cool! Ou pas? J'ai été vaincu, mais regardons de plus près:- L'ajout du code ASCII du caractère 0 et du numéro 10 se fait en une seule opération. Il s'avère qu'un tel truc a été utilisé dans les années 70. Cool.
- Le programme s'appelle récursivement - une belle solution!
- – , . – .
- R1 . , , .
- , ! ?.. , . , zx-pk.ru MOV #NUMBER,R1 !
Au total, la taille réelle est de 16 mots . Exactement comme le mien. Les deux programmes se composent de 12 instructions. Alors quoi de mieux?Même si vous remplacez les appels de pile par des appels de registre, le programme DEC sera plus lent en raison des instructions DEC R0 et CALL à l'intérieur de la boucle.Mais ce n'est pas tout. Quand j'ai commencé à écrire cet article, j'ai remarqué que dans mon programme il restait une instruction rudimentaire (de MKDOS) MOV # 10., R4 - cela n'a aucun sens autre que d'accélérer la boucle intérieure. Il est temps de se débarrasser d'elle. 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 mots . 11 instructions. Maintenant, il semble que c'est tout.Eh bien, mes idées d'optimisation sont terminées. C'était un défi inspirant, voire un pari. Il est remarquable que l'idée proposée par un étudiant pirate informatique au début des années 60 pour PDP-1 ait été utilisée par DEC dix et même vingt ans plus tard, et elle a été appliquée sur l'ordinateur soviétique BK 0011M jusqu'au début des années 2000. Étonnamment, en 2018, il a été possible de réinventer et d'optimiser partiellement l'algorithme. De manière caractéristique, beaucoup considéraient cela comme impossible.Donc, voici le Saint Graal (selon Stephen Levy), que les pirates des années 60 ont essayé de trouver - le programme décimal le plus court pour PDP. Ou ... peut-être encore plus court?Mise à jour: Je savais que ce jour viendrait, mais je n'y ai pas pensé si tôt :) Il s'est avéré que le programme peut être réduit d'un mot de plus! L'idée a été suggérée dans les commentaires de 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 mots . 11 instructions.L'astuce est la suivante. Rappelez-vous, j'ai écrit qu'avec la «mauvaise» organisation du cycle R5, un de plus est obtenu que nécessaire? Eh bien laissez! Nous allons le réduire à la toute fin du programme. Dans la version précédente, R5 était copié dans R0, après quoi la commande BNE (Branch if Not Equal to zero) vérifiait R0, et si elle n'est pas égale à zéro, elle passait au début du cycle. Si seulement nous réduisions d'abord R0 de un, puis (si nous n'obtenions pas zéro) revenons au début ... Attendez une minute, mais il s'agit d'une commande de cycle SOB (soustraire un et branche) normale. Certes, ici, il n'a pas été utilisé de manière canonique: il remplit une fois, puis le compteur de cycles est effiloché. Cela semble décourageant, mais si vous regardez la version précédente du sous-programme, il devient clair comment une nouvelle est raccourcie.Liens utiles: