Breaking Eggs And Making Omelettes

Topics On Multimedia Technology and Reverse Engineering


Sega CD FMV VQ Analysis

July 20th, 2007 by Multimedia Mike

I have amassed quite a collection of Sega CD titles over my years of multimedia hacking. Since it was an early CD-based console, I reasoned that at least some of the games would contain full motion video (FMV). In fact, essentially all Sega CD games fall into one of the following 2 categories:

  1. Standard 16-bit Sega Genesis-type games that were enhanced by a Red Book CD audio soundtrack
  2. Games that were driven entirely by very low-quality FMV

Mad Dog McCree (Sega CD version) -- Mayor's daughter
Screenshot of Mad Dog McCree for the Sega CD, an FMV-driven FPS

Many Sega CD games, particularly those published by Sega itself, contain many large files with the extension .sga. I have never made much headway on understanding any of these files, save for the fact that many of them use sign/magnitude 8-bit PCM audio. As for the video codec, “Cinepak” or “Cinepak for Sega” is often thrown around. I can certify that it is not the stock Cinepak data commonly seen in the early FMV era. Though perhaps the Sega CD console was the proving ground for later Cinepak technologies. A lot of Sega CD FAQs around the internet were apparently plagiarized from each other, which must have originally been plagiarized from Sega marketing material because they all shallowly list one of the system’s graphical capabilities as “Advanced compression scheme.”

Per my understanding, Sega CD games had access to the same graphical capabilities as the underlying Genesis console. Marketing literature and FAQs claim that there were some extended capabilities. But I believe that the FMV must have been restricted to what the Genesis unit could possibly achieve. The Genesis has tile-based graphics, just like many consoles of the period. If you want to do FMV, you are pretty much restricted to a vector quantization compression scheme.

When I started playing Sega CD games for my Gaming Pathology experiment and capturing FMV screenshots with Gens, I recognized an opportunity for testing theories about the underlying coding scheme. My fundamental hypothesis is that these games transmit palettes, vector codebooks and vector maps.

Sherlock Holmes: Consulting Detective (Sega CD)
Sherlock Holmes: Consulting Detective for the Sega CD, an FMV-driven detective mystery

Relevant Sega CD specs at a glance (based on this document):

  • Single-speed CD-ROM drive, i.e., 150 kbytes/second transfer rate
  • Hardware for playing sign-magnitude 8-bit PCM audio (apparently)
  • Tile-based graphics hardware
  • Each tile is 8×8 pixels
  • Each constituent pixel in a tile is 4 bits large, which means that each tile can contain 16 unique colors
  • Each tile has a control word that controls such features as horizontal and vertical mirroring and palette– there are 4 palettes to choose from. Further, the control word allocates 11 bits for specifying a tile which means that the 64K of video RAM can hold up to 2048 tiles.

Based on some quick calculations, it seems plausible that a Sega CD could encode quarter-screen FMV without any compression whatsoever (though 16-color dithering must be performed on each 8×8 block and the screen is restricted to a palette of 64 total colors out of 512 possible).

The bit budget allows for 150,000 bytes/second. To get the audio out of the way, 8000 bytes are used each second (8-bit audio at 8000 Hz).

Ground Zero Texas (Sega CD)
Ground Zero Texas, blasting an alien cleverly disguised as a human (thus saving on alien effects during game production)

The Sega Genesis unit has a resolution of 320×224. Assuming a video resolution of 160×120, the video would be comprised of 300 8×8 vectors. Encoded raw, each vector is essentially comprised of 34 bytes (64 pixels * 4 bits/pixel * 1 byte/8 bits) + 2 tile bytes. The 2 tile bytes specify vector and palette. Thus, it would only require 10200 bytes to encode one frame of 160×120 video using this scheme. We should account for a new palette with each frame. 4 palettes, 16 colors each, 2 bytes for each color (though the palette is only 9 bits in resolution) works out to 128 bytes for the palette. 10328 bytes/frame.

(10328 video bytes/frame * 10 frames/second) + 8000 audio bytes/second = 111280 total bytes/second, well within budget. With that, the developer could go wild and upgrade the audio to 16 kHz and still have room to spare in the budget. Since this is the single-speed data rate, that implies that a disc could store up to 74 minutes of this type of data. However, various spec sheets and FAQs claim that the unit used 500 MB CD-ROMs that could hold 62 minutes of audio.

Naturally, there are some trade-offs that could be made to gain some more frames per second or higher resolution. For example, if restricting to a codebook of 128 vectors and 32 colors, only 1 byte would be required to represent each of the 300 vectors (7 bits for the tile number and 1 bit to select one of the 2 allowed 16-color palettes). 128 vectors * 32 bytes/vector + 300 tiling bytes + 128 palette bytes = 4524 video bytes/frame.

This is important research. Such guesswork could eventually yield clues for reverse engineering Sega CD FMV formats. How else can the world hope to preserve the legacy of such seminal interactive movie classics as Night Trap?

Posted in Game Hacking, Reverse Engineering, Vector Quantization | 6 Comments »

6 Responses

  1. Jonathan Wilson Says: contains some stuff related to this compression (whether its legal to use or not I do not know)

  2. David Says:

    Sent you an email

  3. Multimedia Mike Says:

    @David: Got it.

    @Jonathan: Thanks for the info. Come to think of it, someone once emailed me those Cinepak tech notes. I didn’t know what to make of them at the time but now things are a bit more clear (they make reference to character maps, palettes, tiles, and such).

    About legality, I’m quite confident that this manual falls squarely into the category of, “No one gives a rip anymore.” :-)

  4. Vitor Says: looks to have a decoder…

  5. Multimedia Mike Says:

    Nice find, Vitor. Goes to show, once more, to search exhaustively before embarking on an RE mission. I’m glad I maintain this blog and have a audience of diligent researchers. Thanks.

  6. David Says:

    Yeah thats my decoder :P (Although its been quite a while since I updated that page)

    I sent an email to Mike explaining that I want to add to ffmpeg, but need a prod in the right direction.