Video Coding Puzzle

Hi,
	Since I know you all love a good coding puzzle involving
multimedia technology, chew on this:

	Mario Brito has reverse engineered the multimedia tech used in the
PC series of Wing Commander games. His movie player app is here:

  http://www.wcrevival.de/hcl/movie_player.html

We are hoping to form a clearer expression of some of the decoding
algorithms before releasing the source code. What follows is a description
of a peculiar function that almost seems to have some DCT-like properties.
See if you can shed any light on the problem.

	The technology targets a Pentium 120 MHz CPU as a nominal
platform. Is it possible for this platform to decode DCT-type data in
real-time if the resolution is low enough? These games liked to use
resolutions around 320x165.

	Thanks...
--
	-Mike Melanson



---------- Forwarded message ----------
Date: Fri, 09 Jul 2004 02:35:15 +0100
From: Mario Brito <[email protected]>
To: Mike Melanson <[email protected]>
Subject: Re: Getting the Xan API right

>         I can't seem to find that code example you sent me. It was
> somewhere around January 22. Could you resend it?

Sure thing, here is the function i mentioned:

void crazy_float_stuff(int * t_int)
{
// set up floating point constants first
double da, db;
float fc1, fc2, fc3, fc4;
int ifc1 = 0x3fa73d75;
int ifc2 = 0x3f0a8bd4;
int ifc3 = 0x3ec3cf15;
int ifc4 = 0x59c00000;
memcpy (&fc1, &ifc1, 4);
memcpy (&fc2, &ifc2, 4);
memcpy (&fc3, &ifc3, 4);
memcpy (&fc4, &ifc4, 4);

da = t_int[0] * fc2 + (t_int[1] + t_int[0]) * fc3 + fc4;
db = t_int[1] * fc1 - (t_int[1] + t_int[0]) * fc3 + fc4;

memcpy (t_int, &da, 8);
memcpy (t_int+2, &db, 8);
}

While the code is unquestionably messy, i assure you this code does what it's
supposed to do. In fact it's part of my reconstruction of the WVE video decoder and
is being used on my movie player to play FMV from Wing Commander Prophecy. Something
weird i noticed about the floating point constants used in there:

0x3fa73d75 -> 1.306563
0x3f0a8bd4 -> 0.541196
0x3ec3cf15 -> 0.382439
0x59c00000 -> 6755399441055744.000000

however i had trouble defining these numbers as a float, since

1.306563 -> 0x3fa73d75
0.541196 -> 0x3f0a8bd2                <---------------
0.382439 -> 0x3ec3cf0b                 <---------------
6755399441055744.000000 -> 0x59c00000

which give a wrong result. This made me define those constants as hexadecimal values
instead of floating point numbers just to be on the safe side (although this could be
a quirk from Visual C++, i have yet to verify this)

>From what i have on my notes, the decoder seems to operate on 16x16 blocks, each of
which is apparently divided in 4 8x8 blocks. There's a piece of the decoder that does
something like:

for (it = 0; it < 4; it ++)
{
Function0 (compr, *bitcounter, eax);

        for (i = 0, dest = temp+0x40, source = temp; i < 8; i ++, source += 8, dest
++)
                functionA (dest, source);

        for (i = 0, dest = dest_arr[it], source = temp+0x40; i < 8; i ++, source +=
9,
dest += 16)
                functionB (dest, source);
}

FunctionA does, basically:
if (source[1..7] == 0)
{
sets
dest[0]
dest[9]
dest[18]
dest[27]
dest[36]
dest[45]
dest[54]
dest[63]
to
source[0]
}
else
{
computes something that involves that crazy float function to the same dest
positions as above
}

FunctionB on the other hand computes something that writes dest[0..7] based on
the previous calculations (there seems to be an extra column, unused).

Both FunctionA and FunctionB call the crazy function above.

After that cycle the decoder continues with a similar cycle of just 2 iterations. I
get the impression the first 4 iterations decompress the Y component for the 16x16
block, while the last 2 decompress the Cr and Cb components.

Function0 seems to do some processing relying on lookup tables (looks like an
entropic decoder of some kind). I didn't dig enough into the algorithm to go beyond
speculation, but something caught my eye here... before writing to the destination
buffer there's always a multiplication based on the position on the buffer:

 val *= table[i];
 dest[i] = val;

which reminds me of a dequantization step. This made me think that this strange
function could be part of an IDCT... but as you pointed out back then, it'd be
unusual, since the game was created with a Pentium 120 as the target machine. Well,
this is pretty much where i am now...

Anyway, thanks for listening :-) Let me know if you have any insight.

Take care,

Mario Brito



-------------------------------------------------------
This SF.Net email sponsored by Black Hat Briefings & Training.
Attend Black Hat Briefings & Training, Las Vegas July 24-29 - 
digital self defense, top technical experts, no vendor pitches, 
unmatched networking opportunities. Visit www.blackhat.com