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

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

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"

Download: Hydlide password validator & generator