Con l’inizio del nuovo anno, il gruppo RetroProgramming Italia ha indetto una nuova sfida, il cui obiettivo consiste nel riprodurre 10000 punti del frattale noto come Triangolo di Sierpiński nel minor tempo possibile, implementando l’algoritmo chaos game per i sistemi a 8/16 bit prescelti.
In passato avevo già avuto modo di cimentarmi con questo algoritmo, realizzandone implementazioni in differenti linguaggi per svariati sistemi; ricordo tra queste una versione per CHIP-8, una in BASIC per ZX81 (ridotta successivamente a sole 9 linee di programma in occasione del BASIC 10Liner Contest 2020 e riportata in un frame TeleText/TeleVideo) e una in JavaScript.
Avendo già dimestichezza con l’argomento, che reputo molto interessante e stimolato dall’adesione di persone di rilievo nel mondo della retroprogrammazione, ho deciso di partecipare, ponendomi anche l’obiettivo di imparare qualcosa di nuovo. Mi sono focalizzato quindi sull’implementazione in linguaggio C per ZX Spectrum con z88dk.
z88dk include già, tra gli esempi forniti, un’implementazione in C dell’algoritmo chaos game; tuttavia, essendo codice multipiattaforma, non è ottimizzato e l’esecuzione risulta particolarmente lenta.
Per questo motivo, ho praticamente riscritto il programma, avvalendomi della nuova libreria C (newlib) e affidandomi al compilatore sdcc. La nuova libreria non contiene primitive grafiche ad alto livello, per cui per disegnare i punti del frattale ho fatto ricorso alle funzioni per manipolare gli indirizzi della memoria video, definendo la seguente macro:
#define plot(x,y) *zx_pxy2saddr((x),(y)) |= zx_px2bitmask((x));Ho ottenuto un’ulteriore riduzione dei tempi di esecuzione modificando la generazione dei di numeri pseudocasuali utilizzati per selezionare il vertice ad ogni iterazione, rimuovendo la chiamata alla funzione rand() della libreria standard e utilizzando i valori dei byte della ROM dello ZX Spectrum come sequenza “pseudocasuale”.
Con queste modifiche ed altri piccoli accorgimenti (tra cui lo shift a destra di 1 bit per implementare la divisione per 2 e l’utilizzo di 2 cicli annidati con variabili di controllo a 8 bit anziché di un unico ciclo con variabile di controllo a 16 bit), sono riuscito ad abbassare i tempi di esecuzione, su uno ZX Spectrum +2, emulato con Fuse, a:
- 1.66 secondi per 3000 iterazioni e
- 5.42 secondi per 10000 iterazioni.
Tornando alla macro plot definita prima, è interessante notare che la memoria video dello ZX Spectrum non è gestita in modo lineare. Questo significa che, per poter disegnare ciascun punto del frattale, è necessario svolgere alcuni calcoli per determinare la locazione di memoria il cui contenuto deve essere modificato per “accendere” il pixel corrispondente.Una tecnica utilizzata per ridurre queste operazioni è quella di precalcolare alcuni valori e memorizzarli in un array, in modo da poterli recuperare istantaneamente. Nella fattiscpecie, ho modificato il programma per precalcolare gli indirizzi delle locazioni di memoria corrispondenti al primo byte di ciascuna delle 192 linee dello schermo:
uint8_t *screen_line_address[192];
for (y=0; y<192; y++)
{
screen_line_address[y] = zx_py2saddr(y);
}In questo modo, per “accendere” un pixel, è sufficiente reperire l’indirizzo precalcolato della linea, determinare e sommare l’offset del byte da modificare in base all’ascissa e settare il bit corrispondente al punto da disegnare:
*(screen_line_address[y] + (x >> 3)) |= m[x & 0x07];Con questa modifica, il tempo di esecuzione per 10000 iterazioni è sceso a 5.04 secondi.
Nonostante la riduzione ottenuta, il tempo di esecuzione risultava ancora troppo elevato. Facendo alcune prove, ho appurato che la lentezza era dovuta all’operazione di modulo 3, utilizzata in ciascuna iterazione per ricondurre il numero casuale nell’intervallo degli indici dei 3 possibili vertici, compreso tra 0 e 2.
Ho quindi sostituito il modulo con l’operazione di AND bit a bit e aggiunto un po’ di logica per selezionare indici validi nel caso in cui il risultato fosse 3.
Con l’eliminazione del modulo, sono riuscito ad abbassare il tempo di esecuzione a 1.84 secondi per 10000 iterazioni. La qualità dell’immagine generata è leggermente peggiorata, a causa della logica aggiunta, tutt’altro che casuale.
Senza la pretesa di fare meglio degli autori di z88dk, ma per il puro gusto della programmazione, ho sostituito la chiamata alla funzione zx_py2saddr() con la mia implementazione, constatando con piacere di non aver incrementato il tempo di esecuzione:
(((y & 0x07) | ((y & 0xC0) >> 3) | 0x40) << 8) | ((y & 0x38) << 2)Il seguente video mostra il programma in azione:
Puoi vedere il programma in azione, oppure scaricare l’archivio contenente il proframma in formato .tap e il codice sorgente C, riportato anche di seguito:
#pragma output CRT_ORG_CODE = 0x8184 // sposto ORG per lasciare spazio per la tabella IM2
#pragma printf "%f" // utilizzo printf solo per stampare il tempo di esecuzione (float)
#include <arch/zx.h>
#include <cpu.h>
#include <im2.h>
#include <intrinsic.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Contatore frame (utilizzato per tenere traccia del tempo di esecuzione).
uint8_t frames = 0;
// IM2 service routine. Incrementa il contatore ad ogni frame.
IM2_DEFINE_ISR_8080(isr)
{
++frames;
}
// Utilizzato per "accendere" i pixel nella memoria video: il pixel 0 è quello più a sinistra.
uint8_t m[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
// Ascisse dei vertici del triangolo
uint8_t a[] = { 0, 127, 255 };
// Ordinate dei vertici del triangolo
uint8_t b[] = { 191, 0, 191 };
// Coordinate del punto da disegnare
uint8_t x,y;
// Puntatore ai dati della ROM (utilizzati come sequenza "pseudocasuale")
uint8_t *p = 0;
// Valore pseudocasuale nell'intervallo 0..2, utilizzato come indice per selezionare il vertice del triangolo ad ogni iterazione.
uint8_t k;
// Variabile d'appoggio per la generazione dei numeri "pseudocasuali"
uint8_t h = 0;
// Indici per i loop.
uint8_t i;
uint8_t j;
// Puntatori al primo byte della memoria video per ciscuna delle 192 linee dello schermo.
uint8_t *screen_line_address[192];
// Tempo di esecuzione.
float es;
void main()
{
// Inizializza interrupt IM2.
im2_init((void*)0x8000);
memset((void*)0x8000, 0x81, 257);
cpu_bpoke(0x8181, 0xc3);
cpu_wpoke(0x8182, (unsigned int)isr);
// Abilita interrupt.
intrinsic_ei();
// Precalcola puntatori alla memoria video per ciscuna linea dello schermo.
for (y=0; y<192; y++)
{
screen_line_address[y] = (uint8_t *) ((((y & 0x07) | ((y & 0xC0) >> 3) | 0x40) << 8) | ((y & 0x38) << 2));
}
x = a[0];
y = b[0];
zx_cls(PAPER_WHITE);
// 10000 iterazioni
for (i=0; i<100; i++)
{
for (j=0; j<100; j++)
{
// k = numero "casuale" compreso tra 0 e 2, utilizzato come indice per selezionare il vertice del triangolo.
k = (*p++ & 0x03);
if (k == 3)
{
k = h;
if (++h == 3)
h = 0;
}
// Calcola coordinate del punto da disegnare.
x=(x+a[k])>>1;
y=(y+b[k])>>1;
// Disegna punto (x, y).
*(screen_line_address[y] + (x >> 3)) |= m[x & 0x07];
}
}
// Calcola e stampa tempo trascorso.
es = (float)frames / 50;
printf("%f", es);
// Fin.
for(;;);
}Sicuramente c’è ancora molto margine di miglioramento, ma per ora posso ritenermi soddisfatto del risultato raggiunto.
Concludo con un ringraziamnento allo staff di RetroProgramming Italia per l’opportunità di partecipare a questa interessantissima iniziativa!