R.I.P. Dorkess

Dorkess (AKA Poguita): March 27, 1992-January 27, 2012

The twins, Poguita and Ping Pong (as well as two others we didn't keep, which seemed to be from different fathers) were born at our house on March 27, 1992. Poguita (yes, that is an English/Spanish pun) was named for the distinctive white stripe on her nose.

As with Slinky, I later started calling her Dorkess based on her distinctive personality. She was always extremely high strung, even for a cat. The slightest sudden noise would cause her to do her characteristic "vertical takeoff and landing" - shooting a couple feet into the air - then flee in terror, either out of the house or into a closet to hide. I used to say she never walks anywhere, she just sprints.

Her dorkiness led to a wide array of memorable incidents. In one case me, my mom, and one of my friends were watching something scary on TV. At one point, my mom screamed, at which point the entire clothes hamper exploded, throwing various pieces of clothing into the air. As it turned out, Dorkess had been sleeping in it, and completely freaked out when my mom screamed.

She was also an extremely finicky cat; nothing was acceptable to her unless you did it exactly how she wanted it. Perhaps she was narcissistic, as she did, after all, love staring at herself in shiny surfaces. Though she lacked the congenital metabolic problems Slinky had - and as a result was not so thin and slinky - she seemed to have some kind of a deformity on her back feet such that she was never able to fully retract her claws, resulting in a distinctive clicking as she walked on hard surfaces.

As she got older, she gained another distinctive attribute. For a variety of reasons, from wanting something to letting people know she was entering the house, as well as some which were just mysterious, she would use just about every muscle in her body to howl at an unbelievable volume, which vaguely resembled a baby crying; as one friend put it the first time he heard it, "What the heck was that?". On a couple occasions she even howled so loudly that she got dogs howling along with her. One particularly interesting feature of this was that, when howling, her meows were neither identical nor random, but followed a well-established pitch contour (e.g. there was always a large drop in pitch during the third meow).

Apart from a couple of serious but temporary cases where she was severely sick (and could conceivably have died), she was in fairly good health until just recently (though she certainly showed her age). She did end up going completely deaf a few years ago, but this was probably for the best, as afterwards she was much calmer and less high strung.

At one point a couple years ago, she began accumulating fluid around her lungs, making it difficult to breath. This probably would have killed her, but with regular medication with Lasix (the drug) the problem essentially went away (though the Lasix did seem to be doing some harm to her kidneys and liver). We never did learn the root cause, and it's possible that's ultimately related to why she died. For one reason or another, she eventually decided that she wanted to die, and simply stopped eating. This, on top of her already weakened state due to old age, resulted in her death a week later. The ultimate reason for this choice remains unknown.


One of Dorkess' common places to sleep




The twins: Dorkess (left) and Slinky (right)


The twins sleeping, Zen-style; best guess is that Slinky is in front, Dorkess is in back


Me and Dorkess, 5-10 years ago

Rest in peace, Dorkess.

Public Service Announcement

While solar panels are dark blue, almost black, they are also reflective. This means that they will likely appear white or some other bright color, which may be a big shock (and a big aesthetic problem) if you have a dark roof and the panels are clearly visible.

My parents are NOT amused.

Update: Actually this is only the case when the sky is cloudy, which it was the day my parents had the panels installed. When the sky is clear they look like they do without the reflection.

RIP Bigg'ns

The big, old puppy

June 17, 1997-September 21, 2010

When Size Matters

I and another person, who is an IT professional, spent some time this weekend doing some volunteer work at a charity - more specifically, a homeless shelter and rehabilitation clinic, though any more details information isn't particularly relevant. Our task was to do "computer stuff", including basic maintenance on all their computers (those in the administration offices and those for use by residents), as well as take a look at what they had in storage.

While the computers available to residents weren't bad (about 5 years old or less), the situation in the office was more grim. Almost all of the computers were Pentium 3s and 4s, most with 256 megs of RAM and running Windows 2000 with Internet Explorer 6. That's right, Windows 2000 and IE6, which are both several years past end of life, and thus inherently insecure; oh, and did I mention that all the office staff run with admin privileges?

So, we started off with the easy stuff: chkdsk (full disk surface scan) and defrag on all of them. We intended to run virus scans on all of them, but were repeatedly thwarted by bad CD-ROM drives and stupid video cards that prevented us from using the AV boot disks I'd burned for the occasion (as I didn't trust the computers to not have rootkits), and eventually we had to resort on many computers to just running the AV from inside Windows.

While there were a few more specific problems with the computers, one universal complaint among the office staff was that the computers were anywhere from slow to extremely slow. While defrag no doubt helped a little with that (the computers were between 5 and 40% fragmented), the primary problem appeared to be something else entirely. Most of the computers had 256 megs of RAM, and on boot most of them were using anywhere from 210 to 260 megs of memory; add in 20 megs of memory for IE (I wanted to switch them to Firefox or a newer version of IE, but as both of those used significantly more memory that wasn't really an option), 30-40 megs for an Office app or two, and the observation that Windows starts disk-thrashing when you get to about 85% of physical memory used (about 220 megs), and it was clear that the computers were severely disk-thrashing.

So, memory upgrades were the obvious prescription. But that raises the question: why were the computers using so much memory to begin with? Anyone who remembers back from the day 10 years ago, including both myself and the other guy, can tell you that 256 megs should be plenty for Windows 2000 (and perhaps even XP). Given all the available evidence - that the computers ran Windows 2000 and IE6 in admin mode, our inability to do a proper virus scan on most of them, and the fact that there was a lot of unaccounted for memory (memory that was in use but not accounted for by running processes or kernel allocations) - naturally we assumed that they were severely infested with malware.

As irony would have it, the cause was actually just the opposite. On Sunday I finally got fed up with the situation, and decided to try a drastic experiment inspired with some experience in the past: I uninstalled the AVG Free antivirus that was on most of the computers. This experiment paid off; it turns out that AVG was in fact using a full 130 megs of memory. Without it, Windows was using about 80 megs of memory at boot, which is very much like what we remembered back from the day, when virus scanners took 30-40 megs, which would leave about 110 of the 256 megs available for running applications comfortably.

So... now what? Well, another 256 megs memory would put an end to the problem. But in the mean time, I had a stop-gap measure: get a smaller AV. Out of my previous tests on the best of the free AVs, the best current-generation AV in this regard was Avira AntiVir Personal, weighing in at about 95 megs. So, I switched all of the computers over to that. This reduced the amount of memory in use at boot to about 180 megs, leaving about 40 megs available for comfortably running applications. While that isn't a huge amount, I'm hoping that in a case this severe it will substantially improve performance until more memory can be acquired cheaply.

On that topic, I actually ordered a batch of used and very cheap 256 meg sticks off eBay, and I'm hoping to be able to test them out (which will take a couple days to thoroughly test this quantity of sticks) and get them installed this weekend or next, bringing the computers up to 512 megs; assuming, of course, that these computers (most of them Dells) aren't of the extremely finicky variety that reject all but very closely-matched memory. At 512 megs, it becomes reasonable to start looking at upgrading the computers to XP (pretty sure it wouldn't be a good idea to try Vista on those computers) and Firefox, which would go a long way to improving security (and, of course, at that point it would be worth making them not run as admin).

On one last note, one thing that continues to stump both of us is how on one computer the fonts in IE are enormous. On typical web pages lines of text are often 1-1.5 inches tall, making it extremely difficult to use the web. We both independently looked at both font settings and accessibility features in both IE and Windows, but none of those proved to be the cause. Setting fonts to smallest in IE made text more reasonable, but on some pages the text was actually "smallest", making it impossibly small to read; thus this was not a sufficient solution to the problem.

& Twitter

On a tangentially-related note, I've also joined Twitter. This one I have a very specific purpose for: link spam (the stuff I formerly sent to friends on IM services and pasted into chat room). A place where I can simply link to interesting, funny, or otherwise linkable stuff I find online, without giving any commentary, and I can post stuff too insignificant or off-topic to clutter this blog with (although I may occasionally post short random thoughts, as well).

Those of you who think this blog has had entirely too little computer/programming stuff on it lately should check out my Twitter feed. While these days most of the stuff I think long and hard about (and blog about) is linguistics, the majority of the stuff I read online remains about computers, video games, and programming. So, expect the majority of my tweets to be on those topics, like this blog was, back before I became interested in linguistics.

There are several ways you can access my tweets. If you're on Twitter, you can simply follow me. If you're not, you can either see the mini-Twitter feed now on the blog sidebar, read the Twitter tab of my FaceBook page, or subscribe to the RSS version of my Twitter feed.

& Facebook

So, I joined Facebook.

Not much to say about it. It was purely for practical reasons (because an organization I'm with apparently now uses Facebook to communicate with their members with regard to things like meeting dates), so I'm not planning on doing too much with it. I'll take a look at the features and we'll see. If I can find a use for some part of it (that I actually care to use) I might use it for that; if not I'll just use it as a friend hub and one more way to find me on the internet.

Die! *smash*

I have squashed the mystery.

I did some chatting with Merlin (never mind who that is, just that he knows some about the electrical engineering of computers, as well as programming). He gave me a couple of theoretical possibilities what the problem could be, some of which could be tested, others were simply components on the motherboard that I had no way to individually test.

One thing was the power supply. According to him, it's possible that when data is being sent from the memory to the controller (in 8 blocks of 64 bits), if the power supply is flaky the voltage could droop over time, which could hypothetically explain why the bit only fails only once in each cache line even if the problem is in one of those 64 data lines. However, this was easily disproved, as I do have other power supplies.

More importantly, while talking to him I thought of my grandma's computer (my computer prior to 2001), which had the same type of memory. While this computer is too old to support 512 meg DIMMs (this was why I couldn't just use it to verify the DIMMs worked and be done with it), it did have some smaller DIMMs in it (256 meg). See where this is going?

Now I had more than two DIMMs, and with them I was able to demonstrate that the same bit failure occurred with any combination of two DIMMs (although the frequency of the error did vary some depending on the pair used). This proved conclusively that the DIMMs themselves were not responsible, and the problem had to reside in the common element - the motherboard or the CPU. This appears to be a problem that only shows up when both DIMM slots were full.

Now, it's still possible that it could be a software (BIOS) problem that could be fixed by updating the BIOS, but I don't care to try that, for the reason I mentioned previously.

...Now What?

A few weeks ago my parents' desktop died. This was my old Athlon XP computer I had before I bought the one I have now (about a year and a half ago). A bit of trivial diagnostics demonstrated that either the CPU or motherboard had died, and I didn't have the parts necessary to determine which. So, my dad went looking on eBay for a replacement motherboard and CPU to go with the existing memory, as they didn't really have the money to buy a new computer right now (actually, I was the one who did most of the looking at the specs, to make sure it would work).

A few days ago, the motherboard+CPU arrived, and I quickly set to determining whether or not they worked, as the amount of time to return it was limited. As my past experiences have made me a little paranoid in that respect, naturally the first thing I did was run MemTest 86 on it.

While it seemed to work for the most part, about once every pass (took a couple hours) on test #7, an error would show up. After leaving it running overnight, some patterns emerged. The error was always the 0x02000000 bit getting set when it should be cleared, and it usually occurred when the value written to the memory was 0xFDxxxxxx (less commonly, 0xF9xxxxxx). The base address of the error seemed to always be at 0x3C, 0x7C, 0xBC, or 0xFC. The errors also appeared to cluster in the low 512 megs of the memory space.

In short, it appeared to be 1 bit every 64 bytes, where the containing byte changes from 11111x01 to 11111x11.

Separately, neither of the two 512-meg DIMMs shows this problem, regardless of which of the two sockets the DIMM is in (as tested by running MemTest 86 overnight, which would be expected to produce about a dozen errors). However, when put in in one order, this error occurs. Peculiarly, when put in the opposite order, MemTest begins spewing out memory errors before soon crashing (presumably due to memory errors in the locations the program is at).

So, where is the problem? Well, I wish I knew the answer to that.

The fact that both DIMMs worked correctly when alone suggests that the DIMMs are good (these are the same ones that were used in the computer that failed, and to my knowledge there was nothing wrong with them then). The fact that each DIMM works in both sockets suggests that it's not a bad socket. The fact that it's every 64 bytes tells me that it's not one of the data lines on the DIMMs or on the motherboard, as the data width is 64 bits (64 pins). The fact that the error period isn't into the kilobytes indicates that it's not a CPU cache failure, as I saw in the past.

64 bytes is the size of the cache line for the CPU, which seems to hint that it's somewhere after where the 64-bit memory reads are assembled into whole cache lines; unfortunately, I don't know where exactly this occurs, to narrow down the possibilities. Yet the fact that it only seems to occur in the lowest 512 megs of the memory space is very suspicious, and seems to suggest something with one of the DIMMs, sockets, or data paths on the motherboard, which appear to already be ruled out from earlier tests.

So, I'm really at a loss as to what to make of this and what to do next, and I've got three days left to do it. I can't test the memory on another computer, because I don't have another computer to test it on. The BIOS could use updating, which could theoretically fix the problem, but I've been reluctant to do that because it's a trivial way to say "You broke it, I'm not giving you a refund!"

I suppose I need to try mixing and matching the CPUs and motherboards. I need to do that anyway, to find out exactly what broke on the old computer, but it should also tell me whether the problem is in the CPU or motherboard (though nothing more specific than that).

EPIC FAIL

I got a letter from Wells Fargo bank with a new credit card, today. Nothing out of the ordinary in that respect, but the extent Wells Fargo failed in the process is pretty remarkable.

The first page was all the stuff you'd expect - credit card glued on, as well as account number and other info, and instructions to use it. The second page is shown below (the back is completely blank):



Looks completely innocuous and generic, right? Except for that black block in the lower right that I filled in. There is a bar-code and, in 6 point font, a number of numbers (most that I don't recognize), including the credit card number itself. If you weren't looking for it, you would most certainly never have seen it.

The number of people who have thrown that page away without ever realizing it had their credit card number on it is surely uncountable. Funny how a page about guarding against fraud sets you up perfectly for fraud by printing entirely unnecessary sensitive information on a completely generic page (that would have been cheaper to print without that information). You have to wonder if there's some malicious intent, there.

So, after the facepalm, I go online to activate the new card. After logging in and going to the activation page on Wells Fargo's (secure) web site, I'm met by this page:



Birth date? Work phone number? Really? It's been known for a long time that "security questions" are major security vulnerabilities, but this may just set a new record as to extent.

I can't say I can trust Wells Fargo after that rather brilliant display of insecurity.

What the Goat

The National Weather Service has issued a tornado warning for the South Los Angeles, Long Beach and Whittier [right about here] areas as a powerful new storm moves ashore.

Tornado Warning Issued for South Los Angeles, Long Beach, and Whittier

A tornado watch. In Los Angeles county. Has that ever happened before?

Computer Book Library

This post lists some of the computer books I have on my shelf, between text books and books I bought outside of school. This list is meant to provide readers with books they might be interested in reading, and so is limited to the books most likely to be of interest to others. While I list the versions that I have, myself, the links to the books on Amazon are to the most recent edition at the time of writing about them.

This post is likely to be updated from time to time in the future.

3D Game Engine Design, 2nd ed
David Eberly, Morgan Kaufman, 2006
Covers development of a 3D game engine that includes graphics, physics, and a few lesser topics (though the focus on the book is definitely graphics). Covers both the theory behind concepts and actual implementation of a complete working engine; this latter point makes it vastly superior to more typical graphics books, which usually cover the theory but not a complete implementation.

Artificial Intelligence, 5th ed
George Lugar, Pearson Education, 2004
Computer science textbook I used in the senior-level course.

C++ Programming: Program Design Including Data Structures,
D.S. Malik, Couse Technology, 2002
First year (for me) college textbook

Code Complete
Steve McConnell, Microsoft Press, 1993
Handbook of coding best practices for minimizing bugs and improving maintainability.

Developing Windows NT Device Drivers
Edward Dekker and Joseph Newcomer, Addison Wesley, 1999
A rather dated guide to programming Windows NT (4.0) device drivers.

Developing Your Own 32-Bit Operating System
Richard Burgess, SAMS Publishing, 1995
Prior to the Linux phenomenon, this was pretty much the only book that showed you how to create a full, real, working operating system for a modern computer (at the time, anyway). Throughout the book the author codes the example MMURTL (Message-based MUltitasking Real-Time kerneL), a (some redundancy, here) 32-bit message-passing, preemptive-multitasking operating system that runs on x86 computers, in 32-bit assembly + C, and several sample programs (including the command-line interpreter and debugger) in C.

Fundamentals of Computer Graphics, 2nd ed
Peter Shirley et al., A K Peters, 2005
A fourth-year (for me) college textbook. Like most books of its kind, it teaches you the theory behind graphics (and, if you're lucky, gives you pseudocode for some concepts), but leaves you on your own to figure out how to create a working graphics engine (if you have the need to do so).

Fundamentals of Database Systems, 5th ed
Ramez Elmasri and Shamkant Navathe, Pearson Education, 2007
A fourth-year (for me) college text book on databases. Covers from the basics to the advanced, as well as SQL programming, both in theory and practice.


Game Architecture and Design
Andrew Rollings and Dave Morris, Coriolis Group, 1999
A guide to the complete development process for a commercial game. The first section covers developing a game idea and balancing gameplay, the second section covers project and team management, and the third section covers development from architectural design (the thing code is based on) to production and postmortem analysis. The vast majority of the book is at a higher level, summarizing the entire game development process and the lessons learned by the author from his experience in commercial game development, though the author does create a (simple) working game in the process (several other game ideas are discussed in various chapters, but not developed into the full games).

Game Coding Complete, 3rd ed
Mike McShaffry et a., Charles River Media, 2009
A guide to the game development process and development of game systems. While the scope of material in this book is much the same as other game programming books (e.g. Tricks of the Windows Game Programming Gurus), this book distinguishes itself on quality and scalability. All game programming books invariably contain a guide to the various APIs your game will need to use (e.g. DirectX) and a survey of game technology (e.g. 3D graphics, AI, and networking). However, most books teach you from the perspective of a hobbyist getting into game programming, teaching you easy things that work okay for small games, but lack the power and scalability to deal with a large commercial game (and omit things that aren't necessary for small games).

This book dedicates itself to filling in those gaps, addressing frequently-omitted topics such as the build process, memory management and resource caching, event management, scripting support (the engine the author creates throughout the book is actually a data-driven engine based on Lua scripting), debugging, parallel programming, etc. Of course, it also contains the mandatory survey of game-related technologies, but I haven't looked at those parts and don't expect too much, as most of them are best left to their own books (graphics, physics, networks, AI, etc.), given the overwhelming broadness of those fields.

Programming Applications for Windows, 4th ed
Jeffrey Richter, Microsoft Press, 1999
Perhaps better described by its older name, Advanced Windows, this is the gold standard in "advanced" Windows API programming - things such as multithreading, advanced memory management, DLLs (including DLL injection and function hooking), exception-handling, and advanced window messaging.

Programming Windows, 5th ed
Charles Petzold, Microsoft Press, 1998
The first book to read on Windows API programming. Covers a broad range of topics from basic windows and controls to more advanced topics such as (basic) graphics, printing, multithreading, network communication, etc.

Programming Windows with MFC, 2nd ed
Jeff Prosise, Microsoft Press, 1999
The definitive guide to the Microsoft Foundation Class library, a C++ framework that wraps the Windows API. Analogous to Programming Windows, this was the book to read if you needed to learn MFC, though as MFC is easier to program than the Windows API, this book covers topics beyond those in Programming Windows. MFC is essentially obsolete now that .NET has become so common, though I'm told some people still have to deal with it in older software at their jobs.

Tricks of the Windows Game Programming Gurus
André LaMothe, SAMS Publishing, 1999
The Game Programming Gurus has been pretty well respected throughout its life. This was the 2D Windows game incarnation of the series (also see the companion Tricks of the 3D Game Programming Gurus); it covered basic Windows programming, the various DirectX systems, and then a survey of the various fields in game programming (like those mentioned a ways back). As stated above, this (and presumably the 3D version, which I haven't seen) is more of an introduction to game programming than a reference that would be useful at a real game programming job.

Visual C# 2005 How to Program, 2nd ed
Paul Deitel, Pearson Education, 2005
Lower-division college textbook on C# programming (at my school C and C++ were first-year courses, C#/Java/etc. were second-year).

Lastly, a couple books on the list of things to buy:

Game Engine Architecture
Jason Gregory, A K Peters, 2009

Real-Time Rendering, 3rd ed
Tomas Akenine-Moller, Eric Haines, and Naty Hoffman, A K Peters, 2008

Bibliography - Programming

This post is a partial directory of the various programming and reverse-engineering I've done over the last 12 years, especially those that produced some manner of result (program, specification, or processed data). This list may omit projects that are too old, too obscure, too uninteresting, or that I just don't remember off the top of my head; it also omits most projects that were done as assignments or term projects in school. With a handful of exceptions, all of these are entirely my own work. With the exception of the few most significant projects being moved to the top, the list is in alphabetical order.

This list may undergo updates in the future.

(CHK) Starcraft Map File Format [reverse-engineering]
Reverse-engineering of most of the Starcraft map file format. This was my first modding community project, and it was for this that I was invited to join Campaign Creations in 1998. This consisted of repeated edits of a map in the Starcraft map editor (StarEdit) and then observing the changes in the map file it generates. Perhaps one of the most impressive parts of this accomplishment was that the vast majority of this was done using nothing more than the DOS edit.com utility and Windows calculator; no true hex editor, no disassembler or debugger (at that time I wasn't even familiar with reverse-engineering), etc.

It looks like this spec has become difficult to come by these days. Campaign Creations appears to no longer have it (I'll have to get that fixed) and only a few modified and/or butchered copies of it found on Google, some lacking credits for who wrote it. So, here's the version I still have on my computer.

MoPaQ 2000 [programming]
This (a.k.a. MPQ2K) was the project that really put the name Quantam on the Blizzard game modding map: the first stable, full-featured MPQ editor. Prior to this there was already a full-featured MPQ editor (I think the name was MPQEdit), however the extreme instability and bugginess meant that it was widely considered worse than nothing, and rarely used.

MPQ2K was a command-line user interface for the Lelik MPQ API, a library that hijacked the Starcraft Campaign Editor (StarEdit) and called the MPQ-writing functions it contained (as Starcraft maps are packaged into MPQ archives), without ever knowing the details of the MPQ format, itself (it's worth noting that this is where I learned about breaking and entering into processes and hooking functions). At the same time as the library, Lelik released a sample editor (I believe the name was MPQ Archiver) that the MPQ2K interface design used as a starting point; it was very clumsy and minimalistic, however, and lacked the major features that would make MPQ2K popular, such as scripting. MPQ2K remained the MPQ editor for several years, until cumulative speed improvements finally allowed WinMPQ, a graphical MPQ editor, to seize the title of most popular MPQ editor.

Understanding the significance of a practical MPQ editor requires some knowledge of the context. Prior to the use of MPQs, the only option to modify Starcraft game data, apart from what could be done in the map editor alone, was StarDraft, the predecessor to MPQDraft. StarDraft allowed in-memory patching of most Starcraft data files, allowing much more than was possible with the map editor alone (e.g. modification of sound effects, graphics, gameplay data such as unit statistics, etc.). While this was a hugely important development that essentially founded the Starcraft modding community (apart from custom maps), StarDraft suffered from several severe shortcomings that drastically limited its practicality: it was version-specific (meaning that every time a Starcraft patch was released StarDraft had to be manually updated by the coder before it could work with the new version), it could not replace music and certain other files, and, perhaps most significantly, it tended to actually slow down the game, degrading gameplay noticeably.

Thus, StarDraft was the first revolution in Starcraft modding, and use of MPQ files was the second. The replacement of StarDraft with custom MPQs as the basis for community mods solved many of these problems that plagued StarDraft. Music files could now be patched (although a handful of relatively minor files remained unpatchable until the coming of MPQDraft); as well, as MPQs were used natively by Starcraft and other Blizzard games, rather than requiring hacking into the game via StarDraft, this approach meant no gameplay degradation; it also meant this method could be applied to other Blizzard games that used MPQs, not merely Starcraft. This made StarDraft obsolete overnight.

MoPaQ File Format [reverse-engineering]
The complete reverse-engineering of the MPQ archive format and publishing of what remains the authoritative modder's specification the format. Most of this was performed during development of MoPaQ 2000 2.0. While Lelik reverse-engineered StarEdit sufficiently to allow LMPQAPI to call functions in the Blizzard MPQ API in StarEdit, he never actually looked at the MPQ format itself. Thus the work fell to me to provide functions that didn't exist in StarEdit, by writing code that edited the MPQs directly (code which was then integrated into LMPQAPI 2.0). This was also where I first learned how to reverse-engineer a program via disassembly and debugging. While I gave out a lot of information about the format to a number of people on forums and other media, I didn't actually release a full spec document until some time later (the official version of the spec is here, though as it's a wiki it's been known to be vandalized from time to time).

MPQDraft [reverse-engineering, programming]
The third revolution in Blizzard game modding, MPQDraft perfected the MPQ file technique. Like StarDraft, MPQDraft consisted of a loader that actively invaded the game being patched by a mod; however, MPQDraft suffered from none of the problems of StarDraft: it was version (and game) independent, it finally solved the problem of unpatchable files once and of all, and did not produce any gameplay degradation.

Like StarDraft, MPQDraft allowed the creation of "self-executing MPQs", which allow authors of mods to conveniently distribute large, complex mods in single executable files. However, MPQDraft added support for a plugin system, which allowed developers to add on new functionality to mods, while still making use of the basic functionality of MPQDraft. A couple examples of the most noteworthy plugins developed for MPQDraft are MemGraft (now obsolete), which allowed modification of data stored in the Starcraft executable itself (as opposed to in the Starcraft data files), and ThunderGraft (described below).

MPQDraft is now open-source, on SourceForge. Surprisingly, it still gets more than 600 downloads each month (this is only counting downloads through the SourceForge page; mirrors such as the one on Campaign Creations would not be counted), despite the fact that the most recent game it works on, Warcraft III, is about 8 years old, now.

ThunderGraft [reverse-engineering, programming]
The third of my major modding programs, ThunderGraft adding the ability to play modern audio compression formats (e.g. MP3 and Ogg Vorbis) to older Blizzard games, especially Starcraft. Prior to Warcraft III, Blizzard games used either raw PCM (Diablo) or compressed ADPCM (Starcraft, Diablo II, and Warcraft II) audio formats to store music and sound effects; both formats were undesirable for mods because they were either very bulky (in the case of PCM) or resulted in noticeable loss of audio quality with sub-optimal file sizes (ADPCM). ThunderGraft replaced the entire music streaming system of the games with its own, using the FMod Ex audio library to perform audio decoding of any of the multitude of compression formats the library supports. To my knowledge, it is, six years later, still the only modding tool to attempt such a feat. I finally got around to cleaning up and releasing ThunderGraft as open source a couple months ago on SourceForge, though given that the most recent game it supports, Diablo II, is about 10 years old, and the fact that broadband has made small mod sizes less critical than it was 10 years ago, it sees little use today (only about 30 downloads through SourceForge per month).

Allocation Benchmark [reverse-engineering, programming]
A project to examine the relative performance of several memory allocators - the Windows heap, Windows low-fragmentation heap, Hoard allocator, and the Blizzard Storm allocator (SMem, a custom buddy allocator). Allocation, free, and resize operations were logged from an actual game of Warcraft III via function hooking, then fed in order to each allocator while the duration of each operation is measured, and the results compared. Covered some in various posts.

AUS Decode [reverse-engineering, programming]
This project consisted of reverse-engineering the archive (AIF) and digital audio (AUS) file formats in the Mega Man Anniversary Collection to create a decoder that could extract the music directly from the game. Both AIF and AUS file formats were previously unexamined and undocumented, although the audio compression algorithm turned out to be the documented Sony ADPCM variant VAG. Reverse-engineering of both formats was accomplished with nothing more than a hex editor (no disassembler or debugger). I talked a tiny bit about this, but never said much about the technical side of it or released the code.

(BIN) Diablo II Binary Data Format [reverse-engineering]
Reverse-engineering of a number of major Diablo II binary data formats, e.g. armor.bin, itemtypes.bin monstats.bin, treasureclassex.bin, etc. These files are compiled binary versions of the SLYK spreadsheet files containing game global data. This was originally done with the intent of making a data editor tentatively called HellForge, but I never got around to that. I don't believe I ever released the specs of the BIN files; if I did, it would have been on Phrozen Keep.

DxWnd [reverse-engineering, programming]
DxWnd allows full-screen DirectDraw games that do not support windowed-mode DirectDraw to run in a window. I can't remember whether the initial idea was mine or Skywing's, but I did the initial research and reverse-engineering for the program and came up with the basic method. Skywing then wrote the code and debugged the cases that required modifications to my basic method (e.g. programs that combine Windows GDI and DirectDraw for graphics, such as the Diablo/Starcraft/Warcraft 2 Battle.net interface). I later added code to support window resizing via Direct3D, rather than the standard drawing method using GDI, though I can't remember if that code ever got released.

E Terra [programming]
A real-time strategy game based on ecology and evolution. Because this game focuses on nature and the organic, rather than humanity and society, the gameplay is substantially different than any existing RTS I've heard of, though it's bears some resemblance to Populous. E.g. there are no unit classes - unit "classes" are created by the player through gameplay/evolution; units are not built/trained - they are born automatically; etc. Current status: awaiting the motivation to work on it more.

Engram [design]
The name a Portmanteau contraction of "English program", a programming language based on a subset of natural English. This was something I started working on early in my compilers class, when I heard we were each going to be writing a compiler as a term project. Work on it came to an abrupt end when I learned that we didn't get to choose the language for our compilers. Other than what I communicated to a friend in IRC and IM, I never really wrote down a specification or anything.

LibQ [programming]
A small, minimalistic cross-platform library (designed for at least Windows and POSIX support) of highly platform-dependent features, such as multithreading (more specifically, synchronization, inter-thread/process communication, and atomic operations and structures), endian-conversion, and high-performance file I/O. Talked about extensively on this blog, though that was before I started using tags or anything to make the posts easy to find.

NWNScript Compiler [programming]
A compiler capable of compiling NWScript, the world scripting language used in NeverWinter Nights, NWN2, and Dragon Age, to native machine code for use in Skywing's NWN2 standalone server. This is the first attempt at such a thing that I'm familiar with; both the original games and Skywing's standalone server previously implement interpreters to execute the scripts.

In addition to the analyzer, which parses the NWScript bytecode files and generates intermediate representation code, two backend code generators were created to produce native code by proxy. Skywing's backend generates .NET bytecode, which uses the .NET just-in-time compiler to generate partially optimized native code; my backend generates Low-Level Virtual Machine code, which uses the LLVM optimizer and JIT compiler to produce optimized native code.

Q1 [design, programming]
A fairly simple and elegant RISC processor design and emulator. The Q1 began as an idea for a term project in computer architecture class to create a simple CPU and emulator; like Engram, the Q1 was conceived and work began prior to learning that we couldn't design the instruction set (the whole purpose of the Q1). However, I stuck with this one long enough to finish the basic instruction set architecture and create an emulator and sample programs (though not an assembler, which made it a huge pain to program). A number of the design decisions were discussed on the blog.

Ray Tracer [programming]
As with just about everybody who has ever taken a graphics course, I had to make a simple ray tracer. As this was only one assignment (and not a term project), the emphasis was kind of on the simple (there was no requirement for support of meshes, reflection/refraction, etc. However, I really ended up getting into this one, and added a substantial amount of additional features beyond those required in the assignment. Thanks to all my additions, it easily grabbed the top spot in the class.

While I intended to, I never got around to writing much about the ray tracer and the various features I chose to implement (and why), though the project page on the school wiki summarizes the features and shows them off with various screen shots.

recMPQ [reverse-engineering, programming]
recMPQ was a simple program to test some revere-engineering work on the MPQ format. The World of Warcraft Burning Crusade expansion added several new MPQ format features related to support for large archives (greater than 4 gigabytes). However, at the time no actual archives used these features. Consequently, I was forced to rely on pure disassembly, without being able to look at properly-formed archives or even watch the game load an archive using these features. recMPQ was a program to make a large MPQ archive based on my disassembly findings, which I could then replace a BC archive with to observe whether the game was able to successfully load the archive (indicating I had properly used the new features). This information was ultimately added to my MoPaQ format specification.

TextBreaker [programming]
A system to identify the language of a block of text using artificial neural networks. This was my term project (and accompanying term paper) in artificial intelligence class, which integrated AI, my interest in linguistics, and my interest in biology all into one. Unfortunately, identifying languages isn't as easy as it sounds, and the project ended up being more educational - in the sense of revealing difficulties and what does and doesn't work - than remarkably successful at actually identifying text. Nevertheless, it did manage to impress the (undergraduate) class, the teacher (specializing in AI), and my grandpa (a professional linguist), and my teacher and grandpa both suggested that I continue work on it and submit my results to AI and linguistics journals.

I never got around to cleaning up the source to release it (I did the whole term project in a week and a half, which made for very hackish code), but I did post the accompanying Orthographic Language Identification Using Artificial Neural Networks paper back when I turned it in.

StormDump [reverse-engineering, programming]
A memory tracker and browser used to examine the memory use of Blizzard games. Unlike the benchmarking project mentioned above, which merely logged calls to the allocation functions, this project consisted of reverse-engineering of the memory allocation system itself, and the associated data structures. It logged each memory allocation made, and tracked how many allocations were made of given sizes and types, both at a particular time and in total, and allowed you to dump all memory allocated at a particular time via hotkeys. All of this was done by directly traversing the memory structures for the allocation system. I don't believe I ever gave this or the source out to anyone.

Watcher [programming]
A simple program that logs all calls to API functions in various libraries that you specify using an configuration file. Version 1 of this hooked only functions specified in specified DLLs via INI files; some functions, such as the MPQ APIs, had hard-coded parameter-logging functions. Version 2 was capable of hooking all functions in all libraries and was intended to be scriptable to allow function-specific parameter logging for logged functions, though scriptability was never actually implemented.

ZIC2RAW [reverse-engineering, programming]
A project/program to extract the digital music files from the 3DO version of Mega Race. The format actually ended up being quite trivial to reverse-engineer, though the files turned out to not be entirely self-contained - part of the music data was embedded in the game executable itself, and not stored in the separate music files. Apart from a tool to work with 3DO discs, all of the reverse-engineering for this was done with a hex editor.

Do I Speak WHAT?

Reference material: HP 15C, z80

The Story of ThunderGraft

For those who aren't familiar with it, ThunderGraft was possibly the coolest of the three modding tools I released (the other two being MoPaQ 2000 and MPQDraft). Diablo, Diablo II, Starcraft, and Warcraft II: BNE all use PCM WAV audio (22khz 16-bit if I recall correctly) for their sound effects and music. Diablo used raw PCM WAV audio, while Starcraft introduced (and the other two used) a special "WAV compression", which compressed the audio in lossy ADPCM form, resulting in a compression ratio between 3:1 and 4:1 (though at the cost of audio quality); WAV compression, however, was implemented transparently in the MPQ API - the games saw what they read and wrote to the MPQs as simply PCM, and that's all the audio streaming API was capable of playing (in other words, the audio streaming functions were identical in all four games).

ThunderGraft was a utility that added the ability for all four of these games to play MP3s and Ogg Vorbis, in addition to standard PCM WAVs; even better, it did this in a version-independent way* (the very same ThunderGraft binary worked for all versions of all of those games). Naturally this was huge, especially in the days of dial-up (which was when the modding community first became big). You could use modern audio compression formats that yielded significantly smaller file sizes and higher audio quality compared to WAV compression. Yet ThunderGraft is all but dead now. Why is that?

MPQDraft and ThunderGraft have a few things in common. They're both very simple, clean, version/program independent, and highly effective. The reason is also the same: they both rely on very clean exploits of design to do their thing, without getting into messy exploits of implementation that depend on the precise binary patched. MPQDraft exploited the priority system in the MPQ API; ThunderGraft exploited the fact that the audio streaming API was encapsulated in functions supplied in Storm.dll.

The fact that the functions were entirely contained in Storm meant that I could cleanly capture calls to them and redirect them. For cleanliness, I opted to simply replace the streaming API in its entirety. Anything less would have been version-dependent, as it would have required all sorts of messy code modifications inside Storm's internal functions.

This meant that I needed my own decoding and streaming code to replace Storm's. At the time I just coincidentally happened to have such a thing handy. Specifically, a friend of mine by the moniker Dark_Brood was writing a game engine called Aegis, and happened to have audio decoding/streaming code handy for me to plug into ThunderGraft. He sent me a static library of the code, and in it went. Easy.

Where things took a turn for the worst was when he wrote the next iteration of his game engine. This involved rewriting a whole bunch of stuff, and integrated the various systems in the engine much more tightly (e.g. added garbage collection and other global things). This meant that it was no longer possible to simply extract the audio portion of the engine.

While in theory I could have just continued to use the old version, there was a big problem: I never had the code for the original version, nor did he save a copy after rewriting the code. This is a big problem because static libraries are compiler- and version-dependent. Now the only way I could even compile ThunderGraft was on the very same version the original was compiled on: Visual C++ 6, which is some 11 years old, now, and I haven't even had it installed for many years.

Thus, the only way to resurrect ThunderGraft would be to replace the decoding and streaming system entirely, and thus far I simply haven't managed to muster the effort. After open-sourcing MPQDraft I wanted to do the same with ThunderGraft, but was unable to readily do so for the same reason.

*There is one thing that's version-dependent in ThunderGraft, as there's simply no theoretical way to do it in a version-independent way: importing of non-WAV audio files into maps with StarEdit (the Starcraft map editor). Special support for this was required for several reasons: 1. StarEdit verifies that things imported are WAVs and refuses anything else, 2. it needed to know how long the audio file was in order for triggers to work right. The audio decoding and streaming in ThunderGraft, in contrast, was truly game- and version-independent.

Moving On Up

I'd heard all of this from him directly, but I just ran across this post on the ZDNet Security blog - Microsoft adds 'Skywing' to Windows defense team.

Incidentally, Miller is the arch-nemesis I mentioned earlier.

& Patents... or Lack Thereof

A ways back (might have even been a couple years), I came up with an idea for something called Anonymous Private Mail, or a-p mail, a system of e-mail which provides for much greater privacy. Rather than using an e-mail address, a-p mail identifies individuals by their public/private key pair used to encrypt the e-mails (the private part). What made the a-p mail system so novel was that it was able to route a message from sender to receiver without ever knowing the keys of the sender or recipient (the anonymous part). Because of this, the e-mail server (or anyone monitoring it) could not even tell if two e-mails were sent by the same person or received by the same person (in contrast to normal e-mail systems, where the server always knows at least the e-mail address of the receiver).

I was initially concerned about disclosing how it works, especially with regard to patenting it. This system originated in one of my stories (the universe of Starfall and Eve of Tomorrow, which I briefly mentioned previously) as a method allowing criminals (especially terrorists) to communicate. I was concerned that if I patented it, it would be used in the same was it was used in the story. For this reason I posted the basic description (essentially what I wrote above) on this blog and some forums, asking for comments about whether I should patent it or keep it secret forever.

Eventually, a consensus opinion was reached that if I'd managed to come up with this idea, others would also be able to, so the only thing that keeping it secret would do is prevent me from potentially receiving licensing fees for the patent on it. So, after a great deal of procrastination (me being me), I finally wrote up the patent application and submitted it to the US Patent and Trademark Office last Thursday.

While not entirely unforeseeable, I was still very surprised to find two men in suits at my front door on Friday. To make a long discussion short, they explained that they were from the US Department of Homeland Security; they had seen my patent application, and, apparently, I wasn't the only one concerned about the possible application of the method to criminal organizations (particularly terrorism). They informed me that they'd deleted my patent application, and presented me with a federal gag order barring me from disclosing the details of the method to anyone else (including making further attempts to patent it).

So, I guess I won't be patenting it afterall. Funny how all decisions become easy when you're reduced to only a single option... At least this won't impact my stories - as they weren't targeted specifically at people with great knowledge of computers, most people wouldn't have understood the thing even if I had explained how it worked in the stories.

So Much for That

A couple weeks ago I happened to be at a certain computer store. I happened to notice that they had a sale on a GeForce 9400 GT 512 meg video card for $40 (normally $70). While I already have a sufficiently powerful video card, I'd been thinking for a while about picking up a cheap GeForce, in case I ever felt inclined to play with CUDA (my video card is an ATI). So, I grabbed one.

After a sufficient amount of procrastination (specifically, two weeks, bringing it to the last day to return it), I figured I should see about opening it and installing it, to make sure it works. But first I decided to do a bit of research: namely, whether you can have both an ATI and nVidia card in the computer at a time. Obviously this should work, but with the ATI and nVidia war, driver idiocy, etc., you never know.

Well, it turns out that you can't - at least, not in Vista (I'm using 2008, which is based on Vista). Specifically, Vista only allows one WDDM display driver to be loaded at a time; this means that if you have multiple video cards, they all need to use the same video driver. While Vista still supports older XP XPDM display drivers (and allows multiple XPDM drivers to be loaded at once), it'll cost you - WDDM drivers are required for things such as Aero and DirectX 10; worse, you can't have one driver that's XPDM and one that's WDDM. Windows 7 is rumored to support multiple WDDM display drivers at once.

And that's why I tried it while it was still returnable, and didn't open it before doing some basic research.

Graphics Programming Term Project

In case anybody is interested, here is the paper for my term project in graphics class. I was working on an implementation of it, but thanks to various brick wall problems, that didn't end up getting completed in time (which is why the results section does not discuss the results of the actual implementation), although it did result in me going 38 hours without sleep. It's an interesting method, and at least a couple small parts of it are novel (I'm not aware of them being proposed before), but probably isn't practically useful for the reasons explained in the paper.

Multi-Fragment Deferred Shading Using Index Rendering

Intriguing

Well, just as school is almost over (finals are this week) and I don't have a job lined up yet, substantial amounts of amusement will be welcome in the near future (especially given how bleak the anime outlook is, this season...). Well, as it turns out, I'm in luck! While in the process of banging my head against a wall till I pass out while working on a term project, something amusing happened. I don't have time to explain the details now (despite the fact that this is much more interesting than my school project), but here's a short headline of what's up and coming: Q vs. Scam Debt Collection Agency.

Look forward to it!

& Other Things

I managed to forget something important in my last post, despite the fact that it's closely related to one of the things I did mention; that is, Echoes of War is out. At least, it got shipped to me last week; few others seem to have gotten it already, and as far as I know it hasn't even hit peer-to-peer networks yet.

Echoes of War is an orchestral remix/arrangement of music from all three of Blizzard's universes - Warcraft (III, World of Warcraft), Starcraft (I & II), and Diablo (I-III) - by Eminence. It's about one and a half hours of music, with several tracks from each game and each track being a medley of game pieces.

While some of them fairly closely follow the original sound, some of them are arranged in very novel and surprising ways. Two of the best examples of this are the big band jazz arrangement of the Starcraft I Terran music, and the crazy symphonic/operatic/Middle Eastern/The Rock arrangement of the Starcraft I Zerg music. (other samples can be played from the Echoes of War media section)

How much I like the tracks varies by the track. Several of them I really like, although I'm noticably less fond of the Diablo tracks than the Warcraft and Starcraft ones. But in any case, the album is awesome. If you like the music of Warcraft, Starcraft, and/or Diablo, buy it. I just wish the stupid thing was sold by stores that didn't charge you $14 for shipping...