+---------------------------------------------------------+
| Reverse Engineering of Casltevania II's Password System |
|               by Kingshriek (Dean Fehlau)               |
|           email: kingshriek at yahoo dot com            |
+---------------------------------------------------------+



1. Introduction

This document contains a reverse engineering of the password system in the US
version of Castlevania II: Simon's Quest (CV2). I'm not sure if the system is
the same in the European version. The Japanese release, 
Akumajou Dracula: Noroi no Fuuin was a Famicom Disk System game and saves
directly to disk so no password system was needed. 

It is assumed that the reader is familiar with binary and hexidecimal notation
and is comfortable converting both to and from decimal notation. It is also
assumed that the reader is familiar with basic logic operations (and, or, xor,
left shift, right shift). It will also be helpful if the reader has some
familiarity with 6502 assembly and how the CPU RAM is organized. 

The CV2 password saves the following information :

    1. Simon's experience level
    2. Number of game days that have elapsed
    3. Quantity of garlic and laurels
    4. Possession of quest items - Dracula's body parts and crystals
    5. Possession of other items - garlic, laurels, magic cross, silk bag
    6. Possession of use items - stake, flame, diamond, holy water, 3 daggers
    7. The whip that is in possession

The terms "quest items", "other items", and "use items" will be used throughout
the document. Please see the next section for an exact listing of what each 
category entails. The information above has been split up in this manner 
because each one of the seven categories corresponds to a byte that makes up 
the base password.



2. Notation

Before the password system can be discussed, the reader needs to be familiar 
with the notation used in the document.


    $zz or $zzzz - memory address ($xx is a zero-page address)
    0xzz - value in hexidecimal

    Operators (in order of precedence):

        + , -     Addition, Subtraction
        << , >>   Left Shift, Right Shift    <-------- done first
        &         Logical AND
        ^         Logical XOR    
        |         Logical OR    <-------- done last
        


3. How the password in generated

Before we get into the password generation algorithm, we need to know where and
how the game stores the seven categories of information listed above in memory.
Generally, for items that are stored by a single bit, a value of 1 means the 
item is in possession and a value of 0 means the item is not.

The adressess for this information are as follows:
$004A - use items
        bits (from highest order to lowest)
            7 - not used, keep set to 0
            6 - Oak Stake
            5 - Holy Flame
            4 - Diamond
            3 - Holy Water
            2 - Golden Dagger
            1 - Silver Dagger
            0 - Dagger
$004C - quantity of laurels (max. 8)
$004D - quantity of garlic (max. 8)
$0083 - time elapsed in game days (max. 9)
$008B - Simon's level (max. 6)
$0091 - quest items
        bits (from highest order to lowest)
            7 - not used, keep set to 0
            6 - Blue Crystal    ---+
                                   +--- set both to get the Red Crystal
            5 - White Crystal   ---+
            4 - Dracula's Ring
            3 - Dracula's Nail
            2 - Dracula's Eye
            1 - Dracula's Heart
            0 - Dracula's Rib
$0092 - other items
        bits (from highest order to lowest)
            7-4 - not used, keep set to 0
            3 - Garlic
            2 - Laurels
            1 - Magic Cross
            0 - Silk Bag
$0434 - whip (takes on values between 0 and 4)
            0 - Leather Whip
            1 - Thorn. Whip
            2 - Chain Whip
            3 - Morning Star
            4 - Flame Whip

In summary, the ranges for each value are:

    $004A   0x00-0x7F
    $004C   0x00-0x08
    $004D   0x00-0x08
    $0083   0x00-0x09
    $008B   0x00-0x06
    $0091   0x00-0x7F
    $0092   0x00-0x0F
    $0434   0x00-0x04

Now we can begin with the generation algorithm. The password generation code
begins at $AF21 in RAM. First, the game stores the contents of all the 
above addresses into the address range $0520-$0526. It does this in the 
following manner:

    $0520 = $8B    ; Simon's experience level
    $0521 = $83    ; Time elapsed in game days
    $0522 = $4C | $4D << 4    ; # of garlic and laurels (see note below)
    $0523 = $91    ; quest items
    $0524 = $92    ; other items
    $0525 = $4A    ; use items
    $0526 = $0434  ; whip

    note: # of garlic is stored in the upper 4 bytes of $522 whereas # of
          laurels is stored in the lower 4 bytes 

Next, checksums are computed and stored in $0527-$0528.

    $0527 = ($0520 + $0521 + $0522 + $0523 + $0524 + $0525 + $0526) & 0xFF00
    $0528 = ($0520 + $0521 + $0522 + $0523 + $0524 + $0525 + $0526) & 0x00FF

For randomization, the password generated uses a value from a counter that 
updates on every frame (the counter increments by 0x01 and goes through all
values 0x00-0xFF). The address of this counter is $1D. A "random" value 
used in password generation is stored in $0529 after some intermediate 
calculations, which are stored at $04F7 and $04F6.

The randomizer uses a lookup table for the upper 4 bytes of the $0529 byte.
The lower 4 bytes of $0529 is the same as the lower 4 bytes of the counter
value. Only a single counter value is used for the calculation of $04F7 and
$04F6 values.

The lookup table begins at $AF19 and is 8 bytes long.

    $AF19 - $AF20
    $AF10: xx xx xx xx xx xx xx xx xx 00 01 02 03 04 01 02 
    $AF20: 03 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx

Now for the randomization value code.

    $04F7 = $(0xAF19 + $1D & 0x07)
    $04F6 = $1D & 0x0F
    $0529 = $04F6 | $04F7 << 4

Next, a series of logical operations are performed on the bytes $0520-$0529
to generate the bytes $0530-$053F.

    $0530 = $0520 >> 3
    $0531 = ($0520 & 0x07) << 2 | $0521 >> 6
    $0532 = ($0521 & 0x3E) >> 1
    $0533 = ($0521 & 0x01) << 4 | $0522 >> 4
    $0534 = ($0522 & 0x0F) << 1 | $0523 >> 7
    $0535 = ($0523 & 0x7C) >> 2
    $0536 = ($0523 & 0x03) << 3 | ($0524 & 0xE0) >> 5
    $0537 = $0524 & 0x1F
    $0538 = $0525 >> 3
    $0539 = ($0525 & 0x07) << 2 | $0526 >> 6
    $053A = ($0526 & 0x3E) >> 1
    $053B = ($0526 & 0x01) << 4 | $0527 >> 4
    $053C = ($0527 & 0x0F) << 1 | $0528 >> 7
    $053D = ($0528 & 0x7C) >> 2
    $053E = ($0528 & 0x03) << 3 | $0529 >> 5
    $053F = $0529 & 0x1F

Next, the data in $0530-$53F is modified based on the random values
generated previously. Here, another look-up table is used -- this 
one containing 2-byte memory address stored with the lower-order 
byte first. Start at $B228 and add to the address itself the value 
at $04F6 shifted left by 1.  The address found in the look-up table
is stored at $10 and $11 with the same byte order. The table begins
at $B228 and is 32 bytes long.

    $B228 - $B247
    $B220: xx xx xx xx xx xx xx xx 48 B2 56 B2 64 B2 72 B2 
    $B230: 80 B2 8E B2 9C B2 AA B2 B8 B2 C6 B2 D4 B2 E2 B2
    $B240: F0 B2 FE B2 0C B3 1A B3 xx xx xx xx xx xx xx xx

At each address listed in the table above is a series of 14 bytes
used to XOR with the data at values $0530-$053D. 

    $B248 - 0E 01 0A 10 04 0F 18 1B 16 07 1E 12 11 1D
    $B256 - 04 0F 18 1B 16 07 1E 12 0B 12 02 03 11 1D
    $B264 - 0A 01 0E 10 04 0C 18 1B 16 07 0A 12 11 1D
    $B272 - 0E 0D 0A 1C 04 0D 1A 1B 06 07 1E 12 15 1D
    $B280 - 0E 11 0A 10 04 03 18 1B 16 07 12 12 11 1D
    $B28E - 13 09 0A 12 04 03 18 1B 12 07 16 0A 10 15
    $B29C - 02 0D 0A 12 04 0F 0A 1B 12 07 18 12 11 1D
    $B2AA - 00 1D 0A 18 04 0B 18 1A 14 07 1E 14 11 1D
    $B2B8 - 0E 0D 0E 12 0C 0F 1A 1B 16 07 1E 12 15 1D
    $B2C6 - 0E 01 0A 10 04 0F 18 1B 14 07 00 12 11 1D
    $B2D4 - 00 01 02 03 04 05 06 07 08 09 0A 0B 11 1D
    $B2E2 - 10 0D 0A 16 04 0F 18 1B 16 07 1E 12 1D 1D
    $B2F0 - 02 03 0A 12 04 0F 18 0B 16 07 06 16 01 1D
    $B2FE - 18 05 0A 1A 04 0D 18 1B 16 03 1A 16 17 15
    $B30C - 03 05 0A 02 04 0D 08 0F 1E 0B 12 16 11 04
    $B31A - 1E 05 0A 1A 07 0D 1A 1F 17 00 1A 16 16 15

The above is done by:

    for(i = 0x00; i < 0x0e; i++) {
        $10 = $(0xB228 + ($04F6 << 1))
        $11 = $(0xB229 + ($04F6 << 1))
        $053i = $053i ^ $($10 + ($11 << 2) + i)
    }

Now, the value stored at $04F7 is added to all the values
in the range $0530-$053D.

    for(i = 0x00; i < 0x0e; i++) {
        $053i = $053i + $04F7
    }

Finally, to get the actual bytes that correspond to the actual
password, add 1 to each of the bytes in the range $0530-$053F.
Store these values at $0540-$054F.

    for(i = 0x00; i <= 0x0f; i++) {
        $054i = $053i + 1;
    }

Now, all we need to know is the correspondence between the bytes
in $0540-$054F and the characters used in the password. Here is 
a table that shows the correspondence:

    A - 0x01     K - 0x0B     U - 0x15     4 - 0x1F
    B - 0x02     L - 0x0C     V - 0x16     5 - 0x20
    C - 0x03     M - 0x0D     W - 0x17     6 - 0x21
    D - 0x04     N - 0x0E     X - 0x18     7 - 0x22
    E - 0x05     O - 0x0F     Y - 0x19     8 - 0x23
    F - 0x06     P - 0x10     Z - 0x1A     9 - 0x24
    G - 0x07     Q - 0x11     0 - 0x1B
    H - 0x08     R - 0x12     1 - 0x1C
    I - 0x09     S - 0x13     2 - 0x1D
    J - 0x0A     T - 0x14     3 - 0x1E

The final password is the 16 characters given by the
correspondence in the table above in the same order as the bytes
in $0540 - $054F.



4. How the password is verified

Now that we know how to generate a password, lets go in reverse and
see how the game verifies user-inputted passwords. The password
verification code begins at $AD18 in RAM.

Using the character-hex value traslation table above, the inputted
password is translated into its hexidecimal equivalent and stored in
$0540-$054F. Next, subtract 1 from each value and store the result in
$0530-$053F respectively.

    for(i = 0x00; i <= 0x0f; i++) {
        $054i = $053i - 1;
    }

Next the intermediate "random values" are found from the bytes in
$053E and $053F.

    $04F6 = $053F & 0x0F
    $04F7 = ($053F & 0x10) >> 4 | ($053E & 0x07) << 1

Proceding backwards (relative to password generation), updated the
values in $0530-$053D by subtracting the value $04F7.

    for(i = 0x00; i < 0x0e; i++) {
        $053i = $053i + $04F7
    }

Next, use the look-up table starting at $B228 to find the XOR table
($B248-$B327) in the same way as the generation code.

    for(i = 0x00; i < 0x0e; i++) {
        $10 = $(0xB228 + ($04F6 << 1))
        $11 = $(0xB229 + ($04F6 << 1))
        $053i = $053i ^ $($10 + ($11 << 2) + i)
    }  

Now, we must perform the reverse logical operations to retireve the
base values used for the password, which are stored in $0520-$0529.

    $053x = $053x ^ ($10),x (1st 14 bytes)
    $0520 = $0530 << 3 | ($0531 & 0x1C) >> 2
    $0521 = $0531 << 6 | ($0532 & 0x1F) << 1 | ($0533 & 0x10) >> 4
    $0522 = $0533 << 4 | ($0534 & 0x1E) >> 1
    $0523 = ($0534 & 0x01) << 7 | ($0535 & 0x1F) << 2 | ($0536 & 0x18) >> 3
    $0524 = ($0536 & 0x07) << 5 | ($0537 & 0x1F)
    $0525 = $0358 << 3 | ($0539 & 0x1c) >> 2
    $0526 = $0539 << 6 | ($053A & 0x1F) << 1 | ($053B & 0x10) >> 4
    $0527 = ($053B & 0x0F) << 4 | ($053C & 0x1E) >> 1
    $0528 = ($053C & 0x01) << 7 | ($053D & 0x1F) << 2 | ($053E & 0x18) >> 3
    $0529 = $053E << 5 | ($053F & 0x1F)

For the password to be valid, $527 and $528 should be equal to the
checksums as computed in the password generation code. The game 
stores these values temporarily at $0E and $0F.

    $0E = $0527
    $0F = $0528

The game now computes the checksums as in the generation code.

    $0527 = ($0520 + $0521 + $0522 + $0523 + $0524 + $0525 + $0526) & 0xFF00
    $0528 = ($0520 + $0521 + $0522 + $0523 + $0524 + $0525 + $0526) & 0x00FF

If $0527 = $0E and $0528 = $0F, then all is good. If not, the
password is invalid.

A few more validations are necessary before the password is finally
okayed. What are they? If you guessed the bounds on the base values
at $0520-$0526, you are absolutely correct!

The bounds are as follows:

    $0520 must be < 0x07
    $0523 must be < 0x80 
    $0524 must be < 0x10
    $0525 must be < 0x80
    $0526 must be < 0x05
    $0521 & 0x0F must be < 0x0A
    ($0521 & 0xF0) >> 4 must be  < 0x0A 
    $0522 & 0x0F must be = 0x09
    ($0522 & 0xF0) >> 4 must be < 0x09

If all these checks are successful, the password is validated and the
game loads the bytes $0520-$526 into the respective places in memory.



5. Closing Notes

What is presented here is hopefully and complete and fully correct explanation
of how Castlevania II's password system is generated and verified; however, it
is most likely that I missed something or didn't explain something clearly. If
I'm missing something, or if something in this guide is incorrect or badly
explained, feel free to email me at kingshriek at yahoo dot com. Corrections,
additions, and constructive criticism will be greatly appreciated. Also, any 
worthy additions added to a future version of this document will be duly
credited to the information provider.

Thanks for reading.

eof