伟大的老式游戏编程黑客(2013)

很久以前，当我还是一名大学本科生的时候，我花了一些时间在电脑视频游戏上。那是在8位PC时代，按照今天的标准，游戏硬件几乎是不可能的慢。

那么，当你了解到以前的游戏程序员为了让他们的游戏以可玩的速度运行而做了各种疯狂的事情时，你可能不会感到惊讶。疯狂，疯狂的事情。

虽然我已经尽了最大努力去回忆重要的细节，但我可能弄错了一些东西。如果我有，请原谅我。那是很久以前的事了。

(注意：这篇文章包含一些小图片作为内联数据URL，一些提要阅读器显然没有很好地处理这些图片。如果您看不到提要中的图像，请单击转到原始文章以查看它们。)。

更新2013-12-16：在Hacker News和Proggit上以及这里的博客上都有很多关于这个故事的很好的评论。感谢大家的分享！

我的一个朋友，一位有天赋的程序员，几乎完成了一款新游戏。不知何故，他相当忠实地挤进了一台20世纪80年代的个人电脑，这在当时是一款在拱廊流行的图形令人印象深刻的投币游戏。

唯一的问题是他的游戏版本不能玩。它太慢了，波涛汹涌的动作打破了玩家的沉浸感。它毕竟是一个侧滚轴。

我的朋友一直在玩这个游戏，同时还在上满负荷的大学课程，他似乎开始有点疲惫了。由于担心错过了一些简单的优化，他让我看一下代码。

密码很严格。无论我往哪里看，他已经做了我能想到的所有事情。循环已经展开。不需要的平局已经被消除了。所有浪费的证据都消失了。

然而，在我开始讨论疯狂的事情之前，我应该回顾一下，并解释一下当时的图形硬件是如何工作的。

这里有一个快速版本：图形硬件不能进行千斤顶下蹲。

在有问题的PC上，如果您想要在屏幕上绘制一些东西，您必须自己一个字节一个字节地完成。没有纹理映射器，没有闪光器。只有几个字节。您必须自己移动的字节数。

我朋友的游戏大部分时间都在重新绘制背景。(再说一遍：侧滚轴。)。对于每一帧，它必须绘制几乎一个屏幕大小的背景瓷砖，并根据玩家的位置移动。

如果我没记错的话，每个瓷砖都是28x28像素。每个像素是16种颜色中的一种，用半个字节来表示。因此，在存储器中，瓦片被表示为28个连续行，每行14字节。前14个字节表示第一行，第二个14个字节表示第二行，依此类推。

然而，屏幕是320像素宽，240像素高。然后，在内存中，屏幕缓冲区被布置为240个连续行，每行160字节。

因此，当将地址X处的平铺复制到从地址Y开始的屏幕缓冲区位置时，您必须复制28行。要复制每行，您必须复制14个字节。幸运的是，这款游戏的处理器是6809，它有几个16位索引寄存器和令人愉快的“自动递增”寻址模式(有点像将后缀++操作符应用于C中的指针)。这意味着在传递X和Y寄存器的同时，您可以一次复制4个像素：

LDU，X++；从源平铺Stu，Y++读取2字节字(=4像素)；将其写入屏幕缓冲区。

要复制整行，您必须执行七次操作，因此您可以将这些行夹在一个包含7个计数的循环中：

LDB#7；剩余字数<；-字块宽度@LOOP LDU，X++；从源平铺块Stu，Y++读取2字节字(=4像素)；将其写入屏幕缓冲区DECB；减少剩余字数BNE@LOOP；循环，同时字数保持不变。

复制完该行后，您需要将目标指针Y向前移动，以便它指向您将绘制到屏幕缓冲区中的下一行的起始地址。由于屏幕缓冲区有160字节宽，而平铺只有14字节宽，这意味着您必须将它们的差值加到Y：

这就是其中之一。要复制完整的磁贴，您需要执行相同的操作28次。因此，反过来，您将代码夹在一个包含28个计数的循环中。

将所有这些放在一起，并为重要的数字命名，您可能会得到如下所示的子例程：

；重要常数SCRW=160；屏幕缓冲区宽度(=320 4位像素)TILW=14；背景平铺宽度(=28 4位像素)TILH=28；行背景平铺高度WOFF=scrw-TILW；s-b从平铺行尾到下一平铺开始的偏移COPYTILE；将28x28背景平铺复制到屏幕缓冲区。；参数：；X=背景平铺的起始地址；Y=屏幕缓冲区中目标的起始地址；LDA#TILH；剩余行<；-平铺高度@COPYROW LDB#TILW/2；剩余字<；-以字为单位的平铺宽度@LOOP LDU，X++；从源平铺STU，Y++读取一个字(=4像素)；将其写入屏幕缓冲区DECB；减少剩余字数BNE@LOOP；在字保留时循环；；Leay WOFF，Y；将DST PTR前进到下一个DST行DECA的开始；减少剩余行数BNE@COPYROW；行保留时循环；；RTS；完成！返回给呼叫方。

知道游戏可能会花费大部分时间运行该代码，您可以做任何优秀的程序员都会做的事情：开始计算周期。下面又是一个内部循环，其中包含设置和结束，并用循环计数进行了注释：

LDB#TILW/2；2周期(设置)@LOOP LDU，X++；8 STU，Y++；8 DECB；2 BNE@LOOP；3；；LEAY WOFF，Y；8(精加工)。

查看循环中的这些计数，您不太可能错过仅复制4个像素而耗费21个周期的情况。因此，要复制整行，计算结果是2个周期+(7个迭代)*(21个周期/迭代)+8个周期=157个周期。唉哟。

但这不是你第一次玩键盘了。你知道该怎么做。打开那个环路！

LDU，X++；8周期STU，Y++；8 LDU，X++；8 STU，Y++；8 Lay WOFF，Y；8(精加工)。

现在，循环开销减少到零-您甚至取消了设置-每行只需要7*(8+8)+8=120个周期。那是30%的提速。相当不错。

他知道这些++手术费用很高，每次3个周期。而且，随着循环的展开，他还准确地知道要读或写的每个单词相对于X或Y的位置。因此，他巧妙地用精确的偏移量替换了那些3个周期的后置增量。它们每个只需1个周期，并且0偏移量实际上是免费的：

LDU，X；5周期STU，Y；5 LDU 2，X；6 STU 2，Y；6 LDU 4，X；6 STU 4，Y；6 LDU 6，X；6 STU 6，Y；6 LDU 8，X；6 STU 8，Y；6 LDU 10，X；6 STU 10，Y；6 LDU 12，X；6 STU 12，Y；6 LEAX TILW，X；8(整理)Leay scrw，Y；8(整理)。

通过他的优化，每行周期数减少到(5+5)+6*(6+6)+(8+8)=98个周期。与原始代码相比，速度提高了60%：

Original_SPEED=(1*行)/(157*周期)OPTIMIZED_SPEED=(1*行)/(98*周期)SPEED_UP=OPTIMIZED_SPEED/Original_SPEED=157/98=1.60。

把所有这些放在一起-我再一次使用内存，所以代码可能略有不同-复制平铺子例程看起来类似于这样，它在一个精简的2893个周期中复制了一个完整的平铺，所有28行：

COPYTILE2；将28x28屏幕平铺复制到屏幕缓冲区。；参数：；X=背景平铺的起始地址；Y=屏幕缓冲区中目标的起始地址；执行时间：；；4+28*(82+8+8+2+3)+5=2893个周期；LDA#TILH；初始化行数(4个周期)；@COPY1；；展开内循环(在82个周期中复制28个像素的一行)LDU，X；(1)读取4个像素(5个周期)STU，Y；写入4个像素(5个周期)LDU 2，X；(2)(6个周期)STU 2，Y；(6个周期)LDU 4，X；(3)...。学生4，Y；。LDU 6，X；(4)STU 6，Y；LDU 8，X；(5)STU 8，Y；LDU 10，X；(6)STU 10，Y；LDU 12，X；(7)STU 12，Y；；LEAX TILW，X；前进源到下一行的开始(8个周期)Leay Scrw，Y；前进DST到下一行的开始(8个周期)DECA；减少剩余计数一(2个周期)BNE@COPY1；行保持循环(3个周期)；RTS；完成！退还给呼叫者(5个周期)。

总而言之，这段代码比我们开始时使用的朴素的COPYTILE代码快了60%。

因此，当我的朋友给我看他的代码，问我是否可以让它更快时，我真的很想帮助他。我真的很想能够回答“是”。

但我不得不回答不。我讨厌给出那个答案。但是，在研究代码时，我找不到任何方法来加快速度。

后来，我就是忘不掉这个问题。也许我错过了什么。我是在Apple II电脑和它们的6502处理器上长大的。然而，我朋友的代码是6809。也许它提供了我不知道的优化。

带着重新恢复的乐观情绪，我拨通了大学图书馆的电话，查看了卡片目录。(这是万维网出现之前的日子。)。通过VT220终端仿真器，我搜索了有关6809的书籍。

有一个。一本6809微处理器手册。它在工程学图书馆里。幸运的是，我是一名工科学生，拥有注销特权。

当我到达工程图书馆时，我发现这本书就在它应该放的地方，看起来有点破旧：

我懒得找张椅子，站着翻阅页面，寻找一些古怪的、特定于6809的指令，这些指令可能会抛出很多字节，而且扔得很快。然而，一页又一页地没有找到任何东西。

在我心爱的6502上，如果您想要在堆栈上保存寄存器，您必须一次保存一个寄存器，即使这样，也要通过累加器传输它们。它既慢又贵。因此，当速度很重要时，我学会了避免堆叠。

但在6809上，您可以用一条指令保存所有寄存器或其中的任何子集。而且，令人惊讶的是，它只需要5个周期，外加每个字节多1个周期。

由于处理器有三个16位通用寄存器-D、X和Y-我可以加载它们，然后使用单个PSHS指令在短短11个周期内写入6个字节。相应的PULL指令PULS具有相同的低成本。

此外，6809有两个堆栈寄存器，S和U。我可以使用一个作为源指针，另一个作为目标指针。理论上，使用单个PULS/PSHU对，我可以在22个周期内复制6个字节。

兴奋之情与日俱增，我走向前台，伸手拿出学生证，准备在那本奇妙的小书上签字继续深造。

我会将S和U寄存器保存在某个地方，然后将S指向背景块，将U指向屏幕缓冲区。然后我会从S拉到U，一次复制6个字节，使用D、X和Y作为中间人。要复制组成一行的14个字节将需要三次这样的迭代，这将展开大约60个周期。

当我到达我的房间时，我找到一张纸，把它画了出来：

脉冲D，X，Y；前6字节11周期PSHU D，X，Y；11脉冲D，X，Y；后6字节11 PSHU D，X，Y；11脉冲D；最后2字节7 PSHU D；7 LEAU-WOFF，U；高级DST PTR 8。

只有66个周期，包括对U的行后调整，为下一行做好准备。(请注意，调整现在为负值。)。作为比较，我们前面看到的简单的行复制循环花了157个周期来做同样的事情。我朋友的优化代码用了98。这个疯狂的想法看起来已经大获全胜了。

不过，最后那对PULS/PSHU！真是一辆破车。它需要处理每行的最后两个字节，因为行是28个像素=14个字节宽，而6不会将14平分。

如果游戏使用的是24x24的瓷砖而不是…就好了。但它没有，所以我仔细阅读了手册，寻找一种方法来降低不可避免的最后一双鞋的成本。

然后，出乎意料的是，我发现了金子！这是另一个6809个奇怪的地方，DP寄存器。

在那个时代的6502和大多数8位处理器上，最低的256字节内存被称为零页。零页是特殊的，因为它的存储位置有单字节地址，并且可以用更短且通常更快的指令来访问。

6809的设计者将这一想法更进一步。它们允许您使用DP寄存器将任何页面指定为零页面，他们称之为“直接页面”。

但是我的字节抛出指令都不需要使用直接页。这意味着我可以使用DP寄存器作为额外的单字节中介。现在我可以复制每个PULL-PUSH对7个字节！

有了这个更改，我可以复制整个28像素行，然后只需5条指令就可以前进到下一行：

脉冲D、X、Y、DP；前7字节12周期PSHU D、X、Y、DP；12脉冲D、X、Y、DP；后7字节12 PSHU D、X、Y、DP；12 Leau-WOFF、U；高级DST PTR 8。

那段代码让我感觉棒极了。我已经设法利用机器上的每个可用寄存器进行字节投掷！D，X，Y，U，S，甚至是古怪的DP-他们都全员参与了。

如果你熟悉STACKS，你可能已经注意到我出色计划中的一个细微缺陷：

你看，我刚才给你看的那小段代码我撒了谎。它实际上并没有将背景磁贴中的一行复制到屏幕上。它实际上所做的是将行分成两个7字节的块-我称之为“七字节”-然后将它们绘制到交换过的屏幕上。

回想一下，平铺行在内存中以14个连续字节的形式合理布局，如下所示：

+---+---+|0 1 2 3 4 5 6 7 8 9 A B C D|+---+---+。

因此，当您以7字节的七位数将一行拖放到屏幕上时，它将被水平拆分，如下所示：

+---+---+|7 8 9 A B C D|0 1 2 3 4 5 6|+---+---+。

第一个七重奏现在是第二个，第二个现在是第一个。但是，请注意，每个Septet中的字节没有改变；它们保留了原来的顺序。

此外，如果多次运行行复制代码，则复制的垂直行堆栈最终会颠倒。这是因为代码使用PUSH将行写入屏幕。按下会将堆栈指针移向较低的地址，较低的地址对应于显示器上较高的屏幕行。

为了直观地描述这种行颠倒和间隔交换将造成的破坏，假设您有以下28 x 28的平铺，表示一个键：

如果您使用我的行复制代码的28个应用程序将其绘制到屏幕上，您最终会得到这个不是键的代码：

突破是将“颠倒”和“互换”视为同一事物的两个实例。反转。

反转有一个方便的属性：它是一个对合。颠倒一件东西两次，你就能拿回原来的东西。考虑到这一点，我推断，如果对瓷砖进行预处理以颠倒它们的行，然后再对行内的七位数进行处理，那么当它们出现在屏幕上时，瓷砖最终看起来会很好。在复制和预处理过程中发生的损坏实际上会相互撤消。

在纸上工作时，我还发现预处理步骤可能会忽略行，而只是将瓷砖视为一个长的、线性的七位数序列。1要了解为什么会这样，让我们考虑一个小块，每行2行，每行2个七位数：

在内存中，它将以行为主的顺序进行布局，即，作为4个连续的七位字节：

因此，颠倒行，然后交换每行中的七位数与仅颠倒内存中的七位数顺序相同：

+--+-++-+-++-+|a b||c d||d c|+--+--+=>；+-+-+=>；+--+-+|c d|反转|a b|交换|b a|+-+-++行+-+--++--+。-++-++-+。

因此，破损问题的解决方案被证明是一个简单的一次性预处理步骤：只需将每个瓷砖分成七个字节，并颠倒它们的顺序。

知道损坏问题可以解决后，我对自己的总体想法感觉很好。我看不到任何其他问题，所以我草拟了一个新的复印平铺子例程来呈现给我的朋友。由于行复制逻辑现在只有5条指令，所以我使用了4次，稍微展开了剩下的唯一循环。现在，我没有复制28个单行，而是复制了7个四行。

COPYTILE3；复制28x28屏幕瓦片到屏幕缓冲区。；参数：；X=*SECTET-反转*背景瓦片的起始地址；Y=屏幕缓冲区目标起始地址；执行时间：；34+7*(224+7+3)+7+10=1689个周期；设置：34个周期PSHS U，DP；保存U和DP(8个周期)STS>；sSave；保存S(7个周期)；；LDA#TILH/4；初始四行计数(2个周期)STA>；ROWCT；(5个周期)；；LEAS，X；Initialize src PTR(4个周期)Leau(TILH-1)*scrw+TILW，Y；Initialize DST PTR(8个周期)；；@COPY1；；在4*(48+8)=224周期脉冲X，Y，D，DP PSHU X，Y，D，DP PSHU X，Y，D，DP LEAU-WOFF，U脉冲X，Y，D，D，DP PSHU X，Y，D，DP PSHU X，U 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。Y，D，DP PSHU X，Y，D，DP PULS X，Y，D，DP PSHU X，Y，D，DP Leau-WOFF，U；；DEC>；ROWCT；将剩余的四行计数减少一(7个周期)BNE@COPY1；保留四行时循环(3个周期)；；LDS&>；sSave；恢复S(7个周期)脉冲U、DP、PC；恢复Regs并返回调用方(10个周期)sSave ZMD 1；绘制时用于保存S的STASH ROWCT ZMB 1；var：要复制的剩余行

把周期加起来，总数只有1689个。我已经将我朋友的代码减少了近1200个周期。那是70%的提速！

当我赶上我的朋友，说我已经想出了如何让复印磁贴例程快70%的时候，他的脸亮了起来。然而，当我解释整个七人组和残缺不全的事情时，他的脸没有露出光芒，怀疑情绪高涨。但当我给他看密码的时候，他拿到了。它一下子就好了。

在大约半个小时的工作中，他将代码集成到了游戏中。重建并重新启动后，游戏正在加载。

比赛似乎快得令人吃惊。事实上，它可能只快了三分之一到一半，但这已经足够了。一些重要的感知门槛已经被越过了。游戏现在进行得很顺利，很自然。你可以感觉到不同之处。

在速度问题过去几天后--或者我们是这么认为的--游戏的收尾工作就开始了。这些最后的润色之一是采样音效。这需要每秒将字节大小的片段馈送到音频输出DAC几千次。为了安排进食时间，我的朋友打开了硬件计时中断。

一天晚上玩完游戏后，我们注意到一些瓷砖被损坏了。我们玩得越多，我们看到的腐败就越多。

为了准备调用中断处理程序，处理器会将其当前状态推送到系统堆栈上。但是，在复制磁贴例程期间，没有系统堆栈。系统堆栈寄存器S已被征用。它指的是哪里？直接进入保存引用磁贴的内存缓冲区！

我们坠落了。在做了这么多努力之后，我想我们最重要的加速是导致内存损坏的…

需要休息一下，我们步行到校园附近的一家通宵用餐店吃饭和思考。我们一边吃着煎饼和培根，一边刮刮着烤肉条，一边讨论着这个问题。

只有两个堆栈寄存器，如果不征用这两个寄存器，复制磁贴例程就不会那么快。因此，不可能在不损失来之不易的速度的情况下将S寄存器返回系统。摇滚。但是，如果不使用中断，我们也不可能获得可靠的声音。艰难的境地。

不管怎样，中断都会被触发。而且，当它们运行时，如果复印磁贴正在运行，那么S指向的任何东西都会被重击。

“不要阻止。

.