Robot Odyssey Chip Disassembler

I’ve been spending more time hacking on Robot Odyssesy lately. Most of it has had a specific purpose… I’ll write a separate blog post on that project once it’s a bit more fully baked. In the mean time, the reverse engineering has had some useful side-effects.

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       '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:

Virtual USB Analyzer

From late 2005 to early 2007, I worked on the USB virtualization stack at VMware. We ran into all sorts of gnarly bugs, many of which were very hard to reproduce or which required access to esoteric or expensive hardware. To help with debugging problems both internally and with customers in the field, we added logging support to our virtual USB stack. Starting with VMware Workstation 5.5, if you set the right hidden config option we’d start dumping the contents of all USB packets to a log. It was a USB sniffer (like USB Snoopy), but built into the virtual hardware.

To make it easier to analyze the resulting logs, I started working on a GUI tool that could navigate through these giant log files. This tool proved to be really useful within our team at VMware, and we’d often ask customers on the beta forums to generate log files that we could analyze. I called this tool vusb-analyzer.

Well, it’s been a while, but I’m proud to now have the opportunity to release vusb-analyzer as open source software under the MIT license. This isn’t just a code dump- I removed the tool from our internal repository today, and all future development will occur in the open, in a Subversion repository on Source Forge.

Currently, vusb-analyzer is most useful for analyzing logs captured by VMware products. Indeed, this is a convenient way to debug USB drivers. You can attach your USB device to VMware Workstation, VMware Fusion, or the free-as-in-beer VMware Player, and it can transparently save a plaintext log of all USB packets that pass through. Debugging a driver in a VM is really convenient, and I find it quite useful, but I understand it’s not for everybody. If you already have a favorite USB sniffer tool, it’s easy to extend vusb-analyzer with a log format plugin so it can read other formats. We already did this once, to add support for the logs generated by our favorite hardware USB analyzers.

I hope vusb-analyzer turns out to be useful for the open source community, particularly to those who are working on Linux device drivers. To get started, visit the project’s web site:

Besides the usual introduction and download links, there is also a detailed tutorial with lots of shiny screenshots 🙂

Laser projector update

Looks like my hard disk laser projector made the MAKE blog. Sweet 😉

I’ve been hacking on the software for the projector quite a bit this week- mostly on the code responsible for importing and converting vector graphics data.

In a typical laser projector, you have a high-speed DAC connecting a pair of analog servo amplifiers to a computer. The computer reads samples out of an ILDA file, maybe applies some effects in real-time, then sprays them out of the DAC. In my projector, I wanted a more sophisticated approach- mostly because of the relatively low-bandwidth Bluetooth link that exists between my projector and the PC.

My solution was to create a simple vector graphics virtual machine. The virtual machine runs on the projector’s microcontroller, in lockstep with the servo loops. It has three registers- a position register, a first-order accumulator, and a second-order accumulator. It isn’t turing-complete, but there are instructions to load these registers, wait for a number of samples to elapse, etc. It can interpolate quadratic Bézier curves in hardware. The VM also supports instructions like “jump”, and “increment counter”. This lets it support fairly complex queueing and double-buffering systems.

So far, I have code to:

  • Load paths from an SVG file
  • Convert those paths (lines, quadratic Bézier curves, and cubic Bézier curves) into my “VectorMachine” instructions.
  • Simulate the VectorMachine, and display a visual representation of the samples that the hardware will generate.
  • Queue up instructions for completed frames, using both a local and remote (in the firmware’s memory) queue. The queue has bounded latency, and it lets me flawlessly stream animated vector graphics over Bluetooth to the device.

There are some areas for improvement, like automatically optimizing the path the laser takes when it’s blanked. This could be fun- it’s actually a travelling salesman problem. I also don’t have a good way to get animation, or programatically generated graphics into it. But, it loads simple SVG files, and it does an okay job at it. It does a decent job at rendering Kirby at a blazing fast 8 FPS.

I think it’s time to take a break from this project while I figure out what to do with it next. Maybe music visualization, or Flash animations?

Times New Roman at 532 nanometers

After running the ILDA test pattern at only 4K on my hard disk laser scanner, I really wanted to see how well the projector would do with the kinds of “real” vector graphics that I expected to be able to display. Most commercial ILDA frames are way too complicated for it.

As I mentioned, the control software for the projector still mostly sucks. I have a hacked-together ILDA frame importer, and a little interactive scribbly-widget. I really want to be able to integrate it with Inkscape, or even just give it an SVG importer so I can send single frame images from Inkscape to the projector. This will probably mean writing an SVG parser in Python which generates VectorMachine instructions for my laser projector. Fun.. but pretty complicated. (Oh, lazy web, does anyone know of an existing SVG parser that would be good at such a thing? Preferably written in Python?)

In the mean time, I just tried some crazy Russian shareware to generate ILDA files that I then run through my importer. The results aren’t too bad:

The “A” is very stable, and I can display it quite smoothly. (I don’t know the exact frame rate.) The “Hello World” flickers really badly- it’s probably only refreshing a couple times per second.. but it’s still readable.

Mobile map inspiration

So, I’ve been itching to do something really cool with Python on Symbian Series 60. The first thought was a way to upload images directly from the phone to Gallery. Well, it still needs some polishing, but I wrote most of that at the last SVLUG hackfest. Right now it takes a picture with the phone’s camera, saves it locally, then beams it off directly to a Gallery server over GPRS, via an HTTP proxy and the gallery-remote protocol. Unfortunately, the Python module for the camera doesn’t give you a lot of control. A much more practical (hah!) solution would be to have the script send everything it finds in an ‘outbox’ directory- so you just save images there with any camera app, then upload them at your convenience by running a simple script.

Anyway, while that was kinda fun to write, it wasn’t really as interesting as I’d hoped. This might just be due to the extreme suckiness of phone cameras. Yesterday I found something much cooler. For a while now I’ve been interested in getting maps on my mobile devices. Google maps, of course, seem the obvious solution. Mobile web browsers aren’t fancy enough yet to support the latest AJAX applications, but I’d want a small-screen-tweaked UI anyway.

Well, MGmaps to the rescue right? It’s a pretty spiffy app. Unfortunately, being in Java it’s kinda sluggish and not readily hackable. I’d like to have it make use of my phone’s 512MB MMC card to keep a disk cache of map tiles. Doing all the browsing over a slow GPRS link with very little cache is hardly fun or useful.

Yesterday I stumbled across a Nokia forum post with a literally 100-line Python app to browse Google Maps online. It has a lot of rough edges- drawing artifacts while it’s loading, I had to hack it a bit to support HTTP proxies, and it has a ‘cache’ which will use an unbounded amount of RAM. But, it makes a great proof-of-concept and a great inspiration. I’d love to write a similar app with better cache management, a more extensible and maintainable architecture, and better responsiveness while downloading images.

If I do go through with writing such an app, I’ll finally be using Python to bring a keyhole-like system to devices you always have handy. I shall call it “pyhole”.