Geekly articles weekly

Ensamblador sucio piratea 6502

Este artículo enumera algunos de los trucos que utilizaron los participantes en mi pequeño concurso de programación Commodore 64 . Las reglas del concurso eran simples: crear un archivo ejecutable C64 (PRG), que dibuja dos líneas para formar la imagen a continuación. El que tiene un archivo de menor tamaño ganó.


Las entradas de la competencia se publicaron en tweets abiertos y en mensajes privados que contenían solo bytes del archivo PRG y un hash MD5.

Lista de participantes con enlaces al código fuente:


(Si extrañé a alguien, avíseme, actualizaré la lista).

El resto del artículo está dedicado a algunos trucos de ensamblador que se usaron en la competencia.

Los fundamentos


Graphics C64 funciona de manera predeterminada en el modo de codificación de 40x25 caracteres. El framebuffer en RAM se divide en dos matrices:

  • $0400 (RAM de pantalla, 40x25 bytes)
  • $d800 (RAM en color, 40x25 bytes)

Para establecer un carácter, guarde el byte en la RAM en pantalla, a $0400 (por ejemplo, $0400+y*40+x ). El color RAM se inicializa en azul claro de forma predeterminada (color 14): este es el color que usamos para las líneas, es decir, el color RAM se puede dejar sin tocar.

Puede controlar los colores del borde y el fondo utilizando los registros de E / S de memoria en $d020 (borde) y $d021 (fondo).

Dibujar dos líneas es bastante fácil si programa directamente la pendiente de una línea fija. Aquí hay una implementación en C que dibuja líneas y vacía el contenido de la pantalla a stdout ( malloc() se usa para hacer que el código funcione en una 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); }

Los códigos de pantalla anteriores son $20 (en blanco) y $a0 (bloque 8 × 8 lleno). Si corres, verás una imagen ASCII con dos líneas:

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

Lo mismo se implementa trivialmente en ensamblador:

 !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 }

Resulta PRG un tamaño bastante grande de 286 bytes.

Antes de sumergirnos en la optimización, hacemos algunas observaciones.

En primer lugar, trabajamos en C64 con las rutinas ROM instaladas. Hay toneladas de rutinas que pueden ser útiles. Por ejemplo, limpiar la pantalla con JSR $E544 .

En segundo lugar, los cálculos de dirección en un procesador de 8 bits como 6502 pueden ser engorrosos y consumir muchos bytes. Este procesador tampoco tiene un multiplicador, por lo que un cálculo como y*40+i generalmente incluye un montón de cambios lógicos o una tabla de búsqueda que también consume bytes. Para evitar multiplicar por 40, es mejor avanzar el cursor de la pantalla 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 agregando la pendiente de la línea al contador fijo yf , y cuando la adición de 8 bits establece la bandera de acarreo, suma 40.

Aquí hay un enfoque de ensamblador incremental:

 !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 }

Con 82 bytes, sigue siendo bastante fuerte. Un problema obvio son los cálculos de direcciones de 16 bits. Establezca el valor de screenptr para la screenptr indirecta:

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

screenptr a la siguiente línea agregando 40:

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

Por supuesto, este código se puede optimizar, pero ¿qué pasa si se deshace de las direcciones de 16 bits? Veamos como hacerlo.

Truco 1. ¡Desplazamiento!


En lugar de construir una línea en la RAM en pantalla, dibujamos solo en la última línea de pantalla Y = 24 y desplazamos hacia arriba toda la pantalla, ¡llamando a la función de desplazamiento ROM con JSR $E8EA !

Así es como se optimiza xloop:

  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

Así es como se ve el renderizado:



Este es uno de mis trucos favoritos en este programa. Casi todos los concursantes lo encontraron por su cuenta.

Truco 2. Código auto modificable


El código para almacenar valores de píxeles termina así:

  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

Esto está codificado en la siguiente secuencia 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

Con el código de modificación automática (SMC), puede escribir esto de manera más 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 está codificado en 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

Truco 3. Estado de operación 'encendido'


Se consideraba normal en la competencia hacer suposiciones descabelladas sobre el entorno laboral. Por ejemplo, que el dibujo lineal es lo primero que comienza después de encender el C64, y no hay requisitos para una salida limpia de vuelta a la línea de comando BASIC. Por lo tanto, todo lo que encuentre en el entorno inicial al ingresar al PRG puede y debe usarse a su favor:

  • Los registros A, X, Y se toman como ceros
  • Todos los indicadores de CPU borrados
  • Contenido de página cero (direcciones $00 - $ff )

Del mismo modo, al llamar a algunos procedimientos de ROM KERNAL, puede aprovechar al máximo cualquier efecto secundario: indicadores de CPU devueltos, valores temporales de cero páginas, etc.

Después de las primeras optimizaciones, busquemos algo interesante en la memoria de la máquina:



Zeropage contiene algunos valores útiles para nuestros propósitos:

  • $d5 : 39 / $ 27 == longitud de línea - 1
  • $22 : 64 / $ 40 == valor inicial para el contador de pendiente de línea

Esto ahorrará algunos bytes durante la inicialización. Por ejemplo:

 !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 contiene el valor 39, puede indicarlo al contador x0 , deshaciéndose del par LDA / STA:

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

Philip, el ganador del concurso, lo lleva a extremos en su código . Recuerde la dirección del último carácter de la cadena $07C0 (== $0400+24*40 ). Este valor no está presente en zeropage durante la inicialización. Sin embargo, como efecto secundario de cómo la rutina de desplazamiento desde la ROM utiliza valores temporales de cero páginas, las direcciones $D1-$D2 en la salida de la función contendrán el valor $07C0 . Por lo tanto, para almacenar un píxel, en lugar de STA $07C0,x puede usar el direccionamiento de índice indirecto más corto STA ($D1),y para un byte.

Truco 4. Descargar Optimization


Un binario PRG C64 típico contiene lo siguiente:

  • Primeros 2 bytes: dirección de descarga (generalmente $0801 )
  • 12 bytes de la secuencia de arranque BASIC

La secuencia de arranque principal se ve así (direcciones $801-$80C ):

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

Sin entrar en detalles sobre el diseño de memoria tokenizada BASIC , esta secuencia corresponde más o menos a '10 SYS 2061 '. La dirección 2061 ( $080D ) es donde se ejecuta nuestro programa de código de máquina real cuando el intérprete BASIC ejecuta el comando SYS.

Simplemente parece que 14 bytes es demasiado. Philip, Matlev y Geir usaron varios trucos difíciles para deshacerse por completo de la secuencia principal. Esto requiere cargar el PRG con LOAD"*",8,1 , ya que LOAD"*",8 ignora la dirección de carga PRG (primeros dos bytes) y siempre se carga a $0801 .



Aquí se usaron dos métodos:

  • Truco de pila
  • Truco de reinicio cálido BÁSICO

Truco de pila


El truco consiste en ingresar a la pila del procesador a $01F8 valor que indica nuestro punto de entrada deseado. Esto se hace creando un PRG que comienza con un puntero de 16 bits a nuestro código y cargando el PRG a $01F8 :

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

Tan pronto como el cargador BASIC (vea el código después del desensamblaje ) haya terminado de cargarse y quiera regresar a la persona que llama usando RTS , regresa directamente a nuestro PRG.

Truco de reinicio cálido BÁSICO


Esto es un poco más fácil de explicar simplemente mirando el PRG después del desmontaje.

 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

Presta atención a la última línea ( JMP $02E6 ). La instrucción JMP comienza en $0301 con una dirección de salto de $0302-$0303 .

Cuando este código se carga en la memoria comenzando en la dirección $02E6 , el valor $02E6 escribe en las direcciones $0302-$0303 . Bueno, esta ubicación tiene un significado especial: contiene un puntero al "ciclo de espera BÁSICO" (vea la tarjeta de memoria C64 para más detalles). La descarga de PRG lo sobrescribe con $02E6 y, por lo tanto, cuando el intérprete BASIC después de un reinicio en caliente intenta ir al ciclo de espera, nunca ingresa a este ciclo, ¡sino que ingresa al programa de renderizado!

Otros trucos con el lanzamiento de BASIC


Petri descubrió otro truco de lanzamiento BASIC que le permite ingresar sus propias constantes en zeropage. En este método, crea manualmente su propia secuencia de inicio BASIC tokenizada y codifica las constantes en los números de línea del programa BASIC. En la entrada, los números de línea BÁSICOS, es decir, sus constantes se almacenarán en las direcciones $39-$3A . Muy inteligente!

Truco 5. Flujo de control personalizado


Aquí hay una versión ligeramente simplificada de x-loop que solo imprime una línea y luego detiene la ejecución:

  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

Pero hay un error. Cuando dibujamos el último píxel, ya NO PODEMOS desplazar la pantalla. Por lo tanto, se necesitan ramas adicionales para detener el desplazamiento después de grabar el último píxel:

  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

El flujo de control es muy similar al que producirá el compilador de C a partir de un programa estructurado. El código para omitir el último desplazamiento introduce una nueva instrucción JMP abs que toma 3 bytes. Los saltos condicionales tienen solo dos bytes de longitud, ya que codifican direcciones de salto utilizando un operando relativo de 8 bits con direccionamiento directo.

Se puede evitar JMP para "omitir el último desplazamiento" moviendo la llamada de desplazamiento hacia la parte superior del bucle y cambiando ligeramente la estructura del flujo de control. Así es como Philip lo implementó:

  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

Esto elimina por completo un JMP de tres bytes y convierte el otro JMP en una rama condicional de dos bytes, ahorrando un total de 4 bytes.

Truco 6. Líneas con compresión de bits


Algunos elementos no usan el contador de pendiente de línea, sino que comprimen los bits en una constante de 8 bits. Tal empaque se basa en el hecho de que la posición del píxel a lo largo de la línea corresponde a un patrón repetitivo de 8 píxeles:

 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 } }

Esto se traduce en un ensamblador bastante compacto. Sin embargo, las opciones de contador de inclinación suelen ser incluso más pequeñas.

Ganador


Aquí está el programa ganador del concurso de 34 bytes de Philip. La mayoría de los trucos anteriores funcionan bien en su 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

Pero, ¿por qué detenerse en 34 bytes?


Tan pronto como terminó el concurso, todos compartieron su código y sus notas, y se llevó a cabo una serie de discusiones animadas sobre cómo mejorarlo aún más. Después de la fecha límite, se presentaron varias opciones más:


Asegúrese de mirar, hay varias perlas reales.


Gracias por leer Y un agradecimiento especial a Matlev, Phil, Geir, Petri, Jamie, Ian y David por su participación (espero no haber extrañado a nadie, ¡fue realmente difícil rastrear todas las menciones en Twitter!)

PD Petri llamó a mi concurso "anual", así que, probablemente nos veremos el año que viene.

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

More articles:


All Articles