Monday, 29 May 2017

Mission Supernova - A look at the music

Earlier this month we announced two projects for this year Google Summer of Code to add support for the Sludge engine and for the Mission Supernova games in ScummVM. I am a co-mentor for the Mission Supernova project (the other mentor being Strangerke). We were lucky enough to be provided with the original source code for Mission Supernova (for which we have to thank the rights owner). With the coding period for GSoC starting officially tomorrow we spent the last month looking at this original source code. Interestingly, in addition to the source code for the game we were also given the source code for some tools. One of those converts a MOD music file to a game data file. And I though it would be interesting as a side project to reimplement it so that it works on modern computers, and to then extend it to perform the reverse conversion from game file to the original MOD file (which we don't have).

I thus spent a few days working on this in the past two weeks.

We have been asked not to share the original source code (and anyway you would have to be a bit of a masochist if you want to see C code from over 20 years ago). But I will show a small extract to give you an idea of the work involved. The original source code is in C and for DOS.

The source code for the mod conversion tool is very compact and starts with these two functions:


For anyone familiar with supporting both big endian and little endian platforms, what they do is obvious. They swap bytes to convert between big endian and little endian representations.

If you are wondering what big and little endians are, go read my first post in this blog on adding support for the mac version of Broken Sword (you can also read the third post in that series about fixing speech for some mac versions of Broken Sword).

Conversion between big endian and little endian should come as no surprise. The MOD format was originally developed for Amiga, which are (or at least were at the time) big endians computers. Looking at the specifications of the MOD format shows that it is indeed using the big endian convention. On the other hand the DOS operating system was working on little endian computers. Using a little endian format for the music in Mission Supernova thus made sense to avoid having to swap bytes during runtime. Every little helped at the time to get good performances...

Another thing visible in the code above and that should come as no surprise (at least for developers dealing with old platforms) is that an unsigned int is coded on two bytes (and not on 4 bytes as you would expect nowadays) and a long int uses 4 bytes.

The last point we can note is that functions and variables have German names. Fortunately for me I did study German at school and could understand most of the code straightaway without having to ask Google translate (or my German sister in law) for help.

The first step of my work was to rewrite the code of that tools so that it works on modern computers, whether they are using big endian or little endian conventions, and can be understandable by others.

  • I replaced the byte swap function from the original source code with code we already have in ScummVM that handles byte swapping depending on the platform on which the code is run (so that for example reading a MOD file would only swap bytes when the code is run on a little endian computer).
  • I replaced data types such as unsigned and long with types provided by ScummVM such as uint16 and int32.
  • I rewrote the code to use ScummVM Common::File API instead of the low level DOS file access code.
  • I translated variable and function names to English.
  • I objectified the code a bit adding a ModReader class.
At this point, without the original MOD file, I had no way to know if the code I wrote was correct. Writing this code however helped me understand the differences between the MOD format and the format used by the Mission Supernova game.

The two formats are very similar, but besides the different endianness, there are a few other differences. Actually the format for the two parts of Mission Supernova  is slightly different.

Here is a description of the MOD file header:


And one of the Mission Supernova part 1 data file header:




For the Mission Supernova part 2, there are only 15 instruments stored and not 22.

Note how some information is missing in the Mission Supernova data file. That means that we have to guess what that information should be when converting that data file back to a MOD file. Fortunately none of that missing information is really important. For example for the song name I just decided to use the name of the MOD file that was hardcoded in the original source code.

Some other information is just formatted in a different way, such as the Mission Supernova instruments data having a loop start and loop end instead of a loop start and loop length.

Also the Mission Supernova data file stores explicitly the number of patterns and the offsets of the samples data. Those have to be computed from other informations in the MOD format.

The other difference not seen above between the two formats is in the pattern data. Both are using 32 bit values, but they are not coded in exactly the same way. For details on the differences just look at the source code and comments in the rewritten tool.

This knowledge of the MSN music data file might be useful when we have to work on supporting the music in the game engine reimplementation. For now I used it to write some code to do the conversion the other way around: from the game data file to a MOD file.

This allowed me to check that the code is correct:
  • By checking that the converted MOD file I am getting is played correctly in a player supporting that format.
  • By doing a round trip conversion: converting from MSN data file to MOD and then back to MSN data and checking that I get back the original file.
My first round trip test actually resulted in the original and converted MSN data file having a one byte difference (every bytes were identical except one). The offset of that bytes indicated it was the second byte of the order list length value, coded on two bytes in the Mission Supernova format. And then I realised that  I was using a char variable  (that uses one byte) since in the MOD format the order list length is coded on one byte. Writing that variable on two bytes meant the second byte was garbage.

The final source code is available at https://github.com/criezy/scummvm-tools/tree/supernova/engines/supernova. At some point I might merge it in the main ScummVM repository.

Implementing this reverse conversion also allowed me to listen to the music without waiting for the games to be supported in ScummVM. And to let you enjoyed that music as well, here are recordings for the music of the first and second parts of Mission Supernova converted to MOD and played back in an OpenSource ProTracker clone.

Mission Supernova part 1 music

Mission Supernova part 2 music


Friday, 25 March 2016

NSDockTilePlugIn for ScummVM on OS X

As you may already be aware, this year the ScummVM project is participating to the Google Summer of Code. One of the rules for students who want to participate with us is that they need to submit a simple patch against the ScummVM source code before they are accepted. Usually we direct prospective students  to our bug tracker for ideas on what they could implement. But now most of the bugs that are still open are not trivial to fix. So I was looking at the source code hunting for simple things to do when I found a TODO comment I left two years ago when implementing the TaskbarManager API on OS X.

What is the TaskbarManager API?

The TaskbarManager API allows interacting with the ScummVM application icon in the taskbar (or in the case of OS X in the dock). We have implementations of this API for several systems, but the only one that is complete is the implementation for Windows. In details the API allows to:

  • Display an overlay icon when playing a game. If you have in your extra path png files named after the game IDs, when starting a game the corresponding png image is overlaid on the ScummVM icon in the dock. You can for example get icons from http://www.megamonkey.org/icons/ and below is example of this feature in action.
  • Display progress. This is for example used in the mass add feature to indicate the number of directories scanned in respect with the total number of directories to scan.
  • Display a count. This is also used in the mass add feature to indicate how many games are being added.
  • Notify of an error.
  • Provide a list of recently played games.

The last two were not implemented on OS X and the TODO comment was related to the last point. The idea was that we could provide a list of recently played games in the ScummVM dock menu and thus provide a shortcut to start a game quickly. I decided to take another look at this feature and wrote some bits of code to check that the idea I had hinted at in the TODO would indeed work. I then waited a few days in case a student wanted to implement this as part of his application to the GSoC. But today I finished implementing this feature, cleaned the code and pushed this to the ScummVM repository.

One aspect to consider here is that we want to customise the menu on the ScummVM icon in the dock when ScummVM is not running. That way we can propose a list of recent items in the menu and start ScummVM directly with a game. On OS X we can provide this feature with a plug-in that implements the NSDockTilePlugIn protocol. If an application bundle contains such a plug-in, the OS loads that plug-in when the application is added to the Dock. So there are actually two separate things to implement:

  • Obviously we need to implement the plug-in.
  • But we also need to implement code in ScummVM to update the list of recent games when starting a game.

Saving the list of recent games

The TaskbarManager is part of the ScummVM application and when starting a new game the addRecent method is called. So what I did here was simply to save the list or recent games in a place where the aforementioned plug-in can find it. I decided to use the NSUserDefaults class to do this, which means the list is saved in the user preferences (to be precise in the ~/Library/Preferences/org.scummvm.scummvm.plist file).

(if you don't see the source code below visit the blog as it may not be visible in RSS feeds)


That code is a bit too simple though. There are two main issues with it: the list can grow indefinitely and the same game can appear multiple times in the list. So let's improve the code that updates the array of games.


And that's it. We have this part fully implemented. After playing a few games the ~/Library/Preferences/org.scummvm.scummvm.plist file should look like this:



Implementing the NSDockTilePlugIn

If you took a look at the NSDockTilePlugIn protocol documentation you will have seen that it requires implementing a setDockTile: method, and optionally we can implement a dockMenu method. We actually have nothing to do in the first one, so let's skip it and look directly at the second method.


Here we can note that I am using CFPreferences to read the list of recent games and not NSUserDefaults. Why is that? Do I need to remind you that this code is in a plug-in and not in ScummVM? That means we need to access the preferences of another application. Admittedly we could have used NSUsersDefault addSuiteNamed: to achieve this, but remember, we are implementing a plug-in and not an application. The plug-in is loaded by the SystemUIServer and using NSUserDefaults addSuiteNamed: would have changed the global preferences domain list for the SystemUIServer and not only for the plug-in.

The second point we can note is that the code above is using something called StartGameMenuItem. As you have probably guessed this is a custom class that derives from NSMenuItem. Indeed for each menu item I needed to store somewhere the game ID so that when this menu item is activated it can start the corresponding game. So I decided to inherit from the NSMenuItem class and store the game ID in the derived class. And while I was at it I also added the method to start a new game in that derived class. So here is what this class looks like:


To Conclude

Now if you add ScummVM to the dock, and after playing at least one game, you should see the list of games you played recently in the the dock menu like in the picture below. This provides a quick way to start one of those games.



And here is what it looks like in action:


This is in my opinion the most useful of the features provided by the TaskbarManager API, so I am happy to see it finally implemented (I would have done it sooner if I had not forgotten about it :P).

Edit: Our buildbot uses an older SDK that does not support the NSDockTilePlugIn protocol. So nightly builds from our web site will not contain this new feature. You will need to compile your own version or wait for ScummVM 1.9.0.

Sunday, 30 November 2014

Broken Speech

Yes, another Broken Sword post. In previous posts I wrote about my initial work to add support for the mac version of the Broken Sword game in ScummVM and some more work I did to fix graphical glitches with this version. At that point the game was working fine for me. But soon, we got a report on the forum that the speech was not working. Obviously it was working for me, I would have noticed if it wasn't. So what the heck?!

Bug reports are good. They stop me getting bored. And they show that other users have the mac version of Broken Sword and benefit from my work, which is also gratifying. So let's look at that issue. And to do so, first let's rewind to my first post. I wrote that I assumed the files with the same name (including the extension) as the files of the Windows version where in the same format, and in particular used the same endianness. And the files with a different extension were big endian in the mac version and little endian in the Windows version. That proved mostly correct (a few resources had been left as little endian data in files otherwise converted to big endian).

Except that wasn't correct. So why did it work? Because I had been lucky. When I initially worked on supporting that game it looked like my guess was correct, and I therefore made quick progress as I was not distracted by some strange behaviour. But...

Let's start the story from the beginning:

In the Windows version the speech is stored in a file named speech.clu. There are actually two such files, one on each CD, and they store the speech as 16 bits compressed mono wave data. And as you can expect the data is little endian.

In the Mac version, the files have the same name (speech.clu). So in my initial implementation I assumed the speech data was little endian in the mac version as well. And it worked... with the version I have (the French version). Obviously it didn't work with the version of the user reporting the bug (the English version) since the user reported hearing static noise instead of speech.

The two files (Windows and Mac versions, both English) have the same size:


But opening them in an hex editor shows differences:

Do the differences remind you of something?
If not go back and read again the first two posts in this Broken Sword mac support series.

Before looking at the differences, I will give a short explanation of the speech file format.
The speech files are a collection of sound resources. Each resource contains the wave data for spoken sentence and is organised as follow:
4 bytes: 'data' (i.e. hexadecimal values 64 61 74 61)
4 bytes: number of samples
n bytes: wave data (16 bits mono)

So quite simple, but maybe no as simple as you might think. If you are thinking that n is the number of samples multiplied by 2 (since each sample takes 2 bytes) you are wrong. Because the data is compressed. This is not really important for now so I will keep the description of the compression for later.

What is important here is that we can see that the first 4 bytes after 'data' are identical (in the image above hexadecimal values 8E E6 01 00 - which, since we know it is little endian, means 0x0001E68E = 124558 samples). But the values that follow are obviously a series of 2 bytes values for which the bytes have been swapped.

At this points, here is a small reminder in case you are not following me and did not go back to my previous posts: big endian and little endian are conventions used to interpret the bytes making up a data word (more at http://en.wikipedia.org/wiki/Endianness).  For example 42 in hexa is 2A, or when using two bytes 002A. When using the big endian convention, this would be stored as 00 2A. But when using the little endian convention this would be stored as 2A 00.

So this should be obvious to you now that both the Windows and the Mac version store the number of samples of the sound resource as little endian values, but in the mac version the data samples themselves are stored using big endian convention. Why mix endianness in the same file? Why do this for the mac English version but not the mac French version? Don't ask me, I have no idea.

Since some mac version use little endian and others use big endian, we need to know which one it is. Does it depend on the language, i.e. all French versions use little endian and all English versions use big endian? Maybe. But I don't trust statistics on a set of two samples. And what of the German versions?

Therefore we decided to use a heuristic to find out if the mac version the player has uses big endian data or little endian data. The heuristic works by computing the average difference between two consecutive samples (using absolute values). Using the assumption that a sound wave is smoother than picking values at random, the lower average difference is considered to be the correct endianness.

If we take the 13 samples from the example image above, assuming big endian for the mac version gives us the following curve:


The average difference value from one sample to the next is 425.17.

If we assume little endian data the curve is:

And the average difference value is 9344.75.

So in this case the heuristic tells us the data is big endian, which it is. Of course in the actual source code we use more than 13 samples to get a statistically valid heuristic value.
The original patch that adds the heuristic code can be found in the patch tracker: https://sourceforge.net/p/scummvm/patches/956/

But the story does not ends here. A new bug report very similar to the original one (i.e. speech sounds like static noise) was reported a few months ago. It was quite obvious that the heuristic did not work for that user and the wrong endianness was used. Why is that? It turns out there were several issues with the original heuristic code.

And that is where explaining how the speech data compression works will help to understand what was wrong. The data for one sound resource is broken in blocks, each one starting with a number of samples followed by the sample values. When you have consecutive samples with the same value it uses a negative size and the value is stored only once.
So for example the following sequence:

    0 0 0 0 0 1 2 3 4 5

would be stored as (where the brackets indicate the blocks):
    [
-5 0] [5 1 2 3 4 5]
All those numbers (number of samples and sample value) are stored on 2 bytes.

Here is the original source code (if you don't see the source code visit the blog as it may not be visible in RSS feeds).

I will not show the uncompressSpeech() code (yet). The only thing you need to know is that it uses the value of _bigEndianSpeech as either big endian or little endian data. So what the code above does is get the data assuming little endian data and then compute the heuristic value for the samples it gets and for the same samples to which a byte swap is applied, which should be the value we would get assuming big endian data. Right?

Wrong! This heuristic forgets something: the data is compressed, and when uncompressing it always assume little endian when reading the number of samples for each block. But if the data are big endian this number would be different and the blocks would have different sizes, and because the block boundaries would be wrong it would cause number of samples to be interpreted as sound samples and some sound samples to be interpreted as number of samples.

For example let's look at the resource of 10 sample with the compressed data -5 0 5 1 2 3 4 5.
Assuming the data is stored in big endian, in hexadecimal values with two bytes per value this give us: 80 05 00 00 00 05 00 01 00 02 00 03 00 04 00 05
If we read this with the heuristic above, because the number of sample is always read assuming little endian data we get 80 05 = 1408 samples instead of -5 for the first block. So the code will get the following samples: 0 5 1 2 3 4 5 followed by 4 garbage values read beyond the end of the resource instead of getting 0 0 0 0 0 1 2 3 4 5. So if the data are stored using big endian, the heuristic values gets biased. Almost always it still gets a lower score as reading it as little endian though.

The solution here is to call uncompressSpeech() twice, once assuming little endian and once assuming big endian.

But there is still an issue with this heuristic.
When reading with the wrong endianness, since we may read the wrong length, it may for example be a big negative number. Because we are using a relatively small finite number of samples, statistically we could end up with a small heuristic value because it has a lot of consecutive samples with the same value. For this reason I made an additional change to skip consecutive samples with the same value when computing the average difference.
After that commit the value for the heuristic with the wrong endianness is consistently about 21000, i.e. 1/3rd of 16 bits integer range (65 535 / 3 = 21845). As noted by wjp:  the average absolute difference between two random numbers drawn independently from a uniform distribution between 0 and N is indeed N/3. So this is quite reassuring.

So everything was correct after this change? No, that would be too easy. We want complex puzzles spanning several rooms, not some kind of hidden objects game. And the user reporting the bugs confirmed the bug was still present after that change. So let's look at a different room, or rather a different function.

Here is the code from uncompressSpeech():
Note something relevant? No? Look closer. You see it now? Yes, this function always give us the sound data in little endian format, whatever the endianness in which it is stored, and more importantly whatever the endianness of the computer on which the code is run.

And if you look at the heuristic code above, it assumes it gets data in the native endianness (i.e. the endianness of the computer on which the code is run). So when running on a computer using big endian convention the heuristic was wrong. Let's look again at our previous example and how it was interpret on a big endian computer:
   Read with the correct endianess: 0 1 2 3 4 5 (duplicate values have been removed)
   Was interpreted as: 0 256 512 768 1024 1280

   Read with the incorrect endianess: 0 1280 256 512 768 1024 1280
   Was interpreted as 0 5 1 2 3 4

So in the heuristic code, on a big endian computer we need to swap the bytes of the two set of data to get the correct value. This brings us to the final code, in which the heuristic computation was also moved to a separate function to avoid code duplication (since it is done twice):

The user reporting the bug confirmed he was using ScummVM on a big endian computer (a G4 mac) and that the speech was correct after that final change.

Sunday, 28 September 2014

How it continued

In my very first post on this blog I wrote how I came to be involved with the ScummVM project by adding support to the mac version of Broken Sword 1. I wrote I had been lucky, and you will have to wait a bit longer to know why (yes I know, I am milking this one, but I promise I will explain it soon). I expertly avoided however to reveal that I had also been lazy. When I submitted the initial patch I knew the support was not perfect. I already mentioned it lacked support for AIFF music (and I will take this opportunity to correct myself: apparently the support was added by eriktorbjorn, at least according to the history on github, and not by sev as I mistakenly wrote in my first post). But more importantly there were graphical glitches. Yes! GRAPHICAL GLITCHES! Oh, the horror! And I can't even claim I had not noticed them. That would mean admitting I was blind (or at least color blind).

The first one is visible every time you visit Nico in her apartment, which is quite often (just a shame you can't use that big bed). Notice anything wrong (no, not the bed)?

George, don't leave! Have you seen what is waiting for you out there? A corridor painter in red! Stuff of nightmare! And the psychopath who painted that might still be lurking in a corner!

Just in case the image above appears normal to you, here is what it should have looked like:

No light in the corridor? I guess they forgot to pay the electricity bill.

The second glitch is even bigger, although maybe not as obvious. I had not played the game for a few years myself when I added support for it in ScummVM, and while something was bugging me during my tests I was not sure what it was initially.

Bull's Head Hill, Syria, on a murky day. The sky, the color of a swamp, was empty of any birds. And I was about to jump into the void.
And here is what is should have looked like:

A Sunny day in Syria. Maybe I will live after all. Not that it will stop me jumping though.
So what is wrong? This scene in Syria has a background parallax layer, on top of which the foreground is drawn, with transparency where we should see the background. And you have probably noticed by now that the background was not visible in the mac version.

The game sometimes uses parallax layers to give a sense of depth to the scene. When the characters move on screen, the foreground and background will move at different speed. See wikipedia if you have never heard of a parallax before.

video

This is the only scene in the game that has a background parallax layer. And as such it has a special logic for the draw code. Other scenes may have a foreground parallax layer however, as is visible in the video below.

video

The two glitches are caused by two different bugs. But they are somewhat related. The game uses 256 colors with a different palette for each scene. That means each scene defines a list of 256 colors, and then the image data is defined using the indexes (stored on 1 byte) in that list instead of using directly the colors.

The palette for each scene is actually defined in two separate resources: one that defines the palette for the scene itself and contains 184 colors (indexes 0 to 183), and one for the sprites that contains 72 colors (indexes 184 to 255). The first color (at index 0) is actually reserved for the top bar (inventory) and bottom bar (dialog options) area when the bars are hidden. It is forced to black in all the scenes, whatever the color defined in the data file. This is also the color used for the door in Nico's room. And it is used for the transparent part of the foreground image in the bull's head hill scene. And this is the index used for the transparency in the sprite data as well.

You have probably guessed it by now: the mac version does not use color index 0 for the door in Nico's room and for the transparency in the bull's head hill scene. After a bit of debugging it turned out it is actually using color index 255 (i.e. the last color of the palette instead of the first one). In Nico's apartment that color happens to be red, and in the Bull's Head Hill scene it happens to be some sort of brownish dark green. Once I knew what the problem was, it was fixed with a simple patch.

Other than that the Mac version is identical to the Windows version. It still uses the first 184 colors of the palette for the background and the last 72 colors for the sprites. And it still uses color index 0 for the top and bottom bars area and the transparency in the sprite data. So I have no idea why they made that change for the two cases described above.

Here is the code to get the palette when loading a new room. As explained above it is called twice, once for the first 184 colors and a second time for the remaining 72 colors. We force color 0 to be black. Lines 6 to 9 corresponds to the fix for the mac version, in which we also force color 255 to be black.



And here is the beginning of the draw code. As I wrote above the Bull's Head Hill, which is screen 54, has a special handling. We first draw the background parallax and then draw the screen on top, skipping pixels with color 0 (which here means transparent). On line 21 we have the fix for the mac version, for which we also skip pixels with color 255.



And that is all for today. In the next post I will speak of the speech data, and I will explain why I was lucky in my initial implementation.

Thursday, 18 September 2014

Do you play English? Part 3

In this post I will continue to write about translating games for the ScummVM project. This is the last  part of a three parts series.

Part 3: Translate a game into a new language


Some of the games for which we released a freeware version are from eastern Europe and were not released in English. So to give them a wider audience we decided to add an English translation.

The first such game was Dragon History, a Czech game for which a GSoC student added support in ScummVM in 2009, with the help of the original developer. The game was only released in Czech and Polish originally, but German and English translations have been added. If you want to know more about this game, see the official web site: http://www.ucw.cz/draci-historie/index-en.html

Since I don't know much about Dragon History myself, in this post I will focus on two Polish games from LK Avalon. The first one Soltys, is supported since ScummVM 1.5. It is available to download for free on our web site, and in addition to the original Polish version, we have an English and Spanish translation.

The second game I will write about is Sfinx. It is very similar to Soltys in the way it works, and support for it in ScummVM was added during this year GSoC. We are currently working on the English translation and very soon (maybe tomorrow?) we intend to make it available so that non-Polish ScummVM users can test the game, report bugs and also suggest improvement to the translation.

Edit: the call for tests is now live!

Both Soltys and Sfinx have two data files named vol.dat and vol.cat. The latter is a catalog that lists the files present in the former and at which offset they start. So when the game needs a file, it can look into the catalog where to start reading it in the vol.dat file. To edit the data files however, we need to extract those. Then we can repackage them into a new vol.dat file, generating a new catalog file as well in the process. We have two tools to perform the extraction and packaging, and they work for both Soltys and Sfinx (despite some minor differences in the file format).

Once uncompressed, you will have a lot of files. All the dialogs are in a file named CGE.SAY. The hotspots names are in the files with the SPR extension. The other files can be ignored (they will be needed when repackaging the game though.

So what does the CGE.SAY look like? Here is a small portion of it that shows almost everything there is to know:

;--Anna above.
 1:22=Oh, what a nice pussy!|I would love to have one
;--Vincent in the dark
 1:31=Where's the light? I can't see
 1:32=There should be a shutter,|let's try to lift it

;======================================================================

;--Vincent about the cleaning stuff
 2:01=Cleaning? Never!|It's for the girls!
;--Anna about the cleaning stuff
 2:02=Isn't there a gentleman around?

Lines starting with a semi column are comments. There are a lot of them, which is a great help.
Dialog lines start with xx:yy as you can see above. The xx is the room number. So in the example above we have a portion of the dialogs for the first two rooms. The yy is the text number in this room.
The pipe indicate a line break. So for example the first text of the second room will look like this in game:



Simple, isn't it?
Now let's have a look at one of the SPR files, for example 02ZSYP.SPR. As the name suggest this is one of the hotspots in the second room. The start of the file look like this in the polish version:

Type=AUTO
Name=zsyp na <98>mieci

[phase]
02zsyp00
02zsyp01
02zsyp02

[seq]
 0   -2   0   0  0   8
 1    3  84   2 127  8  .OTWIERA
 1    0  85   2 127  8  .ZAMYKA

 2   -2   0   0  0   8

[ftake]
say    -2    2:5  brudny

[mtake]
reach  -2  2:7     . zsyp
SOUND  2:7 2:84
pause   -1 72
SAY    -2  2:4
NEXT   -1   0      . smiec popycha

The name is what appears on screen when moving the cursor to the hotspot. We can now also see that the file is named after the hotspot name. This makes it easy to find a file when you know the hotspot name... in Polish (not so easy when you know it in English ;) ).

The <98> is the way my text editor displays non ASCII characters using their hexadecimal value (so in decimal we have here character 152).  In this case the character is ś. The game is using the CP852 encoding (with only the example above it could also have been using the mazovia encoding, but other characters allow to make the distinction). Fortunately English does not use many non ASCII characters, so we don't have to deal with this much.

So, the polish name is zsyp na śmieci. Google translate tells me (I don't speak Polish myself) that it translates into garbage chute. So let's modify the second line in the file and see how it looks:

Type=AUTO
Name=garbage chute

[phase]
02zsyp00
02zsyp01
02zsyp02




For Sfinx, the bulk of the work was done by Strangerke and then I made a couple of passes to improve the English and fix spelling mistakes. Uruk, the GSoC student who worked on the engine, also made some modifications.

For Soltys, the Polish to English translation was done by neutron and the Spanish version is from IlDucci and The FireRed. I am currently working on a French translation as well.

The process I explained above is therefore very similar to what I explained in the previous post to improve an existing translation for Drascula:

  • Unpack the data file.
  • Edit the dialogs and hotspot names.
  • Repack.

However there is one major difference. Because the game was only released in Polish in the first place, the font data does not contain all the characters we need for other languages. For English this is not an issue, unless you happen to use a word loaned from French, such as déjà vu or café.  When translating to French however you need those accentuated characters. So there is one more step to do: modify the font data (which was done by Strangerke on Soltys).

The font is stored in a file called CGE.CFT. This is a simple bitmap font, for which each pixel is black (or another color) or transparent. So we need one bit to store a pixel. If the bit is 1, the pixel is visible, and if the bit is 0, the pixel is not visible. The height of the font is 8 pixels, which conveniently can therefore be stored on one byte (because in case you don't already know, 1 byte contains 8 bits). The width is variable, and if for example a character is 4 pixels wide, thus 4x8 pixels, its data is coded on 4 bytes. And there are 256 possible characters.

The font file starts with the width, coded on one byte, for each characters. That takes the first 256 bytes. Then the bitmap starts. Here is the start of the file for Sfinx displayed with hexadecimal values. The first column is the address (also in hexadecimal). We have 16 bytes on each line. A star denotes one or more lines that are identical to the previous line.

0000000 04 06 06 06 06 06 06 04 04 04 04 04 04 04 04 04
0000010 04 04 04 04 04 04 04 04 04 04 04 04 04 04 04 04
0000020 04 02 04 06 04 05 05 02 04 04 03 04 02 03 02 03
0000030 04 04 04 04 04 04 04 04 04 04 02 02 04 04 04 05
0000040 05 05 05 05 05 05 05 05 05 02 04 05 04 06 05 05
0000050 05 06 05 05 06 05 04 06 04 06 05 03 03 03 04 05
0000060 04 05 04 04 04 05 03 04 04 02 03 04 03 06 04 04
0000070 04 04 04 05 03 04 04 06 04 04 04 04 02 04 06 06
0000080 04 04 04 04 04 04 04 04 04 04 04 04 04 05 04 05
0000090 04 04 04 04 04 04 04 05 05 04 04 04 04 04 04 04
00000a0 04 04 04 04 05 05 04 04 05 05 04 04 04 04 04 04
00000b0 04 04 04 04 04 04 04 04 04 04 04 04 04 05 04 04
00000c0 04 04 04 04 04 04 04 04 04 04 04 04 04 04 04 04
*
00000e0 05 04 04 05 04 04 04 04 04 04 04 04 04 04 04 04
00000f0 04 04 04 04 04 04 04 04 04 04 04 04 04 04 03 04
0000100 00 00 00 00 1e 29 2f 29 1e 00 1e 2b 2f 2b 1e 00
0000110 0e 1f 3e 1f 0e 00 0c 1e 3f 1e 0c 00 1c 5b 7f 5b
0000120 1c 00 1c 5e 7f 5e 1c 00 ff ff ff 00 ff ff ff 00
0000130 ff ff ff 00 ff ff ff 00 ff ff ff 00 ff ff ff 00
*
0000180 ff ff ff 00 ff ff ff 00 ff ff ff 00 00 00 00 00
0000190 2f 00 03 00 03 00 14 7f 14 7f 14 00 26 7f 32 00
00001a0 13 0b 34 32 00 1a 25 1a 28 00 03 00 3c 42 81 00
00001b0 81 42 3c 00 06 06 00 08 1c 08 00 60 00 08 08 00
00001c0 20 00 38 07 00 3f 21 3f 00 22 3f 20 00 3b 29 2f
00001d0 00 31 25 3f 00 0f 08 3f 00 37 25 3d 00 3f 25 3d
00001e0 00 01 3d 03 00 3f 25 3f 00 37 25 3f 00 24 00 64
00001f0 00 08 14 22 00 14 14 14 00 22 14 08 00 02 29 05
0000200 02 00 1e 21 2d 0e 00 3c 0a 09 3f 00 3f 25 26 18
0000210 00 1f 21 21 12 00 3f 21 22 3c 00 3f 25 25 20 00
0000220 3f 05 05 01 00 1e 21 29 19 00 3f 04 04 3f 00 3f

If we look at the first few lines, we can see that the characters are between 2 and 6 pixels wide.
Let's try to have a look at the start of the alphabet. In the ASCII table, we can see the value of the letter A is 65, and since values start at 0, that means this is the 66th character. So first we will compute the sum of the widths of the first 65 letters.
That would be 4 + 6 + 6 + 6 + ... + 4 + 4 + 4 + 5 = 263
So if we skip the first 256 bytes (the character widths) and then the next 263 bytes, we should get the data for letter A. So let's look at the data that starts at address 256 + 263 = 519 (207 in hexadecimal).
I have highlighted in red above the width for the 66th characters, which as we can see is 5, and the 5 bytes starting at address 0x207.
Let's write them, with the corresponding binary representation below (with the least significant bit at the top):
 3c 0a 09 3f 00
 0  0  1  1  0
 0  1  0  1  0
 1  0  0  1  0
 1  1  1  1  0
 1  0  0  1  0
 1  0  0  1  0
 0  0  0  0  0
 0  0  0  0  0

So now a bit of ASCII art: we replace the 1 by a @ and the 0 by a space

     @ @
   @   @
 @     @
 @ @ @ @
 @     @
 @     @

You recognize something?

Just for fun, let's do the same for the next two letters:

 @ @       @ @ @  
 @   @     @     @
 @ @ @     @      
 @     @   @      
 @     @   @     @
 @ @ @       @ @

So we can edit the font file using an hexadecimal editor for example. This involves some ASCII art (exciting :-), and it can be challenging to fit an accentuated characters on 5x8 pixels), some additions on hexadecimal numbers and some conversions between binary and hexadecimal (boring :-( ).

This concludes my three parts posts on translating games for ScummVM. I hope you found it interesting. Now I will take some rest while you start testing Sfinx. There is one last thing though: ScummVM is a community effort, and it does not only involves software developments. You can contribute in other ways, such as translating freeware games, translating ScummVM itself or helping with the user manual. So if you are motivated to help us, please get in touch for example on our IRC channel (#scummvm on irc.freenode.net) or forum.


Tuesday, 16 September 2014

Do you play English? Part 2

In this post I will continue to write about translating games for the ScummVM project. This is the second part of a three parts series.

Note: This post contains an embedded sourc code example that is not visible on the RSS feed.

Part 2: Improve the original translation of a game


Sometime the official translation of a game could be mistaken with the result you would get from the AltaVista translation of the 90s. And I am not exaggerating.

The French version of Drascula was an example of this, and I am told the Italian version was not better - but my limited knowledge of the Italian language does not allow me to confirm. While this was hilarious in its own way, it distracted from the game, so we decided to provide an improved translation for both Italian and French. I didn't work at all on the Italian translation, so the examples I will take are all from the French translation. But most of the explanation would work for the other translations.

Here the strings are partly in the game data file and partly in the original executable. We extracted the string from the original executable and instead in ScummVM they are in the drascula.dat file that we provide with ScummVM. So improving the translation meant both modifying this drascula.dat file and modifying the the game data files. Sometimes it also meant adding new strings, as for example the subtitles for some languages were missing in the Von Braun cutscenes.

Modifying the strings in the drascula.dat file is easy. The strings are hardcoded in the source code of the tool used to generate that file. So we just need to modify that source code. The only little difficulty is that non-ASCII characters (e.g. accentuated character, and we have a lot of those in French) are using the Code Page 850 encoding. And in C we need to use the octal number in the string preceded with a backslash. So for example, to have an è, the decimal value in the CP850 encoding is 138, which in octal is 212. So the string would be '\212'. Therefore to get "Chèvre" ("Goat" in English, I think my brain was permanently damaged by working on Broken Sword) I would need to write "Ch\212vre".

Modifying the data file is not much harder. Those files are actually ARJ archives. So you can easily decompress them using a tool that supports this compression. Files with strings are those with the extension CAL (which contain the dialogs) and ALD (which contain the hotspots). But you cannot edit them directly; that would be too simple. They use a simple encryption: each byte is x'ored with 0XFF.

For example the letter A in ASCII has a value of 65. In binary this gives 01000001.
When you x'or it with 0XFF (11111111 in binary) this gives: 10111110 (190 in decimal).
To get back to the original text you just need to X'or it again by 0xFF.

So I quickly wrote a simple C program to decrypt and re-encrypt the files:


To give you an idea of how bad it was, here are some of the hotspots from the original version and the corresponding ones from my improved version.


OriginalImprovedComment
PUITPUITSA simple typo you might think. Maybe, if it had been the only one...
CIMTEIERECIMETIEREAnagrams now? Maybe that was actually designed as a puzzle?
CAISSONTIROIRWhere did that come from??? Canadian French maybe?
CERVEAUSCERVEAUXYou may need a brain to know that the plural of words ending in 'eau' takes a X and not an S.
TRONCCOFFREMaybe my favorite. It make me think that the "translator" may have been working from the English text and not the Spanish one. TRONC is a tree trunk. COFFRE is a chest... or a car trunk.
ARMARIOARMOIREOK, they forgot to translate that one.
BAULCOFFREAnd that one.
ESPEJOMIROIRAnd also that one.
PUERTAPORTEDid I download the Spanish version by mistake?

And you have many more like this. And the dialogs were not much better. For those who understand french here are a few examples of original dialogs:
  • Quelle merde de jeu dans lequel le personnage principal meurt! Un instant, qu'y a-t-il de mon dernier désir?
  • Et bien merci et au revoir. Que tu la dormes bien.
  • Non rien. Je m'es allais déjà.
  • Comment peux-je tuer un vampire?
  • Qu'est-ce qu'on suppose que tu fais?
I will stop there. But I could fill pages like that. So if you speak french and fancy a good laugh, feel free to download the original french version (not the updated one) from our web site and play the game.

Another game for which we improved an existing translation is Mortville Manor. This is a French game that was also released in German and English. Except the DOS version was never released in English. Strangerke (one of the developer who worked on the engine in ScummVM) extracted the English strings from the Amiga and Atari version. But it was still missing all the dialogs. Strangerke created a Google Doc spreadsheet with the French and English strings and with a ScummVM user named Hugo we started fixing the existing English translation and translating the missing strings. Then we implemented a small tool to generate a data file from these strings (mort.dat, which is distributed with ScummVM) so that users can play in English using the game data files from the DOS French or German version.

For Mortville Manor, we actually also bundled the French and German strings and the data for the menu in the mort.dat data file. That way we can easily improve those languages as well. But for now they have not been improved and only the original French and German versions are available. I have been told the German one is not perfect. So if you like this game, speak German, would like to improve the German translation, and have a lot of free time on your hands you can contact me ;-)


See you tomorrow for part 3.

Do you play English? Part 1

One of my main attributions in the ScummVM team for the past few years has been to work on translations. There are two aspects to it:
  • Translating the ScummVM software itself.
  • Translating games.
Concerning the first point, I wrote some of the code to handle translations in an efficient and portable way in ScummVM. I also maintain the French translation and coordinate the work of the translators for the other languages. I may write a post on that topic later. But first I will write a series of three posts in which I will focus on the second point: translating games. I will present several examples to show the variety of work this can involved.

In some cases we can improve slightly a translation for a game without having to modify the data files. I will write about that in this first part. But to turn The Beast into Prince Charming, a face lift is not sufficient and we need to do a more invasive surgical operation. Such an operation is limited to the cases where we have access to the data files. We have good relations with some game companies and we have been allowed to provide some formerly commercial games as freeware on our web site. This made this work possible and I will present this in parts 2 (improve the original translation) and 3 (add a new translation) in the next few days.

Note: This blog post contains embedded source code examples that are not visible on the RSS feed.

Part 1: Fixing a few missing or wrong strings in a game


In some game there is a minor issue with the official translations. Sometimes a subtitle is missing and sometimes there is a big spelling or grammatical mistake. Considering my involvement with the Broken Sword game engine (see my previous post), what better example to start with than Broken Sword?

In 2008, it was reported that an error was displayed instead of the correct subtitle in one place, when George says "Oh?". I will grant you this was not a very critical subtitle.

Here is the code that gets the subtitle to display from its Id.

As you can see it is quite simple.
On the first two lines, knowing the text ID and the language, it asks the Resource Manager to give some data, which in that case come from the text.clu (or text.clm for the mac version) file.  This file contains many blocks. A block contains:
  • A 20 bytes header
    • Bytes 0-5: resource type (here "ChrTxt")
    • Bytes 6-7: version
    • Bytes 8-19: Related to compression (compressed size, compression type and uncompressed size).
  • The number of strings in this block coded on 4 bytes
  • For each string the offset at which it starts (relative to the end of the block header) again coded on 4 bytes.
  • And finally the strings.
Here the version is always 1 and the compression is always "NONE". So we can ignore the header altogether. Thus the code skips it without even looking at its content.

The next few lines check that the string index in this block is smaller than the number of strings. The string ID is coded on 4 bytes, The two highest bytes identify the resource block (ITM_PER_SEC is 0X10000) and the two lowest bytes identify the string in the block (ITM_ID is 0xFFFF).

Then from that index it reads the offset at which the string starts. If the offset is zero it returns an error string. Otherwise it returns the string from the data.

To help you visualize what I wrote above, here is a picture (hexadecimal and ASCII) of the start of one small block. This is from my mac version, so numbers are big endians (see my previous post).

Blue: Header
Red: number of strings (here 11 since it is in hexadecimal)
Green: the offsets for the start of the string (we have 11 of them, each one coded on 4 bytes)
You may have guessed it already, for the particular string from the bug report, in some languages the offset is zero, so instead we get the error message. The fix is simple: I identified the text ID (2950145) and hardcoded in the source code the string to use.


A bit later it was discovered that a bunch of subtitles are also missing from the demo, presumably because it was released early before translations were finalized. But in that case the issue was slightly different: instead of having an offset of zero, the offset itself was also missing. The text ID pointed to an index bigger than the number of strings in the corresponding block. So here is the current version of the code will all the workarounds:


I did a similar fix in Dreamweb. The command "Aller vers" ("Go to") was misspelled "Aller ver". And since it is one of those string present virtually everywhere in the game I decided to add a workaround to fix it, again by hardcoding the correct string in the source code.

See you tomorrow for part 2 and more important changes to a game original translations.