Castlevania III Password Algorithm

Castlevania III
Password Algorithm

Name-and-Password System · Special Names · Game State
Name Hash · Payload · Encoding · Decoding · All Passwords · Code

This article explains the mechanism Castlevania III: Dracula’s Curse uses to save and restore game state through the medium of passwords. This discussion covers the North American and PAL NES versions, not the Japanese Famicom version, Akumajō Densetsu.

Name-and-Password System

Castlevania III uses a combined name-and-password system. At game start, the game prompts the player to enter a name:

A name contains eight characters; the game right-pads shorter names with spaces. The available character set includes the upper-case letters of the English alphabet, space, exclamation mark, question mark, and period. A completely blank name (eight spaces) is valid.

At game over, the game offers the player a choice: immediately continue from the last save point or encode the game state to a password, enabling play to resume sometime in the future.

When the player selects “PASSWORD”, the game displays a screen like the one below.

This example uses the name “EXAMPLE”; the game shows it in the box at the top of the screen. A horizontal table below the name lists the password marks: blank, whip, rosary, and heart. The password, a 4×4 matrix, appears below the table. Each element holds one mark. Passwords tend to be sparse matrices.

To persist the game state, the player writes the name and password on paper. The player can then turn off the NES, which clears system memory and the game state with it.

To restore the game state, the player selects “PASSWORD” from the title screen:

The game then prompts the player to enter the name associated with the password.

Next, the game displays the password entry screen:

The screen displays two cyan cursors, one for selecting the mark from the horizontal table and the other for placing the mark in the password matrix. The following image shows an entered password.

When the player enters the password correctly, the game resumes from the save point. Even a small error produces the following message.

A misplaced mark, a forgotten name, or a transcription mistake typically causes this. The password remains bound to the name entered at game start.

Special Names

Five special names affect gameplay:

Despite what the Angry Video Game Nerd demonstrates in his Castlevania (Part 2) video, “HELP ME” contains a space.

The “OKUDA”, “URATA”, and “FUJIMOTO” special names start Normal Mode with a partner and force the player to keep that partner for the rest of the game. Hard Mode likewise disables partner exchanges. “AKAMA” forces the player through Hard Mode alone.

Some websites claim that using the name “GAMETEAM” with a special password starts the player in Hard Mode and eventually reveals the real ending credits. The alternate credits do reveal the actual team that made the game, but the name-and-password combination has no special property. The game rewards the player with the alternate credits for beating Hard Mode, regardless of the name. The alternate credits also reveal the origin of the special names:

Game State

Passwords store save point, partner, and mode. When the player continues after game over, the game retains only those properties and resets everything else.

Save Points

After losing all lives, the player falls back to the most recent save point. Usually, this restarts the current block (the level) from its beginning. Shortcuts and sub-bosses create exceptions, as the table below shows.

The game has eighteen save points, indexed $00–$11. The game never names the places and bosses; descriptions vary from source to source. By contrast, the HUD displays block and sub-block values. All blocks start with a sub-block of 1 or A, except for the Forest of Darkness, which the player may enter from save points $03 or $04:

Two other save points, $02 and $0A, start mid-block due to sub-bosses:

Save points $0B and $0C share common block values, but they lead to two completely different levels:

Partner

The partner field uses four values, indexed 0–3:

In Normal Mode, without a special name, the game accepts a partner only along a pathway of save points that starts when the player first encounters that partner. During password decoding, the decoder checks the save point and partner combination against the table below. If the combination fails, the decoder rejects the password.

The decoder skips this check for special names other than “HELP ME”. The remaining special names lock the game into a specific partner from the beginning, or in the case of “AKAMA”, no partner.

In addition, the decoder always uses the partner encapsulated in the password, not necessarily the one associated with a special name. For example, if the player starts a new game with “OKUDA”, the player immediately gets stuck with Alucard. However, someone can construct a valid password for “OKUDA” for any partner at any save point and mode. Normal gameplay would never display such a password, but the game accepts it.

The same applies to “AKAMA”, but the game always uses Hard Mode, regardless of the mode encapsulated in the password.

Mode

The mode field uses two values, indexed 0–1:

After the player beats the game in Normal Mode, the game restarts in Hard Mode, which increases the difficulty from the get-go. More enemies spawn. They move faster. They cause more damage. The image below compares one of the first screens in Normal Mode on the left with its Hard Mode counterpart on the right.

The partner paired with the player at the end of Normal Mode carries over into Hard Mode. However, Hard Mode disables partner exchanges; the player remains stuck with the same partner indefinitely, or no partner at all if the player beat Normal Mode alone.

After the player beats the game in Hard Mode, the game restarts without advancing to another difficulty. Hard Mode loops endlessly; the game has only two modes.

Name Hash

The password stores only a 3‑bit hash of the name, not the entire 8-character name. To compute the hash, the game adds 4 to the sum of all character values, then reduces the result modulo 8 to produce a value in the range 0–7:

Interestingly, the game code uses a table to add different constants to the running sum based on the index of the loop:

; hashName()
; out: A = name hash (0--7)
03:B6CD  LDA #$00
03:B6CF  STA $0000    ; sum = 0;
03:B6D1  TAX
03:B6D2  LDA $07F8,X  ; for (X = 0; X < 8; ++X) {
03:B6D5  CLC
03:B6D6  ADC $B6E6,X
03:B6D9  CLC
03:B6DA  ADC $0000
03:B6DC  STA $0000    ;     sum += name[X] + NAME_HASH_SEEDS[X];
03:B6DE  INX
03:B6DF  CPX #$08
03:B6E1  BNE $B6D2    ; }
03:B6E3  AND #$07     ; A = sum % 8;
03:B6E5  RTS          ; return;

; NAME_HASH_SEEDS
; Due to the modulo operation, this table is pointless; the values can be tallied ahead of time. However, the
; intention may have been to apply this table only to the nonblank characters. But that check is not there.
03:B6E6  .byte $07, $03, $01, $06, $02, $04, $05, $00        

As the comment notes, the table does not need to exist; the code could add the constants ahead of time. The developers may have intended to add constants only for nonblank characters, but the code never performs that check.

The game uses Pattern Table tile indices as character values. As shown below, A–Z, followed by exclamation mark and question mark, map to $50–$6B. Period maps to $4B, and space maps to $00.

The game hashes special names the same way as any other name. It also hashes a blank name, represented as 8 spaces, the same way.

Payload

The password encapsulates a 1-byte payload and a 1-byte payload hash.

Contents

The payload byte contains the mode (bit 0), the partner (bits 1–2), the toggle mask index (bit 3), the least significant bit of the save point (bit 4), and the name hash (bits 5–7):

76543210
--------
NNNSTPPM
││││││││
│││││││└─ mode
│││││└┴── partner 
││││└──── toggle mask index
│││└───── save point bit-0
└┴┴────── name hash

The toggle mask index depends on frame timing during password generation, making it effectively random from the player’s perspective. The game uses it when computing the payload hash. Two possible values produce two valid passwords for a given name, save point, partner, and mode. For example, if the player starts a new game with a blank name and repeatedly reaches game over in the first block, the game will eventually reveal a pair of equivalent passwords:

Hash

The payload hash safeguards the integrity of the payload. During decoding, the game uses it to detect errors introduced while the player wrote down or entered the password. It also makes valid passwords exceedingly difficult to guess.

The game computes the payload hash as follows:

1. The game treats the upper and lower nibbles of the payload byte as 4‑bit integers and adds them together:
   nibbleSum = 0x0F & ((payload >> 4) + payload);
2. If the toggle mask index equals 0, the game toggles the even bits of the payload byte (0 ➔ 1 and 1 ➔ 0 for bits 0, 2, 4, and 6). It does this by XORing with $55:
   toggledPayload = payload ^ 0x55;
   Otherwise, the game toggles the odd bits by XORing with $AA:
   toggledPayload = payload ^ 0xAA;
3. The game treats the upper and lower nibbles of the toggled payload byte as 4‑bit integers and adds them together:
   toggledNibbleSum = 0x0F & ((toggledPayload >> 4) + toggledPayload);
4. The game combines the two 4‑bit sums into a byte by treating the first sum as the upper nibble and the second sum as the lower nibble:
   sums = (nibbleSum << 4) | toggledNibbleSum;
5. The game adds the save point and the sums byte, producing the 8‑bit payload hash:
   payloadHash = 0xFF & (savePoint + sums);

These steps define a checksum-like hash function. The hash helps verify the payload, but it does not contain enough information to recover the payload uniquely.

String Representation

Within the password matrix, an 8-mark string represents the payload and its hash. Each mark holds a 2‑bit value that the table below interprets.

Within the string representation, the i^th mark combines the i^th bit of the payload byte and the i^th bit of the hash byte. The payload supplies the high bits, and the hash supplies the low bits. Together, those bits form one mark.

Encoding

Encoding converts a name and game state into a password. The encoder performs these steps:

1. The encoder hashes the name.
2. The current frame counter supplies the toggle mask index.
3. The encoder bitwise concatenates the name hash, bit‑0 of the save point, the toggle mask index, the partner, and the mode to form the payload.
4. The encoder hashes the payload.
5. The encoder converts the payload and its hash into a string of 8 marks.
6. The encoder divides the save point by 2 (shifted-right by 1). This produces a value in the range 0–8, which the table below expresses as a mark in the password matrix.
   
7. The encoder places the initial mark in one of three places:
   
   Each place starts one of the following scramble sequences.
   
   The encoder fills elements 1–8 of the scramble sequence with the 8 marks produced from the payload and its hash. Since that string includes blanks and only 9 of the 16 matrix elements get marked, passwords tend to be sparse matrices.

Decoding

Decoding converts a name and password into a game state. The decoder performs these steps:

1. The decoder hashes the entered name.
2. A valid password places a nonblank mark in exactly one of the places shown below.
   
   If more than one of those places contains a nonblank mark or all three are blank, the decoder rejects the password.
3. The decoder uses the table below to convert the nonblank mark into a value in the range 0–8.
   
   The decoder sets the save point to twice that value.
4. That nonblank mark starts one of the following scramble sequences.
   
   In a valid password, the seven elements of the password matrix not included in the scramble sequence must remain blank. If any of them contain marks, the decoder rejects the password.
5. The decoder creates a string of eight marks from elements 1–8 of the scramble sequence.
6. The decoder derives the payload and payload hash from the high and low bits of the marks in the string, respectively.
7. If payload bit‑4 is set, the decoder increments the save point.
8. The decoder extracts the mode, the partner, and the name hash from the payload.
9. The decoder compares the entered name against the special names, except for “HELP ME”. If the name does not match one of the remaining special names and the mode equals Normal, the decoder validates the save point and partner combination. A partner can appear only along a pathway of save points that starts when the player first encounters that partner. If the combination fails, the decoder rejects the password.
10. The decoder compares the hash of the entered name against the hash extracted from the payload. If they fail to match, the decoder rejects the password.
11. The decoder hashes the payload and compares the result against the payload hash extracted from the password. If they fail to match, the decoder rejects the password.

All Passwords

This site includes the unabridged table of all 3,294 valid name-and-password combinations.

The table uses one column per save point and one row per unique combination of name, partner, toggle mask index, and mode. Because the game hashes the name to a 3‑bit value, the hash yields only eight name classes. The shortest names that cover all classes are blank and B–H, as the table below shows. These names appear at the left of each row.

The table includes the special names because they modify the behavior of the game.

White names and red names indicate Normal Mode and Hard Mode, respectively. “AKAMA” appears only in red because it imposes Hard Mode regardless of the mode encapsulated within the password. The table still includes “AKAMA” passwords that encapsulate Normal Mode for completeness, because those passwords remain valid.

The sprites at the left of each row indicate the partner.

Trevor’s facing direction indicates the toggle mask index: right means 0, and left means 1. Toggle mask index does not affect gameplay, but it doubles the number of valid passwords.

The gaps in the table correspond to invalid save point and partner combinations. In Normal Mode, without a special name, the game accepts a partner only along a pathway of save points that starts when the player first encounters that partner.

Special names other than “HELP ME” lock the player into a particular partner. However, the partner encoded in the password takes precedence over the one associated with the special name. As a result, the table shows the special names with all partner combinations.

Code

For more details, see the annotated assembly segments related to password encoding and decoding. The castlevania3-passwords repository also contains a copy.

The repository also includes the Java program that generated the unabridged password table.