Em 1984, o livro de culto de Steven Levy, Hackers: Heróis da Revolução do Computador , foi lançado. Há uma tradução amadora para o russo, mas está longe de ser o ideal. Eu me comprometi a corrigir imprecisões, colocando o original em inglês ao lado (a propósito, e não é sem pecado), mas o abandonei após o segundo capítulo. De uma forma ou de outra, quero chamar sua atenção para um fragmento (você pode ler em um artigo separado ) dedicado à sub-rotina para imprimir um número em um sistema decimal. Quanto esse programa pode ser reduzido? Qual é o limite?Em agosto de 2018, escrevi um programa para medir o tempo exato de execução das instruções do processador soviético 1801BM1 (ele possui um conjunto de instruções PDP-11 ). Era necessário saber o tempo exato (em ciclos do processador) ao trabalhar na demonstração " Good Apple " para o computador BK 0011M. Eu queria ver os resultados da medição em decimal. Para fazer isso, tive que escrever minha própria sub-rotina - as funções do sistema não estavam disponíveis devido às especificidades do teste.A primeira coisa que fiz foi criar uma matriz TEN com potências de 10. O procedimento pega um número no registrador R0, a saída é uma sequência de texto em NUMBER. Importante: não há instruções de divisão no processador ! 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
Para entender o montador do PDP-11, basta lembrar que os argumentos são escritos da esquerda para a direita (primeiro a fonte, depois o receptor), e os comandos condicionais de ramificação começam com a letra B (da palavra ramificação - ramificação). Não descreverei o algoritmo, ele não tem interesse e é apresentado aqui apenas como ponto de partida. O tamanho dessa rotina é 22 palavras (não incluindo dados).Depois que tudo funcionou, de repente me lembrei de uma história do livro de Stephen Levy: hackers lutavam para reduzir o tamanho de um programa semelhante e também na arquitetura do PDP. É verdade que eles tinham PDP-1, mas alguns anos depois receberam o PDP-11.
Abrindo o livro, encontrei uma descrição extremamente vaga. Os hackers do MIT começaramassim como eu na lista de casas decimais. Mas o que aconteceu a seguir não está claro no texto. Obviamente, isso também não ficou claro para o autor do livro; ele simplesmente escreveu palavras comuns dos lábios das testemunhas oculares daquele concurso de hackers.Eu tive que me aprofundar no arquivo de programas da Internet para PDP-1 . Há muitas coisas interessantes: Minskytron, Munching squares e outros chamados "hacks de exibição" (a propósito, é digno de nota que já - no início dos anos 60 - os hackers do MIT usavam o termo " demo " no mesmo sentido em que o usamos agora no demosceno). Existem muitas rotinas de sistema no arquivo morto, mas, infelizmente, não há número decimal entre elas.Então, armado com um depurador, decidi ver como esse procedimento era implementado no sistema operacional MKDOS, que eu uso nos BK 0010 e BK 0011M. Oh milagre! - Observando atentamente, percebi que o subprograma se encaixa muito bem com a descrição nebulosa do livro "Hackers". Aqui está o código dela: 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
O programa forma uma sequência de texto na pilha e chama o procedimento de impressão para cada caractere salvo. Aparentemente, é exatamente isso o que o livro de Stephen Levy quis dizer com a frase "converte-se da maneira oposta e, com a ajuda de um foco de software astuto, imprime na ordem correta". Outros recursos do algoritmo devem ficar claros nos comentários sobre o código.O tamanho da sub-rotina é de 23 palavras , mas você não pode compará-lo diretamente com a minha sub-rotina: as condições são muito diferentes. Decidi refazer o programa do MKDOS para minhas condições: a formação de uma string de texto na memória.No final, percebi que é melhor deixar apenas a ideia de subtrair o número 10 e escrever o resto do zero. Após várias voltas da otimização do Sansara , obtive o seguinte: 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 palavras , o limite é atingido (pensei), aqui está - Nirvana, sobre o qual Stephen Levy escreveu tão emocionalmente!Quais truques são aplicados aqui:- O primeiro comando define o ponteiro não para o início, mas para o final da linha de texto. O texto é preenchido da direita para a esquerda - isso também é conveniente porque, na saída, obtemos o endereço do início da linha, pronto para ser enviado ao procedimento de impressão de texto.
- , . (INC R5) 1. 0, , ?.. , 10 – , . , . . – . : 1 , , 1 ( ). , , . . -1.
- 10, , , . – ( ). , – . , , . ( 10 10 ) . : ASCII- 0, ! , , . ADD #58.,R0 (48+10).
Fiquei tão satisfeito com o programa que decidi compartilhá-lo no fórum zx-pk.ru (sem suspeitar que qualquer tradição local criticasse sem argumentos). A reação da comunidade foi mais ou menos assim: "você só precisava ver como eles fizeram isso no DEC, é um clássico".Bem, aqui está um programa da DEC , a empresa que criou o PDP-11 e incorporou alguns dos hackers do MIT em suas fileiras:; 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 palavras , legal! Ou não? Fui derrotado, mas vamos dar uma olhada:- A adição do código ASCII do caractere 0 e número 10 é feita em uma operação. Acontece que esse truque foi usado nos anos 70. Legal.
- O programa se autodenomina recursivamente - uma solução bonita!
- – , . – .
- R1 . , , .
- , ! ?.. , . , zx-pk.ru MOV #NUMBER,R1 !
Total, o tamanho real é 16 palavras . Exatamente como o meu. Ambos os programas consistem em 12 instruções. Então, qual é o melhor?Mesmo se você substituir chamadas em pilha por chamadas de registro, o programa DEC será mais lento devido às instruções DEC R0 e CALL dentro do loop.Mas isso não é tudo. Quando comecei a escrever este artigo, notei que, no meu programa, havia uma instrução rudimentar (do MKDOS) MOV # 10., R4 - não faz outro sentido senão acelerar o loop interno. É hora de se livrar dela. 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 palavras . 11 instruções. Agora, ao que parece, é tudo.Bem, minhas idéias de otimização acabaram. Foi um desafio inspirador e até arriscado. É notável que a idéia proposta por um estudante hacker no início dos anos 60 para o PDP-1 tenha sido usada pelo DEC dez e até vinte anos depois, e foi aplicada no computador soviético BK 0011M até o início dos anos 2000. Surpreendentemente, no ano de 2018, foi possível reinventar e otimizar parcialmente o algoritmo. Caracteristicamente, muitos consideraram isso impossível.Então, aqui está o Santo Graal (de acordo com Stephen Levy), que os hackers dos anos 60 tentaram encontrar - o menor programa decimal para PDP. Ou ... talvez até mais curto?Atualizar: Eu sabia que esse dia chegaria, mas não pensei tão cedo :) Aconteceu que o programa pode ser reduzido em mais uma palavra! A ideia foi sugerida nos comentários 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 palavras . 11 instruções.O truque é esse. Lembre-se, eu escrevi que, com a organização “errada” do ciclo R5, mais um é obtido do que o necessário? Bem, deixe! Vamos reduzi-lo no final do programa. Na versão anterior, R5 foi copiado para R0, após o qual o comando BNE (Ramificação se não for igual a zero) verificou R0 e, se não for igual a zero, foi para o início do ciclo. Primeiro, gostaríamos de reduzir R0 em um e depois (se eles não chegassem a zero) ir para o início ... Espere um minuto, mas este é um comando normal de ciclo SOB (Subtrair um e Filial). É verdade que aqui não foi usado de maneira canônica: ele é preenchido uma vez e, em seguida, o contador de ciclos é desgastado. Isso parece desanimador, mas se você olhar para a versão anterior da sub-rotina, fica claro como uma nova é reduzida.Links Úteis: