Rust on the MOS 6502: Beyond Fibonacci

On August 15th, the following answer showed up on the Retrocomputing Stack Exchange site:

llvm-mos compiles a considerable subset of C++ to 6502 machine code out of the box. IIRC it's just missing "runtime support"; things like RTTI, exceptions, and the runtime layout of VTables. [...]

I came across this answer about a week later, so just in time for ICFP 2021 to start. I also had my Haskell Love talk coming up, and I really wanted to get the RetroClash page in shape by then, so that I can direct people there at the end of my talk.

But still! LLVM, and consequently, Rust, on a C64! Damn if that isn't the perfect nerd-sniping for me. So I looked around to find this 6502.org forum post that shows compiling a Rust implementation of the Fibonacci function and linking it with a small C main. I've reproduced their code here in a Git repo for easier fiddling.

So after ICFP, although other things kept piling up, including a GM-ing gig playing Trail of Cthulhu's excellent The Dance in the Blood and coordinating with the awesome David Thinnes on getting Arrow DECA support into clash-pong in time for Haskell Love, I carved out a weekend to dust off my Rust-on-AVR CHIP-8 implementation to try to get it running on the C64.

Full code on GitHub

Időrégész 2015

Amikor már megvolt a C64-ünk, megkaptam egyszerre az LSI-féle 1001 játék sorozat első három részét anyukáméktól (ez úgy '89 körül lehetett), azt hiszem a negyedik-ötödik rész később jelent meg. Annyira nem voltam a scene-ben, hogy azt sem tudtam, hogy van olyan, hogy scene. Az én scene-em az a pár általános iskolai osztálytárs volt, akinek legalább egy ZX Spectrumja volt. Szóval a lényeg, hogy ez a pár könyv volt minden kapcsolatom a C64 játékokkal. Azon a néhány játékon kívül, amik így apukám ismerősein keresztül jutottak hozzánk, a többiről csak olvasni tudtam. Persze a leírás alapján mindegyik a legjobb játéknak tűnt EVER!, és volt néhány, amit el is kezdtem BASIC-ben leprogramozni az alapján, ahogy elképzeltem; ez nyilván több oldalról is ab ovo teljes sikertelenségre volt ítélve.

A harmadik 1001 játékban volt egy végigjátszás az Időrégészről, amibe persze azonnal beleszerettem. A szöveges kalandjáték volt az egyetlen játék-műfaj, aminek a programozásában akkortájt labdába tudtam rúgni annyira, hogy valami játszható jöjjön ki belőle, és emiatt pláne úgy éreztem, hogy ez a játék megszólít engem. Ráadásul nem is tudom, hogy volt-e akkor már CoV, de az biztos, hogy én nem ismertem (a Magic Candle-ös szám volt az első, amikor belefutottam, ha minden igaz, '92-ben), úgyhogy a leírás stílusa, humora is egy teljesen új világot nyitott meg előttem.

Mivel a fent ecsetelt okok miatt warez-ként esélyem se volt hozzájutni, ez lett a második játék, amit eredetiben megvettünk (az első az Impossible Mission 2 volt (kazettán), de azzal én nem sokat játszottam, azt apukám tolta — külön post lehetne, amikor az éjszaka közepén, a TV hangerejét éppen csak hallhatóra állítva ordított a figura leesés közben).

A játék csalódást nem okozott, de végigjátszani az istennek se ment, még az 1001-leírás alapján sem. Az áttörést csak 1991-ben hozta egy osztálytársam, aki rájött, hogy SPOILER ALERT a papnál még imádkozni is kell, nem elég odaadni neki az aranykeresztet vagy mit.

Most illene arról is írni, hogy akkor most ez egy jó játék volt-e. Azt gondolom, hogy most tudom a legkevésbé ezt megítélni, mert túl közelről látom (mint majd mindjárt kiderül hogy miért). Az biztos, hogy akinek annak idején volt C64-e (vagy akár +4-e!), és magyar, az ismeri az Időrégészt meg a többi Rátkai-játékot: nem véletlenül volt róla IDDQD cikk meg Index illetve Facebook csoportok. Igazi cult classic.

Egy modern Időrégész-reprodukció terve

Mostanában elkezdtek érdekelni a régi 8-bites gépek, mivel annak idején az alacsonyszintű programozásuk, meg úgy egyáltalán a felépítésük totál kimaradt nekem. Most, hogy autodidakta módon FPGA-fejlesztést tanulok, elértem oda, hogy épkézláb számítógépeket tudok építeni, amihez persze elkerülhetetlen, hogy megismerjem minden kis részletüket. Ennek egyébként egy nem várt, de kellemes mellékhatása, hogy tudom értékelni a korabeli és azóta készült demókat, amikor minden képkockát önmagában is lehetetlennek tűnik előállítani a C64-en.

Szóval kitaláltam, hogy kipróbálnám egy játék teljes visszafejtését, mivel ilyesmit sose csináltam még. Egy ilyen nem-realtime, nem-grafikus játék, mint az Időrégész, remek kezdő projektnek tűnt. Az alap-elképzelés (még május elején) az volt, hogy visszafejtem a programot annyira, hogy tudjam minden részéről hogy mit csinál, és ezalapján megértem, és minél magasabb szinten reprodukálom a működését. Hogy valami igazán örök formában rögzítsem, mindenképpen a ZMachine virtuális gépet terveztem célbavenni, mivel a modern interactive fiction-világban ez tűnik egyértelműen a bevett eszköznek már évtizedek óta.

Brainfuck on the Commodore 64

What would the Christmas holidays be without some silly hacking? This year, I had this most random idea to try to write something for the Commodore 64, the result of which is available on GitHub.

I grew up on the C64 (I think I was 7 when we got one), but interestingly, I never got into the whole low-level programming thing. Instead, I started using the Graphics BASIC extension after growing out the built-in BASIC interpreter. So I never learned too much about the details of the 6510 CPU, or all the other driver chips like the SID or the VIC-II; but everyone knew even back then that you can't get anything serious done with the performance of BASIC interpreters.

These days, of course, you have very nice cross-compiler tools so you can get both the performance and the advantages of a somewhat-higher-level programming language. My idea for a project was to use the CC65 C cross-compiler to write a compiler for Brainfuck.

So after reading up on the 6502 processor family, it seemed very straightforward to implement the Brainfuck instructions by just storing the cell pointer in the X register and loading to / storing from the A register to do cell arithmetics. Of course, to get good performance, we compile bunches of the same Brainfuck instruction together, so e.g. +++ is compiled into

LDA mem,X ; 4 cycles
       CLC       ; 2 cycles
       ADC 3     ; 2 cycles
       STA mem,X ; 5 cycles

instead of the slower

INC mem,X ; 7 cycles
       INC mem,X
       INC mem,X

(see e.g. here for instruction timings).

So I wrote some C code that generates code like the above, machine code byte by byte. The only interesting part is compiling code for the [ and ] Brainfuck instructions. First of all, the 6502 only has conditional branch instructions for near jumps, whereas in Brainfuck the loop body can be arbirarily large. And second, since the compiler is to be on-line in the sense that it emits the machine code as it reads the Brainfuck source without ever holding the full source in memory (otherwise the source could take up too much of the already limited 64 kilobytes of memory), we have actually no idea when processing a [ how to jump over the loop. Because of these factors, the code I generate for [ is like this:

loop:  LDA mem,X
       BNE enter
       JMP $0000
enter: ... ; rest of the program

where the argument to the JMP instruction is zeroed out initially. We store the loop address in a stack in the compiler, and when we encounter the matching ], apart from emitting the code for JMP loop, we also edit loop+6 to store the current target address.

So that takes care of a traditional compiler. However, my compiler also has a transpiler mode, where it emits C64 BASIC from Brainfuck. Writing this was a lot of fun because I finally got to learn the details of how BASIC programs were stored on these low-powered home computers. Turns out programs were pre-tokenized line by line, so for example, the following line:

is stored as

So the variable name X% and number literals 10, 0 and 100 are stored as text, but the keywords IF, THEN, GOTO and the = operator are stored as single-byte identifiers. I think it's interesting that number literals are stored as text instead of numbers.

The overall structure of the BASIC transpiler is otherwise the same as the compiler. But typing LIST and seeing my generated BASIC code for the first time was so much more satisfying than looking at the generated machine code in the monitor.

In closing, here's a screencast of the program in action.