Game Gene Code Generation Algorithm

Discuss emulation of the Nintendo Entertainment System and Famicom.

Moderator: Moderators

Post Reply
User avatar
colinvella
Posts: 74
Joined: Sun Jun 05, 2016 1:41 pm

Game Gene Code Generation Algorithm

Post 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' };
Last edited by colinvella on Fri Jul 22, 2016 1:33 am, edited 2 times in total.
Tile IDE and tile engine for XNA: http://tide.codeplex.com/
Fancy Fish Mod - Minecraft Mod: http://fancyfishmod.weebly.com/
Bavi_H
Posts: 193
Joined: Sun Mar 03, 2013 1:52 am
Location: Texas, USA
Contact:

Re: Game Gene Code Generation Algorithm

Post 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.
User avatar
Myask
Posts: 965
Joined: Sat Jul 12, 2014 3:04 pm

Re: Game Gene Code Generation Algorithm

Post 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.
Attachments
Default cursor positions.
Default cursor positions.
GGenieN2d8.png (1.06 KiB) Viewed 5218 times
Bavi_H
Posts: 193
Joined: Sun Mar 03, 2013 1:52 am
Location: Texas, USA
Contact:

Re: Game Gene Code Generation Algorithm

Post 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.
Attachments
game-genie-write-catcher.zip
(1.53 KiB) Downloaded 108 times
Last edited by Bavi_H on Sat May 05, 2018 7:25 am, edited 1 time in total.
User avatar
Myask
Posts: 965
Joined: Sat Jul 12, 2014 3:04 pm

Re: Game GenIe Code Generation Algorithm

Post 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).
Bavi_H
Posts: 193
Joined: Sun Mar 03, 2013 1:52 am
Location: Texas, USA
Contact:

Re: Game GenIe Code Generation Algorithm

Post 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.)
User avatar
colinvella
Posts: 74
Joined: Sun Jun 05, 2016 1:41 pm

Re: Game Gene Code Generation Algorithm

Post 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.
Tile IDE and tile engine for XNA: http://tide.codeplex.com/
Fancy Fish Mod - Minecraft Mod: http://fancyfishmod.weebly.com/
User avatar
thefox
Posts: 3134
Joined: Mon Jan 03, 2005 10:36 am
Location: 🇫🇮
Contact:

Re: Game Gene Code Generation Algorithm

Post 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.
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi
User avatar
colinvella
Posts: 74
Joined: Sun Jun 05, 2016 1:41 pm

Re: Game Gene Code Generation Algorithm

Post 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.
Tile IDE and tile engine for XNA: http://tide.codeplex.com/
Fancy Fish Mod - Minecraft Mod: http://fancyfishmod.weebly.com/
User avatar
colinvella
Posts: 74
Joined: Sun Jun 05, 2016 1:41 pm

Re: Game Gene Code Generation Algorithm

Post 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' };
Tile IDE and tile engine for XNA: http://tide.codeplex.com/
Fancy Fish Mod - Minecraft Mod: http://fancyfishmod.weebly.com/
User avatar
Jarhmander
Formerly ~J-@D!~
Posts: 568
Joined: Sun Mar 12, 2006 12:36 am
Location: Rive nord de Montréal

Re: Game Gene Code Generation Algorithm

Post 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.
((λ (x) (x x)) (λ (x) (x x)))
Bavi_H
Posts: 193
Joined: Sun Mar 03, 2013 1:52 am
Location: Texas, USA
Contact:

Re: Game Gene Code Generation Algorithm

Post 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 5120 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 5120 times
Post Reply