Geekly articles weekly

Montador sujo hacks 6502

Este artigo lista alguns dos truques que os participantes do meu pequeno concurso de programação Commodore 64 usaram. As regras do concurso eram simples: crie um arquivo executável C64 (PRG), que desenha duas linhas para formar a imagem abaixo. Aquele cujo arquivo é menor em tamanho venceu.


As entradas da competição foram publicadas em tweets abertos e em mensagens privadas que continham apenas bytes do arquivo PRG e um hash MD5.

Lista de participantes com links para o código fonte:


(Se eu perdi alguém, entre em contato, atualizarei a lista).

O restante do artigo é dedicado a alguns truques de montador que foram usados ​​na competição.

O básico


Os gráficos C64 funcionam por padrão no modo de codificação de 40x25 caracteres. O framebuffer na RAM é dividido em duas matrizes:

  • $0400 (RAM da tela, 40x25 bytes)
  • $d800 (RAM colorida, 40x25 bytes)

Para definir um caractere, salve o byte na RAM da tela, em $0400 (por exemplo, $0400+y*40+x ). A RAM colorida é inicializada em azul claro por padrão (cor 14): essa é a cor que usamos para as linhas, ou seja, a RAM colorida pode ser deixada sem toque.

Você controla as cores da borda e do fundo usando os registros de E / S de memória em $d020 (borda) e $d021 (fundo).

Desenhar duas linhas é muito fácil se você programar diretamente a inclinação de uma linha fixa. Aqui está uma implementação C que desenha linhas e libera o conteúdo da tela para que stdout ( malloc() seja usado para fazer o código funcionar em um PC):

 #include <stdint.h> #include <stdio.h> #include <stdlib.h> void dump(const uint8_t* screen) { const uint8_t* s = screen; for (int y = 0; y < 25; y++) { for (int x = 0; x < 40; x++, s++) { printf("%c", *s == 0xa0 ? '#' : '.'); } printf("\n"); } } void setreg(uintptr_t dst, uint8_t v) { // *((uint8_t *)dst) = v; } int main() { // uint8_t* screenRAM = (uint_8*)0x0400; uint8_t* screenRAM = (uint8_t *)calloc(40*25, 0x20); setreg(0xd020, 0); // Set border color setreg(0xd021, 0); // Set background color int yslope = (25<<8)/40; int yf = yslope/2; for (int x = 0; x < 40; x++) { int yi = yf >> 8; // First line screenRAM[x + yi*40] = 0xa0; // Second line (X-mirrored) screenRAM[(39-x) + yi*40] = 0xa0; yf += yslope; } dump(screenRAM); }

Os códigos de tela acima são $20 (em branco) e $a0 (bloco 8 × 8 preenchido). Se você executar, você verá uma imagem ASCII com duas linhas:

  ## .................................... ##
 .. # .................................. # ..
 ... ## .............................. ## ...
 ..... # ............................ # .....
 ...... ## ........................ ## ......
 ........ ## .................... ## ........
 .......... # .................. # ..........
 ........... ## .............. ## ...........
 ............. # ............ # .............
 .............. ## ........ ## ..............
 ................ ## .... ## ................
 .................. # .. # ..................
 ................... ## ...................
 .................. # .. # ..................
 ................ ## .... ## ................
 .............. ## ........ ## ..............
 ............. # ............ # .............
 ........... ## .............. ## ...........
 .......... # .................. # ..........
 ........ ## .................... ## ........
 ...... ## ........................ ## ......
 ..... # ............................ # .....
 ... ## .............................. ## ...
 .. # .................................. # ..
 ## .................................... ##

O mesmo é trivialmente implementado no assembler:

 !include "c64.asm" +c64::basic_start(entry) entry: { lda #0 ; black color sta $d020 ; set border to 0 sta $d021 ; set background to 0 ; clear the screen ldx #0 lda #$20 clrscr: !for i in [0, $100, $200, $300] { sta $0400 + i, x } inx bne clrscr ; line drawing, completely unrolled ; with assembly pseudos lda #$a0 !for i in range(40) { !let y0 = Math.floor(25/40*(i+0.5)) sta $0400 + y0*40 + i sta $0400 + (24-y0)*40 + i } inf: jmp inf ; halt }

Acontece que o PRG possui um tamanho bastante grande de 286 bytes.

Antes de mergulhar na otimização, fazemos algumas observações.

Primeiramente, trabalhamos em C64 com as rotinas de ROM em vigor. Existem inúmeras rotinas que podem ser úteis. Por exemplo, limpando a tela com JSR $E544 .

Em segundo lugar, os cálculos de endereço em um processador de 8 bits como o 6502 podem ser complicados e consumir muitos bytes. Esse processador também não possui um multiplicador; portanto, um cálculo como y*40+i geralmente inclui várias mudanças lógicas ou uma tabela de pesquisa que também consome bytes. Para evitar multiplicar por 40, é melhor avançar o cursor da tela de forma incremental:

  int yslope = (25<<8)/40; int yf = yslope/2; uint8_t* dst = screenRAM; for (int x = 0; x < 40; x++) { dst[x] = 0xa0; dst[(39-x)] = 0xa0; yf += yslope; if (yf & 256) { // Carry set? dst += 40; yf &= 255; } }

Continuamos adicionando a inclinação da linha ao contador fixo yf e, quando a adição de 8 bits define o sinalizador de transporte, adicione 40.

Aqui está uma abordagem incremental do montador:

 !include "c64.asm" +c64::basic_start(entry) !let screenptr = $20 !let x0 = $40 !let x1 = $41 !let yf = $60 entry: { lda #0 sta x0 sta $d020 sta $d021 ; kernal clear screen jsr $e544 ; set screenptr = $0400 lda #<$0400 sta screenptr+0 lda #>$0400 sta screenptr+1 lda #80 sta yf lda #39 sta x1 xloop: lda #$a0 ldy x0 ; screenRAM[x] = 0xA0 sta (screenptr), y ldy x1 ; screenRAM[39-x] = 0xA0 sta (screenptr), y clc lda #160 ; line slope adc yf sta yf bcc no_add ; advance screen ptr by 40 clc lda screenptr adc #40 sta screenptr lda screenptr+1 adc #0 sta screenptr+1 no_add: inc x0 dec x1 bpl xloop inf: jmp inf }

Com 82 bytes, ainda é bastante robusto. Um problema óbvio são os cálculos de endereços de 16 bits. Defina o valor screenptr para screenptr indireta:

  ; set screenptr = $0400 lda #<$0400 sta screenptr+0 lda #>$0400 sta screenptr+1

screenptr para a próxima linha adicionando 40:

  ; advance screen ptr by 40 clc lda screenptr adc #40 sta screenptr lda screenptr+1 adc #0 sta screenptr+1

Obviamente, esse código pode ser otimizado, mas e se você se livrar dos endereços de 16 bits? Vamos ver como fazer isso.

Truque 1. Rolagem!


Em vez de construir uma linha na RAM da tela, desenhamos apenas na última linha Y = 24 e JSR $E8EA a tela inteira, chamando a função de rolagem ROM com JSR $E8EA !

Veja como o xloop é otimizado:

  lda #0 sta x0 lda #39 sta x1 xloop: lda #$a0 ldx x0 ; hardcoded absolute address to last screen line sta $0400 + 24*40, x ldx x1 sta $0400 + 24*40, x adc yf sta yf bcc no_scroll ; scroll screen up! jsr $e8ea no_scroll: inc x0 dec x1 bpl xloop

É assim que a renderização se parece:



Este é um dos meus truques favoritos neste programa. Quase todos os competidores encontraram por conta própria.

Truque 2. Código de Auto-Modificação


O código para armazenar valores de pixels termina assim:

  ldx x1 ; hardcoded absolute address to last screen line sta $0400 + 24*40, x ldx x0 sta $0400 + 24*40, x inc x0 dec x1

Isso é codificado na seguinte sequência de 14 bytes:

 0803: A6 22 LDX $22 0805: 9D C0 07 STA $07C0,X 0808: A6 20 LDX $20 080A: 9D C0 07 STA $07C0,X 080D: E6 22 INC $22 080F: C6 20 DEC $20

Usando o código de modificação própria (SMC), você pode escrever isso de forma mais compacta:

  ldx x1 sta $0400 + 24*40, x addr0: sta $0400 + 24*40 ; advance the second x-coord with SMC inc addr0+1 dec x1

... que é codificado em 13 bytes:

 0803: A6 22 LDX $22 0805: 9D C0 07 STA $07C0,X 0808: 8D C0 07 STA $07C0 080B: EE 09 08 INC $0809 080E: C6 22 DEC $22

Truque 3. Estado da operação 'power on'


Foi considerado normal na competição fazer suposições malucas sobre o ambiente de trabalho. Por exemplo, que o desenho da linha é a primeira coisa que começa após ligar a energia do C64 e não há requisitos para uma saída limpa de volta à linha de comando do BASIC. Portanto, tudo o que você encontra no ambiente inicial ao entrar no PRG pode e deve ser usado para sua vantagem:

  • Os registros A, X, Y são tomados como zeros
  • Todos os sinalizadores da CPU limpos
  • Conteúdo do Zeropage (endereços de $00 $ff )

Da mesma forma, ao chamar alguns procedimentos de KERNAL ROM, você pode tirar proveito de todos os efeitos colaterais: sinalizadores de CPU retornados, valores temporários de zeropage, etc.

Após as primeiras otimizações, vamos procurar algo interessante na memória da máquina:



O Zeropage contém alguns valores úteis para nossos propósitos:

  • $d5 : 39 / $ 27 == comprimento da linha - 1
  • $22 : 64 / $ 40 == valor inicial para o contador de inclinação da linha

Isso economizará alguns bytes durante a inicialização. Por exemplo:

 !let x0 = $20 lda #39 ; 0801: A9 27 LDA #$27 sta x0 ; 0803: 85 20 STA $20 xloop: dec x0 ; 0805: C6 20 DEC $20 bpl xloop ; 0807: 10 FC BPL $0805

Como $d5 contém o valor 39, você pode indicá-lo para o contador x0 , livrando-se do par LDA / STA:

 !let x0 = $d5 ; nothing here! xloop: dec x0 ; 0801: C6 D5 DEC $D5 bpl xloop ; 0803: 10 FC BPL $0801

Philip, o vencedor do concurso, leva isso a extremos em seu código . Lembre-se do endereço do último caractere da cadeia $07C0 (== $0400+24*40 ). Este valor não está presente no zeropage durante a inicialização. No entanto, como efeito colateral de como a rotina de rolagem da ROM usa valores temporários de zeropage, os endereços $D1-$D2 na saída da função conterão o valor $07C0 . Portanto, para armazenar um pixel, em vez de STA $07C0,x você pode usar um menor do STA ($D1),y indiretamente indexado STA ($D1),y .

Truque 4. Otimização de download


Um binário PRG C64 típico contém o seguinte:

  • Primeiros 2 bytes: endereço de download (geralmente $0801 )
  • 12 bytes da sequência de inicialização do BASIC

A sequência principal de inicialização fica assim (aborda $801-$80C ):

 0801: 0B 08 0A 00 9E 32 30 36 31 00 00 00 080D: 8D 20 D0 STA $D020

Sem entrar em detalhes sobre o layout da memória tokenizada BASIC , essa sequência corresponde mais ou menos a '10 SYS 2061 '. O endereço 2061 ( $080D ) é onde nosso programa de código de máquina real é executado quando o intérprete BASIC executa o comando SYS.

Parece que 14 bytes é demais. Philip, Matlev e Geir usaram vários truques complicados para se livrar completamente da sequência principal. Isso requer o carregamento do PRG com LOAD"*",8,1 , pois LOAD"*",8 ignora o endereço de carregamento do PRG (dois primeiros bytes) e sempre é carregado em $0801 .



Dois métodos foram usados ​​aqui:

  • Truque de pilha
  • Truque de redefinição quente básico

Truque de pilha


O truque é $01F8 na pilha do processador a $01F8 valor que indica nosso ponto de entrada desejado. Isso é feito criando um PRG que começa com um ponteiro de 16 bits para o nosso código e carregando o PRG em $01F8 :

  * = $01F8 !word scroll - 1 ; overwrite stack scroll: jsr $E8EA

Assim que o carregador BASIC (consulte o código após a desmontagem ) terminar o carregamento e desejar retornar ao chamador usando RTS , ele retornará diretamente ao nosso PRG.

Truque de redefinição quente básico


Isso é um pouco mais fácil de explicar simplesmente olhando para o PRG após a desmontagem.

 02E6: 20 EA E8 JSR $E8EA 02E9: A4 D5 LDY $D5 02EB: A9 A0 LDA #$A0 02ED: 99 20 D0 STA $D020,Y 02F0: 91 D1 STA ($D1),Y 02F2: 9D B5 07 STA $07B5,X 02F5: E6 D6 INC $D6 02F7: 65 90 ADC $90 02F9: 85 90 STA $90 02FB: C6 D5 DEC $D5 02FD: 30 FE BMI $02FD 02FF: 90 E7 BCC $02E8 0301: 4C E6 02 JMP $02E6

Preste atenção na última linha ( JMP $02E6 ). A instrução JMP começa em $0301 com um endereço de salto de $0302-$0303 .

Quando esse código é carregado na memória, começando no endereço $02E6 , o valor $02E6 gravado nos endereços $0302-$0303 . Bem, este local tem um significado especial: contém um ponteiro para o “ciclo de espera BASIC” (consulte o cartão de memória C64 para obter mais detalhes). O download do PRG o substitui por $02E6 e, portanto, quando o intérprete BASIC após uma reinicialização a quente tenta ir para o loop de espera, ele nunca entra nesse loop, mas entra no programa de renderização!

Outros truques com o lançamento do BASIC


Petri descobriu outro truque básico de lançamento que permite inserir suas próprias constantes no zeropage. Neste método, você cria manualmente sua própria sequência inicial BASIC tokenizada e codifica as constantes nos números de linha do programa BASIC. Na entrada, os números da linha BASIC, ou seja, suas constantes serão armazenadas nos endereços $39-$3A . Muito esperto!

Truque 5. Fluxo de controle personalizado


Aqui está uma versão ligeiramente simplificada do loop x que imprime apenas uma linha e interrompe a execução:

  lda #39 sta x1 xloop: lda #$a0 ldx x1 sta $0400 + 24*40, x adc yf sta yf bcc no_scroll ; scroll screen up! jsr $e8ea no_scroll: dec x1 bpl xloop ; intentionally halt at the end inf: jmp inf

Mas há um erro. Quando desenhamos o último pixel, não podemos mais rolar a tela. Assim, são necessárias ramificações adicionais para interromper a rolagem após a gravação do último pixel:

  lda #39 sta x1 xloop: lda #$a0 ldx x1 sta $0400 + 24*40, x dec x1 ; skip scrolling if last pixel bmi done adc yf sta yf bcc no_scroll ; scroll screen up! jsr $e8ea no_scroll: jmp xloop done: ; intentionally halt at the end inf: jmp inf

O fluxo de controle é muito semelhante ao que o compilador C produzirá a partir de um programa estruturado. O código para pular a última rolagem apresenta uma nova instrução JMP abs que leva 3 bytes. Os saltos condicionais têm apenas dois bytes de comprimento, pois codificam endereços de salto usando um operando de 8 bits relativo com endereçamento direto.

O JMP para “pular a última rolagem” pode ser evitado movendo a chamada de rolagem para o topo do loop e alterando ligeiramente a estrutura do fluxo de controle. Veja como Philip o implementou:

  lda #39 sta x1 scroll: jsr $e8ea xloop: lda #$a0 ldx x1 sta $0400 + 24*40, x adc yf sta yf dec x1 ; doesn't set carry! inf: bmi inf ; hang here if last pixel! bcc xloop ; next pixel if no scroll bcs scroll ; scroll up and continue

Isso elimina completamente um JMP de três bytes e converte o outro JMP em uma ramificação condicional de dois bytes, economizando um total de 4 bytes.

Truque 6. Linhas com compressão de bits


Alguns elementos não usam o contador de inclinação de linha, mas compactam os bits em uma constante de 8 bits. Essa embalagem é baseada no fato de que a posição do pixel ao longo da linha corresponde a um padrão repetitivo de 8 pixels:

 int mask = 0xB6; // 10110110 uint8_t* dst = screenRAM; for (int x = 0; x < 40; x++) { dst[x] = 0xA0; if (mask & (1 << (x&7))) { dst += 40; // go down a row } }

Isso se traduz em um montador bastante compacto. No entanto, as opções do contador de inclinação são geralmente ainda menores.

Vencedor


Aqui está o programa vencedor do concurso de 34 bytes de Philip. A maioria dos truques acima funciona bem em seu código:

 ov = $22 ; == $40, initial value for the overflow counter ct = $D5 ; == $27 / 39, number of passes. Decrementing, finished at -1 lp = $D1 ; == $07C0, pointer to bottom line. Set by the kernal scroller ; Overwrite the return address of the kernal loader on the stack ; with a pointer to our own code * = $01F8 .word scroll - 1 scroll: jsr $E8EA ; Kernal scroll up, also sets lp pointer to $07C0 loop: ldy ct ; Load the decrementing counter into Y (39 > -1) lda #$A0 ; Load the PETSCII block / black col / ov step value sta $D020, y ; On the last two passes, sets the background black p1: sta $07C0 ; Draw first block (left > right line) sta (lp), y ; Draw second block (right > left line) inc p1 + 1 ; Increment pointer for the left > right line adc ov ; Add step value $A0 to ov sta ov dec ct ; Decrement the Y counter bmi * ; If it goes negative, we're finished bcc loop ; Repeat. If ov didn't overflow, don't scroll bcs scroll ; Repeat. If ov overflowed, scroll

Mas por que insistir em 34 bytes?


Assim que o concurso terminou, todos compartilharam seu código e anotações - e uma série de discussões animadas ocorreu sobre como melhorá-lo ainda mais. Após o prazo, várias outras opções foram apresentadas:


Certifique-se de olhar - existem várias pérolas reais.


Obrigado pela leitura. E um agradecimento especial a Matlev, Phil, Geir, Petri, Jamie, Ian e David pela participação (espero não ter sentido falta de ninguém - foi realmente difícil rastrear todas as menções no Twitter!)

O PS Petri chamou meu concurso de "anual", então provavelmente te vejo no próximo ano.

Source: https://habr.com/ru/post/pt464377/

More articles:


All Articles