+-----------------------------------------------------------------------------+
|    Reverse Engineering of Adventures of Lolo 3's Password System v. 0.98    |
|                         by kingshriek (Dean Fehlau)                         |
|                     email: kingshriek at yahoo dot com                      |
+-----------------------------------------------------------------------------+

The document is organized into sections and subsections in the following way.

    1. Introduction
    2. Notation
    3. Password Generation
        3.1. Memory Locations
        3.2. Reading the Data
        3.3. Compressing the Data
        3.4. Calculating the Checksum
        3.5. The Random Number Generator
        3.6. Encrypting the Data 
        3.7. Unpacking the Data
        3.8. Transcribing the Password
    4. Password Verification
        4.1. Checking the Data
        4.2. Packing the Data
        4.3. Decrypthing the Data
        4.4. Checksum Comparison Test
        4.5. Decompressing the Data
        4.6. A Little Fixing Up
    5. Example of Password Generation
        5.1. Initial Data
        5.2. Example - Compressing the Data
        5.3. Example - Checksum and Random Value
        5.4. Example - Encrypting the Data
        5.5. Example - Unpacking the Data
        5.6. Example - Transcribing the Password
    6. Closing Notes
    A. Appendix A - Update History
    B. Appendix B - Password List and Miscellaneous Facts
    C. Appendix C - C code for password generator/verifier      

In the document are also tables and snippets of C-like code. They are labeled
Table x.y and Code x.y respectively, where x is the section number and y means
it's the yth table or code in the section.


+-----------------------------------------------------------------------------+
| 1. Introduction                                                             |
+-----------------------------------------------------------------------------+

This document contains a reverse engineering of the password system used in
Adventures of Lolo 3. It also works in the game's Japanese counterpart,
Adventures of Lolo 2 (J). The password system used in the game is far more
complicated than the previous Lolo titles, which used 4-letter passwords
that followed a very noticeable pattern. The passwords in Lolo 3 contain
16 characters (alphanumeric and some special ones), and have built into
them a checksum and a randomizer.

It should be noted that the game contains some special, built-in passwords
(see Appendix B) that are completely outside of the password system. They all 
fail the game's and verification check and only serve to do interesting things 
on the password screen such as playing different background music or displaying 
different characters/monsters from the game. 

If you are more interested in the passwords themselves than the process of 
generating and verifying them, feel free to head down to Appendix B, which has
a list of passwords to all the levels of the game. The special, built-in
passwords are listed here as well.

For the readers that are interested in the password system, it is assumed that 
you are familiar with binary and hexadecimal notation and are comfortable 
converting both to and from decimal notation. It is also assumed that you are 
familiar with basic logic operations (AND, OR, XOR, left shift, right shift). 
Knowing some C and being familiar with its syntax will help you better 
understand this document, but it shouldn't be necessary. It will also be 
helpful if you have some familiarity with 6502 assembly and how the NES CPU 
RAM is organized.

I have also included in this document source code for a simple console 
program that generates and degenerates the passwords of Adventures of Lolo 3.


+-----------------------------------------------------------------------------+
| 2. Notation                                                                 |
+-----------------------------------------------------------------------------+

Before the password system can be discussed, the reader needs to be familiar 
with the notation used in the document. I tried to use C syntax as much as
possible. The code snippets in the document are pretty much C, aside from
some shorthand addressing I put in (I hope it's easy to understand).

    
    Data representation ('.' is a placeholder for a digit):

        $.. or $....     memory address ($xx is a zero-page address)
        0b........       value in binary
        0x....           value in hexadecimal

    Bit order (in a byte, from highest to lowest order):

         highest                                                  lowest
        +-------+-------+-------+-------+-------+-------+-------+-------+
        | bit 7 | bit 6 | bit 5 | bit 4 | bit 3 | bit 2 | bit 1 | bit 0 |
        +---------------------------------------------------------------+
        

    Operators (in order of precedence):

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

    The characters for the password use some non-standard characters. This
    document will use other characters in their place.

    Non-standard characters:

        +            (cross)
        @            (heart)
        $            (diamond)
        &            (triangle)

        The symbols '$' and '&' here are not to be confused with the address
        symbol '$' and the operator '&'. The meaning of these at each place
        where they are used should be obvious to the reader.  


    In all code sections, the variable 'A' refers to the accumulator
    register in the CPU.



+-----------------------------------------------------------------------------+
| 3. Password Generation                                                      |
+-----------------------------------------------------------------------------+

This section will describe how the game generates a password when the player
presses the start button on the map screen. 

The generation algorithm, which begins at $9AFD in PRG-ROM, uses 5 subroutines.

    1. Read data in $0151-$0159, $014F, $52, compress, and store in $DF-$E6
    2. Calculate checksum and store in $E7
    3. Generate a random value based on the values at $2C and $2D and store in 
       $E8
    4. Encrypt the data in $DF-$E8
    5. Unpack the data in $DF-$E8 into $E9-$F8, where the password is stored

As for a less detailed and easier to remember description,

    1. compress
    2. checksum
    3. randomize
    4. encrypt
    5. unpack 

The Lolo 3 password saves the following information:

    1. The character that you are using (Lolo or Lala)
    2. The area of the game which you are at
    3. The floors that you have cleared on each level

Before we explore password generation algorithm, we need to know where and how
the game stores the information listed above in memory.

+-----------------------+
| 3.1. Memory Locations |
+-----------------------+

The addresses for the information stored in the password are as follows:

$52 - Character
    Character data is stored in bits 0 and 4. Bit 0 determines whether Lolo
    or Lala is selected. Bit 4 determines if Lolo and Lala are together or
    if the selected character is alone. The other bits are set to 0b0 under
    normal gameplay circumstances. The game ignores them anyway. In summary,

        0x00 - Lolo, 0x01 - Lala    if both Lolo and Lala are together
        0x10 - Lolo, 0x11 - Lala    if alone

$014F - Location 
    Location data is stored in bits 0-4. Bits 5-7 are set to 0b0 under
    normal gameplay circumstances. The game ignores these bits. There are 19 
    valid locations - Levels 1 through 17 and the two Grandpa's Tree training 
    levels. Thus, in normal gameplay $014F has a value in the range 0x00-0x12.
    Here's a list of valid location values for $014F:

        0x00 - Grandpa's Tree 1
        0x01 - Grandpa's Tree 2
        0x02 - Level 1
        0x03 - Level 2
        0x04 - Level 3
        .
        .
        .
        0x12 - for Level 17

    Each of these locations resides in of the game's 3 map areas - the
    Overworld, the Underwater World, and the Underworld. The Overworld is a
    2-screen map, whereas the Underwater World and Underworld are 1-screen
    maps. Level 3 is split between the two screens of the Overworld. Here's a
    list of areas and levels contained within:

        Overworld (left screen) - Levels 1-3
        Overworld (right screen) - Levels 3-8
        Underwater World - Levels 9-13
        Underworld - Levels 14-17

    0x13, while not a valid location value the game will generate,
    corresponds to the right screen portion of Level 3 (0x04 corresponds to
    the left screen portion), but is only tied to the coordinates there.
    If you create a password with this value (as you have to, the game won't 
    generate one), the game will try to place you in the Underworld with 
    these coordinates. Since the Underworld is only a 1 screen map, you will 
    be placed to the right and off of the map! 0x14-0x1F will remove you from
    the map completely!

$0151-$0159 - Level Completion Data
    Each byte corresponds to a set of 2 adjacent (in number) levels. Bits 4-7
    correspond to the earlier of the two levels and bits 0-3 correspond to
    the later of the two levels. $159 only contains one level, Level 17, 
    which is placed in bits 4-7. The lower 4 bits are not used. In summary,

        $0151 - Levels 1 & 2
        $0152 - Levels 3 & 4
        $0153 - Levels 5 & 6
        .
        .
        $0158 - Levels 15 & 16
        $0159 - Level 17

    For floors, the current floor you are on at each level is stored in the
    set of 4 bits that correspond to the level. Thus, someone at Level 1,
    Floor 4 and Level 2, Floor 3, would have 0x43 as the value for $151.
    Special rooms where you get/use items or fight bosses use the value 0x0.
    If the level doesn't have a special room or boss (Levels 8,14,15,16),
    then you won't be able to enter the level. Thus, 0x00 at $153 would 
    place you at the bosses of Levels 5 & 6. Level completion is denoted by 
    0xF. In the course of normal gameplay, completion status is not given
    for Level 13 (as the boss defeats you instead). Therefore, right after
    finishing Level 13, bits 4-7 of $157 are 0x0. Also, since Level 17 is 
    the final level, it is impossible in normal gameplay for the higher 4 
    bits of $159 to have the value 0xF. If these levels are set to 0xF, they 
    won't be destroyed (as there aren't graphics for this in the game) and 
    they will be impossible to enter. In summary,

        0x0 - Special or boss room (except for Levels 8,14,15,16)
        0x1 - Floor 1
        0x2 - Floor 2
        0x3 - Floor 3
        .
        .
        .
        0xA - Floor 10
        0xF - Level completed (except for Levels 13 and 17)

$0150 contains the information for what floors are cleared in the Grandpa's
Tree training levels. It is done so in the same way as in $0151-$0159. The
password does not save this information, hence why it's not listed up above.

+-----------------------+
| 3.2. Reading the Data |
+-----------------------+

In order to read the data needed for the password, the game makes use of a 
80 byte table at  values at $9A29-$9A79, which is provided below (values 
are in hex).


                 Table 3.1 - Table used for reading data

    +----------------------------------------------------------------------+
    |                            $9A29-$9A79                               |
    +----------------------------------------------------------------------+
    | $9A20: xx xx xx xx xx xx xx xx xx 01 51 06 03 01 51 02               |
    | $9A30: 03 01 52 07 04 01 52 02 03 01 53 06 03 01 53 02               |
    | $9A40: 03 01 54 06 03 01 54 02 03 01 55 06 03 01 55 02               |
    | $9A50: 03 01 56 06 03 01 56 02 03 01 57 07 04 01 57 02               |
    | $9A60: 03 01 58 06 03 01 58 02 03 01 59 07 04 01 4F 04               |
    | $9A70: 05 00 52 04 01 00 52 00 01 FF xx xx xx xx xx xx               |
    +----------------------------------------------------------------------+
    | $9A29-$9A2C: 01 51 06 03    Level  1,       $0151H,  5 floors        |
    | $9A2D-$9A30: 01 51 02 03    Level  2,       $0151L,  5 floors        |
    | $9A31-$9A34: 01 52 07 04    Level  3,       $0152H, 10 floors        |
    | $9A35-$9A38: 01 52 02 03    Level  4,       $0152L,  5 floors        |
    | $9A39-$9A3C: 01 53 06 03    Level  5,       $0153H,  5 floors        |
    | $9A3D-$9A40: 01 53 02 03    Level  6,       $0153L,  5 floors        |
    | $9A41-$9A44: 01 54 06 03    Level  7,       $0154H,  5 floors        |
    | $9A45-$9A48: 01 54 02 03    Level  8,       $0154L,  5 floors        |
    | $9A49-$9A4C: 01 55 06 03    Level  9,       $0155H,  5 floors        |
    | $9A4D-$9A50: 01 55 02 03    Level 10,       $0155L,  5 floors        |
    | $9A51-$9A54: 01 56 06 03    Level 11,       $0156H,  5 floors        |
    | $9A55-$9A58: 01 56 02 03    Level 12,       $0156L,  5 floors        |
    | $9A59-$9A5C: 01 57 07 04    Level 13,       $0157H, 10 floors        |
    | $9A5D-$9A60: 01 57 02 03    Level 14,       $0157L,  5 floors        |
    | $9A61-$9A64: 01 58 06 03    Level 15,       $0158H,  5 floors        |
    | $9A65-$9A68: 01 58 02 03    Level 16,       $0158L,  5 floors        |
    | $9A69-$9A6C: 01 59 07 04    Level 17,       $0159H, 10 floors        |
    | $9A6D-$9A70: 01 4F 04 05    Location data,  $014F (bits 0-4)         |
    | $9A71-$9A74: 00 52 04 01    Character data, $52, (bit 4)             |
    | $9A75-$9A78: 00 52 00 01    Character data, $52, (bit 0)             |
    |                                                                      |
    | In the level addresses,                                              |
    |     H - bits 4-7          L - bits 0-3                               |
    |                                                                      |
    +----------------------------------------------------------------------+

The bytes in the table are in sequences of four, i.e. (01 51 06 03),
(01 51 02 03), (01 52 07 04), etc. where each sequence corresponds
to an information entry that the password stores.

The first 2 bytes are the address of the memory from which information for
password generation is received (the information that's stored in the
password). These 2 bytes are ordered with the higher order byte first. Thus, 
the first  2 bytes in the table give the address $0151. Recall that
$0151-$0159 are level addresses and that only bits 4-7 of $0159 are used (for 
Level 17). Also, recall that bits 0-4 of $014F correspond to location data and 
that bits 0 and 4 of $0052 correspond to character data. 

The 3rd byte gives the number of the highest order bit (in the bit order) 
used in the data stored at the address given by the first 2 bytes.

The 4th byte gives how many bits are used to store the information. So, for 
level data, levels with 5 floors need 3 bits and levels with 10 floors need 
4 bits. The location data needs 5 bits and each set of character data needs 
1 bit.

+---------------------------+
| 3.3. Compressing the Data |
+---------------------------+

Right now, the information that's needed for the password is somewhat sparse, 
meaning that not all the bits in each byte have useful information. For
example, character data only needs 2 bits, but it's currently being stored
with 2 sets of 4 bits (a byte). It would be nice to compress this data so 
that only the useful bits are stored, and that's exactly what the game does.

The game does this by sequentially loading the required information into an
8-byte shift register, which is located at $DF-$E6. The data is loaded into 
bit 7 of $E6 and shifted left until the shift register holds all of it. In  
the process of compression, the game refers to the table starting at $9A29
(Table 3.1). Given by the table, address $0151 is loaded first, followed by 
$0152-$0159, and then finally $015F and $52. 

The game then stores the requested data, the byte given by each address in 
the table, into the accumulator (an 8-bit register on the CPU, denoted by A 
in the code examples). Here, the data only occupies the lower order bits and 
needs to be shifted all the way to the left so that it is in position to be 
loaded bit by bit into the shift register. The 3rd byte in each 4-byte 
sequence in the table gives the position of the highest order bit of the data 
to be loaded. Thus, the number of times the data needs to be shifted in the 
accumulator is given by subtracting this bit position from 7 (since the 
accumulator is an 8-bit register). Thus, the number of times needed to shift 
the data is determined by the 3rd byte in each 4-byte sequence in the table 
(hence, why data stored on the lower 4 bits of a byte have a value that is 4 
higher than the data stored on the higher 4 bits).

The number of times to shift the data through the shift register is given by
the 4th byte in the 4-byte sequence, which stores how many bits the
information takes up. 

Hence, this subroutines compresses the data by storing only useful 
information in the shift register.

The above is summarized by the following code.


                    Code 3.1 - compression subroutine

    $E6 = 0x00;
    for(x=0x9A29; x<=0x9A79; x+=4) {    // run through data in table
        y1 = $x & 0xFF00;    // upper byte of address
        y2 = $(x+1) & 0x00FF;    // lower byte of address
        A = $(y1+y2);    // addresses for password information
        ns = $(x+2);
        ns = 7 - ns ;   // number of times to left shift the accumulator
        nr = $(x+3);    // number of times to left shift through $DF-$E6
        A = (A << ns) & 0xFF;    // shift data into loading position
        for(i=0; i<nr; i++) {
            carry[0xE7] = (A & 0x80) >> 7;    // carry from A into $E6
            A = (A << 1) & 0xFF;
            for(y=0xE6; y>=0xE0; y--) {    // shift data through $DF-$E6
                carry[y] = ($y & 0x80) >> 7;  // carry from $y into $(y-1)
                $y = ($y << 1) & 0xFF;
                $y += carry[y+1];
            }
            $DF = ($DF << 1) & 0xFF;
            $DF += carry[$E0];
        }
    } 

+-------------------------------+
| 3.4. Calculating the Checksum |
+-------------------------------+

Once the compression is finished, a checksum calculation subroutine
is entered. The lowest byte of the sum of the bytes $D9-$E6 is stored in
$E7. That is,

                    Code 3.2 - checksum subroutine

    $E7 = ($D7 + $E0 + $E1 + $E2 + $E3 + $E4 + $E5 + $E6) & 0xFF;


+----------------------------------+
| 3.5. The Random Number Generator |
+----------------------------------+

$E8 is the next value that needs to be computed. $E8 is given by a
pseudorandom number generator (RNG). The RNG is in the form of a three-tap 
linear feedback shift register (LFSR).

If you are creating your own password, you can skip this step, as the
value it affects can be anything without affecting the validity of the
password. This is just how the game actually generates passwords and it's
only included for completeness.

The game uses $2D and $2C in RAM for the shift register, where $2D is of
higher order than $2C. Both addresses are initialized to an unknown value 
and are updated 11 times when the player requests a password (pressing Start 
on the map screen). After these 11 iterations, the value of $2C is stored in
$E8. $2C and $2D are only initialized at power-on, i.e. resetting the game 
doesn't change their values. The taps are at bits 15, 1, and 0.

In binary, the RNG satisfies the reccurence relation:

    b[n] = !(b[n+16] ^ b[n+2] ^ b[n+1])

Below is a diagram of the RNG:


              Figure 3.1 - Random Number Generator


                    $2D                       $2C
        +-------------------------+-------------------------+    
   <----  15 14 13 12 11 10  9  8    7  6  5  4  3  2  1  0  <-----+  
        +-------------------------+-------------------------+      |
           |                                           |  |        |
           |                                     +-----+  |        |
           |                                     |        |        |
           |                                     v        v        |
           +----------------------------------->(+)----->(+)----->(o)


                                                 (+) XOR
                                                 (o) NOT


It would be nice to know a few things about the RNG, such as if it
generates all the values between $0000 and $FFFF for $2C-2D. Also, since
the RNG is completely deterministic, it will have to repeat itself
eventually. How many iterations are needed for this to happen (the RNG's
period)?

Since there are an odd number of taps, if the NOT were removed, the RNG 
would preserve either an even number or an odd number of set bits (equal 
to 0b1) amongst $2C-$2D and the new bit that is added to the shift
register. What the NOT does is switch between an even number and an odd 
number of set bits in these 17 bit locations after each iteration. We 
will need this fact later in the determination of the period. 

From the taps, the feedback polynomial is x^16 + x^2 + x + 1. On the
integer ring Z(mod 2), this factors into x + 1 and
x^15 + x^14 + x^13 + ... + x^4 + x^3 + x^2 + 1. Thus, the greatest common
divisor (GCD) of the feedback polynomial with another polynomial mod 2 
will either be 1, x + 1, or x^15 + x^14 + x^13 + ... + x^4 + x^3 + x^2 + 1. 
We will investigate the period by looking at each of these cases.

For the first case, x will be used, since GCD(x , x^16 + x^2 + x + 1) = 1.
Continuously squaring mod (x^16 + x^2 + x + 1) gives:

    x                             x^256 = x^4 + x + 1
    x^2                           x^512 = x^8 + x^2 + 1
    x^4                           x^1024 = x^4 + x^2 + x
    x^8                           x^2048 = x^8 + x^4 + x^2    
    x^16 = x^2 + x + 1            x^4096 = x^8 + x^4 + x^2 + x + 1      
    x^32 = x^4 + x^2 + 1          x^8192 = x^8 + x^4 + x    
    x^64 = x^8 + x^4 + 1          x^16384 = x^8 + x + 1
    x^128 = x^8 + x^2 + x         x^32768 = x

So, after 32768 iterations, we are back at the starting point. Thus, if
the GCD of the starting polynomial and the feedback polynomial is 1, the
period is 32767. By plugging in 1 into all the polynomials, it is seen
that every polynomial in this period has an odd number of terms. So x is
a generator of these odd polynomials.

For a GCD of x + 1, we square in the same fashion and also get a period
of 32767. Here, all the polynomials in a period have an even number of
terms, and x + 1 is a generator.

For a GCD of x^15 + x^14 + x^13 + ... + x^4 + x^3 + x^2 + 1, we find
that squaring it doesn't change its value. Hence, the period is 1, and
seeding the RNG with the value corresponding to this polynomial will
produce a constant sequence. Only one polynomial mod (x^16 + x^2 + x + 1)
has this GCD, so this is the identity coresponding to an even number
of terms.

The only polynomial left mod (x^16 + x^2 + x + 1) is the identity for an
odd number of terms, which is obviously 1 itself.

Therefore, since the NOT switches between even and odd numbered terms
after each iteration, the RNG will have a period of 32767 x 2 = 65534,
unless it is seeded with two specific values that generate constant
sequences. These two values are 0x5555 and 0xAAAA, each consisting of
alternating digits in their binary representations.

Taking this into account, in a single period, $2C has a nearly uniform 
distribution.

    Value                 Probability    
    -----------------------------------------
    0x55                  255 / 65534
    0xAA                  255 / 65534
    all other values      256 / 65534

65534 and 11 are relatively prime. Thus, $E8 has the same distribution.

The RNG algorithm can be expressed by the following code:


                     Code 3.3 - random number generator

    r = $2D << 8 | $2C;
    for(j=0; j<11; j++) {
        r = (r << 1 | !((r >> 15 ^ r >> 1 ^ r) & 0x0001)) & 0xFFFF;
    }
    $2D = r & 0xFF00;
    $2C = r & 0x00FF;
    $E8 = $2C;


Below is a short table of values ($E8) that the RNG generates when
successive passwords are brought up. The table is seeded with 
$2C = 0xFF and $2D = 0xFF.


                  Table 3.2 - RNG Pattern Table

    +-----------------------------------------------------------+
    |            RNG Pattern Table (passwords 1-50)             |
    +----+------+----+------+----+------+----+------+----+------+
    |  # | $E8  |  # | $E8  |  # | $E8  |  # | $E8  |  # | $E8  |
    +----+------+----+------+----+------+----+------+----+------+
    |  1 | 0x6D | 11 | 0x8E | 21 | 0x0A | 31 | 0x7B | 41 | 0xB6 |
    |  2 | 0x86 | 12 | 0xA2 | 22 | 0x72 | 32 | 0x26 | 42 | 0x95 |
    |  3 | 0xC2 | 13 | 0x4E | 23 | 0xEB | 33 | 0x68 | 43 | 0x94 |
    |  4 | 0x21 | 14 | 0x91 | 24 | 0xF6 | 34 | 0xDD | 44 | 0xB9 |
    |  5 | 0xE8 | 15 | 0x39 | 25 | 0x9B | 35 | 0x77 | 45 | 0x58 |
    |  6 | 0xF6 | 16 | 0x85 | 26 | 0x42 | 36 | 0x8B | 46 | 0x67 |
    |  7 | 0x16 | 17 | 0xD9 | 27 | 0x4A | 37 | 0x34 | 47 | 0x46 |
    |  8 | 0xF2 | 18 | 0xCC | 28 | 0xB1 | 38 | 0x48 | 48 | 0x51 |
    |  9 | 0xC0 | 19 | 0x4C | 29 | 0x8E | 39 | 0xDC | 49 | 0x5C |
    | 10 | 0xAC | 20 | 0x47 | 30 | 0xE2 | 40 | 0xEC | 50 | 0x27 |
    +----+------+----+------+----+------+----+------+----+------+


+--------------------------+
| 3.6. Encrypting the Data |
+--------------------------+

Next, $DF-$E7 are encrypted by a combination of summing adjacent values, 
right rotating, and XOR. The encryption is initialized by the random
value $E8 generated in the previous step. The encryption algorithm can 
be more clearly seen in the figure below.

                           
                               Figure 3.2 - Encryption 


      ---+-----+-----+-----+-----+---------------+
         | $E4 | $E5 | $E6 | $E7 |      $E8      |*************>
      ---+-----+-----+-----+-----+---------------+
                                  | | | | | | | |
                                  v v v v v v v v
                                 +---------------+
                                 |      $E8      |**********************
                                 +---------------+                     *
                                  | | | | | | | |                      *
                                  v v v v v v v v                      * 
                               +-------------------+                   *
                               |  7 6 5 4 3 2 1 0  |           *       *
                               |                  8|     +-----*       *
               (+)  XOR        |                  7|-----|-----*       *
                               |                  6|-----|-----*       *
               ***  Bus        |                  5|-----|-----*       v
                               |       Adder      4|-----|-----******>(+)
                               |                  3|-----|-----*       *
                               |                  2|-----|-----*       *
                               |                  1|-----|-----*       *
                               |                  0|-----+     *       *
                               |  7 6 5 4 3 2 1 0  |                   *
                               +-------------------+                   *
                                  ^ ^ ^ ^ ^ ^ ^ ^                      *
                                  | | | | | | | |                      *
      ---+-----+-----+-----+-----+---------------+                     *
         | $E3 | $E4 | $E5 | $E6 |      $E7      |************>        *
      ---+-----+-----+-----+-----+---------------+                     *
                                  ^ ^ ^ ^ ^ ^ ^ ^                      *
                                  | | | | | | | |                      *
                                 *****************                     *
                                         *                             *
                                         *******************************


In the diagram above, $DF-$E8 is represented by two parallel, offset shift 
registers that shift a byte at a time, where each address is mapped with 
the corresponding address on the other shift register. You can picture this
by rolling the diagram into a cylinder, matching the $E7s, $E6s, $E5s, etc.
In this way, the encryption algorithm could be thought of as a helical 
shift register passing through an adder inside that feeds back to the 
preceding byte of the addition (a first order feedback).

Here is the code that does the encryption.
                                        

                   Code 3.4 - encryption subroutine

    for(y=0xE7; y>=0xDF; x--) {
        $y= ($y + $(y+1)) & 0xFF;
        carry = ($y & 0x01) << 7;    // carry from $y into $y
        $y >>= 1;
        $y += carry;
        $y ^= $(y+1);
    }


+-------------------------+
| 3.7. Unpacking the Data |
+-------------------------+

Next, the data in $DF-$E8 is unpacked onto $E9-$F8. Observe that $DF-$E8 
contain 80 bits of information. The password is 16 characters long, so
each byte in $E9-$F8 needs to contain 5 bits from $DF-$E8. Thus, 5 bit 
chunks of data are sequentially taken off of $DF-$E8 and loaded into each
byte of $E9-$F8. The data is loaded by setting up $DF-$E8 as a shift 
register so that the lowest order bits of $DF-$E8 are loaded onto $E9, 
the next 5 onto $EA, the next 5 onto $EB, and so on.

This is done by the following code.


                  Code 3.5 - unpacking subroutine 

    for(z=0xE9; z<=0xF8; x++) {   // run through $E9-$F8
        A = 0x00;    // clear accumulator
        for(i=0; i<5; i++) {    // load 5 bits onto a byte in $DF-$E8 
            carry0 = $E8 & 0x01;    // carry from $E8 into A
            carry[0xDF] = ($DF & 0x01) << 7; // carry from $DF into $E0
            $DF >>= 1;
            for(y=0xE0; y<=0xE7; y++) {
                carry[y] = ($y & 0x01) << 7; // carry from $y into $(y+1)
                $y >>= 1;
                $y += carry[y-1];
            }
            A = (A << 1) & 0xFF;
            A += carry0;
        }
        $z = A;
    }


+-------------------------------+
| 3.8. Transcibing the Password |
+-------------------------------+

Now, all we need to know is the correspondence between the bytes in 
$E9-$F8 and the characters used in the password. This document uses
@, $, & for heart, diamond, and triangle respectively for readability 
purposes.

Here is a table that shows the correspondence:


             Table 3.3 - Password Transcription Table

    +------------------------------------------------------+
    |           Password Transcription Table               |
    +----------+----------+----------+---------------------+
    | 0x00 - 2 | 0x08 - B | 0x10 - L | 0x18 - V            |
    | 0x01 - 3 | 0x09 - C | 0x11 - M | 0x19 - W            |
    | 0x02 - 4 | 0x0A - D | 0x12 - N | 0x1A - Y            |
    | 0x03 - 5 | 0x0B - F | 0x13 - P | 0x1B - Z            |
    | 0x04 - 6 | 0x0C - G | 0x14 - Q | 0x1C - + (cross)    |
    | 0x05 - 7 | 0x0D - H | 0x15 - R | 0x1D - @ (heart)    |
    | 0x06 - 8 | 0x0E - J | 0x16 - S | 0x1E - $ (diamond)  |
    | 0x07 - 9 | 0x0F - K | 0x17 - T | 0x1F - & (triangle) |
    +----------+----------+----------+---------------------+


The table above does not encompass all the characters on the password entry
screen. Except for a few very special passwords (see Appendix B), characters 
not used in any password are:

    0 , 1 , # , (smiley) , ? , ! , * , X            US version
    0 , 1 , A ,    E     , I , O , U , X            Japan version

which all have the value 0xFF.

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


+-----------------------------------------------------------------------------+
| 4. Password Verification                                                    |
+-----------------------------------------------------------------------------+

This section will describe how the game verfies a password a user
has inputted and how it extracts the data stored in it.

The verification algorithm begins at $9BD3 in PRG-ROM. The password is 
verified and read with 6 subroutines.

    1. Check password ($E9-$F8) for forbidden characters (0xFF)
    2. Read data in $E9-$F8, and pack into $DF-$E8
    3. Decrypt the data in $DF-$E8
    4. Calculate the checksum and proceed to step 4 only if it equals $E7
    5. Decompress the data in $DF-$E6 and write to $0151-$0159 ,$014F, $52
    6. Fix up the data in $0151-$0159, $014F, $52 (see Section 4.5 for details)

As for a less detailed, easier to remember description,

    1. check
    2. pack
    3. decrypt
    4. compare
    5. decompress
    6. fix

The section begins assuming the bits for the password are loaded into $E9-$F8.

+------------------------+
| 4.1. Checking the Data |
+------------------------+

First, the password, stored in $E9-$F8, is checked for any forbidden characters
(see Section 3.8). Recall that a forbidden character is represented by 0xFF. If
any are found, the game returns to the password screen for the player to input
another one. If no forbidden characters are encoutered, the game proceeds to
the next subroutine.


                      Code 4.1 - checking subroutine

    for(z=0xE9; z<=0xF8; z++) {    // run through $E9-$F8
        if($z < $80) {
            (proceed checking characters)
        }
        else {
            (break out of loop and return to password screen)
        }
    }   
 

+-----------------------+
| 4.2. Packing the Data |
+-----------------------+


Next, the bits in $E9-$F8 are read and packed into $DF-$E8 by reversing the 
process outlined in Section 3.7. Hence, starting with $F8 and going backwards 
through $E9, the lowest 5 bits on each byte get loaded sequentially onto the 
lowest order bit of the shift register $DF-$E8.


                      Code 4.2 - packing subroutine

    for(z=0xF8; z>=0xE9; z--) {    // run through $F8-$E9
        A = $z;
        for(i=0; i<5; i++) {    // load lowest 5 bits onto $DF-$E8
            carry0 = $A & 0x01;    // carry from A into $E8
            A >>= 1;
            carry[0xE8] = ($E8 & 0x80) >> 7;    // carry from $E8 into $E7
	    $E8 = ($E8 << 1) & 0xFF
            for(y=0xE7; y>=0xDF; y--) {
                carry[y] = ($y & 0x80) >> 7;    // carry from $y into $(y-1)
                $y = ($y << 1) & 0xFF;
                $y += carry[y+1];
            }
        }
    }


+--------------------------+
| 4.3. Decrypting the Data |
+--------------------------+

Next, $DF-$E8 are decrypted by reversing the process outlined in Section 3.6,
that is, replacing the adder with a subtracter, replacing the right rotate
with a left rotate, and carrying out the steps outlined in the encryption
algorithm backwards. 


                  Code 4.3 - decryption subroutine

    for(y=0xDF; y<=0xE7; x++) {
        $y ^= $(y+1);
        carry = ($y & 0x80) >> 7;    // carry from $y into $y
        $y = ($y << 1) & 0xFF;
        $y += carry;
        $y= ($y - $(y+1)) & 0xFF;
    }


+------------------------------+
| 4.4. Checksum Compaison Test |
+------------------------------+

The checksum is then calculated and stored in the accumulator. The game 
compares this value to what is stored at $E7. If the values match,the password 
as validated and proceeds to next step. If they don't match, the password is 
invalid, and the game will ask prompt the player to enter a new one.


                   Code 4.4 - compare subroutine

    A = ($DF + $E0 + $E1 + $E2 + $E3 + $E4 + $E5 + $E6) & 0xFF;
    if (A == $E7) {    // compare to checksum
        (proceed to decompression subroutine)
    }
    else {
        (return to password screen)
    }


+-----------------------------+
| 4.5. Decompressing the Data |
+-----------------------------+

After a successful checksum, the data the password represents is decompressed
and read from $DF-$E6. It is stored in the addresses given by the first two
bytes of the $9A29 table (Table 3.1), that is $5A, $014D, and $0159-$0151.
Before it stores the data in these addresses, the values in these addresses
are first cleared, as well as the value in the address $0150. This value
describes what floors have been cleared in the Grandpa's Tree training levels
(which the password doesn't store - see Section 3.1 - Memory Locations). 
It does this by reversing the process outlined in Section 3.3. 


                   Code 4.5 - decompression subroutine

    $014F = 0;    // clear out data in $014F
    $52 = 0;    // clear out data in $52
    for(w=0x159; w<=0x150; w--) {    // clear out data in $0150-$0159
        $w = 0;
    }
    for(x=0x9A75; x>=0x9A29; y-=4) {    // run through data in table
        A = 0x00;    // clear accumulator
        ns = $(x+2);
        ns = 7 - ns;    // number of times to right shift the accumulator
        nr = $(x+3);    // number of times to right shift the data $DF-$E6
        for(i=0; i<nr; i++) {
            carry[0xDF] = ($DF & 0x01) << 7;    // carry from $DF into $E0
            0xDF >>= 1;
            for(y=0xE0; y<=0xE6; y++) {
                carry[y] = ($y & 0x01) << 7;    // carry from $y into $(y+1)
                $y >>= 1;
                $y += carry[y-1];
            }
            A >>= 1;
            A += $E6;
        }
        A >>= ns;
        y1 = $x & 0xFF00;    // upper byte of address
        y2 = $(x+1) & 0x00FF;    // lower byte of address
        A = A | $(y1+y2); 
        $(y1+y2) = A;    // load data from A into the desired address
    }


+-------------------------+
| 4.6. A Little Fixing Up |
+-------------------------+

You may be thinking the verification/extraction process is now done, but it's 
not quite yet. Remember how the information stored for the levels with 5 
floors is done so with 3 bits? This is troublesome because the value 0xF is 
used to denote that the level has been beaten, and it requires 4 bits. So, 
levels with 5 floors at this point have the value 0x7. Hence, some extra code 
is needed to fix these to the desired 0xF. This way this is done is shown 
below.


                  Code 4.6 - fix 0x7 to 0xF subroutine

    for(x=0x9A29; x<=0x9A69; y+=4) {
        y1 = $x & 0xFF00;    // upper byte of address
        y2 = $(x+1) & 0x00FF;    // lower byte of address
        if($(x+2) == 6) {    // if level has 5 floors and is stored on higher 4
                                bits
            if(($(y1+y2) & 0xF0) == 0x70) {    // change 0x7 to 0xF
                $(y1+y2) |= 0x80;
            }
        }
        if($(x+2) == 2) {    // if level has 5 floors and is stored on lower 4
                                bits
            if(($(y1+y2) & 0x0F) = 0x07) {    // change 0x7 to 0xF
                $(y1+y2) |= 0x08;
             }
         }
    }

Finally, the required data has been extracted from the password. The game then
uses this data to place you in the right location, to give you the right 
character, and to remember which floors you have beaten.


+-----------------------------------------------------------------------------+
| 5. Example of password generation                                           |
+-----------------------------------------------------------------------------+

I thought it would be a good idea to go step by step through the password
generation algorthim with an example. What will be produced is a working 
password from a set of initial data. 

+-------------------+
| 5.1. Initial Data |
+-------------------+

The password we will generate will have the following attributes.

    $0151 = 0xFF         Levels 1-2 completed
    $0152 = 0xF1         Level 3 completed, at floor 1 on Level 4
    $0153 = 0x23         At floor 2 on Level 5, floor 3 on Level 6
    $0154 = 0x01         At boss on Level 7, Level 8 not started
    $0155-$158 = 0x11    Levels 9-16 not started
    $159 = 0x10          Level 17 not started
    $014F = 0x01         Location is Grandpa's Tree 2
    $52 = 0x01           Character is Lala with Lolo

The data above is in the same order as the table at $9A29 (Table 3.1) in memory 
that the game uses to generate passwords, so no rearranging needs to be done. 
First, we'll express these values in binary. Second, we'll mark off the bits to 
be used in the algorithm by referring to the $9A29 table. These bits are marked 
below by asterisks.


    $0151      $0152      $0153      $0154      $0155      $0156
    11111111   11110001   00100011   00000001   00010001   00010001
     *** ***   **** ***    *** ***    *** ***    *** ***    *** ***

    $0157      $0158      $0159       $014F     $52
    00010001   00010001   00010000   00000001   00000001
    **** ***    *** ***   ****          *****      *   *

+-------------------------------------+
| 5.2. Example - Compressing the Data |
+-------------------------------------+

Next, compress these bits (Code 3.1) onto $DF-$E6 by writing only the 
asterisked bits in the same order. Note that there are 61 asterisked bits, 
so append 0b000 to the left of the bit sequence (in $DF).

    $DF-$E6
    00011111 11111001 01001100 00010010 01001001 00010010 01001000 10000101

We'll now express $DF-$E6 in hex for convenience.

                         $DF-$E6
               +-------------------------+
               | 1F F9 4C 12 49 12 48 85 |
               +-------------------------+

+------------------------------------------+
| 5.3. Example - Checksum and Random Value |
+------------------------------------------+

Next, calculate the checksum $E7 (Code 3.2) by adding $DF-$E6 
to get $E7.

    $E7 = (0x1F + 0xF9 + 0x4C + 0x12 + 0x49 + 0x12 + 0x48 + 0x85) & 0xFF = 0x9E

Now we must find the random value $E8. For the sake of convenience, 
we will just make up something instead of tediously stepping through 
iterations in the RNG. Let's use 0x5C.

    $E8 = 0x5C

Thus, we have

                         $DF-$E8    
            +-------------------------------+              
            | 1F F9 4C 12 49 12 48 85 9E 5C |
            +-------------------------------+

+------------------------------------+
| 5.4. Exmaple - Encrypting the Data |
+------------------------------------+

Next, we go into the encryption subroutine (Code 3.4) Start with $E7,  
and see its value is 0x9E. Then, we add it to $E8 and take lowest order 
byte to get 0xFA. The lowest order bit in 0xFA is 0b0, so we right shift
$E7 without a carry. (if it were 0b1, there would be a carry). Doing the 
shifting gives 0x7D (if there was a carry, add 0x80 afterwards). Next, we 
XOR this with the next higher address, $E8. XORing 0x7D with $E8 results in 
0x21. $E7 gets updated with this value.

Summarizing,

    $E7 = 0x9E
    $E8 = 0x5C
    $E7 = ($E7 + $E8) & 0xFF = 0xFA (no carry)
    $E7 = $E7 >> 1 = 0x7D
    $E7 = $E7 ^ $E8 = 0x21 

For the rest of the iterations, we just decreases the addresses in 
question. So, for the next iteration, replace $E7 up above with $E6 and
replace $E8 with $E7 (the new $E7). Continuing until $DF, we get:

    $E6 = 0x85
    $E7 = 0x21
    $E6 = ($E6 + $E7) & 0xFF = 0xA6 (no carry)
    $E6 = $E6 >> 1 = 0x53
    $E6 = $E6 ^ $E7 = 0x72

    $E5 = 0x48
    $E6 = 0x72
    $E5 = ($E5 + $E6) & 0xFF = 0xBA (no carry)
    $E5 = $E5 >> 1 = 0x5D
    $E5 = $E5 ^ $E6 = 0x2F

    $E4 = 0x12
    $E5 = 0x2F
    $E4 = ($E4 + $E5) & 0xFF = 0x41 (carry)
    $E4 = $E4 >> 1 = 0x20
    $E4 = $E4 + 0x80 = 0xA0
    $E4 = $E4 ^ $E5 = 0x8F

    $E3 = 0x49
    $E4 = 0x8F
    $E3 = ($E3 + $E4) & 0xFF = 0xD8 (no carry)
    $E3 = $E3 >> 1 = 0x6C
    $E3 = $E3 ^ $E4 = 0xE3

    $E2 = 0x12
    $E3 = 0xE3
    $E2 = ($E2 + $E3) & 0xFF = 0xF5 (carry)
    $E2 = $E2 >> 1 = 0x7A
    $E2 = $E2 + 0x80 = 0xFA
    $E2 = $E2 ^ $E3 = 0xCF = 0x19

    $E1 = 0x4C
    $E2 = 0x19
    $E1 = ($E1 + $E2) & 0xFF = 0x65 (carry)
    $E1 = $E1 >> 1 = 0x32
    $E1 = $E1 + 0x80 = 0xB2
    $E1 = $E1 ^ $E2 = 0xAB

    $E0 = 0xF9
    $E1 = 0xAB
    $E0 = ($E0 + $E1) & 0xFF = 0xA4 (no carry)
    $E0 = $E0 >> 1 = 0x52
    $E0 = $E0 ^ $E1 = 0xF9

    $DF = 0x1F
    $E0 = 0xF9
    $DF = ($DF + $E0) & 0xFF = 0x18 (no carry)
    $DF = $DF >> 1 = 0x0C
    $DF = $DF ^ $E0 = 0xF5


So now we have:

                         $DF-$E8
            +-------------------------------+
            | F5 F9 AB 19 E3 8F 2F 72 21 5C |
            +-------------------------------+

+-----------------------------------+
| 5.5. Example - Unpacking the Data |
+-----------------------------------+

The unpacking subrouting (Code 3.5) is next. Since the bits in $DF-$E8 are
right shifted into each of the $E9-$F8, we will first express $DF-$E8 in bits
and reverse the sequence so we can read off $E9-$F8 in a left-to-right 
manner.

    $DF-$E3
    11110101    11111001    10101011    00011001    11100011

    $E4-$E8
    10001111    00101111    01110010    00100001    01011100

Reversing gives:

    $E8-E4
    00111010    10000100    01001110    11110100    11110001
    *    *        *    *        *        *    *        *

    $E3-$DF
    11000111    10011000    11010101    10011111    10101111
    *    *        *    *        *        *    *        *


Now, split this sequence into groups of 5 bits each and store into $E9-$F8.

    $E9-$F0
    00111  01010  00010  00100  11101  11101  00111  10001

    $F1-$F8
    11000  11110  01100  01101  01011  00111  11101  01111  


Expressing $E9-$F8 in hex gives:

        $E9-$EC       $ED-$F0       $F1-$F4       $F5-$F8
    +-------------+-------------+-------------+-------------+
    | 07 0A 02 04 | 1D 1D 07 11 | 18 1E 0C 0D | 0B 07 1D 0F |
    +-------------+-------------+-------------+-------------+

+--------------------------------+
| 5.6. Transcribing the Password |
+--------------------------------+

Now look at the Password Transcription Table, printed again below for your 
convenience, to form the password.

    +------------------------------------------------------+
    |           Password Transcription Table               |
    +----------+----------+----------+---------------------+
    | 0x00 - 2 | 0x08 - B | 0x10 - L | 0x18 - V            |
    | 0x01 - 3 | 0x09 - C | 0x11 - M | 0x19 - W            |
    | 0x02 - 4 | 0x0A - D | 0x12 - N | 0x1A - Y            |
    | 0x03 - 5 | 0x0B - F | 0x13 - P | 0x1B - Z            |
    | 0x04 - 6 | 0x0C - G | 0x14 - Q | 0x1C - +            |
    | 0x05 - 7 | 0x0D - H | 0x15 - R | 0x1D - @ (heart)    |
    | 0x06 - 8 | 0x0E - J | 0x16 - S | 0x1E - $ (diamond)  |
    | 0x07 - 9 | 0x0F - K | 0x17 - T | 0x1F - & (triangle) |
    +----------+----------+----------+---------------------+

Doing so gives you the following password:

    9D46 @@9M V$GH F9@K

where @ is a heart and $ is a diamond.

Try it out. It works!

I'm leaving off a verification example because it's really just generation in
reverse, only with a compare added after the checksum is calculated.



+-----------------------------------------------------------------------------+
| 6. Closing Notes                                                            |
+-----------------------------------------------------------------------------+

What is presented here is hopefully a complete and fully correct explanation
of how Adventures of Lolo 3's passwords are generated and verified; however, it
may be the case that I missed something or didn't explain something clearly. If
I'm missing something, or if something in this document 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.


+-----------------------------------------------------------------------------+
| A. Appendix A - Update History                                              |
+-----------------------------------------------------------------------------+

v.0.98  (9/08/2005)
    - added information about the game's special, built-in passwords
    - corrected a counting error in the password trivia section of Appendix B
    - corrected various minor errors in the document

v.0.97  (8/31/2005)
    - expanded Section 3.5 - The Random Number Generator with a more thorough
      discussion of its period
    - expanded Section 3.6 - Encrypting the Data, adding a diagram and giving
      a better explanation of the algorithm
    - added Appendix B - Password List and Miscellaneous Facts
    - fixed a bug in the C code's authentication routine 

v.0.96  (8/28/2005)
    - expanded Section 3.1 - Memory Locations
    - expanded Section 3.5 - The Random Number Generator and greatly
      simplified the algorithm
    - cleaned up C code a bit
    - corrected various minor errors in the document

v.0.95  (8/27/2005)
    - added a random, authentic password generator in the C code
    - fixed a bug in the password generation routine in the C code
    - corrected various minor errors in the document

initial (8/26/2005)
    - initial release



+-----------------------------------------------------------------------------+
| B. Appendix B - Password List and Miscellaneous Facts                       |
+-----------------------------------------------------------------------------+

Below is a list of passwords to every floor in the game, where for each one,
every floor before it has been completed. All passwords use 0x00 in $E8, thus 
they all begin with the character '2'. The Level column is in the format of 
level-floor, with floor B being the boss fight (if there is one). For
readability purposes, this document uses '+', '@', '$', and '&' for the
non-standard characters. For your convenience, this convention will be posted
multiple times on the right side of the table.



              +-----------------------------------------------+
              |                   Passwords                   |
    +---------+-----------------------+-----------------------+
    |  Level  |         Lolo          |         Lala          |
    +---------+-----------------------+-----------------------+
    |  1-1    |  25S3 J5+K 8&7M B5YM  |  25S$ N9R+ KWTH W8TK  |    + (cross)
    |  1-2    |  24JC T6M9 CV97 WSYQ  |  24JM N7@C F+$P 8WQD  |    @ (heart)
    |  1-3    |  25J7 TQ@6 C236 @+D4  |  25JW P7MF FBY4 2L@7  |    $ (diamond)
    |  1-4    |  24$K SGS8 RMR@ F5GD  |  24$T PHYB &TQ7 5L4M  |    & (triangle)
    |  1-5    |  25$5 S+Z@ TMHY DPGF  |  25$@ NRMD F6VN STR+  |
    +---------+-----------------------+-----------------------+
    |  2-1    |  24MF FYS9 R@SH M6S&  |  24MP JZYK $ZZS H4K4  |
    |  2-2    |  24LZ 3WJ$ P2WN YRQR  |  23LK 8BTS WN7@ C55B  |
    |  2-3    |  24MZ HZJD T3CZ Y$J4  |  23MK DDT8 &PRR CP$&  |
    |  2-4    |  23LK 6BKP VJFK FP$$  |  23L& 2CK& ZJZD DPY&  |
    |  2-5    |  23MK BDK5 $K&9 FF3W  |  23M& GFKF +KF5 DZ3V  |
    +---------+-----------------------+-----------------------+
    |  3-1    |  22CN JPVK 8Z63 429M  |  24C4 BN22 6T$T 7CK5  |
    |  3-2    |  22WQ KZ$J SM9W $KGD  |  24W6 CY83 Q@@K MVMJ  |
    |  3-3    |  227L JF&K @K52 DK6C  |  2472 BD92 $PWS W4+R  |
    |  3-4    |  22RS K5VJ 8T8M QCH4  |  24R8 C423 6Z+9 Z46L  |    + (cross)
    |  3-5    |  22HP JZYK $ZZS H3+9  |  24H5 BY42 +TJ4 NQ5W  |    @ (heart)
    |  3-6    |  22@R KP+J 8P93 YG6W  |  24@7 CN63 6&@T R8@7  |    $ (diamond)
    |  3-7    |  225M S6@7 CG5Q K@2L  |  2453 L77G D2M2 +C@8  |    & (triangle)
    |  3-8    |  22PT TGY6 @922 N98C  |  24P9 MH4H $F$T 76@@  |
    |  3-9    |  22FN SSWR HC4B 2CR7  |  24F4 LT3V JRV$ TVCF  |
    |  3-10   |  22ZQ T$&6 &5MQ WPDZ  |  24Z6 M&9C +&H4 J&2C  |
    +---------+-----------------------+-----------------------+
    |  4-1    |  232W 53LZ 4DNB 4KGD  |  252K 6BKP VJFK FTZK  |
    |  4-2    |  2523 82+R 3J5+ HG$@  |  252& 4CTY Y4MV VCH4  |
    |  4-3    |  252M 236+ 5Y&F F9@K  |  22L3 82+R 3J5+ GGQ&  |
    |  4-4    |  22LC 626L 2NKJ Y@LR  |  22LM 236+ 5Y&F F9RG  |
    |  4-5    |  22LM 43+W 4$RW BT5C  |  24L3 626L 2NKJ ZH$T  |
    |  4-6    |  232C 72BN 28B& QF@$  |  232W 33B$ 58VY RPY&  |
    +---------+-----------------------+-----------------------+
    |  5-1    |  25LM 236+ 5Y&F FTZK  |  22B3 S6@7 CG5Q JN4M  |    + (cross)
    |  5-2    |  25QL 2C9+ ZY&Z RPN+  |  22G2 8B&R WJ5G YRZS  |    @ (heart)
    |  5-3    |  25NM V9R+ KWTH LY3M  |  22D3 82+R 3J5+ 6MN7  |    $ (diamond)
    |  5-4    |  25SL LK8V NLTM 9R5L  |  22J2 SJ$R MG56 LSF4  |    & (triangle)
    |  5-5    |  25MM G56B 9PH4 FFT+  |  22C3 Y9HZ JH&& D9$J  |
    |  5-B    |  25TL VG82 QM&& $2KN  |  22K2 $H$C T@JD CZ3V  |
    +---------+-----------------------+-----------------------+
    |  6-1    |  24F@ BNB5 6FY8 DFR@  |  23FC K5LH 8F42 F@LQ  |
    |  6-2    |  25FM B462 6P&5 977L  |  22Z3 J5+K 8&7T 26JY  |
    |  6-3    |  24ZW C4B4 69VQ VRFN  |  23ZH JPLG 892N WHJP  |
    |  6-4    |  25ZR CN63 6&@M WMD5  |  2298 &7WB FQ+R SZ3W  |
    |  6-5    |  249$ V6H5 BGFS 4BRK  |  239D &RRF FGZP P4Q5  |
    |  6-B    |  25PS C423 6Z+2 K+2V  |  22F7 KP+J 8P97 SZ3W  | 
    +---------+-----------------------+-----------------------+
    |  7-1    |  25TP V&PG N6L4 3BKF  |  22K4 $RWC FV&2 7$V7  |    + (cross)
    |  7-2    |  22J4 QS3L GRKV 326B  |  22JN LT3V JRW@ B&2C  |    @ (heart)
    |  7-3    |  22K4 +R3G D6LN 7C&9  |  22KN VQ32 BQJQ GNYQ  |    $ (diamond)
    |  7-4    |  22JN NTW& KCP4 RK$K  |  24J4 QS3L GRKS 4BRK  |    & (triangle)
    |  7-5    |  22KN YQW7 CB4K B98C  |  24K4 +R3G D6LY 9WC5  |
    |  7-B    |  25SP L@5L QR&G 6MN7  |  22J4 SSWR HC5F 7RQP  |
    +---------+-----------------------+-----------------------+
    |  8-1    |  25K4 $RWC FV&B 93G5  |  25K@ DNL7 6TQP T56V  |
    |  8-2    |  2522 SJ$R MGFH SZCY  |  252$ N9R+ KWZ3 TP4V  |
    |  8-3    |  25B5 S+Z@ TMCT B9JD  |  25B+ N&PG N6QF PNYR  |
    |  8-4    |  2563 82+R 3JGY T&BF  |  256& 4CTY Y4Z@ NYWQ  |
    |  8-5    |  25G4 8LVR 3D3B H4Q5  |  25G@ YT3V JRZM MNDP  |
    +---------+-----------------------+-----------------------+
    |  9-1    |  24YJ 82QS 3N4B W77L  |  24YS 53VV 4SP$ NJ+6  |    + (cross)
    |  9-2    |  23YD 7LGN 23K8 8C73  |  23YY 3MG$ 53+2 PYMS  |    @ (heart)
    |  9-3    |  25Y4 8LVR 3F97 6@VS  |  25Y+ 4WNY Y9C9 G8$6  |    $ (diamond)
    |  9-4    |  2285 Q+5V ST&2 7$V7  |  228P L@SL QTF9 Q5&J  |    & (triangle)
    |  9-5    |  248F T+T& ZJ8C CK8B  |  248P N@ZT RW3Q BPDY  |
    |  9-B    |  22Y8 722M 2VCH J$B4  |  22YS 332@ 5LYC ZC&9  |
    +---------+-----------------------+-----------------------+
    |  10-1   |  24SD 9LQT 3&LN 9C92  |  24SN 4MVW 4ZH8 +G++  |
    |  10-2   |  24RD TSRT HG$V H4Q5  |  24RN NTW& KL4K D9$J  |
    |  10-3   |  24TD KPQH 88CZ FTZK  |  24TN DNV7 74+G LS53  |
    |  10-4   |  24QY WQH4 BW7R VWC4  |  23QJ $7RD FWMN CFKZ  |
    |  10-5   |  24SY 3MG$ 556R SZ3W  |  23SJ 82Q5 3PNN &G8V  |
    |  10-B   |  24QD &RRF FRPN MJJ5  |  24QN YQW7 CWC9 J883  |
    +---------+-----------------------+-----------------------+
    |  11-1   |  25TN BN22 6$QK L493  |  22K5 JZYK $LJG DPY$  |    + (cross)
    |  11-2   |  25KT CD53 SPJ8 BFHY  |  22&7 KP+J 3FTP 56R$  |    @ (heart)
    |  11-3   |  25&M B462 8YHY Z@VT  |  2223 S6@7 F7R5 &26B  |    $ (diamond)
    |  11-4   |  252R MR7H K+2K $2KN  |  22L9 TGY6 VR9R 2+BY  |    & (triangle)
    |  11-5   |  25LP L@5L R&VM 9R5L  |  22B4 SSWR GVRZ WM42  |
    |  11-B   |  259Q CY83 LS9W 5G$@  |  22T8 K5VJ 4&GR LJG4  |
    +---------+-----------------------+-----------------------+
    |  12-1   |  246+ V+FZ RPY3 WMD5  |  236B &HNF @LYC ZC&9  |
    |  12-2   |  236B @HDJ 6DP$ NJ+6  |  236V WGD4 9D9W 5G$@  |
    |  12-3   |  236V ZGN9 84BZ 9RFP  |  256J +7HK S9CT D9SH  |
    |  12-4   |  2562 $H$C 7D&+ 4LYG  |  256$ Y6R8 RK$L K+2V  |
    |  12-5   |  256L VG82 V362 4LNK  |  22Q2 $H$C ZHSP H8@7  |
    |  12-B   |  246G $@PQ TP46 VR4N  |  246Q Z+&+ 6STK 67SR  |
    +---------+-----------------------+-----------------------+
    |  13-1   |  23QV ZGN9 C3G5 QK+J  |  25QK +JJP JQKG 8MD4  |    + (cross)
    |  13-2   |  23+Y ZQR& V73Q BPDY  |  25+G +@F5 6BS& J8J4  |    @ (heart)
    |  13-3   |  23NW 53LR ZWM4 KD9L  |  25NJ Q8H& V73Q BPDY  |    $ (diamond)
    |  13-4   |  23YZ P@TH 8$GD M$22  |  25YH QQCT P4QK L493  |    & (triangle)
    |  13-5   |  23SV 5CP@ 2ZWM FTPG  |  25SK 6BKT 5977 +VWG  |
    |  13-6   |  23$Y 5MQ3 LJ4V &6HZ  |  25$G 6VDK D3VM 7RZT  |
    |  13-7   |  23MW &8M@ LY7C @BTJ  |  25MJ 62G& Q9MN FFT+  |
    |  13-8   |  23WZ 5WSC FHS5 F9RG  |  25WH 6LB3 &L4K D9$J  |
    |  13-9   |  23RV PKN& G2LY 7WM6  |  25RK QGJ3 BH46 YRPR  |
    |  13-10  |  23@Y PTRK $6C@ B&2C  |  25@G Q$F@ 2ZWM FTPG  |
    |  13-B   |  23VZ FYS& G6MD KYCP  |  25VH GPBT Z3Q5 P4QS  |
    +---------+-----------------------+-----------------------+
    |  14-1   |  246S W63M NDZH QZM@  |  2367 &S@G $LJG DPY$  |    + (cross)
    |  14-2   |  236R ZTC8 RK$L K+2V  |  2567 @S3C TF97 6@VS  |    @ (heart)
    |  14-3   |  256@ VTY& G2LY 7WM6  |  22QF &$RT Z7RP W3G5  |    $ (diamond)
    |  14-4   |  22QZ Z&3W MDKD 7WM6  |  24QK +JFP 4PJS JD7M  |    & (triangle)
    |  14-5   |  24QP V&N+ GQTF 9RFP  |  23Q5 $$YR KV3& L493  |
    +---------+-----------------------+-----------------------+
    |  15-1   |  24GN VQ52 68MJ GDRT  |  23G4 $RZC 9D9W 5G$@  |
    |  15-2   |  24JN 2LNS KG8J DF@$  |  23J4 8MYW HB&V 326B  |
    |  15-3   |  24HN LTP+ 2TZ3 RPY&  |  23H4 SSFP 4PJS JD7M  |
    |  15-4   |  23K4 GNN9 C3GS QK+J  |  23KN BP4C FCTP 36HZ  |
    |  15-5   |  23G4 +R5H 8YHY Z@VT  |  23GN VQ53 6DP$ NJ+6  |
    +---------+-----------------------+-----------------------+
    |  16-1   |  22@F 7VWR PYMJ GDRT  |  22@Z 3WWW MDKD 7WM6  |
    |  16-2   |  225G +NY6 CRF9 S59C  |  225+ VPDD F@L4 5BTJ  |
    |  16-3   |  22PB @D&7 7$VH 2+2W  |  22PV WFKF 9S5B R9RG  |
    |  16-4   |  22FK +4&+ 2PYM &L4B  |  22F& V5KS 5F9R 4+L&  |
    |  16-5   |  22ZD @SZR 5Z3Q DPN@  |  22ZY WTFZ 3PNN &G8V  |
    +---------+-----------------------+-----------------------+
    |  17-1   |  22TC H8@R Z@LN 7C&9  |  23TS M462 L42B 326B  |    + (cross)
    |  17-2   |  22SW 87JJ DCZM MNDP  |  25S8 @2+R T&2Q 8M43  |    @ (heart)
    |  17-3   |  22TW D9$$ GBPY M$22  |  25T8 R5+K N8W@ D&VJ  |    $ (diamond)
    |  17-4   |  24S3 56@7 @+VW 7HSQ  |  25SS Y@VB @6@V W77L  |    & (triangle)
    |  17-5   |  24T3 K8HP YR&L 3&VK  |  25TS N$VQ ZRPN MJJ5  |
    |  17-6   |  24SM 77@C &G8$ GDRT  |  22JC &LDP JLJ+ GNNT  |
    |  17-7   |  24TM C9HZ WRFT L4K4  |  22KC TPDP FMNN @G$@  |
    |  17-8   |  23S3 2Q53 6DP$ NJ+6  |  22JW WMD$ G2LY 7WM6  |
    |  17-9   |  23T3 GSPT 556R SZ3W  |  22KW MND5 BM8R G$V6  |
    |  17-10  |  23SM 8R5H 8YHY Z@VT  |  24JH @VMS PJS& J8J4  |
    |  17-B   |  22SC 36H5 +QTZ 3Q5V  |  23SS W36+ QPS5 C9HF  |
    +---------+-----------------------+-----------------------+


Lolo 3 contains some hidden, special passwords that have different effects on
the game's password screen. All of these passwords fail the game's verification
check, so you will hear a buzz (signifying a password failure) after the 16th
character is entered. To trigger their effects, you need to manually select 
'END'.  

All the sound test passwords begin with a two-digit number, followed by a 
double zero, '00'. Each two-digit number (within a range) corresponds to a
different background music or sound effect.

Note: In place of the vowels A, E, I, O, and U, the US version of the game uses 
the characters # , (smiley) , ? , ! , * respectively. The Japanese version 
retains the vowels.


    +---------------------------------------------------------+
    |                      Special Passwords                  |
    +---------------------------------+-----------------------+
    |              Effect             |       Password        |
    +---------------------------------+-----------------------+
    | Background Music Test           |  %%00 LOLO 3BGM TEST  |    US version
    | %% is a number between 00 and 23|  %%00 LOLO 2BGM TEST  |    JP version
    +---------------------------------+-----------------------+
    | Sound Effect Test               |  %%00 LOLO 3FGM TEST  |    US version
    | %% is a number between 00 and 48|  %%00 LOLO 2FGM TEST  |    JP version
    +---------------------------------------------------------+      
    | Character Display               |                       |
    |     Lolo                        |  LOLO LOOK PLEA SE@@  |
    |     Lala                        |  LALA LOOK PLEA SE@@  |
    |     Snakey                      |  @SNA KEY+ MONS TER@  |
    |     Leaper                      |  @LEA PER+ MONS TER@  |    + (cross)
    |     Skull                       |  @SKA LWG+ MONS TER@  |    @ (heart)
    |     Rocky                       |  @ROC KY++ MONS TER@  |    $ (diamond)
    |     Medusa                      |  @MED USA+ MONS TER@  |    & (triangle)
    |     Gol                         |  @GOL +GOL MONS TER@  |
    |     Alma                        |  @ALM ARK+ MONS TER@  |
    |     Don Medusa                  |  DONM EDUS AMON STER  |
    |     Moby                        |  @CAP OXX+ MONS TER@  |
    +---------------------------------+-----------------------+


Also, here are some miscellaneous facts about the password system:

    The total number of passwords that can be entered from the password is
    screen is 40^16 = 42949672960000000000000000. Out of these, 
    32^16 = 1208925819614629174706176 entirely consist of valid characters
    (see Section 3.8 for details).

    The total number of valid passwords, i.e. ones that do not have a
    failed checksum (see Section 4.4), is 2^72 = 4722366482869645213696.
    Thus, if you are entering in only valid characters at random, you will
    have a 1/256 chance of inputting a correct password.

    The total number of authentic passwords, i.e. ones that you can actually
    receive from the game itself is 7512576. Thus, out of the valid passwords,
    14673 / 9223372036854775808 (about 1.59 x 10^-13 percent) of them are ones
    that you can actually get through the game. If you are entering passwords
    (comprised of only valid characters again) at random, then you will have a
    14673 / 2361183241434822606848 (about 6.21 x 10^-16 percent) chance of
    entering one you can get from the game.

    Below is the distribution given by the areas and locations of the game if 
    authentic passwords are generated in a uniform, random manner.

        Area                 Probability
        ------------------------------------
        Overworld (left)      88 /  4891
        Overworld (right)   7805 / 14673
        Underwater World    6530 / 14673
        Underworld            74 / 14673

        Location             Probability          Probability given Area
        ---------------------------------------------------------------------
        Grandpa's Tree 1      22 /  4891                        1 /    4
        Level 1               22 /  4891                        1 /    4
        Level 2               22 /  4891                        1 /    4
        Level 3             1366 / 14673       1 / 4 (left),  260 / 1561 (right)
        Level 4             1300 / 14673                      260 / 1561  
        Level 5             1300 / 14673                      260 / 1561
        Level 6             1300 / 14673                      260 / 1561
        Level 7             1300 / 14673                      260 / 1561
        Level 8                5 / 14673                        1 / 1561
        Level 9             1306 / 14673                        1 /    5
        Level 10            1306 / 14673                        1 /    5
        Level 11            1306 / 14673                        1 /    5
        Level 12            1306 / 14673                        1 /    5
        Level 13            1306 / 14673                        1 /    5
        Level 14              26 / 14673                       13 /   37
        Level 15              21 / 14673                       21 /   74
        Level 16              16 / 14673                        8 /   37
        Level 17              11 / 14673                       11 /   74


+-----------------------------------------------------------------------------+
| C. Appendix C - C code for password generator/verifier/authenticator        |
+-----------------------------------------------------------------------------+

Here's some C code that will compile into a console program that generates, 
verifies, and authenticates Lolo 3 passwords. The passwords can either be 
generated from values the user enters or generated randomly. The passwords that 
are randomly generated can either be completely random (valid, but might
produce some weird effects in the game when entered) or they can be both 
random and authentic (can actually be generated by the game itself). The code 
also contains an authentication subroutine which determines if a password is
authentic.

I compiled the code with mingw32-gcc-3.4.2.


----------------------------- code begins here---------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


int randomval,indexval;
int data[11];
int E[10];
int F[16];

int rnd(int,int);
int rndp(int,int,int);
int test(int*,int*,int*);
int initialize(int*,int*);
int generate();
int degenerate();
int generate_authentic();
int authenticate();

int T[60] = { 0, 6, 3,     0, 2, 3,     1, 7, 4,     1, 2, 3, 
              2, 6, 3,     2, 2, 3,     3, 6, 3,     3, 2, 3, 
              4, 6, 3,     4, 2, 3,     5, 6, 3,     5, 2, 3, 
              6, 7, 4,     6, 2, 3,     7, 6, 3,     7, 2, 3, 
              8, 7, 4,     9, 4, 5,     10, 4, 1,    10, 0, 1 };

int main() {

   int i,k;
   int temp,check;
   int gord,sel,aorm;
   int level,floors,floor,location,character,auth;
   char password[19];

   char chr[32] = "23456789BCDFGHJKLMNPQRSTVWYZ+@$&";
   
   /* Intialize data */
   initialize(data,F);
   srand((unsigned)time(NULL));
   
   printf("\n");
   printf("Generate or degenerate a password\n\n");
   printf("    0. Generate    1. Degenerate\n\n");
   printf("Selection? ");
   scanf("%d",&gord);
   
   switch(gord) {
   case 0:
      printf("\n");
      printf("Select the type of password generation:\n\n");
      printf("    0. Manual - Data needed is given by the user\n");
      printf("    1. Random - Generates a random but not necessarily ");
      printf("authentic password\n");
      printf("    2. Authentic Random - Generates a random, authentic ");
      printf("password\n\n");
      printf("Selection? ");
      scanf("%d",&sel);
      
      switch(sel) {
      case 0 :
         /* Get data from user */
         printf("\n");
         printf("Enter which floor you are on for each level.\n\n");
         printf("1-10 are floor numbers, 0 means a special or boss room,\n");
         printf("15 means the level is completed.\n");
         printf("If 0 is picked for a level that has no special room or\n");
         printf("boss, entry to the level will be prohibited.\n\n");
         for(i=0; i<9; i+=1) {
            level = 2*i+1;
            if(level == 3 || level == 13 || level == 17) {
               floors = 10;
            }
            else {
               floors = 5;
            }
            printf("Level %d (%d floors): ",level,floors);
            scanf("%d",&floor);
            if(i != 8) {
               level = 2*i+2;
               floors = 5;
               printf("Level %d (%d floors): ",level,floors);
               scanf("%d", &data[i]);
            }
            data[i] |= (floor << 4);
         }
   
         printf("\n");
         printf("Choose a location:\n\n");
         printf("   0. Grandpa's Tree 1   1. Grandpa's Tree 2   2. Level 1\n");
         printf("   3. Level 2            4. Level 3            5. Level 4\n");
         printf("   6. Level 5            7. Level 6            8. Level 7\n");
         printf("   9. Level 8           10. Level 9           11. Level 10\n");
         printf("  12. Level 11          13. Level 12          14. Level 13\n");
         printf("  15. Level 14          16. Level 15          17. Level 16\n");
         printf("  18. Level 17\n\n");
         printf("Selection? ");
         scanf("%d",&data[9]);
   
         printf("\n");
         printf("Choose character:\n\n");
         printf("     0. Lolo (w/ Lala)       1. Lala (w/ Lolo)\n");
         printf("     2. Lolo (alone)         3. Lala (alone)\n\n");
         printf("Selection? ");
         scanf("%d",&temp);
         data[10] = ((temp & 0x02) << 3) | (temp & 0x01);

         printf("\n");
         printf("Select randomization method:\n\n");
         printf("     0. Auto randomize      1. Manual input \n\n");
         printf("Selection? ");
         scanf("%d",&aorm);
         switch(aorm) {
         case '0':
            indexval = rand() % 65535; 
         break;
         case 1:
            printf("\n");
            printf("Enter random value (0-255): ");
            scanf("%d",&randomval);
            randomval = randomval % 256;
            indexval = 65536;
         break;
         default: break;
      }
      break;
         
      /* random generation */
      case 1:
         for(i=0; i<11; i++) {
            data[i] = rand() % 256;
         } 
         indexval = rand() % 65535;
      break;
         
      /* random, authentic generation */
      case 2:
         generate_authentic();
         indexval = rand() % 65535;
      break;
      default: break;
      break;
      }
      
      /* Generate password */
      generate();
   
      /* Display password */
      
      printf("\n");
      printf("Legend:      + - Cross\n");
      printf("             @ - Heart\n");
      printf("             $ - Diamond\n");
      printf("             & - Triangle\n\n");
      
      printf("Password: ");
      for(k=0; k<16; k++) {
          printf("%c",chr[F[k]]);
          if(k % 4 == 3) {
              printf(" ");
          }
      }      
   break;
   case 1:
   
      /* Get password from user */
      for(i = 0; i<19; i++) {
         password[i] = (char)20;
      }
      printf("\n");
      printf("Input the password in the following format ");
      printf("(xxxx xxxx xxxx xxxx).\n");
      printf("Use uppercase letters.\n");
      printf("Legend:      + - Cross\n");
      printf("             @ - Heart\n");
      printf("             $ - Diamond\n");
      printf("             & - Triangle\n\n");
      printf("Password? ");
      scanf("%s%s%s%s",password,password+5,password+10,password+15);
         
      
      k = 0;
      for(i=0; i<19; i++) {
         switch(password[i]) {
            case '2' : F[k] = 0x00; break;
            case '3' : F[k] = 0x01; break;
            case '4' : F[k] = 0x02; break;
            case '5' : F[k] = 0x03; break;
            case '6' : F[k] = 0x04; break;
            case '7' : F[k] = 0x05; break;
            case '8' : F[k] = 0x06; break;
            case '9' : F[k] = 0x07; break;
            case 'B' : F[k] = 0x08; break;
            case 'C' : F[k] = 0x09; break;
            case 'D' : F[k] = 0x0A; break;
            case 'F' : F[k] = 0x0B; break;
            case 'G' : F[k] = 0x0C; break;
            case 'H' : F[k] = 0x0D; break;
            case 'J' : F[k] = 0x0E; break;
            case 'K' : F[k] = 0x0F; break;
            case 'L' : F[k] = 0x10; break;
            case 'M' : F[k] = 0x11; break;
            case 'N' : F[k] = 0x12; break;
            case 'P' : F[k] = 0x13; break;
            case 'Q' : F[k] = 0x14; break;
            case 'R' : F[k] = 0x15; break;
            case 'S' : F[k] = 0x16; break;
            case 'T' : F[k] = 0x17; break;
            case 'V' : F[k] = 0x18; break;
            case 'W' : F[k] = 0x19; break;
            case 'Y' : F[k] = 0x1A; break;
            case 'Z' : F[k] = 0x1B; break;
            case '+' : F[k] = 0x1C; break;
            case '@' : F[k] = 0x1D; break;
            case '$' : F[k] = 0x1E; break;
            case '&' : F[k] = 0x1F; break;
            default : k--; break;
         }
         k++;
      }   
      
      if(k != 16) {
         printf("\nInvalid password\n");
         return 0;
      }
   break;
   default:
   break;
   }
   
   /* Degenerate password */
   check = degenerate();
      
   /* Print out data stored in password */
   printf("\n\n");
   for(i = 0; i < 9; i++) {
      level = 2*i+1;
      floor = (data[i] & 0xF0) >> 4;
      if(floor == 0) {
         printf("Level %d - at boss or special room\n",level);
      }
      if(floor == 15) {
         printf("Level %d - completed\n",level);
      }
      if(floor != 0 && floor != 15) {
         printf("Level %d - at floor %d\n",level,floor);
      }
      if(i != 8) {
         level = 2*i+2;
         floor = data[i] & 0x0F;
         if(floor == 0) {
            printf("Level %d - at boss or special room\n",level);
         }
         if(floor == 15) {
            printf("Level %d - completed\n",level);
         }
         if(floor != 0 && floor != 15) {
            printf("Level %d - at floor %d\n",level,floor);
         }
      }
   }
      
   location = (data[9] & 0x1F);
   switch(location) {
      case 0x00: printf("Location - Grandpa's Tree 1"); break;
      case 0x01: printf("Location - Grandpa's Tree 2"); break;
      case 0x02: printf("Location - Level 1"); break;
      case 0x03: printf("Location - Level 2"); break;
      case 0x04: printf("Location - Level 3"); break;
      case 0x05: printf("Location - Level 4"); break;
      case 0x06: printf("Location - Level 5"); break;
      case 0x07: printf("Location - Level 6"); break;
      case 0x08: printf("Location - Level 7"); break;
      case 0x09: printf("Location - Level 8"); break;
      case 0x0A: printf("Location - Level 9"); break;
      case 0x0B: printf("Location - Level 10"); break;
      case 0x0C: printf("Location - Level 11"); break;
      case 0x0D: printf("Location - Level 12"); break;
      case 0x0E: printf("Location - Level 13"); break;
      case 0x0F: printf("Location - Level 14"); break;
      case 0x10: printf("Location - Level 15"); break;
      case 0x11: printf("Location - Level 16"); break;
      case 0x12: printf("Location - Level 17"); break;
      default : printf("Location - Not valid location"); break;
   }
      
   printf("\n");
   character = (data[10] & 0x11);
   switch(character) {
      case 0x00: printf("Character - Lolo (with Lala)"); break;
      case 0x01: printf("Character - Lala (with Lolo)"); break;
      case 0x10: printf("Character - Lolo (alone)"); break;
      case 0x11: printf("Character - Lala (alone)"); break;
      default : break;
   }
      
   printf("\n");
      
   /* authenticate password */
   if(check == 0) {
      auth = authenticate();
      if(auth == 0) {
         printf("\nAuthentic password\n");
      }
      else {
         printf("\nValid but not authentic\n");
      }
   }
   else {
      printf("\nError: checksum failure\n");
   }
   
   return 0;
   
}

   
int generate() {

   int compress();
   int checksum();
   int rng();
   int encrypt();
   int unpack();
   
   compress();
   checksum();
   rng();
   encrypt();
   unpack();

   return 0;
}

int degenerate() {

   int fail;
   
   int pack();
   int decrypt();
   int compare();
   int decompress();
   int fix();
   
   pack();
   decrypt();
   fail = compare();
   decompress();
   fix();
   
   return fail;
}

/* Code 3.1 - compression subroutine */
int compress() {
   int A,ns,nr,i,j,k;
   int carryE[10];
      
   E[7] = 0x00;
   for(i=0; i<60; i+=3) {    /* run through data in table */
      A = data[T[i]];
      ns = T[i+1];
      ns = 7 - ns;    /* number of times to left shift the accumulator */
      nr = T[i+2];    /* number of times to left shift through $DF-$E6 */
      A = (A << ns) & 0xFF;    /* shift data into loading position */
      for(j=0; j<nr; j++) {    
         carryE[8] = (A & 0x80) >> 7;   /* carry from A into $E6 */
         A = (A << 1) & 0xFF;
         for(k=7; k>=1; k--) {    /* shift data through $DF-$E6 */
            carryE[k] = (E[k] & 0x80) >> 7;    /* carry from $y into $(y-1) */
            E[k] = (E[k] << 1) & 0xFF;
            E[k] += carryE[k+1];
         }
         E[0] = (E[0] << 1) & 0xFF;
         E[0] += carryE[1];
      }
   }
   return 0;
}

/* Code 3.2 - checksum subroutine */
int checksum() {
   
   E[8] = (E[0] + E[1] + E[2] + E[3] + E[4] + E[5] + E[6] + E[7]) & 0xFF;
   
   return 0;
}
   
/* Code 3.3 - random number generator */
int rng() {
   int i,j,x;
   
   x = 0xFFFF;
   
   if(indexval < 65535) {
      for(i=0; i<indexval; i++) {
          for(j=0; j<11; j++) {
            x = (x << 1 | !((x >> 15 ^ x >> 1 ^ x) & 0x0001)) & 0xFFFF;
          }
      }
   E[9] = x & 0xFF;
   }
   else {
      E[9] = randomval;
   }
   
   return 0;
}
      
/* Code 3.4 - encryption subroutine */
int encrypt() {
   int i,carry;
   
   for(i=8; i>=0; i--) {
      E[i] = (E[i] + E[i+1]) & 0xFF;
      carry = (E[i] & 0x01) << 7;  /* carry from E[i] into E[i] */
      E[i] >>= 1;
      E[i] += carry;
      E[i] ^= E[i+1];
   }
   
   return 0;
}
   
/* 3.5 - unpacking subroutine */
int unpack() {
   int A,i,j,k,carry;
   int carryE[10];

   for(i=0; i<16; i++) {    /* run through $E9-$F8 */
      A = 0x00;    /* clear accumulator */
      for(j=0; j<5; j++) {    /* load 5 bits onto a byte in $DF-$E8 */
         carry = E[9] & 0x01;    /* carry from $E8 into A */
         carryE[0] = (E[0] & 0x01) << 7;    /* carry from $DF into $E0 */
         E[0] >>= 1;
         for(k=1; k<10; k++) {
            carryE[k] = (E[k] & 0x01) << 7;    /* carry from $y into $(y+1) */
            E[k] >>= 1;
            E[k] += carryE[k-1];
         }
         A = (A << 1) & 0xFF;
         A += carry; 
      }
      F[i] = A;
   }
   
   return 0;
}

/* Code 4.2 - packing subroutine */
int pack() {
   int A,carry,i,j,k;
   int carryE[10];

   for(i=15; i>=0; i--) {    /* run through $F8-$E9 */
      A = F[i];
      for(j=0; j<5; j++) {    /* load lowest 5 bits onto $DF-$E8 */
         carry = A & 0x01;    /* carry A into $E8 */
         A >>= 1;
         carryE[9] = (E[9] & 0x80) >> 7;    /* carry from $E8 into $E7 */
         E[9] = (E[9] << 1) & 0xFF;
         E[9] += carry;
         for(k=8; k>=0; k--) {
            carryE[k] = (E[k] & 0x80) >> 7;    /* carry from $y into $(y-1) */
            E[k] = (E[k] << 1) & 0xFF;
            E[k] += carryE[k+1];
         }
      }
   }
   
   return 0;
}
   
/* Code 4.3 - decryption subroutine */
int decrypt() {
   int i,carry;

   for(i=0; i<=8; i++) {
      E[i] ^= E[i+1];
      carry = (E[i] & 0x80) >> 7;    /* carry from E[i] into E[i] */
      E[i] = (E[i] << 1) & 0xFF;
      E[i] += carry;
      E[i] = (E[i] - E[i+1]) & 0xFF;
   }
   
   return 0;
}
    
/* Code 4.4 - compare subroutine */
int compare() {
   int checksum;
   
   checksum = (E[0] + E[1] + E[2] + E[3] + E[4] + E[5] + E[6] + E[7]) & 0xFF;
   if(checksum != E[8]) {    /* compare to checksum */
      return 1;
   }
   else {
      return 0;
   }
}
   
/* Code 4.5 - decompression subroutine */
int decompress() {
   int i,j,k,A,nr,ns;
   int carryE[10];
   
   for(i=0; i<11; i++) {    /* run through data in table */
       data[i] = 0;    /* clear out data */
   }
   for(i=57; i>=0; i-=3) {    /* run through data in table */
      A = 0x00;    /* clear accumulator */
      ns = T[i+1];
      ns = 7 - ns;    /* number of times to right shift the accumulator */
      nr = T[i+2];    /* number of times to right shift the data $DF-$E6 */
      for(j=0; j<nr; j++) {
         carryE[0] = (E[0] & 0x01) << 7;    /* carry from $DF into $E0 */
         E[0] >>= 1;
         for(k=1; k<8; k++) {
            carryE[k] = (E[k] & 0x01) << 7;    /* carry from $y into $(y+1) */
            E[k] >>= 1;
            E[k] += carryE[k-1];
         }
         A >>= 1;
         A += carryE[7];
      }
      A >>= ns;
      A = (A | data[T[i]]);
      data[T[i]] = A;    /* load data */
      
   }
   
   return 0;
}
   
/* Code 4.6 - fix 0x7 to 0xF subroutine */
int fix() {
   int i;
   
   for(i=0; i<=51; i+=3) {
      if(T[i+1] == 6) {    /* if level has 5 floors and is stored on higher 4
                              bits */
         if((data[T[i]] & 0xF0) == 0x70) {
            data[T[i]] |= 0x80;
         }
      }
      if(T[i+1] == 2) {    /* if level has 5 floors and is stored on lower 4 
                              bits */
         if((data[T[i]] & 0x0F) == 0x07) {
            data[T[i]] |= 0x08;
         }
      }
   }
   
   return 0;

}

int test(int data[11],int E[10],int F[16]) {

   int i;

   printf("\n");
   printf("$0151-$0159: ");
   for(i=0; i<9; i++) {
      printf("%02X ",data[i]);
   }
   printf("\n");
   printf("$014F: %02X",data[9]);
   printf("\n");
   printf("$52: %02X",data[10]);
   printf("\n");
   printf("$DF-$E8: ");
   for(i=0; i<10; i++) {
      printf("%02X ",E[i]);
   }
   printf("\n");
   printf("$E9-$F8: ");
   for(i=0; i<16; i++) {
      printf("%02X ",F[i]);
   }
   printf("\n");

   return 0;
}

int initialize(int data[11],int F[16]) {

   int i;

   for(i=0; i<11; i++) {
      data[i] = 0;
   }
   for(i=0; i<16; i++) {
      F[i] = 0;
   }
   
   return 0;
}

/* Generate authentic password */
int generate_authentic() {

   int level,temp;

   level = rnd(1,17);
   
   /* Levels 1 & 2 */
   if(level == 1 || level == 2) {
      data[0] = (rndp(0,5,15) << 4) | rndp(0,5,15);
      if((data[0] & 0x0F) == 0x0F) {
         if((data[0] & 0xF0) == 0xF0) {
            data[1] = (rnd(0,10) << 4) | 0x01;
         }
         else {
            data[1] = (rnd(0,5) << 4) | 0x01;
         }
      }
      else {
         data[1] = 0x11;
      }
      data[2] = 0x11; data[3] = 0x11; data[4] = 0x11;
      data[5] = 0x11; data[6] = 0x11; data[7] = 0x11;
      data[8] = 0x10;
      data[9] = rndp(2,4,0);
      data[10] = rnd(0,1);
   }
   
   /* Level 3 */
   if(level == 3) {
      temp = rnd(0,1);
      if(temp == 1) {
         data[0] = (rnd(0,5) << 4) | 0x0F;
         data[1] = (rnd(0,5) << 4) | 0x01;
      }
      else {
         data[0] = 0xFF;
         data[1] = (rnd(0,10) << 4) | 0x01;
      }
      data[2] = 0x11; data[3] = 0x11; data[4] = 0x11;
      data[5] = 0x11; data[6] = 0x11; data[7] = 0x11;
      data[8] = 0x10;
      data[9] = rndp(2,4,0);
      data[10] = rnd(0,1);
   }
   
   /* Levels 4-7 */
   if(level >=4 && level <= 7) {
      data[0] = 0xFF;
      data[1] = 0xF0 | rndp(0,5,15);
      data[2] = (rndp(0,5,15) << 4) | rndp(0,5,15);
      data[3] = (rndp(0,5,15) << 4) | 0x01;   
      data[4] = 0x11; data[5] = 0x11; data[6] = 0x11;
      data[7] = 0x11; data[8] = 0x10;
      data[9] = rndp(4,8,1);
      data[10] = rnd(0,1);
   }
   
   /* Level 8 */
   if(level == 8) {
      data[0] = 0xFF; data[1] = 0xFF; data[2] = 0xFF;
      data[3] = 0xF0 | rnd(1,5);
      data[4] = 0x11; data[5] = 0x11; data[6] = 0x11;
      data[7] = 0x11; data[8] = 0x10;
      data[9] = rndp(4,9,1);
      data[10] = rnd(0,1);
   }
   
   /* Levels 9-12 */
   if(level >= 9 && level <= 12) {
      data[0] = 0xFF; data[1] = 0xFF; data[2] = 0xFF;
      data[3] = 0xFF;
      data[4] = (rndp(0,5,15) << 4) | rndp(0,5,15);
      data[5] = (rndp(0,5,15) << 4) | rndp(0,5,15);
      data[6] = 0x11; data[7] = 0x11; data[8] = 0x10;
      data[9] = rnd(10,14);
      data[10] = rnd(0,1);
   }
      
   /* Level 13 */
   if(level == 13) {
      data[0] = 0xFF; data[1] = 0xFF; data[2] = 0xFF;
      data[3] = 0xFF; data[4] = 0xFF; data[5] = 0xFF;
      data[6] = (rnd(0,10) << 4) | 0x01;
      data[7] = 0x11; data[8] = 0x10;
      data[9] = rnd(10,14);
      data[10] = rnd(0,1);
   }
      
   /* Level 14 */
   if(level == 14) {
      data[0] = 0xFF; data[1] = 0xFF; data[2] = 0xFF;
      data[3] = 0xFF; data[4] = 0xFF; data[5] = 0xFF;
      data[6] = rnd(1,5);
      data[7] = 0x11; data[8] = 0x10;
      data[9] = 15;
      data[10] = 0x10 | rnd(0,1);
   }
   
   /* Level 15 */
   if(level == 15) {
      data[0] = 0xFF; data[1] = 0xFF; data[2]= 0xFF;
      data[3] = 0xFF; data[4] = 0xFF; data[5] = 0xFF;
      data[6] = 0x0F;
      data[7] = (rnd(1,5) << 4) | 0x01;
      data[8] = 0x10;
      data[9] = rnd(15,16);
      data[10] = 0x10 | rnd(0,1);
   }
   
   /* Level 16 */
   if(level == 16) {
      data[0] = 0xFF; data[1] = 0xFF; data[2] = 0xFF;
      data[3] = 0xFF; data[4] = 0xFF; data[5] = 0xFF;
      data[6] = 0x0F;
      data[7] = 0xF0 | rnd(1,5);
      data[8] = 0x10;
      data[9] = rnd(15,17);
      data[10] = 0x10 | rnd(0,1);
   }
   
   /* Level 17 */
   if(level == 17) {
      data[0] = 0xFF; data[1] = 0xFF; data[2] = 0xFF;
      data[3] = 0xFF; data[4] = 0xFF; data[5] = 0xFF;
      data[6] = 0x0F; data[7] = 0xFF;
      data[8] = rnd(0,10) << 4;
      data[9] = rnd(15,18);
      data[10] = 0x10 | rnd(0,1);
   }
   return 0;
}   

/* Check password for authenticity */      
int authenticate() {

   int area,floor;
   
   /* determine area */
   if(data[9] == 0 || (data[9] >= 2 && data[9] <= 4 &&
                     ((data[1] & 0xF0) != 0xF0))) {
      area = 0;
      if(data[10] != 0x00 && data[10] != 0x01) {
         return 36;
      }
   }
   else if(data[9] == 1 || (data[9] >= 4 && data[9] <= 9 &&
                              ((data[1] & 0xF0) == 0xF0))) {
      area = 1;
      if(data[10] != 0x00 && data[10] != 0x01) {
         return 37;
      }
   }
   else if(data[9] >= 10 && data[9] <= 14) {
      area = 2;
      if(data[10] != 0x00 && data[10] != 0x01) {
         return 38;
      }
   }
   else if(data[9] >= 15 && data[9] <= 18) {
      area = 3;
      if(data[10] != 0x10 && data[10] != 0x11) {
         return 39;
      }
   }
   else {
      return 35;
   }
   switch(area) {
      /* area 1 */
      case 0: 
          /* Level 1 */
         floor = (data[0] & 0xF0) >> 4;
         if(!((floor >=0 && floor <= 5) || floor == 15)) {
            return 1;
         }
         /* Level 2 */
         floor = data[0] & 0x0F;
         if(!((floor >= 0 && floor <= 5) || floor == 15)) {
            return 2;
         }
         /* Level 3 */
         floor = (data[1] & 0xF0) >> 4;
         if((data[0] & 0x0F) == 0x0F) {
            if ((data[0] & 0xF0) == 0xF0) {
               if(!((floor >= 0 && floor <= 10) || floor == 15)) {
                  return 3;
               }
            }
            else {
               if(!((floor >= 0 && floor <= 5) || floor == 15)) {
                  return 4;
               }
            }
         }
         else {
            if(floor != 1) {
               return 5;
            }
         }
         /* Level 4 */
         floor = data[1] & 0x0F;
         if(floor != 1) {
            return 6;
         }
         /* Levels 5-17 */
         if(data[2] != 0x11 || data[3] != 0x11 || data[4] != 0x11 ||
            data[5] != 0x11 || data[6] != 0x11 || data[7] != 0x11 ||
            data[8] != 0x10) {
            return 7;
         }
      break;
      /* area 2 */
      case 1: 
         /* Levels 1-2 */
      if(data[0] != 0xFF) {
            return 8;
         }
         /* Level 3 */
         floor = (data[1] & 0xF0) >> 4;
         if(floor != 15) {
            return 9;
         }
         /* Level 4 */
         floor = data[1] & 0x0F;
         if(!((floor >= 0 && floor <= 5) || floor == 15)) {
            return 10;
         }
         /* Level 5 */
         floor = (data[2] & 0xF0) >> 4;
         if(!((floor >= 0 && floor <= 5) || floor == 15)) {
            return 11;
         }
         /* Level 6 */
         floor = data[2] & 0x0F;
         if(!((floor >= 0 && floor <= 5) || floor == 15)) {
            return 12;
         }
         /* Level 7 */
         floor = (data[3] & 0xF0) >> 4;
         if(!((floor >= 0 && floor <= 5) || floor == 15)) {
            return 13;
         }
         /* Level 8 */
         floor = data[3] & 0x0F;
         if(data[1] == 0xFF && data[2] == 0xFF && 
            (data[3] & 0xF0) == 0xF0) {
            if(!((floor >= 1 && floor <= 5) || floor == 15)) {
               return 14;
            }
         }
         else {
            if(floor != 1) {
               return 15;
            }
         }
         /* Levels 9-17 */
         if(data[4] != 0x11 || data[5] != 0x11 || data[6] != 0x11 ||
            data[7] != 0x11 || data[8] != 0x10) {
            return 16;
         }
      break;
      /* area 3 */
      case 2: 
         /* Levels 1-8 */
         if(data[0] != 0xFF || data[1] != 0xFF || data[2] != 0xFF ||
            data[3] != 0xFF) {
            return 17;
         }
         /* Level 9 */
         floor = (data[4] & 0xF0) >> 4;
         if(!((floor >= 0 && floor <= 5) || floor == 15)) {
            return 18;
         }
         /* Level 10 */
         floor = data[4] & 0x0F;
         if(!((floor >= 0 && floor <= 5) || floor == 15)) {
            return 19;
         }
         /* Level 11 */
         floor = (data[5] & 0xF0) >> 4;
         if(!((floor >= 0 && floor <= 5) || floor == 15)) {
            return 20;
         }
         /* Level 12 */
         floor = data[5] & 0x0F;
         if(!((floor >= 0 && floor <= 5) || floor == 15)) {
            return 21;
         }
         /* Level 13 */
         floor = (data[6] & 0xF0) >> 4;
         if(data[4] == 0xFF && data[5] == 0xFF) {
            if(!(floor >= 0 && floor <= 10)) {
               return 22;
            }
         }
         else {
            if(floor != 1) {
               return 23;
            }
         }
         /* Level 14 */
         floor = data[6] & 0x0F;
         if(floor != 1) {
            return 24;
         }
         /* Levels 15-17 */
         if(data[7] != 0x11 || data[8] != 0x10) {
            return 25;
         }
      break;
      /* area 4 */
      case 3:
         /* Levels 1-12 */
         if(data[0] != 0xFF || data[1] != 0xFF || data[2] != 0xFF ||
            data[3] != 0xFF || data[4] != 0xFF || data[5] != 0xFF) {
            return 26;
         }
         /* Level 13 */
         floor = (data[6] & 0xF0) >> 4;
         if(floor != 0) {
            return 27;
         }
         /* Level 14 */
         floor = data[6] & 0x0F;
         if(!((floor >= 1 && floor <= 5) || floor == 15)) {
            return 28;
         }
         /* Level 15 */
         floor = (data[7] & 0xF0) >> 4;
         if(data[6] == 0x0F) {
            if(!((floor >= 1 && floor <= 5) || floor == 15)) {
               return 29;
            }
         }
         else {
            if(floor != 1) {
               return 30;
            }
         }
         /* Level 16 */
         floor = data[7] & 0x0F;
         if(data[6] == 0x0F && (data[7] & 0xF0) == 0xF0) {
            if(!((floor >= 1 && floor <= 5) || floor == 15)) {
               return 31;
            }
         }
         else {
            if(floor != 1) {
               return 32;
            }
         }
         /* Level 17 */
         floor = (data[8] & 0xF0) >> 4;
         if(data[6] == 0x0F && data[7] == 0xFF) {
            if(!((floor >= 1 && floor <= 10)) && floor != 0) {
               return 33;
            }
         }
         else {
            if(floor != 1) {
               return 34;
            }
         }
         break;
      default: break;      
   }
   return 0;
}

/* Generate random integer between a and b */
int rnd(int a, int b) {
   return (rand() % (b - a + 1)) + a;
}

/* Generate random integer amongst the set {a to b, c} */
int rndp(int a, int b, int c) {
   int temp;
    
   temp = (rand() % (b - a + 2)) + a;
   if(temp == b+1) {
      temp = c;
      }
   return temp;
}

------------------------------ code ends here ---------------------------------

--eof--