Recherche avancée

Sur d’autres sites (2896)

• The 11th Hour RoQ Variation

  12 avril 2012, par Multimedia Mike — Game Hacking, dreamroq, Reverse Engineering, roq, Vector Quantization

  I have been looking at the RoQ file format almost as long as I have been doing practical multimedia hacking. However, I have never figured out how the RoQ format works on The 11th Hour, which was the game for which the RoQ format was initially developed. When I procured the game years ago, I remember finding what appeared to be RoQ files and shoving them through the open source decoders but not getting the right images out.

  I decided to dust off that old copy of The 11th Hour and have another go at it.

  
  
  

  Baseline
  The game consists of 4 CD-ROMs. Each disc has a media/ directory that has a series of files bearing the extension .gjd, likely the initials of one Graeme J. Devine. These are resource files which are merely headerless concatenations of other files. Thus, at first glance, one file might appear to be a single RoQ file. So that’s the source of some of the difficulty : Sending an apparent RoQ .gjd file through a RoQ player will often cause the program to complain when it encounters the header of another RoQ file.

  I have uploaded some samples to the usual place.

  However, even the frames that a player can decode (before encountering a file boundary within the resource file) look wrong.

  Investigating Codebooks Using dreamroq
  I wrote dreamroq last year– an independent RoQ playback library targeted towards embedded systems. I aimed it at a gjd file and quickly hit a codebook error.

  RoQ is a vector quantizer video codec that maintains a codebook of 256 2×2 pixel vectors. In the Quake III and later RoQ files, these are transported using a YUV 4:2:0 colorspace– 4 Y samples, a U sample, and a V sample to represent 4 pixels. This totals 6 bytes per vector. A RoQ codebook chunk contains a field that indicates the number of 2×2 vectors as well as the number of 4×4 vectors. The latter vectors are each comprised of 4 2×2 vectors.

  Thus, the total size of a codebook chunk ought to be (# of 2×2 vectors) * 6 + (# of 4×4 vectors) * 4.

  However, this is not the case with The 11th Hour RoQ files.

  Longer Codebooks And Mystery Colorspace
  Juggling the numbers for a few of the codebook chunks, I empirically determined that the 2×2 vectors are represented by 10 bytes instead of 6. Now I need to determine what exactly these 10 bytes represent.

  I should note that I suspect that everything else about these files lines up with successive generations of the format. For example if a file has 640×320 resolution, that amounts to 40×20 macroblocks. dreamroq iterates through 40×20 8×8 blocks and precisely exhausts the VQ bitstream. So that all looks valid. I’m just puzzled on the codebook format.

  Here is an example codebook dump :
  

  ID 0x1002, len = 0x0000014C, args = 0x1C0D
    0 : 00 00 00 00 00 00 00 00 80 80
    1 : 08 07 00 00 1F 5B 00 00 7E 81
    2 : 00 00 15 0F 00 00 40 3B 7F 84
    3 : 00 00 00 00 3A 5F 18 13 7E 84
    4 : 00 00 00 00 3B 63 1B 17 7E 85
    5 : 18 13 00 00 3C 63 00 00 7E 88
    6 : 00 00 00 00 00 00 59 3B 7F 81
    7 : 00 00 56 23 00 00 61 2B 80 80
    8 : 00 00 2F 13 00 00 79 63 81 83
    9 : 00 00 00 00 5E 3F AC 9B 7E 81
    10 : 1B 17 00 00 B6 EF 77 AB 7E 85
    11 : 2E 43 00 00 C1 F7 75 AF 7D 88
    12 : 6A AB 28 5F B6 B3 8C B3 80 8A
    13 : 86 BF 0A 03 D5 FF 3A 5F 7C 8C
    14 : 00 00 9E 6B AB 97 F5 EF 7F 80
    15 : 86 73 C8 CB B6 B7 B7 B7 85 8B
    16 : 31 17 84 6B E7 EF FF FF 7E 81
    17 : 79 AF 3B 5F FC FF E2 FF 7D 87
    18 : DC FF AE EF B3 B3 B8 B3 85 8B
    19 : EF FF F5 FF BA B7 B6 B7 88 8B
    20 : F8 FF F7 FF B3 B7 B7 B7 88 8B
    21 : FB FF FB FF B8 B3 B4 B3 85 88
    22 : F7 FF F7 FF B7 B7 B9 B7 87 8B
    23 : FD FF FE FF B9 B7 BB B7 85 8A
    24 : E4 FF B7 EF FF FF FF FF 7F 83
    25 : FF FF AC EB FF FF FC FF 7F 83
    26 : CC C7 F7 FF FF FF FF FF 7F 81
    27 : FF FF FE FF FF FF FF FF 80 80
  

  Note that 0x14C (the chunk size) = 332, 0x1C and 0x0D (the chunk arguments — count of 2×2 and 4×4 vectors, respectively) are 28 and 13. 28 * 10 + 13 * 4 = 332, so the numbers check out.

  Do you see any patterns in the codebook ? Here are some things I tried :

  • Treating the last 2 bytes as U & V and treating the first 4 as the 4 Y samples :
    
    
    
  • Treating the last 2 bytes as U & V and treating the first 8 as 4 16-bit little-endian Y samples :
    
    
    
  • Disregarding the final 2 bytes and treating the first 8 bytes as 4 RGB565 pixels (both little- and big-endian, respectively, shown here) :
    
    
    
  • Based on the type of data I’m seeing in these movies (which appears to be intended as overlays), I figured that some of these bits might indicate transparency ; here is 15-bit big-endian RGB which disregards the top bit of each pixel :
    
    
    

  These images are taken from the uploaded sample bdpuz.gjd, apparently a component of the puzzle represented in this screenshot.

  Unseen Types
  It has long been rumored that early RoQ files could contain JPEG images. I finally found one such specimen. One of the files bundled early in the uploaded fhpuz.gjd sample contains a JPEG frame. It’s a standard JFIF file and can easily be decoded after separating the bytes from the resource using ‘dd’. JPEGs serve as intraframes in the coding scheme, with successive RoQ frames moving objects on top.

  However, a new chunk type showed up as well, one identified by 0×1030. I have never encountered this type. Where could I possibly find data about this ? Fortunately, iD Games recently posted all of their open sourced games at Github. Reading through the code for their official RoQ decoder, I see that this is called a RoQ_PACKET. The name and the code behind it are both supremely unhelpful. The code is basically a no-op. The payloads of the various RoQ_PACKETs from one sample are observed to be either 8784, 14752, or 14760 bytes in length. It’s very likely that this serves the same purpose as the JPEG intraframes.

  Other Tidbits
  I read through the readme.txt on the first game disc and found this nugget :

          g)      Animations displayed normally or in SPOOKY MODE
                  SPOOKY MODE is blue-tinted grayscale with color cursors, puzzle
  
                  and game pieces.  It is the preferred display setting of the
  
                  developers at Trilobyte.  Just for fun, try out the SPOOKY
  
                  MODE.
  

  The MobyGames screenshot page has a number of screenshots labeled as being captured in spooky mode. Color tricks ?

  Meanwhile, another twist arose as I kept tweaking dreamroq to deal with more RoQ weirdness : After modifying my dreamroq code to handle these 10-byte vectors, it eventually chokes on another codebook. These codebooks happen to have 6-byte vectors again ! Fortunately, I was already working on a scheme to automatically detect which codebook is in play (plugging the numbers into a formula and seeing which vector size checks out).

• Playing Video on a Sega Dreamcast

  9 mars 2011, par Multimedia Mike — Sega Dreamcast

  Here’s an honest engineering question : If you were tasked to make compressed video play back on a Sega Dreamcast video game console, what video format would you choose ? Personally, I would choose RoQ, the format invented for The 11th Hour computer game and later used in Quake III and other games derived from the same engine. This post explains my reasoning.

  Video Background
  One of the things I wanted to do when I procured a used Sega Dreamcast back in 2001 was turn it into a set-top video playback unit. This is something that a lot of people tried to do, apparently, to varying degrees of success. Interest would wane in a few years as it became easier and easier to crack an Xbox and install XBMC. The Xbox was much better suited to playing codecs that were getting big at the time, most notably MPEG-4 part 2 video (DivX/XviD).

  The Dreamcast, while quite capable when it was released in 1999, was not very well-equipped to deal with an MPEG-type codec. I have recently learned that there are other hackers out there on the internet who are still trying to get the most out of this system. I was contacted for advice about how to make Theora perform better on the Dreamcast.
  
  Interesting thing about consoles and codecs : Since you are necessarily distributing code along with your data, you have far more freedom to use whatever codecs you want for your audio and video data. This is why Vorbis and even Theora have seen quite a bit of use in video games, "internet standards" be darned. Thus, when I realized this application had no hard and fast requirement to use Theora, and that it could use any codec that fit the platform, my mind started churning. When I was programming the DC 10 years ago, I didn’t have access to the same wealth of multimedia knowledge that is currently available.

  Requirements Gathering
  What do we need here ?

  • Codec needs to run on the Sega Dreamcast ; this eliminates codecs for which only binary decoder implementations are available
  • Must decode 320x240 video at 30 fps ; higher resolutions up to 640x480 would be desirable
  • Must deliver decent quality at 12X optical read speeds (DC drive speed)
  • There must be some decent, preferably free, encoder readily available ; speed of encoding, however, is not important ; i.e., "take as long as you need, encoder"

  Theora was the go-to codec because it’s just commonly known as "the free, open source video codec". But clearly it’s not suitable for, well... any purpose, really (sorry, easy target ; OW ! stop throwing things !). VP8/WebM — Theora’s heir apparent — would not qualify either, as my prior experiments have already demonstrated.

  Candidates
  What did the big boys use for video on the Dreamcast ? A lot of games relied on CRI’s Sofdec middleware which was MPEG-1 video and a custom ADPCM format. I don’t know if I have ever seen DC games that used MPEG-1 video at a higher resolution than 320x240 (though I have not searched exhaustively). The fact that CRI used a custom ADPCM format for this application may indicate that there wasn’t enough CPU power left over to decode a perceptual, transform-based audio codec alongside the 320x240 video.

  A few other DC games used 4X Technologies’ 4XM format. The most notable licensee was Alone in the Dark : The New Nightmare (DC version only ; PC version used Bink). This codec was DCT-based but incorporated 16-bit RGB colorspace into its design, presumably to optimize for applications like game consoles that couldn’t directly handle planar YUV. AITD:TNN’s videos were 640x360, a marked improvement over the typical Sofdec fare. I was about to write off 4XM as a contender due to lack of encoder, but the encoding tools are preserved on our samples site. A few other issues, though : The FFmpeg decoder doesn’t seem to work correctly as of this writing (and nobody has noticed yet, even though it’s tested via FATE).

  What ideas do I have ? Right off the bat, I’m thinking vector quantizer (VQ). Vector quantizers are notoriously slow to compress but are blazingly fast to decompress which is why they were popular in the early days of video compression. First, there’s Cinepak. I fear that might be too simple for this application. Plus, I don’t know if existing (binary-only) compressors are very decent. It seems that they only ever had to handle small videos and I’ve heard that they can really fall over if anything more is demanded of them.

  Sorenson Video 1 is another contender. FFmpeg has an encoder (which some allege is better than Sorenson’s original compressor). However, I fear that the wonky algorithm and colorspace might not mesh well with the Dreamcast.

  My thinking quickly converged on RoQ. This was designed to run fullscreen (640x480) video on i486-class hardware. While RoQ fundamentally operates in a YUV colorspace, it’s trivial to convert it to any other colorspace during decoding and the image will be rendered in that colorspace. Plus, there are open source encoders available for the format (namely, several versions of Eric Lasota’s Switchblade encoder, one of which lives natively in FFmpeg), as well as the original proprietary encoder.

  Which Library ?
  There are several code choices here : FFmpeg (LGPL), Switchblade (GPL), and the original Quake 3 source code (GPL). There is one more option that I think might be easiest, which is the decoder Dr. Tim created when he reverse engineered the format in the first place. That has a very liberal "do whatever you like, but be nice and give me credit" license (probably qualifies as BSD).

  This code is no longer at its original home but the Wayback Machine still had a copy, which I have now mirrored (idroq.tar.gz).

  Adaptation
  Dr. Tim’s code still compiles and runs great on Linux (64-bit !) with SDL output. I would like to get it ported to the Dreamcast using the same SDL output, which KallistiOS supports. Then, there is the matter of fixing the longstanding chroma bug in the original sample decoder (described here). The decoder also needs to be modified to natively render RGB565 data, as that will work best with the DC’s graphics hardware.

  After making the code work, I want to profile it and test whether it can handle full-frame 640x480 playback at 30 frames/second. I will need to contrive a sample to achieve this.

  Unfortunately, things went off the rails pretty quickly when I tried to get the RoQ decoder ported to DC/KOS. It looks like there’s a bug in KallistiOS’s minimalistic standard C library, or at least a discrepancy with my desktop Linux system. When you read to the end of a file and then seek backwards to someplace that isn’t the end, is the file still in EOF state ?

  According to my Linux desktop :

  open file ;          feof() = 0
  seek to end ;        feof() = 0
  read one more byte ; feof() = 1
  seek back to start ; feof() = 0
  

  According to KallistiOS :

  open file ;          feof() = 0
  seek to end ;        feof() = 0
  read one more byte ; feof() = 1
  seek back to start ; feof() = 1
  

  Here’s the seek-test.c program I used to test this issue :

  PLAIN TEXT

  C :

  1. #include <stdio .h>
  2.  
  3. int main()
  4. {
  5.   FILE *f ;
  6.   unsigned char byte ;
  7.  
  8.   f = fopen("seek_test.c", "r") ;
  9.   printf("open file ;     feof() = %d\n", feof(f)) ;
  10.   fseek(f, 0, SEEK_END) ;
  11.   printf("seek to end ;    feof() = %d\n", feof(f)) ;
  12.   fread(&byte, 1, 1, f) ;
  13.   printf("read one more byte ; feof() = %d\n", feof(f)) ;
  14.   fseek(f, 0, SEEK_SET) ;
  15.   printf("seek back to start ; feof() = %d\n", feof(f)) ;
  16.   fclose(f) ;
  17.  
  18.   return 0 ;
  19. }

  EOF
  Speaking of EOF, I’m about done for this evening.

  What codec would you select for this task, given the requirements involved ?

• Heroic Defender of the Stack

  27 janvier 2011, par Multimedia Mike — Programming

  Problem Statement

  I have been investigating stack smashing and countermeasures (stack smashing prevention, or SSP). Briefly, stack smashing occurs when a function allocates a static array on the stack and writes past the end of it, onto other local variables and eventually onto other function stack frames. When it comes time to return from the function, the return address has been corrupted and the program ends up some place it really shouldn’t. In the best case, the program just crashes ; in the worst case, a malicious party crafts code to exploit this malfunction.

  Further, debugging such a problem is especially obnoxious because by the time the program has crashed, it has already trashed any record (on the stack) of how it got into the errant state.

  Preventative Countermeasure

  GCC has had SSP since version 4.1. The computer inserts SSP as additional code when the -fstack-protector command line switch is specified. Implementation-wise, SSP basically inserts a special value (the literature refers to this as the ’canary’ as in "canary in the coalmine") at the top of the stack frame when entering the function, and code before leaving the function to make sure the canary didn’t get stepped on. If something happens to the canary, the program is immediately aborted with a message to stderr about what happened. Further, gcc’s man page on my Ubuntu machine proudly trumpets that this functionality is enabled per default ever since Ubuntu 6.10.

  And that’s really all there is to it. Your code is safe from stack smashing by default. Or so the hand-wavy documentation would have you believe.

  Not exactly

  Exercising the SSP

  I wanted to see the SSP in action to make sure it was a real thing. So I wrote some code that smashes the stack in pretty brazen ways so that I could reasonably expect to trigger the SSP (see later in this post for the code). Here’s what I learned that wasn’t in any documentation :

  SSP is only emitted for functions that have static arrays of 8-bit data (i.e., [unsigned] chars). If you have static arrays of other data types (like, say, 32-bit ints), those are still fair game for stack smashing.

  Evaluating the security vs. speed/code size trade-offs, it makes sense that the compiler wouldn’t apply this protection everywhere (I can only muse about how my optimization-obsessive multimedia hacking colleagues would absolute freak out if this code were unilaterally added to all functions). So why are only static char arrays deemed to be "vulnerable objects" (the wording that the gcc man page uses) ? A security hacking colleague suggested that this is probably due to the fact that the kind of data which poses the highest risk is arrays of 8-bit input data from, e.g., network sources.

  The gcc man page also lists an option -fstack-protector-all that is supposed to protect all functions. The man page’s definition of "all functions" perhaps differs from my own since invoking the option does not have differ in result from plain, vanilla -fstack-protector.

  The Valgrind Connection

  "Memory trouble ? Run Valgrind !" That may as well be Valgrind’s marketing slogan. Indeed, it’s the go-to utility for finding troublesome memory-related problems and has saved me on a number of occasions. However, it must be noted that it is useless for debugging this type of problem. If you understand how Valgrind works, this makes perfect sense. Valgrind operates by watching all memory accesses and ensuring that the program is only accessing memory to which it has privileges. In the stack smashing scenario, the program is fully allowed to write to that stack space ; after all, the program recently, legitimately pushed that return value onto the stack when calling the errant, stack smashing function.

  Valgrind embodies a suite of tools. My idea for an addition to this suite would be a mechanism which tracks return values every time a call instruction is encountered. The tool could track the return values in a separate stack data structure, though this might have some thorny consequences for some more unusual program flows. Instead, it might track them in some kind of hash/dictionary data structure and warn the programmer whenever a ’ret’ instruction is returning to an address that isn’t in the dictionary.

  Simple Stack Smashing Code

  Here’s the code I wrote to test exactly how SSP gets invoked in gcc. Compile with ’gcc -g -O0 -Wall -fstack-protector-all -Wstack-protector stack-fun.c -o stack-fun’.

  stack-fun.c :

  PLAIN TEXT

  C :

  1. /* keep outside of the stack frame */
  2. static int i ;
  3.  
  4. void stack_smasher32(void)
  5. {
  6.  int buffer32[8] ;
  7.  // uncomment this array and compile without optimizations
  8.  // in order to force this function to compile with SSP
  9. // char buffer_to_trigger_ssp[8] ;
  10.  
  11.  for (i = 0 ; i <50 ; i++)
  12.   buffer32[i] = 0xA5 ;
  13. }
  14.  
  15. void stack_smasher8(void)
  16. {
  17.  char buffer8[8] ;
  18.  for (i = 0 ; i <50 ; i++)
  19.   buffer8[i] = 0xA5 ;
  20. }
  21.  
  22. int main()
  23. {
  24. // stack_smasher8() ;
  25.  stack_smasher32() ;
  26.  return 0 ;
  27. }

  The above incarnation should just produce the traditional "Segmentation fault". However, uncommenting and executing stack_smasher8() in favor of stack_smasher32() should result in "*** stack smashing detected *** : ./stack-fun terminated", followed by the venerable "Segmentation fault".

  As indicated in the comments for stack_smasher32(), it’s possible to trick the compiler into emitting SSP for a function by inserting an array of at least 8 bytes (any less and SSP won’t emit, as documented, unless gcc’s ssp-buffer-size parameter is tweaked). This has to be compiled with no optimization at all (-O0) or else the compiler will (quite justifiably) optimize away the unused buffer and omit SSP.

  For reference, I ran my tests on Ubuntu 10.04.1 with gcc 4.4.3 compiling the code for both x86_32 and x86_64.