Micah's bloggy widget

Chip Simulation

If you haven't heard of Robot Odyssey, it's a game where you build logic circuits that control robots in order to solve puzzles. You can build circuits directly inside the robots, but you can also program them into 'chips'- small 8-pin integrated circuits. The game also comes with several chips: a clock generator, 4-bit counter, and the infamous "wallhugger", a chip you can stick in your robot to have it follow the walls of a maze.

Once you 'burn' a circuit into a chip, you can load and save it but you can't see inside. So this has made the built-in chips a bit of a mystery. There's no way in-game to see how they work, and for all we know they could be 'magic' in some way. I had speculated a bit on how they store the compiled chips. Was it some kind of super-optimized machine code? Or maybe some kind of encoded Programmable Array Logic that was especially quick to simulate on an 8086 processor?

Well, it turns out that the code for simulating chips is clever in places, but the file format is quite straightforward. It's sort of halfway between an electrical netlist and a bytecode language. On every in-game clock tick, every bytecode instruction in the chip executes in order. Instructions can represent logic gates (AND, OR, XOR, NOT, RS flip-flop), or they can enter/exit a nested chip. Bytecode parameters can be one of two data types: The state of a pin, or a list of pin addresses.

Here's a really simple circuit inside the Robot Odyssey prototype chip:

And this is the top of the .CSV (Chip Save) file that the game produces:

00000000  00 00 00 00 00 00 00 00  01 00 00 00 01 ff 07 00  |................|
00000010  02 00 09 ff 00 03 00 0a  ff ff ff ff ff 00 00 00  |................|

First 8 bytes: Pin states. All pins are off.
First opcode (01). This is an AND gate.
- Pin states for the AND's inputs. Both are off. (00 00)
- A list of 16-bit addresses that will receive this gate's output.
  - Address of Pin 2 (00 01)
  - End of list (FF)
Second opcode (07). This exits a chip. Since this is the outermost chip, after this opcode is the end of the chip's electrical data. The parameters for this opcode are a list of lists which describes 'nodes', or places where we need to copy a pin state directly from one place to another.
- First list:
  - Source address (00 02). This is Pin 3.
  - First destination (00 09). This is the first pin of the AND gate.
  - End of list (FF)
- Second list:
  - Source address (00 03). This is Pin 4.
  - First destination (00 0a). This is the second pin of the AND gate.
  - End of list (FF)
- End of list (FF)
Afterwards is garbage. In this case, (FF FF FF). This is probably left over in memory at the time the chip was compiled, and doesn't mean anything. The chip interpreter doesn't read this data.

Chip Disassembler

So, I figured out (I think) the entire file format, and wrote a Python script to disassemble it into something a little more human-readable. The above example chip disassembles to:

Sample Chip Disassembly

Chip1 {
    HELP       'SPIFFY SAMPLE CHIP'
    HELP       '1'
    HELP       '2 OUTPUT'
    HELP       '3 INPUT 1'
    HELP       '4 INPUT 2'
    HELP       '5'
    HELP       '6'
    HELP       '7'
    HELP       '8'

    PIN        Chip1_pin2<0> 'out'
    PIN        Chip1_pin3<0> 'in'
    PIN        Chip1_pin4<0> 'in'

    AND        AND1_in0<0> AND1_in1<0> => [Chip1_pin2<0>]
    Node       Chip1_pin3<0> => [AND1_in0<0>]
    Node       Chip1_pin4<0> => [AND1_in1<0>]
}

Wallhugger Disassembly

For a more exciting example, now we can finally see inside the wallhugger chip! Converting this to a graphical schematic is left as an exercise to the reader :)

Chip1 {
    HELP       'Wall Hugger'
    HELP       '1 Top thruster    ^ Hook up pins'
    HELP       '2 Left bumper     ^ as described.'
    HELP       '3 Left thruster   ^ This chip will'
    HELP       '4 Bottom bumper   ^ cause a robot'
    HELP       '5 Bottom thruster ^ to follow(hug)'
    HELP       '6 Right bumper    ^ the walls of a'
    HELP       '7 Right thruster  ^ room.'
    HELP       '8 Top bumper      ^'

    PIN        Chip1_pin1<0> 'out'
    PIN        Chip1_pin2<0> 'in'
    PIN        Chip1_pin3<0> 'out'
    PIN        Chip1_pin4<0> 'in'
    PIN        Chip1_pin8<1> 'in'
    PIN        Chip1_pin7<1> 'out'
    PIN        Chip1_pin6<0> 'in'
    PIN        Chip1_pin5<0> 'out'

    OR         OR1_in0<0> OR1_in1<0> => [Chip1_pin5<0>]
    OR         OR2_in0<0> OR2_in1<0> => [OR1_in1<0>]
    OR         OR3_in0<0> OR3_in1<0> => [Chip1_pin3<0>]
    OR         OR4_in0<0> OR4_in1<0> => [OR3_in1<0>]
    AND        AND1_in0<0> AND1_in1<1> => [OR2_in1<0>, OR4_in1<0>]
    OR         OR5_in0<1> OR5_in1<0> => [Chip1_pin7<1>]
    OR         OR6_in0<0> OR6_in1<0> => [OR5_in1<0>]
    AND        AND2_in0<0> AND2_in1<0> => [OR2_in0<0>, OR6_in1<0>]
    AND        AND3_in0<0> AND3_in1<0> => [OR6_in0<0>, OR8_in0<0>]
    OR         OR7_in0<0> OR7_in1<0> => [Chip1_pin1<0>]
    OR         OR8_in0<0> OR8_in1<0> => [OR7_in1<0>]
    AND        AND4_in0<0> AND4_in1<0> => [OR4_in0<0>, OR8_in1<0>]
    NOT        NOT1_in0<1> => [AND1_in0<0>, AND3_in0<0>, AND4_in1<0>, AND2_in0<0>]
    OR         OR9_in0<1> OR9_in1<0> => [NOT1_in0<1>]
    OR         OR10_in0<0> OR10_in1<0> => [OR9_in1<0>]
    OR         OR11_in0<0> OR11_in1<1> => [OR9_in0<1>]
    Chip2 {
        PIN        Chip2_pin1<1>
        PIN        Chip2_pin2<0>
        PIN        Chip2_pin3<0>
        PIN        Chip2_pin4<0>
        PIN        Chip2_pin8<1>
        PIN        Chip2_pin7<0>
        PIN        Chip2_pin6<0>
        PIN        Chip2_pin5<0>
    
        FF<01>     FF1_in0<0> FF1_in1<1> => [Chip2_pin5<0>] []
        OR         OR12_in0<0> OR12_in1<0> => [FF1_in0<0>]
        OR         OR13_in0<1> OR13_in1<0> => [FF1_in1<1>]
        OR         OR14_in0<0> OR14_in1<0> => [OR13_in1<0>]
        OR         OR15_in0<0> OR15_in1<0> => [OR12_in0<0>]
        OR         OR16_in0<0> OR16_in1<0> => [OR15_in1<0>]
        FF<01>     FF2_in0<0> FF2_in1<1> => [Chip2_pin6<0>] []
        OR         OR17_in0<0> OR17_in1<0> => [FF2_in0<0>]
        OR         OR18_in0<0> OR18_in1<1> => [FF2_in1<1>]
        OR         OR19_in0<0> OR19_in1<0> => [OR17_in0<0>]
        OR         OR20_in0<0> OR20_in1<0> => [OR19_in1<0>]
        OR         OR21_in0<0> OR21_in1<0> => [OR18_in0<0>]
        FF<01>     FF3_in0<0> FF3_in1<1> => [Chip2_pin7<0>] []
        OR         OR22_in0<0> OR22_in1<0> => [FF3_in0<0>]
        OR         OR23_in0<0> OR23_in1<1> => [FF3_in1<1>]
        OR         OR24_in0<0> OR24_in1<0> => [OR22_in0<0>]
        OR         OR25_in0<0> OR25_in1<0> => [OR24_in1<0>]
        OR         OR26_in0<0> OR26_in1<0> => [OR23_in0<0>]
        FF<10>     FF4_in0<1> FF4_in1<0> => [Chip2_pin8<1>] []
        OR         OR27_in0<1> OR27_in1<0> => [FF4_in0<1>]
        OR         OR28_in0<0> OR28_in1<0> => [FF4_in1<0>]
        OR         OR29_in0<0> OR29_in1<1> => [OR27_in0<1>]
        OR         OR30_in0<1> OR30_in1<0> => [OR29_in1<1>]
        OR         OR31_in0<0> OR31_in1<0> => [OR28_in0<0>]
        Node       Chip2_pin1<1> => [OR30_in0<1>, OR13_in0<1>, OR18_in1<1>, OR23_in1<1>]
        Node       Chip2_pin2<0> => [OR25_in0<0>, OR31_in1<0>, OR21_in0<0>, OR14_in1<0>]
        Node       Chip2_pin3<0> => [OR20_in0<0>, OR28_in1<0>, OR26_in0<0>, OR14_in0<0>]
        Node       Chip2_pin4<0> => [OR16_in0<0>, OR31_in0<0>, OR21_in1<0>, OR26_in1<0>]
    }
    Node       Chip1_pin2<0> => [OR7_in0<0>, OR10_in0<0>, Chip2_pin2<0>]
    Node       Chip1_pin4<0> => [OR3_in0<0>, OR10_in1<0>, Chip2_pin3<0>]
    Node       Chip1_pin8<1> => [OR5_in0<1>, OR11_in1<1>, Chip2_pin1<1>]
    Node       Chip1_pin6<0> => [OR1_in0<0>, OR11_in0<0>, Chip2_pin4<0>]
    Node       Chip2_pin8<1> => [AND1_in1<1>]
    Node       Chip2_pin7<0> => [AND2_in1<0>]
    Node       Chip2_pin6<0> => [AND3_in1<0>]
    Node       Chip2_pin5<0> => [AND4_in0<0>]
}

Download it

If you want to try it out yourself, or you want more detailed info about the file format, grab the latest source code here:
http://svn.navi.cx/misc/trunk/python/robot_odyssey_chip_disasm.py

13th-Apr-2009 11:44 am - Announcing the VMware SVGA Device Developer Kit

Over the weekend, I finally had time to release another work-related open source project: the VMware SVGA Device Developer Kit. It's a set of documentation and example code for the virtual graphics card that's present in all VMware virtual machines. The examples run on the (virtual) bare metal, so it's a really easy way to experiment with low-level graphics driver programming.

12th-Apr-2009 03:29 pm - Robot Odyssey Mouse Hack 1

Yesterday I spent some more time reverse engineering Robot Odyssey. This was a great game, and it's kind of a nostalgic pleasure for me to read and figure out all of this old 16-bit assembly. So far I've reverse engineered nearly all of the drawing code, big chunks of the world file format, and most of the code that's responsible for moving around objects on the screen.

So, I thought I'd try manipulating some of that data. I extended my existing binary patch to add even more code to the game's per-frame blit function. It sets up the mouse using DOS Int 33h, and lets you manipulate the game's table of sprite locations by dragging objects with the mouse.

I took a video to show the results. It's still obviously a hack, but it may actually be kind of useful for assembling circuits more quickly:

The source code is available, but it's a bit rough. This patch is getting kind of unwieldy in its current state, and I think my next step will be coming up with a better tool for doing these kinds of patches. I'm thinking either:

A pre/post-processor for NASM, which has binary patching oriented features.
It would use signatures (byte mask + md5sum) to identify interesting code and data regions in the original binary, and allow you to replace or invoke snippets of code in the original binary using this mechanism. This should make it easier to do very invasive patches which can apply against slightly different versions of a game.
Or, scripting support for DOSBox.
This could be a lot like the Lua support in FCEUX which made Super Mario Drag & Drop possible. As much as I like the idea of self-contained binary patches that operate in the same environment the game itself runs in, a Python plugin interface for DOSBox could be extremely powerful. Imagine a real-time level editor, or various kinds of real-time memory comparison tools...

5th-Apr-2009 12:32 pm - Robot Odyssey: 4-way low latency flip flop

Robot odyssey rocks. Also, I didn't realize that you could upload a video captured with VMware Workstation directly to Youtube. It's pretty neat that they support our video codec.

Here's a video of a chip I was just designing, a low-latency 4-way flip flop:

4th-Apr-2009 03:01 pm - A Binary Patch for Robot Odyssey

Robot Odyssey is one of the games that I have the fondest childhood memories of. It's both a high-quality educational game, and a gentle (but very challenging) introduction to digital logic.

There's a Wikipedia article on the game. There's also DroidQuest which is a Java-based clone of Robot Odyssey. The DroidQuest site also contains some good info on Robot Odyssey itself, including the only walkthrough I've ever seen.

So, I recently got inspired to try playing through Robot Odyssey again. As a kid, I never managed to beat the game. For a long time, it was nearly impossible to run it on a modern machine. It required a 5.25" disk drive due to the ancient copy protection, it has CGA graphics, assumes you're using an IBM XT keyboard, and all of the timing is based on the 4.77 MHZ CPU frequency of the original XT.

Thankfully there's DOSBox, a really high quality emulator that can run old games like this quite faithfully. I started trying to play Robot Odyssey on DOSBox, but there were still two big problems:

Copy Protection.

Robot Odyssey checks to make sure you're running from the original 5.25" disks, which have a "flaky bit" on them. If the flaky bit isn't detected, the game will still load but your soldering iron doesn't work!
Inconsistent speed.

DOSBox is really good at slowing down the CPU, but this isn't an exact science. Some things that were really really slow on the original XT (like writing to the CGA card) are fairly fast on DOSBox, and other things are comparatively too slow. This means you're constantly futzing with the speed of DOSBox's CPU emulation, depending on what level you're in, how many robots are on the screen, etc.

The Patch:

So, I decided to solve these problems (and a few others) by binary patching the game itself. Since there are a bunch of user-tweakable knobs, I figured the best way to distribute this patch was as a Python script which patches the original binaries. You can grab the script from:

http://tinyurl.com/ropatch

If you're interested in the technical details of how the patch works, the source is pretty well commented. I won't bore you with that here. This is a list of the patcher's features:

Disables copy protection.

This is necessary to run the game on any modern machine, even assuming you have the original disks.
Installs a frame rate limiter.

Instead of adjusting the CPU speed, this is a real and fairly accurate frame rate limiter. You can specify a desired frame rate on the command line when applying the patch. By default it runs at 8 FPS, which feels about right based on memory. (I don't have an IBM XT handy for checking what the speed is supposed to be...)
Halts the CPU when idle.

When the frame rate limiter is sleeping, it yields the CPU. This will help a lot if you're running the game in a multitasking environment or a virtual machine.
Compatibility with Windows XP's built-in DOS emulation.

You need the "-p" flag for this, and the frame rate limiter won't be as precise- but the game will be playable just by double-clicking it in Windows!
"Fast" mode.

This is an optional feature, enabled with the "-f" flag, which speeds up the game when keyboard input is waiting. This makes it feel a lot more responsive, and makes it faster to navigate around the level. You can also hold down any repeating key as a very simple "turbo" button.
Keyboard compatibility patch.

Normally, Robot Odyssey is totally unplayable on any computer without a numeric keypad, including laptops, due to a bug in its keyboard handler. If you enable the "-k" flag, the patcher will rewrite the game's keyboard mapper to be fully compatible with AT keyboards. This also removes the need to play with Caps Lock on.

Usage:

To use the patch, you'll need:

Python
NASM, a spiffy assembler
Original Robot Odyssey binaries.

Make sure the binaries you have aren't already patched or cracked in any way. I won't distribute these myself (so don't ask!) but there are numerous abandonware sites on the web which should have this game. I'm not sure if multiple revisions of this game were produced. This patcher tries to be pretty lenient, but I've only tested it with one version. For reference, these are the SHA-1 hashes from my copy of Robot Odyssey:
```
756a92e6647a105695ac61e374fd2e9edbe8d935  GAME.EXE
692a9bb5caca7827eb933cc3e88efef4812b30c5  LAB.EXE
360e983c090c95c99e39a7ebdb9d6649b537d75f  MENU2.EXE
a6293df401a3d4b8b516aa6a832b9dd07f782a39  MENU.EXE
12df28e9c3998714feaa81b99542687fc36f792f  PLAY.EXE
bb7b45761d84ddbf0a9e561c3c3603c7f65fd36d  SETUP.EXE
e4a1e59665595ef84fe7ff45474bcb62c382b68d  TUT.EXE
```
Something that can run DOS games with CGA graphics! This could be a PC booted into DOS, a Windows machine, DosBOX...

Before you apply the patch, make backup copies of all your game binaries:

    micah@carrot:~/robot$ mkdir original
    micah@carrot:~/robot$ cp *.EXE original/
    micah@carrot:~/robot$ ls original/
    GAME.EXE  LAB.EXE  MENU2.EXE  MENU.EXE  PLAY.EXE  SETUP.EXE  TUT.EXE

Now apply the patch to each binary. Each section of the game (Robotropolis, the Innovation Lab, and the Tutorials) have their own separate EXE file, each of which has a separate copy of the game engine. You can use the same or different settings for each.

For example, to patch all binaries with default frame rate, and with the keyboard patch enabled:

    micah@carrot:~/robot$ python robot_odyssey_patcher.py original/GAME.EXE GAME.EXE -k
    Found copy protection. Disabling...
    Found blitter loop. Patching...
    Found keyboard mapper. Patching...
    Saving comment at 0x1a4d0
    micah@carrot:~/robot$ python robot_odyssey_patcher.py original/TUT.EXE TUT.EXE -k
    Copy protection not found.
    Found blitter loop. Patching...
    Found keyboard mapper. Patching...
    Saving comment at 0x11380
    micah@carrot:~/robot$ python robot_odyssey_patcher.py original/LAB.EXE LAB.EXE -k
    Found copy protection. Disabling...
    Found blitter loop. Patching...
    Found keyboard mapper. Patching...
    Saving comment at 0x152a0

Now run PLAY.EXE in Windows, DOSBox, etc. You should see the game running at a steady 8 FPS, and the non-numpad arrow keys should work.

Experiment with the options! The "-h" option gives you a full list of the available setitngs. For example, if you want the game to run a bit faster, you might add "-f -r 10". This will run the game at 10 FPS, and speed it up when there's keyboard input. Remember to add "-p" if you're running in the Windows DOS emulation.

This patcher may also work for games other than Robot Odyssey, which were based on the same engine. For example, Gertrude's Secrets and Rocky's Boots. You may have to leave off the "-k" option, since these games don't necessarily use the same keyboard mapping as Robot Odyssey.

Enjoy exploring Robotropolis!

20th-Mar-2009 10:52 am - PicoGUI... not quite dead yet?

Way back in 1999, when I was in high school, I started my own embedded GUI project for a little 68EZ328-based Linux machine I wire-wrapped. This turned into PicoGUI, which I spent about 4 years working on. It was a great learning experience, but I eventually stopped maintaining PicoGUI. (I wrote a short document at the time, explaining why.)

Apparently there's at least one device that still runs it... the mvBlueLYNX networked camera from MATRIX VISION. The manual has a whole section on PicoGUI, including a link to some Doxygen'ed docs for the client library, configuration options for pgserver, and so on.

Looks like they're using PicoGUI's "Classique" (Classic Mac OS) theme :)

17th-Feb-2009 02:29 pm - Spark Fun in Fortune magazine

Spark Fun Electronics is awesome. If you're an electronics hobbyist who hasn't heard of them, you're missing out. While us hobbyists have long been able to get a huge variety of "reasonably" priced staple components from Digi-key, and crazy-cheap surplus components from places like All Electronics Corp. and B.G. Micro, I couldn't help feeling like the industry was leaving hobbyists in the dust. If we wanted bargains on 10-year-old technology we were in luck, but the latest and greatest parts were getting more and more out of reach to the average hobbyist. Either there would be a minimum order of 5000, or they would be in a ridiculously small SMT package, or the data sheets would be proprietary. Most often, all of the above.

Spark Fun to the rescue! They really are the first online electronics store I've seen that's really by hobbyists and for hobbyists. They buy the latest and greatest development boards, sensors, and other toys, put the specs up on their web site, build breakout boards, and sell them for very reasonable prices. As if that wasn't enough, Spark Fun has become kind of a clearinghouse for custom hobbyist-designed platforms. They stock everything from MAKE staples like the Arduino, to special-purpose platforms like the Uzebox AVR-based game console.

Oh, and did I mention they're in Boulder? If only I'd known while I was still in school...

Anyway, given how awesome Spark Fun is, I was really proud to see that Spark Fun was mentioned in Fortune Small Business magazine:

Customize

This page was loaded Jul 6th 2009, 7:03 pm GMT.

Chip Simulation

Chip Disassembler

Sample Chip Disassembly

Wallhugger Disassembly

Download it

Advertisement