有哪个高手可以解读“世界黑客编程大赛第一名的作品（97年Mekka ’97 4K Intro）”? 第1页

supersodasea 网友的相关建议:

TL;DR：已经对该程序完全的解读并用 Javascript 完成复刻，想玩的话可以直接点下面的链接进行体验。理论上手机上也可以运行。（点击画面开始运行，含音乐）

初中的时候曾经看到过这个程序，当时教室里电脑装的还是 Windows XP，可以直接通过网上流传的 debug 脚本运行这段程序，当时惊叹于它体积之小，好奇它的实现原理，曾经试图进行过逆向，奈何当年水平不够，也没有搜索到详解，遂作罢。一周前看到这个问题，但依然没有人正面给出完整的解析，于是重新点燃了兴趣，趁着国庆假期完整地逆向了一遍，并用 Javascript 按同样的逻辑复刻了一遍。

首先是对几种流言的澄清：

首先是流传甚广的“Mekka ’97 4K Intro”这个名字——实际上这是比赛的名字而不是程序的名字，这个程序“Omniscent”是 Mekka & Symposium 1997 比赛 PC 4K 组的第一名。这个比赛还有各种其他类似的有趣 Demo，有兴趣的可以了解一下。
这个程序调用了 DirectX 进行绘制——那肯定是假的，DOS 哪来的 DirectX……
这个程序的纹理使用了系统内置的资源——也是假的，实际上程序内使用的纹理都是运行时生成的。唯一可以说是用了系统资源的就是上下两行字……

再来大致介绍一下这个程序的各种细节（逆向到一半才看到开发者写的文档，和实际情况基本上是吻合的。详细细节可以参考我的复刻代码。）：

压缩部分：

原始程序大小为 4095 字节。
使用 161 字节的代码将后面的 4095 - 163 = 3932 字节的数据解压为 4782 字节，然后跳转执行。
作者声称使用的是“LZSS77”算法进行压缩，不过更常见的叫法应该是去掉77的“LZSS”。
运行中实际占用的内存为 272KiB。

时间部分：

将 PIT 设置为 1000 / 350 ≈ 2.86ms 触发一次，各种计数器都由时钟中断驱动。所以即使画面出现卡顿也不会出现音画不同步的现象。

音乐部分：

直接通过写端口的方式对 MPU-401 这个 MIDI 设备进行操作。初始化之后就是标准的 MIDI 命令流了，于是加了 jzz-synth-tiny 这个包就能在浏览器里播放音乐了。
包含四个 MIDI 通道的数据，数据简单来说是每两个字节为一个音符，前一个字节为音高，后一个字节为时长（以 1000 / 350 * 29 ≈ 82.86ms 为单位）。如果下一个字节为负数则表示开始循环，循环次数为这个负数的绝对值；下一个字节为零则表示结束循环或者结束该通道的数据。循环可以嵌套，程序内是使用递归实现的。

纹理部分：

程序使用的是 320*200*8位（256色）模式，调色盘是程序运行时插值生成的，如下所示。

程序使用了 15 张纹理，大小均为 64*64——实际上算上生成时的应该有20张纹理，如下所示。

随机数是用 LCG 生成的，参数为。随机种子为固定的 4347，所以每次运行生成的贴图都是固定的（通过结尾处背景的星星可以比较明显地观察出）。
纹理16和17（纹理编号是从0开始编号，下同）是通过在随机位置叠加一堆圆形生成的，如果放大看的画应该还是能看出有圆形的痕迹的。纹理16和17分别是半径为15的圆随机112次，和半径为5的圆随机800次。这种噪音生成方式竟然看起来还不错？
纹理18是先将第1行填充为 0x14，然后对从第2行开始，每个点的颜色等于它上方和右上方的颜色的平均值加一个随机数扰动，所以看起来有倾斜方向的纹路。
纹理19就是纯粹的随机撒了 4096 次点……
在生成好噪音纹理后，将这4张噪音纹理复制到2~15号纹理的存储空间中，并加上不同的偏移量，就形成了五颜六色但仔细看却是重复的14张纹理。
然后对这些纹理加上图案（其实就是一系列矩形填充）。填充有三种模式：覆盖原来的值（例如纹理3的灯），在原来的贴图上加上一个偏移量（例如纹理12的上下两道深色部分），以及覆盖为黄黑相间的斜条纹（例如纹理14、15）。
纹理11下方的红色过度也是随机撒点，颜色和次数随高度递减。
纹理2的岩浆在运行的时候颜色是会变换的。这个实际上靠的是对调色盘的 0xC0-0xDF 这段从红到黄再到红的渐变进行“循环位移”来实现的。
纹理0是单独生成的，不过这个图案很简单，相信有一定数学基础的人能够自己想出生成的公式。
贴图1是每 1000 / 350 * 8 ≈ 22.86ms 更新一次，在预先随机好的30个位置绘制亮度随时间变化的 5*5 图案。注意这个图案和最后星空的图案是重复使用的。
除此之外就是 Demo 末尾的开门动画，会在开门的时候复制纹理15到纹理13的不同位置做到开门的效果，中间部分填 0x00（软光栅遇到颜色 0x00 的时候会当作透明）。
画面上下的文字：通过 int 0x10 中断在恰当位置绘制后，将帧缓冲中的每个字节复制成两份，实现了横竖都放大两倍的效果（所以文字中间才会有黑线，因为实际上是一行变成了两行，下面的一行是原来那行的右边部分，自然是黑色的。

场景部分：

模型的基本单位为四边形，场景使用一系列立方体拼成，模型数据包括当前位置六个面的纹理（每个面用4位表示，0代表当前面为空，剩下15个值对应15个纹理），以及下一步的移动方向，带一点简单的旋转。一共有362个顶点和367个四边形。重复的顶点会复用，所以四边形的数量和顶点的数量差不多。用上帝视角看的话，场景的这个样子的（外部和内部，这里是使用WebGL画的）：

光栅化部分：

在自己分配的缓冲区中进行绘制，完成绘制后整个复制到位于 0xA0000 处的显存中。
使用的是正统的光栅化算法，而不是光线跟踪。毕竟场景不像那些 256 字节的Demo那样简单。
预先对顶点处理好摄像机的旋转和移动，然后再进行光栅化。
顺带一提，摄像头的更新频率是 1000 / 350 * 8 = 22.86ms，所以实际上性能最优情况下“帧率”是 43.75 帧/s。
没有Z缓冲区，而是按四个顶点变换后的Z轴值之和排序（里面有段快速排序），用画家算法从远到近绘制。
用约 1119 字节实现了完整的视锥裁剪+透视矫正+多边形扫描线光栅化！还带光照和线性雾！（虽然光照是用顶点色实现的）可以说是这段程序里最复杂的一部分了。具体逻辑可以参考我的复刻代码。
视锥裁剪实际上只是使用near平面进行裁剪，将四边形裁剪为三~五边型。
观察一下调色盘，可以发现前面有6组从暗变亮的颜色。所以光照和雾效是怎么实现的也就不言而喻了吧。（实际上预处理了一个 128 * 256 的LUT，两个维度分别是亮度和颜色。亮度是由顶点色和一个与顶点的Z值相关的值的乘积决定的。）
顺带一提，里面用到了一个小技巧，就是较小的32位正整数可以当作32位非规格化浮点数来运算，可以互相加减或者乘除普通的浮点数。这个技巧节省了一些代码。

实际上在逆向代码的过程中也没有遇到太大的麻烦，代码的逻辑也比较清晰，也没用特别花里胡哨的地方，就是最后光栅化时各种浮点指令看的稍微有点头疼。

关于实现的难度：这段程序肯定不是一句轻描淡写的“简单”能够解释的。写出这个程序需要扎实的计算机图形学知识，x86汇编知识（值得一提的是里面大量使用了不带rep前缀的lods/stos/movs），还需要一些创造力（当然，根据开发者的文档，这个程序是由好几个人合作完成的）。虽然这段程序还算得上是地球人能理解的范畴（笑），但这次的逆向过程不禁让我对那群23年前那群有趣的前辈肃然起敬。必可活用于下一次.jpg

最后来欣赏一下复刻版本的一些截图，特别是最后一张图背景星星的位置也和原版完全一致，可以说是“像素级复刻”了。

最后来个彩蛋：这个 Demo 的场景实际上致敬了 1994 年的游戏《Descent》（天旋地转），我特意用 DOSBox 体验了一下。（然后马上晕3D了……）下面是几张第一关的截图：

skywind3000 网友的相关建议:

这种代码我也写过，1KB 大小的空战游戏，很久以前读书时闲着蛋疼写的：

WINXP下（或者DOSBOX:D-Fend Reloaded）在DOS窗口中运行DEBUG，然后把横线下的内容复制、粘贴到DEBUG窗口中，回车就可以见到了。

       -------------------------------------------------------------------- e100 e8 5f 0 e8 4c 1 e8 ed 0 b8 0 4c cd 20 f f 0 8 7 1 7 1 6 7 7 1 0 f 1 0 0 e11f 0 fe c2 cb c4 c1 8a d3 c5 df 8a cc c5 d8 8a da c6 cb d3 c3 c4 cd 86 8a e137 c8 d3 8a d9 c1 d3 dd c3 c4 ce 99 9a 9a 9a ea c2 c5 de c7 cb c3 c6 84 c9 e14f c5 c7 a7 a0 0 87 97 8a ef f2 ec e5 f8 e9 ef 8a 97 87 0 66 60 b8 0 11 a3 e168 e 1 5 80 bb a3 16 1 5 0 1 a3 10 1 5 80 0 a3 12 1 5 10 2 a3 14 1 8b 3e 10 e185 1 fc b9 80 2 33 c0 f3 aa 1e 33 c0 8e d8 8e c0 be 24 0 66 ad 1f 66 a3 18 e19e 1 8c c8 66 c1 e0 10 b8 1d 2 bf 24 0 fa 66 ab b0 34 e6 43 b8 87 0 e6 40 e1b7 8a c4 e6 40 fb 66 33 c0 1e 7 b8 13 0 cd 10 be 7e 3 bb 0 0 8b 3e 16 1 ac e1d1 3c c0 73 4 aa 43 eb 9 24 3f 50 ac 59 f3 aa 43 43 80 fb 9b 72 e9 33 c0 cd e1ea 1a 81 e2 ff 7f 89 16 1c 1 66 61 c3 33 c0 8e c0 66 a1 18 1 bf 24 0 fa 66 e203 ab b0 34 e6 43 33 c0 e6 40 e6 40 fb 66 33 c0 b8 3 0 cd 10 1e 7 e8 4d 0 e21c c3 60 1e 6 8c c8 8e d8 8e c0 33 c0 e4 60 8b c8 83 e1 7f 8b 1e 10 1 3 d9 e235 24 80 f6 d0 c1 e8 7 88 7 e4 61 c 80 e6 61 24 7f e6 61 b0 20 e6 20 7 1f e24e 61 cf c3 c3 60 b4 2 b7 0 ba d 0 cd 10 b3 3 be 54 1 e8 9 1 61 e8 b1 1 c3 e269 be 20 1 e8 fe 0 33 c0 cd 16 c3 60 8b 36 e 1 bf 40 1f b9 c0 5d fc b8 0 a0 e283 8e c0 f3 a5 e 7 61 c3 60 8b 3e e 1 b9 c0 5d e 7 33 c0 fc f3 ab 61 c3 c8 e29d 0 0 0 60 8b 4e 4 8b 56 6 8a 46 8 81 f9 40 1 73 1a 81 fa 96 0 73 14 8b 3e e2b8 e 1 8b da c1 e2 8 c1 e3 6 3 da 3 d9 3 fb 88 5 61 c9 c3 c8 2 0 0 60 8b 1e e2d4 16 1 ba 0 0 83 6e 4 8 83 6e 6 8 c7 46 fe f 0 b9 0 0 33 c0 8a 7 43 3c 0 e2f0 74 1e 50 8b 46 6 83 7e 8 0 74 4 3 c2 eb 3 3 46 fe 50 8b 46 4 3 c1 50 e8 e30b 8f ff 83 c4 6 41 83 f9 10 72 d3 ff 4e fe 42 83 fa 10 72 c7 8b 4e 4 8b 56 e324 6 61 c9 c3 c8 0 0 0 52 66 a1 1c 1 66 69 c0 35 4e 5a 1 66 40 66 a3 1c 1 e33e 66 c1 e8 10 66 25 ff 7f 0 0 99 f7 7e 4 8b c2 5a c9 c3 c8 0 0 0 8b 1e 12 e358 1 b9 20 0 b8 0 0 83 3f 0 74 7 83 c3 10 40 49 75 f4 c9 c3 fc ac 3c 0 74 a e373 b4 e 34 aa 60 cd 10 61 eb f1 c3 c3 0 1d 19 c4 0 19 1d c1 c4 c7 0 c2 19 e38c c4 0 19 0 c1 c4 c4 0 c2 70 0 19 c1 c4 c2 28 1d c2 70 28 70 0 c3 70 c2 28 e3a6 c2 70 c2 28 c2 19 70 c2 28 c6 70 28 70 19 c2 28 c3 70 c2 28 19 28 c2 70 e3be c2 0 c2 70 19 c3 28 70 c3 28 19 28 70 c4 0 70 19 28 70 28 c3 70 28 19 70 e3d7 c6 0 1d 70 0 28 0 70 0 70 1d c7 0 1d 70 0 28 36 70 0 70 1d c7 0 1d c2 0 e3f2 28 36 70 c2 0 1d c9 0 28 70 19 c2 70 cb 0 28 70 19 c2 70 cb 0 28 c4 70 e40b cc 0 28 c2 70 cd 0 28 19 cf 0 70 c8 0 c8 32 0 0 56 57 c7 46 fe 9c 2 c7 e425 46 fc cd 2 c7 46 fa 28 3 c7 46 f8 51 3 c6 46 f1 1 c6 46 f0 0 c6 46 ef 0 e43f 66 c7 46 e8 0 0 0 0 c7 46 e2 a0 0 c7 46 e0 78 0 c7 46 d2 0 0 c7 46 ce 0 e45a 0 a1 10 1 89 46 ec a1 14 1 89 46 f6 a1 12 1 89 46 f4 c7 46 de 0 0 8b 76 e474 f6 eb 38 68 40 1 ff 56 fa 59 89 4 68 c8 0 ff 56 fa 59 5 ce ff 89 44 2 83 e48e 7e de 35 7d c c7 44 4 1 0 c7 44 6 17 0 eb a c7 44 4 2 0 c7 44 6 1c 0 ff e4aa 46 de 83 c6 8 83 7e de 50 7c c2 e9 94 3 66 8b 46 e8 66 89 46 e4 eb 14 66 e4c3 60 33 c0 cd 1a 8b c1 66 c1 e0 10 8b c2 66 89 46 e4 66 61 66 8b 46 e4 66 e4db 2b 46 e8 66 83 f8 c 72 de 66 8b 46 e4 66 89 46 e8 b8 8b 2 ff d0 c7 46 de e4f4 50 0 8b 76 f6 eb 36 8a 44 6 50 ff 74 2 ff 34 ff 56 fe 83 c4 6 8b 44 4 1 e50e 44 2 81 7c 2 96 0 7e 14 68 40 1 ff 56 fa 59 89 4 6a 3c ff 56 fa 59 f7 d8 e528 89 44 2 ff 4e de 83 c6 8 83 7e de 0 75 c4 8b 5e ec 80 7f 4b 0 74 f 83 6e e542 e2 2 83 7e e2 0 7d 5 c7 46 e2 0 0 8b 5e ec 80 7f 4d 0 74 10 83 46 e2 2 e55c 81 7e e2 40 1 7e 5 c7 46 e2 40 1 8b 5e ec 80 7f 48 0 74 f 83 6e e0 3 83 e576 7e e0 0 7d 5 c7 46 e0 0 0 8b 5e ec 80 7f 50 0 74 10 83 46 e0 2 81 7e e0 e590 96 0 7e 5 c7 46 e0 96 0 8b 5e ec 80 7f 1 0 74 3 e9 b0 2 8b 5e ec 80 7f e5aa 1d 0 74 33 80 7e f0 0 75 31 c6 46 f0 1 ff 56 f8 c1 e0 4 8b 7e f4 3 f8 80 e5c4 7e ef 2 7d 1c fe 46 ef c7 5 2 0 8b 46 e2 89 45 8 8b 46 e0 5 f7 ff 89 45 e5de a eb 4 c6 46 f0 0 c7 46 de 0 0 8b 7e f4 e9 a3 1 8b 45 8 89 46 d6 8b 45 a e5f9 89 46 d4 8b 5 89 46 d0 3d 1 0 74 b 3d 2 0 75 3 e9 a7 0 e9 6b 1 83 7d 2 0 e615 74 6d 8b 46 d6 2b 46 e2 89 46 da 83 7e da 0 7d 5 f7 d8 89 46 da 8b 46 d4 e62e 2b 46 e0 89 46 d8 83 7e d8 0 7d 5 f7 d8 89 46 d8 83 7e da d 7d a 83 7e e647 d8 d 7d 4 c6 46 f1 0 6a 2 ff 56 fa 59 40 1 46 d4 81 7e d4 a0 0 7e 5 c7 e661 46 d0 0 0 6a 8 ff 56 fa 59 b c0 75 25 8b 46 d6 3b 46 e2 7e 5 b8 ff ff eb e67b 3 b8 1 0 1 46 d6 eb 10 ff 45 4 8b 45 4 3d 28 0 7e 5 c7 46 d0 0 0 8b 45 2 e697 8b 55 4 83 e2 1 b c2 75 3 e9 d8 0 6a 1 ff 76 d4 ff 76 d6 ff 56 fc 83 c4 e6b1 6 e9 c7 0 8b 46 d4 5 fb ff 89 46 dc eb 27 6a 9 ff 76 dc 8b 46 d6 5 fb ff e6cb 50 ff 56 fe 83 c4 6 6a 9 ff 76 dc 8b 46 d6 5 3 0 50 ff 56 fe 83 c4 6 ff e6e5 46 dc 8b 46 d4 5 5 0 3b 46 dc 7f ce 83 6e d4 4 83 7e d4 ec 7d 8 c7 46 d0 e6ff 0 0 fe 4e ef c7 46 dc 0 0 8b 46 f4 89 46 f2 eb 65 8b 5e f2 83 3f 1 75 56 e719 83 7f 2 1 75 50 83 7e d0 0 74 4a 8b 46 d6 2b 47 8 89 46 da 83 7e da 0 7d e733 5 f7 d8 89 46 da 8b 5e f2 8b 46 d4 2b 47 a 89 46 d8 83 7e d8 0 7d 5 f7 e74c d8 89 46 d8 83 7e da f 7d 19 83 7e d8 f 7d 13 8b 5e f2 c7 47 2 0 0 c7 46 e766 d0 0 0 fe 4e ef ff 46 ce ff 46 dc 83 46 f2 10 83 7e dc 20 7c 95 8b 46 d6 e77f 89 45 8 8b 46 d4 89 45 a 8b 46 d0 89 5 ff 46 de 83 c7 10 83 7e de 20 7d e798 3 e9 54 fe 6a 14 ff 56 fa 59 b c0 75 3b ff 56 f8 c1 e0 4 8b 56 f4 3 d0 e7b1 89 56 f2 8b 5e f2 c7 7 1 0 c7 47 2 1 0 c7 47 4 0 0 68 40 1 ff 56 fa 59 e7cc 8b 5e f2 89 47 8 6a a ff 56 fa 59 5 ec ff 8b 5e f2 89 47 a b8 96 0 2b 46 e7e6 ce 89 46 d4 83 7e d4 0 7d 5 c7 46 d4 0 0 8b 46 d4 89 46 de eb 11 6a 4 ff e800 76 de 68 3f 1 ff 56 fe 83 c4 6 ff 46 de 81 7e de 96 0 7c e8 81 7e d2 8c e819 0 7d f c6 46 f1 1 8b 46 d2 25 1 0 89 46 da eb 5 c7 46 da 1 0 83 7e da 0 e834 74 e 6a 0 ff 76 e0 ff 76 e2 ff 56 fc 83 c4 6 b8 74 2 ff d0 ff 46 d2 80 e84d 7e f1 0 74 3 e9 63 fc 80 7e f1 0 75 2e 66 8b 46 e8 66 89 46 e4 eb 14 66 e866 60 33 c0 cd 1a 8b c1 66 c1 e0 10 8b c2 66 89 46 e4 66 61 66 8b 46 e4 66 e87e 2b 46 e8 66 3d d0 2 0 0 72 dc 5f 5e c9 c3 ff 53 4b 59 57 49 4e 44 30 35 g --------------------------------------------------------------------

游戏运行于DOS环境，用方向键控制飞机位置，CTRL发射激光，

如果运行在WINXP下面，粘贴操作只需要点击DEBUG窗口的图标，选“编辑”即可。

我 2004年实现的竖版空战射击游戏，整个代码 1K以内。

Win7/10 下 DosBox的用法（没有 WinXP和 VmWare时）：

下载安装 D-Fend Reloaded 最新版（带GUI和 FreeDOS 的DosBox）并运行
复制游戏代码（横线中内容）保存到 C:Users用户名D-Fend ReloadedVirtualHDgame.txt
双击 D-Fend Reloaded窗口中的 DosBox，启动DosBox窗口
按CTRL_F12将CPU Speed调到10000以上
输入命令：debug < C:game.txt，按回车启动游戏

原理：

使用 COM 文件，结构更紧凑。
16 位汇编代码：使用 MASM 编译。
资源：主要是飞机图片，用 RLE 压缩，星空和子弹是程序代码绘制的，不占用资源。
字体：字体使用 BIOS 内嵌 8x16 点阵字体，有个固定内存地址可以访问到。
绘图：双缓冲，先在内存中绘制，然后 memcpy 拷贝到显存 0xa000:0000 处。
控制：接管键盘中断 Int9，键盘按下或者放开时触发，内部维护一个数组，代表某键是否按下。
音效：PC Speaker，写 0x61 端口控制频率。
逻辑：尽量往精简写。

那么是否能用很短的代码实现游戏逻辑呢？可以的，只要你实现的足够精简即可。

源代码呢？哪天等我翻翻老家电脑，找到的话我贴出来。

出门右转：

256字节3D程序是如何实现3D引擎的呢？

有哪个高手可以解读“世界黑客编程大赛第一名的作品（97年Mekka ’97 4K Intro）”? 的其他答案点击这里

有哪个高手可以解读“世界黑客编程大赛第一名的作品（97年Mekka ’97 4K Intro）”? 第1页

相关话题

前一个讨论

下一个讨论

相关的话题