Breaking Eggs And Making Omelettes

Topics On Multimedia Technology and Reverse Engineering


Archives:

Important Strides In Compression Technology

November 16th, 2007 by Multimedia Mike

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.


Universal Media Disc (UMD) for the Sony PSP

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.

All multi-byte numbers are little-endian.

  bytes 0-3      signature: 'CISO'
  bytes 4-7      unknown
  bytes 8-11     size of decompressed ISO
  bytes 12-15    unknown
  bytes 16-19    sector size in bytes (usually 0x800 = 2048)
  bytes 20-23    unknown
  bytes 24..     index data

Each index is 4 bytes. The top bit is set if the sector is part of contiguous data; the top bit is cleared if that sector is the last one representing the file. The length of the index data is implied by the value in the first entry in the table, since that is the absolute location of the first sector. The length of a sector is implied by the delta between two consecutive indices. The final index in the index table is the same as the length of the entire CISO image file.

The three unknown fields, starting at bytes 4,12, and 20, respectively, tend to contain 0, 0, and 1, respectively. I am not versed in zlib compression levels, but does 0 indicate no compression? Or perhaps 1?

Posted in Game Hacking | 8 Comments »

8 Responses

  1. Jim Leonard Says:

    “Exactly what is the usage model for these images? Real-time access from a memory stick, I hope?” Yes, that’s exactly what they are for. In the wonderful world of PSP hacking, you can dump games directly to a memory stick and run them from there. Heck, you can run multiple games from a big enough stick, eliminating the need to carry games around with you.

  2. NBC Says:

    typedef struct ciso_header
    {
    unsigned char magic[4]; /* +00 : C’,’I’,’S’,’O’ */
    unsigned long header_size; /* +04 : header size (==0x18) */
    unsigned long long total_bytes; /* +08 : number of original data size */
    unsigned long block_size; /* +10 : number of compressed block size */
    unsigned char ver; /* +14 : version 01 */
    unsigned char align; /* +15 : align of index (offset = index[n]<<align) */
    unsigned char rsv_06[2]; /* +16 : reserved */
    #if 0
    // INDEX BLOCK
    unsigned int index[0]; /* +18 : block[0] index (data offset = index<<align) */
    unsigned int index[1]; /* +1C : block[1] index (data offset = index<<align) */
    :
    :
    unsigned int index[last]; /* +?? : block[last] */
    unsigned int index[last+1]; /* +?? : end of last data point */
    // DATA BLOCK
    unsigned char data[]; /* +?? : compressed data */
    #endif
    }CISO_H;

  3. Multimedia Mike Says:

    Thanks, NBC. I suppose that pretty much answers my question. Although some of those fields do not reconcile with my samples. I would have noticed the header size field if it were 0x18, but my samples report 0.

    So did I, in fact, call it when I presumed that the individual sectors are zlib-compressed? But that wouldn’t make much sense since many sectors are 2048 bytes. Is it that only single-sector files, or the final sectors of files, are compressed?

    That could explain why I could not see any ISO-9660 data structures, and perhaps it might explain why the PNG files inside don’t seem to be valid (if the tail sector is compressed).

  4. NBC Says:

    http://www.google.com/search?hl=en&q=devhook+sdk&btnG=Google+Search

    get the devhook sdk

  5. Multimedia Mike Says:

    Thanks for the clue. Worming through the links, I found this program that includes C source for reading a CISO.

    It turns out that the high bit does not indicate that the file is part of a contiguous sector. Rather, it indicates that the sector is compressed with zlib.

    One day, I need to write a ISO-9660 FUSE driver that knows how to handle various deviations and bastardizations of the format, such as CISO and the Dreamcast’s variation.

  6. Ian Farquhar Says:

    Cool stuff, guys.

    It may surprise you to know (well, it surprised me) that the physical UMD spec is actually formally documented as ECMA-365:

    http://www.ecma-international.org/publications/standards/Ecma-365.htm

    Needless to say, they’ve not documented the logical disk format, so the above is equivalent to ECMA-130 (for CD’s). Any work anyone can do to pull the as-yet undocumented logical format together would be really interesting.

  7. Multimedia Mike Says:

    Yeah, I caught that on your blog, Ian. My memory is a bit blurry now, but that might have been what prompted me to want to study the UMD filesystem layout.

    Physical disc specs are a bit low level for my taste. That stuff gets handled by a different department. From my perspective, I start caring about the data when it gets distilled and error-corrected into nice, neat, 2048-byte sectors. :-)

  8. Ian Farquhar Says:

    I’m amazed that anyone is reading my blog. Nice to hear.

    It still begs the question: why did Sony submit their spec to ECMA? The official reason was to facilitate the release of movies on UMD, and for it to become the standard for disc-based mobile video.

    And breaking with historical tradition, Sony’s announcements seem to include adult content as a major genre. For those unfamiliar with the history, it is said that one of the major factors contributing to Beta’s loss against VHS was Sony’s hostility to adult movies. The early purchases of VCRs by consumers of this genre heavily favored VHS, and Beta never recovered the lead despite being technically superior in most ways.

    Anyway, if mobile movies were the aim, then it’s still half a spec. Possibly they’ve pushed this through ECMA to build physical construction production capacity, thus reducing cost per title, while keeping the logical spec proprietary, and maybe under Sony control? Hard to say.

    Even so, it still doesn’t make sense. I really suspect that Sony had undisclosed bigger plans or products, that have never come to fruition.