Recherche avancée

Sur d’autres sites (4345)

• 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).

• CD-R Read Speed Experiments

  21 mai 2011, par Multimedia Mike — Science Projects, Sega Dreamcast

  I want to know how fast I can really read data from a CD-R. Pursuant to my previous musings on this subject, I was informed that it is inadequate to profile reading just any file from a CD-R since data might be read faster or slower depending on whether the data is closer to the inside or the outside of the disc.

  Conclusion / Executive Summary
  It is 100% true that reading data from the outside of a CD-R is faster than reading data from the inside. Read on if you care to know the details of how I arrived at this conclusion, and to find out just how much speed advantage there is to reading from the outside rather than the inside.

  Science Project Outline

  • Create some sample CD-Rs with various properties
  • Get a variety of optical drives
  • Write a custom program that profiles the read speed

  Creating The Test Media
  It’s my understanding that not all CD-Rs are created equal. Fortunately, I have 3 spindles of media handy : Some plain-looking Memorex discs, some rather flamboyant Maxell discs, and those 80mm TDK discs :

  
  
  

  My approach for burning is to create a single file to be burned into a standard ISO-9660 filesystem. The size of the file will be the advertised length of the CD-R minus 1 megabyte for overhead— so, 699 MB for the 120mm discs, 209 MB for the 80mm disc. The file will contain a repeating sequence of 0..0xFF bytes.

  Profiling
  I don’t want to leave this to the vagaries of any filesystem handling layer so I will conduct this experiment at the sector level. Profiling program outline :

  • Read the CD-ROM TOC and get the number of sectors that comprise the data track
  • Profile reading the first 20 MB of sectors
  • Profile reading 20 MB of sectors in the middle of the track
  • Profile reading the last 20 MB of sectors

  Unfortunately, I couldn’t figure out the raw sector reading on modern Linux incarnations (which is annoying since I remember it being pretty straightforward years ago). So I left it to the filesystem after all. New algorithm :

  • Open the single, large file on the CD-R and query the file length
  • Profile reading the first 20 MB of data, 512 kbytes at a time
  • Profile reading 20 MB of sectors in the middle of the track (starting from filesize / 2 - 10 MB), 512 kbytes at a time
  • Profile reading the last 20 MB of sectors (starting from filesize - 20MB), 512 kbytes at a time

  Empirical Data
  I tested the program in Linux using an LG Slim external multi-drive (seen at the top of the pile in this post) and one of my Sega Dreamcast units. I gathered the median value of 3 runs for each area (inner, middle, and outer). I also conducted a buffer flush in between Linux runs (as root : 'sync; echo 3 > /proc/sys/vm/drop_caches').

  LG Slim external multi-drive (reading from inner, middle, and outer areas in kbytes/sec) :

  • TDK-80mm : 721, 897, 1048
  • Memorex-120mm : 1601, 2805, 3623
  • Maxell-120mm : 1660, 2806, 3624

  So the 120mm discs can range from about 10.5X all the way up to a full 24X on this drive. For whatever reason, the 80mm disc fares a bit worse — even at the inner track — with a range of 4.8X - 7X.

  Sega Dreamcast (reading from inner, middle, and outer areas in kbytes/sec) :

  • TDK-80mm : 502, 632, 749
  • Memorex-120mm : 499, 889, 1143
  • Maxell-120mm : 500, 890, 1156

  It’s interesting that the 80mm disc performed comparably to the 120mm discs in the Dreamcast, in contrast to the LG Slim drive. Also, the results are consistent with my previous profiling experiments, which largely only touched the inner area. The read speeds range from 3.3X - 7.7X. The middle of a 120mm disc reads at about 6X.

  Implications
  A few thoughts regarding these results :

  • Since the very definition of 1X is the minimum speed necessary to stream data from an audio CD, then presumably, original 1X CD-ROM drives would have needed to be capable of reading 1X from the inner area. I wonder what the max read speed at the outer edges was ? It’s unlikely I would be able to get a 1X drive working easily in this day and age since the earliest CD-ROM drives required custom controllers.
  • I think 24X is the max rated read speed for CD-Rs, at least for this drive. This implies that the marketing literature only cites the best possible numbers. I guess this is no surprise, similar to how monitors and TVs have always been measured by their diagonal dimension.
  • Given this data, how do you engineer an ISO-9660 filesystem image so that the timing-sensitive multimedia files live on the outermost track ? In the Dreamcast case, if you can guarantee your FMV files will live somewhere between the middle and the end of the disc, you should be able to count on a bitrate of at least 900 kbytes/sec.

  Source Code
  Here is the program I wrote for profiling. Note that the filename is hardcoded (#define FILENAME). Compiling for Linux is a simple 'gcc -Wall profile-cdr.c -o profile-cdr'. Compiling for Dreamcast is performed in the standard KallistiOS manner (people skilled in the art already know what they need to know) ; the only variation is to compile with the '-D_arch_dreamcast' flag, which the default KOS environment adds anyway.

  PLAIN TEXT

  C :

  1. #ifdef _arch_dreamcast
  2.   #include <kos .h>
  3.  
  4.   /* map I/O functions to their KOS equivalents */
  5.   #define open fs_open
  6.   #define lseek fs_seek
  7.   #define read fs_read
  8.   #define close fs_close
  9.  
  10.   #define FILENAME "/cd/bigfile"
  11. #else
  12.   #include <stdio .h>
  13.   #include <sys /types.h>
  14.   #include </sys><sys /stat.h>
  15.   #include </sys><sys /time.h>
  16.   #include <fcntl .h>
  17.   #include <unistd .h>
  18.  
  19.   #define FILENAME "/media/Full disc/bigfile"
  20. #endif
  21.  
  22. /* Get a current absolute millisecond count ; it doesn’t have to be in
  23. * reference to anything special. */
  24. unsigned int get_current_milliseconds()
  25. {
  26. #ifdef _arch_dreamcast
  27.   return timer_ms_gettime64() ;
  28. #else
  29.   struct timeval tv ;
  30.   gettimeofday(&tv, NULL) ;
  31.   return tv.tv_sec * 1000 + tv.tv_usec / 1000 ;
  32. #endif
  33. }
  34.  
  35. #define READ_SIZE (20 * 1024 * 1024)
  36. #define READ_BUFFER_SIZE (512 * 1024)
  37.  
  38. int main()
  39. {
  40.   int i, j ;
  41.   int fd ;
  42.   char read_buffer[READ_BUFFER_SIZE] ;
  43.   off_t filesize ;
  44.   unsigned int start_time, end_time ;
  45.  
  46.   fd = open(FILENAME, O_RDONLY) ;
  47.   if (fd == -1)
  48.   {
  49.     printf("could not open %s\n", FILENAME) ;
  50.     return 1 ;
  51.   }
  52.   filesize = lseek(fd, 0, SEEK_END) ;
  53.  
  54.   for (i = 0 ; i <3 ; i++)
  55.   {
  56.     if (i == 0)
  57.     {
  58.       printf("reading inner 20 MB...\n") ;
  59.       lseek(fd, 0, SEEK_SET) ;
  60.     }
  61.     else if (i == 1)
  62.     {
  63.       printf("reading middle 20 MB...\n") ;
  64.       lseek(fd, (filesize / 2) - (READ_SIZE / 2), SEEK_SET) ;
  65.     }
  66.     else
  67.     {
  68.       printf("reading outer 20 MB...\n") ;
  69.       lseek(fd, filesize - READ_SIZE, SEEK_SET) ;
  70.     }
  71.     /* read 20 MB ; 40 chunks of 1/2 MB */
  72.     start_time = get_current_milliseconds() ;
  73.     for (j = 0 ; j <(READ_SIZE / READ_BUFFER_SIZE) ; j++)
  74.       if (read(fd, read_buffer, READ_BUFFER_SIZE) != READ_BUFFER_SIZE)
  75.       {
  76.         printf("read error\n") ;
  77.         break ;
  78.       }
  79.     end_time = get_current_milliseconds() ;
  80.     printf("%d - %d = %d ms => %d kbytes/sec\n",
  81.       end_time, start_time, end_time - start_time,
  82.       READ_SIZE / (end_time - start_time)) ;
  83.   }
  84.  
  85.   close(fd) ;
  86.  
  87.   return 0 ;
  88. }

• Stop doing this in your encoder comparisons

  14 juin 2010, par Dark Shikari — Uncategorized

  I’ll do a more detailed post later on how to properly compare encoders, but lately I’ve seen a lot of people doing something in particular that demonstrates they have no idea what they’re doing.

  PSNR is not a very good metric. But it’s useful for one thing : if every encoder optimizes for it, you can effectively measure how good those encoders are at optimizing for PSNR. Certainly this doesn’t tell you everything you want to know, but it can give you a good approximation of “how good the encoder is at optimizing for SOMETHING“. The hope is that this is decently close to the visual results. This of course can fail to be the case if one encoder has psy optimizations and the other does not.

  But it only works to begin with if both encoders are optimized for PSNR. If one optimizes for, say, SSIM, and one optimizes for PSNR, comparing PSNR numbers is completely meaningless. If anything, it’s worse than meaningless — it will bias enormously towards the encoder that is tuned towards PSNR, for obvious reasons.

  And yet people keep doing this.

  They keep comparing x264 against other encoders which are tuned against PSNR. But they don’t tell x264 to also tune for PSNR (–tune psnr, it’s not hard !), and surprise surprise, x264 loses. Of course, these people never bother to actually look at the output ; if they did, they’d notice that x264 usually looks quite a bit better despite having lower PSNR.

  This happens so often that I suspect this is largely being done intentionally in order to cheat in encoder comparisons. Or perhaps it’s because tons of people who know absolutely nothing about video coding insist on doing comparisons without checking their methodology. Whatever it is, it clearly demonstrates that the person doing the test doesn’t understand what PSNR is or why it is used.

  Another victim of this is Theora Ptalarbvorm, which optimizes for SSIM at the expense of PSNR — an absolutely great decision for visual quality. And of course if you just blindly compare Ptalarbvorm (1.2) and Thusnelda (1.1), you’ll notice Ptalarbvorm has much lower PSNR ! Clearly, it must be a worse encoder, right ?

  Stop doing this. And call out the people who insist on cheating.