{"article":{"slug":"a-great-old-timey-game-programming-hack","title":"A Great Old-Timey Game-Programming Hack","subtitle":null,"summary":"Tom Moertel recalls an 8-bit era 6809 assembly trick for drawing game graphics fast enough on painfully slow hardware, abusing the stack pointer to blast tiles into the screen buffer, and urges engineers to tell their old stories.","content_type":"blog_post","language":"en","canonical_url":"https://blog.moertel.com/posts/2013-12-14-great-old-timey-game-programming-hack.html","author":{"name":"Tom Moertel","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Tom Moertel's Blog","url":"https://blog.moertel.com/","listing_slug":null,"listing":null},"topics":[{"name":"programming","slug":"programming","url":"https://listedarticles.com/topics/programming"},{"name":"history","slug":"history","url":"https://listedarticles.com/topics/history"},{"name":"performance","slug":"performance","url":"https://listedarticles.com/topics/performance"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":4667,"reading_minutes":20,"published_at":"2013-12-14T00:00:00.000Z","added_at":"2026-11-11T02:08:19.579Z","updated_at":"2026-11-11T02:08:19.579Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/a-great-old-timey-game-programming-hack","markdown_url":"https://listedarticles.com/articles/a-great-old-timey-game-programming-hack.md","example":false,"citation":"Tom Moertel, Tom Moertel's Blog. \"A Great Old-Timey Game-Programming Hack.\" 14 Dec 2013. https://blog.moertel.com/posts/2013-12-14-great-old-timey-game-programming-hack.html (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://blog.moertel.com/posts/2013-12-14-great-old-timey-game-programming-hack.html"},"body_markdown":"# A Great Old-Timey Game-Programming Hack\n\nBy\n[Tom Moertel](https://blog.moertel.com/about.html)\n\nPosted on December 14, 2013\n\nTags: [assembly](https://blog.moertel.com/tags/assembly.html \"All pages tagged 'assembly'.\"), [6809](https://blog.moertel.com/tags/6809.html \"All pages tagged '6809'.\"), [games](https://blog.moertel.com/tags/games.html \"All pages tagged 'games'.\"), [hacks](https://blog.moertel.com/tags/hacks.html \"All pages tagged 'hacks'.\")\n\nA long time ago, when I was a college undergrad, I spent some time working on computer video games.\nThis was in the 8-bit PC era, when the gaming hardware was almost impossibly slow by today’s standards.\n\nIt 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.\nCrazy, crazy things.\n\nThis is a story about one of those things.\n\nWhile I’ve done my best to recall the important details, I may have gotten some things wrong.\nIf I have, please forgive me.\nIt was a long time ago.\n\n(*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.*)\n\n*Update 2013-12-16: There have been lots of great comments about this story on [Hacker News](https://news.ycombinator.com/item?id=6913467) and [Proggit](http://www.reddit.com/r/programming/comments/1t05uy/a_great_oldtimey_gameprogramming_hack/), as well as [here on the blog](http://blog.moertel.com/posts/2013-12-14-great-old-timey-game-programming-hack.html#disqus_thread). Thanks for sharing, everyone!*\n\n### The set-up\n\nA friend of mine, a gifted programmer, was nearly finished with a new game.\nSomehow, 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.\n\nThe only problem was that his version of the game was unplayable.\nIt was too slow, and the choppy motion broke the player’s immersion.\nIt was after all a side-scroller.\n\nMy friend, who had been working on the game while also taking a full load of college courses, was starting to seem a little frazzled.\nFearing that he had missed some easy optimization, he asked me to take a look at the code.\n\nI did. But there was no easy optimization to be had.\n\nThe code was *tight*.\nEverywhere I looked, he had already done all the things I could think of.\nLoops had been unrolled.\nUnneeded draws had been eliminated.\nAll evidence of waste had vanished.\n\nAnd, with them, our hopes of an easy fix.\n\nBut what about a hard fix?\nA crazy fix?\n\nWell, that was always a possibility.\n\nBefore I get to the crazy stuff, however, I should back up and explain how graphics hardware worked back then.\n\n### How graphics hardware worked back then\n\nHere’s the quick version:\nThe graphics hardware didn’t do jack squat.\n\nOn the PC in question, if you wanted to draw something onto the screen, you had to do that yourself, byte by byte.\nNo texture mappers, no blitters.\nJust bytes.\nBytes that you had to move yourself.\n\nFun.\n\nMy friend’s game spent most of its time redrawing the background.\n(Again: side-scroller.)\nFor every frame, it had to draw nearly a screen’s worth of background tiles, shifted for the player’s position.\n\nIf my memory serves me, each tile was 28 by 28 pixels.\nEach pixel was one of 16 colors, taking half a byte to represent.\nTherefore, tiles were represented in memory as 28 contiguous rows of 14 bytes each.\nThe first 14 bytes represented the first row, the second 14 bytes the second row, and so on.\n\nThe screen, however, was 320 pixels wide by 240 pixels high.\nIn memory, then, a screen buffer was laid out as 240 contiguous rows of 160 bytes each.\n\nSo when copying a tile at address *X* onto a screen buffer location starting at address *Y*, you had to copy 28 rows.\nTo copy each row, you had to copy 14 bytes.\nFortunately, 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).\nThat meant you could copy 4 pixels at a time while advancing both the *X* and *Y* registers in passing:\n\n```\n    LDU ,X++     ; read a 2-byte word (= 4 pixels) from source tile\n    STU ,Y++     ; write it to screen buffer\n```\n\nTo copy a full row, you had to do that seven times, so you might sandwich those lines within a 7-count loop:\n\n```\n    LDB #7       ; remaining words <- tile width in words\n@LOOP\n    LDU ,X++     ; read a 2-byte word (= 4 pixels) from source tile\n    STU ,Y++     ; write it to screen buffer\n    DECB         ; reduce remaining-word count\n    BNE @LOOP    ; loop while words remain\n```\n\nWhen you were done copying the row, you needed to advance the destination pointer *Y* so that it pointed to the starting address for the next row you would draw into the screen buffer.\nSince the screen buffer was 160 bytes wide and a tile was only 14 bytes wide, that meant you had to add their difference to *Y*:\n\n```\n    LEAY 160-14,Y\n```\n\nAnd, just like that, you have copied a row onto the screen.\n\nThat’s one.\nTo copy a full tile, you need to do the same thing 28 times.\nSo, in turn, you sandwich *that* code within a 28-count loop.\n\nPutting it all together, and giving names to the important numbers, you might end up with a subroutine like this:\n\n```\n;;; important constants\n\nSCRW = 160          ; screen-buffer width in bytes (= 320 4-bit pixels)\nTILW =  14          ; background-tile width in bytes (= 28 4-bit pixels)\nTILH =  28          ; background-tile height in rows\nWOFF = SCRW - TILW  ; s-b offset from end of one tile row to start of next\n\nCOPYTILE\n;;;\n;;; Copy a 28x28 background tile into a screen buffer.\n;;; Arguments:\n;;;   X = starting address of background tile\n;;;   Y = starting address of destination in screen buffer\n;;;\n    LDA #TILH               ; remaining rows <- tile height\n@COPYROW\n    LDB #TILW/2             ; remaining words <- tile width in words\n@LOOP\n    LDU ,X++                ; read a word (= 4 pixels) from source tile\n    STU ,Y++                ; write it to screen buffer\n    DECB                    ; reduce remaining-word count\n    BNE @LOOP               ; loop while words remain\n    ;;\n    LEAY WOFF,Y             ; advance dst ptr to start of next dst row\n    DECA                    ; reduce remaining-row count\n    BNE @COPYROW            ; loop while rows remain\n    ;;\n    RTS                     ; done! return to caller\n```\n\nAnd that code would be fine.\n\nIf you didn’t care about speed.\n\n### Caring about speed\n\nKnowing that the game is probably going to spend most of its time running that code, you do what any good programmer would: start counting cycles.\nHere’s the inner loop again, with setup and finishing, annotated with cycle counts:\n\n```\n    LDB #TILW/2             ; 2 cycles (set-up)\n@LOOP\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    DECB                    ; 2\n    BNE @LOOP               ; 3\n    ;;\n    LEAY WOFF,Y             ; 8 (finishing)\n```\n\nLooking at those counts within the loop, you’re not likely to miss that you’re burning 21 cycles to copy just 4 pixels.\nTo copy a full row, then, works out to 2 cycles + (7 iterations) \\* (21 cycles/iteration) + 8 cycles = 157 cycles.\nOuch.\n\nBut this isn’t your first time at the keyboard.\nYou know what to do.\nUnroll that loop!\n\n```\n    LDU ,X++                ; 8 cycles\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LEAY WOFF,Y             ; 8 (finishing)\n```\n\nNow, with the loop overhead reduced to zero – you’ve even eliminated the set-up – each row takes only 7 \\* (8 + 8) + 8 = 120 cycles.\nThat’s a 30-percent speed-up.\nPretty good.\n\nAnd that’s where most programmers probably would have left it.\n\nBut not my friend.\n\nHe knew that those `++` operations were costly, 3 cycles apiece.\nAnd, with the loop unrolled, he also knew exactly where each word to be read or written was located with respect to *X* or *Y*.\nSo he cleverly replaced those 3-cycle post-increments with exact offsets.\nThey cost only 1 cycle apiece, and the 0 offset is actually free:\n\n```\n    LDU  ,X                 ; 5 cycles\n    STU  ,Y                 ; 5\n    LDU 2,X                 ; 6\n    STU 2,Y                 ; 6\n    LDU 4,X                 ; 6\n    STU 4,Y                 ; 6\n    LDU 6,X                 ; 6\n    STU 6,Y                 ; 6\n    LDU 8,X                 ; 6\n    STU 8,Y                 ; 6\n    LDU 10,X                ; 6\n    STU 10,Y                ; 6\n    LDU 12,X                ; 6\n    STU 12,Y                ; 6\n    LEAX TILW,X             ; 8 (finishing)\n    LEAY SCRW,Y             ; 8 (finishing)\n```\n\nWith his optimizations, the cycle count per row had been reduced to (5 + 5) + 6 \\* (6 + 6) + (8 + 8) = 98 cycles.\nCompared to the original code, that’s 60 percent faster:\n\n```\noriginal_speed  = (1*row) / (157*cycle)\noptimized_speed = (1*row) /  (98*cycle)\n\nspeed_up  =  optimized_speed / original_speed - 1  =  157 / 98 - 1  =  0.60.\n```\n\nPutting it all together – and, again, I’m going by memory so the code might have been slightly different – the copy-tile subroutine looked something like this, and it copied a full tile, all 28 rows, in a lean 2893 cycles:\n\n```\nCOPYTILE2\n;;;\n;;; Copy a 28x28 screen tile into a screen buffer.\n;;; Arguments:\n;;;   X = starting address of background tile\n;;;   Y = starting address of destination in screen buffer\n;;; Execution time:\n;;;   4 + 28 * (82 + 8 + 8 + 2 + 3) + 5 = 2893 cycles\n;;;\n    LDA #TILH      ; initialize row count (4 cycles)\n    ;;\n@COPY1\n    ;; unroll inner loop (copies one row of 28 pixels in 82 cycles)\n    LDU ,X         ; (1) read 4 pixels (5 cycles)\n    STU ,Y         ;     write 4 pixels (5 cycles)\n    LDU 2,X        ; (2) (6 cycles)\n    STU 2,Y        ;     (6 cycles)\n    LDU 4,X        ; (3) ...\n    STU 4,Y        ;     ...\n    LDU 6,X        ; (4)\n    STU 6,Y        ;\n    LDU 8,X        ; (5)\n    STU 8,Y        ;\n    LDU 10,X       ; (6)\n    STU 10,Y       ;\n    LDU 12,X       ; (7)\n    STU 12,Y       ;\n    ;;\n    LEAX TILW,X    ; advance src to start of next row (8 cycles)\n    LEAY SCRW,Y    ; advance dst to start of next row (8 cycles)\n    DECA           ; reduce remaining count by one (2 cycles)\n    BNE @COPY1     ; loop while rows remain (3 cycles)\n    ;;\n    RTS            ; done!  return to caller (5 cycles)\n```\n\nThis code, all in all, was 60% faster than the naive `COPYTILE` code we started out with.\n\nBut that wasn’t fast enough.\nNot nearly.\n\nSo when my friend showed me his code and asked if I could make it faster, I really wanted to help him.\nI really wanted to be able to answer yes.\n\nBut I had to answer no.\nI hated giving that answer.\nBut, studying the code, I couldn’t see any way to speed it up.\n\nAnd yet, the hook was set.\n\nLater, I couldn’t get the problem out of my head.\nMaybe I had missed something.\nI had grown up on Apple II computers and their 6502 processors.\nMy friend’s code, however, was for the 6809.\nMaybe it afforded optimizations that I didn’t know about.\n\nWith renewing optimism, I dialed into the university’s library to access the card catalog.\n(These were the days before the World Wide Web.)\nThrough a VT220 terminal emulator, I searched for books about the 6809.\n\nThere was one.\nA 6809 microprocessor manual.\nIt was in the engineering library.\nLuckily, I was an engineering student and had sign-out privileges.\n\nJust like that, I was off to the library.\n\n### A crazy idea\n\nWhen I got to the engineering library, I found the book right where it was supposed to be, looking a little beat up:\n\n[*The MC6809-MC6809E Microprocessor Programming Manual*](https://archive.org/details/bitsavers_motorola68_13419254/mode/2up).\n\nNot bothering to find a chair, I flipped through the pages standing, looking for some oddball, 6809-specific instruction that might throw a lot of bytes and throw them fast.\nPage after page, though, turned up nothing.\n\nThen I came upon [PSHS](https://archive.org/details/bitsavers_motorola68_13419254/page/n99/mode/2up?q=pshs).\n“Push registers on the hardware stack.”\n\nOn my beloved 6502, if you wanted to save registers on the stack, you had to do it one register at a time and, even then, by transferring them through the accumulator.\nIt was slow and expensive.\nSo I had learned to avoid the stack when speed mattered.\n\nBut on the 6809 you could save *all* of the registers – or any subset of them – with *a single instruction*.\nAnd, amazingly, it cost a mere 5 cycles, plus 1 cycle more per byte pushed.\n\nSince the processor had three 16-bit general-purpose registers – *D*, *X*, and *Y* – I could load them up and then use a single `PSHS` instruction to write 6 bytes in just 11 cycles.\nThe corresponding pull instruction, [`PULS`](https://archive.org/details/bitsavers_motorola68_13419254/page/n101/mode/2up?q=puls), had the same low cost.\n\nFurther, the 6809 had *two* stack registers, *S* and *U*.\nI could use one as a source pointer and the other as a destination pointer.\nIn theory, with a single `PULS`/`PSHU` pair, I could copy 6 bytes in 22 cycles.\n\nThat’s crazy, crazy fast.\n\nExcitement mounting, I headed for the front desk and reached for my student ID.\nI was going to sign out that wonderful little book for further study.\n\n### A crazy plan\n\nWalking back to the dorms, I formed my plan.\n\nI would save the *S* and *U* registers somewhere, and then point *S* at the background tile and *U* at the screen buffer.\nThen I would pull from *S* and push to *U*, copying 6 bytes at a time, using *D*, *X*, and *Y* as go-betweens.\nTo copy the 14 bytes that make up a row would require three such iterations, which unrolled would be about 60 cycles.\n\nWhen I reached my room, I found a piece of paper and sketched it out:\n\n```\n    PULS D,X,Y    ; first 6 bytes    11 cycles\n    PSHU D,X,Y    ;                  11\n    PULS D,X,Y    ; second 6 bytes   11\n    PSHU D,X,Y    ;                  11\n    PULS D        ; final 2 bytes     7\n    PSHU D        ;                   7\n    LEAU -WOFF,U  ; advance dst ptr   8\n```\n\nJust 66 cycles, including the after-row adjustment to *U* that prepares it for the next row.\n(Note that the adjustment is now negative.)\nFor comparison, the naive row-copy loop that we looked at earlier took 157 cycles to do the same thing.\nAnd my friend’s optimized code took 98.\nAlready, this crazy idea was looking like a big win.\n\nStill, that last `PULS`/`PSHU` pair!\nWhat a clunker.\nIt was needed to handle the final two bytes per row, since the rows were 28 pixels = 14 bytes wide, and 6 doesn’t divide 14 evenly.\n\n*That darn remainder of 2 bytes!*\n\nIf only the game had used 24-by-24 tiles instead…\nBut it hadn’t, so I pored through the manual, looking for a way to lower the cost of that inevitable last pair.\n\nAnd then, by surprise, I struck gold!\nIt was another 6809 oddity, the *DP* register.\n\nOn the 6502 and most 8-bit processors of the era, the lowest 256 bytes of memory was called the *zero page*.\nThe zero page was special because its memory locations had single-byte addresses and could be accessed with shorter and usually faster instructions.\n\nThe 6809’s designers took this idea one step further.\nThey let you use the *DP* register to designate *any* page as the zero page, which they called the “direct page.”\n\nBut none of my byte-slinging instructions needed to use the direct page.\nThat meant I could use the *DP* register as an additional one-byte go-between.\nNow I could copy 7 bytes per pull-push pair!\n\nAnd 14 *is* evenly divisible by 7.\n\nWith this change, I could copy a whole 28-pixel row and advance to the next in just 5 instructions:\n\n```\n    PULS D,X,Y,DP  ; first 7 bytes    12 cycles\n    PSHU D,X,Y,DP  ;                  12\n    PULS D,X,Y,DP  ; second 7 bytes   12\n    PSHU D,X,Y,DP  ;                  12\n    LEAU -WOFF,U   ; advance dst ptr   8\n```\n\n56 cycles!\nFifty. Six. Cycles.\n\nThat bit of code made me feel just *awesome*.\nI had managed to harness every single available register on the machine for byte-slinging!\n*D*, *X*, *Y*, *U*, *S*, and even the oddball *DP* – they were all fully engaged.\n\nI was feeling great about this solution.\n\nExcept for just one thing…\n\n### I’ll have a little more crazy, please\n\nIf you’re acquainted with stacks, you may have noticed a subtle flaw in my brilliant plan:\n\n*Pushes and pulls work in opposite directions.*\n\nSee, I lied about that little block of code I just showed you.\nIt didn’t *actually* copy one row from a background tile onto the screen.\nWhat it actually did was break the row into two 7-byte blocks – I’ll call them “septets” – and then draw them onto the screen *swapped*.\n\nRecall that tile rows were laid out sensibly in memory as 14 contiguous bytes, like this:\n\n```\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n| 0   1   2   3   4   5   6   7   8   9   A   B   C   D |\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n```\n\nSo when you pulled-and-pushed a row onto the screen in 7-byte septets, it would get horizontally split like this:\n\n```\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n| 7   8   9   A   B   C   D | 0   1   2   3   4   5   6 |\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n```\n\nThe first septet was now second, and the second now first.\nNote, however, that the bytes within each septet were unchanged; they retained their original ordering.\n\nFurther, if you ran the row-copy code multiple times, the vertical stack of rows you copied would end up being upside down.\nThat’s because the code uses pushes to write the rows onto the screen.\nPushes move the stack pointer toward lower addresses, and lower addresses correspond to screen lines higher up on the display.\n\nTo visualize the havoc that this row-reversal and septet-swapping would wreak, let’s say that you had the following 28-by-28 tile, representing a key:\n\nIf you had used 28 applications of my row-copy code to draw it onto the screen, you would have ended up with this not-a-key:\n\nSo . . . *that* was a problem.\n\nBut this problem, too, had an elegant solution!\n\nTo review:\n\n- the rows were upside down\n- the septets within each row were swapped\n- but the bytes within each septet were unchanged\n\nThe breakthrough was to see “upside down” and “swapped” as two instances of the same thing. *Reversal.*\n\nReversal has this handy property: it’s an [*involution*](http://en.wikipedia.org/wiki/Involution_(mathematics)).\nReverse something twice, and you get back the original.\nWith this in mind, I reasoned that if the tiles were pre-processed to reverse their rows and then the septets within the rows, the tiles would end up looking fine when they hit the screen.\nThe mangling that occurred during copying and pre-processing would, in effect, undo each other.\n\nWorking it out on paper, I also discovered that the pre-processing step could ignore the rows and just treat the tiles as one long, linear sequence of septets.[1](#fn1)\nTo see why this is so, let’s consider a small tile of 2 rows of 2 septets each:\n\n```\n+---+---+\n| a   b |\n+---+---+\n| c   d |\n+---+---+\n```\n\nIn memory, it would be laid out in row-major order, that is, as 4 sequential septets:\n\n```\n+---+---+---+---+\n| a   b | c   d |\n+---+---+---+---+\n```\n\nSo, reversing the rows and then swapping the septets within each row is the same as just reversing the septet order in memory:\n\n```\n+---+---+                  +---+---+                  +---+---+\n| a   b |                  | c   d |                  | d   c |\n+---+---+        =======>  +---+---+        =======>  +---+---+\n| c   d |        reverse   | a   b |        swap      | b   a |\n+---+---+        rows      +---+---+        septets   +---+---+\n\n+---+---+---+---+          +---+---+---+---+          +---+---+---+---+\n| a   b | c   d |          | c   d | a   b |          | d   c | b   a |\n+---+---+---+---+          +---+---+---+---+          +---+---+---+---+\n```\n\nSo the solution to the mangling problem turned out to be a simple, one-time pre-processing step:\nJust break each tile into septets and reverse their order.\n\nKnowing that the mangling problem could be solved, I was feeling good about my overall idea.\nI couldn’t see any other problems, so I sketched out a new copy-tile subroutine to present to my friend.\nSince the row-copy logic was now just 5 instructions, I used it 4 times, unrolling the sole remaining loop a bit.\nNow, instead of copying 28 single rows, I copied 7 quad-rows.\n\nThe code looked something like this:\n\n```\nCOPYTILE3\n;;;\n;;; Copy a 28x28 screen tile into a screen buffer.\n;;; Arguments:\n;;;   X = starting address of *septet-reversed* background tile\n;;;   Y = starting address of destination in screen buffer\n;;; Execution time:\n;;;   34 + 7 * (224 + 7 + 3) + 7 + 10 = 1689 cycles\n;;;\n    ;; setup:  34 cycles\n    PSHS U,DP      ; save U and DP (8 cycles)\n    STS >SSAVE     ; save S (7 cycles)\n    ;;\n    LDA #TILH/4    ; initial quad-row count (2 cycles)\n    STA >ROWCT     ; (5 cycles)\n    ;;\n    LEAS ,X                    ; initialize src ptr (4 cycles)\n    LEAU (TILH-1)*SCRW+TILW,Y  ; initialize dst ptr (8 cycles)\n    ;;\n@COPY1\n    ;; copy four rows of 28 pixels in 4 * (48 + 8) = 224 cycles\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    LEAU -WOFF,U\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    LEAU -WOFF,U\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    LEAU -WOFF,U\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    LEAU -WOFF,U\n    ;;\n    DEC >ROWCT     ; reduce remaining quad-row count by one (7 cycles)\n    BNE @COPY1     ; loop while quad-rows remain (3 cycles)\n    ;;\n    LDS  >SSAVE    ; restore S (7 cycles)\n    PULS U,DP,PC   ; restore regs and return to caller (10 cycles)\n\nSSAVE ZMD  1       ; stash for saving S while drawing\nROWCT ZMB  1       ; var: remaining rows to copy\n```\n\nAdding up the cycles, the total was just 1689.\nI had shaved almost 1200 cycles off of my friend’s code.\nThat’s a 70 percent speed-up!\n\nBeaming, I went to show my friend.\n\n### The acid test\n\nWhen 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.\nWhen I explained about the whole septets-and-mangling thing, though, his face unlit, doubts rising.\nBut when I showed him the code, he got it.\nIt clicked.\n\n“Let’s try it out!” he said.\n\nIn about a half hour’s work, he had the code integrated into the game.\nAfter a rebuild and reboot, the game was loading.\n\nThe title screen came up.\n\nHe was into the game.\n\nAnd . . .\n\n*Holy crap!*\n\nThe game seemed amazingly fast.\nIn truth, it was probably only a third to a half faster, but that was enough.\nSome important perceptual threshold had been crossed.\nThe game-play was now smooth, natural.\nYou could feel the difference.\n\nWe just sat there, playing the game and grinning.\nIt was a good day.\n\nBut it would not last.\n\n### In for a penny . . .\n\nA few days after the speed problem was behind us – or so we thought – the game’s finishing touches were applied.\nOne of those finishing touches was sampled sound effects.\nThis required feeding byte-sized morsels to the audio-output DAC a few thousand times each second.\nTo schedule the feedings, my friend had turned on a hardware-clocked interrupt.\n\nWorked like a charm.\nThe sounds sounded great, and everything was perfect.\n\nExcept for one thing.\n\nAfter playing into the game one night, we noticed that some of the tiles were getting corrupted.\nThe more we played, the more corruption we saw.\n\n*Oh, no.*\n\nSomething very bad was happening.\n\nAnd then it hit us.\n\nWhat happens if an interrupt goes off during the copy-tile routine?\n\nThe processor, to prepare for calling the interrupt handler, would push its current state onto the system stack.\nBut, during the copy-tile routine, *there was no system stack*.\nThe system-stack register *S* had been commandeered.\nAnd where was it pointing?\nRight into the memory buffer that held the reference tiles!\n\nOops.\n\nWe slumped.\nAfter all that effort, to think that our all-important speed-up was causing memory corruption…\n\nNeeding a break, we walked to an all-night diner near campus to eat and think.\nOver pancakes and bacon, scrapple and grilled stickies, we talked through the problem.\n\nThere were only two stack registers, and without commandeering both of them, the copy-tile routine wouldn’t be nearly as fast.\nThere was no way, then, to return the *S* register to the system without losing our hard-won speed.\nBut there was also no way that we could get reliable sound without using interrupts.\n\nOne way or another, then, interrupts were going to be triggered.\nAnd, when they were, if copy-tile was running, whatever *S* was pointing to was going to get hammered.\n\n“How can we prevent the corruption?” I asked.\n\nWe sat there, ignoring our food, the question hanging in the air.\n\nSuddenly, my friend slapped the table.\nHe had it.\n\n“Don’t prevent it!” he said.\n\n“What?” I asked.\n\n“Don’t prevent the corruption,” he explained.\n“Let it happen.\nJust not to the reference tiles.”\n\nIt was simple, really.\nHe continued:\n\n“Just swap *S* and *U* in the copy-tile routine.\n*U* will point at the reference tiles, and *S* at the screen buffer.\nIf an interrupt goes off, the corruption will happen where *S* is pointing – *on the screen.*\nThe corruption will last only until we redraw the next frame.”\n\n“That’s brilliant!” I said.\n\nEager to try his solution, we quickly finished our meal.\n\n### . . . In for a pound\n\nWalking back to the dorms, though, it bothered us that players might see screen glitches, even if for just a frame.\nWe both felt that there had to be some way to make the hack perfect, if only we could find it.\n\nLater that night, we found it.\n\nAgain, it was simple once we saw it.\nAll we had to do was change the tile ordering.\nInstead of placing the tiles onto the screen from top to bottom, left to right, we would go right to left, bottom to top.\nIn other words, from high addresses to low addresses.\n\nThat 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.\nAnd 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](#fn2)\n\nIt was the perfect hack!\n\n### To the old days!\n\nAnd that’s the way things were.\nThe challenge wasn’t overwhelming complexity, as it is today.\nThe challenge was cramming your ideas into machines so slow, so limited that most ideas didn’t fit.\n\nYou had to bang your ideas around, twist them, turn them, searching for something, *anything* that would help you squeeze them into the machine.\nSometimes you found it, and you got one step closer to realizing your ideas.\nSometimes you didn’t.\n\nBut the search was always instructive.\n\nIn this case, the search yielded several small victories that, together, solved the problem.\nBut when you consider all the things we had to do to make that darn game fast enough, it does seem crazy.\n\nWe started with a tile-copying subroutine whose core was a hand-tuned, unrolled loop of machine instructions.\nThen, to buy a 70-percent speed-up:\n\n1. 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*.\n2. Then we pre-processed the tiles so that drawing them would actually *fix* them.\n3. But then – *dammit!* – interrupts that occurred during drawing could corrupt the reference tiles.\n4. So, to protect the reference tiles, we corrupted the screen buffer instead.\n5. But that corruption would be visible.\n6. So we changed the tile-placement order to repair – *on the fly* – any corruption that might have occurred, before it could ever be displayed.\n7. And it all worked!\n\nWe did *that.*\nFor 70 percent.\n\nAnd it was *so* worth it.\n\n### Tell ’em if you got ’em\n\nAnyway, I wanted to share that story with you for two reasons.\n\nThe first is that it’s a fun story.\nIt’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.\nThe result was powerfully satisfying.\n\nThe struggle, I learned, is worth it.\n\nThe second reason is to encourage you to tell your stories.\nI know that, “back in the day,” most video games probably gave rise to many stories like this one.\nI’d love to hear them.\nBut too many of them are lost, having faded out of memory before anyone thought to preserve them.\n\nIf you have a story, please don’t wait.\nTell it.\nEvery day you wait, it gets harder.\n\nTell it.\n\n---\n\n1. Exercise: Prove that for all finite sequences of finite sequences, applying (*reverse* ⋅ *concat*) is the same as applying (*concat* ⋅ *reverse* ⋅ *map* *reverse*).[↩︎](#fnref1)\n2. We also had to make sure that nothing valuable was stored in the memory locations just before a screen buffer.\n   They could, in theory, also be corrupted if an interrupt occurred while placing the top-left septet of the top-left corner tile.\n   This septet’s address corresponded to the start of the buffer.[↩︎](#fnref2)\n","body_html":"<h1 id=\"a-great-old-timey-game-programming-hack\">A Great Old-Timey Game-Programming Hack</h1>\n<p>By\n<a href=\"https://blog.moertel.com/about.html\" rel=\"nofollow ugc noopener\">Tom Moertel</a></p>\n<p>Posted on December 14, 2013</p>\n<p>Tags: <a href=\"https://blog.moertel.com/tags/assembly.html\" title=\"All pages tagged &#39;assembly&#39;.\" rel=\"nofollow ugc noopener\">assembly</a>, <a href=\"https://blog.moertel.com/tags/6809.html\" title=\"All pages tagged &#39;6809&#39;.\" rel=\"nofollow ugc noopener\">6809</a>, <a href=\"https://blog.moertel.com/tags/games.html\" title=\"All pages tagged &#39;games&#39;.\" rel=\"nofollow ugc noopener\">games</a>, <a href=\"https://blog.moertel.com/tags/hacks.html\" title=\"All pages tagged &#39;hacks&#39;.\" rel=\"nofollow ugc noopener\">hacks</a></p>\n<p>A long time ago, when I was a college undergrad, I spent some time working on computer video games.\nThis was in the 8-bit PC era, when the gaming hardware was almost impossibly slow by today’s standards.</p>\n<p>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.\nCrazy, crazy things.</p>\n<p>This is a story about one of those things.</p>\n<p>While I’ve done my best to recall the important details, I may have gotten some things wrong.\nIf I have, please forgive me.\nIt was a long time ago.</p>\n<p>(<em>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.</em>)</p>\n<p><em>Update 2013-12-16: There have been lots of great comments about this story on <a href=\"https://news.ycombinator.com/item?id=6913467\" rel=\"nofollow ugc noopener\">Hacker News</a> and <a href=\"http://www.reddit.com/r/programming/comments/1t05uy/a_great_oldtimey_gameprogramming_hack/\" rel=\"nofollow ugc noopener\">Proggit</a>, as well as <a href=\"http://blog.moertel.com/posts/2013-12-14-great-old-timey-game-programming-hack.html#disqus_thread\" rel=\"nofollow ugc noopener\">here on the blog</a>. Thanks for sharing, everyone!</em></p>\n<h3 id=\"the-set-up\">The set-up</h3>\n<p>A friend of mine, a gifted programmer, was nearly finished with a new game.\nSomehow, 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.</p>\n<p>The only problem was that his version of the game was unplayable.\nIt was too slow, and the choppy motion broke the player’s immersion.\nIt was after all a side-scroller.</p>\n<p>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.\nFearing that he had missed some easy optimization, he asked me to take a look at the code.</p>\n<p>I did. But there was no easy optimization to be had.</p>\n<p>The code was <em>tight</em>.\nEverywhere I looked, he had already done all the things I could think of.\nLoops had been unrolled.\nUnneeded draws had been eliminated.\nAll evidence of waste had vanished.</p>\n<p>And, with them, our hopes of an easy fix.</p>\n<p>But what about a hard fix?\nA crazy fix?</p>\n<p>Well, that was always a possibility.</p>\n<p>Before I get to the crazy stuff, however, I should back up and explain how graphics hardware worked back then.</p>\n<h3 id=\"how-graphics-hardware-worked-back-then\">How graphics hardware worked back then</h3>\n<p>Here’s the quick version:\nThe graphics hardware didn’t do jack squat.</p>\n<p>On the PC in question, if you wanted to draw something onto the screen, you had to do that yourself, byte by byte.\nNo texture mappers, no blitters.\nJust bytes.\nBytes that you had to move yourself.</p>\n<p>Fun.</p>\n<p>My friend’s game spent most of its time redrawing the background.\n(Again: side-scroller.)\nFor every frame, it had to draw nearly a screen’s worth of background tiles, shifted for the player’s position.</p>\n<p>If my memory serves me, each tile was 28 by 28 pixels.\nEach pixel was one of 16 colors, taking half a byte to represent.\nTherefore, tiles were represented in memory as 28 contiguous rows of 14 bytes each.\nThe first 14 bytes represented the first row, the second 14 bytes the second row, and so on.</p>\n<p>The screen, however, was 320 pixels wide by 240 pixels high.\nIn memory, then, a screen buffer was laid out as 240 contiguous rows of 160 bytes each.</p>\n<p>So when copying a tile at address *X* onto a screen buffer location starting at address *Y*, you had to copy 28 rows.\nTo copy each row, you had to copy 14 bytes.\nFortunately, 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 <code>++</code> operator to pointers in C).\nThat meant you could copy 4 pixels at a time while advancing both the *X* and *Y* registers in passing:</p>\n<pre><code>    LDU ,X++     ; read a 2-byte word (= 4 pixels) from source tile\n    STU ,Y++     ; write it to screen buffer</code></pre>\n<p>To copy a full row, you had to do that seven times, so you might sandwich those lines within a 7-count loop:</p>\n<pre><code>    LDB #7       ; remaining words &lt;- tile width in words\n@LOOP\n    LDU ,X++     ; read a 2-byte word (= 4 pixels) from source tile\n    STU ,Y++     ; write it to screen buffer\n    DECB         ; reduce remaining-word count\n    BNE @LOOP    ; loop while words remain</code></pre>\n<p>When you were done copying the row, you needed to advance the destination pointer *Y* so that it pointed to the starting address for the next row you would draw into the screen buffer.\nSince the screen buffer was 160 bytes wide and a tile was only 14 bytes wide, that meant you had to add their difference to *Y*:</p>\n<pre><code>    LEAY 160-14,Y</code></pre>\n<p>And, just like that, you have copied a row onto the screen.</p>\n<p>That’s one.\nTo copy a full tile, you need to do the same thing 28 times.\nSo, in turn, you sandwich <em>that</em> code within a 28-count loop.</p>\n<p>Putting it all together, and giving names to the important numbers, you might end up with a subroutine like this:</p>\n<pre><code>;;; important constants\n\nSCRW = 160          ; screen-buffer width in bytes (= 320 4-bit pixels)\nTILW =  14          ; background-tile width in bytes (= 28 4-bit pixels)\nTILH =  28          ; background-tile height in rows\nWOFF = SCRW - TILW  ; s-b offset from end of one tile row to start of next\n\nCOPYTILE\n;;;\n;;; Copy a 28x28 background tile into a screen buffer.\n;;; Arguments:\n;;;   X = starting address of background tile\n;;;   Y = starting address of destination in screen buffer\n;;;\n    LDA #TILH               ; remaining rows &lt;- tile height\n@COPYROW\n    LDB #TILW/2             ; remaining words &lt;- tile width in words\n@LOOP\n    LDU ,X++                ; read a word (= 4 pixels) from source tile\n    STU ,Y++                ; write it to screen buffer\n    DECB                    ; reduce remaining-word count\n    BNE @LOOP               ; loop while words remain\n    ;;\n    LEAY WOFF,Y             ; advance dst ptr to start of next dst row\n    DECA                    ; reduce remaining-row count\n    BNE @COPYROW            ; loop while rows remain\n    ;;\n    RTS                     ; done! return to caller</code></pre>\n<p>And that code would be fine.</p>\n<p>If you didn’t care about speed.</p>\n<h3 id=\"caring-about-speed\">Caring about speed</h3>\n<p>Knowing that the game is probably going to spend most of its time running that code, you do what any good programmer would: start counting cycles.\nHere’s the inner loop again, with setup and finishing, annotated with cycle counts:</p>\n<pre><code>    LDB #TILW/2             ; 2 cycles (set-up)\n@LOOP\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    DECB                    ; 2\n    BNE @LOOP               ; 3\n    ;;\n    LEAY WOFF,Y             ; 8 (finishing)</code></pre>\n<p>Looking at those counts within the loop, you’re not likely to miss that you’re burning 21 cycles to copy just 4 pixels.\nTo copy a full row, then, works out to 2 cycles + (7 iterations) * (21 cycles/iteration) + 8 cycles = 157 cycles.\nOuch.</p>\n<p>But this isn’t your first time at the keyboard.\nYou know what to do.\nUnroll that loop!</p>\n<pre><code>    LDU ,X++                ; 8 cycles\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LDU ,X++                ; 8\n    STU ,Y++                ; 8\n    LEAY WOFF,Y             ; 8 (finishing)</code></pre>\n<p>Now, with the loop overhead reduced to zero – you’ve even eliminated the set-up – each row takes only 7 * (8 + 8) + 8 = 120 cycles.\nThat’s a 30-percent speed-up.\nPretty good.</p>\n<p>And that’s where most programmers probably would have left it.</p>\n<p>But not my friend.</p>\n<p>He knew that those <code>++</code> operations were costly, 3 cycles apiece.\nAnd, with the loop unrolled, he also knew exactly where each word to be read or written was located with respect to *X* or *Y*.\nSo he cleverly replaced those 3-cycle post-increments with exact offsets.\nThey cost only 1 cycle apiece, and the 0 offset is actually free:</p>\n<pre><code>    LDU  ,X                 ; 5 cycles\n    STU  ,Y                 ; 5\n    LDU 2,X                 ; 6\n    STU 2,Y                 ; 6\n    LDU 4,X                 ; 6\n    STU 4,Y                 ; 6\n    LDU 6,X                 ; 6\n    STU 6,Y                 ; 6\n    LDU 8,X                 ; 6\n    STU 8,Y                 ; 6\n    LDU 10,X                ; 6\n    STU 10,Y                ; 6\n    LDU 12,X                ; 6\n    STU 12,Y                ; 6\n    LEAX TILW,X             ; 8 (finishing)\n    LEAY SCRW,Y             ; 8 (finishing)</code></pre>\n<p>With his optimizations, the cycle count per row had been reduced to (5 + 5) + 6 * (6 + 6) + (8 + 8) = 98 cycles.\nCompared to the original code, that’s 60 percent faster:</p>\n<pre><code>original_speed  = (1*row) / (157*cycle)\noptimized_speed = (1*row) /  (98*cycle)\n\nspeed_up  =  optimized_speed / original_speed - 1  =  157 / 98 - 1  =  0.60.</code></pre>\n<p>Putting it all together – and, again, I’m going by memory so the code might have been slightly different – the copy-tile subroutine looked something like this, and it copied a full tile, all 28 rows, in a lean 2893 cycles:</p>\n<pre><code>COPYTILE2\n;;;\n;;; Copy a 28x28 screen tile into a screen buffer.\n;;; Arguments:\n;;;   X = starting address of background tile\n;;;   Y = starting address of destination in screen buffer\n;;; Execution time:\n;;;   4 + 28 * (82 + 8 + 8 + 2 + 3) + 5 = 2893 cycles\n;;;\n    LDA #TILH      ; initialize row count (4 cycles)\n    ;;\n@COPY1\n    ;; unroll inner loop (copies one row of 28 pixels in 82 cycles)\n    LDU ,X         ; (1) read 4 pixels (5 cycles)\n    STU ,Y         ;     write 4 pixels (5 cycles)\n    LDU 2,X        ; (2) (6 cycles)\n    STU 2,Y        ;     (6 cycles)\n    LDU 4,X        ; (3) ...\n    STU 4,Y        ;     ...\n    LDU 6,X        ; (4)\n    STU 6,Y        ;\n    LDU 8,X        ; (5)\n    STU 8,Y        ;\n    LDU 10,X       ; (6)\n    STU 10,Y       ;\n    LDU 12,X       ; (7)\n    STU 12,Y       ;\n    ;;\n    LEAX TILW,X    ; advance src to start of next row (8 cycles)\n    LEAY SCRW,Y    ; advance dst to start of next row (8 cycles)\n    DECA           ; reduce remaining count by one (2 cycles)\n    BNE @COPY1     ; loop while rows remain (3 cycles)\n    ;;\n    RTS            ; done!  return to caller (5 cycles)</code></pre>\n<p>This code, all in all, was 60% faster than the naive <code>COPYTILE</code> code we started out with.</p>\n<p>But that wasn’t fast enough.\nNot nearly.</p>\n<p>So when my friend showed me his code and asked if I could make it faster, I really wanted to help him.\nI really wanted to be able to answer yes.</p>\n<p>But I had to answer no.\nI hated giving that answer.\nBut, studying the code, I couldn’t see any way to speed it up.</p>\n<p>And yet, the hook was set.</p>\n<p>Later, I couldn’t get the problem out of my head.\nMaybe I had missed something.\nI had grown up on Apple II computers and their 6502 processors.\nMy friend’s code, however, was for the 6809.\nMaybe it afforded optimizations that I didn’t know about.</p>\n<p>With renewing optimism, I dialed into the university’s library to access the card catalog.\n(These were the days before the World Wide Web.)\nThrough a VT220 terminal emulator, I searched for books about the 6809.</p>\n<p>There was one.\nA 6809 microprocessor manual.\nIt was in the engineering library.\nLuckily, I was an engineering student and had sign-out privileges.</p>\n<p>Just like that, I was off to the library.</p>\n<h3 id=\"a-crazy-idea\">A crazy idea</h3>\n<p>When I got to the engineering library, I found the book right where it was supposed to be, looking a little beat up:</p>\n<p><a href=\"https://archive.org/details/bitsavers_motorola68_13419254/mode/2up\" rel=\"nofollow ugc noopener\"><em>The MC6809-MC6809E Microprocessor Programming Manual</em></a>.</p>\n<p>Not bothering to find a chair, I flipped through the pages standing, looking for some oddball, 6809-specific instruction that might throw a lot of bytes and throw them fast.\nPage after page, though, turned up nothing.</p>\n<p>Then I came upon <a href=\"https://archive.org/details/bitsavers_motorola68_13419254/page/n99/mode/2up?q=pshs\" rel=\"nofollow ugc noopener\">PSHS</a>.\n“Push registers on the hardware stack.”</p>\n<p>On my beloved 6502, if you wanted to save registers on the stack, you had to do it one register at a time and, even then, by transferring them through the accumulator.\nIt was slow and expensive.\nSo I had learned to avoid the stack when speed mattered.</p>\n<p>But on the 6809 you could save <em>all</em> of the registers – or any subset of them – with <em>a single instruction</em>.\nAnd, amazingly, it cost a mere 5 cycles, plus 1 cycle more per byte pushed.</p>\n<p>Since the processor had three 16-bit general-purpose registers – *D*, *X*, and *Y* – I could load them up and then use a single <code>PSHS</code> instruction to write 6 bytes in just 11 cycles.\nThe corresponding pull instruction, <a href=\"https://archive.org/details/bitsavers_motorola68_13419254/page/n101/mode/2up?q=puls\" rel=\"nofollow ugc noopener\"><code>PULS</code></a>, had the same low cost.</p>\n<p>Further, the 6809 had <em>two</em> stack registers, *S* and *U*.\nI could use one as a source pointer and the other as a destination pointer.\nIn theory, with a single <code>PULS</code>/<code>PSHU</code> pair, I could copy 6 bytes in 22 cycles.</p>\n<p>That’s crazy, crazy fast.</p>\n<p>Excitement mounting, I headed for the front desk and reached for my student ID.\nI was going to sign out that wonderful little book for further study.</p>\n<h3 id=\"a-crazy-plan\">A crazy plan</h3>\n<p>Walking back to the dorms, I formed my plan.</p>\n<p>I would save the *S* and *U* registers somewhere, and then point *S* at the background tile and *U* at the screen buffer.\nThen I would pull from *S* and push to *U*, copying 6 bytes at a time, using *D*, *X*, and *Y* as go-betweens.\nTo copy the 14 bytes that make up a row would require three such iterations, which unrolled would be about 60 cycles.</p>\n<p>When I reached my room, I found a piece of paper and sketched it out:</p>\n<pre><code>    PULS D,X,Y    ; first 6 bytes    11 cycles\n    PSHU D,X,Y    ;                  11\n    PULS D,X,Y    ; second 6 bytes   11\n    PSHU D,X,Y    ;                  11\n    PULS D        ; final 2 bytes     7\n    PSHU D        ;                   7\n    LEAU -WOFF,U  ; advance dst ptr   8</code></pre>\n<p>Just 66 cycles, including the after-row adjustment to *U* that prepares it for the next row.\n(Note that the adjustment is now negative.)\nFor comparison, the naive row-copy loop that we looked at earlier took 157 cycles to do the same thing.\nAnd my friend’s optimized code took 98.\nAlready, this crazy idea was looking like a big win.</p>\n<p>Still, that last <code>PULS</code>/<code>PSHU</code> pair!\nWhat a clunker.\nIt was needed to handle the final two bytes per row, since the rows were 28 pixels = 14 bytes wide, and 6 doesn’t divide 14 evenly.</p>\n<p><em>That darn remainder of 2 bytes!</em></p>\n<p>If only the game had used 24-by-24 tiles instead…\nBut it hadn’t, so I pored through the manual, looking for a way to lower the cost of that inevitable last pair.</p>\n<p>And then, by surprise, I struck gold!\nIt was another 6809 oddity, the <em>DP</em> register.</p>\n<p>On the 6502 and most 8-bit processors of the era, the lowest 256 bytes of memory was called the <em>zero page</em>.\nThe zero page was special because its memory locations had single-byte addresses and could be accessed with shorter and usually faster instructions.</p>\n<p>The 6809’s designers took this idea one step further.\nThey let you use the <em>DP</em> register to designate <em>any</em> page as the zero page, which they called the “direct page.”</p>\n<p>But none of my byte-slinging instructions needed to use the direct page.\nThat meant I could use the <em>DP</em> register as an additional one-byte go-between.\nNow I could copy 7 bytes per pull-push pair!</p>\n<p>And 14 <em>is</em> evenly divisible by 7.</p>\n<p>With this change, I could copy a whole 28-pixel row and advance to the next in just 5 instructions:</p>\n<pre><code>    PULS D,X,Y,DP  ; first 7 bytes    12 cycles\n    PSHU D,X,Y,DP  ;                  12\n    PULS D,X,Y,DP  ; second 7 bytes   12\n    PSHU D,X,Y,DP  ;                  12\n    LEAU -WOFF,U   ; advance dst ptr   8</code></pre>\n<p>56 cycles!\nFifty. Six. Cycles.</p>\n<p>That bit of code made me feel just <em>awesome</em>.\nI had managed to harness every single available register on the machine for byte-slinging!\n*D*, *X*, *Y*, *U*, *S*, and even the oddball <em>DP</em> – they were all fully engaged.</p>\n<p>I was feeling great about this solution.</p>\n<p>Except for just one thing…</p>\n<h3 id=\"i-ll-have-a-little-more-crazy-please\">I’ll have a little more crazy, please</h3>\n<p>If you’re acquainted with stacks, you may have noticed a subtle flaw in my brilliant plan:</p>\n<p><em>Pushes and pulls work in opposite directions.</em></p>\n<p>See, I lied about that little block of code I just showed you.\nIt didn’t <em>actually</em> copy one row from a background tile onto the screen.\nWhat it actually did was break the row into two 7-byte blocks – I’ll call them “septets” – and then draw them onto the screen <em>swapped</em>.</p>\n<p>Recall that tile rows were laid out sensibly in memory as 14 contiguous bytes, like this:</p>\n<pre><code>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n| 0   1   2   3   4   5   6   7   8   9   A   B   C   D |\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</code></pre>\n<p>So when you pulled-and-pushed a row onto the screen in 7-byte septets, it would get horizontally split like this:</p>\n<pre><code>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n| 7   8   9   A   B   C   D | 0   1   2   3   4   5   6 |\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</code></pre>\n<p>The first septet was now second, and the second now first.\nNote, however, that the bytes within each septet were unchanged; they retained their original ordering.</p>\n<p>Further, if you ran the row-copy code multiple times, the vertical stack of rows you copied would end up being upside down.\nThat’s because the code uses pushes to write the rows onto the screen.\nPushes move the stack pointer toward lower addresses, and lower addresses correspond to screen lines higher up on the display.</p>\n<p>To visualize the havoc that this row-reversal and septet-swapping would wreak, let’s say that you had the following 28-by-28 tile, representing a key:</p>\n<p>If you had used 28 applications of my row-copy code to draw it onto the screen, you would have ended up with this not-a-key:</p>\n<p>So . . . <em>that</em> was a problem.</p>\n<p>But this problem, too, had an elegant solution!</p>\n<p>To review:</p>\n<ul><li>the rows were upside down</li><li>the septets within each row were swapped</li><li>but the bytes within each septet were unchanged</li></ul>\n<p>The breakthrough was to see “upside down” and “swapped” as two instances of the same thing. <em>Reversal.</em></p>\n<p>Reversal has this handy property: it’s an <a href=\"http://en.wikipedia.org/wiki/Involution_(mathematics)\" rel=\"nofollow ugc noopener\"><em>involution</em></a>.\nReverse something twice, and you get back the original.\nWith this in mind, I reasoned that if the tiles were pre-processed to reverse their rows and then the septets within the rows, the tiles would end up looking fine when they hit the screen.\nThe mangling that occurred during copying and pre-processing would, in effect, undo each other.</p>\n<p>Working it out on paper, I also discovered that the pre-processing step could ignore the rows and just treat the tiles as one long, linear sequence of septets.<a href=\"#fn1\">1</a>\nTo see why this is so, let’s consider a small tile of 2 rows of 2 septets each:</p>\n<pre><code>+---+---+\n| a   b |\n+---+---+\n| c   d |\n+---+---+</code></pre>\n<p>In memory, it would be laid out in row-major order, that is, as 4 sequential septets:</p>\n<pre><code>+---+---+---+---+\n| a   b | c   d |\n+---+---+---+---+</code></pre>\n<p>So, reversing the rows and then swapping the septets within each row is the same as just reversing the septet order in memory:</p>\n<pre><code>+---+---+                  +---+---+                  +---+---+\n| a   b |                  | c   d |                  | d   c |\n+---+---+        =======&gt;  +---+---+        =======&gt;  +---+---+\n| c   d |        reverse   | a   b |        swap      | b   a |\n+---+---+        rows      +---+---+        septets   +---+---+\n\n+---+---+---+---+          +---+---+---+---+          +---+---+---+---+\n| a   b | c   d |          | c   d | a   b |          | d   c | b   a |\n+---+---+---+---+          +---+---+---+---+          +---+---+---+---+</code></pre>\n<p>So the solution to the mangling problem turned out to be a simple, one-time pre-processing step:\nJust break each tile into septets and reverse their order.</p>\n<p>Knowing that the mangling problem could be solved, I was feeling good about my overall idea.\nI couldn’t see any other problems, so I sketched out a new copy-tile subroutine to present to my friend.\nSince the row-copy logic was now just 5 instructions, I used it 4 times, unrolling the sole remaining loop a bit.\nNow, instead of copying 28 single rows, I copied 7 quad-rows.</p>\n<p>The code looked something like this:</p>\n<pre><code>COPYTILE3\n;;;\n;;; Copy a 28x28 screen tile into a screen buffer.\n;;; Arguments:\n;;;   X = starting address of *septet-reversed* background tile\n;;;   Y = starting address of destination in screen buffer\n;;; Execution time:\n;;;   34 + 7 * (224 + 7 + 3) + 7 + 10 = 1689 cycles\n;;;\n    ;; setup:  34 cycles\n    PSHS U,DP      ; save U and DP (8 cycles)\n    STS &gt;SSAVE     ; save S (7 cycles)\n    ;;\n    LDA #TILH/4    ; initial quad-row count (2 cycles)\n    STA &gt;ROWCT     ; (5 cycles)\n    ;;\n    LEAS ,X                    ; initialize src ptr (4 cycles)\n    LEAU (TILH-1)*SCRW+TILW,Y  ; initialize dst ptr (8 cycles)\n    ;;\n@COPY1\n    ;; copy four rows of 28 pixels in 4 * (48 + 8) = 224 cycles\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    LEAU -WOFF,U\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    LEAU -WOFF,U\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    LEAU -WOFF,U\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    PULS X,Y,D,DP\n    PSHU X,Y,D,DP\n    LEAU -WOFF,U\n    ;;\n    DEC &gt;ROWCT     ; reduce remaining quad-row count by one (7 cycles)\n    BNE @COPY1     ; loop while quad-rows remain (3 cycles)\n    ;;\n    LDS  &gt;SSAVE    ; restore S (7 cycles)\n    PULS U,DP,PC   ; restore regs and return to caller (10 cycles)\n\nSSAVE ZMD  1       ; stash for saving S while drawing\nROWCT ZMB  1       ; var: remaining rows to copy</code></pre>\n<p>Adding up the cycles, the total was just 1689.\nI had shaved almost 1200 cycles off of my friend’s code.\nThat’s a 70 percent speed-up!</p>\n<p>Beaming, I went to show my friend.</p>\n<h3 id=\"the-acid-test\">The acid test</h3>\n<p>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.\nWhen I explained about the whole septets-and-mangling thing, though, his face unlit, doubts rising.\nBut when I showed him the code, he got it.\nIt clicked.</p>\n<p>“Let’s try it out!” he said.</p>\n<p>In about a half hour’s work, he had the code integrated into the game.\nAfter a rebuild and reboot, the game was loading.</p>\n<p>The title screen came up.</p>\n<p>He was into the game.</p>\n<p>And . . .</p>\n<p><em>Holy crap!</em></p>\n<p>The game seemed amazingly fast.\nIn truth, it was probably only a third to a half faster, but that was enough.\nSome important perceptual threshold had been crossed.\nThe game-play was now smooth, natural.\nYou could feel the difference.</p>\n<p>We just sat there, playing the game and grinning.\nIt was a good day.</p>\n<p>But it would not last.</p>\n<h3 id=\"in-for-a-penny\">In for a penny . . .</h3>\n<p>A few days after the speed problem was behind us – or so we thought – the game’s finishing touches were applied.\nOne of those finishing touches was sampled sound effects.\nThis required feeding byte-sized morsels to the audio-output DAC a few thousand times each second.\nTo schedule the feedings, my friend had turned on a hardware-clocked interrupt.</p>\n<p>Worked like a charm.\nThe sounds sounded great, and everything was perfect.</p>\n<p>Except for one thing.</p>\n<p>After playing into the game one night, we noticed that some of the tiles were getting corrupted.\nThe more we played, the more corruption we saw.</p>\n<p><em>Oh, no.</em></p>\n<p>Something very bad was happening.</p>\n<p>And then it hit us.</p>\n<p>What happens if an interrupt goes off during the copy-tile routine?</p>\n<p>The processor, to prepare for calling the interrupt handler, would push its current state onto the system stack.\nBut, during the copy-tile routine, <em>there was no system stack</em>.\nThe system-stack register *S* had been commandeered.\nAnd where was it pointing?\nRight into the memory buffer that held the reference tiles!</p>\n<p>Oops.</p>\n<p>We slumped.\nAfter all that effort, to think that our all-important speed-up was causing memory corruption…</p>\n<p>Needing a break, we walked to an all-night diner near campus to eat and think.\nOver pancakes and bacon, scrapple and grilled stickies, we talked through the problem.</p>\n<p>There were only two stack registers, and without commandeering both of them, the copy-tile routine wouldn’t be nearly as fast.\nThere was no way, then, to return the *S* register to the system without losing our hard-won speed.\nBut there was also no way that we could get reliable sound without using interrupts.</p>\n<p>One way or another, then, interrupts were going to be triggered.\nAnd, when they were, if copy-tile was running, whatever *S* was pointing to was going to get hammered.</p>\n<p>“How can we prevent the corruption?” I asked.</p>\n<p>We sat there, ignoring our food, the question hanging in the air.</p>\n<p>Suddenly, my friend slapped the table.\nHe had it.</p>\n<p>“Don’t prevent it!” he said.</p>\n<p>“What?” I asked.</p>\n<p>“Don’t prevent the corruption,” he explained.\n“Let it happen.\nJust not to the reference tiles.”</p>\n<p>It was simple, really.\nHe continued:</p>\n<p>“Just swap *S* and *U* in the copy-tile routine.\n*U* will point at the reference tiles, and *S* at the screen buffer.\nIf an interrupt goes off, the corruption will happen where *S* is pointing – <em>on the screen.</em>\nThe corruption will last only until we redraw the next frame.”</p>\n<p>“That’s brilliant!” I said.</p>\n<p>Eager to try his solution, we quickly finished our meal.</p>\n<h3 id=\"in-for-a-pound\">. . . In for a pound</h3>\n<p>Walking back to the dorms, though, it bothered us that players might see screen glitches, even if for just a frame.\nWe both felt that there had to be some way to make the hack perfect, if only we could find it.</p>\n<p>Later that night, we found it.</p>\n<p>Again, it was simple once we saw it.\nAll we had to do was change the tile ordering.\nInstead of placing the tiles onto the screen from top to bottom, left to right, we would go right to left, bottom to top.\nIn other words, from high addresses to low addresses.</p>\n<p>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.\nAnd 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.<a href=\"#fn2\">2</a></p>\n<p>It was the perfect hack!</p>\n<h3 id=\"to-the-old-days\">To the old days!</h3>\n<p>And that’s the way things were.\nThe challenge wasn’t overwhelming complexity, as it is today.\nThe challenge was cramming your ideas into machines so slow, so limited that most ideas didn’t fit.</p>\n<p>You had to bang your ideas around, twist them, turn them, searching for something, <em>anything</em> that would help you squeeze them into the machine.\nSometimes you found it, and you got one step closer to realizing your ideas.\nSometimes you didn’t.</p>\n<p>But the search was always instructive.</p>\n<p>In this case, the search yielded several small victories that, together, solved the problem.\nBut when you consider all the things we had to do to make that darn game fast enough, it does seem crazy.</p>\n<p>We started with a tile-copying subroutine whose core was a hand-tuned, unrolled loop of machine instructions.\nThen, to buy a 70-percent speed-up:</p>\n<ol><li>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 <em>upside down and horizontally broken</em>.</li><li>Then we pre-processed the tiles so that drawing them would actually <em>fix</em> them.</li><li>But then – <em>dammit!</em> – interrupts that occurred during drawing could corrupt the reference tiles.</li><li>So, to protect the reference tiles, we corrupted the screen buffer instead.</li><li>But that corruption would be visible.</li><li>So we changed the tile-placement order to repair – <em>on the fly</em> – any corruption that might have occurred, before it could ever be displayed.</li><li>And it all worked!</li></ol>\n<p>We did <em>that.</em>\nFor 70 percent.</p>\n<p>And it was <em>so</em> worth it.</p>\n<h3 id=\"tell-em-if-you-got-em\">Tell ’em if you got ’em</h3>\n<p>Anyway, I wanted to share that story with you for two reasons.</p>\n<p>The first is that it’s a fun story.\nIt’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.\nThe result was powerfully satisfying.</p>\n<p>The struggle, I learned, is worth it.</p>\n<p>The second reason is to encourage you to tell your stories.\nI know that, “back in the day,” most video games probably gave rise to many stories like this one.\nI’d love to hear them.\nBut too many of them are lost, having faded out of memory before anyone thought to preserve them.</p>\n<p>If you have a story, please don’t wait.\nTell it.\nEvery day you wait, it gets harder.</p>\n<p>Tell it.</p>\n<hr />\n<ol><li>Exercise: Prove that for all finite sequences of finite sequences, applying (<em>reverse</em> ⋅ <em>concat</em>) is the same as applying (<em>concat</em> ⋅ <em>reverse</em> ⋅ <em>map</em> <em>reverse</em>).<a href=\"#fnref1\">↩︎</a></li><li><p>We also had to make sure that nothing valuable was stored in the memory locations just before a screen buffer.</p><p> They could, in theory, also be corrupted if an interrupt occurred while placing the top-left septet of the top-left corner tile.\n This septet’s address corresponded to the start of the buffer.<a href=\"#fnref2\">↩︎</a></p></li></ol>","headings":[{"level":1,"text":"A Great Old-Timey Game-Programming Hack","id":"a-great-old-timey-game-programming-hack"},{"level":3,"text":"The set-up","id":"the-set-up"},{"level":3,"text":"How graphics hardware worked back then","id":"how-graphics-hardware-worked-back-then"},{"level":3,"text":"Caring about speed","id":"caring-about-speed"},{"level":3,"text":"A crazy idea","id":"a-crazy-idea"},{"level":3,"text":"A crazy plan","id":"a-crazy-plan"},{"level":3,"text":"I’ll have a little more crazy, please","id":"i-ll-have-a-little-more-crazy-please"},{"level":3,"text":"The acid test","id":"the-acid-test"},{"level":3,"text":"In for a penny . . .","id":"in-for-a-penny"},{"level":3,"text":". . . In for a pound","id":"in-for-a-pound"},{"level":3,"text":"To the old days!","id":"to-the-old-days"},{"level":3,"text":"Tell ’em if you got ’em","id":"tell-em-if-you-got-em"}]}}