Last week I asked Claude whether Unreal Tournament could run on the Nokia 9500. The answer was no: a 150 MHz ARM9, no floating-point hardware and no source code. Quake 1, on the other hand, has its source under the GPL, and somebody had already got it to about 10 fps on an iPod Classic.
So now there's Quake9500: the whole game, software rendered, with sound, saves and the full menu, on the Communicator's 640×200 screen. As with NES9500, the code was written by Claude (Anthropic's AI). I built it on my Windows 2000 VM, ran it on the phone, sent back logs and complained. The first build that reached a level ran at about 3 fps. The timedemo now runs at 13.6 fps at full screen height, and it fits in a SIS of about 210 KB, game data not included.
This post is about how it got there. It gets geekier than the NES one, because Quake fights back.
The patient
Here's the machine, as the game's own log sees it:
HAL display: mode 0, 640x200, 16 bpp HAL display: memory 0x59912000, first pixel +32, line 1280 bytes Base directory D:/Quake, hunk 12288 KB, 7740 KB RAM free Video: 320x200 on a 640x200 screen, aspect 2,00, surface cache 600 KB
The CPU is an ARM925T with an 8 KB data cache, no FPU and no divide instruction. Every float operation is a function call, and so is every integer divide. Quake was written for the Pentium and leans hard on its FPU. The SDK's compiler is GCC 2.9-psion-98r2, so everything is C89.
Where the code comes from
Unlike NES9500, this one is a port with a long family tree. id Software released the source under the GPL, SDLQuake put it on SDL, Dan East's Pocket Quake added fixed-point paths to the renderer for PocketPCs, and Rockbox added ARM fixes for unaligned reads of map and model data. Rockbox gets about 10 fps on a 216 MHz iPod Classic. Quake9500 starts from Rockbox's tree at commit d54b9e6f, throws out SDL and Rockbox, and adds these:
| File | Lines | What it does |
|---|---|---|
sys_epoc.c | 767 | Main loop, files, clock, the log, the frame time report |
vid_epoc.c | 197 | Video driver: buffers, palette, handing frames to the blit |
snd_epoc.c | 132 | Sound driver: Quake's DMA ring, emptied by the audio thread |
softfloat.c | 1411 | Our own float helpers and integer divides, with ARM assembly fast paths |
armrt.c | 171 | 64-bit helpers that egcc.lib lacks |
epocsys.cpp | 899 | Native layer from Doom9500: window, framebuffer, blit loops, keys, exception handler |
epocaudio.cpp | 345 | Audio thread feeding CMdaAudioOutputStream |
On top of that, 46 of the original files changed, for about 2800 changed lines in a diff. The heaviest are r_alias.c and r_draw.c.
Sound was a step backwards on purpose: id's original mixer is back. Rockbox mixed inside the SDL audio callback and needed mutexes everywhere. Now all Quake code runs on the game thread, and the audio thread only copies from the ring and plays silence for anything not mixed yet. The log from a real play session says 3795 chunks mixed, 1 underflows, 0 write errors.
Quake's 2D art is 320×200, doubled across. The menu comes out very wide.
Ways to kill a Communicator
The first days went into crashes, and some of them were spectacular.
- Stack overflow reboots the phone. Quake likes big local arrays: 128 KB for the pak directory, about 130 KB for the edge and surface lists, 64 KB for the warp buffer. On Symbian an overflow takes the whole phone down. All of them are static now, and
EPOCSTACKSIZEis 80 KB. - Software floats that trap. Symbian's float helpers raise exceptions where a PC returns NaN or infinity.
CalcFovdoes a 0/0 before the view size is set. A handler installed withRThread().SetExceptionHandlernow counts float errors and logs real faults with the QuakeC function and the entity it was working on. - A bug from 1996. An alias model frame's bounding box doesn't always hold all its vertices. The crucified zombie in
start.bsphas one at y = −2, andD_PolysetDrawFinalVertsthen indexes its row table with a negative number. Models with any vertex outside the view now take the clipped path.
3.2 to 1
Quake renders 320×200 and each pixel is doubled across, so a game pixel is twice as wide as it is tall. That's vid.aspect 2.0, and the picture keeps its true proportions. The catch is that the view is 3.2:1. With the usual 90° across, you only see about 35° up and down.
Top: true proportions, the default. Bottom: -aspect 0.83, the vertical field of a PC squeezed into the same 200 rows. You see more of the room, and everyone in it is squashed.
This aspect also broke things. Pocket Quake's 9.23 fixed-point x and y scales overflowed at 2:1 and drew grey bars across the view, so they're 10.22 now. It wasn't the last time this screen shape caused trouble.
The speed hunt
The first number I believed was 7.4 fps in timedemo demo1. Earlier builds reported 12, but they were drawing a broken world, which turns out to be faster.
Every point is a line from the quakelog.txt the phone wrote, like 969 frames 71,5 seconds 13,6 fps. Repeats and test runs are left out.
The first tool was a sampling profiler, and it lied. It put 19% of the time right after the blit, where the wall clock measured 0.1 ms. So it was replaced by timing every part of the frame with the clock: start with -parts and the timedemo writes this at the end. One of these came back after every build. This is the last full one:
Frame times, timedemo: 970 frames, 74.1 ms each
(fl = software float operations, div = integer divides, per frame)
0.3 ms 55 fl 0 div input, commands, server
2.7 ms 1154 fl 0 div client read
3D view, of which:
1.8 ms 1316 fl 19 div view setup, mark leaves
9.7 ms 2193 fl 688 div BSP walk, edges
4.9 ms 5426 fl 75 div brush models (doors, lifts)
5.4 ms 1988 fl 0 div edge scan
3.4 ms 2613 fl 23 div surface cache (lighting)
4.0 ms 4408 fl 0 div surfaces: mip level, gradients, rotation
10.8 ms 759 fl 0 div texture spans
2.3 ms 634 fl 0 div z spans
2.2 ms 1734 fl 55 div sky, water, the rest of the surfaces
2.4 ms 2441 fl 4 div alias models: bounding box
0.8 ms 743 fl 0 div alias models: light point
4.1 ms 4495 fl 298 div alias models: setup, transform; sprites
6.8 ms 1846 fl 1419 div alias models: triangles (also the view model's)
0.0 ms 0 fl 0 div view model: the rest
2.2 ms 2053 fl 100 div particles
1.5 ms 7 fl 0 div lowres row doubling
0.0 ms 1 fl 0 div the rest
0.3 ms 41 fl 1 div 2D and palette
7.7 ms 1 fl 0 div blit
0.1 ms 76 fl 0 div sound, rest of the frame
Half-height 3D. The biggest single win is a cheat. With r_lowres 1 the 3D view is drawn at 320×100 into every other row, and each row is then copied into the one below it. A game pixel is now as tall as it is wide, and there's half as much to draw. That took the timedemo from 8.1 to 9.9 fps, and I liked the look enough to make it the default.
Left: r_lowres 1. Right: r_lowres 0. Both zoomed 2×.
Our own soft float. GCC's float helpers on this SDK come from EUSER.DLL and go through Symbian's 96-bit TRealX. softfloat.c replaces __addsf3, __mulsf3 and the rest, with ARMv4 assembly fast paths that give up to C on anything unusual. How do you test hand-written ARM assembly on a PC? tools/armtest.py is a small ARMv4 interpreter that reads the assembly strings straight out of softfloat.c and runs them against a Python mirror, which is itself checked against exact fractions. Zero failures. The result on the phone: 9.9 to 10.2 fps. A small gain, so floats weren't the big lever.
Our own divides. Same treatment for __udivsi3: binary search for the top bit, then a computed jump into a chain of three instructions per bit. No speed change at all, libgcc's was already that good. But counting the calls gave us a new number: 21,661 integer divides per frame.
The divide that should have been a multiply. Most of those came from Pocket Quake's fixed-point edge code, which "multiplies" by dividing by a reciprocal:
transformed_fxp[0] = local_fxp[0]/vright_fxp[0]+local_fxp[1]/vright_fxp[1]+local_fxp[2]/vright_fxp[2];
That's 11 divides per vertex and 6 per clip-plane test, on a CPU with no divide instruction. It does have smull, which gives the high word of a 32×32 product and costs next to nothing:
transformed_fxp[0] = MulHi(local_fxp[0],vright_mul[0])+MulHi(local_fxp[1],vright_mul[1])+MulHi(local_fxp[2],vright_mul[2]);
BSP walk and edges went from 18.7 to 10.9 ms and from 12,614 divides per frame to 600. It's also more accurate: the worst projection error dropped from 0.8 to 0.03 pixels.
Spans without divides. D_DrawSpans8 did two divides per 16 pixels for perspective correction. Now it normalises 1/z, looks up a 256-entry reciprocal table and refines it with one Newton step:
r = span_rtab[(d >> 22) & 255]; e = UMulHi (d, r); // d*r/2^60 = 1 - error, as 2^28 r = UMulHi (r, 0x20000000u - e) << 4; // r * (2 - d*r)
A Python check put the error at 0.004 of a texel, and the timedemo went from 11.0 to 11.4 fps.
Models and particles. Alias models got a fixed-point transform (a 16.16 matrix, smull, one 231/z per vertex), a fixed-point bounding box test with 64-bit edge compares, a matrix cached per entity per frame and a light point cache. AngleVectors reads a 16384-step sine table, because the SDK's double-precision sin and cos are slow. Particles went fixed-point too, from 4.7 to 2.3 ms. Together that's worth close to 2 fps.
A compiler bug. After the fixed-point bounding box went in, more models took the slow clipped path, and we couldn't see why. r_bboxfx 2 ran both tests and logged every disagreement. The fixed-point boxes were fine, and the float ones were nonsense: the grenade launcher pickup had a box like a 10-unit stick, and ogres had boxes pointing down. The float test had been wrongly rejecting models that should have been drawn. The culprit is this perfectly ordinary line from id's code, which GCC 2.9 gets wrong with soft floats:
basepts[0][0] = basepts[1][0] = basepts[2][0] = basepts[3][0] =
(float)pframedesc->bboxmin.v[0];
Written out one value at a time, every disagreement disappeared from the log. The same pattern got split up in sv_move.c, sv_user.c and world.c, just in case.
The log file. My bug report said "Huuuuuuge lag in the beginning when picking up stuff". "You got the shells" goes to the console, and the console went to quakelog.txt with an fopen, an append and an fclose on the memory card, for every line. The log now goes to an 8 KB RAM buffer once the game is running. "Client read" went from 7.8 to 2.6 ms, the jitter vanished, and together with the bounding box fix that was the jump from 12.5 to 13.7 fps. It's the best return on effort in the whole project.
The blit. Each 8-bit pixel has to become two 16-bit ones. A second palette table holds every colour already doubled in a 32-bit word, so the loop is an and, a load with a scaled index and a four-word store:
"ldr r7, [%0], #4\n\t"
"and r4, r7, #0xff\n\t"
"ldr r4, [%3, r4, lsl #2]\n\t"
"and r5, r7, #0xff00\n\t"
"ldr r5, [%3, r5, lsr #6]\n\t"
"and r6, r7, #0xff0000\n\t"
"ldr r6, [%3, r6, lsr #14]\n\t"
"mov r7, r7, lsr #24\n\t"
"ldr r7, [%3, r7, lsl #2]\n\t"
"stmia %1!, {r4, r5, r6, r7}\n\t"
That took it from 9.3 to 7.7 ms. Two cleverer ideas gave nothing: looking up each doubled row only once, and skipping rows that hadn't changed. The limit is writing 256 KB per frame to screen memory, at about 34 MB/s.
Coarser mips. d_mipscale 2 picks the next smaller texture one step earlier. The surface cache went from 4.3 to 2.8 ms, and the timedemo from 14.7 to 15.0 fps.
Top: d_mipscale 1. Bottom: d_mipscale 2, the default. This is the worst wall I could find, and on a monitor the bigger blocks are easy to see. My verdict on the phone was "Not blurry at all!"
Knowing when to stop. A per-plane cache of the 1/z gradients cut the floats in the BSP walk from 3256 to 1945 per frame, and the time didn't move at all. One software float operation costs about 30–40 cycles, so removing more of them is close to pointless. What's left is integer work and memory: texture spans take around 30 cycles per pixel, most likely cache misses on texels in that 8 KB data cache.
Killing the status bar
The status bar takes 48 of the 200 rows, which hurts on this screen. It's gone, as in Doom9500. The 3D view always gets the whole height, and H draws the bar over the view when you want to know how much health you have left.
Without the bar and with it.
The key is bound with a new bindifunbound h togglestats after quake.rc, because default.cfg does an unbindall, and a plain bind would overrule your config. And since nearly any key during a demo opens the menu, keys.c now makes an exception for that one. Drawing 200 rows instead of 152 costs speed: the timedemo fell from 15.0 to 13.2 fps. Removing the dirty-row blit, which had nothing left to skip, brought back 13.6. That dip in the chart is one I chose on purpose.
The map called ",000000"
Saving took a very long time, and then this happened on loading:
Loading game from D:/Quake/id1/s0.sav... FindFile: can't find maps/,000000.bsp Couldn't spawn server maps/,000000.bsp Couldn't load map load failed.
The phone is set to Finnish, and the C library's printf follows the locale: "%f" writes something like 4096,000000. Its fscanf doesn't, and reads a %f only up to the comma. So the first number stopped at the comma, every later %f failed on it, and when the code then asked for the map name, it got the leftover ,000000.
There's now a small Q_ftoa that always writes a point and doesn't go through the library's slow float formatting. The loader reads numbers as words and parses them with Q_atof, which accepts both, so older saves should load too.
The slowness was id's code being careful: a fflush after every entity, several hundred times per save, on top of the library's 1 KB buffer. A 256 KB setvbuf and no flushes means the whole file goes to the card in one write.
While I was complaining, the volume got fixed too. The slider was linear, so its lowest step was only 20 dB down. It's now 5 dB per step, which makes 0.1 about −45 dB, and full volume is as loud as before.
The gun below the screen
Then I actually played it, and noticed that the axe was almost off the screen and the shotgun wasn't there at all. That's the screen shape again. Quake's weapons sit below the line of sight, and a PC's default view (320×152 at pixel aspect 0.83) sees about 59° up and down. Ours sees 35°, so the gun is simply below the bottom edge. A timedemo doesn't complain about that.
The fix gives the gun its own projection. All the alias code reads the scale and the centre from globals at draw time, so R_DrawViewModel swaps them while it draws the gun. fit makes the gun look as it does on the PC's view, fitted to our height. That looked small on such a wide screen, so r_gunscale (default 1.4) then grows it upwards from the bottom edge:
fit = verticalFieldOfView * (1.0f / GUN_PC_VFOV); // 0.625 / 1.14
if (size > 0 && fit < 1)
{
bottom = (r_refdef.vrect.y + r_refdef.vrect.height - 0.5f) * r_aliasuvscale;
aliasxscale = xs * fit * size;
aliasyscale = ys * fit * size;
aliasycenter = yc + (bottom - yc) * (1 - size);
}
From the top: the axe in true perspective, the axe now, the shotgun in true perspective (yes, it's there, somewhere below the screen), the shotgun now.
Shadows on the barrels
Now that the guns were finally visible, the double-barrelled shotgun had dark patches all over the tops of its barrels. They were there all along, just below the screen.
Left: the bug. Right: the fix. Zoomed 3×.
To find it, Claude compiled the game's own d_polyse.c for the PC twice, once with Pocket Quake's integer gradients and once with id's original float version, and fed both the shotgun's triangles. The integer version showed the patches, and logging both versions side by side pointed straight at the depth steps:
tri 4 zx: int -13639920, exact 31570262 (dxdenom -95) tri 5 zx: int 5803844, exact -19312923 (dxdenom -171)
Wrong by miles, and with the wrong sign. Each step is a difference of two products divided by twice the triangle's area, in 32-bit ints:
r_zistepx = (t1 * p01_minus_p21 - t0 * p11_minus_p21) / d_xdenom;
Here t0 and t1 are differences in 1/z, stored as 231/z. The gun's z is scaled 3× to keep it in front of the world, and it comes as close as 5 units, so those differences approach 230. Multiply that by a few dozen pixels and it no longer fits in 32 bits. The depth test then lets the dark wood behind the barrels win. A monster right in your face can hit the same overflow.
The fix drops just enough low bits first, so that the products fit. Screen distances are below 2048 here, so 20 bits always do. Small differences are calculated exactly as before:
m = (t0 < 0 ? -t0 : t0) | (t1 < 0 ? -t1 : t1);
if (m < (1 << 20))
{
*stepx = (t1 * p01_minus_p21 - t0 * p11_minus_p21) / d_xdenom;
*stepy = (t1 * p00_minus_p20 - t0 * p10_minus_p20) / ydenom;
return;
}
sh = 1;
while ((m >> sh) >= (1 << 20))
sh++;
t0 >>= sh;
t1 >>= sh;
*stepx = (t1 * p01_minus_p21 - t0 * p11_minus_p21) / d_xdenom * (1 << sh);
*stepy = (t1 * p00_minus_p20 - t0 * p10_minus_p20) / ydenom * (1 << sh);
On the default size the shotgun went from 263 pixels different from id's float code to zero. The test lives on in tools/polytest.
A debt from the NES9500 post
In the NES9500 post I said that Quake9500 still polled window server events the old way. It did, right up until writing this post. The loop looked at iEventStatus and never took the completed request's signal off the thread's semaphore, so every event left one stale signal behind, and every later wait had to spin through all of them. That may well be why the game got sluggish after a while. The fix is one line at the top of the poll loop:
while (w.iEventStatus != KRequestPending)
{
User::WaitForRequest(w.iEventStatus);
TWsEvent event;
w.iWs.GetEvent(event);
w.iEventStatus = KRequestPending;
w.iWs.EventReady(&w.iEventStatus);
How these screenshots were made
None of the game pictures in this post were taken on the phone. They come from the phone's code, though: the same C files compiled for a PC, with a stand-in for epocsys.cpp and epocaudio.cpp that has no window and writes frames to disk. Only the speed numbers and the logs come from the phone.
Quake isn't 64-bit clean, as it casts pointers to int and long all over the place. On 64-bit Windows both are 32 bits, so normally that would crash at once. The trick is to keep the whole process below 2 GB, where those casts lose nothing: link the image at 4 MB, turn off ASLR, and clear IMAGE_FILE_LARGE_ADDRESS_AWARE in the PE header with a few lines of Python, because this ld has no option for it. Add -fwrapv so ints wrap as they do on the ARM, and a virtual clock so every run gives the same frames. A small script says what happens at which frame, such as 120 cmd impulse 3 or 320 shot b_new. It ran on the first try.
The obvious question is whether a PC build really draws what the phone draws, since it uses the x86's floats and not softfloat.c. So we ran the same timedemo on it. Same 969 frames, and this line from the report is identical to the phone's, character for character:
Alias models per frame x10: 90 rejected, 8 clipped, 30 unclipped; 6 by the float test; 0 unclipped had to be clipped (r_bboxfx 1)
Timings are meaningless on the virtual clock, of course.
The console, on Chr+Z. timeframes starts and stops a speed report for real play.
The launcher and the icon
The same recipe as in the NES9500 post: a tiny app for the Desk that starts quake9500.exe and exits. This one also checks that pak0.pak exists and tells you where to copy it if it doesn't, because the game itself can only stop with an error.
The icons come from Quake's own console background. The Q is dark brown on brown there, so a Python script masks it out by brightness and redraws it in rust on the darkened texture, at 64×50 and 25×20.
What's missing
- Music. Quake's CD tracks could be MP3s through Doom9500's libmad.
- Multiplayer and the mission packs.
- ARM assembly for the span drawers. Rockbox's notes call those the big ones, and they're the biggest part left in the report.
- A proper number for real play. The timedemo never runs the game server, so there's no monster AI, QuakeC or physics in the 13.6 fps. The release build also leaves out the operation counters, which cost a few milliseconds per frame, and I haven't timed that yet. It plays well enough for me.
The controls: arrows or the rocker move and turn, the rocker's middle, Enter or Ctrl fires, Space jumps, Shift runs, Alt strafes while held and Chr toggles strafing, Backspace or / changes weapon, H shows the status bar, Esc opens the menu and Chr+Z the console. Chr with Q W E R T Y U I A S D F gives F1 to F12, with F6 for quicksave and F9 for quickload.
Install the SIS, then copy id1\pak0.pak from the shareware or the full game (the full game also needs pak1.pak) to \Quake\id1\ on the memory card or to C:\Quake\id1\. Saves and config.cfg land next to it, and quakelog.txt goes in the Quake folder. Quake9500 is GPL like the code it's built on, so the source goes out with the SIS.
Thanks to id Software for Quake and for releasing its source, to SDLQuake, to Dan East for Pocket Quake and to the Rockbox people for their port.
Quake's box asked for a 75 MHz Pentium. The 9500 has twice the clock, no FPU, no divide instruction and a screen shaped like a letterbox. Thirteen frames per second, and it fits in a coat pocket.
Ei kommentteja:
Lähetä kommentti