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.

What the

This one was a bit too long to post on Twitter. A quote from a link I tweeted:

In addition, the appeals court took aim at several filtering schemes. Blocking all files of a certain type (such as RAR files) was deemed inappropriate, since a file type has no bearing on the legality of an upload. Scanning by IP address was also tossed, because numerous people can use a single IP address. File name filtering tells you nothing about the contents of a file, so that was tossed. Even content scanning was problematic, as the court noted that this would just lead to encrypted files. Besides, even if you could know that a file was copyrighted, it could still be a legal "private backup" not distributed to anyone else.

Courts making rulings based on actual technical knowledge? What's this world coming to? I note that they even listened to me (okay, probably just other people with similar technical knowledge) and realized that content scanning would be ineffective as it would just lead to ubiquitous encryption with no actual reduction in infringement.

& Domain-Specific Computing

So, I went to the public lecture at UCI today (the one I posted an event for on my Facebook page). These public lectures are by various guest speakers on a wide range of topics; each one is usually something of an overview of a particular field, often ones which the average computer science student has minimal or no exposure to in their classes. As with last time, there were free brownies and coffee/tea.

Note that this post is all from memory. I didn't take notes or anything, so there are likely to be omissions and vagueness compared to the actual lecture.

The topic this time was domain-specific computing. Essentially this refers to the use of some manner of special-purpose hardware to offload work from a general-purpose CPU, either eliminating the CPU entirely or allowing the use of a smaller, cheaper, and more efficient CPU. The ultimate purpose of this is to reduce overall cost and power consumption while increasing overall performance for a given task.

If this doesn't sound revolutionary, it's because it's not. Modular electronics have been around for as long as electronics in total. If you want a real-world example of something built this way, you can look at just about anything at all. Computers consist of many components (e.g. motherboard, video card), each composed of many further components (GPU, southbridge, northbridge, etc.), usually microchips.

The problem then is that it's hard to manufacture these chips. It's expensive, requires skill in engineering, and is largely done manually. Skilled electrical engineers must manually design a circuit, then a huge fabrication plant uses big and very expensive machines to manufacture the circuit, which is then available for use in various devices. Because of the expense and manufacturing requirements, most companies are not able to produce custom chips in this way.

As a result, very common specialized circuits are produced and sold off-the-shelf in large quantities, while less general circuits instead use code running on a general-purpose CPU. After chip design and fabrication, another electric engineer must then analyze everything a particular device must do, determine where it would be beneficial to use specialized off-the-shelf components (which may either be used directly or require some manner of mapping to make the data fit the exact component), then determine which CPU to use for everything else, and have the programmers write the code for it.

Done correctly, the resulting device is faster, cheaper to manufacture, and more efficient than simply using a fast CPU to do everything. One of the papers he cited examined different algorithms implemented on a general-purpose CPU, a general-purpose GPU, and a custom FPGA (chips that can be programmed without massive fabrication plants, but are less efficient than standard fabricated chips). For one algorithm (seemingly a highly parallel one), the GPU performed 93x as well as the CPU, and the FPGA 11x. While the GPU was 8x as fast as the FPGA in absolute terms (though presumably you could increase the size of the FPGA 8 times, to match the GPU's total performance), when you compare performance:power consumption, the GPU was 60x that of the CPU, and the FPGA was about 220x: about 3.5x the performance of the GPU (and I'd wager the FPGA cost less than either of them). In other algorithms, the difference was tens of thousands of times.

But it's still a whole lot of work. Consequently, this tends to be done for mass-produced electronic devices, while more specialized things are simply executed on a common computer, as it's cheaper to code a program than engineer an electrical device.

This guy (the one who gave the lecture) is working to develop analysis and automation tools to reduce the cost and difficulty of custom hardware development, to significantly increase the range of things that are viable to produce this way. Ideally, you'd be able to write a specification or algorithm (e.g. a C++ program that describes an entire device's function), then automation would analyze the system, performing these steps (essentially the same ones I summarized above):

1. Break it down into major functional units
2. Determine which units can use off-the-shelf components and what the optimal component is
3. Locate algorithms that would substantially benefit from the production of new components and then design those components for manufacturing, either using FPGAs, circuit boards, or as actual fabricated chips
   
4. Choose the optimal CPU and algorithm for the tasks remaining (that aren't worth implementing in hardware) and write the code. Remember that different tasks run better or worse on different CPU architectures, so this step must find the best CPU for the given algorithm or rewrite the algorithm in a way that runs better on a more preferable (e.g. cheaper) CPU. For example, CPUs that lack branch prediction are cheaper and more energy-efficient, but perform poorly on algorithms that use a great deal of branching; however, depending on the task to be performed, an alternate algorithm might be able to perform the task with less branching.
   
5. Design an optimal bus architecture for all the different electronic to communicate

Of course, it's very likely that this ideal is fundamentally impossible - at least until artificial intelligence is able to perform as well as a skilled electrical engineer. However, he hopes to create tools that drastically reduce the amount of human time and cost needed for this process, and the talk was about recent research toward that goal. A few of the automation problems under research by different groups:

• Identification of identical algorithm matches to existing circuits as well as partial matches that can work with some amount of data conversion
• Profiling of different matching circuits to determine which performs optimally on a given problem
• Determination of which algorithms would perform substantially better if implemented in custom hardware
• Conversion of procedures (e.g. C++ programs) to electronic schematics for manufacturing
• Profiling of different CPU architectures (e.g. x86 and ARM), models (e.g. i5 and i7), and variants (e.g. cache size, with or without optional subunits, etc.), to determine which is optimal for a given device, based on performance and cost
• Profiling of different bus architectures (e.g. mesh and crossbar) and configurations (e.g. number and size of channels) to determine what is optimal for a device
• Modularization for energy efficiency, to allow entire circuits to be shut off when they aren't in use (but others are)
  

I don't remember too much more detail than what I've already said. One last point is that this guy seemed to be a big fan of the multiband radio-frequency interconnect (RF-I) bus for the purpose of inter-component communication. This works essentially the same as the radio or broadcast TV, where bandwidth is split into separate channels, each with a different range of modulation frequencies. As this allows bandwidth to be arbitrarily allocated between many bus channels (and may even be configured in real time), this is very amenable to communication and power optimization.

Actually, it looks like the slides from the lecture are available online for you to look at, beyond what I've already written about it.

& Content Filtering

Following a brief scuffle with Patrick Ross in the comments of the Copyright Alliance blog, I thought the topic I briefly discussed deserved elaboration: content filtering. That is, the analysis and identification of illicit content packets as they pass through a router, based on hashing (not so effective) or fingerprinting (more effective), usually followed by dropping the packet.

I'll discuss the full range of content filtering, though one thing at a time.

First of all, the specific type I referred to previously: filtering at the internet service provider level. Imagine an ISP that is being legally pressured to do something about file-sharing by copyright industry representatives, a situation hundreds of ISPs around the world find themselves in at this very moment.

Now, Mr. Sales Rep, from another company that makes deep packet inspection hardware, offers to sell a product to Mr. Business Suit from the ISP, that will solve the file-sharing problem, as many sales reps are currently doing. This company's tests show that the product is 95% effective at identifying and blocking traffic containing illicit copyrighted material, and has a low rate of false-positives. Naturally, Mr. Business Suit at the ISP looks at this product, and sees an amazing solution to all of their problems. Mr. Engineer at the same ISP looks at the product and sees a million-dollar paperweight, and tells Mr. Sales Rep to get out of his office. Nevertheless, convinced by Mr. Sales Rep, Mr. Business Suit purchases the product, and has Mr. Engineer install it.

Now the product has been installed, and everybody watches eagerly, as Mr. Engineer turns the new product on. Immediately the product begins logging transfers of copyrighted content by the thousands, and successfully blocks them. Yet Mr. Engineer looks at his network statistics and sees that not only is the product having 0 effect on the amount of internet traffic, there is still just as much illicit content being successfully uploaded by users of the ISP.

What could possibly have gone wrong? And why were the appraisals of the product so drastically different between Mr. Business Suit and Mr. Engineer, to begin with? Is the product defective? Did Mr. Sales Rep lie?

Well, not exactly.

What happened is that the ISP's users adapted effortlessly to the new piece of filtering hardware. While it's certainly viable, if implemented competently, to detect and block things like copyrighted content, this is only possible if you have access to the data being transmitted. The universal Achilles heel of such identification algorithms is encryption.

Modern file-sharing software supports end-to-end encryption - the same kind used to secure credit card transactions online: the uploader encrypts the data, the downloader decrypts it, and nothing in the middle can access the data in between the two, because nothing else has the encryption key. This "nothing" includes that million-dollar product our ISP just bought.

Now, this encryption is not a technology that needs to be developed, nor does it need to be downloaded and installed by the user. It's already there. If a user is able to share files through a P2P application, the encryption code is already in that P2P application; it needs only to be enabled by a user clicking a check box. And, of course, you can be certain that it will be turned on by default in future versions of said software if content filtering by ISPs becomes common.

In other words, each of those "blocked" uploads the product registers is merely the first of two attempts. A blocked upload is merely an upload that will succeed seconds later, after the user clicks the box to enable encryption (though if content filtering is widely deployed, users won't even need to do that). Thus, to make a long story short, while you have successfully prevented file-sharers from uploading unencrypted illicit content, you haven't actually prevented a single copyright infringement.

This is a theoretical problem, not an implementation issue. As such, there is no basis to hope that this is a limitation that will ever be overcome in the future.

But look on the bright side: Mr. Sales Rep got a nice commission off that million bucks the ISP paid his company, and as he technically never lied, the ISP has no legal recourse to argue fraudulent advertising.

However, the fact that ISP-level filtering is a technological dead-end should not be taken to mean that all filtering technology is useless. As stated, filtering technology can be effective, given that it has access to the data. Of course, the hackers of the world will continually work to find new ways to evade such filtering algorithms, but it should still be possible to successfully filter enough to justify the cost of the filtering hardware/software.

One example where this works to a satisfactory degree, both in theory and in practice, is YouTube. Because YouTube actually processes and decodes the content uploaded to it, it's impossible for it to not have access to the data - it couldn't function otherwise. As such, it always has access to the full, unencrypted content uploaded, at which point filtering of that content is possible, and in fact is already being performed.

Dumb file storage sites - sites like RapidShare - which store data without any regard to what type of data it is, fall somewhere in the middle. As they do not require access to the data itself, encryption is entirely possible, and would indeed be capable of evading any filtering of uploaded content done on the part of the site. However, use of this type of encryption would be much more of an inconvenience than is the case with encryption in P2P programs; in this case, encryption must be done manually, by the user, through a completely separate program (almost anything that can make ZIP files can encrypt them, for instance), and the encryption key must be distributed through other channels, such as forums that link to the encrypted file. As such, while filtering at the level of such sites will certainly not prevent such encrypted transmission of content (nor probably even a majority of total transmission), it's possible that filtering systems might reduce sharing of illicit content by some sufficiently valuable fraction by means of sheer annoyance.

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).

& Solid State Stuff

Pretty soon I'm going to be looking to upgrade some things on my computer, starting with the hard drive. In addition to getting a large disk to begin using for archived anime (as opposed to the large stack of DVDs I've burned), I was going to get a solid-state disk to put my Windows 7 that I won in a raffle a couple weeks ago on.

For anyone not familiar with them, SSDs have the benefit that they have 0 seek time (as opposed to about 9 ms for HDs), combined with linear read speeds several times that of HDs. For very large and contiguous files, which involve only linear access, an SSD could be 3 or 4x as fast as an HD. But for accessing large numbers of small, non-contiguous files, which involve many seeks, the difference is much, much larger. Thus SSDs can be anywhere from substantially faster to massively faster than HDs, depending on the type of access.

But what exactly do I do with the SSD when I get it? Prior to Wednesday, the answer was obvious: use it as my boot drive. That is, put Windows and frequently used programs on it, and use a separate HD to put large and infrequently used stuff on.

Today, however, there's another option, thanks to the announcement of this evil little thing: a disk controller which combines an HD and an SSD, using the SSD as a massive cache for the much larger HD. That is, instead of having the SSD serve as a dedicated boot drive, it's used to cache frequently used files from all over the HD (when talking about an 80 gig cache, "frequently" probably amounts to once every week or two).

One obvious advantage is that the superior performance of the SSD is applied not just to system files (e.g. Windows), but also to anything on the disk that gets used frequently. Similarly, you don't need to let part of the SSD go to waste if you don't have enough files to fill it up (I'm told using an SSD as your boot drive takes 30-40 gigs of SSD, while higher end SSDs go up to 256 gigs). Another big benefit is that you don't have to manually split files that are normally on the boot drive (e.g. Program Files and the Users documents folder) between the SSD and HD depending on whether you want them fast or slow; for example, I wouldn't want to put downloaded anime on my (dedicated) SSD, nor would I want my SSD bloated with the various bulky compiler intermediates.

Now, the big question is how exactly this is going to work. According to the manufacturer, it requires a driver for Windows in order to work. This suggests that caching may all be done in software, rather than hardware. This brings up the obvious question: in what cases the cache will be used? If the cache is only used within the current Windows boot (essentially serving as a gigantic system cache), this won't be very useful, at least for me (perhaps for a database server, with multiple terabytes of database, a 100+ gig cache would be substantially beneficial). I already have 8 gigs of RAM, about 4 of which (at a minimum) is available to be used by the system cache, which is a pretty decent cache for one session (and RAM is much faster than an SSD, anyway).

From the write-up, however, it sounds like the cache at least persists between Windows boots, which would mean it wouldn't quite be that bad. However, if the caching is all software-based via a Windows driver, this obviously means that it won't be of any benefit prior to loading that driver - that is, during boot up/shut down and going into/out of hibernate, which are things I was hoping to gain out of getting an SSD.

I guess we'll find out when the thing ships, in 3 weeks or so.

Random Fact of the Day

You can't install SilverLight on a Pentium 2. It has to be something that supports SSE.

Random Fact of the Day

Exact Audio Copy, like some similar programs (I know older versions of Nero are like this) can be made to work on a Windows limited user account, but it requires a couple of things.

First, you have to make the DAT files in the EAC folder writable by all users (or at least those you want to be able to use it).

Second, you have to enable low-level access to the disk drive for limited users. The easiest and least dangerous (in terms of downloading software from who knows where) method of doing this is to simply use Nero BurnRights (search down on the page), and it will allow you to set this option; note that you don't need to actually have Nero to use this program. Of course you'll have to install it and run it as admin, but once you set the option you'll be able to use EAC (and other similar programs) from any user.

Finally, make sure EAC is set to use the Native Win32 Interface (EAC Options->Interface); this should be the default, but who knows.

& Very Old Things - Part 3

So. Thus far everything I did involved nothing more than the memory editor and cheat search. In other words, something just about anybody could do. To really say that I reverse-engineered Blaster Master, I needed something a lot bigger, and I knew just what to do: I was gonna find the cause of a 21-year-old bug. There's a well known glitch in Blaster Master that on some bosses, if you or the boss is being hit when you pause the game, you (or the boss) will continue to take damage while the game is paused. This only works on some bosses, however, leaving a big question mark as to whether it's a bug or a feature (it was especially strange that it affected both player and boss); I wanted to find out.



Unsurprisingly, it's quite a bit of work to reverse-engineer something you have absolutely no info on (e.g. in computer programs you at least know OS API calls the program makes, and can use that as a starting point), especially when you're learning both the hardware and the assembly language as you go. Ultimately, it took me an embarrassingly long time to get the job done (certainly more than it was worth), and I ended up disassembling a lot more of the game than was necessary (as is often the case when you don't have any idea what you are looking for). I'll just talk about some of the more important lines of investigation, findings, and complications.

As I didn't know anything about the game, naturally the first thing was to hit "step into" and see where I ended up. I always ended up in the same place: a busy loop that checks a single value. Given the nature of this and some idea about the hardware, I reasoned that this was a loop to wait for the next vertical sync, to start on the next frame; this was confirmed by observing that address being written to from the non-maskable interrupt (vsync) handler.

From there I stepped out of the function and took a look around, writing down the various functions called after vsync. I then went about refining the list and detailing more levels of the call tree, ultimately (after all of my disassembly) resulting in the call tree and other related notes below (note the comments have a focus on things relevant to finding this pause glitch). One thing of particular importance is that there's an object-oriented handler for each object type, and the appropriate handler is called for each non-empty object table entry.

$E936 waits for vertical blank to occur
$C971: for each object calls $C8DF, decreases hit timer if nonzero, calls $C9A4, and calls $C928
-$C8DF copies object data from $400+$56 to $46 ($C925 writes life)
-$C9A4 sets hit timer back to full and decreases life in the object buffer when hit with hit timer at 0 after decrement
--$EA3A
--$EB51 saves the object-specific handler to $7A (LE)
--jumps to the object-specific handler at $C9D3
-$C928 copies object data from $46 to $400+$56
$CA4B->$EA3A->$E61B->$E63C/$EB98 unmaps $8DF6 page [the page the object handlers are], which gets mapped by the NMI handler

$EB7E NMI handler (does not branch)
$EB97 IRQ/BRK handler (stub)
$F7: controller 1 state (bits in reverse order)
$F8: controller 2 state (bits in reverse order)

For a while I did some looking around with breakpoints on the location in the object buffer where the life is stored, looking for things that modify it. Some of the information gathered this way:

Copy of object struct for current object: 46
Buffer used to hold 16-bit pointers [LE] from various tables: 7A

$53 [life of the current object] written to directly by $8DF6 in $C9A4 when damage is taken
$8C6B-8C9F, $8DDF-8DFE (inside $8D76) only executed when hit timer is 0
During pause taking hit, $C1E6->$D7A0 returns A0/N+ to $8DD5 on boss 2, but 7F/N- to boss 5

$D7A0 seems to determine whether you get hit during pause. $7E indicates whether you're being hit or not: high bit for hit, lower bits for damage taken.
$7E is written to by $D71A in ($C141->$D711) when hit by boss, $D7B2 to clear hit per frame. $D71A is not reached when paused with boss 5 because $D6CD does not return
$D6CD returns if the current object is hitting the player, throws an "exception" returning to caller of caller if not hitting (returns from $D710)

Eventually I decided to take a more systematic look at the object handler for the catacombs (overhead view) player object:

$8C38->8D98->$8DBF catacombs player object handler paused
-$C15F
-$C0FF->$EF2B sets $3E and $3F to the X and Y coordinates (in pixels on screen) of the player for $D7A0
-$C1E6->$D7A0 returns A0/N+ to $8DD5 on boss 2, but 7F/N- to boss 5, when paused and being hit. A indicates the damage player should take. highest bit of A and the negative flag indicates whether player is hit or not.
-on N+, $C216 then handles hit (including decrease life)
-$93BD
-$EA3A
-$F029
-$E63C

From this we can see that $C1E6 is the switch we're looking for, determining whether the player takes damage; though a look through the function shows a clear lack of anything resembling hit detection - it simply reads from a struct in memory at $7C, generated who knows where. So, if that isn't determined in the player object handler, maybe it was handled in the objects you can be hit by. For that reason, and to satisfy my curiosity a bit about what makes bosses tick, I decided to take a look at a boss handler function; and as I hate the crab boss so much, naturally I went with that, first.



It was about this time that I discovered that NOPing function calls was a very effective way to quickly get an idea what a function is doing. This method works poorly on computers, because of the greater number of registers and drastically greater stack usage, making such NOPs result in crashes more often than not. On the NES (or at least in Blaster Master), however, the method works very well, with crashes very uncommon.

Crab (level 5) boss unpaused object handler ($A6D0):
-$A07B: (no discernible effect)
-$A6DE: handles movement of crab and state transitioning (but not animation)
-$A7A2: spawns bubbles when necessary
--$C1F5: spawns a bubble
-$C0FF: updates crab screen position based on crab 65 position (NOPout fixes crab position where it shouldn't be, despite crab 65 object movement). affects everything onward.
-$C153->$EB51
-for each body segment (right pincer, left pincer, back):
--$C141->$D711: detection of whether player has been hit. detection of player being hit by green sprite is elsewhere.
---$D6CD: checks for collision
--$C216->$DECC (only if hit)
-$C12C: (no discernible effect)
-$C189: draws (animates?) the green sprite
-$C144->$D697: sets player damage if player hits green sprite. also handles things damaging the boss.
--$D6CD: returns on collision (either player hit by something or boss hit by something). eats the stack frame if no collision (returns to caller of caller)
-$9EB3: animates the background layer

Okay, so $D6CD is another function that looks like a good candidate. So, let's take a look and see if it's what we're looking for or another tangentially related function (don't blame me for the formatting, Blogger doesn't like indentations).

$44 = A
$00 = $3E - ($40 / 2)
$01 = $3F - ($41 / 2)
X = 0xF
do
{
A = $7E[X]
if (A > 0)
{
$45 = A
A = $7C[X] - $00
if (A <= $40)
{
A = $7D[X] - $01
if (A <= $41)
return
}
}
X -= 3
} while (X >= 0)

throw

Now that looks like a collision detection function, more or less. We can see the X coordinate, Y coordinate, width, and height of whatever it is we're comparing against at $3E-$41, respectively (this is a case of a memory region being used like a stack frame). We can also see an array of 5 structs containing the X coordinate, Y coordinate, and a thingy, respectively, starting at $7C. Clearly only the size of the "current" object is considered, and the array of thingies are just points.

Well, let's think about it for a minute. We know that this function is called 4 times for the crab boss, for the 4 different parts of the body (and that one of those is not like the others). What might collide with the boss that would be of interest? Well, the player and the player's projectiles. A bit of playing around proved this to be true: the first entry in the array is the player, the rest are the player's projectiles (limited to 4, as you can see). That third byte in the struct array indicates the amount of damage the projectile does (or 7F for the player).

So, now we have everything we need to figure out how this works. The boss object checks for collisions with the player and the player's projectiles. If it hits the former, it marks the player for damage, which is then applied by the player object handler (presumably next frame, since the player handler always gets executed before enemy handlers); if it's the latter, the boss takes damage, though only if the part hit is the green sprite, which is the hit box.

Now that we know how the collision detection and damage system works, and why bosses that are susceptible to being hit while paused also themselves can hit you while paused (the collision detection for both is one in the same); that just leaves the question of why it only operates on some bosses. Well, it was about here that I discovered that that wasn't actually true. While only some bosses can be hit (and hit you) while paused, this is not the case for projectiles. Specifically, the projectiles fired by boss 3 and boss 8-1 can hit you while paused, even though the boss cannot be hit while paused.

Well, it turns out there are two sets of object-specific handlers, one for when the game is running, one for when it's paused. Now, bullets and other things are generally not prone to the problem of dealing damage while paused, as they disappear as soon as they hit something (e.g. the bubbles spewed by the crab boss). The things that can hit you while paused appear to be exactly those objects that have pause handlers and that don't disappear after hitting you; this is the case with all susceptible bosses, plus the projectiles of bosses 3 and 8-1.
Boss object handlers:
1 (63): base $A58A, paused stub
2 (5F): $9B64
3 (61): $A196, paused stub
4 (5D): $970C
5 (65): $A6CD, paused stub
6 (5F): $9B64
7 (5D): $970C
8-1 (67): $AA34, paused stub
8-2 (69): $AC84, paused stub

While I didn't go searching for every single object handler to compare the paused and non-paused versions, I did compile a list of the ones for the bosses. Note that there is only actually a single table of handlers in memory; the address in the table points to the paused handler, while the unpaused handler is always 3 bytes afterward (3 bytes is the size of a JMP instruction). For the bosses not prone to this glitch, you can see that I've indicated the pause handler is a stub that returns immediately. For the rest, the pause handler jumps midway into the unpaused handler (after things like movement).



To illustrate this, take a look at the handler for boss 2 ($9B67):
-$A07B: (no discernible effect)
-$C01E: handles movement of boss
-if time to spawn next projectile:
--$C1F5->$D851: fork projectile from boss, giving it a new proto-object type
--$C216
-paused handler jumps directly to here
-$C0FF
-$9D77: draw and do hit detection for arms
-$C090->$D770: do hit detection for back (not hit box)
--$D711: hit detection
-$C093: do hit detection for hit box
-$9EB3: moves and animates the background

So, that's how it is. Now we know why it happens and why it only affects some things. That just leaves one more question: is it a bug or a feature? Unfortunately, the evidence is much too ambiguous to answer that clearly. While it's within the bounds of imagination that damaging the boss during pause could have been intentionally put in as a cheat of sorts, it's very hard to imagine that the same thing against the player would be intended.

Yet it's also hard to imagine that it could be a bug; while the player being hit during pause could be eliminated by a single change to the player handler (a single mistake, in other words), doing the same for bosses would require that every boss's handler be changed. Furthermore, there's the fact that only 2 of the 5 unique boss object handlers (2 of them are used for 2 bosses each, bringing the total to 9 bosses) have pause handlers, in contrast to the player and most projectiles, and without pause handlers the bosses don't even get drawn completely (and what point is there in having a pause that lets you see the boss battle if you can't see the boss?). It seems as though a lot of stuff was left out or in arbitrarily; I have to wonder if there is a deadline lurking in here, somewhere.



Various resources used during reverse-engineering:
Nintendo Entertainment System Documentation
6502 Instruction Summary
How NES Graphics Work
Comprehensive NES Mapper Document
For more info, see this big list of documents

& Very Old Things - Part 2

As for the hacking itself, this started out with simple stuff. Search memory, find special values (life, lives, gun power, boss items, etc.), and overwrite them. This was quite easy with an emulator that has a cheat search feature; you simply have it save the memory contents at the initial state, the repeatedly perform searches based on specified criteria until you've narrowed it down to 1 or a small number of possibilities. For example, finding player health was a trivial matter of searching for something that decreases each time you take damage and stays the same in between damage.



With the exception of the boss items, all of the others in this list were similarly easy to find. Boss items, however, were a bit more complicated. Because you only get the items after beating a boss, naturally this is a situation where there are likely to be a lot of changes all over RAM, as it's a major transition in the gameplay; this means that you can't narrow it down as easily. I had to try several locations, starting with the ones whose values made them the most probable to be correct (specifically ones that had a bit flipped on when the item was picked up).

However, there was one other complication figuring that one out: boss items are represented by two separate bit masks that are partially redundant. I first discovered the mask at 3FC, because that's the one that changes the bullet your tank fires after you get the first boss item; as it was a visual change, it was very easy to see that it was working. Once I found that, I checked to see if it was a bit flag, and confirmed it was, finding the flags for the second and third boss items by experimentation.

That's where things got weird. While this mask contained flags for boss items, the flags for the other boss items didn't seem to actually do anything. As well, while having the hover bit flag set caused hover power to be displayed (it's hidden prior to getting the third boss item), you couldn't actual hover. The bits here also did not make the upgrades show up on the pause screen. So, I went on, with my infinite life and gun power, and killed a few more bosses (somehow I still remember most of the maps of this game).

I found that there was a second bit mask with a completely different set of flags, one for each of the 7 items in the game. For the first 2 items, these flags did nothing more than make the item show up in the pause screen. For the third item (hover) this flag allowed you to hover, but did not show the hover power bar or allow you to accumulate hover power (so you still couldn't actually fly with this flag alone). I still can't imagine why it was done this way, but at least I figured out all the flags.

One thing that I couldn't figure out with cheat searches, however, was boss life. That is, I found it - repeatedly: it was in a different place every time (including even for the same boss). I correctly reasoned that this implied that the boss's life was not a special value, but that bosses were simply common entries in the list of objects in the game. As it turns out, so is the player; you just don't notice that because the player is always at index 0 in the object array and thus always at address 0x400, while the boss was stuck in whatever slot was available at the time. This led directly to the discovery of the object array itself. From there, I started looking at the struct that represented each object, beginning with offset 0xD: life.

As I've already pointed out that you tend to have to get clever when coding on a system with so little RAM, it shouldn't be surprising that maps are stored in a similarly clever way. As far as I can tell, there is only a single map for each area in the game (8 areas), which is 128x256 or less. However, the map is diced up and jam-packed in there such that they need to do some camera tricks when transitioning between areas (teleporting through some doors) to make sure you never see other sections that are contiguous in memory.

While I was working on it, I figured I should try to answer some long-standing questions about Blaster Master. To begin with, why does the power of your gun (what it actually shoots) not always match the gun power that's displayed? For example, if you have full gun (8 bars) and get hit, you take 1 bar of damage, but the effect of your gun falls beneath what 7 bars should give you. Many years ago I hypothesized that there were two variables for gun power; one was the one displayed, and one that was the actual effect: getting hit did a bit more damage to effect than the display.

It turned out to be simpler than that. It's a consequence of the fact that while most hits (I can't think of any counterexamples) do an integral number of bars of damage, life, gun, and hover are stored from 0-FF, in bytes. See where this is going? One bar = 20, but 8 bars = FF, not 100. In other words, the number of bars displayed is (x + 1) / 20. When you get full gun and then take a hit, your gun drops to DF; while this still displays as 7 bars, it doesn't give you the maximum gun effect (which requires E0). It's not clear whether this is a bug or a feature, though I'm kind of leaning toward a bug (specifically, an edge case the coders didn't think of, which could be easily solved).

All numbers are in hex.

Continues: 37E
Lives: DD
Gun: C3
Hover: 92
Bosses killed: 3FB. bit x = boss x+1
Boss items 1: 3FC. same values as 3FB.
Boss items 2: 99. bit 0: hover, 1: dive, 2: wall 1, 3: wall 2, 4: crusher, 5: key, 6: hyper
Homing Missiles: 6F0
Lightning: 6F1
Thunderhead Missiles: 6F2
Pause: 15

Gun Levels:
20: 2 long shots
40: 3 long shots
80: circling shots
C0: white wave shots
E0: full wave shots

Beginning of Object Table: 400. 12 slots. Slot 0 is reserved for the player. Slots 1-4 are reserved for projectiles. Enemies fill slots 5-11 as needed.

Object Struct (14 bytes)
byte @0: Object type. A few of the known object types:
3: Normal
4: Dying
5: On left wall
6: On right wall
7: On ceiling
8: Diving
9: Climbing H->V convex
A: Climbing V->H convex
B: Climbing horizontal->vertical concave
C: Climbing V->H concave
D/E/F 10/11/12: Entering/transitioning/leaving door right/left
1B: Outside tank
1D: Entering tank
84/85/86: Entering/transitioning/leaving door catacombs

byte @1: Orientation. The exact meaning of this seems to vary by object type.
Tank mode: Between 0 for left and F for right (the intermediates indicate that the tank is changing face), with the high bit set if the tank is pointing to the left
Catacombs mode: 0 for up, 1 for right, 2 for down, etc.
uint16 [LE] @2: Horizontal position. The high byte indicates the attribute-size tile, while the bottom byte is the position within that tile. The highest bit indicates that you're currently moving through a teleporting door.
uint16 [LE] @4: Vertical position
byte @6: X velocity
byte @7: Y velocity
byte @8: Attribute-size tile index on screen? This was always observed to be (Y * 0x11) + X where X and Y are relative to the tiles visible on screen.
byte @9: Hit timer: the number of ticks until the object can be hit again. Controls invulnerability, damage flashing, and also decreases gun by 1 for each tick above 1 (this causes gun power to drop smoothly rather than suddenly, though I'm not sure why they did it this way; life does not do this when damage is taken).
byte @A: Current AI state
byte @B: Frames till AI state change
byte @C: ?? (no observed effect)
byte @D: Life. For trivia value, normal tank shot does 4, hyper shot does 6, crusher shot does 8, normal catacomb shot does 1, catacomb shot with wave gun does 2, and grenades do 2.

Note that the AI state bytes in the struct are for simple enemies. Bosses have other state stored elsewhere. For example, in the above crab boss, the AI state and timer control movement but not spraying bubbles, which occurs entirely independently. The density of bubble spray, however, was directly controlled by the life of the boss; e.g. below 0x20 life (it starts with 50) it does the full sawtooth volley with dozens of bubbles.

& Very Old Things - Part 1

Bring back any painful memories?

So, a couple days I had one of those evil, perverted urges I'm so notorious for. Specifically, I felt like doing a bit of hacking of Blaster Master. For those not familiar with it, it was an NES game published 21 years ago. A good one, in fact. But before I talk a bit about anything I did resembling reverse-engineering, let me explain the NES hardware to the best of my knowledge (which consists of what I saw in my hacking, and a bit of stuff I looked up online).

The main CPU of the NES is a modified 6502, the CPU used in various Commodore and Apple computers (not that I ever used one of those). The 6502 is a primitive CISC CPU, and in fact somewhat resembles the x86 (though more primitive). It has 3 8-bit registers: a numeric accumulator (A) and 2 index registers (X and Y). Operations generally operate on the value of A and a memory location or literal, and write the result back to A.

It has a stack, though from what I saw in Blaster Master it seems to be relatively rarely used, used mainly to save registers (though even that was pretty rare). Specifically, I didn't see much in the way of stack frames holding local variables. Functions that require local variables tended to have (dedicated) memory ranges allocated to them to be used as private buffers. For example, one address I initially thought was the boss life location actually turned out to be in a buffer region used by the function while updating objects in the object list. This kind of surprised me, as the NES has only 2 KB of RAM; I imagine this must be forced by the architecture, e.g. a lack of instructions to access the stack at a specific offset.

As for the graphics system. If you ever messed around with text mode and text graphics in DOS, the NES graphics system is similar. At the lowest level, graphics are stored as blocks called patterns. Each pattern is 8x8 pixels, 2 bits each (total of 4 colors). The NES has enough video memory for 512 patterns at a time, stored in 2 pattern tables. What exactly it does with these patterns depends. The NES has 3 graphics layers: 1 for background and 2 for sprites (1 in front of and 1 behind the background layer).

deconstructulator provides an excellent illustration for most of the things discussed here. It shows the pattern tables (note that the top half is the sprite pattern table and the bottom half is the background pattern table) and sprites along with a playable version of Super Mario Bros.; although it does not show the name/attribute tables. Refer to that from here onward.

The background layer (illustration below) is very much like the screen buffer in DOS text mode; it's a buffer of screens composed of 32x30 patterns each (indices into the pattern table), called name tables (lost in translation, perhaps?); all patterns in the background must come from the same pattern table. The NES supports up to 4 screen buffers in this way, though it only contains enough memory for 2 of them (if the cartridge doesn't supply additional memory, the game can simply set the NES to mirror the 2 screens).

However, so far each pixel only has 2 bits of color (the bits in the pattern table). An additional table, called the attribute table, supplies an additional 2 bits to the name tables, increasing the total to 4 bits, or 16 colors (though each tile on screen still has only 4 colors within it). However, the attribute table does not contain a value for every tile. Rather, it only contains 1 two-bit entry for each block of 2x2 entries in the name table (so 16x16 blocks composed of 4 patterns). This is the reason 16x16 blocks appear everywhere in NES games - that's the smallest block that can be fully independently controlled.

The background position is specified independently of the sprites. A horizontal and vertical scroll position is specified by pixel for the background, which indicates where the graphics chip should start drawing the background on screen. This is how smooth scrolling works, although implementing this can be quite a trick, as you have to essentially use the name tables as a ring buffer (even more tricky if you support scrolling in both dimensions).




A shot of the side-scrolling portion of Blaster Master (top) and the corresponding, merged name/attribute tables (bottom). The white lines indicate where the top left of the screen currently is (where the two lines cross). The visual discontinuities are caused by the way the game streams the background into the name/attribute tables on demand, filling in only what's on screen in the frame; they're stale data. The color glitches result when the current color in the attribute table for an entry does not match some of the stale patterns still in that name table for that entry (e.g. on the far left the second column of patterns is discolored because they are stale and the attribute entry now corresponds to the first column of patterns, which is on screen).

The NES supports 64 sprites, each either 1 or 2 patterns in size (8x8 and 8x16, respectively), depending on whether a global flag is set. Analogous to the attribute table, each sprite contains the 2 high bits of color (though still that allows only 4 colors per sprite). Other info each sprite possesses includes position (obviously), mirroring parameters, and whether the sprite is in the foreground or background. However, even if you can have 64 sprites, the NES only supports 8 sprites per scan line; if there is more than that, only the 8 with the highest priority are drawn (smart games can cycle through their sprites each frame, but that results in flicker).

There are, however, some tricks that can be done to circumvent some of the innate limitations (e.g. 16 colors, 16x16 blocks, 64 sprites, etc.). These often involve clever but perverse tricks related to swapping out the various things such as scroll offset or sprite data while drawing is underway. One common use of this is to draw part of the screen (the gameplay) with scrolling, while a portion of the screen on top or bottom is fixed (the score area). This can also be used to draw more than 64 sprites per frame, though there's still a limitation of only 8 sprites per scan line.



Blaster Master and others frequently use the background as a grotesque way to draw very large sprites. In the above screen shot, the boss crab is actually the background, while the bubbles, player, and energy bars are sprites (the green areas of the boss are actually sprites, as well). The crab has a couple frames of animation; each of these is on a separate screen in the name table, and every frame the scrolling position is modified. This results in the crab moving around the screen and animating, as if it were a huge sprite.

Oh, and in case you were wondering, yes, this boss frequently exceeds the 8 sprites per scan line limit (that would be 4 bubbles), resulting in the game slowing down to draw them all.

& That Memory Leak

I'm pretty sure that a while back I mentioned a particular Firefox plugin called Feed Sidebar. It's a nice little RSS feed plugin that does exactly what I wanted an RSS plugin to do (and all others work differently). As such, I'm rather fond of it, and have been rather tolerant of its faults.

The particular fault I believe I discussed was that it leaked memory. With the ~15 RSS feeds I have on it set to update every 10 minutes, it leaked about 20 megs of memory per hour. While many would probably not find this to be a serious problem (e.g. 8 hours x 20 megs/hour = 160 megs leaked before shutting down for the day), as I tend to leave my computer running for weeks straight, this was a moderate annoyance. Left on its own, Firefox would crash about every three days due to address space exhaustion (32-bit applications have a 2 gig address space, and fragmentation can reduce the amount actually allocatable below that; I was seeing it crash around 1.5 gigs). Much more frequently, I'd start World of Warcraft and my computer would grind to a halt, as Windows really, really doesn't like it when you get > 90% memory usage (up until a month or two ago, when I have 4 gigs of RAM), and I'd have to manually restart Firefox at that point.

On one occasion I e-mailed the author about the problem; he said that he'd been looking for the leak for a while, and was stumped. Unfortunately, as I haven't done anything with Javascript (what Firefox plugins are written in) in over a decade, and I don't know the first thing about the Firefox plugin architecture, I couldn't go looking for the problem myself as I've done so many times in the past (at least 3 or 4 incidents on the blog).

However, a couple weeks ago the problem suddenly become much worse. Immediately after installing Firefox 3.5, I noticed that it was now hemorrhaging about 150 megs/hour, more than seven times as fast as in 3.0 and earlier (in fact, at first I thought it was that 3.5 was just unstable, as it crashed about every day; then I noticed that it was allocating massive amounts of memory). After verifying both that this was consistent/reproducible and that this was indeed due to the particular addon, I e-mailed the author again, with my new data.

Apparently that got a pretty quick response. A couple days later he sent me a test build he wanted me to try. After some looking, he'd come to believe that there was a bug in Firefox that was leaking SQLite resources; resources that should have been freed when an SQLite connection was closed were being leaked (it was not clear from his e-mail whether this was a new bug with 3.5, or just that the quantity of resources leaked was greater in 3.5). This test build included a workaround for it (presumably he saved the connection instead of creating a new connection every time it updates the RSS feeds, but he didn't say).

This seemed to work well. After installing it, I immediately noticed that it was not hemorrhaging memory like it did before (previously it was leaking about 25 megs each time the RSS feeds were updated, which was now gone). Rather, after a couple of days of collecting data, I concluded that it was now only leaking 1-2 megs each update (about 10 megs/hour).

It's not clear yet whether this is true leakage (which would suggest that one leak was plugged but another remains) or that this is a side-effect of the workaround. It's conceivable that Firefox might delay freeing SQLite resources as long as a connection is in use; if he's indeed keeping an SQLite connection open the whole time, we could imagine that this "leak" is not a leak (lack of resource reclamation) so much as a deferral of resource reclamation. If this is the case, this should go away after Firefox fixes the SQLite connection leak and he goes back to creating a new connection on every update.

We'll see.

Incidentally, version 4.1 of Feed Sidebar was released today; this is the version I tried a test build of. After I've had more time to collect data I'll have to see if it's leaking the same amount as the test build, or if there have been further modifications.

& Detexify

So, somebody just linked me to Detexify, a very neat little program that reads your "handwriting" and tries to find the TeX special character that you just wrote.

Now, personally I don't have much use for such a thing, as I don't use TeX. However, it happens to be open source, which means that if I can muster the energy I'm going to try it with the set of Chinese characters and see how well it can do identifying those. If it can do that decently I have some much less theoretical uses for it...

Curve Ball

Some surprising last-minute good news from France:

After the parliament voted in favor of the law, no one doubted that it would be approved by the senate and National Assembly as well. As expected the law was indeed ratified by the senate this morning, but to everyone’s surprise it didn’t make it through the National Assembly.
...
Unfortunately the law is not completely off the table. It is likely to be voted on again on April 27 according to members of UMP, one of the supporting parties. However, failing to get it passed through the National Assembly the first time is clearly a huge mistake that is almost amateurish, and public opinion is not likely to change anytime soon.

Which I suppose makes for a (tentative) good-triumphs-over-evil-in-the-end Hollywood ending, after what the proponents of the law pulled in parliament.

Name That Movie

See if you can recognize this one.

A bill written by big business interests is proposed in French parliament. Hugely controversial, the bill is opposed by most apart from the business interests that wrote it, and it is difficult to see how it could pass (although you can never underestimate the corruption of government officials). As the deadline for the vote draws near, an intense debate lasting 42 hours straight breaks out among parliament members.

Eventually, late Thursday evening, it is decided that the debate should cease and parliament members should go home for the night, and the bill would be voted on the next week. So, parliament members do exactly that. After about 98% of parliament members have left the building, the vote is called early, at nearly 11 PM on Thursday night. With 16 members remaining, the bill passes, 12 to 4.

Can you name that movie?

Actually you can't, because it actually happened - yesterday. This is the French Three-Strikes law, which promises to disconnect people from the internet on allegation of copyright infringement, without ever having to present evidence in court or even tell the accused what copyright they are thought to have infringed. It will also require running spyware on all computers that constantly talks to government systems and monitors activity and the state of your network.

Welcome to French democracy, proving that America really isn't that bad afterall.

& 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.

Various Thingies

First of all, I should mention that my house is fine; the fire didn't get near it. The probability of it getting here was fairly low, but we did a bit of better-safe-than-sorry packing. Though last night while driving home from school I did drive past a (unrelated) fire that filled the entire intersection with smoke in about a 50 feet radius; I still don't know what was on fire (I couldn't see it), but the smoke was very obvious, and I heard fire trucks going by.

In other news, it's been relatively difficult to collect data on Firefox after reenabling the Feed Sidebar addon. Firefox crashed after three days of logging memory usage, and then a couple days later I needed to restart it because I needed the memory for WoW (Firefox was using about a gig). But the addon defintiely seems like the cause of the memory leak. From the days I gathered data, it looks like it leaks about 40 megs/hour (although that's only over a couple days; it might decrease over time).

Finally, I just noticed something that happened last year: the Starcraft soundtrack, not previously available (the compressed audio shipped with the games is 22 khz ADPCM, which is pretty poor quality), is on iTunes for $10; the other Blizzard OSTs that were included in the collectors' editions of Diablo 2, Warcraft 3, and World of Warcraft are also available there (though unfortunately all of them are single CDs, which means they are incomplete). The music is DRM-free (although I hear they encode personally identifying information in the audio files), 256 kbps AAC (good quality), though you will have to install the Apple iTunes crapware to buy it. I'm told the M4A files should play on all PC audio players that support AAC (I know they work on WinAmp), though they are not MP3s, and will not work on MP3 audio players. That's your public service announcement for today.

& More Leakage

So, after writing that last post about the audio driver handle leak, I decided to log some data - specifically, the amount of memory Firefox allocates, and the number of handles in the Symantec Anti-Virus process smc.exe. It's now been about a week since I started gathering data (although unfortunately the power went out in the middle, so I ended up with two smaller replicates).

The data for smc.exe shows that it begins at approximately 450 handles on startup, and acquires an additional 3100 handles per day (although 'day' is about 14 hours, as I hibernate my computer at night; meaning about 220 handles/hour). This definitely doesn't seem normal, and I'm going to venture a guess that it's a handle leak. I also noted that the increase seems to be linear over the course of the day, so is unlikely to be related to something like automatic update.

I already knew that Firefox was hemmorhaging memory. If I recall correctly, the amount of memory allocated by Firefox increased by 200-300 MB per day. This time, I tried using Firefox for several days without two of the three addons I normally use (the third was NoScript, so I didn't want to try without that unless I had to). While this test didn't last as long as I'd hoped (thanks to that power outage), after four days, Firefox had only increased from 125 MB (when I first started it, with a lot of saved tabs) to 205 MB (now). In four days I would have predicted it would hit 600-900 megs.

This strongly suggests that one of the two plugins is responsible for the massive leakage, although I'll have to watch what happens after I reenable the one most likely the be causing the leak (as the other is newly installed, and this problem has been around for longer): Feed Sidebar (version 3.1.6). So, we'll see what happens with that. Might have an answer in another 4-7 days about that.