gameshark-optimization.md

GameShark Optimization

You are working on a memory hacking system that can overwrite the memory on a console via key/value pairs of memory address to value. The basic syntax looks like this:

8120770A FFEB
50000D01 0000
8020770C 007F
8120771E 7F1F

Where the first two digits of each line represent the write type, the next six represent the memory address (in hexadecimal), and the last four represent the value being written.
The write types are as follows:

• 81: Two bytes (four hex digits) will be written at the address
• 80: One byte (two hex digits) will be written at the address
• 50: This is a special write action, akin to a for loop:
  • The line is formatted 5000XXYY ????, where XX is the number of addresses to be written, and YY is the offset between each address. We can ignore the ???? for now. Then, whatever the next line is (an 80 or 81 line) will be repeated XX times, incrementing the address by YY each time.
  • In the example above, this means we would be writing the byte 7F 14 (0D plus one) times starting at address 20770C

Here's the problem: most programs do not take advantage of the 50 syntax, and end up being very long and unruly. We need a way to automatically detect when we could be using the 50 syntax to shorten programs (by shorten, we mean reduce the total number of lines).
But it gets tricker. It's possible to use a 50 line to write over a series of addresses, then go back and individually correct addresses that have been written over. Consider this program:

81207708 7F7F
8120770A 7F7F
8120770C 7F7F
8120770E 0000
80207710 007F

This program doesn't have an unbroken repetition in the values it's writing, but it can still be shortened to the following:

50000801 0000
80207708 007F
8120770E 0000

This program would still result in the same memory mapping, but it's two lines shorter.

How can we dynamically determine where these loops could shorten our program, while still considering that the loops themselves do not have to result in the correct memory, as long as fixing the values after the loop still results in the entire program being fewer lines?