A great old-timey game-programming hack (2013)

Comments

A long time ago, when I was a college undergrad, I spent some time working on computer video games. This was in the 8-bit PC era, when the gaming hardware was almost impossibly slow by today’s standards.

It might not surprise you, then, to learn that game programmers of yore did all sorts of crazy things to make their games run at playable speeds. Crazy, crazy things. This is a story about one of those things.

While I’ve done my best to recall the important details, I may have gotten some things wrong. If I have, please forgive me. It was a long time ago.

(Note: This post contains some small images as inline-data URLs that some feed readers apparently don’t handle well. If you can’t see the images in your feed, click through to the original article to see them.)

Update 2013-12-16: There have been lots of great comments about this story on Hacker News and Proggit, as well as here on the blog. Thanks for sharing, everyone!

The set-up

A friend of mine, a gifted programmer, was nearly finished with a new game. Somehow, he had squeezed into a 1980’s-era PC, pretty faithfully, what was at the time a graphically impressive coin-op game popular at the arcades.

The only problem was that his version of the game was unplayable. It was too slow, and the choppy motion broke the player’s immersion. It was after all a side-scroller.

My friend, who had been working on the game while also taking a full load of college courses, was starting to seem a little frazzled. Fearing that he had missed some easy optimization, he asked me to take a look at the code. I did.

But there was no easy optimization to be had. The code was tight. Everywhere I looked, he had already done all the things I could think of. Loops had been unrolled. Unneeded draws had been eliminated. All evidence of waste had vanished. And, with them, our hopes of an easy fix.

But what about a hard fix? A crazy fix? Well, that was always a possibility.

Before I get to the crazy stuff, however, I should back up and explain how graphics hardware worked back then.

How graphics hardware worked back then

Here’s the quick version: The graphics hardware didn’t do jack squat. On the PC in question, if you wanted to draw something onto the screen, you had to do that yourself, byte by byte. No texture mappers, no blitters. Just bytes. Bytes that you had to move yourself. Fun.

My friend’s game spent most of its time redrawing the background. (Again: side-scroller.) For every frame, it had to draw nearly a screen’s worth of background tiles, shifted for the player’s position.

If my memory serves me, each tile was 28 by 28 pixels. Each pixel was one of 16 colors, taking half a byte to represent. Therefore, tiles were represented in memory as 28 contiguous rows of 14 bytes each. The first 14 bytes represented the first row, the second 14 bytes the second row, and so on.

The screen, however, was 320 pixels wide by 240 pixels high. In memory, then, a screen buffer was laid out as 240 contiguous rows of 160 bytes each.

So when copying a tile at address X onto a screen buffer location starting at address Y, you had to copy 28 rows. To copy each row, you had to copy 14 bytes.

Fortunately, the processor for this game was a 6809, which had a few 16-bit index registers and delightful “auto-increment” addressing modes (sort of like applying the postfix ++ operator to pointers in C). That meant you could copy 4 pixels at a time while advancing both the X and Y registers in passing:

LDU ,X++ ; read a 2-byte word (= 4 pixels) from source tile
STU ,Y++ ; write it to screen buffer

To copy a full row, you had to do that seven times, so you might sandwich those lines within a 7-count loop:

LDB #7 ; remaining words

+---+---+ =======> +---+---+ | c d | reverse | a b | swap | b a | +---+---+ rows +---+---+ septets +---+---+ +---+---+---+---+ +---+---+---+---+ +---+---+---+---+ | a b | c d | | c d | a b | | d c | b a | +---+---+---+---+ +---+---+---+---+ +---+---+---+---+

So the solution to the mangling problem turned out to be a simple, one-time pre-processing step: Just break each tile into septets and reverse their order.

Knowing that the mangling problem could be solved, I was feeling good about my overall idea. I couldn’t see any other problems, so I sketched out a new copy-tile subroutine to present to my friend. Since the row-copy logic was now just 5 instructions, I used it 4 times, unrolling the sole remaining loop a bit. Now, instead of copying 28 single rows, I copied 7 quad-rows.

The code looked something like this:

COPYTILE3
;;; Copy a 28x28 screen tile into a screen buffer.
;;; Arguments:
;;; X = starting address of *septet-reversed* background tile
;;; Y = starting address of destination in screen buffer
;;; Execution time:
;;; 34 + 7 * (224 + 7 + 3) + 7 + 10 = 1689 cycles
;; setup: 34 cycles
PSHS U,DP ; save U and DP (8 cycles)
STS >SSAVE ; save S (7 cycles)
LDA #TILH/4 ; initial quad-row count (2 cycles)
STA >ROWCT ; (5 cycles)
LEAS ,X ; initialize src ptr (4 cycles)
LEAU (TILH-1)*SCRW+TILW,Y ; initialize dst ptr (8 cycles)
;; @COPY1
;; copy four rows of 28 pixels in 4 * (48 + 8) = 224 cycles
PULS X,Y,D,DP
PSHU X,Y,D,DP
PULS X,Y,D,DP
PSHU X,Y,D,DP
LEAU -WOFF,U
PULS X,Y,D,DP
PSHU X,Y,D,DP
PULS X,Y,D,DP
PSHU X,Y,D,DP
LEAU -WOFF,U
PULS X,Y,D,DP
PSHU X,Y,D,DP
PULS X,Y,D,DP
PSHU X,Y,D,DP
LEAU -WOFF,U
PULS X,Y,D,DP
PSHU X,Y,D,DP
PULS X,Y,D,DP
PSHU X,Y,D,DP
LEAU -WOFF,U
;; DEC >ROWCT ; reduce remaining quad-row count by one (7 cycles)
BNE @COPY1 ; loop while quad-rows remain (3 cycles)
;; LDS >SSAVE ; restore S (7 cycles)
PULS U,DP,PC ; restore regs and return to caller (10 cycles)
SSAVE ZMD 1 ; stash for saving S while drawing
ROWCT ZMB 1 ; var: remaining rows to copy

Adding up the cycles, the total was just 1689. I had shaved almost 1200 cycles off of my friend’s code. That’s a 70 percent speed-up! Beaming, I went to show my friend.

The acid test

When I caught up with my friend and said I’d figured out how to make the copy-tile routine 70% faster, his face lit up. When I explained about the whole septets-and-mangling thing, though, his face unlit, doubts rising. But when I showed him the code, he got it. It clicked. “Let’s try it out!” he said.

In about a half hour’s work, he had the code integrated into the game. After a rebuild and reboot, the game was loading. The title screen came up. He was into the game. And . . . Holy crap! The game seemed amazingly fast.

In truth, it was probably only a third to a half faster, but that was enough. Some important perceptual threshold had been crossed. The game-play was now smooth, natural. You could feel the difference.

We just sat there, playing the game and grinning. It was a good day. But it would not last.

In for a penny . . .

A few days after the speed problem was behind us - or so we thought - the game’s finishing touches were applied. One of those finishing touches was sampled sound effects. This required feeding byte-sized morsels to the audio-output DAC a few thousand times each second. To schedule the feedings, my friend had turned on a hardware-clocked interrupt. Worked like a charm. The sounds sounded great, and everything was perfect. Except for one thing.

After playing into the game one night, we noticed that some of the tiles were getting corrupted. The more we played, the more corruption we saw. Oh, no. Something very bad was happening.

And then it hit us. What happens if an interrupt goes off during the copy-tile routine? The processor, to prepare for calling the interrupt handler, would push its current state onto the system stack. But, during the copy-tile routine, there was no system stack. The system-stack register S had been commandeered. And where was it pointing? Right into the memory buffer that held the reference tiles! Oops.

We slumped. After all that effort, to think that our all-important speed-up was causing memory corruption… Needing a break, we walked to an all-night diner near campus to eat and think. Over pancakes and bacon, scrapple and grilled stickies, we talked through the problem.

There were only two stack registers, and without commandeering both of them, the copy-tile routine wouldn’t be nearly as fast. There was no way, then, to return the S register to the system without losing our hard-won speed. But there was also no way that we could get reliable sound without using interrupts.

One way or another, then, interrupts were going to be triggered. And, when they were, if copy-tile was running, whatever S was pointing to was going to get hammered.

“How can we prevent the corruption?” I asked. We sat there, ignoring our food, the question hanging in the air.

Suddenly, my friend slapped the table. He had it. “Don’t prevent it!” he said. “What?” I asked. “Don’t prevent the corruption,” he explained. “Let it happen. Just not to the reference tiles.”

It was simple, really. He continued: “Just swap S and U in the copy-tile routine. U will point at the reference tiles, and S at the screen buffer. If an interrupt goes off, the corruption will happen where S is pointing - on the screen. The corruption will last only until we redraw the next frame.”

“That’s brilliant!” I said. Eager to try his solution, we quickly finished our meal. . . .

In for a pound

Walking back to the dorms, though, it bothered us that players might see screen glitches, even if for just a frame. We both felt that there had to be some way to make the hack perfect, if only we could find it. Later that night, we found it.

Again, it was simple once we saw it. All we had to do was change the tile ordering. Instead of placing the tiles onto the screen from top to bottom, left to right, we would go right to left, bottom to top. In other words, from high addresses to low addresses.

That way, when an interrupt went off and corrupted the memory locations immediately before the tile we were currently drawing, the corruption would be fixed when the very next tile was drawn. And since tile-drawing took place in a buffer that wasn’t displayed until it was fully drawn (and the vertical refresh had occurred), nobody would ever see the corruption.2

It was the perfect hack!

To the old days!

And that’s the way things were. The challenge wasn’t overwhelming complexity, as it is today. The challenge was cramming your ideas into machines so slow, so limited that most ideas didn’t fit. You had to bang your ideas around, twist them, turn them, searching for something, anything that would help you squeeze them into the machine. Sometimes you found it, and you got one step closer to realizing your ideas. Sometimes you didn’t. But the search was always instructive.

In this case, the search yielded several small victories that, together, solved the problem. But when you consider all the things we had to do to make that darn game fast enough, it does seem crazy.

We started with a tile-copying subroutine whose core was a hand-tuned, unrolled loop of machine instructions. Then, to buy a 70-percent speed-up:

• We replaced this subroutine with a very special manifestation of insanity that commandeered both stack pointers and used pulls and pushes, and every single available register, to draw tiles upside down and horizontally broken.
• Then we pre-processed the tiles so that drawing them would actually fix them.
• But then - dammit! - interrupts that occurred during drawing could corrupt the reference tiles.
• So, to protect the reference tiles, we corrupted the screen buffer instead.
• But that corruption would be visible.
• So we changed the tile-placement order to repair - on the fly - any corruption that might have occurred, before it could ever be displayed.
• And it all worked!

We did that. For 70 percent. And it was so worth it.

Tell ’em if you got ’em

Anyway, I wanted to share that story with you for two reasons. The first is that it’s a fun story. It’s one my earliest memories of struggling with a messy computing problem and, through dogged persistence, zeroing in on a solution that was both effective and elegant. The result was powerfully satisfying. The struggle, I learned, is worth it.

The second reason is to encourage you to tell your stories. I know that, “back in the day,” most video games probably gave rise to many stories like this one. I’d love to hear them. But too many of them are lost, having faded out of memory before anyone thought to preserve them. If you have a story, please don’t wait. Tell it. Every day you wait, it gets harder. Tell it.

Exercise: Prove that for all finite sequences of finite sequences, applying (reverse ⋅ concat) is the same as applying (concat ⋅ reverse ⋅ map reverse).↩︎

We also had to make sure that nothing valuable was stored in the memory locations just before a screen buffer. They could, in theory, also be corrupted if an interrupt occurred while placing the top-left septet of the top-left corner tile. This septet’s address corresponded to the start of the buffer.↩︎