Page 1 of 1

Game Gene Code Generation Algorithm

Posted: Thu Jul 21, 2016 2:28 pm
by colinvella
I just wanted to share an algorithm (in C#) for converting two types of cheats (substitute and compare-and-substitute) into Game Genie codes. The Game Genie decoding algorithm can be found online (http://tuxnes.sourceforge.net/gamegenie.html) but I couldn't find one for the encoding process. Most likely there's one in some emulator's source repository somewhere but I was too lazy to keep searching and decided to have a go at reversing the decoding process myself :)

Some things to note:
  • The algorithm here is in the form of a property (getter method) of a Cheat class. It has access to properties: Address (unsigned short), Value (byte), NeedsComparison (boolean) and CompareValue (byte)
  • When NeedsComparison is False, CompareValue is ignored and two 6-letter Game Genie code variants are generated using Address and Value only. This is a substitute-only code
  • When NeedsComparison is True, CompareValue is taken into consideration and two 8-letter Game Genie code variants are generated using Address, Value and CompareValue. This is a compare-and-substitute code
  • The algorithm generates two code variants because bit 7 of the 3rd letter nybble in the code is not used when decoding the cheat properties and can hence be either 1 or 0. The two variants differ only in the 3rd letter. For example, the codes GOSSIP and GOISIP both represent the same cheat (substitute $14 at address $D1DD)
  • The algorithm does not work with cheats that target the lower 32K of the address space since when decoded, the addresses are mapped in the upper 32K (3rd letter bit 7 could have been used for this purpose, in hindsight)


So here goes:

Code: Select all

       public string GameGenieCode
        {
            get
            {
                byte[] nybbles = new byte[NeedsComparison ? 8 : 6];

                // reverse of
                // address = 0x8000 + ((n3 & 7) << 12) | ((n5 & 7) << 8) | ((n4 & 8) << 8) | ((n2 & 7) << 4) | ((n1 & 8) << 4) | (n4 & 7) | (n3 & 8);

                // common to both 6-letter and 8-letter codes
                nybbles[0] = (byte)(((Value   >> 4) & 8) | ((Value   >>  0) & 7));
                nybbles[1] = (byte)(((Address >> 4) & 8) | ((Value   >>  4) & 7));

                nybbles[2] = (byte)(((Address >> 4) & 7)); // unknown bit 7 produces 2 variants
                nybbles[3] = (byte)(((Address >> 0) & 8) | ((Address >> 12) & 7));
                nybbles[4] = (byte)(((Address >> 8) & 8) | ((Address >>  0) & 7));

                if (NeedsComparison)
                {
                    // reverse of
                    // data = ((n1 & 7) << 4) | ((n0 & 8) << 4) | (n0 & 7) | (n7 & 8);
                    // compare = ((n7 & 7) << 4) | ((n6 & 8) << 4) | (n6 & 7) | (n5 & 8);
                    nybbles[5] = (byte)(((CompareValue >> 0) & 8) | ((Address      >> 8) & 7));
                    nybbles[6] = (byte)(((CompareValue >> 4) & 8) | ((CompareValue >> 0) & 7));
                    nybbles[7] = (byte)(((Value        >> 0) & 8) | ((CompareValue >> 4) & 7));
                }
                else // 6 letter code
                {
                    // reverse of
                    // data = ((n1 & 7) << 4) | ((n0 & 8) << 4) | (n0 & 7) | (n5 & 8);
                    nybbles[5] = (byte)(((Value   >> 0) & 8) | ((Address >> 8) & 7));
                }

                StringBuilder stringBuilder = new StringBuilder();
                foreach (byte nybble in nybbles)
                    stringBuilder.Append(gameGenieNybbleToChar[nybble]);

                stringBuilder.Append(" / ");

                nybbles[2] |= 8; // variant

                foreach (byte nybble in nybbles)
                    stringBuilder.Append(gameGenieNybbleToChar[nybble]);
                
                return stringBuilder.ToString();
            }
        }

        public static char[] gameGenieNybbleToChar = new char[]
            { 'A', 'P', 'Z', 'L', 'G', 'I', 'T', 'Y',
              'E', 'O', 'X', 'U', 'K', 'S', 'V', 'N' };

Re: Game Gene Code Generation Algorithm

Posted: Thu Jul 21, 2016 7:21 pm
by Bavi_H
colinvella wrote:The algorithm generates two code variants because bit 7 of the cheat Address is not used when decoding the cheat properties and can hence be either 1 or 0. The two variants differ only in the 3rd letter. For example, the codes GOSSIP and GOISIP both represent the same cheat (substitute $14 at address $D1DD)
When entering codes on an actual Game Genie, the high bit of the third letter helps move the cursor automatically to make entering codes easier.

After you enter the 6th letter, the Game Genie checks if the high bit of the third letter is clear. If so, it will move the cursor to the next line. (If you're on the last line, the cursor will stay on the 6th letter.) You can still add the 7th and 8th letters by pressing B to back up or by clicking on the 7th blank. Any 8-letter code is converted to a "compare and value" modification, no matter what the value of the extra bit is.

If the Game Genie thinks it was an 8-letter code, you can click on the next line to skip the 7th and 8th letters and enter another code. Any 6-letter code is converted to a "value only" modification, no matter what the value of the extra bit is.

But setting the extra bit correctly is a nice thing to do in case the code is ever used on a real Game Genie. When the bit is set wrong, you'll have to manually adjust the cursor.

Re: Game Gene Code Generation Algorithm

Posted: Thu Jul 21, 2016 9:35 pm
by Myask
Bavi beat me to it. GOSSIP is a bad example for this reason, it has the "8-character code?" bit (n2&8) set, but is six-character.?
I wasn't sure if it controlled the compare check or just the input.
*doublechecks* PowerPak seems to just go "is it 8 characters" too to decide "is this a compare cheat?" (So does Mednafen.)
One should set it for cheats that use the compare value, though.

Re: Game Gene Code Generation Algorithm

Posted: Thu Jul 21, 2016 10:15 pm
by Bavi_H
Myask wrote:I wasn't sure if it controlled the compare check or just the input.
I should clarify that I have only tested with the Game Genie ROM, not the actual Game Genie hardware. I used the FCEUX script attached below to capture the writes the Game Genie uses to send the codes to its hardware as described in these posts:
My understanding is the bits described as "set if an 8-letter code" or "compare enable" are what actually turns on the "compare and value" ability. When I tested the Game Genie ROM in FCEUX, I found these bits are set for any 8 letter code, it doesn't matter what the "extra bit" (the high bit of the 3rd letter) is. These results make me think the Game Genie only uses the "extra bit" to move the cursor.

Note: If you re-create the test, be aware that if you enter multiple codes for the same address, the Game Genie only uses the first one and marks the others as invalid/disabled. For example, you'll have to test GOSSIP and GOISIP on separate runs, not by entering them both on the same run.

EDIT 2018-05-05: Put the lua file inside a zip file because lua attachments are now disabled for security reasons.

Re: Game GenIe Code Generation Algorithm

Posted: Thu Jul 21, 2016 10:42 pm
by Myask
Bavi_H wrote: Note: If you re-create the test, be aware that if you enter multiple codes for the same address, the Game Genie only uses the first one and marks the others as invalid/disabled. For example, you'll have to test GOSSIP and GOISIP on separate runs, not by entering them both on the same run.
Hmm, that would mean you can't patch the same byte simultaneously in different banks even if it's different.

Quickly verified on real NES/GG/SMB3 that it's 6/8 character that matters, not n2&8: IEUXKGAA (Tanooki Mario start, SMB3) , IEUXKG, IELXKG, IELXKGAA all still perform the modification (bit set without a full 8-character code does not make for an invalid length, apparently). IELXKGAP (compare = 10 instead of 00, but 8-char bit unset) does not, much like IEUXKGAP (compare = 10, 8-char set).

Re: Game GenIe Code Generation Algorithm

Posted: Thu Jul 21, 2016 11:51 pm
by Bavi_H
Bavi_H wrote:be aware that if you enter multiple codes for the same address, the Game Genie only uses the first one and marks the others as invalid/disabled.
Myask wrote: Hmm, that would mean you can't patch the same byte simultaneously in different banks even if it's different.
Yep. The Game Genie manual [PDF] says if you enter multiple codes and they don't work as you expected to try entering them in a different order. I think this was in case you tried to enter two codes that used the same address. Since you can't get them both to work at the same time, re-arranging them might make you a little happier that you can at least get one to work at a time, instead of just thinking the disabled code didn't work at all.


Another interesting thing from the manual: I now know that the "programming methods" in the manual describe how you can swap letters in a way that changes the "value" part of the code without affecting the "address" or "compare" parts, and without telling you what the letters actually mean.

(When I first read my cousin's Game Genie manual as a kid, I saw the programming section in the contents and was excited, thinking it would explain how the letters mapped to addresses and values like POKEs on my Commodore 64. I quickly flipped to that section and read it, but I was so mad it only told you to play around with swapping letters and didn't tell you what they meant.)

Re: Game Gene Code Generation Algorithm

Posted: Fri Jul 22, 2016 12:35 am
by colinvella
I keep wondering why CodeMasters (or whoever came up with the Game Genie coding system) chose to not use bit 8 of the third nybble letter in the code and restrict the resulting address to the top 32K. Had they included the bit in the coding process, they would have been able to address the lower 32K as well, allowing cheats in lower ram, including PPU and joypad registers.

Re: Game Gene Code Generation Algorithm

Posted: Fri Jul 22, 2016 12:46 am
by thefox
colinvella wrote:I keep wondering why CodeMasters (or whoever came up with the Game Genie coding system) chose to not use bit 8 of the third nybble letter in the code and restrict the resulting address to the top 32K. Had they included the bit in the coding process, they would have been able to address the lower 32K as well, allowing cheats in lower ram, including PPU and joypad registers.
This would not have been technically possible. The cart connector does not have the necessary signals to unmap the 2 KB RAM from the bus (which would be required to override the value). Same goes for the CPU/PPU registers.

Re: Game Gene Code Generation Algorithm

Posted: Fri Jul 22, 2016 12:53 am
by colinvella
thefox wrote:
colinvella wrote:I keep wondering why CodeMasters (or whoever came up with the Game Genie coding system) chose to not use bit 8 of the third nybble letter in the code and restrict the resulting address to the top 32K. Had they included the bit in the coding process, they would have been able to address the lower 32K as well, allowing cheats in lower ram, including PPU and joypad registers.
This would not have been technically possible. The cart connector does not have the necessary signals to unmap the 2 KB RAM from the bus (which would be required to override the value). Same goes for the CPU/PPU registers.
I think I see what you mean. Some cartridges can do some nifty tricks with the bus (the MMC5 extended graphics mode and Namco 163 nametable banking comes to mind), but they do not have access to the first 8K main memory accessible to the CPU. This wasn't immediately obvious to me as my cheat system sits between CPU and main memory, not CPU and cartridge.

Re: Game Gene Code Generation Algorithm

Posted: Fri Jul 22, 2016 1:54 am
by colinvella
Here's an update of the encoder that sets the 8 letter bit correctly. Only one code is generated.

Code: Select all

        public string GameGenieCode
        {
            get
            {
                byte[] nybbles = new byte[NeedsComparison ? 8 : 6];

                // reverse of
                // address = 0x8000 + ((n3 & 7) << 12) | ((n5 & 7) << 8) | ((n4 & 8) << 8) | ((n2 & 7) << 4) | ((n1 & 8) << 4) | (n4 & 7) | (n3 & 8);

                // common to both 6-letter and 8-letter codes
                nybbles[0] = (byte)(((Value   >> 4) & 8) | ((Value   >>  0) & 7));
                nybbles[1] = (byte)(((Address >> 4) & 8) | ((Value   >>  4) & 7));

                nybbles[2] = (byte)(((Address >> 4) & 7));
                nybbles[3] = (byte)(((Address >> 0) & 8) | ((Address >> 12) & 7));
                nybbles[4] = (byte)(((Address >> 8) & 8) | ((Address >>  0) & 7));

                if (NeedsComparison)
                {
                    nybbles[2] |= 8; // set 3rd nybble bit 7 to make it behave nicely in real Game Genie
 
                    // reverse of
                    // data = ((n1 & 7) << 4) | ((n0 & 8) << 4) | (n0 & 7) | (n7 & 8);
                    // compare = ((n7 & 7) << 4) | ((n6 & 8) << 4) | (n6 & 7) | (n5 & 8);
                    nybbles[5] = (byte)(((CompareValue >> 0) & 8) | ((Address      >> 8) & 7));
                    nybbles[6] = (byte)(((CompareValue >> 4) & 8) | ((CompareValue >> 0) & 7));
                    nybbles[7] = (byte)(((Value        >> 0) & 8) | ((CompareValue >> 4) & 7));
                }
                else // 6 letter code
                {
                    // reverse of
                    // data = ((n1 & 7) << 4) | ((n0 & 8) << 4) | (n0 & 7) | (n5 & 8);
                    nybbles[5] = (byte)(((Value   >> 0) & 8) | ((Address >> 8) & 7));
                }

                StringBuilder stringBuilder = new StringBuilder();
                foreach (byte nybble in nybbles)
                    stringBuilder.Append(gameGenieNybbleToChar[nybble]);
                
                return stringBuilder.ToString();
            }
        }

        public static char[] gameGenieNybbleToChar = new char[]
            { 'A', 'P', 'Z', 'L', 'G', 'I', 'T', 'Y',
              'E', 'O', 'X', 'U', 'K', 'S', 'V', 'N' };

Re: Game Gene Code Generation Algorithm

Posted: Fri Jul 22, 2016 5:27 am
by Jarhmander
Bavi_H wrote:
colinvella wrote:The algorithm generates two code variants because bit 7 of the cheat Address is not used when decoding the cheat properties and can hence be either 1 or 0. The two variants differ only in the 3rd letter. For example, the codes GOSSIP and GOISIP both represent the same cheat (substitute $14 at address $D1DD)
When entering codes on an actual Game Genie, the high bit of the third letter helps move the cursor automatically to make entering codes easier.

After you enter the 6th letter, the Game Genie checks if the high bit of the third letter is clear. If so, it will move the cursor to the next line. (If you're on the last line, the cursor will stay on the 6th letter.) You can still add the 7th and 8th letters by pressing B to back up or by clicking on the 7th blank. Any 8-letter code is converted to a "compare and value" modification, no matter what the value of the extra bit is.

If the Game Genie thinks it was an 8-letter code, you can click on the next line to skip the 7th and 8th letters and enter another code. Any 6-letter code is converted to a "value only" modification, no matter what the value of the extra bit is.

But setting the extra bit correctly is a nice thing to do in case the code is ever used on a real Game Genie. When the bit is set wrong, you'll have to manually adjust the cursor.
Oh man, you just gave me the info I needed! I made too a Game Genie code generator/decoder and was wondering what's the purpose of that bit, and I ended up adding a parameter to select which of the 2 equivalent codes to return for encoding a Game Genie code.

Re: Game Gene Code Generation Algorithm

Posted: Fri Jul 22, 2016 7:34 pm
by Bavi_H
The most popular explanations of the Game Genie encoding assign values to the letters like this:

letter: APZLGITY
hex...: 01234567

letter: EOXUKSVN
hex...: 89ABCDEF

If you use these assignments, you have to move the bits like this:
top: In a 6-letter code, letters 1 through 6 are rearranged to value and address.<br />bottom: In an 8-letter code, letters 1 through 8 are rearranged to value, address, and compare.
top: In a 6-letter code, letters 1 through 6 are rearranged to value and address.
bottom: In an 8-letter code, letters 1 through 8 are rearranged to value, address, and compare.
extra-bits-high.png (8.32 KiB) Viewed 5121 times
In A Note on Game Genie Codes for the NES, the author explains if you assign values to the letters this way:

letter: APZLGITY
hex...: 02468ACE

letter: EOXUKSVN
hex...: 13579BDF

Then the bit movement is easier (a shift and some nybble swaps):
top: In a 6-letter code, letters 1 through 6 are rearranged to value and address.<br />bottom: In an 8-letter code, letters 1 through 8 are rearranged to value, address, and compare.
top: In a 6-letter code, letters 1 through 6 are rearranged to value and address.
bottom: In an 8-letter code, letters 1 through 8 are rearranged to value, address, and compare.
extra-bits-low.png (10.44 KiB) Viewed 5121 times