Sierpinski challenge

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.

Triangolo di Sierpiński, generato con l'algoritmo chaos game.
Triangolo di Sierpiński, generato con l’algoritmo chaos game.

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.

SierpChaos CHIP-OTTO Z88
SierpChaos (versione CHIP-8) in esecuzione su CHIP-OTTO per Z88 (2017)

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.
Triangolo di Sierpinski (chaos game) su ZX Spectrum. Tempo di esecuzione: 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.

Triangolo di Sierpinski (chaos game) su ZX Spectrum. Tempo di esecuzione: 5.04 secondi per 10000 iterazioni.

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.

Triangolo di Sierpinski (chaos game) su ZX Spectrum. Tempo di esecuzione: 1.84 secondi per 10000 iterazioni.

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:

Triangolo di Sierpinski (chaos game) in esecuzione su ZX Spectrum +2, emulato con Fuse.

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!

Il triangolo di Sierpiński con lo ZX81: aggiornamento

Triangolo di Sierpinski su ZX81 - versione migliorata
Triangolo di Sierpinski su ZX81 – versione migliorata

Recentemente, sono venuto a conoscenza del BASIC 10Liner Contest e ho immediatamente pensato che il mio programma per generare il frattale noto come Triangolo di Sierpinski sul Sinclair ZX81, con le opportune modifiche, avrebbe potuto essere incluso a buon diritto tra i partecipanti della categoria “SCHAU”. Infatti, questa categoria è dedicata a demo, strumenti e applicazioni realizzati in 10 righe di codice (con lunghezza massima di 256 caratteri), mentre le altre categorie sono specifiche per i giochi.

Così, ho colto l’opportunità di riscrivere il codice, in modo da:

  • ridurre la lunghezza del programma (massimo 10 righe),
  • migliorare la qualità dell’immagine generata.

Il listato risultante è mostrato di seguito: il programma è effettivamente lungo 9 linee; inoltre, la scelta dei punti (X=0, Y=0), (X=30, Y=40) e (X=0, Y=60) quali vertici del triangolo garantisce un’immagine perfettamente simmetrica.

Listato del programma
Implementazione del programma di generazione del Triangolo di Sierpinski con algoritmo chaos game in 10 (anzi, 9!) righe

Bonus: per un’autentica esperienza retrocomputeristica, qui puoi trovare la versione TELETEXT/TELEVIDEO del listato BASIC e dell’output del programma!

Puoi scaricare un archivio zip contenente il codice sorgente, la documentazione completa e i file pronti per l’utilizzo con gli emulatori, oppure semplicemente vedere il programma in azione con l’emulatore online di ZX81.
Al completamento del caricamento, dovrebbe apparire una schermata bianca, con in fondo il messaggio “0/0”. A questo punto, per eseguire il programma, occorre premere il tasto “R” (ora dovrebbe essere visibile la scritta “RUN”, seguita da un cursore nero) ed infine il tasto “ENTER”.

Enjoy the SCHAU! 😉

Read in English

Il triangolo di Sierpiński con lo ZX81/Lambda 8300

Il triangolo di Sierpinski su Sinclair ZX81

Qualche anno fa, per combattere la noia durante un lungo viaggio in treno, scrissi un semplice programmino per ZX81, per disegnare il triangolo di Sierpiński utilizzando l’algoritmo chaos game.

Implementazione BASIC dell’algoritmo chaos game per disegnare il triangolo di Sierpinski su ZX81

Il programma non richiede alcuna espansione e pertanto può girare su ZX81 con 1 KB di memoria o su computer compatibili, come il Lambda 8300.
Proprio con quest’ultimo, oggi ho realizzato un video del programma in esecuzione:

Programma BASIC per rappresentare il triangolo di Sierpinski in esecuzione su computer Lambda 8300

Puoi eseguire il programma sull’emulatore online, oppure scaricare il file .p.

Triangolo di Sierpinski in esecuzione su Sinclair ZX81
Il programma in esecuzione su Sinclair ZX81
Read in English