One of the big advantages of home computers in the early 1980s over their console counterparts was that they usually had some form of bitmap mode—a graphics mode that grants control over each pixel individually. The alternatives generally involved character or tile graphics, where a set of predefined patterns are assembled in a grid to produce a screen. This approach is much faster and allows for more efficient use of memory, and it also meshes better with text modes. Each letter gets its own tile and the layout of tiles corresponds to a text screen. Every system we’ve looked at on this blog, with the exception of the ZX Spectrum, has some kind of text or tile mode. The Spectrum only provides a bitmap mode, and it prints text by copying letters out of its character generator ROM into the bitmap as if they were 8×8 sprites.
Sometimes the boundary between the two is fuzzy. When we did our rescue of Mandala Checkers on the ZX81, we made use of its predefined characters to produce something like a very low-resolution bitmap (a technique often called semigraphics). When experimenting with the PC’s CGA card, we warped the text mode so severely that we actually got a relatively credible 16-color graphics display out. When we looked at the graphics on the Sega Genesis, we found that it relied entirely on tile-based graphics but it also provided so many tiles that we were able to produce the equivalent of a bitmapped display with it.
The C64 has a programmable character mode like the consoles of its era—we’ve used it in the past to experiment with custom fonts—but it also provides a bitmap mode. This bitmap mode turns out to more or less be an automated version of the technique we used on the Genesis—the 320×200 screen is organized as a 40×25 grid of a thousand 8×8 cells. Each cell is specified by 8 bytes, each of which represents a single row in the 8×8 character space, much like it would in a custom character set definition.
This produces a deeply weird memory layout compared to the bitmapped framebuffers we’ve seen on the PC or the Apple II. The first byte represents the top row pixels 0-7, but then pixels 8-15 are byte 8, and 16-23 are byte 16, and so on up to the right edge, where pixels 312-319 are represented by byte 312. When we begin the next row of pixels, we use bytes 1, 9, 17, and so on up to 313. This continues until the 8th row of pixels, which repeats the pattern again starting at byte 320. Even then, that’s only enough to narrow down your location to 8 pixels. The 8 bits of the byte then correspond to each one pixel, with the larger pixels representing pixels further to the left (so, the leftmost pixel is the 128 bit, and the rightmost one is the 1 bit). The Commodore 64 Programmer’s Reference Guide provides a master formula for setting a pixel in BASIC (assuming the bitmap is at $2000
, which is the usual place to put it in small programs):
BYTE=8192+INT(Y/8)*20+INT(X/8)*8+(Y AND 7)
POKE BYTE, PEEK(BYTE) OR 2^(7-(X AND 7))
That is quite a bit of math, and it includes several multiplications that the 6502 chip will not do for us. There is also the delightful quality that properly specifying an X coordinate requires a 9-bit integer. My old bitmap library managed all this as directly as possible, and it could handle initialization and pixel control with a footprint of only 168 bytes, but it was quite slow.
It’s usually possible to trade space for time, though. With 64KB of RAM, we don’t have to be quite as stingy as we have been.
The Goal
I started looking into this because my old bitmap library wasn’t good enough to support the Simulated Evolution program from back in April. I had two problems with it: it was way too slow, and it wouldn’t be able to draw the displays we needed anyway.
Normally, the C64’s bitmap mode is a 320×200 display, and within each 8×8 cell we may only use two colors: a foreground and a background. This follows inevitably from the fact that we’re only using one bit for each pixel. However, we need to be able to draw three colors with complete freedom to draw the Simulated Evolution screen: white for the bugs, green for the plankton, and blue for the background. Fortunately, the C64 has an alternate mode (multicolor mode) where the resolution drops to 160×200 but this menas that we now have two bits of data per pixel. This lets us do what we wish and also lets us preconfigure the whole screen to just use the colors we want.
Unfortunately, it also makes setting any given pixel rather trickier. We need to set two bits, but depending on the color we wish to set, we may have to set the pixels to different values, and that means performing more complicated bitmasking operations. As part of our operation we’d like to pay as little extra cost as possible when doing this.
The Strategy
The work that’s costing us the most time is the multiplication and bit rotation operations that let us actually find the correct offset into our bitmap. The most expensive part of that is the Y coordinate; most of the X coordinate math ends up cancelling out neatly and turning into simple bitmasking operations. (As an added bonus, now that we’re working with a 160×200 screen, our X coordinates fit into an 8-bit register again, and for those operations that need to treat it as a 9-bit value, the carry bit was custom-built for this very purpose!)
The most direct way to make an attack on the multiplications and bitmasking operations that we need for the Y coordinate is simply to not do them. With 200 possible pixel rows, we can simply precompute the start of each row of pixels and store them in RAM. That turns a lot of math into a single 16-bit table lookup. Similarly, we may create some tables to make it easier to translate the residual bit of the X coordinate into the bitmasks we’ll need to use to get our multicolor results.
Our tables definitely multiply the size of our code, though: we’ve expanded our memory footprint from 168 bytes to 703. On the plus side, the actual program size on disk is only 300 bytes or so, so we haven’t quite doubled our program size when it comes to loading time.
Continue reading →