Monthly Archives: April 2011

Creating A Lossless SMC Encoder

Look, I can’t explain how or why I come up with this stuff. For some reason, I thought it would be interesting to write a new encoder for the Apple SMC video codec. I can’t even remember why. I just sat down the other day, started writing, and now I have a lossless SMC encoder that I’m not sure what to do with. Maybe this is to be my new thing— writing encoders for marginal multimedia formats.

SMC is a vector quantizer (a lossy method) but I decided to attack it from the angle of lossless encoding. A.k.a. Apple Graphics Codec, SMC operates on 4×4 blocks in an 8-bit paletted colorspace. Each 4×4 block can be encoded with 1, 2, 4, 8, or 16 colors. Blocks can also be skipped (copied from previous frame) or copied from blocks rendered immediately prior within the same frame.

Step 1: Validating Infrastructure
The goal of this step is to encode the most braindead SMC frame possible and see if FFmpeg/libav’s QuickTime muxer can create a valid file. I think the simplest frame would be one in which each vector is encoded with the single-color mode, starting with color 0 and incrementing through the palette.

Status: Successful. The only ‘trick’ was to set avctx->bits_per_coded_sample to 8. (For fun, this can also be set to 40 (8 | 0x20) to specify a grayscale palette.)

Step 2: Preprocessing
The video frames will arrive at the encoder as 32-bit RGB. These will need to be converted to a paletted colorspace before encoding. I don’t want to use FFmpeg’s default dithering approach as this will result in a substantial loss of quality as described in this post. I would rather maintain a palette built from observed colors throughout successive frames. If the total number of unique observed colors ever exceeds 256, error out.

That’s what I would like to do. However, I noticed that FFmpeg/libav’s QuickTime muxer has never taken into account the possibility of encoding palettes. The path of least resistance in this case is to dither the input to match QuickTime’s default 8-bit palette (if a paletted QuickTime file does not specify a palette, a default 1-, 2-, 4-, or 8-bit palette is selected).

Status: Successful, if slow. I definitely need to optimize this step later.

Step 3: Most Naive Encoding
The most basic encoding is to “encode” each block as a 16-color block. This will actually result in a slightly larger frame size than a raw encoding since each 4×4 block will be prepended by a byte opcode (0xE0 in this case) to indicate encoding mode. This should demonstrate that the encoder is functioning at the most basic level.

Status: Successful. Try not to laugh too hard at the Big Buck Bunny dithered to an 8-bit palette:

Step 4: Better Representation Continue reading

Removing GRUB

I have a Windows/Linux dual-booting computer that I don’t want to be dual boot anymore– the Linux part needs to go. Thus, the GRUB bootloader needs to be removed so that Windows boots normally. I found lots of tips around the internet about how to do this. Of course, none of them worked. So I must add to the general body of knowledge.

I found tips that described how to manually remove GRUB via Linux– by using 'dd' to overwrite no more than 446 sectors of the boot disk with zeros. This strikes me as a dangerous and unstable proposition. It also wasn’t an option since I had already opted to reformat the formerly Linux partition via the Windows CD-ROM before I endeavored to remove the bootloader.

Other forums and sites mentioned a combination of utilities found on the Windows CD-ROM including FIXBOOT, FIXMBR, and BOOTCFG. While these programs performed some functions, they didn’t achieve the desired effect– to make Windows boot automatically.

New idea: Repartition the disk such that there is a (relatively) tiny extra partition. Then, well… reinstall Linux. I used a 4 GB partition and Ubuntu 10.10 and let it run its course which ended with installing GRUB… again.

Seems roundabout– installing Linux specifically to boot into Windows. But it works.

Reverse Engineering Radius VideoVision

I was called upon to help reverse engineer an old video codec called VideoVision (FourCC: PGVV), ostensibly from a company named Radius. I’m not sure of the details exactly but I think a game developer has a bunch of original FMV data from an old game locked up in this format. The name of the codec sounded familiar. Indeed, we have had a sample in the repository since 2002. Alex B. did some wiki work on the codec some years ago. The wiki mentions that there existed a tool to transcode PGVV data into MJPEG-B data, which is already known and supported by FFmpeg.

The Software
My contacts were able to point me to some software, now safely archived in the PGVV samples directory. There is StudioPlayer2.6.2.sit.hqx which is supposed to be a QuickTime component for working with PGVV data. I can’t even remember how to deal with .sit or .hqx data. Then there is which is the tool that transcodes to MJPEG-B.

Disassembling for Reverse Engineering
Since I could actually unpack the transcoder, I set my sights on that. Unpacking the archive sets up a directory structure for a component. There is a binary called RadiusVVTranscoder under RadiusVVTranscoder.component/Contents/MacOS/. Basic deadlisting disassembly is performed via ‘otool’ as shown:

  otool -tV RadiusVVTranscoder | c++filt

This results in a deadlisting of both PowerPC and 32-bit x86 code, as the binary is a “fat” Mac OS X binary designed to run on both architectures. The command line also demangles C++ function signatures which gives useful insight into the parameters passed to a function.

Pretty Pictures
The binary had a lot of descriptive symbols. As a basis for reverse engineering, I constructed call graphs using these symbols. Here are the 2 most relevant portions (click for larger images).

The codec initialization generates Huffman tables relevant to the codec:

The main decode function calls AddMJPGFrame which apparently does the heavy lifting for the transcode process:

Based on this tree, I’m guessing that luma blocks can be losslessly transcoded (perhaps with different Huffman tables) which chroma blocks may rely on a different quantization method.

Assembly Constructs
I started looking at the instructions (the x86 ones, of course). The binary uses a calling convention I haven’t seen before, at least not for the x86: Rather than pushing function arguments onto the stack, the code manually subtracts, e.g., 12 from the ESP register, loads 3 32-bit arguments into memory relative to ESP, and then proceeds with the function call.

I’m also a little unclear on constructs such as “call ___i686.get_pc_thunk.bx” seen throughout relevant functions such as MakeRadiusQuantizationTables().

I’m just presenting what I have so far in case anyone else wants to try their hand.