Breaking Eggs And Making Omelettes

Topics On Multimedia Technology and Reverse Engineering


HD I-movie

February 21st, 2007 by Multimedia Mike

Today’s IMDb Studio Briefing reports that when Disney’s Pirates of the Caribbean: Dead Man’s Chest is released, it will contain a live-action version of the Liar’s Dice game filmed in high definition. Do you think we can qualify this as an HD interactive movie?

Posted in Multimedia PressWatch | Comments Off on HD I-movie

The Interpreter

February 17th, 2007 by Multimedia Mike

Somewhere along the line I got sucked into this multimedia hacking field as an extracurricular activity. There are abundant specializations in the computer field that one can take up as a hobby. But other specialties that I have always been curious about got sidelined, such as 3D graphics and artificial intelligence — 2 things I have always wanted to study more carefully.

Yet another topic is that of compiler and interpreter theory. There were compiler construction elective courses in school but I honestly didn’t care back then. Let the compiler do its job; I have higher level tasks. Naturally, if I’m suddenly interested in compiler theory, there must a reason for it.

Certain computer games use (what are probably) custom scripting languages to describe the game flow and character interactions. When I study these plaintext scripting files, I find myself wondering what would be involved in writing an interpreter for such a language. One such game is Clue Chronicles: Fatal Illusion, based on the popular Clue board game (a.k.a. Cluedo).

Clue Chronicles cover

The scripting language appears to be mildly object oriented with C++-type comments (‘//’) and reliant upon a number of implicit library functions. Principally, it defines scenes with graphic backdrops and the transparent Smacker multimedia files that are to be played as animations, as well as the subtitle text that should be overlaid. At the conclusion of certain interactions, methods are called that, e.g., add an item to your inventory or a clue to your notepad.

From my computer science studies, I seem to recall something about tools named Lex and Yacc along with the GNU variants, Flex and Bison. These are supposed to be suited for the task of writing compilers and interpreters in some cases. Here is a page that discusses writing a simple interpreter using Lex and Yacc.

Here is a sample of the language:

  // ## Common Scripts ##

  //  Scarlet says, "Sorry...I don't know..."
  sc1105 = SequentialScript(Autoplay, Looping, Scripts
      SequentialScript(Autoplay, Looping, Scripts
          Looping(false), NoSkip(false),
          Transparent(0, 255, 0)
        Caption(Text("Scarlet: Sorry...I don't know anything about that.")),
        Caption(Text(" ")),
    Caption(Text(" ")),
    Caption(Text(" ")),

And here is the full file (originally titled sc1.ini), which is one of many files used to drive the game: clue-chronicles-scarlet-1.txt

I’m just wondering if anyone reading this blog has the first clue about how one would go about writing an interpreter for this little language? This is not a field to which I have had extensive exposure.

Posted in Game Hacking | 5 Comments »

Breaking Eggs And Making Omelettes: The Paper

February 16th, 2007 by Multimedia Mike

I presented a paper at LinuxTag in 2005, nearly 2 years ago. I can’t believe I never got around to posting it. Here it is in PDF format, named after this blog: “Breaking Eggs and Making Omelettes: Intelligence Gathering For Open Source Software Development.” It’s a pretty high level overview of the RE craft written mostly for those who have not had much exposure.

linuxtag-2005-re-paper.pdf (~100 KB)

Posted in Reverse Engineering | Comments Off on Breaking Eggs And Making Omelettes: The Paper

ASM: What It Can Do For You

February 14th, 2007 by Multimedia Mike

I’ve had my nose deep in the multimedia mess for so long that I forget that people outside the field might not understand some of the ideas that those of us “skilled in the art” believe are intuitive. One such concept is that of manually programming in assembly language (colloquially referred to as ASM).

“But no one codes in ASM these days,” they exclaim. “Compilers are smart enough to do all the optimization you will ever need.” First, I would like to state that I place very little faith in compilers to always do the right thing, particularly during the optimization phase, but that’s neither here nor there. Allow me to explain why manual ASM programming is often done during multimedia programming.

First, it’s true: very few people write actual, usable applications purely in ASM. Where ASM comes in handy is in optimization in the form of invoking series of special instructions in ways that compilers wouldn’t be able to leverage.

That’s the short answer about why people still manually code some program components in ASM these days. The rest of this post will be devoted to explaining exactly how certain special instructions are useful in multimedia applications.

A lot of modern consumer-level CPUs (x86_32, x86_64, PPC) have special categories of instructions that are designed to perform the same operation on lots of data bits, all at the same time. Remember when Intel rolled out the Pentium MMX instructions? That’s what those were good for– performing lots of the same operation in parallel. Since then, there have been various upgrades to the concept, and from various other manufacturers (and some branching out, such as special floating point operations as well as cache control instructions). But the main idea that is useful in multimedia programming remains the same and it’s called “single instruction, multiple data” or SIMD; you execute one instruction and it operates on multiple data in parallel.

SIMD instructions are invaluable in multimedia programming because processing multimedia typically involves performing the same operation on every data element in a huge buffer. If you can do the same operation on 2 data elements, or 4, or 8, or 16 at a time, rather than just one at a time, that’s great.

Here’s a more tangible example: You have a large array of bytes. You have to add the quantity 5 to each byte. With the traditional load-do_math-store sequence, this looks like:

  load next data byte into reg1
  reg1 = reg1 + 5
  store reg1 back to memory
  [repeat for each byte]

Even if you have a 32-bit CPU, you can’t effectively load 4 data bytes at a time and add 0x05050505 because if any individual sums exceed 255, the carry will spill into the next most significant byte. However, the Intel MMX provides 8 64-bit registers (really just the same as the FP regs, but that’s trivia). Depending on the SIMD instruction issued, a register may be treated as 8 8-bit elements, 4 16-bit elements, or 2 32-bit elements. Check out the parallel approach for solving the previous problem:

  init mm1 (mmx register) as 0x0505050505050505
  load next 8 bytes into mm2
  mm2 = mm2 + mm1, treat data as 8 unsigned bytes
  store 8 bytes back to memory
  [repeat for each block of 8 bytes]

Powerful, huh? You’re not performing one addition at a time; rather, there are 8 happening in parallel. That’s something that a compiler generally can’t pick up on and optimize for you behind the scene (though I’ve heard legends that Intel’s compiler can perform such feats, which I would like to see). But there’s more:

  • Intel’s SSE2 and the PowerPC’s AltiVec SIMD facilities provide 128-bit registers. Thus, this same process can operate on 16 bytes in parallel.
  • The data doesn’t have to be treated as unsigned bytes; you can also ask it to be treated as signed bytes, or signed or unsigned words or doublewords. It all depends on the instruction issued

There’s also saturation. This goes by many names such as clamping and clipping. In the above example, if we want to make sure that none of the bytes go above 255 (and wrap around to 0 as a result), we must perform this tedious process for each byte:

  next_byte = *buffer;
  if (next_byte + 5 > 255)
    next_byte = 255;
    next_byte += 5;
  *buffer++ = next_byte;

Not so with SIMD instructions which typically have saturation modes. When you invoke the saturation variant of the add instruction, it automatically makes sure that none of the data elements go above the limit (255 for an unsigned byte or 127 for a signed byte).

What would be the practical application of adding a constant value to each byte in a buffer? This is one of the earliest examples I found related to SIMD programming. The example pertained to brightening the intensity information of an image. This is particularly pertinent to me since I remember working briefly with a image manipulation program that did not take saturation into account when brightening an image. It simply wrapped the values right around to 0 and kept adding. As demonstrated, using hand-coded SIMD ASM in this case would have yielded both correct and fast results.

What about applications in multimedia video codecs? The parallel saturated addition happens to come in handy in such situations. There are many mainstream video codecs which operate on 8×8 blocks of samples. Further, they have to decode one block and then add that block to a block which occurs in the previous frame. This turns out to be a fantastic use for parallel addition with saturation.

These are but a few simple applications for hand-coded ASM code. I may write more on the matter, if I am so inspired.

Posted in Programming | 4 Comments »

« Previous Entries Next Entries »