Breaking Eggs And Making Omelettes

Les articles publiés sur le site

• Writing A Dreamcast Media Player

  6 janvier 2017, par Multimedia Mike — Sega Dreamcast

  I know I’m not the only person to have the idea to port a media player to the Sega Dreamcast video game console. But I did make significant progress on an implementation. I’m a little surprised to realize that I haven’t written anything about it on this blog yet, given my propensity for publishing my programming misadventures.

  
  
  

  This old effort had been on my mind lately due to its architectural similarities to something else I was recently brainstorming.

  Early Days
  Porting a multimedia player was one of the earliest endeavors that I embarked upon in the multimedia domain. It’s a bit fuzzy for me now, but I’m pretty sure that my first exposure to the MPlayer project in 2001 arose from looking for a multimedia player to port. I fed it through the Dreamcast development toolchain but encountered roadblocks pretty quickly. However, this got me looking at the MPlayer source code and made me wonder how I could contribute, which is how I finally broke into practical open source multimedia hacking after studying the concepts and technology for more than a year at that point.

  Eventually, I jumped over to the xine project. After hacking on that for awhile, I remembered my DC media player efforts and endeavored to compile xine to the console. The first attempt was to simply compile the codebase using the Dreamcast hobbyist community’s toolchain. This is when I came to fear the multithreaded snake pit in xine’s core. Again, my memories are hazy on the specifics, but I remember the engine having a bunch of threading hacks with comments along the lines of “this code deadlocks sometimes, so on shutdown, monitor this lock and deliberately break it if it has been more than 3 seconds”.

  Something Workable
  Eventually, I settled on a combination of FFmpeg’s libavcodec library for audio and video decoders, xine’s demuxer library, and xine’s input API, combined with my own engine code to tie it all together along with video and output drivers provided by the KallistiOS hobbyist OS for Dreamcast. Here is a simple diagram of the data movement through this player:

  
  
  

  Details and Challenges
  This is a rare occasion when I actually got to write the core of a media player engine. I made some mistakes.

  xine’s internal clock ran at 90000 Hz. At least, its internal timestamps were all in reference to a 90 kHz clock. I got this brilliant idea to trigger timer interrupts at 6000 Hz to drive the engine. Whatever the timer facilities on the Dreamcast, I found that 6 kHz was the greatest common divisor with 90 kHz. This means that if I could have found an even higher GCD frequency, I would have used that instead.

  So the idea was that, for a 30 fps video, the engine would know to render a frame on every 200th timer interrupt. I eventually realized that servicing 6000 timer interrupts every second would incur a ridiculous amount of overhead. After that, my engine’s philosophy was to set a timer to fire for the next frame while beginning to process the current frame. I.e., when rendering a frame, set a timer to call back in 1/30th of a second. That worked a lot better.

  As I was still keen on 8-bit paletted image codecs at the time (especially since they were simple and small for bootstrapping this project), I got to use output palette images directly thanks to the Dreamcast’s paletted textures. So that was exciting. The engine didn’t need to convert the paletted images to a different colorspace before rendering. However, I seem to recall that the Dreamcast’s PowerVR graphics hardware required that 8-bit textures be twiddled/swizzled. Thus, it was still required to manipulate the 8-bit image before rendering.

  I made good progress on this player concept. However, a huge blocker for me was that I didn’t know how to make a proper user interface for the media player. Obviously, programming the Dreamcast occurred at a very low level (at least with the approach I was using), so there were no UI widgets easily available.

  This was circa 2003. I assumed there must have been some embedded UI widget libraries with amenable open source licenses that I could leverage. I remember searching and checking out a library named libSTK. I think STK stood for “set-top toolkit” and was positioned specifically for doing things like media player UIs on low-spec embedded computing devices. The domain hosting the project is no longer useful but this appears to be a backup of the core code.

  It sounded promising, but the libSTK developers had a different definition of “low-spec embedded” device than I did. I seem to recall that they were targeting something along with likes of a Pentium III clocked at 800 MHz with 128 MB RAM. The Dreamcast, by contrast, has a 200 MHz SH-4 CPU and 16 MB RAM. LibSTK was also authored in C++ and leveraged the Boost library (my first exposure to that code), and this all had the effect of making binaries quite large while I was trying to keep the player in lean C.

  Regrettably, I never made any serious progress on a proper user interface. I think that’s when the player effort ran out of steam.

  The Code
  So, that’s another project that I never got around to finishing or publishing. I was able to find the source code so I decided to toss it up on github, along with 2 old architecture outlines that I was able to dig up. It looks like I was starting small, just porting over a few of the demuxers and decoders that I knew well.

  I’m wondering if it would still be as straightforward to separate out such components now, more than 13 years later?

  The post Writing A Dreamcast Media Player first appeared on Breaking Eggs And Making Omelettes.

• Translating Return To Ringworld

  17 août 2016, par Multimedia Mike — Game Hacking

  As indicated in my previous post, the Translator has expressed interest in applying his hobby towards another DOS adventure game from the mid 1990s: Return to Ringworld (henceforth R2RW) by Tsunami Media. This represents significantly more work than the previous outing, Phantasmagoria.

  
  
  Return to Ringworld Title Screen
  

  I have been largely successful thus far in crafting translation tools. I have pushed the fruits of these labors to a Github repository named improved-spoon (named using Github’s random name generator because I wanted something more interesting than ‘game-hacking-tools’).

  Further, I have recorded everything I have learned about the game’s resource format (named RLB) at the XentaxWiki.

  New Challenges
  The previous project mostly involved scribbling subtitle text on an endless series of video files by leveraging a separate software library which took care of rendering fonts. In contrast, R2RW has at least 30k words of English text contained in various blocks which require translation. Further, the game encodes its own fonts (9 of them) which stubbornly refuse to be useful for rendering text in nearly any other language.

  Thus, the immediate 2 challenges are:
  

  1. Translating volumes of text to Spanish
  2. Expanding the fonts to represent Spanish characters

  Normally, “figuring out the file format data structures involved” is on the list as well. Thankfully, understanding the formats is not a huge challenge since the folks at the ScummVM project already did all the heavy lifting of reverse engineering the file formats.

  The Pitch
  Here was the plan:

  • Create a tool that can dump out the interesting data from the game’s master resource file.
  • Create a tool that can perform the elaborate file copy described in the previous post. The new file should be bit for bit compatible with the original file.
  • Modify the rewriting tool to repack some modified strings into the new resource file.
  • Unpack the fonts and figure out a way to add new characters.
  • Repack the new fonts into the resource file.
  • Repack message strings with Spanish characters.

  Showing The Work: Modifying Strings
  First, I created the tool to unpack blocks of message string resources. I elected to dump the strings to disk as JSON data since it’s easy to write and read JSON using Python, and it’s quick to check if any mistakes have crept in.

  The next step is to find a string to focus on. So I started the game and looked for the first string I could trigger:

  
  
  

  This shows up in the JSON string dump as:

    {
      "Spanish": "!0205Your quarters on the Lance of Truth are spartan, in accord with your mercenary lifestyle.",
      "English": "!0205Your quarters on the Lance of Truth are spartan, in accord with your mercenary lifestyle."
    },
  

  As you can see, many of the strings are encoded with an ID key as part of the string which should probably be left unmodified. I changed the Spanish string:

    {
      "Spanish": "!0205Hey, is this thing on?",
      "English": "!0205Your quarters on the Lance of Truth are spartan, in accord with your mercenary lifestyle."
    },
  

  And then I wrote the repacking tool to substitute this message block for the original one. Look! The engine liked it!

  
  
  

  Little steps, little steps.

  Showing The Work: Modifying Fonts
  The next little step is to find a place to put the new characters. First, a problem definition: The immediate goal is to translate the game into Spanish. The current fonts encoded in the game resource only support 128 characters, corresponding to 7-bit ASCII. In order to properly express Spanish, 16 new characters are required: á, é, í, ó, ú, ü, ñ (each in upper and lower case for a total of 14 characters) as well as the inverted punctuation symbols: ¿, ¡.

  Again, ScummVM already documents (via code) the font coding format. So I quickly determined that each of the 9 fonts is comprised of 128 individual bitmaps with either 1 or 2 bits per pixel. I wrote a tool to unpack each character into an individual portable grey map (PGM) image. These can be edited with graphics editors or with text editors since they are just text files.

  Where to put the 16 new Spanish characters? ASCII characters 1-31 are non-printable, so my first theory was that these characters would be empty and could be repurposed. However, after dumping and inspecting, I learned that they represent the same set of characters as seen in DOS Code Page 437. So that’s a no-go (so I assumed; I didn’t check if any existing strings leveraged those characters).

  My next plan was hope that I could extend the font beyond index 127 and use positions 128-143. This worked superbly. This is the new example string:

    {
      "Spanish": "!0205¿Ves esto? ¡La puntuacion se hace girar!",
      "English": "!0205Your quarters on the Lance of Truth are spartan, in accord with your mercenary lifestyle."
    },
  

  Fortunately, JSON understands UTF-8 and after mapping the 16 necessary characters down to the numeric range of 128-143, I repacked the new fonts and the new string:

  
  
  Translation: “See this? The punctuation is rotated!”
  

  Another victory. Notice that there are no diacritics in this string. None are required for this translation (according to Google Translate). But adding the diacritics to the 14 characters isn’t my department. My tool does help by prepopulating [aeiounAEIOUN] into the right positions to make editing easier for the Translator. But the tool does make the effort to rotate the punctuation since that is easy to automate.

  Next Steps and Residual Weirdness
  There is another method for storing ASCII text inside the R2RW resource called strip resources. These store conversation scripts. There are plenty of fields in the data structures that I don’t fully understand. So, following the lessons I learned from my previous translation outing, I was determined to modify as little as possible. This means copying over most of the original data structures intact, but changing the field representing the relative offset that points to the corresponding string. This works well since the strings are invariably stored NULL-terminated in a concatenated manner.

  I wanted to document for the record that the format that R2RW uses has some weirdness in they way it handles residual bytes in a resource. The variant of the resource format that R2RW uses requires every block to be aligned on a 16-byte boundary. If there is space between the logical end of the resource and the start of the next resource, there are random bytes in that space. This leads me to believe that these bytes were originally recorded from stale/uninitialized memory. This frustrates me because when I write the initial file copy tool which unpacks and repacks each block, I want the new file to be identical to the original. However, these apparent nonsense bytes at the end thwart that effort.

  But leaving those bytes as 0 produces an acceptable resource file.

  Text On Static Images
  There is one last resource type we are working on translating. There are various bits of text that are rendered as images. For example, from the intro:

  
  
  

  It’s possible to locate and extract the exact image that is overlaid on this scene, though without the colors:

  
  
  

  The palettes are stored in a separate resource type. So it seems the challenge is to figure out the palette in use for these frames and render a transparent image that uses the same palette, then repack the new text-image into the new resource file.

• Translating Return To Ringworld

  17 août 2016, par Multimedia Mike — Game Hacking

  As indicated in my previous post, the Translator has expressed interest in applying his hobby towards another DOS adventure game from the mid 1990s: Return to Ringworld (henceforth R2RW) by Tsunami Media. This represents significantly more work than the previous outing, Phantasmagoria.

  
  
  Return to Ringworld Title Screen
  

  I have been largely successful thus far in crafting translation tools. I have pushed the fruits of these labors to a Github repository named improved-spoon (named using Github’s random name generator because I wanted something more interesting than ‘game-hacking-tools’).

  Further, I have recorded everything I have learned about the game’s resource format (named RLB) at the XentaxWiki.

  New Challenges
  The previous project mostly involved scribbling subtitle text on an endless series of video files by leveraging a separate software library which took care of rendering fonts. In contrast, R2RW has at least 30k words of English text contained in various blocks which require translation. Further, the game encodes its own fonts (9 of them) which stubbornly refuse to be useful for rendering text in nearly any other language.

  Thus, the immediate 2 challenges are:
  

  1. Translating volumes of text to Spanish
  2. Expanding the fonts to represent Spanish characters

  Normally, “figuring out the file format data structures involved” is on the list as well. Thankfully, understanding the formats is not a huge challenge since the folks at the ScummVM project already did all the heavy lifting of reverse engineering the file formats.

  The Pitch
  Here was the plan:

  • Create a tool that can dump out the interesting data from the game’s master resource file.
  • Create a tool that can perform the elaborate file copy described in the previous post. The new file should be bit for bit compatible with the original file.
  • Modify the rewriting tool to repack some modified strings into the new resource file.
  • Unpack the fonts and figure out a way to add new characters.
  • Repack the new fonts into the resource file.
  • Repack message strings with Spanish characters.

  Showing The Work: Modifying Strings
  First, I created the tool to unpack blocks of message string resources. I elected to dump the strings to disk as JSON data since it’s easy to write and read JSON using Python, and it’s quick to check if any mistakes have crept in.

  The next step is to find a string to focus on. So I started the game and looked for the first string I could trigger:

  
  
  

  This shows up in the JSON string dump as:

    {
      "Spanish": "!0205Your quarters on the Lance of Truth are spartan, in accord with your mercenary lifestyle.",
      "English": "!0205Your quarters on the Lance of Truth are spartan, in accord with your mercenary lifestyle."
    },
  

  As you can see, many of the strings are encoded with an ID key as part of the string which should probably be left unmodified. I changed the Spanish string:

    {
      "Spanish": "!0205Hey, is this thing on?",
      "English": "!0205Your quarters on the Lance of Truth are spartan, in accord with your mercenary lifestyle."
    },
  

  And then I wrote the repacking tool to substitute this message block for the original one. Look! The engine liked it!

  
  
  

  Little steps, little steps.

  Showing The Work: Modifying Fonts
  The next little step is to find a place to put the new characters. First, a problem definition: The immediate goal is to translate the game into Spanish. The current fonts encoded in the game resource only support 128 characters, corresponding to 7-bit ASCII. In order to properly express Spanish, 16 new characters are required: á, é, í, ó, ú, ü, ñ (each in upper and lower case for a total of 14 characters) as well as the inverted punctuation symbols: ¿, ¡.

  Again, ScummVM already documents (via code) the font coding format. So I quickly determined that each of the 9 fonts is comprised of 128 individual bitmaps with either 1 or 2 bits per pixel. I wrote a tool to unpack each character into an individual portable grey map (PGM) image. These can be edited with graphics editors or with text editors since they are just text files.

  Where to put the 16 new Spanish characters? ASCII characters 1-31 are non-printable, so my first theory was that these characters would be empty and could be repurposed. However, after dumping and inspecting, I learned that they represent the same set of characters as seen in DOS Code Page 437. So that’s a no-go (so I assumed; I didn’t check if any existing strings leveraged those characters).

  My next plan was hope that I could extend the font beyond index 127 and use positions 128-143. This worked superbly. This is the new example string:

    {
      "Spanish": "!0205¿Ves esto? ¡La puntuacion se hace girar!",
      "English": "!0205Your quarters on the Lance of Truth are spartan, in accord with your mercenary lifestyle."
    },
  

  Fortunately, JSON understands UTF-8 and after mapping the 16 necessary characters down to the numeric range of 128-143, I repacked the new fonts and the new string:

  
  
  Translation: “See this? The punctuation is rotated!”
  

  Another victory. Notice that there are no diacritics in this string. None are required for this translation (according to Google Translate). But adding the diacritics to the 14 characters isn’t my department. My tool does help by prepopulating [aeiounAEIOUN] into the right positions to make editing easier for the Translator. But the tool does make the effort to rotate the punctuation since that is easy to automate.

  Next Steps and Residual Weirdness
  There is another method for storing ASCII text inside the R2RW resource called strip resources. These store conversation scripts. There are plenty of fields in the data structures that I don’t fully understand. So, following the lessons I learned from my previous translation outing, I was determined to modify as little as possible. This means copying over most of the original data structures intact, but changing the field representing the relative offset that points to the corresponding string. This works well since the strings are invariably stored NULL-terminated in a concatenated manner.

  I wanted to document for the record that the format that R2RW uses has some weirdness in they way it handles residual bytes in a resource. The variant of the resource format that R2RW uses requires every block to be aligned on a 16-byte boundary. If there is space between the logical end of the resource and the start of the next resource, there are random bytes in that space. This leads me to believe that these bytes were originally recorded from stale/uninitialized memory. This frustrates me because when I write the initial file copy tool which unpacks and repacks each block, I want the new file to be identical to the original. However, these apparent nonsense bytes at the end thwart that effort.

  But leaving those bytes as 0 produces an acceptable resource file.

  Text On Static Images
  There is one last resource type we are working on translating. There are various bits of text that are rendered as images. For example, from the intro:

  
  
  

  It’s possible to locate and extract the exact image that is overlaid on this scene, though without the colors:

  
  
  

  The palettes are stored in a separate resource type. So it seems the challenge is to figure out the palette in use for these frames and render a transparent image that uses the same palette, then repack the new text-image into the new resource file.

  The post Translating Return To Ringworld first appeared on Breaking Eggs And Making Omelettes.

• Approaches To Modifying Game Resource Files

  16 août 2016, par Multimedia Mike — Game Hacking

  I have been assisting The Translator in the translation of another mid-1990s adventure game. This one isn’t quite as multimedia-heavy as the last title, and the challenges are a bit different. I wanted to compose this post in order to describe my thought process and mental model in approaching this problem. Hopefully, this will help some others understand my approach since what I’m doing here often appears as magic to some of my correspondents.

  High Level Model
  At the highest level, it is valuable to understand the code and the data at play. The code is the game’s engine and the data refers to the collection of resources that comprise the game’s graphics, sound, text, and other assets.

  
  
  Simplistic high-level game engine model
  

  Ideally, we want to change the data in such a way that the original game engine adopts it as its own because it has the same format as the original data. It is very undesirable to have to modify the binary engine executable in any way.

  Modifying The Game Data Directly
  How to modify the data? If we modify the text strings for the sake of language translation, one approach might be to search for strings within the game data files and change them directly. This model assumes that the text strings are stored in a plain, uncompressed format. Some games might store these strings in a text format which can be easily edited with any text editor. Other games will store them as binary data.
  

  In the latter situation, a game hacker can scan through data files with utilities like Unix ‘strings’ to find the resources with the desired strings. Then, use a hex editor to edit the strings directly. For example, change “Original String”…

  0098F800   00 00 00 00  00 00 00 4F  72 69 67 69  6E 61 6C 20  .......Original 
  0098F810   53 74 72 69  6E 67 00 00  00 00 00 00  00 00 00 00  String..........
  

  …to “Short String” and pad the difference in string lengths using spaces (0x20):

  0098F800   00 00 00 00  00 00 00 53  68 6F 72 74  20 53 74 72  .......Short Str
  0098F810   69 6E 67 20  20 20 00 00  00 00 00 00  00 00 00 00  ing   ..........
  

  This has some obvious problems. First, translated strings need to be of equal our smaller length compared to the original. What if we want to encode “Much Longer String”?

  0098F800   00 00 00 00  00 00 00 4D  75 63 68 20  4C 6F 6E 67  .......Much Long
  0098F810   65 72 20 53  74 72 00 00  00 00 00 00  00 00 00 00  er Str..........
  

  It won’t fit. The second problem pertains to character set limitations. If the font in use was only designed for ASCII, it’s going to be inadequate for expressing nearly any other language.

  So a better approach is needed.

  Understanding The Data Structures
  An alternative to the approach outlined above is to understand the game’s resources so they can be modified at a deeper level. Here’s a model to motivate this investigation:

  
  
  Model of the game resource archive format
  

  This is a very common layout for such formats: there is a file header, a sequence of resource blocks, and a trailing index which describes the locations and types of the foregoing blocks.

  What use is understanding the data structures? In doing so, it becomes possible to write new utilities that disassemble the data into individual pieces, modify the necessary pieces, and then reassemble them into a form that the original game engine likes.

  It’s important to take a careful, experimental approach to this since mistakes can be ruthlessly difficult to debug (unless you relish the thought of debugging the control flow through an opaque DOS executable). Thus, the very first goal in all of this is to create a program that can disassemble and reassemble the resource, thus creating an identical resource file. This diagram illustrates this complex initial process:

  
  
  Rewriting the game resource file
  

  So, yeah, this is one of the most complicated “copy file” operations that I can possibly code. But it forms an important basis, since the next step is to carefully replace one piece at a time.

  
  
  Modifying a specific game resource
  

  This diagram shows a simplistic model of a resource block that contains a series of message strings. The header contains pointers to each of the strings within the block. Instead of copying this particular resource block directly to the new file, a proposed modification utility will intercept it and rewrite the entire thing, writing new strings of arbitrary length and creating an adjusted header which will correctly point to the start of each new string. Thus, translated strings can be longer than the original strings.

  Further Work
  Exploiting this same approach, we can intercept and modify other game resources including fonts, images, and anything else that might need to be translated. I will explore specific examples in a later blog post.

  Followup

  • Translating Return to Ringworld, in which I apply the ideas expressed in this post.

• Approaches To Modifying Game Resource Files

  16 août 2016, par Multimedia Mike — Game Hacking

  I have been assisting The Translator in the translation of another mid-1990s adventure game. This one isn’t quite as multimedia-heavy as the last title, and the challenges are a bit different. I wanted to compose this post in order to describe my thought process and mental model in approaching this problem. Hopefully, this will help some others understand my approach since what I’m doing here often appears as magic to some of my correspondents.

  High Level Model
  At the highest level, it is valuable to understand the code and the data at play. The code is the game’s engine and the data refers to the collection of resources that comprise the game’s graphics, sound, text, and other assets.

  
  
  Simplistic high-level game engine model
  

  Ideally, we want to change the data in such a way that the original game engine adopts it as its own because it has the same format as the original data. It is very undesirable to have to modify the binary engine executable in any way.

  Modifying The Game Data Directly
  How to modify the data? If we modify the text strings for the sake of language translation, one approach might be to search for strings within the game data files and change them directly. This model assumes that the text strings are stored in a plain, uncompressed format. Some games might store these strings in a text format which can be easily edited with any text editor. Other games will store them as binary data.
  

  In the latter situation, a game hacker can scan through data files with utilities like Unix ‘strings’ to find the resources with the desired strings. Then, use a hex editor to edit the strings directly. For example, change “Original String”…

  0098F800   00 00 00 00  00 00 00 4F  72 69 67 69  6E 61 6C 20  .......Original 
  0098F810   53 74 72 69  6E 67 00 00  00 00 00 00  00 00 00 00  String..........
  

  …to “Short String” and pad the difference in string lengths using spaces (0x20):

  0098F800   00 00 00 00  00 00 00 53  68 6F 72 74  20 53 74 72  .......Short Str
  0098F810   69 6E 67 20  20 20 00 00  00 00 00 00  00 00 00 00  ing   ..........
  

  This has some obvious problems. First, translated strings need to be of equal our smaller length compared to the original. What if we want to encode “Much Longer String”?

  0098F800   00 00 00 00  00 00 00 4D  75 63 68 20  4C 6F 6E 67  .......Much Long
  0098F810   65 72 20 53  74 72 00 00  00 00 00 00  00 00 00 00  er Str..........
  

  It won’t fit. The second problem pertains to character set limitations. If the font in use was only designed for ASCII, it’s going to be inadequate for expressing nearly any other language.

  So a better approach is needed.

  Understanding The Data Structures
  An alternative to the approach outlined above is to understand the game’s resources so they can be modified at a deeper level. Here’s a model to motivate this investigation:

  
  
  Model of the game resource archive format
  

  This is a very common layout for such formats: there is a file header, a sequence of resource blocks, and a trailing index which describes the locations and types of the foregoing blocks.

  What use is understanding the data structures? In doing so, it becomes possible to write new utilities that disassemble the data into individual pieces, modify the necessary pieces, and then reassemble them into a form that the original game engine likes.

  It’s important to take a careful, experimental approach to this since mistakes can be ruthlessly difficult to debug (unless you relish the thought of debugging the control flow through an opaque DOS executable). Thus, the very first goal in all of this is to create a program that can disassemble and reassemble the resource, thus creating an identical resource file. This diagram illustrates this complex initial process:

  
  
  Rewriting the game resource file
  

  So, yeah, this is one of the most complicated “copy file” operations that I can possibly code. But it forms an important basis, since the next step is to carefully replace one piece at a time.

  
  
  Modifying a specific game resource
  

  This diagram shows a simplistic model of a resource block that contains a series of message strings. The header contains pointers to each of the strings within the block. Instead of copying this particular resource block directly to the new file, a proposed modification utility will intercept it and rewrite the entire thing, writing new strings of arbitrary length and creating an adjusted header which will correctly point to the start of each new string. Thus, translated strings can be longer than the original strings.

  Further Work
  Exploiting this same approach, we can intercept and modify other game resources including fonts, images, and anything else that might need to be translated. I will explore specific examples in a later blog post.

  Followup

  • Translating Return to Ringworld, in which I apply the ideas expressed in this post.

  The post Approaches To Modifying Game Resource Files first appeared on Breaking Eggs And Making Omelettes.