I just wanted to draw attention to a recent effort by one Michael Sabin who has been building a Java application called jPSXdec to play back videos ripped from the Sony PlayStation 1.

To review, the original PlayStation had a bit of dedicated hardware called the motion decoder (MDEC) which decoded specially formatted blocks of what were essentially motion JPEG data. Assorted games also compressed the blocks using Huffman codes which were decoded by software. While the MDEC hardware was rigid in the data it would accept, PS programmers could deploy whatever Huffman tables they chose. I always thought it would be an interesting project (and a natural extension of my usual efforts) to catalog the various tables needed to play movies from different games, as well as different strategies that games have used to store the data on the disc.

Michael S. has been doing just that. There is a blog to document jPSXdec’s progress. Near and dear to my heart, however, is the fact that he is building a remarkable document (seen in the project’s download list) that explains precisely how to decode this data, from the perspective of a non-multimedia geek, no less.

Google announced their Highly Open Participation Contest today. I really hope that the name is not a backronym inspired by the common acronym for International House of Pancakes. GHOP is an effort to bring pre-university students into the open source fold through a Summer of Code-like program. Whereas GSoC projects were required to center around code, these GHOP efforts can be related to documentation, QA, R&D, translation, and assorted other areas, as specified by participating project’s issue trackers.

10 open source projects were selected for this initial run. FFmpeg was not one of them. According to the FAQ page, “each project has a fairly low barrier to entry”. I admit, that would eliminate FFmpeg from consideration right away.

The number is 240. In learning how YouTube works its magic so that MobyGames may one day take user’s video submissions, Trixter has been doing his own poking at the video giant to determine what parameters the site uses to transcode user videos. What he learned: 240 lines, 240 kbps, 240 frames in a GOP. His best guess for why things are the way the are: …”it sure seems like the YouTube guys were taking blind stabs at encoding parameters (ie. ‘Hey, let’s set everything to 240 and see what happens!’).”

If Michael can show off the very first pictures from his new digital camera, then so can I… where “new” is roughly July, 2003. I was organizing thousands of digital photos from the last 6 years and found what must be the first pictures from my current digital camera, based on the filename. And wouldn’t you know, the pictures were of felines:

It’s all coming back now — I invested in the Canon Powershot S400 back when I was fostering a family of 5 kittens and their mother for the local animal shelter.

So it has come to this– posting cat pictures. Eh, it’s a holiday. Above was Scooter. He was the bravest of the litter. This was feeding time:

As you can plainly see, I’m not a very good photographer. Plus, I had a phenomenal amount of difficulty adjusting to this new camera, which was a substantial feature upgrade from the S100 I had purchased 2 years earlier. Many of my earliest photos can out very blurry or with saturated colors until I learned how the camera expected to be used.

So I’m running the latest Ubuntu release in a virtual machine under my main Windows XP machine (it’s a blessing that I no longer need to choose between operating systems these days– I can run them all simultaneously on the same machine if I wish). Today I noticed a feature of Bash that for all I know has been in place for over a decade. I just have never seen it enabled by default in any distribution before. I had to do some research — indeed, one of the first problems in Unix is learning how to ask the right question — but I eventually figured out that the feature is called “Programmable Completion”.

Tab completion is God’s gift to command line navigation. It’s something I always take 10 seconds to carefully explain to anyone who is struggling with the Unix command line for the first time since navigating through a filesystem is agonizing without it. Programmable completion takes tab completion and tries to make it smarter. I first noticed this peculiar behavior on my Ubuntu VMware session today. If there are 2 files in the current directory, xyz.tar.gz and xyz.tar.bz2, then typing ‘tar zxvf x<TAB>’ automatically completes xyz.tar.gz while ‘tar jxvf x<TAB>’ automatically completes to xyz.tar.bz2. I noticed this, thought it was an interesting touch, thought for a moment about how it might work, and immediately wondered what would happen if the underlying mechanism isn’t aware of a mapping that I need.

It didn’t take long before I ran into that eventuality. I was trying to play some impossibly obscure formats with xine. I navigated to the necessary directories only to find that they were apparently empty of any files. I never realized just how important tab completion is to me. Now I’m reading pages of documentation trying to figure out how to disable programmable completion entirely. (It would probably be enough to ask the desktop terminal emulator to run my own Bash config files on startup– I don’t understand why I have to specifically configure such programs to do this.)

Effectively, Bash is making a decision here about what files it thinks I want to see. I’m surprised a Linux distribution would program that kind of behavior by default. How condescending is it when a Microsoft OS tells you that there are entire sets of files that you don’t need to see? Maybe that’s not a fair comparison, as the programmable completion feature is more akin to a list of file filters in a “File Open…” dialog box. Thing is, there’s no obvious way to select “show all files”.

Computer programs get into trouble when they try to anticipate what a normal user needs. More often, such programs have the effect of shaping end user behavior to account for the educated guesses that the computer makes.

Engineering is about trade-offs and compromises. One of the most fundamental trade-offs to be made when designing a storage format is whether multi-byte numbers will be encoded as little or big endian numbers. But have you ever studied the data structures involved in ISO-9660, the standard filesystem format for optical discs? It seems that the committee tasked with developing this standard were unwilling to make this one tough decision and specified all multi-byte numbers as omni-endian. I just made that term up. Maybe it could be called bi-endian or multi-endian. The raw detail is that multi-byte numbers are stored in little endian format and then in big endian. For example, 0×11223344 is stored using 8 bytes: 0×44 0×33 0×22 0×11 0×11 0×22 0×33 0×44.

Do any other filesystems take this compromise? I am not that versed. I have studied the odd game-related optical filesystem; I had to write a manual ext2 searching tool for a sysadmin class; I also had to try to recover a virus-corrupted FAT16 filesystem (to no avail; that virus cleanly chewed up some of the most important sectors).

Anyway, if I were to go ahead and try for a new FUSE driver for ISO-9660 (or modify an existing driver), I would want to go after the main format. Plus, I would want to natively interpret that CISO format on the fly. Further, I would use this as a platform to understand what is so special about the apparent ISO-9660 data ripped from a Sega Dreamcast GD-ROM.

Are there any other ISO bastardizations to target for such a tool?

Ian Farquhar expressed surprise the other day that anyone reads his blog. So I thought I would point out that his new blog is kind of nifty. I don’t know what backend software is powering the blog, though, and I’m mistrustful of all the Javascript goings-on. The page transitions frighten me.

Anyway, he likes to talk about hard multimedia-type stuff. Which is apropos since he probably works for Nero (hey Ian: an ‘About Me’ page — about you — would do wonders). So you should check it out. We niche multimedia blogs need to stick together. I hope his blog stays fresh.

Remember my old PAVC idea? I have been thinking about it again. As a refresher, this idea concerns efficiently and losslessly compressing RGB video frames output from an emulator for early video game systems such as the Nintendo Entertainment System (NES) and the Super NES. This time, I have been considering backing off my original generalized approach and going with a PPU-specific approach. (PPU stands for picture processing unit, which is what they used to call the video hardware in these old video games systems.) Naturally, I would want to start this experiment (again) with my favorite — nay — the greatest video game console of all time, the NES. Time for more obligatory, if superfluous, NES screenshots.

Little Samson, all-around awesome game

Here’s the pitch: Modify an emulator (I’m working with FCE-Ultra) to dump PPU data to a file. Step 2 is to take that data and run it through a compression tool. What kind of data would I care about for step 1? On the first frame, dump out all of the interesting areas of the PPU memory space. This may sound huge, but it is only about 9-12 kilobytes, depending on the cartridge hardware. Also, dump the initial states of a few key PPU registers that are mapped into the CPU’s memory space. As the game runs, watch all of these memory and register values and log changes. This really isn’t as difficult as it sounds since FCEU already cares deeply when one of these values changes. When something changes, mark it as “dirty” and dump that value during the next scanline update.

With that data captured, the next challenge is to compress it. I am open to suggestions on how best to encode this change data. I would hope that we could come up with something a little better than shoving a frame of change data through zlib.

Decompression and playback would entail unraveling whatever was performed in step 2 above. Then, the decoder simulates the NES PPU by drawing scanline by scanline, and applying state change data between scanlines.

What are the benefits to this approach? Ideally, I am aiming not only for lossless compression, but for better compression than what is ordinarily achieved with the large files distributed via BitTorrent and coordinated at tasvideos.org. When I first started investigating this idea over 2 years ago, MPEG-4 variants were still popular for compressing the videos. These days, H.264 seems to have taken over, which performs much better, even on this type of data (allegedly, H.264′s 4×4 transform allows for lower artifacts on sharp edge data such as material from old video game consoles).

Sword Master, mediocre game with great graphics

There are also some benefits from the perspective of NES purists. The most flexible NES emulators allow the user to switch palettes in order to get one that is “just right”. A decoder for this type of data could offer the same benefits.

Of course, an encoder is not much use without an analogous decoder that end users can easily install and use. I think this is less of an issue due to the possibility of creating a decoder in Flash or Java.

Followup: Some Reddit readers tackled this challenge and conquered it. Read up on it here.

Back in the glory days of the old 8-bit Nintendo Entertainment System, I used to read my Nintendo Power magazine issues religiously. One issue that stood out to me, and that I never forgot about, is one that briefly mentioned Treasure Master (volume 26, July 1991, Robin Hood: Prince of Thieves issue).

This will be the first NES game where you can actually win prizes by playing it to the finish! The Game Pak will be released in the fall, and everyone will have time to master it. When you finish the game, you’ll reach a point where you can enter a speical password. In February of 1992, American Softworks will reveal the password that will allow you to play a secret portion of the game. The first person to finish the secret level and call in will win a $25,000 bond. Many of those who finish later will still be eligible for prizes– the sooner you finish, the better the prize. As you can imagine, the code is top secret, and the password system has been proven uncrackable by MIT and the CIA. (emphasis added)

click for larger image

So the gimmick for this substandard, side-scrolling, run & jump game was that players would buy it, play it, and build up skill in a few months. Then, after everyone has had a chance to get really good at the game, the company would release a password that would unlock a secret stage. Play through this stage and you could win big prizes.

Naturally, the part about the uncrackable code caught my attention. I didn’t even realize the CIA provided such a vetting service. Anyway, I didn’t hear anything else about the game again. Many years passed and I saw the game in a used video game shop. I figured it was time to revisit the uncrackable code issue since I know a little more about computers and codes now. And I also know better than to accept an uncrackable code claim at face value.

How uncrackable is the code? The introductory blurb from Nintendo Power raises some questions, many of which can be answered by the Treasure Master instruction manual. The full details of the contest are provided. Apparently, the password was to be announced on MTV on April 11, 1992, probably during a commercial. Players would enter the password, along with their game cartridge’s unique serial number, in order to unlock the special levels of the game. Upon completion of the levels, the game would return a special winning number that the player could give to the operator on the other end of a 1-900 phone number to try to win a prize.

To be fair, the official manual doesn’t mention the uncrackable code nonsense. The James Bond material highlighted in the Nintendo Power preview can probably be attributed to some Marketing/PR flunkie at American Softworks working more closely with the magazine than their own engineering department.

Also, Nintendo really wants you to know that they have nothing to do with the contest:

Threat Model
Read the rest of this entry »

After completing gcfuse and xbfuse, I am hungry for more game-related filesystem hacking. I set my sights on another format — I wondered what lay in hiding on those universal media discs (UMDs) that the Sony PlayStation Portable uses.

You probably don’t have the tools or the know-how to rip sectors off of these discs by yourself. If you happen to come across a pre-ripped image in the shadier portions of the internet, you may find that the rip has an extension of .cso. This stands for compressed ISO. Would you be surprised to learn that there is not a lot of documentation about this format out there? There are some closed but free Windows tools out there to convert between ISO and CISO and some other formats. What knowledge is out there indicates that the format offers 9 different compression levels. So does stock zlib.

Internally, a CISO format begins with a ‘CISO’ signature and eventually starts in with an enormous table of indices. These seem to be absolute offsets into the file. My first theory was that they are individual files. Combined with the above zlib speculation, I figured that each file was zlib compressed. That’s when I enlisted the help of the fellow who recently implemented native zlib functionality in FFmpeg — Mans Rullgard.

What he managed to figure out was that each index in the table actually references a 2-kilobyte sector. Further, the offset has its high bit cleared to indicate that the sector is the last of a file (a UMD has a max capacity of 1.8 GB which can be expressed in only 31 bits). Thus, the deltas between the indices imply the length of the sector, which is almost alway 2048 bytes, except for (statistically) the last sector of the file. So this leads us to the revolutionary compression technology on display here–

Do not store the final sectors of individual files with implicit zero-padding. (Not true; read further analysis in the comments.)

Hey, it counts as compression. The technique exploits a characteristic inherent in a specific type of data. It seemed a bit silly at first, in a “would that actually make a difference?” kind of way. But the math does work. At least for the few representative samples observed, the CISO image is about 75% of the size of the “uncompressed” image. If a disc uses its full 1.8 GB, then 1,800,000,000 bytes / 2048 bytes/sector = 878907 sectors. 878907 sectors * 4 index bytes/sector = 3515628 bytes. It’s 3.5 MB, but not nearly enough to blow the 2 GB limit necessary to make this format work in the worst case scenario.

Honestly, I haven’t had this much fun collaboratively cracking a file format since a bunch of us got together back in the day and worked out Nullsoft Video (NSV)… and then the official spec was released anyway.

There are still a number of mysteries:

• None of this explains the advertised compression levels feature. I am starting to think that perhaps the entire index table can be zlib compressed, but that it simply wasn’t done for the observed samples.
• There is no real filesystem data present. It stands to reason that the original UMD must have some notion of a filesystem since some utility knew where the files lived and how long they were. The Wikipedia article claims that these discs use an ISO-9660 filesystem. I generally know what ISO-9660 filesystem data looks like, and I’m not seeing it here. There isn’t much familiar, except for some PNG files which are difficult to interpret, leading to…
• Is the filesystem fragmented? That would be highly uncharacteristic of a filesystem built to live on an optical, read-only medium. But cursory investigations have indicated that there might be some fragmentation.
• Exactly what is the usage model for these images? Real-time access from a memory stick, I hope? Because Mans determined that stock bzip2 performs better than CISO on a raw image.

Here are the format details we have worked out so far. If anyone knows the original author of the CISO format, send him over here. In my experience, people who design these types of formats are not necessarily trying to keep anything secret; they just haven’t gotten around to writing up and publishing a formal description, and have no compelling reason to release their tools’ source code into a Windows world where most people can’t compile anyway.

Read the rest of this entry »