Wednesday, November 14, 2007

Hardware hacking

I recently rekindled an interest I have in fooling around with hardware. I bought myself a USB I/O device from Elexol, a local electronics supplier, and with a lot of junk from Dick Smith Electronics I've managed to control some LEDs from my Linux box - an awesome feat I'm sure you'll agree - all without doing any soldering. This makes my wife happy (did I mention I got married?), who is somewhat afraid the soldering iron will burn down the house one day. It also means I can pull apart old projects to make new ones without making a big mess or having to buy new components.

Went to Jaycar Electronics and bought a 10-pin connector and some ribbon cable. Here's a shot of my board looking a bit neater. While there I also bought some push button switches which I'm sure will come in handy.

Sunday, October 28, 2007

At the Wirefly X-Prize Cup

As I happened to be in Orlando, Florida on my honeymoon, my lovely wife gave me permission to fly out to New Mexico attend the Wirefly X-Prize Cup. I arrived around 9am to discover that the first attempt by Armadillo Aerospace to win the Northrop Grumman Lunar Lander Challenge was scrubbed due to a clogged fuel igniter. The second attempt was after lunch and everything went great for the first leg of the flight. Refueling appeared to be going fine when the announcers reported that there appeared to be another clog in a fuel line. This was reported to have been cleared, and the flight appeared to go fine. Due to a requirement of the prize the vehicle has to hover over the landing pad until 90 seconds of flight time is complete. During the last 7 seconds of this hover the vehicle fell. When the dust cleared the module was lying on its side. is reporting that the dust may have been the problem. We won't know until Carmack makes a report.

Jason Silverman from Wired Science is blogging about it, and has spoken to Carmack. I saw Silverman there in the Masten Space tent (David Masten has been a fabulous host for AA enthusiasts). Carmack is reported as saying that the clog from this morning was the cause of the crash this afternoon but the damage to the vehicle is minimal.

On the second day I swore to get there early enough to see the first flight. I got from Las Cruses to the airforce base in 50 minutes, but they wouldn't open the west gate for an hour, and then the bus from the parking lot to the show took another 25 minutes so I got there around 8:30am and the team was already deployed. The first leg of the attempt went well, but on the return flight there was a problem immediately after takeoff and an abort. As with yesterday's attempt, the problem was a blowout in the graphite sleeve of the engine. While out in the field they moved the engine from Pixel to the module. I believe the intention was to fly it back after the refit but the X-Prize people told them that this was not an acceptable repair as the engine was not "carried" onto the field (it was on the truck).

The final attempt was after lunch.. and with much anticipation we waited through the setup process, only to be rewarded with a failure to liftoff the pad for the first leg. I saw a plume of LOX cover the pad at about 2 of the countdown.. then flames covered the pad and engulfed the engine. It was over in a matter of seconds. John (in his white shirt) and the others (in their blue outfits) turned towards the camera and walked away shortly after. A fire truck was called in to put out the smoldering vehicle.

Last I heard the AST was out looking at the debris and the rest of the launch window was scrubbed. There would be no more attempts today.

I got some awesome sunburn.

Tuesday, April 24, 2007

FreeSynd version 0.2 released

The never ending effort to recreate a game from 1993 continues. There's now nine developers in the project and none of us do much. Every now and then I get bored and fix something.. go to check it in and discover that, shock, someone else has checked something in too! Then I have to update and resolve conflicts. Take the good with the bad I guess.

Anyway, in release 0.2 you will be happy to discover that we have done some work to get sound faithfully reproduced. For a while, we were focusing on music and trying to get the SDL midi synthesiser to play back this ancient XMIDI format. Believe it or not, this was actually acheived. Slight problem though, Syndicate used custom instruments. This was not uncommon at the time. The result was that the music just didn't sound good.. but it was good enough to ignore for a while.

Having declared that I wasn't going to touch sound.. I got bored one day and changed my mind. I told myself that I really ment I wasn't going to touch music so fiddling with the sound effects was fine. Turns out the sound effects were stored in the data files in much the same way as the sprites are, so it wasn't difficult to get it going. Pretty soon I had the whooshy menu sounds going.. so then I moved onto the weapons and other in-game sounds.

After completing that I figured, what the hell, might as well look at music. Turns out that SDL_Mixer uses a library called timidity to convert MIDI to wav output.. I actually thought it used whatever real MIDI hardware you had.. but apparently not. Anyway, SDL_Mixer will read a file called timidity.cfg in the current directory, in which you can specify custom instruments. You can download packs of these instruments, along with a suitable config file, from various places on the web. At first I figured this was the solution to the custom instrument problem.

Unfortunately, Syndicate predates all this stuff. Sure, MIDI was around when Syndicate came out. Sure, XMIDI is a MIDI format. But your average home PC that Syndicate ran on didn't have MIDI hardware.. it had an adlib card, or a sound blaster.. so that's what Bullfrog made their music for. Some people owned Amigas, and I'm sure Syndicate for the Amiga used the Amiga MIDI hardware to play beautiful sound.. but on a PC of the day, the best you could hope for was that the user had a Gravis Ultra Sound card.. and that's was so rare that Bullfrog never bothered to release GUS support for Syndicate.

Which is a shame, cause it turns out that the instrument format used by timidity is none other than the GUS instrument patch format. So, if Bullfrog had supported the GUS when they released Syndicate, we'd have faithful XMIDI playback right now. But they didn't.

Of course, if anyone out there knows how to make GUS patches from a sample.opl file, please, send me an email.

Instead, what I did was take some advice that someone gave me a while ago: just press CTRL-F6 in dosbox and save a WAV of the original game music. I then edited the wav in Audacity, exported it as an mp3, dumped it in the FreeSynd directory and told SDL_Mixer to play it. I did this for the intro and the great mood music for actual gameplay.

Of course, that gave me the problem that the intro music (and sound effects) were not synchronized with the FLI playback. So I tried fiddling with the frames-per-second of the FLI.. that gave me about half a solution.. but the real problem was that there are actual pauses in the intro.. there's a big table of them. They mainly correspond with those captions you see down the bottom of the screen (eg "CITY NAME: NEW HESSEN EUROPE") which I also wasn't doing. Once I started displaying the captions and doing the pauses, the mp3 started to line up.

So there ya go.. another release of FreeSynd. Right on track to being feature complete by 2013.

Wednesday, April 11, 2007

Boomerang 2

I was recently asked what I would do differently if I was writing a decompiler from scratch today. Having worked on decompilers for the past 9 years myself and worked with others who have worked on decompilers for longer still, I like to think we now know enough about it to recognise some of the mistakes we've made and identify some areas of improvement.

The primary difficulty of decompilation is that most analysis requires interprocedural information. Most everyone recognises this need early on so there's an assumption that you need to keep the intermediate representation for the entire program in memory at the same time. For many years we've had a hell of a lot of memory to play with (4 gig will be standard on desktop PCs next year) and with 64 bit architectures and virtual memory you can swap to disk for as much memory as you need. So it would appear that structuring a decompiler like a compiler, with intermediate disk formats for each compilation module is unnecessary. I think this is a mistake.

Having intermediate disk forms is more than just a solution to the memory issue. For a start, there's the ability to start and stop the analysis. In compilation, this is used to great effect when making incremental changes to source files; the files that are not changed do not need to be recompiled to their intermediate disk forms. It's a rare use case where one incrementally changes an input binary to a decompiler, (this does happen though, for example, when doing incremental comparisons of different versions of a program), but a decompilation takes a long time and a single bug can crash the decompiler resulting in hours of lost work. Interruptability alone is justification for intermediate disk forms, but there's another reason.

Because decompilation is still experimental engineering, inspection of intermediate forms is important. The Boomerang decompiler had a number of ways in which we could inspect the intermediate representation. We could stop the decompilation early, print out call graphs, dataflow graphs and register transfer language (RTL). A number of attempts were made at producing a GUI.. the primary purpose being to provide feedback on the progress of the decompilation and to allow inspection at the different stages. Tools to convert intermediate disk forms (which should be stored as efficiently as practical) into a form that is presentable to an engineer are much better seperated from the GUI, which now becomes primarily for feedback of progress.

This suggests another benefit of intermediate disk forms: no longer is it necessary to have a single tool, "the decompiler", to work on the intermediate representation. The decompiler can be seperated into individual tools which do a specific job and do it well. So what kind of tools do we need?

Firstly, a tool which uses a loader library to put the executable image into memory, and an instruction decoder library to turn individual instructions into intemediate representation, would use the variety of techniques that we've developed over the years to find all the code in an executable and, using another library, output it in the intermediate disk forms.

The inspection tools can be used at this point to confirm that all the code has been found and is loaded correctly. Because the intermediate representation is on disk, in a collection of files, the engineer can make a backup of these files and the decoding stage not need be repeated should some later analysis mess up the decompilation.

Following the decoding stage, a lot of analysis and data gathering occurs. Converting the intermediate representation to SSA form. Performing use/def analysis, liveness analysis, parameter analysis, etc. All this information could go into seperate files.. that way the previous intermediate forms can be kept around to do other analysis on, and an invalid analysis result can be recalculated without affecting other analysis phases.

After collecting all this information, the process of decompilation is essentially just transforming the intermediate representation from one form to another. As such, the workhorse of the decompiler is the transformation tool. It should load up the appropriate parts of the intermediate representation, read a script written in a domain specific language and then write back out the intermediate representation.

Often a transformation will require the incremental update of an analysis. I believe this can be acheived using a simple timestamp system on the intermediate disk forms. Yes, what I'm saying is that something similar to a Makefile can be used to drive the entire decompilation process.

The last tool, of course, is the code generation tool. For each designed language we need a tool that will take the intermediate representation and produce "source code" files.

That's enough about architecture. Already I've described a decompiler system which is very different to anything that has been built todate. If you're thinking about writing a decompiler, I hope you'll consider something similar to this.

Another thing I like to think I've learnt over the years of working on decompilers is that it sucks having to come up with an intermediate representation all by yourself. In fact, coming up with an intermediate representation for compilers could be a life time obsession all on its own. There's a lot of schools of thought on the subject. Obviously, something like the tuples of simple compiler is not a lot of good for decompiler. One needs to at least represent all the statements of a high level language as well as the individual instructions you might see in an assembly listing. There's a lot of work in it.. so why not take some advice from people who think about this kind of stuff?

The LLVM Compiler Infrastructure Project has a well thought out "virtual instruction set" which allows such complicated operands that it can express high level languages to such a degree that a simple PERL script can turn a C program into LLVM instructions (not that I recommend that). Perhaps more importantly, it has a mature, efficient on-disk representation and a number of useful analysis phases that work on it. There's an active community where you can report bugs, get help and recruit interested parties. I think you could do worse.

Tuesday, March 13, 2007

Almost Have A Game Engine Here..

What's the most annoying thing about trying to write a game engine? Ohh, I'm spoiled for choice, ok, I think the most annoying thing is getting together some half decent looking art so you don't go insane testing your engine with stick figures. Well, I recently came up with an interesting solution.. why not use some existing art from one of your most favourite games?

You may note, I've done this before. This time, I picked a game that is a little more recent, but not too recent, GTA3. No, not Vice City, not San Andreas, but those two are the same engine, just updated some.

As I've mentioned before, I have a liking of the OGRE graphics engine. So the first order of business was to get the models out of GTA3 and into OGRE's mesh format. The format used by GTA3 is the Renderman DFF file format. The individual dff files are concatenated together in the models\gta3.img file, which is indexed by the models\gta3.dir file. There's plenty of tools around to extract the GTA3 img file, so I didn't bother writing one.

I wrote a tool called dff2ogre (source) to convert a single model into a mesh.xml and optionally a skeleton.xml file. Using the OGRE command line tools, you can then convert the xml files into their binary forms. I put the resulting mesh/skeleton files into media\models in my OGRE directory and modified one of the sample programs to display it.

The first thing I noticed was that there were no textures.. this was to be expected as I hadn't converted any of them. The second thing I noticed was that the Y and Z axises were swapped. I should have went and fixed my converter to take care of this, but instead I just did a rotation about the X axis and forgot about it. This made a lot of my later code confusing and I wish I had bothered to correct the problem earlier. May this be a warning to you.

So, how about those textures? GTA3 stores textures in TXD files. Again, there are plenty of tools around to extract the textures from a TXD. I chose to extract them as TGA files and put them in the media\materials\textures directory of my OGRE directory. You also need to make material scripts with an entry for each texture, and some of the textures need scene_blend alpha_blend / depth_write off set in them (glass, trees, etc). I put my scripts in the media\materials\scripts directory and fired up my sample program again and now had lovely textures.

The next big problem was taking all these individual models and turning them into a city. Turns out there are files with the IPL extension in data\maps which list each model and its position and rotation in the world. This actually took some fiddling to get right. Again, the co-ordinate system is different, so you need to change the rotation, swap the Y and Z axis and negate one of them. The result was a city I could ghost around in. I only did the first island.

At this point, allow me to tell you how fantastic OGRE's scene manager is. I loaded up over 700 unique meshes, over 200,000 triangles, and ghosting around was smooth as if I only had 200 triangles loaded. The original game didn't do it this way, it would unload and reload meshes whenever you crossed arbitary zone boundaries. This is why there is so much effort to provide the textures in seperate TXD files and associate those files with the meshes, so the textures can be unloaded when they are not needed.

Anyway, the next little challenge was converting the player model to OGRE format. This was the first DFF with a skeleton that I had tried to convert and it took a little effort to get going. I modified dff2ogre to look for the PED.IFP file, which contains all the character animations in the game, and converted them to OGRE animations. This, of course, didn't work first time and took a lot of fiddling to get going well. Again, those swapped axises are a bitch.

I wrote some really simple ray casting code to keep the player character above ground. Basically, you just start at a point in the middle of the mesh and cast a ray straight down. OGRE gives you back a sorted list of the entities in the world that you have hit. Ignoring the player entity itself, the first entity you hit is likely the ground.. but you really need to check every polygon in every entity that OGRE claims you have hit to ensure that you find the polygon that is closest to your starting position. Once I had the intersection point with that polygon I modified the position of the player node so the feet of the player mesh were above that point.

Similarly, you can cast a ray from the middle of the player mesh in the current direction and prevent the movement in that direction if it will result in the mesh intersecting some part of the world. Play the right animation and you now have a player character that can run around the world.

Thing is, running around the world was only a small part of GTA3. A much bigger part.. one could even say, the reason you played the game.. was vehicles. So I picked a random vehicle model (the kuruma if you're interested) and converted it to OGRE format. Like the player character, vehicle models have skeletons. Some parts of the vehicle are low poly or damaged parts, so I hid the submeshes that were attached to those bones. The models look good.

So how do we make this car go? At first, I tried writing similar ray casting code to what I had done with the player character. The results were unrealistic, to say the least, and I knew it would be a lot more effort to get anything reasonable out of it. As a first try it was ok, but something was lacking.

Physics. OGRE has tight bindings to the Open Dynamics Engine, so I figured this would be my best bet. Unfortunately, the OGRE bindings do not include the "new" trimesh collision object, so making the vehicle dynamics object interact with the world was still up to me in the form of ray casting. The result was less than impressive. I tried both simulating the vehicle as a box which hovers over the terrain and as a box with four wheels connected with a suspension. Neither resulted in good results.

So, after feeling lost for a while, I decided to try the Bullet Physics Library. I expected it to be difficult to use, but was pleasantly surprised. The trimesh collision objects work very well and are impressively fast (again, over 700 models, 200,000 polygons and excellent performance). My only wish is that I could use a trimesh for the vehicle model.. but for some reason you can't have weight assigned to trimesh collision objects (they can't move). Most importantly, Bullet has a vehicle object, so getting some basic car dynamics going is easy.

Unfortunately, even with extensive tweaking and fiddling, I was unable to get my vehicles to not flip over so much and, more annoyingly, not get embedded into the ground or drive through walls. Frustration abounds! I spent way too much time worrying about this and decided to just move on. Maybe there will be improvements to Bullet's vehicle class in the future.

The other major facet of GTA3 was the weapons. Like the wheels on the vehicles, GTA3 puts all the meshes for weapons in a single file, creatively called weapons.dff. I actually manually extracted these from the mesh.xml file, it was easier than writing a tool to do it. After screwing around with trying to place the weapon into the player's hand by following bones and applying rotations and translations manually, I actually bothered to read the docs and discovered that OGRE provides a function called attachEntityToBone() which does it all for me. Fun eh?

After parsing data\weapons.dat I had all the information I needed to animate the player character and do "instantaneous" firing. Of course, I had nothing to shoot at, so I got myself another pedestrian model (a mafia dude) and wrote code to animate him to receive damage and fall down when he died. The result was almost convincing.

What was and still is, lacking is the particle physics which make the game look so pretty. There is a nice big data file called particle.cfg which outlines how to make these particle effects, but it contains LOTS of parameters and I'm not sure what half of them mean. Of course, it seems that their particle systems are really only one particle.. in OGRE I would just use a billboard. I ended up doing this for the muzzle flash of the weapons, and it looks reasonable, but its not very exciting.

And so, I guess we're up to the point in the story where I explain what I have learned. Writing a game engine is a lot more fun when you have art to show and a knowledge that the art is in a form that can work. Unfortunately, writing a game engine is still a lot of work. I hope one day I'll finish this project. Maybe someone will put together a GTA3 mod with all free art and my engine could be used to make an all free game. Maybe someone would like to work on making this project playable. Maybe someone would like to make a multiplayer game using it as a base. If so, let me know and I'll release the code.. but at the moment it is largely useless.

Friday, February 16, 2007

It's better than a binary only driver..

Recently, Greg K.H. made an offer to write free linux kernel drivers to any company that will provide him with docs to their hardware. Some BSD folks had a problem with Greg making this offer to people who would only give up their docs if the developer signed an NDA. Theo de Raadt chimed in declaring that "it is a fucking farce", which is his usual way. As far as they are concerned, an open source driver without docs is not open at all. That may be so, but I still think having source code.. any source code.. which actually works, is better than having no docs or source code.

It would be nice if companies would hand over docs without an NDA.. that is certainly preferable for everyone.. but some of them just won't, and getting them to hand over docs under an NDA with the ok for someone to write a free driver (be it GPL or BSD licensed) - that's something and it shouldn't be ignored.

Now, if companies start doing this and drivers start showing up as GPL, but without the documentation, you guys can go ask the companies for the docs yourself (with or without NDA) and make your own driver using the GPL driver as a reference implementation.. or you can reverse engineer the GPL driver, it's certainly a hell of a lot easier than trying to reverse engineer a binary driver isn't it?

I'm sure Greg and his merry band will be pressing for docs without NDA, but in the event that an NDA is the only way forward, it's certainly better than no driver at all.

Finally, just let me say, docs are not the be all of driver development. Great to have them, but docs can be wrong and you won't have any idea until you implement them. At least a driver, you can test. So unless you intend to start asking hardware companies for their VHDL, you're better off having a working source code driver to confirm the docs (if you can get em) are accurate.

Thursday, February 08, 2007

Distributed vs Centralized revision control

In the last few years we've seen the rise of the so called distributed revision control systems. These are, essentially, tool support for maintaining your own personal version of an open source project.

Let's take, as an example, the WINE project. They use Git, the same version control system as the Linux kernel. Suppose I have a favourite application that I would like to run using WINE. There might be some things that my app requires which WINE doesn't yet support. I don't mind implementing these things, but I really couldn't be bothered going through the hassle of satisfying every whim of the WINE developers (how they like their patches submitted, how they like their changelog written, etc).

What happens when WINE releases a new version which I want to upgrade to? Do I keep an entire source code tree around just to run my favorite app? What if I have more than one favorite app? Git lets me update my source code tree and merge any updates that conflict with my local changes. But it does more than that.. it lets me "check in" my local changes, to a local repository, and if some member of the WINE team happens to implement something that I implemented to get my favourite app to work, I can tell Git to drop my change and use the WINE developers (cause he probably knows what he's doing more than I do). Git makes it really easy to maintain my personal tree.

Let us, for a moment, consider the alternative. Centralized revision control systems, like CVS, don't make this easy. Sure, I can make local changes to the source tree then, later, I can update and fix any conflicts and, this way, I can maintain a personal tree, but it is not easy because I can't "check in" my changes. This, I think, actually has a beneficial upside: it encourages people to go through the effort to sanitize their personal tree and check it into the repository. These changes become part of the core distribution and everyone benefits. Not only can I now run my favorite app, but everyone who wants to run that app can also run it.

Unfortunately, it takes a lot of time and effort to sanitize your tree.. and not everyone wants to do that. Beyond all other reasons, I believe this is why distributed revision control tools exist. Some people might want their "personal" tree to be for their personal use only, but I think the majority of people don't really care.. they keep their tree personal just because it is too much effort to make it public. Even with Git (and the others) it is easy to make your personal changes public, but most people don't bother because it is *some* effort. It is only the core developers of a project which make their changes public; the same developers that would check in their changes to the repository if they were using a centralized revision control system.

Is there as some middle ground? I think there is.. using the centralized revision control system, Subversion(SVN) it is very easy to create branches. Unlike CVS, which made branching a nightmare, SVN provides a server-side copy command which uses copy-on-change semantics. As such, making a branch is really just copying the tree to somewhere else in the repository, usually a directory called /branches. Also, SVN makes it easy to setup per-directory access permissions.

So, taking the example above, what would it be like if the WINE project decided to use Subversion, and to use it properly? If they set it up right, I could go to the website and download a script.. let's call it I could then run ./ QuantumG and it would connect to the source code repository and create me an account. The account would be read-only to the entire repository, except to the directory /branches/QuantumG/. Under there it would copy the WINE source code, then the script would fetch the source code to my machine, change into the directory, and quit.

I can now make my changes and check them into the WINE repository. One of the great things about Subversion is that it gives a unique number (called the revision number) to every check in. So, should I get to the point where my favorite app is now working, I might feel like telling the world.. so I'd post a message to the wine-devel mailing list and say "hey everybody, I just got my favorite app to work! Take a look, the revision number is 23893." People who liked that app and wanted to run it with WINE would just merge the changes from my branch into their own branch. Maybe one of these people would think "Gee, that's really cool, I think everyone should have that, I'm going to sanitize these changes and get it checked into the trunk." They might not consider this much work because they haven't needed to do all the work I did to get it working in the first place.

Of course, all this can be done with a distributed revision control system too, but it is significantly more effort. Maybe this effort will go down in the future. Maybe something approaching the above ideal can be achieved using distributed revision control systems and public branch repositories. Hopefully, the people who make Git will see the wisdom of making all trees public until you explicitly set them to be private (for those people who really do want a private branch) instead of the current practice of making trees private by default.

Monday, January 15, 2007

People that provide rpm files, but not tar.gz/tgz files, should be shot. Typically this isn't so much of a problem, as I can use alien on my debian based distro to convert an rpm into a deb, but I'm in the road right now and don't have access to a machine with that. So, after struggling to get the rpm utilities installed on a naked linux box, where I didn't have root, I've decided that enough is enough. I figure what I need is a web site where I can submit the rpm and it will create a tar.gz for me (ala And I figure that other people need this too. So I've sucked up the cost and done it. Here it is:

Of course, I've put a lot of Google ads on the site. Hopefully this will give me enough income after a year to cover the renewal of the registration and the hosting. Otherwise I might just let it lapse.