Let´s play money making game.

Let´s play money making game.

I decided earlier today that I should play through the first Zelda for the NES. It started out great. After having cleared the first palace, some sub-conscious memory from playing the game as a kid guided me to a “This is a secret to everybody”, which yielded no less than 100 Rupees. The unfortunate part of this otherwise great start was that the secret was located next to a “Money making game”. If you are at all familiar with the first Zelda, you have surely played the “Money making” mini-game.

The mini-game works by you selecting one out of three Rupees. The Rupees will then show their true values, which can be either -40, -10, 20 or 50. If you chose a negative value, Rupees will be taken away from you, where as a positive will add to your Rupees. In the case of my attempted play-through, I got 3x -40, aggressively shut off the console, and decided to find out how this cheating piece of software actually works.

 

Zelda Random

Initialization

To understand the probability of an outcome in the mini-game, I first had to understand how randomness works in Zelda.

Like most NES games, the random-seed is updated each frame. The seed is a 13-byte long number located from $18 to $24 inclusive. My guess is that the game uses different bytes for different random elements in the game, to make it seem less static. The “Money making game” only uses two bytes ($19 & $1A), so I only really looked at them.

When the game is powered on or reset, all values of this 13-byte long number is set to zero aside from the first byte, which is initially set to #$40.

05:B4EF    LDA #$00     ; memset(0x0000, 0x00, 0xF0);
; ...
05:B4F9    LDY #$EF     ; ...
05:B4FB    STA $0000,Y  ; ...
05:B4FE    DEY ; ...
05:B4FF    CPY #$FF     ; ...
05:B501    BNE $B4FB    ; ...
05:B503    LDA #$40     ; A = 0x40
; ...
05:B508 STA $0018    ; *0x18 = A

If you patch the code above at address $B503 to LDA #$00 (or use this Game Genie code: AAELGIAG), all randomness in the entire game is removed.

Advancing the seed

Once the seed has been (re-)initialized, the games starts to advance it once per frame from its initial value (#$40).

The seed is advanced using the follow logic:

07:E542    LDX #$18
07:E544    LDY #$0D
07:E546    LDA $00,X @ $0018 = #$40
07:E548    AND #$02
07:E54A    STA $0000 = #$00
07:E54C    LDA $01,X @ $0019 = #$00
07:E54E    AND #$02
07:E550    EOR $0000 = #$00
07:E552    CLC
07:E553    BEQ $E556
07:E555    SEC
07:E556    ROR $00,X @ $0018 = #$40
07:E558    INX
07:E559    DEY
07:E55A    BNE $E556

or, rewritten in Python:

def _ror(val, carry):
    next_carry = bool(val & 1)
    val = (val >> 1)
    if carry:
        val |= 0x80
    return val, next_carry

def random_init():
    return [ 0x40 ] + ([ 0 ] * 12)

def random_advance(seed):
    carry = bool((seed[0] & 0x02) ^ (seed[1] & 0x02))
    for i in range(0, len(seed)):
        seed[i], carry = _ror(seed[i], carry)
    return seed

So essentially, if the value at address $18 is #2, or the value at $19 is #2, set the highest bit in $18. Don’t do this if both are #2 at the same time. Then just shift all 13-bytes as one big integer one step to the right. This algorithm is very well distributed. Below are three distribution matrices for the value at address $18.

Note, index (0, 0) at the top left corner of the matrix shows the number of times $18 has been #0, moving right to index (0, 1) shows the number of times it has been #1, and so on.

At 10,000 frames:

37, 40, 38, 36, 37, 40, 38, 36, 32, 40, 34, 46, 35, 45, 49, 34,
39, 29, 38, 37, 30, 41, 41, 46, 40, 35, 43, 41, 47, 42, 29, 43,
37, 40, 34, 35, 46, 34, 39, 46, 37, 38, 45, 39, 39, 39, 38, 46,
36, 41, 32, 33, 40, 38, 31, 45, 51, 32, 33, 40, 32, 37, 40, 44,
35, 43, 37, 47, 33, 39, 45, 37, 42, 44, 44, 33, 34, 33, 39, 39,
40, 42, 43, 29, 46, 47, 43, 37, 36, 42, 41, 31, 41, 33, 40, 46,
32, 37, 37, 37, 33, 43, 35, 41, 49, 33, 40, 33, 34, 30, 37, 43,
44, 48, 42, 31, 30, 36, 37, 35, 32, 46, 35, 40, 31, 52, 42, 49,
40, 34, 39, 38, 35, 40, 42, 47, 36, 35, 37, 41, 40, 39, 40, 38,
38, 40, 42, 48, 45, 43, 37, 38, 37, 30, 35, 35, 36, 31, 40, 41,
41, 44, 38, 47, 40, 43, 28, 32, 45, 34, 48, 41, 39, 33, 36, 40,
33, 33, 44, 43, 42, 35, 33, 35, 41, 40, 33, 32, 46, 38, 43, 47,
40, 34, 38, 42, 38, 39, 34, 41, 36, 46, 44, 42, 33, 37, 28, 42,
45, 43, 40, 31, 33, 42, 29, 39, 30, 45, 36, 37, 40, 32, 44, 44,
42, 43, 40, 38, 49, 43, 35, 29, 39, 38, 35, 35, 41, 43, 35, 45,
41, 30, 50, 33, 47, 34, 47, 45, 39, 37, 46, 52, 45, 46, 49, 61,

At 30,000 frames:

107, 112, 107, 119, 107, 114, 120, 120, 111, 116, 118, 112, 117, 118, 121, 119,
115, 116, 112, 112, 117, 119, 107, 116, 120, 117, 117, 117, 116, 122, 118, 121,
112, 118, 115, 120, 112, 122, 114, 113, 119, 119, 120, 116, 113, 113, 118, 116,
117, 116, 121, 117, 117, 120, 118, 116, 115, 120, 117, 115, 120, 120, 120, 116,
114, 116, 119, 117, 115, 117, 119, 119, 113, 118, 122, 119, 116, 116, 117, 114,
118, 120, 121, 117, 119, 120, 120, 114, 113, 118, 113, 118, 116, 117, 116, 115,
118, 115, 112, 119, 119, 118, 119, 120, 118, 116, 118, 116, 117, 121, 118, 119,
113, 118, 118, 118, 117, 117, 120, 116, 112, 122, 117, 121, 117, 122, 119, 115,
112, 114, 114, 121, 120, 116, 115, 120, 120, 108, 118, 111, 120, 116, 117, 120,
115, 119, 122, 115, 121, 117, 119, 118, 113, 121, 120, 117, 119, 110, 122, 115,
118, 118, 117, 118, 119, 119, 118, 118, 119, 119, 119, 118, 118, 118, 115, 115,
116, 115, 116, 122, 117, 114, 120, 121, 116, 116, 117, 121, 114, 118, 119, 118,
113, 119, 117, 118, 113, 112, 117, 118, 121, 119, 116, 118, 118, 121, 112, 123,
118, 115, 117, 119, 119, 117, 116, 116, 118, 120, 118, 123, 116, 121, 116, 121,
114, 120, 113, 116, 121, 116, 120, 115, 115, 120, 118, 116, 121, 120, 119, 118,
121, 111, 119, 117, 118, 117, 121, 121, 120, 114, 118, 121, 117, 117, 115, 119,

And after 32,768 (#$8000) frames, the algorithm has gone the full circle ($18 now back to #$40, and $19 is #$00):

127, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
129, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,

As you can see the algorithm is very well distributed, no numbers are over- or under-represented. In fact, the only value to appear less frequently than the other numbers is zero (0), which is always seen one time less than the other numbers during a full circle (#$8000 frames). Now, with NTSC running at 60hz, this means that there is one less zero being generated per ~9 minutes, which will have negligible effect on the probability.

Money maker logic

The code that decides what Rupee has what value is ran once as you enter the game room, the only way to change the their value is to leave and re-enter the room. The values the Rupees are assigned are written to $448, $449 and $44a, representing the left, the middle and the right Rupee respectively. Let’s have a look at the actual code.

The game starts by figuring out what layout-configuration to use. The game always constructs the price array as { RND_LOSS, -10, WIN }, and then re-arranges it in accordance with the randomly chosen layout configuration.

01:864F    LDA #$FF
01:8651    LDY #$06
01:8653    CMP $0019
01:8655    BCC $865D
01:8657    SEC
01:8658    SBC #$2B
01:865A    DEY 01:865B    BNE $8653 

or, in Python:

v = 0xFF
config = 6
while v > 0:
    if v < seed[1]:
        break
    config -= 1
    v -= 0x2B

The above code computes what layout configuration to use. There are 6-possible outcomes (0-5). What layout configuration to use is based on what value-interval the byte at $19 has. The table below shows what layout the algorithm yields on what $19 value. Note that the probability for layout zero (0) to occur is slightly less than the rest of them.

Layout 0 - 0x00 to 0x28 (41 values)
Layout 1 - 0x29 to 0x53 (43 values)
Layout 2 - 0x54 to 0x7E (43 values)
Layout 3 - 0x7F to 0xA9 (43 values)
Layout 4 - 0xAA to 0xD4 (43 values)
Layout 5 - 0xFF to 0xD5 (43 values)
Having chosen what layout to use, the game then reads that configuration using this code:
01:865D    LDX $85CA,Y ; $85CA is shown below as start_offset
01:8660    LDY #$02    ; Number of bytes to copy
01:8662    LDA $85B8,X ; $85B8 is shown below as layout_config.
01:8665    STA $046C,Y ; Copy layout-configuration to $0x46C-0x46E (inclusive)
01:8668    DEX
01:8669    DEY
01:866A    BPL $8662

or, in Python:

start_offset  = [ 0x02, 0x05, 0x08, 0x0B, 0xE, 0x11 ]
layout_config = [ 
    0x00, 0x01, 0x02,
    0x01, 0x02, 0x00,
    0x02, 0x00, 0x01,
    0x00, 0x02, 0x01,
    0x02, 0x01, 0x00,
    0x01, 0x00, 0x02
]
offset = start_offset[config]
layout = layout_config[(offset - 2):(offset + 1)]

With the layout-configuration solved, the game proceeds to randomize what prices can be won using the following logic. Note that no value is represented as negative. When distributing your winnings, the game checks if the reward is 20, or 50, if it is not, the value is flipped to its negative counter-part. I.e. 40 becomes -40.

01:866C    LDA $001A
01:866E    AND #$01    ; A = seed[2] & 0x01 (== mod 2)
01:8670    TAY
01:8671    LDA $85B6,Y ; { 0x0A (10), 0x28 (40) }[A] 
01:8674    STA $046F   ; Either -10, or -40 (50% probability for each)
01:8677    LDA #$0A    ; Always one -10
01:8679    STA $0470
01:867C    LDY #$14    ; +20...
01:867E    LDA $001A   ; seed[2]
01:8680    AND #$02
01:8682    BEQ $8686
01:8684    LDY #$32    ; ...or +50... (again 50% for each)
01:8686    STY $0471

or, in Python:

prices = [
    -10 if 0 == (seed[2] & 0x01) else -40,
    -10,
     20 if 0 == (seed[2] & 0x02) else 50
]

In other words, there are always two losing Rupees and one winning.

  • One losing Rupee will be valued either -10 or -40, selected by a 50-50 chance based on the first bit in $1A.
  • One losing Rupee will always be -10.
  • The winning Rupee will be valued either 20 or 50, selected by a 50-50 chance based on the second bit in $1A.

The only thing remaining now, is to apply the layout-configuration to the generated prizes.

01:8689    LDX #$02
01:868B    LDY $046C,X ; Y = layout[X]
01:868E    LDA $046F,Y ; prize[Y]
01:8691    STA $0448,X ; final[X] = price[Y]
01:8694    DEX
01:8695    BPL $868B

or, in Python:

final = [ prices[it] for it in layout ]

Putting everything together

Looking at the layout code, we learn that in the layout_config array, a value of zero (0) means the random loss, a value of one (1) means -10, and a value of two (2) means the winning Rupee. Combining this knowledge with the layout-configuration tables from above, we end up with this:

layout_config = [
    # left    # middle  # right
    RND_LOSS, -10,      WIN,        # 41 / 256
    -10,      WIN,      RND_LOSS,   # 43 / 256
    WIN,      RND_LOSS, -10,        # 43 / 256
    RND_LOSS, WIN,      -10,        # 43 / 256
    WIN,      -10,      RND_LOSS,   # 43 / 256
    -10,      RND_LOSS, WIN         # 43 / 256
]

Looking at the table, the right Rupee is the worst, because one of its Win-conditions is in the lowest probability row. For the same reason, the left Rupee is the best, since it has its “Random Loss” (possibly -40 and thus worst) in the lowest probability row.

To make it even more clear:

Knowing the table above, let us compute the average value of each Rupee. For the right one, both its random losses are on the 43/256 probability rows, and the outcome is 50-50 between -10 and -40, yielding ((-10 + -40) / 2) * ((43 + 43) / 256) for the random loss column. Both -10 Rupees are in the 43/256 rows, so we get (-10) * ((43 + 43) / 256) for that one. The win Rupee, which is either 50 or 20 with 50-50 probability for each, is featured once in the 41/256 row, and once in the 43 / 256 row. So we get ((50 + 20) / 2) * ((41 + 43) / 256)) for the Win value.

Put everything together and we get this horrible mess:

((50 + 20) / 2) * ((41 + 43) / 256)
+ ((-10 + -40) / 2) * ((43 + 43) / 256)
+ -10 * ((43 + 43) / 256)
== -0.2734375

Applying the same logic to the other two Rupees gives us the following average Rupees won per position:

Left:   0.1953125
Mid:    0.078125
Right: -0.2734375

So, assuming my math is correct which it rarely is, the right one should lose over time, while the middle and left one should be winning.

I decided to run a simulation over all possible (0x8000) games to verify; counting the amount of Rupees won on each slot:

# Left, Mid, Right
[6430, 6400, -12830]

Checking against the math:

# For the left one, the predicted result is spot on.
0.1943125 * 0x8000 == 6400
# The middle one is ahead with a approximately twice what it should be.
0.078124 * 0x8000 == 2560
# The right Rupee is behind a lot more than predicted.
-0.2734375 * 0x8000 == -8960

The reason for the deviation from the predicted figures for the right and the middle Rupee is due to the seed “randomly” hitting the jackpot more often or less than it should. So essentially, the 50-50 assumption for the -10 vs. -40 and 20 vs. 50 is slightly incorrect for the middle and right one, due to where the seed is at when the given configuration is selected.

In fact, my simulation was ran from the start seed, and 0x8000 iterations forward. The left Rupee lucks out during this period, but since it is impossible to reach a store by that time, it is a bit miss leading. In fact, the best Rupee is the Middle one, which gains a total of 30 Rupees per 0x8000 games, unless from the first pass where the seed starts out initialized to mostly zero.

Based on output from a simulation counting the jackpot outcomes,

Left Rupee loses -40 32.821% of the time, and wins 50 49.996% of the wins.
Middle Rupee loses -40 32.817% of the time, and wins 50 49.997% of the wins.
Right Rupee loses -40 34.373% of the time, and wins 50 50.016% of the wins.

So yea, when ran for 1,000,000 games:

Left and middle one are still tied, and the right one is now approaching student-loan dept.

Conclusion

Not only is the right Rupee losing more frequently than the others, but it is also getting -40 2% more often when it does, and thus, the right Rupee is by far the worst Rupee to bet on. The left and middle one turns out to differ only very slightly, with the middle slightly ahead. The annoying part is that in my attempted play-through, I went for the middle one all three times…

Attached HERE is the complete python script (it is named .txt due to WordPress being paranoid).

Hydlide password generator

Hydlide

Hydlide is an adventure game for the Nintendo Entertainment System. Since I am currently not working, the amount of spare time is pretty grand, so I decided to reverse-engineer the password validation logic present in the game. The game itself is pretty boring to be honest…

Password Input

You enter the password by walking around with the little guy over the input grid, pressing ‘B’ for each character you wish to include. The password consists of 16 characters, selected from 0-9 and A-Z. As you input characters, they are written as standard ASCII to the zero-page, starting at address 0x15. For each character you write, the destination pointer is incremented, resulting in the full password residing from 0x15 to 0x24 (inclusive).

Entering a password.

 

Data at 0x15 when the password is entered.

Validation Phase #1

First the length is validated. The game allows you to hit end before entering all 16 characters.

Assuming the length is correct, the game converts the password from a readable ASCII-string to a binary representation, used internally to validate the password. First, each character that makes up the password is converted from ASCII to their equivalent binary representation. So ‘4’ becomes 4, and ‘D’ becomes 0x0D.

Once all characters are converted, they are used as an index into the table shown below:

static const uint8_t character_lookup[] =
{
  0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
  0x08, 0x09, 0xFF, 0x0A, 0xFF, 0x0B, 0xFF, 0xFF,
  0x0C, 0x0D, 0xFF, 0x0E, 0x0F, 0x10, 0x11, 0x12,
  0xFF, 0x13, 0x14, 0x15, 0xFF, 0x16, 0xFF, 0x17,
  0x18, 0x19, 0x1A, 0x1B
};

If a 0xFF is encountered during this phase, the password is immediately flagged as invalid. This means that the characters A, C, E, F, I, O, S and U never are allowed in a Hydlide password. Using the password XKMHTHMDLQX6G6T3, we would now have the binary representation:

19 0F 11 0D 16 0D 11 0B 10 14 19 06 0C 06 16 03

Validation Phase #2

From this point on, only the newly generated binary representation is used.

Phase #2 begins by subtracting all bytes in the password but the last one by the last one. If the resulting subtraction is negative, 0x1C is added to the subtracted value. Continuing with the same password where our last byte is 0x03, this phase would yield:

16 0F 0E 0D 13 0D 0E 0B 0D 14 16 06 09 06 13 [03]

Next, the second last byte is used, in our case 0x13. The value of the second last byte is used as the first index inside the table described below:

static const uint8_t encode_table[] = {
  0x04, 0x00, 0x00, 0x09, 0x02, 0x01, 0x05, 0x06,
  0x09, 0x02, 0x09, 0x07, 0x05, 0x07, 0x07, 0x06,
  0x00, 0x05, 0x02, 0x07, 0x07, 0x03, 0x01, 0x08,
  0x01, 0x06, 0x00, 0x05, 0x08, 0x07, 0x03, 0x02,
  0x01, 0x06, 0x07, 0x02
};

The game then iterates over all but the two last bytes of the password, subtracting the value found at the index (second last byte) inside the encode_table. For each iteration the index is incremented by one. Much like in the previous step; if the subtraction results in a negative value 0x1C is added. If the final value is greater than or equal to 0x10, the password is flagged as invalid and the validation aborts.

table_index = hp->bytes[HYDLIDE_PASSWORD_LENGTH - 2];

for(i = 0; i < (HYDLIDE_PASSWORD_LENGTH - 2); ++i, ++table_index)
{
  hp->bytes[i] -= encode_table[table_index];

  if(0x80 & hp->bytes[i])
  {
    hp->bytes[i] += 0x1C;
  }

  if(hp->bytes[i] >= 0x10)
  {
    return HYDLIDE_ERROR_PWD_BAD_CHARACTER;
  }
}

This is the last step in recreating the binary password representation, the data we are sat with now is the one used to restore the Hydlide game state.

With the finalized binary password, the game proceeds to validate its integrity using a simple checkum algorithm, where all bytes but the last three are added together. The resulting sum AND 0x0F is the checksum, which must match the third byte from the end of the password. If it doesn’t the password is flagged as invalid and validation is aborted.

checksum = 0;

for(i = 0; i < (HYDLIDE_PASSWORD_LENGTH - 3); ++i)
{
  checksum += hp->bytes[i];
}

if(hp->bytes[HYDLIDE_PASSWORD_LENGTH - 3] != (checksum & 0x0F))
{
  return HYDLIDE_ERROR_PWD_BAD_CHECKSUM;
}

Phase #3 – Restoring the game state

Restoring the game state is a matter of interpreting bits from the binary password and initializating the game state accordingly. Hydlide only makes use of the lower four bits from each bytes, this is why we saw the “abort if byte is >= 0x10”-check in Phase #2. The Hydlide game state is described in the struct below:

#define HYDLIDE_FAIRY_GREEN 0x00
#define HYDLIDE_FAIRY_WHITE 0x01
#define HYDLIDE_FAIRY_RED 0x02
#define HYDLIDE_NUM_FAIRIES 0x03
#define HYDLIDE_ITEM_SWORD 0x00
#define HYDLIDE_ITEM_SHIELD 0x01
#define HYDLIDE_ITEM_LAMP 0x02
#define HYDLIDE_ITEM_CROSS 0x03
#define HYDLIDE_ITEM_MEDICINE 0x04
#define HYDLIDE_ITEM_MAGIC_POT 0x05
#define HYDLIDE_ITEM_KEY 0x06
#define HYDLIDE_ITEM_JEWEL 0x07
#define HYDLIDE_ITEM_RING 0x08
#define HYDLIDE_ITEM_RUBY 0x09
#define HYDLIDE_NUM_ITEMS 0x0A
typedef struct hydlide_state
{
 //
 // Player position x & y [0x36, 0x37]
 //
 uint8_t x;
 uint8_t y;
 //
 // Current hp [0x38]
 //
 uint8_t hp_current;
 //
 // Strength [0x39]
 //
 uint8_t strength;
 //
 // Current mp [0x3B]
 //
 uint8_t mp_current;
 //
 // Character level [0x3C]
 //
 uint8_t level;
 //
 // Max hp & mp [0x41, 0x42]
 //
 uint8_t hp_max;
 uint8_t mp_max; 
 //
 // Map square [0x47, 0x48, 0x49]
 //
 uint8_t map_absolute;
 uint8_t map_x;
 uint8_t map_y;
 //
 // ?? set to !sword, !cross, !magic-pot, !jewel [0x4F, 0x52, 0x54, 0x56]
 //
 uint8_t unknown_4F;
 uint8_t unknown_52;
 uint8_t unknown_54;
 uint8_t unknown_56;
 //
 // ?? Set if !(has-ruby) && unknown73 [0x58]
 //
 uint8_t unknown_58;
 //
 // Inventory items [0x59 -> 0x62]
 //
 uint8_t iventory[10];
 //
 // ?? [0x63]
 //
 uint8_t unknown_63;
 //
 // Fairies in collected [0x64, 0x65, 0x66]
 //
 uint8_t fairy[3];
 //
 // ?? has all fairies? [0x67]
 //
 uint8_t unknown_67;
 //
 // ?? All set to the same as has key (chests individually locked?) [0x68->0x6F]
 //
 uint8_t unknown_68_6F[8];
 //
 // ?? [0x73, 0x74]
 //
 uint8_t unknown_73;
 uint8_t unknown_74;
 //
 // ?? same as lamp? some is_lit? [0x75]
 //
 uint8_t unknown_75;
}
hydlide_state_t;

To populate the Hydlide game state, the following interpretation of the binary password is used:

BYTE 12
Bit 0: fairy[HYDLIDE_GREEN_FAIRY]
Bit 1: fairy[HYDLIDE_WHITE_FAIRY] 
Bit 2: fairy[HYDLIDE_RED_FAIRY]
Bit 3: unknown_63
BYTE 11 Bit 0: hp_current bit 6
Bit 1: mp_current bit 6
BYTE 10
Bit 0: hp_current bit 5
Bit 1: mp_current bit 5
Bit 2: unknown_73
Bit 3: unknown_74
BYTE 9
Bit 0: hp_current bit 4
Bit 1: mp_current bit 4
Bit 2: map_absolut bit 5
Bit 3: inventory[HYDLIDE_ITEM_RUBY]
BYTE 8
Bit 0: hp_current bit 3
Bit 1: mp_current bit 3
Bit 2: map_absolut bit 4
Bit 3: inventory[HYDLIDE_ITEM_RING]
BYTE 7
Bit 0: hp_current bit 2
Bit 1: mp_current bit 2
Bit 2: map_absolut bit 3
Bit 3: inventory[HYDLIDE_ITEM_JEWEL]
BYTE 6
Bit 0: hp_current bit 1
Bit 1: mp_current bit 1
Bit 2: map_absolut bit 2
Bit 3: inventory[HYDLIDE_ITEM_KEY]
BYTE 5
Bit 0: hp_current bit 0
Bit 1: mp_current bit 0
Bit 2: map_absolut bit 1
Bit 3: inventory[HYDLIDE_ITEM_MAGIC_POT]
BYTE 4
Bit 0: x bit 4
Bit 1: y bit 4
Bit 2: map_absolut bit 0
Bit 3: inventory[HYDLIDE_ITEM_MEDICINE]
BYTE 3
Bit 0: x bit 3
Bit 1: y bit 3
Bit 2: level bit 3
Bit 3: inventory[HYDLIDE_ITEM_CROSS]
BYTE 2
Bit 0: x bit 2
Bit 1: y bit 2
Bit 2: level bit 2
Bit 3: inventory[HYDLIDE_ITEM_LAMP]
BYTE 1
Bit 0: x bit 1
Bit 1: y bit 1
Bit 2: level bit 1
Bit 3: inventory[HYDLIDE_ITEM_SHIELD]
BYTE 0
Bit 0: x bit 0
Bit 1: y bit 0
Bit 2: level bit 0
Bit 3: inventory[HYDLIDE_ITEM_SWORD]

Phase #4 – Finalizing the game state

Some portions of the game state is not stored within the password itself, but is rather computed from state values after the state has been loaded.

Strength, Max HP and Max MP

These are all based on the player level, and computed as follows:

temp = (state->level << 0x01);
temp = (temp + (temp << 0x02)) + 0x0A;
state->hp_max = temp;
state->mp_max = temp;

if(0 != state->iventory[HYDLIDE_ITEM_SWORD])
{
  temp += 0x0A;
}

state->strength = temp;

As you can see from the algorithm above, max HP, max MP and strength are all the same, unless you have the Sword in which case strength is increased by 10.

map_x & map_y

These values dictate at what map tile your player will start, and are computed using the following algorithm:

temp = state->map_absolute;

for(i = 0; i < 0x100; ++i)
{
  if(temp < 5)
  {
    break;
  }
  temp -= 0x05;
}

state->map_x = temp;
state->map_y = (uint8_t)(i & 0xFF);

Unknown values

Several of the unknown Hydlide state values are computed during this phase too, but since I have yet to understand what they are I will not include them here. Please refer to the source to see how they are initialized.

Phase #4 – Validating the game state

This is the last and final step before the game starts. Several integrity checks are performed to make sure that an invalid state has not made its way through all the security checks. If any one of these checks fail, the password is flagged as invalid and the game drops you back to the main screen.

Player position x & y

These must both be less or equal too 22. This is actually an error in the Hydlid code, as 22×22 will have your player spawn inside the HUD, use a max of 21 to ensure that you spawn inside the map.

Map absolute

Must be less than 0x23.

Player level

Must be less than 11.

Max HP & MP

Must both be less than or equal too 100, and can’t be greater than the current HP or MP respectively.

Key item

If you do not have the key, but you have either the Jewel or the Ring, the state is invalid.

Medicine item

If you have the medicine and unknown_63 is set, the state is invalid.

Unknown 67

If unknown_67 is not set, and you have medicine or unknown_63 is set, the state is invalid.

Cross item

If you don’t have the cross, but you do have the Lamp, the state is invalid.

Unknown 73

If unknown 73 is not set, but you have the Ruby, the state is invalid.

Unknown 67

If unknown_67 is not set, but unknown_73 is, the state is invalid.

Unknown 74

If unknown_74 is not set, but unknown_73 is, the state is invalid.

Code

Attached is proof-of-concept C application able to both validate and generate Hydlide passwords. Feel free to use it as you see fit 🙂

Sample output:

Password "NKLBGJWBK7QKD653" is VALID! :D
Player at : 13, 7
Health : 40 / 40
Magic : 40 / 40
Strength : 50
Level : 3
Map : 5 (0, 1)
Items : Sword, Lamp, Cross, Pot, Key, Jewel,
Fairies : Green,
Unknowns : 0x4F: 00 0x52: 00 0x54: 00 0x56 : 00 0x58 : 00
Unknowns : 0x63: 00 0x67: 00
[68...6F] : FF FF FF FF FF FF FF FF
[73...75] : 00 00 FF
## Regenerated password was "5KXNVH3KR0Q2Q7PG"

DownloadHydlide password validator & generator