Colour Scheme

Rendering the Mandelbrot Set

6502 Assembly Version

While I was working on this mandelbrot rendering program, I was also working on my simple 65(c)02 webassembly-based virtual machine. Naturally then, when I was trying to pick something more computationally interesting to do on my VM, to display its power and my assembly knowledge, I fused the two ideas together!
Thus, I began the arduous journey to create the image you see above.

What's the big deal?

If you read the other article, where I explain the process of figuring out whether a pixel should be counted as part of the Mandelbro Set or not, this might sound like a fairly minor challenge. That is until you see the instruction set we're working with:

Screenshot from the very helpful www.masswerk.at

That's right. Add and subtract.
That's it.
And the accumulator is only 8 bits. Larger numbers need to be handled semi-manually. If I wanted to do multiplication (which I definitely needed for this fractal), I was going to have to implement it myself. Luckily, this is just the sort of stuff I love tinkering with, so I was very excited to learn about how to get this working.

I started by setting up an easy way to draw pixels to the screen. This was relatively easy, because I control how the console works, so I just added some of the unicode block characters (█, ▒, ▀, ▄, etc.) as special chars to the console, and made a small library that would designate a certain region of memory to be the framebuffer. Then, I could use the top and bottom half-block characters to represent single pixels, if that bit in the framebuffer was a 1.
Once that was working, I could move on to the actual hard part: getting rational numbers working on the 6502.

C Reference Implementation

The first thing I decided I would need was a reference implementation in a language I was more familiar with. So I quickly whipped up a simple emulation of the console's pixelated framebuffer using '##' for set pixels and got to making it actually produce an image. This also involved finding a reasonable viewport offset and zoom level to produce a nice picture. The zoom level is - of course - 16 so that the coordinate scaling can be achieved by shifting the bits right by 4.

Then I spent a while researching different methods and optimisations I could use to get it to work as I wanted, without taking an eon. Luckily, I already knew a bit about fixed-point arithmetic - the method I would use to get fractional values on the 6502. This simply involves setting an "imaginary" decimal point in a number to determine its scaling factor. This is essentially what you learn to do to store amounts of currency. Using floating-point for that could easily lead to slight imprecision errors, and would have been too slow to run on older machines anyway. That's why you just store an integer number of cents/pence/whatever and split it into separate units later. This can be done in binary as well. In my case I used 16-bit numbers where the top byte was the integer part, and the lower byte was the fractional amount.

In Decimal for currency:
  ¢ 2452 --> $ 24.52
In Binary:
  0x0100 --> 1.00
  0x0324 --> 3.14

Knuckling down in 6502 ASM

After that, I managed to dig up an old copy of a 6502 programming guide in the internet. This was probably one of my favourite moments in this project, because it was a true treasure-trove of old-school dev-wisdom and techniques to implement useful functions on that classic CPU. I'll spare you the long-winded details before this page turns into a novel, but in essence we're able to use a technique that's normally used in hardware multiplication. In a naïve approach, (for A * B) you might just add A to itself in a loop that runs B times. But by using some clever bit-shifts you only have to perform - at most - as many additions as there are bits in the number. In my case, I was using 16-bit numbers, so I knew the routine would only loop a maximum of 16 times. See the Wikipedia page on binary multiplication for more info.

Finally, I combined all the previously accrued knowledge and began writing the actual Mandelbrot program. At first I was going to have it work as it did in my other CPU-based Mandelbrot renderer, where it loops through all the pixels and tests up to some maximum number of iterations to check if it belongs in the set. This would also work for the 6502 version, but it would not be very interesting to look at. Especially since, when I first started the project, the VM had been only running at roughly 25kHz. Up until now this had been sufficient for "Hello, world" and the like, but now I really needed the speed. So, along with speeding up to VM to around 820kHz, I made the program only calculate one iteration for each pixel, and then to repeat this for the whole screen repeatedly until the desired iteration count was reached. This would have the effect of letting the user watch the image slowly become more refined over time.

After that was achieved, and with a lot of annoying little bugs located and dealt with, it was finally producing the correct image. So I polished it up a bit with a loading indicator and some log messages, to make sure you knew it was doing something, while it slowly chugged away at the calculations. I also added a few obvious optimisations, like skipping part of the first iteration, because all the values start as 0, and checking the framebuffer to see if we've already discarded this pixel, before running the calculations again.

It was certainly a happy moment when I finally found the last little issue and watched it churn out a very pixelated Mandelbrot.

Back to Main Page