In September I added HiRes+ support to Aaron Ardiri's Lemmings for Palm OS, the full-screen mode of the Tungsten T3 and its successors (see Lemmings in HiRes+ on the Tungsten T3). The source headers say that changes need Aaron's consent, so I asked him. What followed was a week of emails, five pull requests and a lot of stories from 2001. Here is that exchange, shortened to the parts that tell the story. The emails are quoted as written, with a few typos fixed; […] marks what I left out.
My email to his old address bounced, so the first contact was a short note on LinkedIn:
Saturday: “If you do a fork and pull request”
So I wrote the longer version by email, with two photos from my T3:
Thomas · 3 October, 11:43
You're right, the game already supports hi-res: 320x320 on the Palm OS 5 high density devices. What it doesn't support is HiRes+, the 320x480 / 480x320 screens with a collapsible input area […]
Two photos from my Tungsten T3 are attached, same level:
The source headers say modifying and redistributing it needs your consent, so I haven't published anything yet. How would you prefer to handle it? […]
Aaron · 3 October, 12:54
these look great.. my inner OCD tells me the background on the left and right of the tool bar would look better as black, not white ;)
If you do a fork and pull request, I can merge the changes into the main repo.. ;)
great that you were able to build everything as well ;) I have boxes full of devices, I should try and bring them out and rebuild stuff..
the lemmings code was ported to iOS, BlackBerry 10 and Android as well.. but Sony stopped it being released.. I eventually released it as Caveman..
That is where the black bars of the HiRes+ version come from. By the afternoon they were in, and so were the first three pull requests:
Thomas · 3 October, 16:54
Your wish is fulfilled: the space beside the tool bar is black now. And while I was at it, the title bar got the same look […]
The pull requests are open […] Here is a preview of the article […]
Aaron · 3 October, 17:21
looks good ;)
we had so many hacks in place to make lemmings even feasible on PalmOS.. there are some really cool tricks inside the code.
- 16 bit grayscale with color remapping
- bitmaps using read-only memory handles
- the mini midi engine ;)
I miss the development environment... I was also maintaining PilRC for a while - adding color support.. :) I also sent a copy of the article to Chip - we still chat every now and then ..
SHARK is also on GitHub... where we solved cross platform development before Apple and Google messed everything up.. :)
What the code shows
Those three tricks are all in the source. Remember the target: a Motorola DragonBall with 16 MHz on the first models, very little working memory, and up to 50 lemmings at once on a level several screens wide.
16 colors, and grays you can tune
At start-up the game checks what the display can do. It tries 8 bits per pixel first, only to find out whether the device has a color screen. Then it switches down to 4 bits per pixel, which means 16 colors. That halves the amount of data compared to 8 bits, and every byte that has to be moved costs time. To make 16 colors enough, every level brings its own 16-color palette as a resource in the level pack. The graphics stay the same, only the colors behind the 16 numbers change.
On the grayscale devices, like the Palm III or the m100, the game runs with 2 bits per pixel, so 4 shades. Their LCD controller has registers that decide how dark "light gray" and "dark gray" really are. Lemmings writes to them directly: 0xFFFFFA32 and 0xFFFFFA33 on the original DragonBall, different values on the EZ and VZ. That is the grayscale setting in the game menu, which lets you tune the two grays for your screen.
Bitmaps in protected memory
A Palm has two kinds of memory. The dynamic heap is the working memory for programs, and on older devices it is tiny, sometimes less than 100 KB for everything. The storage heap, where databases and applications live, is much larger, but it is write-protected. Programs are only supposed to write to it through the Data Manager.
Lemmings needs room for the sprites of all lemming animations and their masks. One of the build switches in the source says it all: NO_DYNAMIC_RAM // dont use any dynamic ram whatsoever! So at start-up the game creates a temporary database and puts the sprite bitmaps there, as resources in the storage heap. While it fills them, it briefly lifts the write protection with MemSemaphoreReserve.
The catch: to draw into a bitmap with the normal Palm OS calls, you need a window for it, and WinCreateBitmapWindow only accepts bitmaps from the dynamic heap. Aaron's comment in the source explains the way around it:
// winLemmings, winLemmingsMask and winGameMask are "readonly" graphics // resources in the game, so, we have to hack around this :) we have to // fool the Palm OS, by creating a small bitmap, and then replacing the // bitmap with our "handle" we created earlier.
So the game creates a window for a small dummy bitmap, deletes the dummy, and points the window at the bitmap in the database. From then on, Palm OS draws from the storage heap as if nothing had happened. The same idea shows up when you save a game on an older Palm: the level is compressed straight into the save database, because there is not enough working memory for a temporary copy.
Drawing faster than Palm OS
The level is drawn into an offscreen buffer that is wider than the screen. Scrolling only changes the position from which the game copies to the display. That copy does not use Palm OS at all: the game writes straight into the display memory, with hand-written 68k assembly. There is even a switch to copy only the lines that have changed.
The high-resolution screens of the Sony Cliés (320x320) and the HandEra 330 (240x240) are handled the same way, with lookup tables. For the Clié, a table turns every byte of the 160x160 image into two bytes with each pixel doubled. For the HandEra, three tables stretch the image by a factor of 1.5. That is how the game used high-resolution screens long before Palm OS had a standard way to do it.
A mini MIDI engine
From Palm OS 5 on, Palms have an ARM processor and a sound stream API: the system regularly asks a callback function for the next block of audio samples. Lemmings ships that callback as a small piece of native ARM code, written by Aaron, Chip and Ivo Jager, and loads it as a resource.
Every time it is called, the callback plays a standard MIDI file: it keeps its own clock in microseconds, and when the next MIDI event is due, it starts or stops a note. Each note plays a short instrument sample at the right pitch. Up to 16 voices are mixed into 16-bit sound at 22,050 Hz. The music for a level, the two samples (one instrument, one for percussion) and the code together take only about 15 KB. The source even contains an emulated Moog filter, switched off.
I asked whether I could write about all this, and mentioned that I had to patch his PilRC to build Lemmings on a 64-bit Mac:
Thomas · 3 October, 17:40
Would you mind if I mention the 16 bit grayscale with color remapping, the read-only bitmap handles and the mini MIDI engine in the article? […]
Funny coincidence with PilRC: to build Lemmings on my Mac, I had to patch PilRC 3.2, because it reads the BMP headers with the wrong field sizes on 64-bit systems. So your PilRC is still in use.
Aaron · 3 October, 18:28
absolutely ;)
I published the code to reveal all our secrets from back then.. :) a lot of the old games were ported to SHARK... so they never died ;)
I did see some posts about PilRC which is why I mentioned it ;) the palm source guys in France took it over internally when ARM devices came out.
SHARK is really cool, especially the r9 hacks we did to get around PACE and run applications fully natively..
Aaron · 3 October, 19:05
cannot believe this code is 25 years old!
Sunday: “Probably a reason we never added it”
Then I started playing on the T3 for real, and the bugs came. A fourth pull request with fixes went to Aaron. His reply was short:
Aaron · 4 October, 19:20
finding more issues?
probably a reason we never added it way back haha ;) probably needs a little more testing before everything is done.. I should bring out a device from storage and test this stuff
Thomas · 4 October, 19:31
yes, and I'm not sure yet whether I should already regret opening the pull requests for HiRes+ ;-) No, I'm still optimistic that I'll get it all ironed out. […]
Right now I'm on a nasty bug. […] when a level is finished and the verdict dialog is open, the Palm switches itself off, and you then press the HotSync button, the device hangs.
Aaron · 4 October, 19:36
No stress ;)
Palm's DIA support was dodgy so to speak haha... I remember when we did SHARK.. we handled it completely differently.. maybe some insights there?
SHARK 2.0 had issues as well.
He sent along the TODO list of SHARK 2.0 for Palm OS. The Tungsten T3 was already on it:
- dynamic input areas >> Tapwave Zodiac, Tungsten T3, Garmin iQue 3600/3600a implementation issues with the dynamic input area support. using PINS on these devices causes a software reset = un-explainable? the Garmin iQue devices dont have sufficient dynamic memory for 320x448 - hence, by default, these devices will only run in legacy mode (320x320).
Aaron · 4 October, 19:36
sounds familiar !!
The freeze turned out to be in his original build as well. I told him in the evening, and asked one more thing:
Thomas · 4 October, 22:27
[…] the HotSync freeze I mentioned is in your original build too, and only happens in a very rare situation […] It's fixed in pull request #4 now […]
Would it be too cheeky to ask one more thing? What do you think about removing the registration from Lemmings, so that everyone gets the full version right away? […] unless you're still planning to make money with the game ;-)
Monday: “It was never about the money”
The next morning, three emails were waiting. The first one started with a complaint about my HiRes+ article, which quoted his source comment about the bitmaps, but not all of it:
Aaron · 5 October, 06:13
You didn't keep the comment
f*ck you palm
haha :) I was super proud to figure out the storage memory for bitmaps - we never made that trick public and everyone wondered how the hell we pulled it off haha
Here it is, right after the window had been created for a small dummy bitmap:
globals.winLemmings = WinCreateBitmapWindow(bmpPtr, &e); // f*ck you palm :P - get around that darn limitation BmpDelete(bmpPtr); bmpPtr = (BitmapType *)MemHandleLock(globals.hanLemmings); globals.winLemmings->bitmapP = bmpPtr;
Aaron · 5 October, 06:13
As for the registration stuff - I would recommend a #define for that when building. Something like DISABLE_DRM - I had built some crazy digital rights management systems to deal with piracy back in the day.. that's still educational
as for the old skool midi - yes, on 68k devices we used simple tones, bound to the main gameloop. for arm, the sound handling ran in its own separate thread (audio callback)
That explained the last bug I had fixed: on the m515, fast forward had made the music four times as fast, because there the tune moves on with the game loop.
Aaron · 5 October, 06:13
as for the bug.. maybe the best thing to mention is that we were pushing the limits of the devices to start with - the edge cases were really weird and a lot of things were being developed as they go - for example, DIA didn't come from the start.. it was introduced later
and yes, when dialogs pop up - the rules changed completely.. it's no wonder that's where a lot of the weird cases show their face.. with SHARK - we moved away from system dialogs/forms and drew everything ourselves..
we had fragmentation issues within the PalmOS ecosystem alone - forget about symbian, windows mobile etc.. it was tough for a lot of developers..
it was also 25 years ago ;)
Aaron · 5 October, 06:36
I had some booby traps for people using pirated level packs haha.. man.. that was fun. [Reddit]
it took a long time before I even considered porting it to our cross platform toolchain - which happened in 2010 [ZDNet] while I was between jobs (moving from Stockholm to Munich).. would have been lemmings on iPhone - that would have been huge.. Sony stopped that tho.. oh well.
the code is designed to do weird stuff if you start tampering ;) that was by design to mess with the piracy scene back in the day
Aaron · 5 October, 06:43
I do miss the good old days - I worked with a bunch of really cool guys all over the world.. we just built stuff because we loved it.. it was never about the money ;) but, it was cool to travel to all those conferences and we did secure some really nice projects..
whats most funny about it all - we all did it part time...we all had full time jobs in parallel - this was just a hobby of ours..
A few hours later, all five pull requests were in his repository:
Aaron · 5 October, 10:03
merged :)
How it ended
Half an hour later I remembered that I hadn't even said thank you:
Thomas · 5 October, 10:33
One more thing I forgot: thanks for merging the pull requests! I'll probably send one or two more in the next days. I've noticed that the Palm LifeDrive still has a problem with the status bar, and that fix will come together with the DISABLE_DRM switch you suggested. And the NR70V is still tickling me a little, but let's see. Of course I don't want to take up too much of your time, I know that reviewing takes time too.
Aaron · 5 October, 10:34
all good :) just send through - trust you're doing a good job haha
And that is how it went. The registration stays in the code, as Aaron suggested, and a build switch, REGISTERED_BUILD, turns it off: the PRC in his repository is now the full version, without a demo notice. It came with pull request #6, together with the fix for the LifeDrive and two small fast forward fixes, and #7 brought music for every level. Aaron merged both.
The NR70V will have to wait, at least until the itch gets too strong. Like it was for Aaron and his friends back then, this is a hobby for me. But it was a wonderful trip back in time.
Thanks to Aaron for his time, his patience with seven pull requests, and all the stories. And to Chip Kerchner, who co-wrote Lemmings. If you want more of those stories, Aaron's autobiography is on his website.