Author Archives: Multimedia Mike

SNES Hardware Compression

I was browsing the source code for some Super Nintendo Entertainment System (SNES) emulators recently. I learned some interesting things about compression hardware. I had previously uncovered one compression algorithm used in an SNES title but that was implemented in software.

SNES game cartridges — being all hardware — were at liberty to expand the hardware capabilities of the base system by adding new processors. The most well-known of these processors was the Super FX which allows for basic polygon graphical rendering, powering such games as Star Fox. It was by no means the only such add-on processor, though. Here is a Wikipedia page of all the enhancement chips used in assorted SNES games. A number of them mention compression and so I delved into the emulators to find the details:

  • The Super FX is listed in Wikipedia vaguely as being able to decompress graphics. I see no reference to decompression in emulator source code.
  • DSP-3 emulation source code makes reference to LZ-type compression as well as tree/symbol decoding. I’m not sure if the latter is a component of the former. Wikipedia lists the chip as supporting “Shannon-Fano bitstream decompression.”
  • Similar to Super FX, the SA-1 chip is listed in Wikipedia as having some compression capabilities. Again, either that’s not true or none of the games that use the chip (notably Super Mario RPG) make use of the feature.
  • The S-DD1 chip uses arithmetic and Golomb encoding for compressing graphics. Wikipedia refers to this as the ABS Lossless Entropy Algorithm. Googling for further details on that algorithm name yields no results, but I suspect it’s unrelated to anti-lock brakes. The algorithm is alleged to allow Star Ocean to smash 13 MB of graphics into a 4 MB cartridge ROM (largest size of an SNES cartridge).
  • The SPC7110 can decompress data using a combination of arithmetic coding and Z-curve/Morton curve reordering.

No, I don’t plan to implement codecs for these schemes. But it’s always comforting to know that I could.

Not directly a compression scheme, but still a curious item is the MSU1 concept put forth by the bsnes emulator. This is a hypothetical coprocessor implemented by bsnes that gives an emulated cartridge access to a 4 GB address space. What to do with all this space? Allow for the playback of uncompressed PCM audio as well as uncompressed video at 240x144x256 colors @ 30 fps. According to the docs and the source code, the latter feature doesn’t appear to be implemented, though; only the raw PCM playback.

Back on the Salty Track

After I posted about my initial encounter and frustration with Google’s Native Client (NaCl) SDK and took a deep breath, I realized that I achieved an important proof of concept– I successfully played music using the NaCl SDK audio output interface. Then I started taking a closer read through the (C-based set of) header files and realized I might be able to make a go of it after all. I had much better luck this time and managed to create a proper Native Client interface that allows for controlling playback, presenting metadata, and toggling individual voices (a fascinating tool for studying classic game music).

I haven’t bothered to post the actual plugin because, really, what’s the point? I started with NaCl SDK 0.3 which requires Chrome 12, which means terribly limited reach, even among Chrome users. At least, that was true when I restarted this little project. Chrome 12 was formally released this past week. Chrome development really does move at breakneck pace.

Anyway, here is a static screenshot of what the plugin currently looks like:



Not pretty, but it does the job.

Dev Journal
Various notes based on this outing:

  • Portability: I tested my plugin using Chrome 12 on 64-bit Windows, Mac, and Linux. Mac and Linux both work; Windows does not.
  • Build System: SDK 0.3 is still lacking in its ability to compile .cpp files (instead of .cc files); necessary because libgme is C++ using .cpp files. This requires some build system modification.
  • Getting the interfaces: This is where I got tripped up the first time around. get_browser_interface() from their example actually refers to a parameter passed in through the PPP_InitializeModule() function. The SDK’s template generator renames this to get_browser().
  • Debugging: I feel unstoppable once I have a printf() mechanism available to me during development. To that end, console.log() from JavaScript outputs to Chrome’s built-in JavaScript console log while putting printf() statements in the actual NaCl plugin causes the messages to show up in ~/.xsession-errors on Linux/X.
  • Size Matters: The binaries generated with the NaCl 0.3 SDK are ridiculously huge. The basic “Hello World” example in C compiles to binaries that are 6.7 MB and 7.8 MB for the 32- and 64-bit builds, respectively. This made me apprehensive to build a full version of SaltyGME that contains all the bells and whistles offered by the library. However, all of the GME code compiled into the binary adds very little size. Curiously, the C++ version of “Hello World” only ranges from 1.8-2.0 MB for 32- and 64-bit. Is there some kind of C tax happening here? Note that running ‘strip’ on the resulting .nexe files (they’re ELF files, after all) brings the sizes down into the C++ range, but at the cost of causing them to not work (more specifically, not even load).
  • No Messaging: The NaCl SDK is supposed to have a messaging interface which allows the NaCl plugin to send asynchronous messages up to the hosting page. When I try to instantiate it, I get a NULL. I’m stuck with the alternative of polling from the JavaScript side to, e.g., determine when a song has finished loading via the network.

That’s all I can think of for now. I may work on this a little more (I’d like to at least see some audio visualization). Maybe Google will enable NaCl per default sometime around Chrome 21 and this program will be ready for prime time by then.

See Also:

Cracking Aztec Game Audio

Here’s a mild multimedia-related reverse engineering challenge for you. It’s pretty straightforward for those skilled in the art.

The Setup
One side effect of running this ridiculously niche interest blog at the intersection of multimedia, reverse engineering, and game hacking is that people occasionally contact me for assistance on those very matters. So it was when one of my MobyGames peers asked if I can help to extract some music from a game called Aztec Wars. The game consists of 2 discs, each with a music.xbe file that contains multiple tunes and is hundreds of megabytes large.



That’s all the data I received from the first email. At first I’m wondering what makes people think I have some magical insight into cracking these formats with such little information. Ordinarily, I would need to have the entire data file to work with and possibly the game binaries. But I didn’t want to ask him to upload hundreds of megabytes of data and I didn’t feel like downloading it; commitment issues and all.

But then I gathered a little confidence and remembered that the .xbe files are probably just Game Resource Archive Formats (GRAF) which are, traditionally, absurdly simple. I asked my colleague to send me a hexdump of the first kilobyte of one of the .xbe GRAFs ('hexdump -C -n 1024 music.xbe > file') as well as the total file size of the GRAF.

The Hexdump
The first music.xbe file is 192817376 bytes large. These are the first 1024 144 bytes (more than enough):

00000000  01 00 00 00 60 04 00 00  14 00 00 00 01 00 00 00  |....`...........|
00000010  0d 00 00 00 48 00 00 00  94 39 63 01 1c a4 21 03  |....H....9c..¤!.|
00000020  7a d2 54 04 04 28 ad 05  d8 88 fd 06 d8 88 fd 06  |zÒT..(­.Ø.ý.Ø.ý.|
00000030  2a 6e 46 08 2a 6e 46 08  2a 6e 46 08 2a 6e 46 08  |*nF.*nF.*nF.*nF.|
00000040  50 13 2f 0a e0 28 7e 0b  52 49 46 46 44 39 63 01  |P./.à(~.RIFFD9c.|
00000050  57 41 56 45 66 6d 74 20  10 00 00 00 01 00 02 00  |WAVEfmt ........|
00000060  44 ac 00 00 10 b1 02 00  04 00 10 00 64 61 74 61  |D¬...±......data|
00000070  fc 13 63 01 00 00 00 00  00 00 00 00 00 00 00 00  |ü.c.............|
00000080  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

The Challenge
Armed with only the information in the foregoing section, figure out a method for extracting all the audio files in that file and advise on their playback/conversion. Ideally, this method should require minimal effort from both you and the person on the other end of the conversation.

The Resolution
The reason I ask is because I came up with a solution but knew, deep down, that there must be a slightly easier way. How would you solve this?

The music files in question are now preserved on YouTube (until they see fit to remove them for one reason or another).

Internecine Legal Threats

FFmpeg and associated open source multimedia projects such as xine, MPlayer, and VLC have long had a rebel mystique about them; a bunch of hackers playing fast and loose with IP law in order to give the world the free multimedia experience it deserved. We figured out the algorithms using any tools available, including the feared technique of binary reverse engineering. When I gave a presentation about FFmpeg at Linuxtag in 2007, I created this image illustrating said mystique:



It garnered laughs. But I made the point that we multimedia hackers just press on, doing our thing while ignoring legal threats. The policy has historically worked out famously for us– to date, I seem to be the only person on the receiving end of a sort-of legal threat from the outside world.

Who would have thought that the most credible legal threat to an open source multimedia project would emanate from a fork of that very project? Because that’s exactly what has transpired:



Click for full threat

So it came to pass that Michael Niedermayer — the leader of the FFmpeg project — received a bona fide legal nastygram from Mans Rullgard, a representative of the FFmpeg-forked Libav project. The subject of dispute is a scorched-earth matter involving the somewhat iconic FFmpeg zigzag logo:

   
Original 2D logo enhanced 3D logo

To think of all those years we spent worrying about legal threats from organizations outside the community. I’m reminded of that time-honored horror trope/urban legend staple: Get out! The legal threats are coming from inside the house!

I’m interested to see how this all plays out, particularly regarding jurisdiction, as we have a U.K. resident engaging an Italian lawyer outfit to deliver a legal threat to an Austrian citizen regarding an image hosted on a server in Hungary. I suspect I know why that law firm was chosen, but it’s still a curious jurisdictional setup.

People often used to ask me if we multimedia hackers would get sued to death for doing what we do. My response was always, “There’s only one way to know for sure,” by which I meant that we would just have to engage in said shady activities and determine empirically if lawsuits resulted. So I’m a strong advocate for experimentation to push the limits. Kudos to Michael and Mans for volunteering to push the legal limits.