The Nintendo Entertainment System was my first console. My parents were very much against video games, so their directive was that if I was to have a console, I'd have to buy it myself.

So I got a paper route. Well, two paper routes, really. It took me about two years to earn enough money to finally buy an NES, and after I did, I whiled away so much of my life stomping goombas and slaying bosses. Kept the paper route, though.

The NES did not have very much of anything, really. A 1.79MHz processor, 2Kb ram, 2Kb video ram, and 256b sprite ram. Cartridges weren't very powerful either – 32kb for games, and 8kb for sprites. This is comparatively nothing; game developers fit entire worlds into this tiny space, and they had to be quite clever doing so. It's why the clouds and bushes in Super Mario Bros. were the same, but with a different colour bit set.

Because of these hardware limitations, the NES did not have the ability to save games until a cartridge was designed with a button battery. It was revolutionary.

But the part I want to focus on is the solution that predated saving games. Instead, the state of one's game was preserved in alphanumeric strings, and you had to enter them into a password screen when you powered on the console. This too happened in the context of very limited storage and execution space; a password system had to be both data-dense and computationally efficient.

Metal Gear had just such a save system, using a 25 character string (ignoring the spaces). The game had a large map, four ranks, 25 items, 8 weapons, 22 prisoners to rescue, and 9 bosses. That's a lot of data to encode in a very small space.

Here's how that worked.

First, a save state table is created in read-only-memory. For the sake of efficiency, a five-bit binary number is used for each character of the table. This allows the encoding of five data points in one character, expanding the data that can be encoded in 25 characters to 125 data points. Each character then has 32 states: 1-6 and A-Z can be encoded this way using the binary digits 00000 through 11111. (26 letters and 6 numbers = 32 bits)

As a result, a table of binary values can be built in which each line sums to a character in the password sequence. After struggling with getting a ROM disassembler running, I found this github repo that has an annotated copy of the disassembled passwords.asm file. Score.

Based on the assembly language in that repo, the password table looks like this:

As a simple example, if you had 23 handgun ammo, row 11 would read 10111:

16 + 0 + 4 + 2 + 1 = 23

Because this row is a count, the math is straight binary to integer – base 2 to base 10. But it gets weirder.

As an example with a mix of binary and boolean values (0 = false, 1 = true): if you had 74 handgun ammo and had rescued prisoners 17 and 19, row 22 would read 10101:

 1 + 0 + 1 + 0 + 1 = 21

Note the 0 in the second column. This is because 72 is less than 96 (64 + 32), so the bit representing 32 is set to off – it's not needed. This is a mix of integer and boolean math – the 21 is valueless for our purposes, except as an index into the character selection table below. Just, it's the base-10 version of 10101. The count of ammo for the handgun is split across two rows.

Instead of having the user enter ones and zeroes, the sequence is transposed according to a mapping to characters:

Returning to the previous examples, the value for 23 handgun ammo, in row 11, with value 10111 can be found in index 23: the character R.

A complete example combining the two above alters the count a little bit. Row 11's maximum value (11111) represents 31 handgun ammo, and Row 22's maximum value (also 11111) indicates 96 handgun ammo and having rescued prisoners 17 through 19. Combining the two examples above brings gives us 23 + 74 = 87 ammo, so let's work that out.

The binary value of 87 is split across the two characters (11 and 22). The bits for 64 and 32 are in row 22, while the bits for 16, 8, 4, 2, and 1 are in row 11. Row 11 has 10111, while row 22 has 10101. The first two bits represent the 64 and 32 bits of the count of handgun ammo, which can then be appended to the values in row 11 to produce 1010111 - a seven-bit binary number representing 87.

Snake begins the game at rank 1, so the first row is 00001, which maps to the character '2'. With 87 handgun ammo and prisoners 17 and 19 rescued, the password looks like this:

21111 - 11111 - R1111 - 11111 - 1P11?

The last character (? to indicate unknown) is a checksum. This is a security measure. Because the assembly is bananas, I had to have a look at a password generator to work out how it gets set:

private int AccurateChecksum(int[] table) {
    int sum = 7;
    int carry = 0;  //simulate the carry flag

    for(int letter = 23; letter >= 0; letter--) {
        //add with carry
        sum += table[letter] + carry;

        //set the carry flag if the sum goes over 255 (0xFF)
        carry = (sum > 0xFF) ? 1 : 0;

        //truncate sum to one byte
        sum &= 0xFF;
    }

    //and sum with 0x1F (31)
    sum &= 0x1F;

    return sum;
}

So: sum 7 and the characters in the password moving backwards, carry the 1 when sum goes over 255, trim it to one byte, then apply a mask to constrain the value to 5 bits – the value then is between 00000 and 11111 – the bounds of the 1-6 and A-Z frame.

So, with our example password 21111 - 11111 - R1111 - 11111 - 1P11?:

7 +                         ####  Pad
(0 + 0 + 21 + 0) +          ####  11P1   
(0 + 0 + 0 + 0 + 0) +       ####  11111
(0 + 0 + 0 + 0 + 23) +      ####  1111R
(0 + 0 + 0 + 0 + 0) +       ####  11111
(0 + 0 + 0 + 0 + 2)         ####  11112
=  51

51 in binary is 00110011, but we only want the last five bits, so 10011 – the final character should be N.

That said, it very well may be an impossible game state to have ammo without having the item that consumes that ammo. In that case, the handgun flag is in the 3rd row, so that sequence would read 00001, which maps to 2. Our password then is:

21211 11111 R1111 11111 1P11?

And the checksum then sums to 53 – 00110101. The lopped five-bit sequence, finally, is 10101. In this case, the checksum character would instead be P.

Ok, but why?

To make testing easier. This is the universal reason cheats exist in games. So that testers can set the game into a desired state without having to do the work of getting to that state. They can then make sure the game acts as expected.

No, why write about it?

Well, because it's neat. Metal Gear came out in 1989, long before we were all thinking in digital metaphors. This work was done against the backdrop of a very analogue world – people were thinking about gear ratios and electromechanical relays. Not ones and zeroes.

Also, this work was done in a very low-level language: Assembly. Specifically 6502 Assembly. Here's an example. So much of the work is just moving data into registers and doing math on them.

These games were made by wizards, is ultimately why. It's only when I got a glimpse at the runes on a page that I began to see the complexity of the spellbook. It's part of the appeal of software – its lore goes incredibly deep.