m9b · part 6 of 6

Re-retro: five games on 36 MHz

The five games were written for DOS PCs of the early 1990s. Their modern source ports assume a modern machine. Running them on m9b meant undoing some of that modernization: putting them back on a diet of memory, cycles and sound hardware that’s in some ways tighter than the PCs they first ran on.

The machine they land on

m9b is in-order, has no floating-point unit, and runs at 36 MHz with 8 MB of RAM behind caches whose misses cost about 25 cycles each (part 3). It has no sound chip and no MIDI synthesizer. It does have a 32-bit hardware multiplier and divider, a reasonably fast SD card, and a video engine that does page flipping and scaling for free.

The software is simply ported, not rewritten. Each game is its upstream source, trimmed to what the build needs, with every change marked, and a platform layer of its own in place of SDL.

One platform for five games

All five share a small runtime, first written for Doom:

• C library and files: picolibc, with its system calls mapped onto the console UART and onto FatFs, so open, read and lseek work on the SD card. The C++ ports (System Shock’s physics, all of Exult) use picolibc’s libstdc++, exceptions included.
• A trap handler that dispatches the interrupts, and emulates misaligned loads and stores: the CPU traps on them, and old game code is full of them.
• Video: every game draws its 320 × 200, 8-bit screen as it always did. The port copies it to one of three display buffers, cleans it out of the data cache, and the vertical-blank interrupt points the line table at it, with each line doubled horizontally and shown on 2 or 3 screen lines: the 4:3 picture a VGA monitor gave (part 4).
• Sound effects are mixed in the audio interrupt, at 12 or 24 kHz rather than 48, with each result held for 4 or 2 output samples. The effects are 11 or 22 kHz samples to begin with, so nothing is lost, and the mix costs a few percent of the CPU instead of a tenth.
• Loading: programs live on the SD card, picked from a boot menu. The SD driver reads runs of sectors with one command, 32 bits at a time: Doom’s level load went from 4.6 s to 1.7 s as the SD card driver improved.

Music: rendered once, streamed forever

All five games composed their music for a synthesizer: an AdLib or Sound Blaster’s Yamaha OPL FM chip, or a Roland MT-32. None fits. An open-source OPL2 core needs 1,337 cells and 4 block RAMs on this chip, which has about a thousand cells and one block RAM to spare. A software synthesizer would cost 10 to 15% of the CPU before the game draws anything, and the ports’ own emulators compute in floating point.

So the music is rendered once, on a PC, and streamed from the SD card during play. For four of the games, that’s libADLMIDI’s emulation of the OPL3 chip playing each game’s own instruments and its sound driver’s volume rules: Doom’s GENMIDI bank, Descent’s HMI banks, System Shock’s AIL timbres; Tyrian through its own player and OPL emulator. Ultima VII uses Exult’s recordings of a real Roland MT-32, the synthesizer it was composed for. Every track comes out as 24 kHz mono WAV at a common loudness, streamed through a ring buffer in PSRAM that the main loop tops up and the audio interrupt drains.

The results aren’t small: 81 MB for Doom, 69 for Descent, 128 for Tyrian, 95 for System Shock, 208 for Ultima VII. SD cards are big so that’s not much of a problem.

System Shock needed one more step. Its music is adaptive: each theme is up to 54 short sequences, and a music AI starts them on up to 8 threads, a main piece and layers over it, choosing what comes next from what’s happening. Each sequence is rendered on its own (227 files), and the port implements the music driver’s interface on top of them: the game’s own AI still picks the pieces, the port streams up to eight of them at once and mixes them.

Doom: the drawers

Doom spends its time in two loops: R_DrawColumn, which draws walls and sprites a vertical column at a time, and R_DrawSpan, which draws floors and ceilings a horizontal row at a time. Together they’re 40% of the frame.

From there, the hardware took over: the CPU going synchronous at 36 MHz, the 2-way data cache, faster SD reads, cbo.zero in memset and memcpy, the radix-4 divider. The timedemo now runs at about 22 fps. Before the second cache way, moving a buffer by a few hundred bytes changed Doom’s speed by 2%: a column of the screen touches 200 cache lines, and whatever else was hot fought it for them.

Descent: one divide in sixteen

Descent is a true 3D game with perspective-correct texture mapping, and D1X’s C version of the texture mapper divides by depth for every pixel: 70 cycles or more each. At first, texture mapping was two thirds of the time and the game ran at 5 fps.

• The texture mapper now computes exact texture coordinates every 16 pixels, from one reciprocal, and steps linearly in between, with both coordinates packed into one word as Doom’s span drawer does, four pixels per iteration.
• Divides that the original did in assembly, 64 by 32 bits, now take two hardware divides instead of a bit-by-bit loop.
• The cockpit is a full-screen bitmap with a transparent hole for the 3D view, and D1X redrew it, with every gauge, every frame. Now its opaque runs are rendered once, it’s redrawn only where the 3D view can reach, and the texture mapper skips scanline pieces the cockpit will cover anyway. Cockpit and gauges went from 8% of the time to 1%.
• Key polling checked all 256 keys on every query, 6% of the time; now only held keys are checked.

About 10 fps in the first level, with the full cockpit.

Tyrian: one check per pixel

Tyrian’s profile showed two thirds of the time in one function, drawing the three scrolling background layers a byte at a time, each pixel checked against the screen’s edges. Rows that are wholly on screen now skip the checks, and the game went from 17 to 35 fps: its full speed, set by its own timer, with time to spare. Its music needed rendering too: OpenTyrian’s OPL emulator computes envelopes in floating point for every sample.

System Shock: back to 1994’s memory

Shockolate is Night Dive’s 2018 release of the Macintosh source, made portable. The Mac version, and the port, assumed far more memory than 1994’s DOS version: starting level 1 took 5.3 MB of heap, and a cutscene 17 MB. m9b has 5.1 MB of heap for it.

• The resource table had an entry for each of 32,768 possible resource IDs: 1.1 MB. System Shock’s go up to about 5,500.
• Compound resources (a texture’s sizes, a critter’s frames) were read whole when one item was needed, and the item decoded into a copy. Now only the index is read, and each item when first asked for.
• Movies were loaded whole (14 MB for the intro), their sound unpacked into another 2.5 MB, and kept after playing. Now they stream from the file as they play, and use the low-resolution cutscenes the DOS version shipped, a quarter of the decoding.

Level 1 now takes 2.8 MB, a cutscene about 0.2 MB. Speed came from two places: the texture unpacker read words at odd addresses, 97% of the misaligned accesses the trap handler was emulating, and the fixed-point divides went through a 64-bit software routine instead of the hardware divider. With those fixed and the radix-4 divider in the CPU, a saved game went from 5.8 to 7.4 fps. Double clicks needed their own fix: at 7 fps, two clicks fell between polls of the mouse, so the buttons are now sampled in the audio interrupt, with their times.

Ultima VII: a heap diet

The original Ultima VII is 16-bit real-mode code on Origin’s own memory manager, with no source. Exult reimplements its engine in C++17, and plays the original data. Starting The Black Gate took 6.2 MB of heap; m9b has 5.8 MB to give it, and the C library’s allocator lost another 540 KB to holes, until Doug Lea’s malloc replaced it.

• Usecode, the games’ scripts, 1.5 MB of bytecode, was read whole at the start. Now each function is read when a call needs it, and the least recently used are dropped to keep 192 KB at most.
• Shapes read from the 7.3 MB shape file stayed in memory forever. Now the least recently used are dropped past 384 KB.
• Terrain took 4 KB per kind of map chunk, and Trinsic has 120; now 3 bytes per tile. Rendered floors are cached for 24 chunks instead of 100.

Trinsic, a few minutes in, now peaks at 4.1 MB, with room for the MT-32 music and sound effects. It plays at 7 to 13 fps. Exult does more work per object than the 1992 engine did on a 386, and that’s the next thing to look at.

The 1992 engine itself runs too. Ultima7_Decomp is a decompilation of both DOS games into portable C and C++, and m9b-u7 gives it a platform layer for the board. The game gets the DOS memory it expected, in a 4 MB arena, and needed few changes: its far heap keeps blocks word-aligned, so the CPU doesn’t trap, and sprite spans and tiles are drawn a word at a time. Walking around Trinsic, it runs at 8 to 10 fps, against its own limit of 10 steps a second. Its music and sound effects are the same MT-32 recordings the Exult port uses.

How the ports were tested

• The Doom timedemo plays a fixed demo and checksums every frame, so every hardware and software change can be compared by its run time, with proof that it draws the same pictures.
• Host test harnesses run System Shock and Ultima VII, with the same port code, on 32-bit x86 Linux, holding them to the board’s heap and filling new memory with garbage as the board would. Memory diets were done there, then checked on the board.
• Remote control: a running game answers screenshot requests over the serial port and takes key presses from it, so a game can be driven and checked without watching the display for automated testing.
• Profiling: a profile build samples the program counter from an interrupt and sends the histogram over the serial port.

None of the five games is fast by today’s standards. But they run in full, with their music, in a chip whose hardware most likely was not designed for them.