Naposledy o C64 a mém rotozoomeru

Tento článek popisuje, jak funguje moje 1KB intro pro Commodore 64, které jsem přihlásil na demoparty Forever 2026. Přikládám i zdrojový kód, takže pokud někdo vidí, že by šlo něco udělat lépe nebo úsporněji – klidně dejte vědět. Kdo mne zná, ví že jsem Speccy maniak, takže C64 byl pro mě nový terén.

Rotozoomer je jeden z klasických demo efektů a byl to můj jeden velký sen, nějaký si udělat. Ano trvalo to spoustu let, přemlouvání, ale nakonec se mi povedl a jsem spokojený. Na obrazovce se zobrazuje textura – v tomto případě barevná šachovnice s nápisem "C64" – která se zároveň otáčí a přibližuje/oddaluje. Výsledek vypadá, jako by kamera kroužila nad dlaždicovým vzorem. Efekt je doplněn o plynulý pohyb v ose X a pulsující zoom. Chtěl jsem sem dopsat, že to popisuji pro nevidomé, kteří navštěvují můj web, ale ti by si to asi ani nepřečetli.... :)

Intro se skládá ze tří fází:

1. Dissolve efekt – BASIC obrazovka se náhodně "rozpadá" a mizí (cca 3 sekundy)
2. Intro část – textura s nápisem C64 se pomalu otáčí s pevným zoomem (cca 4 sekundy)
3. Hlavní smyčka – plný rotozoomer s animovaným zoomem, pohybem a rotací – běží donekonečna

Jelikož jsem měl již hotový efekt pro ZX Spectrum, chtěl jsem použít stejný způsob kreslení jako v ZX intru. Commodore 64 má obrazovku rozdělenou do mřížky 40×25 znaků (trošku jiné než na ZX). Každý znak je ve skutečnosti čtvereček 8×8 pixelů (stejné jako na ZX). Normálně se znaky kreslí z takzvaného Character ROM – paměti, kde jsou uložené tvary písmen a symbolů.

Ale my Character ROM vůbec nepoužijeme. Místo toho naplníme celou obrazovku znakem číslo 160 – to je v PETSCII kódování plný blok, tedy čtvereček vyplněný celý jednou barvou (vím, teoreticky jí použijeme, ale jen na to vyplnění). A barvu každého znaku určuje Color RAM, speciální paměť na adrese $D800 - ano, podobně jako atributy na ZX.

Matematika rotozoomeru (nebojte se, přežijete to)

Rotozoomer funguje na principu mapování textury. Pro každý "pixel" na obrazovce potřebujeme zjistit, jakou barvu má mít – tedy na jaké místo v textuře odpovídá.

Textura je čtvercový obrázek 16×16 bodů, který se opakuje donekonečna (jako dlaždice na podlaze). Každý bod v textuře má souřadnice U a V (je zvykem používat U a V místo X a Y, aby se to nepletlo se souřadnicemi obrazovky).

Kdybychom chtěli texturu zobrazit rovně a bez zoomu, byl by výpočet triviální: pixel na pozici (X, Y) obrazovky odpovídá bodu (X, Y) v textuře. Ale my chceme texturu otočit o nějaký úhel a přiblížit nebo oddálit. K tomu slouží matice rotace.

Rotace bodu (U, V) o úhel φ funguje takto:

  U' = U * cos(φ) - V * sin(φ)
  V' = U * sin(φ) + V * cos(φ)

Zoom přidáme jednoduše tím, že hodnoty sin a cos přeškálujeme – čím větší číslo, tím víc se textura "roztáhne" a zdá se, že je blíže.

Kdybychom tohle počítali pro každý pixel zvlášť, potřebovali bychom spoustu násobení a bylo by to pomalé. Používá se ale chytrý trik: přírůstkový výpočet.

Všimněme si, že pohybem o jeden pixel doprava na obrazovce se texturové souřadnice změní vždy o stejnou hodnotu – říkejme jí dU a dV. Podobně pohybem o jeden pixel dolů se souřadnice změní o jinou konstantní hodnotu.

Tyto přírůstky jsou:

  dU (na pixel doprava)  = cos(φ) * zoom_faktor
  dV (na pixel doprava)  = sin(φ) * zoom_faktor

A pro pohyb o řádek dolů to jsou hodnoty kolmé na předchozí:

  pro posun na další řádek: row_U -= dV,  row_V += dU

Díky tomu stačí na začátku spočítat dU a dV jednou, a pak pro každý pixel jen přičítáme – žádné další násobení nebo sin/cos výpočty za běhu!

Jak se to implementuje na 6502?

Procesor 6502 (resp. 6510 v C64) je v mnoha ohledech "chudší" než Z80, na kterém jsem zvyklý programovat. Má jen tři registry – A (akumulátor), X a Y – a žádné 16-bitové operace. Vše 16-bitové musíme dělat ručně po bajtech.

Pro plynulé animace potřebujeme desetinná čísla. Na 8-bitovém procesoru je standardním řešením fixed-point aritmetika: číslo reprezentujeme jako celé číslo, ale myslíme si, že desetinná čárka je někde uprostřed. Například 16-bitové číslo $0380 interpretujeme jako 3,5 – vysoký bajt je celá část (3), nízký bajt je desetinná část ($80 = 128/256 = 0,5).

Souřadnice textury U a V jsou tedy uloženy jako dvojice bajtů: u_hi + u_lo, v_hi + v_lo. Přírůstky dU a dV stejně tak: du_hi + du_lo, dv_hi + dv_lo. Sčítání pak vypadá takto:

  lda u_lo
  clc
  adc du_lo     ; přičti nízký bajt (desetinná část)
  sta u_lo
  lda u_hi
  adc du_hi     ; přičti vysoký bajt + carry z předchozího
  sta u_hi

Přechod řádku (row_U -= dV) je analogický, jen používáme odečítání přes SBC.

Výpočet dU a dV: sin tabulka a mulzoom

Abychom nemuseli počítat sin a cos za běhu (na 6502 by to bylo prakticky nemožné v rozumném čase), máme v programu předpočítanou tabulku sinusu – 256 hodnot pro úhly 0° až 360°. Hodnoty jsou v rozsahu -29 až +29 (tedy sin(x) * 29, zaokrouhleno na celá čísla).

Cosinus dostaneme zadarmo: cos(φ) = sin(φ + 90°). Protože máme 256 hodnot pro celý kruh, 90° = 64 pozic v tabulce. Takže cos(angle) = sintab[angle + 64].

Výpočet dU pak vypadá:

  dU = sintab[angle + 64] * zoom / 64
  dV = sintab[angle]      * zoom / 64

Dělení 64 je proto, aby výsledek byl ve správném měřítku pro fixed-point aritmetiku. A toto násobení s dělením obstarává rutina mulzoom.

Mulzoom implementuje násobení metodou "shift and add" – klasický algoritmus binárního násobení, kde číslo postupně posouváme doprava a přičítáme druhý operand vždy, když je aktuální bit 1. Protože hned pak dělíme 64 (= 2^6), stačí udělat jen 6 iterací místo 8 – výsledek přirozeně "vypadne" ve správné bitové pozici.

Dissolve efekt a LFSR

Na začátku intra se BASIC obrazovka náhodně "rozpadá" – znaky mizí v náhodném pořadí. K tomu potřebujeme generátor pseudonáhodných čísel, ale v 1KB programu není místo na nic sofistikovaného.

Řešením je LFSR – Linear Feedback Shift Register. Je to jen jeden bajt, který v každém kroku posuneme doleva (ASL) a pokud vypadne 1 (carry), XORujeme s konstantou $1D. Výsledkem je sekvence 127 různých hodnot, která vypadá náhodně, ale je deterministická a zabere jen pár bajtů kódu.

Synchronizace s obrazovkou

Aby obraz neblikal a netrhal se, musíme kreslit ve chvíli, kdy elektronový paprsek není ve viditelné části obrazovky. C64 má registr $D012 (RASTER), který udává aktuální vykreslovací řádek. Čekáme na řádek 250 – to je pod obrazem – a teprve pak začneme kreslit.

-   lda $d012
    cmp #250
    bne -        ; čekej dál dokud nejsme na řádku 250

Jak se vešlo vše do 1 kilobajtu?

Výsledná velikost je přesně 1024 bajtů, ale první verze měla kolem 2kB... takže jsem prvotní pokus hodně optimalizovat... ale nakonec se povedlo :)

Zdrojový kód

Kód je psaný pro assembler ACME a je (snad) dobře okomentovaný. V komentářích najdete i srovnání s Z80 instrukcemi pro ty, kdo přicházejí ze světa ZX Spectra jako já.

Hlavní části kódu:

• start – inicializace, BASIC stub (SYS 2064), vymazání obrazovky
• falling – dissolve efekt s LFSR pseudonáhodným generátorem
• intro – úvodní rotace s pevným zoomem, 200 snímků
• main – hlavní smyčka s animovaným zoomem a pohybem
• rotozoom – výpočet zoom faktoru z sin tabulky, nastavení pozice
• calc_duv – výpočet přírůstků dU/dV z úhlu a zoomu
• draw – samotné vykreslení 36×21 "pixelů" do Color RAM
• mulzoom – násobení se znaménkem metodou shift-and-add, dělení 64
• signext – rozšíření znaménka z 8 na 16 bitů
• sintab – předpočítaná tabulka sinusu, 256 hodnot (-29 až +29)
• texture – textura 16×16 bajtů, šachovnice s nápisem "C64"

Co by šlo udělat lépe?

Jsem si vědom několika věcí, které nejsou ideální:

• Sin tabulka má "ploché" oblasti kolem maxima a minima (index 64 a 192), kde je hodně stejných hodnot. To způsobuje mírné vizuální "zasekávání" při určitých úhlech. Proto intro startuje na úhlu 5 místo 0.
• Výpočet indexu do textury dělá v draw smyčce instrukci AND #$FF, která je zbytečná (bajt je vždy 8-bitový). Zůstal tam z ladění a všiml jsem si ji až po odeslání příspěvku.
• Pohyb v ose Y je statický – row_v_hi je pořád 2. Zbyl by bajt nebo dva na animaci i v Y, ale jak to jen říct... .
• Kdybych chtěl ještě ušetřit, šlo by sin tabulku zkrátit na 64 hodnot a zbytek symetrie dopočítat – ale to by přidalo kód a už jsem nechtěl experimentovat.

Kdyby měl někdo lepší nápady na optimalizaci – ať velikostní nebo výkonnostní – klidně se ozvěte. Pro C64 jsem programoval poprvé a jistě tam jsou věci, které by zkušený C64 koder udělal elegantněji. Možná jsou ve zdrojovém kódu časti, které nedávaji smysl (teď jsem například jen pohledem narazil na and #$ff , který je pozůstatkem ladění, ale už jsem to nechal tak jak je a nebudu to dále řešit...

Jo málem jsem zapomněl, zdrojový kód si můžete stáhnout zde.