Monthly Archives: April 2006

Patenting CPU instruction sets and $150 PCs

Via a blurb on ArsTechnica about a Chinese $150 PC, I’ve stumbled upon the Story of Lexra, a now out-of-business semiconductor IP provider. A few things in that article struck me as interesting, namely

  • You cannot patent an instruction set.
  • “You can patent designs and methods that are necessary to implement a particular unusual instruction that is part of the instruction set.
  • Guess what Intel has patents for MMX instructions on… Although this point is now moot, as AMD and Intel have cross-licensing agreements, it was an interesting way to stop AMD from offering “fully compatible” CPUs (which resulted in AMD offering 3Dnow).
  • “One interesting problem with the patent system is that one institution, the PTO, determines whether a patent is valid but a different institution, the courts, determine whether one infringes. It is entirely possible for the two institutions to interpret a patent differently and for either a non-infringer to be wrongly convicted or an infringer to get away with their crime.

Scary, isn’t it?

Phoenix Wright – Ace Attorney (Nintendo DS)

Phoenix Wright is a bit an odd title for Western gamers, but I sincerely hope that more niche titles like it make their way over here from Japan. It’s a strongly structured adventure (although some would argue it is not much more than a heavily scripted visual novel), but that is not to its detriment in my opinion.

In your role as defense attorney, you alternatingly look for clues / evidence, and then progress to the actual trial, where you cross-examine witnesses to uncover contradictions in their testimonies. While that may not sound like much, the contradictions become increasingly hard to find and the overall story (as in the crimes themselves with their motivations and their relation to each other) meshes all of that into an interesting narrative.

There are 5 cases altogether, 4 of which are ported from the Japanese GBA game, and a much longer 5th case, which was specifically written for the DS and uses many of the system’s features very well (touch-screen, microphone, 3D graphics). Overall, the game took me about 10-12h to complete, and I very much enjoyed finding clues and contradictions, although as mentioned before, the structure is very rigid and usually there is only one correct way of doing things.

Size-optimising Code

I try to keep my image compression code fairly simple; it doesn’t do the best lossy compression, it doesn’t to the best lossless compression, but it does both fairly well, fairly fast, and without introducing much code bloat.

As a measure of this, I simply look at the size of the resulting executable for my simple test-application, wako. This can of course be very misleading, but it certainly is some measure of complexity, and I try to maintain its size below 40,000 bytes. But generally speaking, I want to do this by simplifying the code and making it more reusable, not by applying some complicated tricks that make the code harder to read but result in smaller a smaller binary.

So after fixing a problem in the implementation (using a fixed factor to convert from a floating point error-estimate of the mean-square error to a fixed point representation, which could then overflow), the code had grown above the “magic 40,000” mark. This was due to the fact that many channels can be interleaved into a single file, but to do that properly they each have to have comparable error estimates.

One obvious place to reduce the size, is the very basic command-line argument parser (which is not part of the library itself, but the sample application), which when commented out, reduces the size of the binary by 8kb! Rewriting this explicit parser to be data-/table-driven did not reduce the size as much as hoped, but it was enough.

39,849

As an aside, did you know the order of declarations within a structure has a non-negligible effect on code-size? 😉

Wavelet 3.2

As I’ve taken a two-day vacation pre-easter, I’ve gotten some more work done on my Wavelet Image Compression Library (and not played games as some of my colleagues were led to believe ;)).
Before this version all the subbands of an octave (i.e. HD, VD, and DD coefficients) were written as a single block in an interleaved manner. The changes I’ve made give each subband its own block, which increases the number of blocks, and thus allows for better and more fine-grained scheduling (which increases compression performance). Unfortunately, this led to a three times slower error estimation, which I then managed to cunningly avoid by computing the estimate for 3 blocks at a time.
Other changes include a more consistent behaviour for the -bpp command line switch, bug fixes to the scheduling where my accumulated fixed-point error estimates would overflow, and quite a few other things.
A experimental change was an exact error estimation, which I’ve then removed again as the code became unreadable, it was slow as hell, and didn’t actually help that much.
There is now a Darcs repository here (don’t try browsing there) from which you can get the current version and against which you can send me patches. You can also read my totally unfunny changelog entries if you need more information on the changes between versions.