Levellass's Patching Tutorial

This is where you can post your Commander Keen related stories, artwork, or other stuff that is related to Commander Keen but otherwise doesn't belong in another forum.
User avatar
Levellass
S-Triazine
Posts: 5265
Joined: Tue Sep 23, 2008 6:40

Levellass's Patching Tutorial

Post by Levellass »

Thinking of making this an article on the wiki, not sure if worth it though.


This is a basic guide to understanding and creating patches for the Commander Keen games. It is intended to be a step-by-step guide from simple to complex patch techniques for the novice patcher. It is currently incomplete.


STEP 1: SETTING UP.

First read Ceilick's or my modding tutorial: http://www.shikadi.net/keenwiki/Ceilick ... g_Tutorial This will inform you of basic mod setup as well as get you some rudimentary patches and an idea of how things work. For graphics editing use Keengraph, this will make things easier later on.

Some basic patch utilities can be found in a special zip crated for this tutorial, TutoriTools:

The only other thing you'll need at the moment is a 'hex editor' with which you can view raw Keen code. For preference I use XVI32: http://xvi32.en.softonic.com/ Download and install and that's it!



STEP 2: COPYING PATCHES.

This is the simplest way to get patches, the Keen wiki contains over 4'000 individual example patches all annotated with perfectly comprehensible gibberish. For the most part these can be copy-and-pasted straight into your patch file. The best place to start is the main Patch Index, which lists all the pages with patches on them: http://www.shikadi.net/keenwiki/Category:All_patches

As an example, say we wish to increase the number of lives Keen has in Keen 5 when he starts a new game. We will thus be searching the wiki for 'lives' or 'new game' As it so happens the Patch:Lives page ( http://www.shikadi.net/keenwiki/Patch:Lives ) has a section with the patch we want:

Code: Select all

#Lives Keen has at game start -Keen 5
%patch $5C9B $6F6AW $0003W #3 lives

This can be copied straight from the wiki as-is. It's quite obvious here that the '$0003W' somehow stands for '3 lives'. We don't need to know how just yet, we can change this number to change the number of lives Keen has. helpfully the wiki has most of such changeable numbers color-coded in blue for quick identification.

Using this approach the novice patcher can build an entire mod based on the work of what others have done before. But there are issues; for example, if we give Keen $0010W lives he starts the game not with 10, but with 16 lives, what's going on? Maybe if we look deeper at what we're doing...


STEP 3: TRACKING YOUR CHANGES

By now you should have a patch file full of things you want in your mod or just want to test. But is there any way to track just what's going on? Yes, and it involves the 'hex editor' we downloaded earlier.

First we need to create a 'dump file' for our mod. This is a complete copy of the patched executable as it exists after CKPatch has finished doing everything. We should also have a 'clean dump', one that nothing has been changed in. To do this we will put two 'dump commands' into our patch file, one at the start, one at the end. Set up your patch file to look something like this:

Code: Select all

%ext ck4

#Clean dump
%dump DCLEAN.DMP

#Patches,
#More patches

#Modified dump
%dump DMOD.DMP

%end

Now when you run your mod two files will be created in your mod folder. These will be overwritten each time you run your mod, updating any changes. (As these are for testing be sure and remove the %dump commands when you release your mod.)

Now attempt to open the files. Hopefully you can't, the .DMP file type shouldn't be used by anything. You should get a suggested list of programs you can use that contains XVI32, if not you can browse your own computer to find XVI32 and select that. Make sure to tick 'always use this program'!

XVI32 will open with the files in two windows. It looks like a whole bunch of numbers on the left side and weird ASCII symbols on the right. This is the raw code of the Keen games. To look at our patch press ctrl-G to open the goto menu. There you can type in the very first number of your patch, in the case of our example this is '$5C9B' (You don't need the '$' but you can type it in if you want. Press enter.

You should now see a different set of numbers in the window, this s the code at the location of the patch. Do the same for the other window\file. Now you can see a before and after view of the game's code side-by-side. If you did everything right you should see a string of numbers like '6A $6F $10 $00' This seems to be a slightly garbled version of our patch's numbers, '$6F6AW $0010W' Ok, but what does that mean?


STEP 4: DEC, HEX, BYTES, WORDS AND LONGS

Now we move on to the structure of patches themselves and how they may be more precisely edited. Patches are nearly universally based on 'hexadecimal' where numbers are based on 16 instead of 10. Reading this short introduction may help, but isn't necessary. https://en.wikipedia.org/wiki/Hexadecimal

Basically patch numbers are a bit odd. Fortunately anyone with windows doesn't actually need to know much about this. Simply fire up windows inbuilt calculator and press alt-3 to covert it to programming mode. At the top left of the window there are four possible options, Bin, Oct, Dec and Hex. Switching between these will automatically convert a number you have typed in.

Normal numbers, and the mode you will start in, are 'dec' for 'decimal'. If we type in 10 here we can see the proper patch number by switching to 'hex' mode. We see 'A' meaning for 10 lives we should use this patch:

Code: Select all

#Lives Keen has at game start -Keen 5
%patch $5C9B $6F6AW $000AW #10 lives

This is unbelievably useful; a lot of patches can be hard to figure out if the numbers are large and in hex. This simple method will often shed light on things.

But why is the code arranged differently? Why was it scrambled when we looked at it? This is part of how CKPatch deals with information. As an example the following three patches do *exactly the same thing*:

Code: Select all

#Lives Keen has at game start -Keen 5
%patch $5C9B $6A $6F $03 $00

#Lives Keen has at game start -Keen 5
%patch $5C9B $6F6AW $0003W

#Lives Keen has at game start -Keen 5
%patch $5C9B $00036F6AL

The three patches are written using bytes, words and longs (Double words.) These are different ways of arranging the same data. Keen's code is arranged in bytes, in patches single two-digit numbers. Two of these make a word and four a long. But due to the interesting way (some) computers work to get these you need to rearrange the numbers slightly. $0003W makes sense, but as bytes the second part ($03) comes *before* the first ($00) When you build up a word or long from bytes you need to reverse the byte order!

This explains the odd way the code appears, but why use words and longs at all? For one thing, clarity; '$0003W' is simpler to deal with, 258 is $0102W in word form which is how it appears in windows calculator. Split up into bytes it's $02 $01 which is a little confusing. Many numbers in Keen use the word format, requiring two bytes. (And some require four.)

A note of cation, while you can rearrange patches like this, do NOT attempt to change a single byte into a word or long or vice-versa. The result will not 'fit' into Keen's code. The equation must balance, two bytes to a word, two words to a long.


STEP 5: EDITING EXISTING PATCHES

But something else is odd here, what does '$6F6AW' mean? It's coded in brown and a very big number, why is it there? The patch description mentions two hotlinks, one to the 'new game' patch for more patches and one to 'game stats': http://www.shikadi.net/keenwiki/Patch:Game_stats The Game Stats page has a number of interesting sections dealing in just how such numbers work. While not necessary reading for us yet, investigation will explain a lot about how patches work.

The vital takewaway is that by exploring the wiki instead of just straight copying a patcher can get a better idea of what their patches actually *do*. If in doubt looking at similar patches can be informative. More complex explanations including a full one about the brown numbers will be later. For now we focus on one question:

What if the wiki doesn't have what you want?


STEP 6: FIND AND REPLACE

Say we want to change Keen's standing animation so it's the same as his looking up one, but for some reason the wiki doesn't have a patch for Keen's standing animation. In this case we must look for possible patches in the game's code. Then we can write our own patch at that location! As such we open up the *clean* dump file in XVI32.

First we need to know what we're looking for. Obviously somewhere is a number for Keen's standing image. To find out what that is we open the mod's graphics folder and find Keen's standing sprite image. As it turns out there are two, left and right. If you're using Modkeen, tough luck, things get tricky. But in Keengraph the two images are 5SPR0108.BMP and 5SPR0116.BMP. These two numbers, 108 and 116 are what are used by the game. (In Modkeen they're not, sorry.)

Likewise Keen's looking up image (There's only one!) is 5SPR0124.BMP. Converting these in windows calculator gives us $6C and $74 as the originals and $7C as our desired change. In XVI32 we goto the search menu, select 'count' and type in '74' in the 'hex string' box.

1'947 matches. Oh.

But wait! Most numbers in Keen are words! That's $0074W or $74 $00! We search for that.

31 matches. Still a lot. Maybe try them later. What about $6C $00? 18 matches. Using Ctrl-F we can find the first one, then use the F3 key to find the next, and next, and next...

The first match is at $2AE4 (Look at the 'Adr. Hex' counter at the bottom left of the window.) The second at $3041E and so on. We thus start building a possible patch list that looks like this:

Code: Select all

#Possible Keen standing image patches:
%patch $2AE4  $007CW 
%patch $3041E $007CW 

But do we *really* want to test each of these out one at a time? That sounds like hard work. So let's patch smarter. We can eliminate a few right off the bat. The second patch for example. In XVI32 we can see on the right of the window a bunch of text, in fact the patch is part of the 'l' in 'normal', one of the difficulty options! That's probably not what we're looking for. The third patch is the same. We can toss out quite a few patches this way.

What's left we can test half at a time; if we have ten patches test 5 at once, if nothing happens, test the other five, if something happens discard the second set and split the 5 possible patches into 3 and 2. In this way a large number of patches can be tested in a short time. (Though some might crash the game, which makes things harder.)

But as it so happens a smart patcher won't even need to do this. The fourth possible match is at $30BCA, in fact the hex code it's buried in is '$74 $00 $6C $00 $03 $00' $74? Isn't that the other thing we were searching for? Looks suspicious! And won't you know it? These patches change Keen's standing animation:

Code: Select all

#Change Keen's standing animation in Keen 5
%patch $30BC8 $007CW
%patch $30BCA $007CW

For the true novice this is probably the only way of finding new patches. It's slow and inefficient but it works surprisingly often. But with all the patches we have, is there a way of being faster about things?


STEP 7: LOCATION, LOCATION, LOCATION

One method of being faster is getting an idea of where you should be looking. Quite often a patch exists for one game or situation but not the exact one you want. The Keen Vorticons and Keen Galaxy games form two series based on the same basic code, most pates work the same way between games. If you know a patch for one game you can often use it to make a patch for another.

We should expect that the game's code is organized in a similar manner in each game in a series, so stuff in one game will be in sort of the same place as it is in another. As an example consider the 'lives at start' patch from above. In Keen 4, 5 and 6 it is as follows:

Code: Select all

#New game lives patches
%patch $5CC7 $7A6AW $0003W #Keen 4
%patch $5C9B $6F6AW $0003W #Keen 5
%patch $5A9B $75A6W $0003W #Keen 6

Notice the locations are quite similar, when looking for matching patches we should test those closest to an existing patch first. This works within and across games.

We can also use an existing patch to get an idea where a related patch may be. For example the following patches list stuff Keen has when starting a new game in Keen 5:

Code: Select all

#Stuff Keen has at game start (Defaults)
%patch $5C8F $6F54W $0000W #Extra Keen at score (High word)
%patch $5C95 $6F52W $4E20W #Extra Keen at score (Low word)
%patch $5C9B $6F6AW $0003W #Lives (3)
%patch $5CA1 $6F56W $0005W #Ammo (5)

It's simple common sense that the patch for Keen's starting ammo will be near his starting lives and a simple look at the code is enough to confirm this and write the patch. Now let's look in more detail how we can use the structure of existing patches to make new ones.


STEP 8: COPYCAT PATCHES

Let's suppose you want to change the default difficulty of demo mode games. ( http://www.shikadi.net/keenwiki/Patch:Demo_mode ) There is have a patch for Keen 4 on the wiki, but not one for Keen 5, which you want:

Code: Select all

#Difficulty of demo mode -Keen 4
%patch $3EF6 $0002W #First game
%patch $5209 $0002W #Subsequent games

Looking for '$0002W' gets you hundreds of possible matches, that could take days to track down. but it's likely that the code around the patch is similar in the three Galaxy games. Opening a Keen 4 dump and going to the first patch we see the following code at $3EF2;

Code: Select all

$C7 $06 $70 $7A $05 $00 $C7 $06 $4A $47 $02 $00 $9A $A8 $08 $35 $1B
Searching for '$C7 $06 $4A $47 $02 $00 'gives us 4 results in the entire game; one of these matches the second patch at %5209, these must set the game difficulty in various spots! We can test this and create new patches for Keen 4, but that's not what we want. So we then pen up Keen 5's dump and look for that same data.

No matches. Rats! In hindsight this makes sense, we can't expect everything to be identical. So let's look for some other stuff nearby and see what we get. For various reasons stuff following $9As and $C7 $06s tends to change between games and even dump files. getting a feel for what does and doesn't change takes time and practice, but less then you'd think. From experience I expect '$05 $00 $C7 $06' and '$02 $00 $9A' not to change much between games, both involve numbers affecting the same thing across games for example.

Looking for the first one in Keen 4 gives us only TWO matches, both of which match the demo difficulty patches we have. And for Keen 5? Two matches! Right next to each match is a '$02 $00' that we need to change in our new patches. We thus make this patch and test it, and it works!:

Code: Select all

#Difficulty of demo mode -Keen 5
%patch $3EF0 $0002W #First game
%patch $5203 $0002W #Subsequent games

One final note for this part; a simple tool has been written to extract default patches from the games. GetPatch lets you take a patch location and extract the game's data at that location in patch form. This allows you to generate the (default) patch for a chunk of code in seconds without having to copy it out.

To run GetPatch simply drag the desired Keen data onto the program and type in your patch location (In hexadecimal, you don't need the '$' character.) The program will ask you for and 'extra skip', this is mostly irrelevant, it just makes the program read extra data when it comes across the Keen game's 'stop' signal. You can usually just press enter and get the patch written.

Patches are produced in a file called OUTPUT.TXT Some formatting errors may occur, the program is basic.
Last edited by Levellass on Sat Apr 16, 2016 5:09, edited 1 time in total.
What you really need, not what you think you ought to want.
User avatar
Nisaba
Janitress
Posts: 1597
Joined: Fri Jan 01, 2016 23:34
Location: The Outpost
Contact:

YAUS!

Post by Nisaba »

Oh thank you Levellass! Thank you so much!
what a sweet joy!!!

I wish I had this guide years ago, when I sparked interest in making a Keen mod myself. for some reason the lack of a gentle and detailed patch-tutorial impeded me of doing so.

and yes! this beginners tutorial should get a wiki entry. That's for sure! And if you wish, I'm unhesitant to give it some screenshots, work on the layout and proofread everything (for eg. $5C9B needs to be inserted as hex, by default dec is checked. The novice patcher might get confused by this. also please link to the developers homepage: http://www.chmaas.handshake.de/delphi/f ... m#download)
at least for me (being about to get a deeper understanding of patches instead of copy and paste everything God-given) this article is awaited eagerly! Thanx and thanx again!
this tutorial is the cat's pyjamas!
troublesomekeen wrote:"It is no small act of kindness to work out a patch for me. A greater kindness is when Levellass teaches me how." Chapter 8, Verse 2
out now (link) : Image
User avatar
Levellass
S-Triazine
Posts: 5265
Joined: Tue Sep 23, 2008 6:40

Post by Levellass »

Let's continue. I am building a bunch of basic utilities to help train patchers, TutoriTools. At present it contains only one tool but the pack will be expanded as the tutorial is. It can be got here: https://dl.dropboxusercontent.com/u/394 ... iTools.zip


And we continue.


STEP 9: TEXT PATCHES

One of the simpler and more requested type of patch is the text patch, a patch that alters what text the game displays at certain points. These patches consist of two parts, the text itself and the text 'pointer'. Let's run through an example. Say we want to alter what appears when Keen tries to enter water in Keen 4 without the Wetsuit. By default this is 'I can't swim.' which can be easily seen in-game.

Finding the text is a simple enough matter; simply open the game dump in XVI32 and open the 'Search' menu and select 'Find'. There we can select the 'Text string' option and look for the text. (Be sure and use the right case and punctuation. To be more sure of success you might want to search for only a short part of the text, such as "I can't".) This gives us exactly one result at $30A3D.


XVI32's window is divided into two parts, a hex side on the left and a text side on the right. When we look at our result we can see the can't swim text in the executable as plain as day on the right side of the window, as well as all the other texts that surround it. From that we can make the following patch:

Code: Select all

#Text for can't swim message
%patch $30A3D  "I can't swim!" $00

The text in this patch is commonly referred to as a text 'string'. (Because it's one long line.) Note something important here; the text string ends with '$00'. This tells the game to stop reading text there, which is important, if we change the '$00' into '$20' (A space) for example the message becomes "I can't swim! Cool! I can breathe under water now!" This happens because the game keeps reading the text and accidentally reads TWO texts. In fact doing this will crash the game with a 'string exceeds width error'.

Another thing to note comes to light when we look at the next text string, about breathing under water. Properly patched it looks like this:

Code: Select all

#Text for wetsuit
%patch $30A4B  "Cool!  I can breathe" $0A
               "under water now!" $00

The '$0A' means 'Go to the next line down' and it stops all the text being on one long line. This is VERY important, if you have a line of text that is too long the game will crash. (With that 'string exceeds width' error mentioned above.) One of the hardest and most annoying things about text patching is knowing where to move down to the next line.

With a little thinking this reveals another limitation of text patches; it is easy to have a patch that is shorter than the old text; nothing needs to really be changed. But one that is longer will probably overwrite something important. For example, if we change the swim message to:

Code: Select all

#Text for can't swim message
%patch $30A3D  "I can't swim without a wetsuit!" $00

Everything seems fine when Keen tries to enter the water... but when he gets the wetsuit the following message displays: "ithout a wetsuit!". This is because that text string has been overwritten by your new message. What we need then is a way to 'move about' all the text strings. This can be done, it involves something called 'pointers'.


STEP 10: POINTERS

A pointer is exactly what it sounds like, it 'points' to a location in the game executable. There are two types, words and longs, but we'll only consider words at the moment. A word pointer is two bytes, like a normal word, except that they refer to a location instead of a value. One thing should be made clear now, this location will need to have another value added to it to give you the true location. Sometimes, such as in the Keen Vorticons games, this value is zero, but often it isn't.

The location you need to add for text patches is called the 'data segment location', we'll find out what this means later. It is different for each game, the following is a list for the 'default' versions of Keen games:

Code: Select all

Keen 1: $13050
Keen 2: $17780
Keen 3: $19820
Keen 4: $2EE70
Keen 5: $30340
Keen 6: $30D30
Keen D: $23A70

You can find this location yourself, it is 4 bytes less than where the text string 'Borland C++' is in the executable. (This text was added in automatically when the game was created to mark the data segment's start.)

So where does this leave us with our swimming text patch? Well if we know where the text is and the value added we can work out what the game's pointer will look like. In our example we open up Windows Calculator and enter the following sum: 30A3D - 2EE70. This gives us the value 1BCD. Looking in our game dump for this value we find one match at $F3A5, from that we can create the following patch:

Code: Select all

#Can't swim text read from
%patch $F3A5 $1BCDW

So what use is this to us? Well by changing this value we can change were the game looks for the can't swim message, adding 1 will move the text's location 1 and so on. This means that if we don't have enough space we can move the text somewhere more roomy. Alternatively we can make one small text string longer and move the start of the next string so it doesn't get overwritten. (This will shrink the next text string of course.)

So let's say we want that large can't swim message, we could jiggle it around with the wetsuit message, or we could just find something unimportant and overwrite it. Fortunately Keen, especially Keen Galaxy, has a large number of checks and error messages that shouldn't come up in regular gameplay. These can be changed or overwritten with little concern. The keen wiki page 'Game errors' ( http://www.shikadi.net/keenwiki/Patch:Game_errors ) contains an exhaustive list of game error messages complete with their text pointers and text locations.

Let's say we overwrite the 'MarkTileGraphics' errors. These appear when you mess up the tileset properties somehow, no released game should ever trigger them if properly tested. The first patch looks like this:

Code: Select all

%patch $168F9  $4099W #Text called from
%patch $32F09 "RF_MarkTileGraphics: Background anim of 0:" $00

There are six patches in total which allows quite a bit of text to be stuffed in. To move our can't swim patch we just take the MarkTile pointer, $4099W and replace $1BCDW with it. If we then launch the game we can see that Keen gives the error message when he tries to enter the water. We can now edit this error message and change it to whatever we want Keen to say:

Code: Select all

#Move can't swim message so it can be longer
%patch $F3A5  $4099W #Move message
%patch $32F09 "I'm too lazy to swim, maybe later." $00

But what about the error message? We might need it if we mess up while building the game or you might feel that if it ever *did* appear it should make sense. Well we can just swap it around with the swim message, and make the error smaller. It could be as short as 'E1' (Error 1) or 'Back anim 0', as long as it makes sense to you and\or any possible players:

Code: Select all

#Move error
%patch $168F9  $1BCDW #Move message
%patch $30A3D  "Error #314" $00

It is easily possible to compress the game's dozens of errors into just a few lines, freeing up massive amounts of 'text space'. It should also be noted that looking at what you have done in the game dump is a useful way of keeping track of how much space you have and whether anything has been overwritten.

Finally if this seems a little tricky there's a small tool that will scan the Keen games for any text you want and try to automatically generate a text patch plus text pointer for that text. This is 'LText' and it can be found in the TutoriTools folder. Simply type some text into 'LText'TXT' and run the executable. It will create an output folder giving you all possible patches for all possible Keen games that contain that text. It's not perfect, it will often miss text pointers that are hidden in tricky spots, but it can be used to drastically cut all the manual work out of finding new text patches.


This is the end of the tutorial at present. There's still a lot to cover, mostly involving understanding the way the game does things and using this to better build and modify patches. Next up we'll be looking at just why we have to treat text pointers in such an odd way, why do we have to add a value to them to get the location? What's the data segment? But that's for another day.
What you really need, not what you think you ought to want.
User avatar
Nisaba
Janitress
Posts: 1597
Joined: Fri Jan 01, 2016 23:34
Location: The Outpost
Contact:

Post by Nisaba »

Wow...

a bunch of basic utilities to help train patchers sounds sweet indeed!
But all of this will take me days to update the wiki over here:
Levellass' Keen Patching Tutorial.
anyhow, as your student I'm hanging on your lips.
troublesomekeen wrote:"One need only look upon the KeenWiki to know the extent of Levellass' help." Chapter 14, Verse 9
out now (link) : Image
User avatar
Levellass
S-Triazine
Posts: 5265
Joined: Tue Sep 23, 2008 6:40

Post by Levellass »

Please let go of my lips.

Anyway as a minor update a second utility has been added, GetPatch. This lets you take a patch location and extract the game's data at that location in patch form. This allows you to generate the (default) patch for a chunk of code in seconds without having to copy it out. Instructions are in a readme in the zip file.
What you really need, not what you think you ought to want.
User avatar
Nisaba
Janitress
Posts: 1597
Joined: Fri Jan 01, 2016 23:34
Location: The Outpost
Contact:

Post by Nisaba »

...
out now (link) : Image
User avatar
Levellass
S-Triazine
Posts: 5265
Joined: Tue Sep 23, 2008 6:40

Post by Levellass »

Aaaah I have a new job that is sapping my life!



STEP 11: SEGMENTS

Now we look at why we went to all that effort in the last section. First we must ask, 'What would be the best way to find text, or anything, given extremely limited processing power?' One might imagine we could simply deal with the text's actual location each time. However there's a problem; the executable is larger than 64Kb, meaning that addresses would ahve to be in DWords, something the game finds difficult to deal with. But there's another problem too, that of distance.

Every time an address is given the game must 'look up' the location. It is more difficult and time consuming to look up and go to a 'faraway' address than a nearby one. It would therefore be very advantageous for the game to be organized in some way to minimize the 'lookup times' and this is in fact the case.

The game executable is organized into a number of 'chunks' or 'segments', each specializing in a certain type of code. Due to the somewhat automated creation of these segments they can vary wildly in size and specialty. (For example each level name is its own segment.) Some segments contain sprite code, others drawing routines or the main game loop.

Each segment is (or attempts to be) organized such that code in a segment most commonly calls code in the same segment. This is why, for example, sprite behaviors are all clustered in one or two segments. In the Vorticons trilogy the game consists of but a few segments, one for the main game code and a few others for things like data and game text files.

For various reasons the rest of this section relates almost entirely to the Galaxy and Dreams games, the segment structure o Vorticons being far simpler and relating more to what will be discussed later.


STEP 12: SEGMENT CALLS

Whenever the game wishes to call a piece of code that is not in the same segment it uses a segment call, also known as a 'far call' (As it is capable of 'calling' the farthermost bits of code.) (Same segment calls involve something else, a 'near call'.) These calls have several interesting features. We will begin by examining one, in this case the one that tells the game how Keen should act while standing still:

Code: Select all

#Keen standing behavior -Keen 4
%patch $2F80C $0B800395RL

The specifics of how this patch was obtained do not matter here (and will be covered later.) For now we are simply interested in its format. The cal is a Dword, as expected, composed of two parts. The first word is the segment address, the second word is the address within that segment. This raises a problem, with only a word for the segment address how can the game call segments further than $FFFF? It does so by dividing the address by 16 ($10) In hex this has the effect of lopping off the last digit of the address. Our example here calls a segment located at $B800. This has the side effect that segments can only start at multiples of $10, but this is of little consequence.

Our example is thus calling code located at $B800 + $395 or $BB95. Opening the Keen 4 dump in XVI 32 and going to the address shows us the first byte is $55, which is nearly always the start of a piece of game code. At this point this copy of the dump, preferably produced some time ago, should be kept open for alter comparison.

This is in fact Keen's standing behavior. We can test this by replacing the specific call with a 'blank call' that calls nothing:

Code: Select all

#Keen standing behavior, blanked -Keen 4
%patch $2F80C $00000000L

In this case, running the game causes Keen to do nothing when standing still, he doesn't get bored or respond to arrow presses. But why does this new patch use 'L' while the original used 'RL'? Attempting the above patch with 'RL' causes the game to crash messily when Keen appears.


STEP 13: RELATIVE PATCHES

This is because segment calls *except* blank calls require a *relative* address. Delete the patch and produce a new dump of the Keen 4 executable. Open this in XVI 32 *while also keeping the older dump from earlier open.* Go to the patch address and compare the four bytes there in both versions. What do you notice?

If all went well and the dumps were from different days then while the first two bytes should be the same, the next two should differ. This doesn't seem to make sense, the same game run the same way produces two (slightly) different dumps.

What is happening is that these collections of bytes are giving the proper address in computer memory for the code... but the game itself is being loaded into a different location in memory each time. This means that everything in the game has an 'extra' value added to it. This could be added to the segment or inter-segment value (Or both.) but is by convention added to the segment value. The value is largely random and can change each time the game is started.It is impossible to write an ordinary patch that can guess the game's location and work, even if it *were* possible the patch would only work once!

Fortunately CKPatch has the RL functionality to automatically detect and add the game's memory offset to any existing patch. It is applied *only* to far calls.

Now we have seen a 'bare' far call, we can move on to see a 'complete' one.


STEP 14: FULL FAR CALLS

The patch above was an 'action patch', which will be discussed much later. It is just an address the game loads then runs. Most far calls in code are several bytes longer, such as follows:

Code: Select all

#Full far call
%patch $1234 $B8 $0004W  $50 $9A $187409F1RL     $83 $C4  $02

In this example a lot is happening. It plays sound 4 when called. A lot of this will be covered later. The first four bytes take the two-byte value '0004' and 'save' it for the called code to use. $9A tells the game 'the next four bytes are a far call' Finally '$83 $C4 $02' tells the game to 'unload' two bytes now the game is done with them.

The most basic calls will not load anything before being run, they are just five bytes, $9A and the address. Other calls will load (and dismiss) several values in several ways. But there are several important things to note here.

First of all simply scanning for $9A will identify where a far call is in most code. Secondly replacing this and the next four bytes with '$90' will cause the call to be deleted and the code not to be run. As an example this patch takes our above code and stops the playsound code being called, muting the sound in that situation:

Code: Select all

#Full far call -deleted
%patch $1234 $B8 $0004W  $50 $90 $90$90$90$90 $83 $C4  $02

Finally, the far call will have nearly an identical setup everywhere in the game if it calls the same code. Even though the call is different in each dump, all identical calls will be altered the same way by the same amount. If you know where one is you can look at that location in the dump and then look for other versions of that call, tracking down each and every time that code is called in the game. This is an immensely powerful thing to do.


STEP 15: FAR CALL SEARCHES

Starting from scratch we'll take a random sound patch from the Keen wiki, we could also use a patch from a mod or one we discovered ourselves:

Code: Select all

#Keen starts pogoing while walking sound -Keen 4
%patch $BF39 $02

The first thing we do is open up a dump of Keen 4 and got to the patch's location. There we find the same setup as our last example, the value 2 is loaded, code called then unloaded. We pay especial attention to the far call. Though yours will differ and example might be:

Code: Select all

$9A $F1 $09 $49 $1F

This is the version of the far call for sounds in this dump. Searching for this sequence of bytes gives us no less than 78 matches, all of them different calls to play a sound in the game.

Many things can be done with this, if we know the sound we want to alter we can search the matches until we find it. If we know what code we want to tweak (Such as the location of Keen's walking behavior) we can look for matches at or near that location for the sounds that code uses. Or, if we know nothing, we can simply try all of the 78 patches, changing the sounds they play and testing the game, allowing us to potentially label every single sound and situation in the game, providing endless clues as to the locations of other bits of code.


STEP 16: NOTES

There are a few other things to note when dealing with segments. The first is that you *can* 'make up' segment addresses when patching and the game will work fine, so long as the address points to the right location. However doing so can cause some minor problems since you are in effect fragmenting the game and probably slowing its performance. If at all possible 'default' segment values should be used. These can be guessed from other patches or the Keen wiki has an incomplete list.

Another thing is that only 'action patch' calls can be blanked with the $00000000L value.

As a final wrap-up we shall consider the 'odd' segment, the data segment. The data segment is special since it doesn't usually have to be called; instead usually an address within the segment is given, and usually not for code, but for data like text. This topic will in fact make up several sections on its own, after we have learned about jumps and variables. Suffice to say it is an incredibly powerful resource to master.

Finally, converting between a location and call can be tricky. To help the TutoriTools package contains a utility called 'RL' that will take a far call patch and convert it into a code location. Simply paste the patch in 'INPUT.TXT' and run RL, the address will be printed in 'OUTPUT.TXT'

Next up we'll look at near calls and jumps.
What you really need, not what you think you ought to want.
User avatar
Nisaba
Janitress
Posts: 1597
Joined: Fri Jan 01, 2016 23:34
Location: The Outpost
Contact:

Post by Nisaba »

out now (link) : Image
User avatar
Levellass
S-Triazine
Posts: 5265
Joined: Tue Sep 23, 2008 6:40

Post by Levellass »

And a new installment.



STEP 17: NEAR CALLS AND JUMPS

So far we have seen how a chunk of code may be run from somewhere else in the game. Specifically we've seen how a 'Far Call' is used. However there are other ways for the game to run or skip bits of code and we will examine them now. The first to look at is the 'Near Call'; in practice this does exactly the same thing as the Far Calls we've examined but there are certain conditions for its use. Consider this example from Keen 1:

Code: Select all

#Searching Yorps call tiles, gravity
%patch $1A24 $E8 $1203W  $E8 $1243W  $5D $C3

There are two Near Calls in this patch, each following the format of $E8 $xxxxW. In this case they call two chunks of code, sprite-tile interaction and game gravity. These code chunks are located at $2C2A and $2C6D respectively. It can be seen that unlike the Far Call whose destination can be calculated just by looking at the code, the Near Call's destination takes the current code location and adds something to it to get the destination.

This has several effects. The first is that the Near Call will be different if it is placed in different locations. Unlike the Far Call its code cannot simply be cut-and-pasted to different locations. Instead moving it requires 'adjusting' the call so it continues to point to the right location. Take this example, which removes the Searching Yorp's tile call:

Code: Select all

#Searching Yorps call gravity
%patch $1A24 $E8 $1246W  $5D $C3

Here we have deleted 3 byes of code, the first call. (Which we can do for a reason that will be explained much later.) Doing this moves the second call 3 bytes back, meaning that we need to adjust it by 3 so it will still call the right code.

There are several other unique properties to Near Calls. A given Near Call will always appear the same in memory dumps, it doesn't change each time like Far Calls do. A Near Call can be 'blanked' by decreasing its value by 1 (With rare exceptions. This works because the call goes from pointing to the first byte of one chunk of code to the last byte of the previous chunk.) or by replacing it with the string $90 $90 $90.

Near Calls are used because they are quicker to perform than Far Calls. In general they are used within a segment while Far Calls are used between segments. In Keen Vorticons, where the game code is almost entirely one segment, nearly all calls are Near Calls. Conversely Keen Galaxy and Dreams have very few, almost all in the form $0E $E8 $xxxxW.


STEP 18: NEGATIVE CALLS

At this point you may be wondering how a Near Call would cal a chunk of code that occurs before it in the executable; currently it seems as if it can only jump 'forward'. This is accomplished through the use of 'negative jumps' in an interesting way. In short any word value that is greater than $8000 can also be a negative number, obtained by subtracting $10000 (65536) from it.

A value that can be positive OR negative is known as 'signed' (Since it can have a '-' sign in front of it.) A value that is always positive is known as 'unsigned'. It is important to know what is being used since giving the game a small negative number when it expects a large positive one (or vice versa) is bound to cause problems.

Under this system the value $ABCD could either be the positive value 43981 or the negative value 43981 - 65536 = -21555. Exactly which is used in any given situation can be confusing. For example Near Calls will treat this as negative by default, but positive if it can't jump back far enough. (So $E8 $ABCDW will jump back to $2222W if located at $CDEF but will jump forward to $11435 if located at $6868, since $6868 - $ABCD is less than zero and the program can't jump back to before where its code starts.)

This means that, by and large, Near Calls have a range of $8000 on either side unless close to the start of the code. There is no way to 'force' a Near Call to read 'negative' values the way to want.

Negative numbers can be calculated directly. Consider trying to jump from $869D to $8553; to calculate the jump required simply treat it as follows: $18553 - $869D = $FEB6.

Windows calculator has a shortcut for turning a positive number into a negative one (And vice versa.) Opening Calculator and setting it to mode 3, then hex one can enter any number they wish then click the 'not' button to turn it negative. This is very helpful.

The same principles apply to jumps, which will be discussed next. In the TutoriTools folder there is a program called CALLSCAN that will search a dump for Near Calls if the destination is known. To use it simply drag-and-drop a dump onto the program and enter the destination. It will produce a list of Near Calls as well as a file full of patches that overwrite them, for testing.


STEP 19: JUMP SHORT, JUMP NEAR

The Calls run a segment of code and then return back to where they started. Jumps however do not return, they simply 'jump over' a piece of code. Jumps cannot be used to run separate chunks of code, instead they must be used within a chunk to allow the game to choose whether or not to do different things. Let's look at the two most basic, jumping Short and Near:

Code: Select all

#Jump Short over a Jump Near
%patch $ABCD $EB $03 $E9 $0123W

In this patch the first two bytes are the 'Jump Short', this tells the game to simply skip the next three ($03) bytes of code. In this case the Jump Near. The Jump Near is the next three bytes of code and tells the game to skip $0123 bytes of code. It is very similar to a Near Call, except again, it will not return to its starting position if used.

Note that the Jump Short has a range of only $80 (128) on either side of its location. Like Jump Near a value larger than $80 will be considered negative. Unlike Jump Near this is always the case.

Both of these jumps are 'mandatory'; the code will always be skipped. This has limited use and there are several other jumps that are 'conditional', that is, they will only skip code under certain conditions. The following jumps cover all possible circumstances. Note that they all share the same limited range. Their range can be increased by combining them with a Jump Near.

Code: Select all

 $72 $00      JB: Jump if below
 $73 $00      JAE: Jump if above or equal
 $74 $00      JE: Jump if equal
 $76 $00      JBE: Jump if below or equal
 $77 $00      JA: Jump if above

 $7C $00      JL: Jump if less
 $7D $00      JGE: Jump if greater or equal
 $7E $00      JLE: Jump if less or equal
 $7F $00      JG: Jump if greater
 $75 $00      JNE: Jump if not equal

The greater/less jumps are for signed integers (those that can be negative), while the above/below jumps are for unsigned integers (Positive only.) Again this is important; the value $FFFFW will be considered -1 and thus smaller than zero by a greater\less type jump but 65535 and thus greater than zero by an above\below type jump.

But what exactly are the jumps checking and how do they work? For this we must examine Jump Checks.


STEP 20: JUMP CHECKS

A Jump Check is a segment of code containing a jump. It takes one game variable (Explained in the next section.) and compares it to a fixed value, then jumps (or not) depending on the result. Shown below are the two most common Jump Checks:

Code: Select all

#What Keen needs to shoot -Keen 4
%patch $E569 $83 $3E $7A58W $00 $75 $0E

#Exit behavior check -Keen 1
%patch $44D2 $81 $3E $6F0CW  $3867W  $74 $03 $E9 $009BW

The first check is used in Keen 4 to check if Keen has any ammunition he can use when trying to shoot. The second is used in Keen 1 to see if the player's behavior is right for walking through the exit. (It also shows how a short jump can be combined with a Jump Near.)

In these examples the first byte tells the game whether the variable will be compared against a byte or a word. $83 indicates a byte, $81 a word. The next byte, $3E tells the game to compare two things. The next word (two bytes) is the variable to compare. This will be explained in more detail in the next section. After that comes the value to compare against, this is either a byte or word. Finally comes the jump and its length.

The first example can thus be read as follows: "Work with bytes. Compare Keen's ammo to zero. Jump over code if they are NOT EQUAL."

The second example can be read as follows: "Work with words. Compare Keen's behavior with $3867. Jump if EQUAL. (In this case the small jump is over a larger jump so the end result is Keen will skip skipping code if his behavior is $3867, or walking.)

Whenever the game makes a 'decision' a jump of some sort will be involved. However by itself this isn't very useful to us; how do we use jumps to make patches or find things to patch? Before we can do that we need to learn about another area of patching, game variables.
What you really need, not what you think you ought to want.
User avatar
Levellass
S-Triazine
Posts: 5265
Joined: Tue Sep 23, 2008 6:40

Post by Levellass »

Aaaand another installment!


STEP 21: GAME VARIABLE BASICS

Game variables are all the things the game uses to keep track of things. Specifically these are locations in the game's 'data segment', used for storing many things such as most of the game text. Each game variable uses two bytes of the data segment each and can be located anywhere in the data segment. It is possible for variables to overlap and overwrite each other or other things (such as text strings) in the data segment.

Each variable thus consists of two important parts; firstly is the actual location of the variable in memory, that stores the value and the pointer that identifies that specific variable by location. These two elements appear in almost all variable related patches.

You will notice that this is similar to the text patches we have learned about earlier, and indeed it's possible to put a game variable inside a text string and change a piece of text as you play. The concepts are very similar.


STEP 22: OVERFLOW AND UNDERFLOW

Since there are no limits that tell the game when to stop increasing or decreasing a variable, eventually a variable can reach the largest\smallest possible value it can and the game will keep going. When this happens a 'flip' can occur. Keen games are often set up to avoid this.

As an example Keen's ammo counter decreases by 1 each time he shoots. When it reaches zero the game makes sure he cannot shoot anymore. If it did not do this Keen's next shot would give him -1 shots, which the game actually treats in that case as 65'535 shots. While the game prevents this, the reverse case Keen can acquire so much ammunition that he ends up with no ammo at all is possible.

This relates to the idea of negative and positive numbers discussed earlier.


STEP 23: CHANGING VARIABLES

A six byte string is required to set a variable. This involves overwriting the previous value with a new one. This is often done when something starts or stops, such as starting a new game. The first two bytes indicate setting, the next two are the variable's pointer and the last two the value it is set to.

In this example the variable as $C28B in the data segment is set to 4. No matter what the value was before this it will be 4 after. Looking both on the wiki and at patches we've covered so far we can see that such setting patches are common.

Code: Select all

#Set variable $C28B to 4
%patch $1234 $C7 $06 $C28BW  $0004W

Two special commands will increase or decrease a variable by exactly one. These are both four bytes in length. The first two bytes indicate whether to increase or decrease the variable while the last two are the variable involved. (Since the increase\decrease is regular no value is needed.)

This is often done when modifying a variable's value in a regular, repeated manner, such as a counter ticking down to zero. (Note that variables will not 'stop' at any value, they can always be decreased or increased.) Keen's ammo counter is an example of this, decreasing by 1 every time he shoots.

Code: Select all

#Decrease variable $C28B by 1
%patch $1234 $FF $06 $C28BW

#Increase variable $C28B by 1
%patch $1234 $FF $0E $C28BW

A five or six byte string will increase a variable by a specific amount. There are two versions of this command; the first is five bytes long and adds a 1-byte value to the variable, the second is six bytes long and adds a two-byte value. The difference lies in the first byte of the sequence; as we've seen previously $83 is 1 byte and $81 is two bytes (a word). These two versions can be seen in the example, both doing the exact same thing.

Code: Select all

#Increase variable $C28B by 5
%patch $1234 $83 $06 $C28BW  $05

#Increase variable $C28B by 5
%patch $1234 $81 $06 $C28BW  $0005W

Once again if the value added is greater than $80 (1 byte) or $8000W (two bytes) then the value will 'flip' and become negative. (For example $FF\$FFFFW is -1.) This allows for decreasing a variable as well as increasing it. This puts a (large) limit on how much a variable can be increased in at one time.


STEP 24: VARIABLES AND JUMPS

Now we can see how variables work with jumps. This greatly expands our patching abilities. If we know (or discover) what a given variable does we can search for it in the game and find out where else it's referred to.

As an example let's look at a patch from the Keen wiki that tells us how many lives Keen gets when a new game is started.

Code: Select all

#New game lives patch
%patch $5CC7 $7A6AW $0003W #Lives (3)

This patch tells us two things, firstly that Keen gets three lives and that Keen's lives variable is at address $7A6AW. Opening our game dump we can search for all references to this value. We find there are no less than 16 references to this variable. The first is our New Game patch. The second is at $667E and involves the following code:

Code: Select all

#Second life variable reference
%patch $667E $FF $0E $7A6AW
From what we know of variables we can tell that this is decreasing Keen's lives variable by 1 It seems likely that this is run when Keen dies, taking a life from him. And indeed if we replace this code with $90s we find Keen doesn't lose a life when he dies.

Code: Select all

#Keen doesn't lose a life on dying
%patch $667E $90 $90 $90 $90

Repeating this process we can find where Keen gets 1UPs, what controls a Game Over and more. All from just one variable. We can even use these patches to find nearby variables and 'decode' them giving us even more information and patching ability. It is no understatement to say that jumps and variables are one of the cores of patching.


STEP 25: CURRENT VARIABLE

This is all well and good, we have variables and we can see them being altered and set, but it's not long before we start to notice other values that don't seem to relate to game variables at all Window sizes for example. And sometimes odd things happen to variables. This relates to the 'current' or 'topmost' variable and the 'stack'.

The current variable is the one (and only one) value the game is currently working with. Before the game can use (as opposed to compare or change) a value it must be set as the current variable.

A three byte command will change the current top variable to a specific two-byte value. This will have no effect unless combined with other commands. A special case is setting to zero which is a two byte command. (Though the three byte command will also work.)

Code: Select all

#Set current variable to 8
%patch $1234 $B8 $0008W

#Set current variable to 0
%patch $1234 $B8 $0000W

#Set current variable to 0 - usual version
%patch $1234 $33 $C0

There are two three-byte commands that will increase or decrease the current variable by a given amount. (Interestingly it is possible to increase\decrease by a negative number as well, which is in fact done. This can make some patches look odd.) The first byte determines increase or decrease while the next two bytes (word) are the amount.

Code: Select all

#Increase current variable by 8
%patch $1234 $05 $0008W

#Decrease current variable by 8
%patch $1234 $2D $0008W

It is also possible to copy a game variable to the top variable or to write the top variable to a game variable. This is needed to store variables or make use of game variables without altering them. While reading has little effect unless paired with other commands writing will change the value of a game variable.

By combining these commands it is possible to copy the value from one game variable to another or even multiple variables.

Code: Select all

#Load variable $C28B as current variable
%patch $1234 $A1 $C28BW

#Set variable $C28B to current variable's value
%patch $1234 $A3 $C28BW

#Copy variable $C28B to current variable then copy it to $CDBCW, $CDBEW and $D8F0W
%patch $1234 $A1 $C28BW  $A3 $CDBCW  $A3 $CDBEW  $A3 $D8F0W

STEP 26: THE STACK

Now things get interesting. For the game usually needs to have more than just the current variable 'nearby' when running code. It needs a small 'stack' of values it can get stuff from and put stuff on.

The 'stack' is a collection of values 'stacked' one on top of the other in memory. The game uses these values and the location of a given value in the stack is important. The stack is not the same as the game variables and is located in a different area of memory.

Only the 'topmost' value in the stack can be manipulated; if 'lower' values are needed then the 'higher' values must be removed from the stack. If those variables will be needed later they will have to be stored as game variables and loaded back onto the stack as needed. This makes manipulating the stack complex.

The stack can be made 'taller' by copying the current variable and adding it to the stack. This is a single byte command, $50. It is usually combined with the 'set current variable' to in effect set the topmost stack variable. Repeating the push command will simply push the current variable onto the stack multiple times. (Thus $B8 $0008W $50 $B8 $0008W $50 can be shortened to $B8 $0008W $50 $50.)

Code: Select all

#Push the value 8 onto the stack
%patch $1234 $B8 $0008W  $50

#Push the value 0 onto the stack
%patch $1234 $33 $C0 $50

#Push the value 8 onto the stack twice
%patch $1234 $B8 $0008W $50 $50

Much more rarely a game variable can be copied to the stack by first changing the current variable.

Code: Select all

#Push the value at $C28B onto the stack
%patch $1234 $A1 $C28BW $50

The stack is extremely limited in size and as such as soon as a value is used it is wise to pull it off the stack. This in effect deletes the value making the stack 'shorter.' There are multiple ways to do this. The command $44 removes ''one'' byte (Half a variable!) from the stack. (Meaning it must always appear as $44 $44 in Keen.) The command $83 $C4 $xx removes x bytes from the stack up to 128 bytes. There is also the never used command $81 $C4 $xxxxW which can remove up to 32'000 bytes from the stack, but this is impractical. (Note once again the use of $81 and $83.)

Code: Select all

#Remove 2 variables from the stack 1
%patch $1234 $44 $44 $44 $44

#Remove 2 variables from the stack 2
%patch $1234 $83 $C4 $04

In total the most commonly seen arrangement in Keen is for several variables to be set, pushed onto the stack and code run followed by the variables being deleted from the stack. In the example given here the code starting at $9A takes seven variables. The first two are $0001W and the last $1424W. (The other four are loaded in $57 $56 $50 $1E which is outside our scope for the time being.)

Code: Select all

#Typical code arrangement
%patch $1234 $B8 $0001W $50 $50 $57 $56 $50 $1E $B8 $1424W  $50 $9A $1D290F28RL  $83 $C4 $0E

In our next, brief installment we'll look at putting this knowledge to use by building our own custom bit of code incorporating the things we've learned here.
Last edited by Levellass on Tue Nov 08, 2016 11:34, edited 1 time in total.
What you really need, not what you think you ought to want.
User avatar
Nisaba
Janitress
Posts: 1597
Joined: Fri Jan 01, 2016 23:34
Location: The Outpost
Contact:

Post by Nisaba »

superb
out now (link) : Image
User avatar
Levellass
S-Triazine
Posts: 5265
Joined: Tue Sep 23, 2008 6:40

Post by Levellass »

STEP 27: PUTTING IT ALL TOGETHER

Now we should be able to manipulate the very values the game uses themselves, as well as understand a lot of what the game does. As such we will now create a novel patch from scratch. This patch will make Keen gain the Wetsuit and play a sound if he has a red gem while mooning.

The first step is to go to the Keen Wiki and see f any such patch exists. We find it does not. Next we consider possible ways to make the patch. Evidently we want to make some custom code and run that when Keen moons. On looking over the relevant page we see a section titled 'sprite behavior' that has patches controlling what code Mooning Keen runs. It warns us that Keen uses this code in other situations too, so we cannot simply replace it.

As such we'll need to find some 'spare' space in the game executable we can put our new code. Following the 'sprite behavior' link we find that there are already some custom sprite behavior code patches in existence. We can copy the format of one of these for our patch. The first patch in the section is for a behavior that kills Keen:

Code: Select all

#Custom behavior: Kill Keen = $037D0526RL
%patch $3CE5 $90 $90
%patch $3CF6 $55 $8B $EC $56 $57 $8B $76 $06 $8B $7E $08 
             $9A $0B8013E9RL     $5F $5E $5D $CB

By combining this with the call patch we find on the Keen Mooning page we get the following path that, when tested, causes Keen to die when he moons:

Code: Select all

#Custom behavior: Kill Keen = $037D0526RL
%patch $3CE5 $90 $90
%patch $3CF6 $55 $8B $EC $56 $57 $8B $76 $06 $8B $7E $08 
             $9A $0B8013E9RL     $5F $5E $5D $CB

#Use new behavior mid-mooning
%patch $2F91A $037D0526RL

We can double check the call; $037D * 10 = $37D0, + $0526 = $3CF6. The next step is to replace the custom code from the original patch with our own. But how do we do that? The simplest way might be to replace '$9A $0B8013E9RL'; that is a call to some other code and since we see nothing relating to Keen dying in the patch we must assume that is what calls the Keen dying code. But we can take a more general approach to writing code blocks.


STEP 28: CODE BLOCKS

Each block of code in the game must start and end in a certain way. If code is a sentence then these starts and stops are capital letters and full stops. The most important byte is the 'stop' byte, $CB ($C3 in Keen Vorticons.) Replacing a code block with just this byte will completely eliminate it. If we work this into our patch we find that while in mid-moon Keen can do nothing, not even move.

Code: Select all

#Custom behavior: Absolutely nothing = $037D0526RL
%patch $3CE5 $90 $90
%patch $3CF6 $CB

#Use new behavior mid-mooning
%patch $2F91A $037D0526RL

When writing blocks of code there are two basic 'setups' we can use to contain custom code strings. These are far from the full array of possible setups, which can be very interesting indeed, but they are a useful rough guide.

Here the first line of the setup is the start, appearing before custom code strings, while the second is the finish, appearing at the end. The first basic setup is for general code, while the second is usually used when two different sprites are involved. It will be noted the the original patch we used uses a more complex setup then it requires and in fact the simpler setup can be used with its 'kill Keen' code.

Code: Select all

#Code setup 1
%patch $3CF6 $55 $8B $EC
             $5D $CB

#Code setup 2
%patch $3CF6 $55 $8B $EC $56 $57 $8B $76 $06 $8B $7E $08 
             $5F $5E $5D $CB

Now we need to find the variables we want to alter, as well as the 'play sound' code. All of these can be easily tacked down by browsing the Keen Wiki, but here we'll work from scratch. First we can track down the Wetsuit and Red Gem variables by looking for the Items Cheat, which gives both of them. To do this we simply have to search for the 'Free items!' text, either manually or with a program.

Doing so reveals that the text is located at $2F391. This value less the data segment start of $2EE70 is $521 and looking for the string '$21 $05' gives us one match at $7537. We can test this by altering the text call and we do indeed see the F10-I cheat is affected.

Next we open the game dump and go to this location, we can expect it to have the 'give stuff' code nearby, before or after. Indeed we find the following code around this area, bounded before and after by '$CB' he 'stop' byte. This is the entire F10-I window code:

Code: Select all

#Free items mode window code
%patch $751A $83 $3E $C675W  $00 $74 $60 $9A $1D060999RL     $B8 $0003W  $50
             $B8 $000CW  $50 $9A $19311070RL     $83 $C4 $04 $B8 $0521W  $50
             $9A $19310E1FRL     $83 $C4 $02 $33 $F6 $EB $0B $8B $DE $D1 $E3
             $C7 $87 $7A60W  $0063W  $46 $83 $FE $04 $7C $F0 $C7 $06 $7A58W
             $0063W  $C7 $06 $7A5CW  $0001W  $9A $1D060A9BRL     $9A $14600EDFRL
                     $B8 $0BB8W  $50 $90 $0E $E8 $154DW  $83 $C4 $02 $B8 $0001W
                 $5F $5E $8B $E5 $5D $CB

We can see that there are some variable checks first, the keys needed to trigger the cheat, then two values that draw a window, then the text. After this we see a number of variables being set to various values. By changing the value they're set to, one by one, we can identify $7A5CW as the Wetsuit and $7A60W as the Gems. (All four; further investigation reveals $7A60W is in fact the Red Gem variable alone, so the four Gems must be being set together, possibly using the $04 following the variable.)

Finally we need to look for the sound code, which we've done before. In this case we know Keen makes a sound when he dies, we also have the 'Keen dies' call in our original patch. From that we can calculate Keen's dying code is located at $CBE9. From that we can extract the following, rather large code block:

Code: Select all

#Kill Keen code
%patch $CBE9  $55 $8B $EC $83 $3E $C5D1W  $00 $74 $03 $E9 $00B1W  $83 $3E $C629W 
                  $00 $74 $03 $E9 $00A7W  $8B $1E $D6 $A7 $81 $7F $1C $0CD4W
              $75 $03 $E9 $0099W  $C7 $06 $CAB5W  $0000W  $C7 $06 $C5D1W  $001EW
                  $C7 $06 $A7DAW  $0001W  $C7 $47 $06 $0000W  $C7 $47 $20 $0003W 
                  $83 $3E $ED $A7 $11 $75 $30 $9A $1D02002ARL     $3D $0080W
              $7D $12 $B8 $0D2EW  $50 $FF $36 $D6 $A7 $9A $09DC120ARL     $83
              $C4 $04 $EB $40 $B8 $0D4CW  $50 $FF $36 $D6 $A7 $9A $09DC120ARL 
                  $83 $C4 $04 $EB $2E $EB $2C $9A $1D02002ARL     $3D $0080W    
              $7D $12 $B8 $0CF2W  $50 $FF $36 $D6 $A7 $9A $09DC120ARL     $83
              $C4 $04 $EB $10 $B8 $0D10W  $50 $FF $36 $D6 $A7 $9A $09DC120ARL
                  $83 $C4 $04 $B8 $0017W  $50 $9A $187409F1RL    $83 $C4 $02 
              $8B $1E $D6 $A7 $C7 $47 $18 $FFD8W  $C7 $47 $16 $0010W  $5D $CB

Knowing we're looking for a Far Call narrows down he numbers that could be the sound to a handful. Knowing that there are only a few sounds limits it exclusively to the code '$B8 $0017W $50 $9A $187409F1RL $83 $C4 $02' which we can test by patching, successfully.

From all of this we can build up our custom code block. Firstly it will use the basic setup:

Code: Select all

#Custom behavior: Absolutely nothing = $037D0526RL
%patch $3CE5 $90 $90
%patch $3CF6 $55 $8B $EC $5D $CB

Next, the first thing we will need to do is to check if Keen has a Red Gem, if he doesn't we will skip our new code. There are a lot of options we have for jumps here, skipping if zero gems, skipping if less than one gem, skipping if less than or equal to zero gems...In these cases it is best to be precise, if Keen has ONE Red Gem and one Red Gem only, will the code run. This is '$01 $75'. Since we don't know how big the jump will be we will leave its size as $xx for now.We're also working with bytes ($83) since we only need to check small numbers. (1 or not 1)

Code: Select all

#Custom behavior: Absolutely nothing = $037D0526RL
%patch $3CE5 $90 $90
%patch $3CF6 $55 $8B $EC $83 $3E $7A60W $01 $75 $xx $5D $CB

Next we'll need the code for sound, which we have, and setting the Wetsuit variable to 1. This would be '$C7 $06 $7A5CW $0001W' We now place these after the jump check and count how long the combined code is. The sound code is 12 bytes and the setting code 6 bytes for a total of 18 or $12 bytes. We thus fill in the jump size and get our final patch:

Code: Select all

#Custom behavior: Absolutely nothing = $037D0526RL
%patch $3CE5 $90 $90
%patch $3CF6 $55 $8B $EC $83 $3E $7A60W  $01 $75 $12 $C7 $06 $7A5CW $0001W
             $B8 $0017W  $50 $9A $187409F1RL     $83 $C4 $02 $5D $CB

#Use new behavior mid-mooning
%patch $2F91A $037D0526RL

The patch can be tested and works fine. Some adjustment is still needed, notably the sound being played will need to be altered to be more suitable to the patcher's tastes. We also notice the sound plays continuously rather than just once, which suggests the code is being run over and over, not just once. This is in fact the case due to how the Keen Mooning action works. There are several ways around this; we could alter he Keen mooning action so it only uses the code once. This involves the 'action type' which is not something we have covered. The patch required is this:

Code: Select all

#Keen mooning uses code once
%patch $2F90E $0000W

Ho weer it may be better to add another check in our code to see if Keen has the Wetsuit; if so the code can be skipped. This will ensure that if Keen gets the Wetsuit and tries to moon again (Which he can.) then nothing will happen. This simply involves inserting another jump check into the patch, either before or after the first jump. Here I add it after. Notice that now the first jump has had its length increased by (Notice also the second jump is as wide as the first was, we didn't need to recalculate its length.)

The patch code has also been slightly rearranged to look nicer, but nice looking patches aren't a must. Finally note that the second jump is the opposite of the first; instead of skipping code if something isn't 1, it skips if something isn't 0. A side effect of these jumps being so specific is that the item cheat (Which sets gems to 99.) won't let Keen trigger this since he'll have more than one red gem.

Code: Select all

#Custom behavior: Absolutely nothing = $037D0526RL
%patch $3CE5 $90 $90
%patch $3CF6 $55 $8B $EC $83 $3E $7A60W  $01 $75 $19 $83 $3E $7A5CW  $00 $75
             $12 $C7 $06 $7A5CW $0001W $B8 $0017W  $50 $9A $187409F1RL     
             $83 $C4 $02 $5D $CB

#Use new behavior mid-mooning
%patch $2F91A $037D0526RL
What you really need, not what you think you ought to want.
User avatar
Nisaba
Janitress
Posts: 1597
Joined: Fri Jan 01, 2016 23:34
Location: The Outpost
Contact:

Post by Nisaba »

  • excellent!
for an updated article on the Keen Wiki head over to: www.shikadi.net/keenwiki/Patching Tutorial
out now (link) : Image
User avatar
Levellass
S-Triazine
Posts: 5265
Joined: Tue Sep 23, 2008 6:40

Re: Levellass's Patching Tutorial

Post by Levellass »

STEP 29: SPRITE ACTIONS

The following sections relate only to Keen Galaxy (and Dreams) Keen Vorticons has a different, more complicated, way of dealing with sprites, entirely code-block related. This will be covered after the more elegant Galaxy method.

First let us try and patch Keen's walking animations. These are eight different values; four for walking left and four for walking right. If we search for these values we find the following results for Keen 4:

Code: Select all

#Keen walking animations
%patch $2FF04 $008BW $0083W
%patch $2FF22 $008CW $0084W
%patch $2FF40 $008DW $0085W
%patch $2FF5E $008EW $0086W

Immediately we notice these are in the data segment somewhere. They are also paired, the first frame walking left is immediately followed by the first frame walking right. Each pair however is $1E or 30 bytes apart. This looks to be some sort of list or structure, but not one made up entirely of animations. Since this is the data segment we can look for references to the animations. When we do so we get the following results:

Code: Select all

#Walking references -main code
%patch $BF7E  $1094W
%patch $BFA0  $10D0W
%patch $BFC3  $10B2W
%patch $BFCA  $10EEW

#Walking references - data segment
%patch $2FF20 $10B2W
%patch $2FF3E $10D0W
%patch $2FF5C $10EEW
%patch $2FF7A $1094W

There appear to be four references to the animations in the main code, plus four in the data segment. In fact the four in the data segment are right next to the animations we found first! Specifically they are $1C or 28 bytes ahead of the animation pair. The first animation pair has a reference to the second animation pair's location, the second the third pair's and so on, with the fourth pair having a reference to the first.

This suggests that what we have in the data segment is some sort of cycle, 1->2->3->4->1... that is entered from the main code and looped over and over as Keen walks. From this we can assume that each animation in the game has one of these 30-byte structures to go with it. Extracting patch data starting at the first animation pair we get the following:

Code: Select all

#First walking animation data
%patch $2FF04 $8B $00 $83 $00 $04 $00 $01 $00 $01 $00 $06 $00 $18 $00 $00 $00
              $2C $06 $80 $0B $A9 $14 $80 $0B $5F $1B $80 $0B $B2 $10

Now we know that the first and last values are words, and that the entire data string could be displayed as 16 two-byte words. Doing this makes the data more sensible, a lot of repeated $00 bytes become part of low-value words. However on the second line the first 12 bytes of data are a bit strange; one word, ($0B80W here.) appears three times, each time after another word. Its value also changes between the raw game data and memory dumps. This suggests that what we have here are three longs, 4-byte pointers to code in the game. Given that we can organize the four walking actions as follows:

Code: Select all

#First walking frame data - organized
%patch $2FF04 $008BW $0083W $0004W $0001W $0001W $0006W $0018W $0000W
              $0B80062CRL   $0B8014A9RL   $0B801B5FRL   $10B2W
%patch $2FF22 $008CW $0084W $0004W $0001W $0001W $0006W $0018W $0000W
              $0B80062CRL   $0B8014A9RL   $0B801B5FRL   $10D0W
%patch $2FF40 $008DW $0085W $0004W $0001W $0001W $0006W $0018W $0000W
              $0B80062CRL   $0B8014A9RL   $0B801B5FRL   $10EEW
%patch $2FF5E $008EW $0086W $0004W $0001W $0001W $0006W $0018W $0000W
              $0B80062CRL   $0B8014A9RL   $0B801B5FRL   $1094W

Each data structure, from here out called a sprite 'action' thus consists of 12 values each controlling something different about the sprite. We can see exactly how powerful these are by copy-pasting a walk action onto the Poison Slug's sliming action, finding the Poison Slug's action in the same way we found Keen's:

Code: Select all

#Poison Slug sliming action replaced with Keen walking action
%patch $30EBE $008EW $0086W $0004W $0001W $0001W $0006W $0018W $0000W
              $0B80062CRL   $0B8014A9RL   $0B801B5FRL   $1094W

This patch has a remarkable effect; Slugs randomly turn into an exact copy of Keen, one that follows the players instructions and seems to be very nearly identical to the player themselves. The only difference seems to be that these copies of Keen don't die when they touch enemies or deadly tiles and can't get point items. This suggest that nearly everything about a sprite is controlled by these data structures. In the following sections we will explore each part of them and what they do, starting with the simplest.


STEP 30: ACTION REFERENCES

The first value to examine is bytes 29 and 30, the last value in the action. This is a reference to the next action the sprite will perform. We see this is what gives Keen a four frame walking loop. Manipulating these is quite simple; we just have to replace the default values with any other valid action reference. In this example Keen's walking frames are reduced to just two, this is done by taking the last value of the loop (That sends Keen back to the first action.) and replacing the second reference with it:

Code: Select all

#Keen's walking loop is two actions long:
%patch $2FF20 $10B2W
%patch $2FF3E $1094W

In fact the first line of the patch is not needed, since it is not changed. It now becomes quite trivial to alter the game in significant ways. As an example let us consider a patch that stops Keen from being bored. The first step is to identify the animations of Keen's bored animations; for simplicity we'll ignore Keen's first bored animation which can get confused with his 'looking up' animations. The relevant animations for the first action of Keen's second and third bored sequences are 148 and 150. Since these are the same whether Keen faces left or right we just search for two identical words. (In this case $0094W $0094W and $0096W $0096W.) This gives us the following results:

Code: Select all

#Keen shrug-blinks (Bored 2)
%patch $2F838 $0094W $0094W

#Keen start reading book (Bored 3)
%patch $2F946 $0096W $0096W

From this we can tell what references Keen's bored sequences use, starting with the first one and adding $1E to get all the rest. We can even work backwards and get the first bored action we had trouble with before, we simply assume the first bored sequence is right before the other two:

Code: Select all

#Keen's bored actions
$09AAW #Keen looks up (Bored-1)
$09C8W #Keen shrugs (Bored-2)
$09C8W #Keen shrugs (Bored-2)
$09E6W #Keen shrugs 1
$0A04W #Keen shrugs 2
$0A22W #Keen shrugs 3
$0A40W #Keen shrugs 4
$0A5EW #Keen shrugs 5
$0AD6W #Keen starts reading book 1 (Bored-3)
$0AF4W #Keen starts reading book 2
$0B12W #Keen starts reading book 3
$0B30W #Keen starts reading book 4
$0B4EW #Keen reads book 1
$0B6CW #Keen reads book 2
$0B8AW #Keen reads book 3
$0BA8W #Keen stops reading book 1
$0BC6W #Keen stops reading book 2
$0BE4W #Keen stops reading book 3

Finally we can search for the first steps in each bored sequence, if we change these values to Keen's 'standing' reference then Keen won't ever get bored. As it happens our searches give us exactly one result for each bored sequence, all in the same general area of code. (Which should also give us a head start when it comes to finding other patches relating to Keen being bored, such as the time taken.) Here the default values are listed first, followed by the patch that alters them to remove Keen being bored:

Code: Select all

#Keen goes from standing to bored
%patch $BC06  $09AAW #Bored-1 start
%patch $BC3A  $09C8W #Bored-2 start
%patch $BC4F  $0AD6W #Bored-3 start

#Keen doesn't get bored anymore
%patch $BC06  $098CW #Bored-1 start
%patch $BC3A  $098CW #Bored-2 start
%patch $BC4F  $098CW #Bored-3 start

While it's possible to search for every action reference the Keen Wiki has a page listing them all already, which greatly simplifies things. This page is http://www.shikadi.net/keenwiki/Patch:Sprite_actions Using that almost any sprite action can be found an analyzed so that a patcher may understand how it works.


STEP 31: ANIMATIONS AND CACHES

Next let us consider the first four bytes of the actions, the animations for the sprite facing left and right. These are simple enough to patch, indeed you may wonder why we didn't start with them. Simply find the animation you want and change the value to whatever you want it to be. For example this patch replaces Keen's standing animation with that of him facing the player:

Code: Select all

#Keen standing faces player
%patch $2F7FC $0094W $0094W

There are of course issues, animations are different sizes and the wrong sized one can cause problems; if for example Keen uses his first dying animation for standing, he'll fall through floors and eventually out of the level because he can't stand properly. However another problem becomes apparent if we try and replace Keen's walking animations with those of the Mad Mushroom, an enemy. (Here we leave Keen's 4-frame walking loop unchanged even though we have only two replacement animations, just for simplicity):

Code: Select all

#Keen walking animations now Mad Mushroom
%patch $2FF04 $0145W $0147W
%patch $2FF22 $0146W $0148W
%patch $2FF40 $0145W $0147W
%patch $2FF5E $0146W $0148W

This works fine in levels such as Crystalus where Mad Mushrooms are, but when Keen tries to enter a level such as the Border Village where there are no Mushrooms, the game crashes with the error 'Tried to place an uncached sprite'. It appears that Mad Mushrooms do something to levels to allow their animations to be displayed.

This 'something' is caches. Due to the limited amount of memory that Keen has it cannot keep all possible graphics in memory at once. Instead each level loads only the resources it needs. For sprites this involves 'dicing up' the sprites into chunks, roughly one for each enemy (And a big one for Keen.) These chunks are given a start and end limit and are loaded into memory when a sprite spawns.

One can find the cache of a sprite by searching for its start and end limits, for the Mad Mushroom these are $0145W and $0148W respectively. Searching for these gives us 4 and 7 results respectively. Both of these values occur once in the Mushroom's sprite actions, where they are easily identified. For the other occurrences we simply replace them with a more limited value (Such as $0146W, which cuts animations off the start OR end of the cache.) and test whether Mad Mushrooms crash the game. As it turns out the very first occurrence of both is a cache limit, and that limit is in the same area as all other cache limits. This allows us to identify all the caches in the game, and this list is available on the Keen wiki as well at http://www.shikadi.net/keenwiki/Patch:Sprite_cache

However our problem remains; trying to increase Keen's cache to hold the Mad Mushroom makes it take up a massive amount of memory; modifying caches is fine when you want to 'steal' animations from one enemy and give it to another that follows it in graphics order, but it cannot allow large changes. If we want Keen to have the Mushroom animations we'll need to sneak a Mad Mushroom into any level he's in.

With this limitation recognized we are now aware of all the difficulties involved in patching animations.


STEP 32: ANIMATION SPEED

We have already identified the first and last bytes of each action; looking at Keen's walking actions we can hazard a guess at the other bytes. A few are either 1 or 0, suggesting some sort of binary attribute, on\off yes\no. The second row of each action obviously has 3 code references in it. But bytes 4\5, 10\11 and 12\13 seem to posses values that, like the animations, can vary a bit. Focusing on bytes 10\11 we see these have a value of 6 in Keen's walking actions:

Code: Select all

#First walking frame data
%patch $2FF04 $008BW $0083W $0004W $0001W $0001W $0006W $0018W $0000W
              $0B80062CRL   $0B8014A9RL   $0B801B5FRL   $10B2W

To test what these control we can increase the value until we notice something (Or decrease it as well.) Let us change this to $0016W:

Code: Select all

#Keen's walking value changed
%patch $2FF0E $0016W
%patch $2FF2C $0016W
%patch $2FF4A $0016W
%patch $2FF68 $0016W

When we run the game we immediately notice two things; firstly Keen animates far, far slower than usual; the value obviously directly affects Keen's animation speed. Secondly Keen seems to slide across the ground. We can test this by changing the value again, each time we see that altering the value alters Keen's animation speed and also seems to affect his movement.

This seems simple enough to patch, it controls how long a sprite spends on an action. This also seems to affect speed for some actions, which makes sense if an action has a certain amount of 'speed' it must use during its time. There does seem to be a few exceptions though, any action with a value of $0002W for bytes 5\6 has a value of $0000W for its animation speed. And some speeds, such as falling aren't affected.


STEP 33: MOVEMENT SPEED

Given all this some value in the sprite action must control Keen's walking speed somehow. The most likely value is bytes 12\13, these have a large, but not exceptionally large value. We can test this by patching them to be $10 larger:

Code: Select all

#Keen walks faster
%patch $2FF10 $0028W
%patch $2FF2E $0028W
%patch $2FF4C $0028W
%patch $2FF6A $0028W

When we test this we indeed find that Keen walks a lot faster now, confirming that those bytes control Keen's horizontal speed in either direction. In fact the next two bytes control a sprite's vertical speed, aside from gravity, but this is much less useful since moth things either walk on the ground of fall through the air. (It is useful when dealing with, say, Keen's shots, which can move up and down in the air.)

So it seems a large amount, but not all, of a sprite's speed is dictated by its actions. This is a combination of both the action's speed and how long the sprite spends on that action. So to double the speed of a sprite one can either double its speed value or halve its animation time. (Or a combination of both.)Keeping this in mind is important, altering one thing could affect another unintentionally.

This concludes the 'simple' parts of the sprite action, everything else has a more complicated function, several of which will be explored in the next installment.
What you really need, not what you think you ought to want.
User avatar
Nisaba
Janitress
Posts: 1597
Joined: Fri Jan 01, 2016 23:34
Location: The Outpost
Contact:

Re: Levellass's Patching Tutorial

Post by Nisaba »

been there, done that.
thanks for explaining the essential structure behind all those sprite actions. sharing all these information is very much appreciated!
wiki updates can be found here: http://www.shikadi.net/keenwiki/Patchin ... te_actions
out now (link) : Image
Post Reply