Faxanadu Mantras - Part II

Let's start with the subroutine that begins at offset 0x9850. The first few bytes of the mantra the user entered are read and transformed. Afterwards two checks are performed which ensure the validity of the mantra.

At the beginning of that function some indexes are initialized.



Afterwards another function (offset 0x98A7; I call this function GetLSBBits) is called three times. This function takes two parameters: The register A contains the next character from the mantra and the register Y contains the number of bits that should be read from that byte. Note that the Y least-significant bits of the character are read, the 8-Y most significant bits are disregarded. In all three instances 6 bits are supposed to be read from the first three characters. This makes perfect sense if you recall that the highest numeric value for a character in the mantra was 0x3F or 111111 in binary form.



At this point you might already suspect the format of the mantra. 64 input characters and extracting the six least significant bits of an 8 bit byte. That sounds familiar. The mantra is in fact basically a Base64 encoded string of the player's inventory and stats with some checksums mixed in. It's a slightly modified Base64 code though because later a number of bits that's not 6 will be read depending on the storage size of certain attributes or items.

The next part of this function is the first check for validity. You might remember that memory address $666 holds the length of the password the user entered. The 5 most significant bits of that value must equal the value of the 2nd byte in the array that was generated from the mantra. How exactly the value of this byte is created is mentioned later.



The last part of the function converts all remaining bytes from the mantra array to the new array. While doing this it also adds up all bytes of the $4CD array to perform another check on the validity of the mantra.



Now that we know how the bytes in the $4CD array are used let's see how that array was created in the first place. As I said it's a transformation of the mantra bytes from the array at $600. This transformation takes place in the GetLSBBits function at offset $98A7.



I've actually had major problems to understand that function. The reason for this was that the 6502 rotate instructions (ROL in this case) do not work like their x86 equivalents and it took me a while to realize that (Update: I forgot about the existence of the x86 instructions RCR and RCL which behave like the 6502 instructions). If you rotate a value by 1 on x86 CPUs the LSB of that value gets the value of the former MSB. On 6502 it gets the value of the carry flag. There were two reasons why I was confused before I understood this behaviour: The first one was that the values of the $4CD array are not reset after the user enters a wrong password. The 6502 ROL behaviour makes that perfectly fine though. All the old values will have been rotated out of all bytes after the mantra is processed. The 2nd point of confusion was how bytes of value 0 could suddenly turn into bytes of value 1 after a rotation. An impossibility on x86 CPUs but it works on 6502 due to the carry flag which is rotated in.

Let's recall the two validity checks. The first one is that the 5 most significant bits from the byte at offset $4ED must equal the size of the mantra the user entered. To get through this check it's possible to generate the mantra and just put the length of the mantra into the highest 5 bits of the 2nd byte. The other check, the sum of all bytes in the array must be 0, is just as simple if you know that the first byte of the array ($4CD) is not used for anything at all. It was probably used by the programmers of Faxanadu to correct the checksum and that's what I used it for too. Later we will see that it would also be possible to append a correcting byte to the mantra because even the longest valid mantra (without appended random characters) doesn't nearly need 32 characters.

That was (nearly) all that's necessary to check the validity of a password. Let's move on to the actual game data that resides in the mantra. This data is extracted from the mantra in the subroutine at $95E9.

It all starts with the code below. I've called the subroutine at $98E9 GetNextBits. It works nearly like GetLSBBits but reads bits from an array in sequential order without disregarding the MSB bits. The number of bits to read is passed in Y, the current byte position and the current bit position are kept in the same registers as in GetLSBBits. I'm not going to discuss GetNextBits because it's nearly identical to GetLSBBits.

The code snippet shows that the GetNextBits function is called 5 times. The Y bit value it returns is stored elsewhere in memory. I've found out what exactly is read to what memory position using trial-and-error. In most cases it was not necessary to create passwords to try what happens for a certain value. When the data is read from the mantra it's directly stored in the part of the memory that's also used during the game, so changing from a Long Sword to a Giant Blade or something can be done by editing a single byte in memory.



After these four values were read the modus operandi changes a bit because in the next few lines the current equipment of the player is read. To read those values a new function (at $96B0) is introduced. This function - which I won't discuss extensively - reads the next bit (using GetNextBits) and if the value is 1 (Item equipped) reads another Y bits (using GetNextBits again) to find out which item is worn.



The last thing that's left to read is the inventory of the player. This is once again done differently. At first a number of bits (in Y) are read that gives away the number of items in a specific part of the inventory. Then another number of bits (X) are read Y times to fill the inventory with the item identified by the next X bits. Every part of the inventory has a maximum amount of items it can support. If this maximum number is exceeded the mantra is once again flagged as invalid.



That's it. The rest of the function only sets or clears the carry flag depending on whether the mantra was recognized as invalid or not.

If you know about Faxanadu you might wonder how that can be everything. Neither your experience nor your gold is encoded in the mantra. These two values are not stored separately, apparently they depend on your rank. Depending on which rank you have you'll get a certain amount of gold and experience when you restart the game.

There is actually a Faxanadu mantra generator available online (written in JavaScript) and I've written my own one in C++ (not very usable, you have to recompile the file every time you want to generate a new mantra). If you compare the passwords generated by these two generators you might notice that there are often differences between the generated passwords. This can easily be explained. Trailing 'A' characters are in most cases unnecessary because 'A' is the character with the numeric value 0 which is coincidentally the value that's used to pad the mantra if the number of bits it's not evenly divisible by 8. The online generator removes unnecessary trailing zeros, my generator does not. This also has an effect on the 2nd on the 3rd character of the mantra because that's where the size of the mantra is stored. The checksum in byte 0 (mantra characters 1 and 2) is not affected.

I haven't yet mentioned the meaning of certain bit values in the mantra (like Hand Dagger = 0; Long Sword = 1). This information can be found in the source file of my mantra generator.

By the way, vsj????,Xwbg3BuApxA5ikQl4 is a decent mantra that can be used to start in the first city with full equipment. Time to teach those first few monsters a lesson with your Dragon Slayer and Tilte.