Alice’s bubbles (Part 1)

Marchen Maze title screen
Or more humbly, the awesome Märchen Maze translation postmortem. It’s more or less a compilation/addendum for this pcedev forum [post].

Märchen Maze is a PCEngine HuCard game released by Namco the 11th of December 1990. It’s a conversion of the 1988 arcade game. It was also ported to the almighty Sharp X68000. As you may have guessed the X68000 version is a near perfect conversion of the original arcade game. It features some jolly 3D isometric view and colourfull introduction. Well, things are not that fancy on the PCEngine version. The 3D isometric view was changed to a top view (à la Mercs or Commando). And the intro is now in sepia tones. What about the story and gameplay? Check the Video Game Den review [here].

Ok! Back to business.
The PCEngine has some neat RPGs. Unfortunately only a few of them were translated into the idiom of the perfidious Albion (English). This was a perfect excuse for trying out that black art called romhacking. Monster Maker was my first choice. I must admin that cdrom games are not a really good choice for your first romhacking experience. A HuCard game is far more simpler to hack. So I went for Momotarō Katsugeki. It’s a cool platform game with tons of text. Unfortunately the text is displayed top to bottom and from left to right in bubbles. It was clearly out of my league. So I asked some people if they knew some easily translatable games. I can’t remember who suggested it. But Märchen Maze was designated as it doesn’t have too much text and no apparent string compression.

The first thing I had to do was to find where the text was stored in the ROM. After hours of pain, David Shadoff took pity. And like a mighty wizard, he managed to extract the whole script in no time. So I had the rom location of the strings. All I had to do was to put read breakpoint in Mednafen. I was able to locate the text output routine ($87D6). The string “parsing” was spotted from $89E5 to $8CD8 using step-by-step debugging starting from the the output routine. It made me realized that $5C,$5D held the pointer to the string to be displayed. The parsing routine was called from $E377 using jmp ($202C) instead of jsr. The return address was pushed by hand onto the stack. Here’s an snippet of the parsing routine. $ff is a special value. More on this later.

l_89e2: LDY     $271b
        LDA     [$5c], Y
        CMP     #$ff
        BNE     l_89ee

The most important information was that I now knew the zero page location holding the string pointer. Setting a write breakpoint to $5C:$5D led me to $8C4B.

        LDA     [$52], Y
        STA     <$5c
        INY     
        LDA     [$52], Y
        STA     <$5d

I was lucky because what precedes told me where the string table was.

        LDA     #$00
        STA     <$64
        LDA     #$56
        STA     <$65
        LDY     #$0c
        LDA     [$64], Y
        STA     <$52
        INY     
        LDA     [$64], Y
        STA     <$53
        LDA     $2716
        ASL     A
        TAY     
        LDA     [$52], Y
        STA     <$5c
        INY     
        LDA     [$52], Y
        STA     <$5d

So $5c:$5d is set using the data pointed by $52:$53 indexed by $2716. Let’s put $2716 aside. This is clearly the string index. So $52:$53 contains our string pointer. And the preceding lines tells us that the string table address is stored at $560C. A quick revealed that the string table was stored from $5614 to $5849. If we translate the address, it’s at the file offsets $11814 to $11A49 (this is with the annoying 512 bytes offset). Now that I had the string pointer table, I could make it point to whenever I want (technically). So the translated texts may not have to fit into the original string locations. I checked that I got it right by swapping the pointer table entries. And as expected the intro started with the second text and so on.
A quick look at the tile vram showed me that the font already contains capital letters. So I decided to manually edit the ROM and managed to get this:
Quick hack

The next step was to modify the font in order to have lowercase letters.
To continue…

The last man on Earth sat alone in a room…

This is what is supposed to be the shortest post on this blog.
Remember last post where I used __builtin_ctz to compute GCD? Well… Here’s a way to compute the log2 of an integer using another gcc builtin. Let me introduce __builtin_clz. clz stands for count leading zeroes. So this wonderful thing counts 0 bits starting from the most significant bit. Please note that the result is undefined for 0.

inline uint32_t ilog2(uint32_t i)
{
	return (32-__builtin_clz(i));
}

Check the section 5.49 of GCC doc for more builtins.

By the way the title of this post comes from a short novel by Fredric Brown called Knock.

GCD and destroy

Some weeks ago I decided to fix once and for all this bloody hdrr. As it requires the framebuffer average log luminance, I decided to compute it be generating a pixel accurate mipmap. So for a 320×240 framebuffer we will have the following downsampling steps : (4,4) (4,4) (5,5) (4,3).
Don’t ask me why but instead of working on a way to decompose a number, I decided that I needed to find the greatest common divisor of width and height! 10 seconds later thanks to the almighty web search engine I started reading the Wikipedia entry about Binary GCD. And after some interweb jumps I ended on this article. The Stein’s algorithm looked cool.
If you look at Sputsoft code, you’ll realize that the shift_to_uneven function removes trailing zeros. This can be optimized using GCC builtins. The builtins we need is __builtin_ctz that counts trailing zeros.
We can then replace shift_to_uneven by:

u >>= __builtin_ctz(u);

And the GCD function now looks like this:

uint32_t gcd( uint32_t c, uint32_t d )
{
uint32_t u,v,s;

u = __builtin_ctz(c);
v = __builtin_ctz(d);

s = (u < v) ? u : v; u = c >> u;
v = d >> v;

while(u != v)
{
if(u > v)
{
u -= v;
u >>= __builtin_ctz(u);
}
else
{
v -= u;
v >>= __builtin_ctz(v);
}
}
return u << s; }[/sourcecode] Tadam!

Malevitch can’t code!

Some months ago, Iq asked on Pouet bbs if anyone had some tip and tricks on creating a minimal glx framework.
Viznut answered that he managed to have open a window and refresh a framebuffer in 300 bytes using kernel syscalls.
So I jumped on the bandwagon and decided to code my own minimal X client using raw X11 protocol.
Here’s my miserable attempt. Looking at xcb and Xlib code helped a lot. Unfortunately it failed on half of the boxes where it was tested because of authentication.
Kernel_error tried to add it but he said it’s a pain in the harp.
Oh by the way, it’ll crash on x64… Here’s small article in french about the different syscall conventions. And you’ll surely understand why it’ll crash 🙂

Dataflash of the two worlds

I spent the whole afternoon trying to make the arduino works with 2 dataflash chips. A coupe of really stupid code mistakes and some weird stuffs later, it worked. You can now have 2 instances of ATD45DB161D class. For example one will use the pins 2, 4 and 5 for SS, RESET and WP and the other one will use pins 10,8 and 7.
I couldn’t make SS work with an other pin than the pin 10 until I ran across forum post. So I have to set both the requested SS pin and pin 10 (hardwired SS pin) high before setting the SPCR register so that the atmega168 becomes master.
So I moved the SPCR initialization to a new method astutely called Enable. And I added its counterpart called Disable which drives the SS pin high.
So before using a given Dataflash chip, you’ll have to call Enable before using it. And call Disable when you are done with it.

As I’m not happy with the current design, I created a new branch for this dev.

You can find it [here].
Any ideas/suggestions for a cleaner/safer way to handle multiple SPI device are welcome 🙂

[edit]: Arg, I should have checked Atmel site. They have an application note called AVR151: Setup And Use of The SPI.
[edit] (it’s the last one. I swear 🙂 ) I moved the SPI master init into a new function (spi_init). It’s a little bit cleaner now. But it’ll stay in a branch until I run more tests and have some feedback.

Alice in GitHub

Some of the stuffs I posted here are now on [GitHub]. Namely, the and the [ips patcher]. Feel free to clone them 🙂
I’m taking a little break from OpenGL stuffs and the pcengine tracker. To relax I’m working on Marchen Maze translation. I’m nearly done with the introduction. I’m currently working on the insertion software. But I need to find someone to translate the script… Anyway you can check my progress on [pcedev].

And for more useless stuffs you can check my [twitter page].

Lights out!

After spending hours playing Primrose, I decided to code a little board game using GGI during a week-end. I don’t remember how but I ended on the Lights Out wikipedia page.

The gameplay is quite simple. You have a 5×5 board with tiles randomly switched on. Well not really randomly because it’s frustrating to have an unsolvable board ;). Your goal is to switch all the tiles off by pressing them. The problem is that when you press a tile, the four adjacent tiles are toggled on or off (see it as an xor).

And voila! It’s a very basic implementation. It features simple graphics, no text nor title screen…

Fireballs of fire!

EEK! 6 months !

It’s not that I had nothing to write. On the contrary, I have a lot to post. I just didn’t found the time to write… Erm.. Let’s go with a 7 months old stuff.

While working on the tracker, I wanted to add some kind of “live” mode. The user could choose which sequence to play, modify it, control volume, add an effect etc… So I came with the idea to associate a command to a key combo.

Combos are detected by walking down a tree. Each time a button is pressed, we look at the current node and check if one of its children is associated to this button. If that’s the case, this child becomes the new current node. Otherwise there’s no matching combo and we reset the current node to the tree root. If the button pressed didn’t not changed for a certain amount of time (timeout), we check there’s a child corresponding to the current button. This way, we can detect combo containing a sequence like “press A button during t seconds”.

Let’s look at a simple example.

Mkit will successively return : DOWNDOWN+RIGHTRIGHT0 (aka nothing) – A

We have 0 because when you go from RIGHT to A, there’s a moment when you don’t press any button. And as we check keys every vsync, we necessary get 0 (unless if you are Superman on Redbull).

Consider we want to handle the following combos :

The combo tree is very similar to a lexical tree. A node can have 0 to N children but only one parent.

The tree is store in level-order with the longest path first. This means that you’ll have to be very careful and store node children by their depth. We have for our example :

Root – Down – A – Down+Right – Down+Left – Nothing – Left – Right – A – Nothing – Nothing – Leaf – A – B – Leaf – Leaf

In the current implement, the tree is stored in 2 arrays. The first one contains the index to first child of a node. And the second the key for each node.

combo_tree : 1, 3, 5, 6, 7, 8, 9, 10, 128 | 2, 11, 12, 128 | 0, 128 | 1
combo_keys: .db 255, JOY_DOWN, JOY_I, JOY_DOWN | JOY_RIGHT, JOY_DOWN | JOY_LEFT
.db 0, JOY_RIGHT, JOY_LEFT, JOY_I, 0, 0, JOY_I, JOY_II

The root is always at index 0 and we associate the key value 255 to it.
The tree traversal algorithm is very simple. For a given node i, we know that its children are at indices j from combo_tree[i] to combo_tree[i+1]-1. And that we can reach them only if the current key is combo_key[j]. If the bit 7 of a value in the children list is set, this means that we have a transition a leaf. The remaining bits are used as an index to a jump table.
The traversal looks like this:

i // current node index
for(j=combo_tree[i]; jCOMBO_DEFAULT_DELAY in combo.asm). Note that in current code combo_tree, combo_keys and combo_jumpTable are in RAM. So you’ll have to initialize them before-hand.

If you have any question, feel free to leave a comment or go and join the [PCEdev Forum].

Talking about web stuff, I finally updated the gallery. Hurray!

Micro SDisco

Some months ago, I bought a 4DSystem’s µDRIVE-uSD-G1 (microDRIVE) from Sparkfun. It’s basically a serial module which let you access a microSD memory card (from 512Mb to 2Gig). You may wonder why use an external module as SD cards have a SPI interface? The main reason is … laziness. All file-system operations are performed by the module. So why bother coding fat16 support or whatever? Unfortunately, the current microDRIVE firmware only supports raw access.

Arduino with 4D System\'s uDRIVE-uSD-G1

Anyway, I wrote a small module for the current firmware. It was implemented as a template in order to support various serial implementations. The serial class must provide the following methods :

  • uint8_t read()
  • void print(uint8_t)
  • int available()

It’d have been better if all the serial implementations derived from a same interface. But as I didn’t want to modify the base Arduino code (and as i said earlier, because I’m lazy), I went for the easy/brutal way. And you’d probably never have more than one microDRIVE. At least you want raid 😀

I tested Arduino‘s HardwareSerial and SoftwareSerial, as long as ladyada’s AFSoftSerial. None of the software implementations work 😐 Only soft read is working (hardware tx was used). As software serial is working for the serial LCD, I think the problem might be the autobaud detection during microDRIVE initialization… Or not…

Be careful! There’s a bug in the rev1 firmware. The internal memory address is not incremented to the next sector block after a write operation. It was corrected in the rev2.

IPS delivery (part 3)

Happy new year!

Just after Christmas, Tomaitheous released Bubblegum Crash patch. Yeepee!

As it’s an IPS patch, I tried to patch the rom with the wonderful ips patcher. Unfortunately, it was unable to patch it. I had a nice “Record offset is out of file bound.” error.
All was IPSProcessRecord function fault. First, I considered the file offset to be out of bound if it was superior or equal to the file size. But if you are appending data to a file, the offset is equal to the file size. Second, I never updated the patched file size. So If we keep appending data to a rom, the bound test will fail.

Anyway! Everything is fixed now. And I was able to successfully apply the patch. So go grab the latest version here:

And as usual, feel free to contact me or leave a comment if you have any request or problem.