📅August 19th, 2022
Short version: To disable collisions e.g., walk through walls in J. R. R. Tolkien's Lord of the Rings for SNES, use the following Pro Action Replay codes
80E0C780 (Disable horizontal collisions)
80E13480 (Disable vertical collisions)Longer explanation below.
There are some areas in maps I wanted to look at in this game, and those areas are inaccessible playing the game normally. How can you look at inaccessible parts of the game?
One option: rip the map. That would work, although it's cumbersome. It would cascade into the problem of also ripping the tileset graphics and figuring out how the each map datum maps to which tile. I did this process once for a different game, Lagoon. Those maps are here. It was doable because I already did some other projects involving that game so I had some information about it. For games I'm less familiar with, like LotR, it will take longer, probably so long it's not worth it.
An easier option instead is to disable collisions. So I set out to do that.
The general sense I had was that this will be a code change to the collision logic in the game. Some code must take the player's position, do some comparisons on it, and permit you to move or not move based on the comparisons. But which code is doing this?
1. Where position is stored
Breaking the problem down, the first step is to find where your position is stored in memory. It's likely to be an X, Y position since what kind of a maniac would store it in polar.
So there's a number, somewhere in the program. Classic problem where we don't know where it is stored. But worse yet, we also don't know what the number is, what its value is.
When faced with this kind of problem I do something I'm calling "special diffing", you can call it whatever you want, basically you take 3 or more memory dumps.
- For dump 0, you've got your character somewhere.
- For dump 1, you move them a little bit to the right.
- For dump 2, you move them a little bit more to the right.
And then write some code that opens the dumps, looking through each offset for some number that's increasing from dump 0 to 1, and 1 to 2. Want more confidence? Take more memory dumps to have more data points.
Why move horizontal and not vertical? Because there isn't a strong convention in computer graphics about whether up is positive or not. For horizontal there's a pretty strong convention.
Why move to the right, and not left? Convenience, we probably expect the position value to increase going to the right.
Why move just a little, and not a lot? So that you don't overflow the byte type (e.g., exceed 255) since that's a hassle to account for.
Using this diffing technique gave a few answers
- 7E05D3
- 7E0AE7
- 7E0EF7
- 7E1087
- 7E128F <-- The answer
- 7EFD46
It was a low enough number to rule out the false positives and find the answer:
7E128FThe other values corresponded to position too, but they were an output of it not an input. E.g., changing the value wouldn't stick, except for 7E128F.
2. What position is used for
The next obvious step is to break-on-write of position. We expect it to get hit whenever your character walks around, since it would get updated then. And moreover, we'd expect that code path to not get taken if you're hitting a wall.
Bad news here. The break-on-write will always fire regardless of whether you're moving or not-- the code is set up to always overwrite your position even if it doesn't need to. So that kind of breakpoint won't directly tell us which code paths fire or don't fire based on your hitting a wall.
For the record, it hits here:
$80/C88E 99 8F 12 STA $128F,y[$80:128F] A:0100 X:0000 Y:0000 P:envmxdizcThat's okay. It will at least tell us something, when your position does get updated while moving, and we can still reason about what happens when it doesn't get updated.
And in particular, we can locally disassemble or CPU log to find the preceding operations
...
$80/C883 69 00 00 ADC #$0000 A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C886 99 97 14 STA $1497,y[$80:1497] A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C889 AA TAX A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C88A 18 CLC A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C88B 79 8F 12 ADC $128F,y[$80:128F] A:0000 X:0000 Y:0000 P:envmxdiZc
$80/C88E 99 8F 12 STA $128F,y[$80:128F] A:013A X:0000 Y:0000 P:envmxdizcSo some position-increment value gets saved to $80:1497, then increment the position by that number too. We can use this to work backwards and see a bunch of other fields updated as well.
Now we know the neighborhood of the collision code and can reason about the code path involved.
3. Finding the branch
There are a couple ways to proceed from here. There's a 'nice' option and a 'cheesy' option.
The 'nice' option is to take where we know the position is stored, and find the chain of operations done to its value. This works out if the control flow for controlling position is pretty localized-- say, if collision-checking and position-updating is all in one tidy function and they're right next to each other.
Unfortunately, the position-updating logic was messy. It was seemingly tangled up with the logic for checking for interact-ables (e.g., doors, NPCs). So while the 'nice' option is still an option, it's costly. Therefore there's the 'cheesy' option.
The cheesy option is to break on position change, using the information we found above, so we at least have some kind of frame delimiter and something to look for. Then enable CPU logging. Log:
- one 'frame' where you can move, and
- one 'frame' where you're obstructed.
Then strip out IRQs (they create noise) in the CPU log. So now we have a clean logfile.
What is a CPU log?
Just text.
And you know what you can do with text?
Put it through a differ.
So I put the result through a giant diff. For this I used Meld.
The diff isn't so crazy.
See there's data-divergence up until a certain point. After that, execution-divergence. It was a kind of thing where I scrolled through it and it caught my attention, so not a really thorough debugging experience, anyway the previous stuff to untangle where position is stored helped to understand the data-divergence and filter out noise in the diff.
And that ended up being the answer. The comparison
$80/E0C4 DD 41 E6 CMP $E641,x[$80:E643] A:0010 X:0002 Y:00B2 P:envMxdizc
$80/E0C7 90 05 BCC $05 [$E0CE] A:0010 X:0002 Y:00B2 P:envMxdiZCwill check if you're about to collide with a wall, or not. If you're free to move, you take the branch. If you're obstructed, you fall through. Therefore we can disable collisions by always taking the branch. So change
$80/E0C7 90 05 BCC $05 [$E0CE]to
$80/E0C7 80 05 BRA $05 [$E0CE]A quick test will show you this only covers horizontal collisions. Vertical goes down a completely separate code path. I guessed that they shared a common subroutine
$80/E0BD 20 22 D0 JSR $D022 [$80:D022] A:00B2 X:0150 Y:00B2 P:envmxdizCand this ended up being true. Setting a breakpoint on D022 ended up hitting for the vertical case:
$80/D022 DA PHX A:0E05 X:016B Y:0095 P:envmxdizc
$80/D023 5A PHY A:0E05 X:016B Y:0095 P:envmxdizc
$80/D024 8A TXA A:0E05 X:016B Y:0095 P:envmxdizc
$80/D025 4A LSR A A:016B X:016B Y:0095 P:envmxdizc
$80/D026 4A LSR A A:00B5 X:016B Y:0095
...
$80/D033 7A PLY A:0000 X:0016 Y:026C P:envmxdiZc
$80/D034 FA PLX A:0000 X:0016 Y:0095 P:envmxdizc
$80/D035 60 RTS A:0000 X:016B Y:0095 P:envmxdizc
$80/E12D E2 20 SEP #$20 A:0000 X:016B Y:0095 P:envmxdizc
at which point it's easy to step out 1 frame and see the caller. And it turns out the caller looks very similar to the horizontal case, with the same kind of branch. It has
$80/E131 D9 41 E6 CMP $E641,y[$80:E643] A:0000 X:003F Y:0002 P:envMxdizc
$80/E134 90 05 BCC $05 [$E13B] A:0000 X:003F Y:0002 P:eNvMxdizcSo you can do a similar thing, changing the branch on carry clear to a branch unconditional
$80/E134 80 05 BRA $05 [$E13B] Putting it all together, the two codes are
80E0C780 (Disable horizontal collisions)
80E13480 (Disable vertical collisions)Here's a demo of it in action, successfully getting past a door.
Side thing, I also used the code to get above the door in Bree. That said, even when enabling collisions again, it didn't take me anywhere. So the door's either controlled by non-'physical' means or not implemented.
I was still left with this question of whether we can conclusively say the door is not implemented.
It's one thing to prove a positive, prove a program does something. Easy enough, you show it doing the thing.
It's another thing to prove a negative, to prove a computer program will never do a thing. Can you prove the door can never open? Not ever? You can't really, you can only reach levels of confidence. Can you prove White Hand is not in Pokemon? Can you prove Herobrine is not in Minecraft? Has anyone ever conclusively proven that the pendant in Dark Souls doesn't do anything? Well, see, they ran the program through a simulator and-- just kidding, they went low tech and asked the director, so then it's a social engineering problem of whether you believe him.
When people use formal or other methods to prove program behaviors or nonbehaviors, they exploit constraints in the programming language or execution environment. For example, a language like Haskell has a rich set of constraints which are helpful in proving behavior. Or if a computer is unplugged and has no battery, you have confidence it won't power on. But in our case we're talking about object code, not source code, and we're talking about something the hardware could do. The instruction set of the object code alone doesn't provide helpful constraints. Hell, we can't even universally statically disassemble programs on this platform (because the choice of instruction width is dynamically chosen). Statically prove nonbehavior?
I'm not trying to give credibility to conspiracy theories or the mindset behind that kind of thinking. I'm trying to explain why you might not find a conclusive answer when you might want one. Anyway, through this exercise I got a greater level of confidence that the door doesn't go anywhere.
Some details
- You can use both codes or one at a time.
- Disabling collisions means you also can't interact with objects like doors. If you want to pass through doors, re-enable collisions or enable them for one direction.
- If collisions are disabled for you, they're also disabled for allies, NPCs, and enemies.
- Disabling collisions will let you pass through 'physical' doors in the game, where you're obstructed simply by where you're allowed to walk. For example, the gate in Moria, and the fires on the steps by the Balrog. There can be other 'non-physical' doors, where you need to trigger the right game event (e.g., have a key) to open them.
I used password tricks to get to the end area with all events signaled in any case, and had collisions off. I got to freely walk around the area where you find Galadriel with the mirror.
It turns out, the area is an infinite plane!
It's for the best not to try and rip the level data. /j
📅May 17th, 2022
Say you're writing a Win32 application. You add a toolbar. Simple enough. Toolbar would look better with some things on it.
You want to, say, add a button to it. Like this
Flip through Petzold.
No chapters for toolbar dropdowns.
No obvious samples to use.
We're on our own, then.
Attempt 1: BTNS_DROPDOWN
You follow some of the sample code, and do the most natural thing. Use the toolbar button style 'BTNS_DROPDOWN'. (By the way, BTNS_DROPDOWN is the updated define for TBSTYLE_DROPDOWN. They mean the same thing.)
TBBUTTON tbButtons[] =
{
{ STD_CUT, 0, TBSTATE_ENABLED, BTNS_DROPDOWN, {0}, 0, (INT_PTR)L"Test" },
};
m_hwnd = CreateToolbarEx(
parent,
WS_CHILD | WS_VISIBLE | CCS_ADJUSTABLE | TBSTYLE_TOOLTIPS,
0,
sizeof(tbButtons) / sizeof(TBBUTTON), //nBitmaps
HINST_COMMCTRL,
0, // wBMID
tbButtons, //lpButtons
sizeof(tbButtons) / sizeof(TBBUTTON), // iNumButtons
90, 90, 90, 90,
sizeof(TBBUTTON)); // uStructSize
SetWindowLongPtr(m_hwnd, GWLP_USERDATA, (LONG_PTR)this);
SendMessage(m_hwnd, TB_AUTOSIZE, 0, 0);
ShowWindow(m_hwnd, TRUE);
Compile and run. STD_CUT is your standard built-in Windows scissors 'cut' icon. Result looks like this:
That visually looks fine. But wait. Let's try clicking on it.
It doesn't even show a 'button is pushed' animation. It should at least do that, right?
What gives? It's not disabled.
Attempt 2: TBSTYLE_EX_DRAWDDARROWS
Okay, so maybe our initialization of the dropdown menu was incomplete. Dropdown menus usually have an arrow at the right. Perhaps we need to add the "arrow at the right" extended style? Let's try adding the code
SendMessage(m_hwnd, TB_SETEXTENDEDSTYLE, 0, TBSTYLE_EX_DRAWDDARROWS);So that now, it looks like
TBBUTTON tbButtons[] =
{
{ STD_CUT, 0, TBSTATE_ENABLED, BTNS_DROPDOWN, {0}, 0, (INT_PTR)L"Test" },
};
m_hwnd = CreateToolbarEx(
parent,
WS_CHILD | WS_VISIBLE | CCS_ADJUSTABLE | TBSTYLE_TOOLTIPS,
0,
sizeof(tbButtons) / sizeof(TBBUTTON), //nBitmaps
HINST_COMMCTRL,
0, // wBMID
tbButtons, //lpButtons
sizeof(tbButtons) / sizeof(TBBUTTON), // iNumButtons
90, 90, 90, 90,
sizeof(TBBUTTON)); // uStructSize
SendMessage(m_hwnd, TB_SETEXTENDEDSTYLE, 0, TBSTYLE_EX_DRAWDDARROWS);
SetWindowLongPtr(m_hwnd, GWLP_USERDATA, (LONG_PTR)this);
SendMessage(m_hwnd, TB_AUTOSIZE, 0, 0);
ShowWindow(m_hwnd, TRUE);
Let's compile and run it and see what it looks like now.
This looks better. There's an arrow on the right. That should mean something good. Let's try clicking on it.
Clicking on the button itself works.
Clicking on the arrow doesn't 🙁
Attempt 3: BTNS_WHOLEDROPDOWN
Maybe the ticket is WHOLEDROPDOWN. Looking it up in the header, BTNS_WHOLEDROPDOWN purports to
That sounds like it could make the whole button appear responsive, so why not let's try it.
Result looks like this:
Okay. What if we try to click on it?
Nothing happens 🙁
What to do?
The Answer
The answer: toolbar dropdown menus, by default, don't have any animation for clicking on them. They're not like normal buttons. That's right, the button is still working, there's just no visual feedback unless you explicitly attach some yourself.
To make the toolbar dropdown button do something, you have to just trust that it is set up ok, and attach some behavior to the dropdown notification.
Fortunately you don't have to re-invent the wheel to do that. Here's an easy way to attach a simple pop-up menu to the dropdown.
First, you need to have your WndProc pay attention to WM_NOTIFY. The handler can be something like
case WM_NOTIFY:
{
LPNMTOOLBAR lpnmtb = (LPNMTOOLBAR)lParam;
if (lpnmtb->hdr.code == TBN_DROPDOWN)
{
// Get the coordinates of the button.
RECT rc;
SendMessage(lpnmtb->hdr.hwndFrom, TB_GETRECT, (WPARAM)lpnmtb->iItem, (LPARAM)&rc);
// Convert to screen coordinates.
MapWindowPoints(lpnmtb->hdr.hwndFrom, HWND_DESKTOP, (LPPOINT)&rc, 2);
HMENU hMenuLoaded = LoadMenu(g_hInst, MAKEINTRESOURCE(IDR_MENU1));
// Get the submenu for the first menu item.
HMENU hPopupMenu = GetSubMenu(hMenuLoaded, 0);
TPMPARAMS tpm;
tpm.cbSize = sizeof(TPMPARAMS);
tpm.rcExclude = rc;
TrackPopupMenuEx(hPopupMenu, TPM_LEFTALIGN | TPM_LEFTBUTTON | TPM_VERTICAL, rc.left, rc.bottom, hWnd, &tpm);
DestroyMenu(hMenuLoaded);
}
break;
}As for the menu IDR_MENU1, you can point it to a menu you have defined. Or, if you want a placeholder thing, put something like this in your .rc file:
IDR_MENU1 MENU
BEGIN
POPUP "TEST"
BEGIN
MENUITEM "Option 1", ID_TEST_OPTION1
MENUITEM "Option 2", ID_TEST_OPTION2
END
ENDThat goes along with these defines in the Resources.h coupled to the .rc file:
#define IDR_MENU1 132
#define ID_TEST_OPTION1 32777
#define ID_TEST_OPTION2 32778Build, and you get this:
In animated form:
The dropdown works. Success!
It so happens if you re-try Attempt 2, TBSTYLE_EX_DRAWDDARROWS with a pop up menu, then it'll provide visual arrow-is-pressed feedback where it didn't before. See:
This is because BTNS_DROPDOWN, TBSTYLE_EX_DRAWDDARROWS, and BTNS_WHOLEDROPDOWN follow a common principle: anything that appeared unresponsive with no pop up menu attached is responsive once a menu is attached.
This system was not super well explained elsewhere, so maybe this will help you.
📅April 25th, 2022
I made a Visual Studio extension for 65C816 syntax highlighting. Suitable for SNES or C256 Foenix projects. Looks like this:
The source+binary are on GitHub, here: https://github.com/clandrew/vscolorize65c816
I had some past experience working on a big existing system in a Visual Studio extension in a job I had a little while ago. This was my first time writing an extension for a recent version from scratch. The experience was different.
I accomplished what I set out to do and it's working well, but the path of getting there was cumbersome.
Here is a list of the problems I ran into.
Problem: No extension template.
Root cause: Template requires an optional add-on.
How debugged: search engine.
Problem: Official template has build error right out of the gate:
error VSSDK1048: Error trying to read the VSIX manifest file "obj\Debug\extension.vsixmanifest". Could not load file or assembly 'Microsoft.VisualStudio.Threading, Version=16.7.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a' or one of its dependencies. The system cannot find the file specified.
Root cause: The template has a missing dependency. To fix, you have to update the NuGet package "Microsoft.VSSDK.BuildTools".
How debugged: Shotgun debugging
Problem: Template does not behave correctly out of the gate. When launched with debugger, it is never loaded
Root cause: The template is missing an attribute
How debugged: Search engine
You don't create a syntax highlighter object out of the blue. You define a 'Package' object to set it up. I defined one in code.
Problem: Package object is never instantiated.
Root cause: You have to define, at a minimum, two attributes to make it get loaded: [PackageRegistration] and [ProvideAutoLoad].
How debugged: Looking at other extensions as examples + shotgun debugging
Problem: The package is instantiated, but doesn't correctly associate with the intended files. Error message when opening files that have ProvideLanguageExtension. "An error occured in 'file' when attempting to open 'file.s'. There is no editor available for 'file.s'. Make sure the application for the file type (.s) is installed."
Root cause: Something is stale. Reload the file! Even if you restart the whole IDE, it's not enough! It stays stale unless you specifically reload the file
How debugged: Shotgun debugging
Problem: The package adds a LanguageInfo service, but the LanguageInfo is never instantiated.
Root cause: You have to call AddService after InitializeAsync, not before
How debugged: Shotgun debugging + code examples
Problem: The syntax is not highlighted as intended
Root cause: Need to have IVsColorizer::ColorizeLine return the intended values
How debugged: Actual debugging
Problem: The choice of which attribute value maps to which color seems arbitrary
Root cause: There is a system of default colors. You can know that default through experimentation, or over-ride it in a specific way
How debugged: Experimentation
Takeaway- I accomplished what I was trying to do, but there was a lot of shotgun debugging and 'just trying things'. The extension framework has you hook into a complicated system which is also closed-off and opaque, so there is no way to directly debug it.
It may as well be running on a different computer.
By "system", I'm referring to
- The mechanism that instantiates your custom package and calls InitializeAsync on it
- The thing that looks at your custom package and loads it based on PackageRegistration
- The thing that sets up associations using package attributes like ProvideLanguageExtension.
- The thing that executes methods of objects set up with IServiceContainer::AddService
Look at my extension or other people's samples. You're supposed to define a **** ton of attributes on the Package class.
Here's an example from an open source project on GitHub:
It's to the point where the attributes are really a language in and of themselves. Guess what, they feed into some complicated loader that executes before your code is ever executed. If there's a mistake in the attributes? Get your psychic powers ready. Because there's no insight into this closed system or way see what it's doing. It doesn't even have the decency to put its state to debug console.
The time I spent actually debugging problems was in the minority. Most problems, the only way to fix them was by trying things. It's really bad. They could not be debugged in the debugger because they occur in a complicated system you don't have access to. This system and its higher-level concepts were not documented well enough to automatically know what to type. "Is ProvideLanguageService not supposed to have languageResourceID 100? Is that the reason it's failing, or something else?"
I'm not even angry about the 17KB of code and god knows how much memory it takes to make text a different color according to a simple scheme. What's really bad is this this closed off system that everyone is supposed to just be okay with, since I see it as part of a trend. UI layouts from markup are like this. App store launching is like this. Software junk food "press F5"-style emulators and VMs are like this. As we get more and more complicated software systems, there isn't enough follow-through to make them fully open and debuggable. So if they 'just work the first time' fantastic. But we all live in reality. Things will go wrong, and when they do, it's clear the system is grand and complicated and undocumented and undiagnosable.
As a random example, can you imagine if Direct3D 12 had no debug layer, and all it told you was E_INVALIDARG? Why would we accept this more broadly?
This is why I keep writing GUI applications as executables with Win32 or Windows Forms say. The form designer has the decency to give you a call stack. Actionable stack or some error string should be the bare minimum.
Shifting topics, here are things I learned about Visual Studio custom colorizers:
- The 'state' values passed to/from your callbacks have whatever meaning you want them to. The meaning of states is all user-defined. It's opaque to Visual Studio.
- An IVsLanguageInfo is reponsible for providing two things: a colorizer, and a code window manager. But you don't need to have both. You can just provide one if you want. For example you can provide a colorizer, but return E_NOTIMPL to IVsLanguageInfo::GetCodeWindowManager.
- In IVsColorizer::ColorizeLine, character at index N in the 'pszText' corresponds to element N of 'attributes' parameter.
- To add colors to text, you set values in the 'attributes' parameter of IVsColorizer::ColorizeLine. Like this:
Why does 1 mean red? Because it's based on whatever you set in your IVsProvideColorableItems callback object.
Yes, it's 1-indexed.
If you don't have an IVsProvideColorableItems set up, you'll get some defaults with blue, green, red, and black (default) text numbered in some way. You can experiment what means what. Using a value of greater than 6 will crash the extension, so that's fun. In my case, the default was almost good enough, but I wanted gray for directives like C++ has, for e.g., #include and #pragma. So I did end up implementing IVsProvideColorableItems.
All told, if you use the syntax highlighter with custom build tools, it looks like this:
so the experience is pretty smooth.
Direct download to the release is here https://github.com/clandrew/vscolorize65c816/releases/tag/v1.0.
📅April 15th, 2022
I had a conversation with someone recently.
It went like
Them: … And that's for someday whenever we have AI.
Me: We have AI. We had it for over 30 years
Them: I mean real AI.
Me: People keep raising the goalposts on what counts as AI.
Them: Well, fundamentally AI is whenever a computer makes a decision, so I'm referring to something more than that.
Me: A decision. A branch?
What is a decision made by a computer?
Consider say train tracks. You know, where there's a switch on the train track to choose which side the train goes onto. Say the switch is to the left, so the train goes to the left.
Would you say that the train track "made a decision"? Probably not. The track hardware was configured a certain way, so the train went that way. Makes sense. Easy to explain. To say the train track "made a decision" is giving this really simple hardware a lot of credit. If you were to say the train tracks "make a decision", you'd be saying all inanimate objects in your life are making decisions all the time- like a house of cards makes a 'decision' to stay up, or a building makes a 'decision' to stay standing-- it would all sound a bit crazy and the word "decision" would be so broad that it loses all meaning.
Now, adjust the scenario. Say there's more trains, more tracks. Three trains, ten tracks. More switches. Again the trains go according to the switches. Would you then say that the train tracks "made a decision"? Again, probably not. Although the trains' paths were more complicated, they can still be explained. The switches controlled where the trains were going to go. You can see how they work.
Now, adjust the scenario further. There's a billion trains on a billion tracks. Yes, that's a lot of trains. The paths are so complicated we only have insight into some of the switches. We can only debug some parts of the system directly. That said, we do have a model for the rest of the system. There are real trains and tracks. The model has an explanation based on hardware and not magic.
A computer system is this way like trains on a track. It doesn't make sense to say that a computer "makes a decision" any more than a train track does. There is electricity flowing through different paths, and although these paths are complicated they can be explained and expressed as functions.
You can go a step further and claim that human brains are the same. More trains, more tracks compared to computers- more complication. Yet, if you have belief in the natural world, you can buy an explanation where it's all running on hardware and not magic. The difference between the human brain and the train tracks isn't anything fundamental. The difference is the complexity of the system.
Why is a train track just "some hardware configuration" while human's behavior gets elevated to this higher status, gets this special label called "a decision"? It's the complexity and that's all. A system that's sufficiently complicated and hard to simulate gets the elevated status of "decision". Nothing's inherently special about a "decision" other than the fact we've decided it's too complicated to reason about.
People ascribe magical qualities to systems that are complicated. "Free will". "Agency". "Decision". They're all functions, they all have a set of inputs and outputs. Yet these words have this mysterious quality about them, like they happen independently, spontaneously, defying explanation. I say the spontenaity is all an illusion. With enough information, any decision made by human or computers can be debugged and stepped through. If we had a system with infinite computing power and perfect information, we could predict the future, even if it means simulating forward.
This is why free will is a comforting illusion. We're living in that moment where a coin has been flipped, yet the answer has not been revealed to you yet.
This is in regards to things at macroscopic scale. Not quantum particles
You might be saying, "I don't like this idea. I like free will. Because what does it matter? Whether the coin's been flipped and not yet revealed yet, or not flipped at all-- you have the same information. It doesn't change anything."
Or you're saying, "I don't like this idea. I like free will. Because, if people think they don't have free will, it makes them feel helpless and lethargic, like they shouldn't take initiative on things."
Those are both the wrong takeaway, though. Just because free will is an illusion, doesn't mean the things you do don't matter. They do matter. And as for the coin flip, does it change anything- well, no and yes.
If you believe the coin flip is a function with inputs (physical world) and output (a heads or tails), then you might want to debug and more deeply understand how the inputs affect the result. You might look into physics simulations. How does air resistance affect the coin's path in the air? What about the weight distribution of coins? How does your style of coin-flipping affect its travel through the air? You can learn something about why you got a heads or tails.
On the other hand if you believe the coin flip is 100% purely decided in the moment, based on completely undeterminable factors, your inquiry about it stops there. The result is just random. It may as well be magic. It just is.
Mapping the idea of the "coin flip" onto human decisions, the real takeaway is that human decisions can be explained. They have a physical, natural basis. They're not random. They're not magic. Yes, they are super complicated- they're functions with lots of inputs and outputs- they are functions nonetheless. People have reasons for the things they do.
I don't care whether you believe in "free will". I don't care whether you buy my idea about free will being an illusion, about decisions and "the coin flip" or not. If you don't, that's fine.
I do care that you accept human decisions can be explained. They're not really spontaneous, not unexplainable black boxes. They're a product of previous work and exposure to the outside world. From whatever starting point, that's the end point to end up at. I understand a lot of decisions are hard to explain. But we can try and we should.
The idea of explainable decisions may seem like an obvious no-brainer. The thing is, I keep running into people for whom it's not obvious. They will say things of the form, "Red-haired people don't like baseball". Arguments of the form "X type of people don't like to do Y". In some cases, the person has even written essays on it, read studies on it, and spent dozens and dozens of hours debating with others on podcasts about it.
But when you press them on the $64,000 question, "Why do red-haired people not like baseball", it's not even that they don't have an answer- they will get bewildered by the question like they've never even considered it before. Their answer is "they just don't." Okay. That's it, they just don't. Just 'cause. They don't.
Could be these people believe in bio-essentialism. Like red hair intrinsically, genetically causes you to like certain sports and not others. It's determined from birth. Maybe even earlier. No matter how you're socialized, who raises you, they'll claim your involvement in baseball in really affected by red hair. Or at least, there's a very severe natural ceiling in redhead interest. Bio-essentialiasm has become un-pallateable over the years, especially when used to describe gender or racial groups, and is not well scientifically explained or justified (compared to heritability, which is different), so they don't want to say that out loud.
Could be they are confused about descriptive claims. Descriptive claims are things like "the house is red.", it's what something is today. By contrast, normative claims are "the house should be green", it's about what we should do, what we ought to do. Sometimes, people see a descriptive claim like "red-haired people don't tend to like baseball", that will get confused into a normative claim, "red-haired people should not get into baseball". It's as if things today represent the 'correct' state of the world and it's a lost cause to try and change anything, ignoring the fact things have changed before and are constantly changing.
Could be they don't care about the reason. They want to talk about the correlation they're seeing, where it would appear red-haired people don't currently play baseball, but stop short of trying to debug why. This might seem incredible, given how much time and energy they've spent on the topic. All those hours spent debating with people, listening to podcasts, making social media posts, editing videos. Still it can happen. Our educational system has a lot of gaps where people end up having a deep lack of curiosity.
If unchallenged directly on debugging the reason, there's a typical pattern that comes up. They will dance around the subject, make descriptive claims that imply bio-essentialism, gesture towards inexplicable "choices" of red-haired people, and use those to funnel into normative claims.
For example, they'll say something of the form, "Studies show that currently, only 5% of red-haired people like baseball, much lower than average. That's inarguable. And those are the choices they're making, nothing wrong with that. So you shouldn't put red-haired people on baseball teams so they're not going to be invested in the sport anyway".
What happened here? Dissecting this, they took a descriptive claim about how things are today. They used "inarguable" to subtly imply a lack of bias around interpretation of the information, plus a way to use speaking in absolutes to imply the description will always hold. Then used the claim to make a judgment about what we should do, along with the word "choices" to say it's a just state of the world. Where to question it would be to take power away from red-haired people somehow, even when that's what the very proposal is doing. Although it is sneaky it falls apart when challenged directly, since there's no well-justified reason for the claim, even if it sounds like there is one.
The confusion, the lack of curiosity, it comes from this idea that people invest heavily in the concept of opaque human "decisions". As if humans aren't this huge network of train tracks, a billion tracks with different switches, as if instead they're built on randomness and magic. People use "decisions" and "free will" as a cop-out from having to investigate any more. It keeps them from having to ask the hard questions of why someone might do something, or what would motivate something to happen. They can write it off as "that's their decision", "just because that's what they wanted to do", without acknowledging that people don't do random things. The indiscriminate acceptance of "just because" leads to poorly-formed normative claims, and people putting the trappings of thoughtfulness around bad arguments.
Although we can not debug every neuron in the brain, we can intuitively know that people don't do random things.
Imagine your favorite hobby, or a sport you like to play. If you were air-dropped in the middle of the forest or desert and raised there apart from civilization, where would you get the idea to do that hobby? How would you ever think to kick a black-and-white ball around? How would you think to slide a rubber disc on ice? The idea came from other people. Or, can you accept the premise that advertising works? It does, doesn't it? That makes more sense than companies spending billions of dollars on literally nothing, something that doesn't work. People keep getting exposed to advertisements, so they are more likely to buy that product. It's hard to accept how shaped you are by your environment but that's the bitter medicine everyone needs to accept.
Although human motives are complicated, it doesn't mean we shouldn't even try to understand them. Human intelligence and artificial intelligence might have different levels of complexity, but that's all. They are both based on natural causes, not randomness.
If your computer program has some misbehavior and it was important to you, you'd output some logs, you'd attach a debugger. You wouldn't say, "that's the computer's decision" and refrain from investigating any more.
📅April 12th, 2022
Here is some C++:
compiled to x86.
Obvious disclaimer this is brittle, very platform and compiler dependent, will break if you look at it the wrong way.
How it works: this part
if (fnChar[0] == 0xE9) // Strip off dummy call
{
realMain = fnChar + ((fnChar[2] << 8) | fnChar[1]) + 5;
}is because some compiler settings can mean your functions are called from jump thunks. For example, if you take the address of function "main", stored as fnChar, it gives you
Rather than the function body you'd expect, it's an entry in a sea of jumps. These are incremental linking jump thunks. While we could deal with this by disabling incremental linking, it's not too hard to robustify against. To look up what's the "real" address of main, the code looks at the offset of the jump-relative, adds it on plus 5 which is the length of the jmp operation.
After that is this part:
for (int i = 0; i < INT_MAX; ++i) // Find offset to jump to
{
if (realMain[i + 0] == 0xCC && realMain[i + 1] == 0x68)
{
return reinterpret_cast<SimpleFn>(realMain + i + 1);
}
}This seeks through main for some delimiter. The delimiter, in this case, is
Wherever it finds the int 3 delimiter, that's the code we want to call. Could key off of only 0xCC but that's a very common term, it also happens to be used for setting up an argument to __CheckForDebuggerJustMyCode, so use the first byte of the subsequent push to dis-ambiguate.
And finally, the
exit(0);is a cheesy trick to compensate for the fact that we didn't set up the stack frame properly. We'd run into this problem when jumping into the middle of almost any function (by messing with the function pointer). As far as the compiler's concerned, you're supposed to jump to the beginning of functions. By jumping into the middle, we skip a bunch of initialization, like the allocation of stack-allocated variables in function scope. And switching to global variables doesn't help for debug. When compiling for debug, the generated code allocates stack space automatically for you even if you have no local variables.
When main exits, it'll compare the stack pointer, and make sure it reflects base pointer + stack allocation to make sure nothing corrupted the value of the stack pointer somehow. This validation would catch a legitimate issue in this case. Bailing out with exit avoids the whole thing.
In all, this is a case where the compiler says you have code that's not reachable but it actually is.
The principle of this being possible is obvious to some people, but not all. I've had people say to me that "good compilers can always 100% statically know if code is reachable or not". It's not true, for C++ to x86 anyway. I tell them, "No, code is just code. At the end of the day, if code exists in a binary, you can execute it. Compilers can't exhaustively evaluate what generated code will do. They can't solve the halting problem" They don't understand what I mean and there's a gap in understanding so I hope a proof-by-example would explain, even if it's a super contrived and impractical one.
"But what if I enable optimizations?" If you enable optimizations, the code labeled "unreachable" will be actually missing from the binary. Yes that means the compiler is wrong. To work around I'd suggest adding some dummy control flow to tell the compiler the code is reachable.
This was tested using MSVC.
If you want to try the above code, here:
📅March 1st, 2022
Answer: mostly, yes. Explanation below.
Part 1: Yes or No
Remember GDI? Say you're using GDI and Win32, and you want to draw some graphics to a window. What to do. You read the documentation and see what looks like the most obvious thing: "SetPixel". Sounds good. Takes an x and y and a color. What more could you want? Super easy to use.
But then, you see a bunch of cautionary notes. "It's slow." "It's inefficient." "Don't do it."
Don't do it?
Well. All these cautionary notes you see are from days of yore:
- Computers are faster now. Both CPU and GPU. Take an early CS algorithms class, experiment with solutions. You’ll see sometimes the biggest optimization you can do is to get a faster computer.
- An earlier Windows graphics driver model. Say, XPDM not WDDM. WDDM means all hardware-accelerated graphics communicate through a “Direct3D-centric driver model”, and yes that includes GDI. Changes in driver model can impose changes in performance characteristics.
- Different Windows presentation model. That's something this API is set up to negotiate with, so it could affect performance too. Nowadays you're probably using DWM. DWM was introduced with Windows Vista.
The date stamps give you skepticism. Is that old advice still true?
As a personal aside, I've definitely seen performance advice from people on dev forums that is super outdated and people get mis-led into following it anyway. For example for writing C++ code, to "manually turn your giant switch case into a jump table". I see jump tables in my generated code after compilation... The advice was outdated because of how much compilers have improved. I've noticed a tendency to trust performance advice "just in case", without testing to see if it matters.
Let us run some tests to see if SetPixel is still slow.
I wrote a benchmark program to compare
- SetPixel, plotting each pixel of a window sequentially one by one, against
- SetDIBits, where all pixels of a window are set from memory at once.
In each case the target is a top-level window, comparing like sizes. Each mode effectively clears the window. The window is cleared to a different color each time, so you have some confidence it’s actually working.
Timing uses good old QPC. For the sizes of timespans involved, it was not necessary to get something more accurate. The timed interval includes all the GDI commands needed to see the clear on the target, so for SetDIBits that includes one extra BitBlt from a memory bitmap to the target to keep things fair.
The source code of this benchmark is here.
Here are the results
| Width | Height | Pixel Count | SetPixel | SetDIBits |
| 1000 | 1000 | 1000000 | 4.96194 | 0.0048658 |
| 950 | 950 | 902500 | 4.7488 | 0.0042761 |
| 900 | 900 | 810000 | 4.22436 | 0.0038637 |
| 850 | 850 | 722500 | 3.71547 | 0.0034435 |
| 800 | 800 | 640000 | 3.34327 | 0.0030824 |
| 750 | 750 | 562500 | 2.92991 | 0.0026711 |
| 700 | 700 | 490000 | 2.56865 | 0.0023415 |
| 650 | 650 | 422500 | 2.21742 | 0.0022196 |
| 600 | 600 | 360000 | 1.83416 | 0.0017374 |
| 550 | 550 | 302500 | 1.57133 | 0.0015125 |
| 500 | 500 | 250000 | 1.29894 | 0.001311 |
| 450 | 450 | 202500 | 1.05838 | 0.0010062 |
| 400 | 400 | 160000 | 0.826351 | 0.0009907 |
| 350 | 350 | 122500 | 0.641522 | 0.0006527 |
| 300 | 300 | 90000 | 0.467687 | 0.0004657 |
| 250 | 250 | 62500 | 0.327808 | 0.0003364 |
| 200 | 200 | 40000 | 0.21523 | 0.0002422 |
| 150 | 150 | 22500 | 0.118702 | 0.0001515 |
| 100 | 100 | 10000 | 0.0542065 | 9.37E-05 |
| 75 | 75 | 5625 | 0.0315026 | 0.000122 |
| 50 | 50 | 2500 | 0.0143235 | 6.17E-05 |
Viewed as a graph:
Conclusion: yeah, SetDIBits is still way faster than SetPixel in general, in all cases.
For small numbers of pixels, the difference doesn't matter as much. For setting lots of pixels, the difference is a lot.
I tested this on an Intel Core i7-10700K, with {NVIDIA GeForce 1070 and WARP} with all similar results.
So the old advice is still true. Don't use SetPixel, especially if you’re setting a lot of pixels. Use something else like SetDIBits instead.
Part 2: Why
My benchmark told me that it’s still slow, but the next question I had was ‘why’. I took a closer look and did some more thinking about why it could be.
It's not one reason. There's multiple reasons.
1. There's no DDI for SetPixel.
You can take a look through the public documentation for display devices interfaces, and see what’s there. Or, take a stab at it and use the Windows Driver Kit and the provided documentation to write a display driver yourself. You’ll see what’s there. You’ll see various things. You’ll see various blit-related functions in winddi.h. For example, DrvBitBlt:
BOOL DrvBitBlt(
[in, out] SURFOBJ *psoTrg,
[in, optional] SURFOBJ *psoSrc,
[in, optional] SURFOBJ *psoMask,
[in] CLIPOBJ *pco,
[in, optional] XLATEOBJ *pxlo,
[in] RECTL *prclTrg,
[in, optional] POINTL *pptlSrc,
[in, optional] POINTL *pptlMask,
[in, optional] BRUSHOBJ *pbo,
[in, optional] POINTL *pptlBrush,
[in] ROP4 rop4
);That said, you may also notice what’s not there. In particular, there’s no DDI for SetPixel. Nothing simple like that, which takes an x, y, and color. It’s important to relate this to the diagrams on the “Graphics APIs in Windows” article, which shows that GDI talks to the driver for both XPDM and WDDM. It shows that every time you call SetPixel, then what the driver sees is actually far richer than that. It would get told about a brush, a mask, a clip. It’s easy to imagine a cost to formulating all of those, since they you don’t specify them at the API level and the API is structured so they can be arbitrary.
2. Cost of talking to the presentation model
There’s a maybe-interesting experiment you can do. Write a Win32 application with your usual WM_PAINT handler. Run the application. Hide the window behind other windows, then reveal it once again. Does your paint handler get called? To reveal the newly-revealed area? No, normally it doesn’t.
So what that must logically mean is that Windows kept some kind of buffer, or copy of your window contents somewhere. Seems like a good idea if you think about it. Would you really want moving windows around to be executing everyone’s paint handlers all the time, including yours? Probably not. It’s the good old perf-memory tradeoff in favor of perf, and it seems worth it.
Given that you’re drawing to an intermediate buffer, then there’s still an extra step needed in copying this intermediate buffer to the final target. Which parts should be copied, and when? It seems wasteful to be copying everything all the time. To know what needs to get re-copied, logically there has to be some notion of an “update” region, or a “dirty” region.
If you’re an application, you might even want to aggressively optimize and only paint the update region. Can you do that? At least at one point, yes you could. The update region gets communicated to the application through WM_PAINT- see the article “Redrawing in the Update Region”. There’s a code example of clipping accordingly. Now, when I tried things out in my application I noticed that PAINTSTRUCT::rcPaint is always the full window, even in response to a small region invalidated with InvalidateRect, but the idea is at least formalized in the API there.
Still, there’s a cost to dealing with update regions. If you change one pixel, that one-pixel area is part of the update region. Change the pixel next to it, the region needs to be updated again. And so on. Could we have gotten away with having a bigger, coarser update region? Maybe. You just never know that at the time.
If you had some way of pre-declaring which regions of the window you’re going to change, (e.g., through a different API like BitBlt), then you wouldn’t have this problem.
3. Advancements in the presentation model help, but not enough
In Windows, there is DWM- the Desktop Window Manager. This went out with Windows Vista and brought about all kinds of performance improvements and opportunity for visual enhancements.
Like the documentation says, DWM makes it possible to remove level of indirection (copying) when drawing contents of Windows.
But it doesn’t negate the fact that there still is tracking of update regions, and all the costs associated with that.
4. Advancements in driver model help, but not enough
DWM and Direct3D, as components that talk to the driver through the 3D stack, have a notion of “frames” and a particular time at which work is “flushed” to the GPU device.
By contrast, GDI doesn’t have the concept of “frames” or flushing anything. Closest thing would be the release of the GDI device context, but that’s not strictly treated as a sign to flush. You can see it yourself in how your Win32 GDI applications are structured. You draw in response to WM_PAINT. Yes there is EndPaint, but EndPaint doesn’t flush your stuff. Try it if you want- comment out EndPaint. I tried it just to check and everything still works without it.
Since there isn’t a strict notion of “flushing to the device”, SetPixel pixels have to be dispatched basically immediately rather than batched up.
5. 3D acceleration helps, but not enough
Nowadays, GDI blits are indeed 3D accelerated.
- They were,
- then they weren’t for Vista,
- then they were again.
I noticed this firsthand, too. Very lazy way to check- in the “Performance” tab in Task manager when I was testing my application, I saw little blips in the 3D queue. These coincided with activity in the SetPixel micro-benchmark.
Again, very lazy check. Good to know we are still accelerating these 2D blits, even as the graphics stack has advanced to a point of making 3D graphics a first-class citizen. Hardware acceleration is great for a lot of things, like copying large amounts of memory around at once, applying compression or decompression, or manipulating data in other ways that lend itself to data-parallelism.
Unfortunately, literally none of that helps this scenario. Parallelism? How? At a given time, the driver doesn’t know if you’re done plotting or what you will plot next or where. And it can’t buffer up the operations and execute them together, because it, like Windows, doesn’t know when you’re done. Maybe, it could use some heuristic.
But that brings this to the punchline: even if the driver had psychic powers, it could see into the future and know exactly what the application is going to do and did an absolutely perfect job of coalescing neighboring blits together, it doesn’t negate any of the above costs, especially 1. and 2.
Conclusion
Even in the current year, don’t use SetPixel for more than a handful of pixels. There’s reasons to believe the sources of the bottlenecks to have changed over 30 years, yet even still the result is the same. It’s slow and the old advice is still true.
Epilogue: some fantasy world
This post was about how things are. But, what could be? What would it take for SetPixel not to be slow? The most tempting way to think about this is to flatten or punch holes through the software stack. That works, even if it feels like a cop-out.
📅February 19th, 2022
To make it so you don't need to water your plants in Harvest Moon for Super Nintendo, use the PAR codes
82A8ACEA
82A8ADEAExplanation below.
The game 'Harvest Moon' for Super Nintendo has fun elements, but also repetitive ones. One of them that wore on me was having to water your plants. If you water at night, it's not even a skill-based action mechanic since you can restore your energy and night lasts forever. I wanted to experience the game and see its content, but not have the repetitive action of watering.
Idea: patch the game so that watering is not needed
First approach was to take memory dumps before and after watering a tile, and diff them. Seems ok. But, the diffs were too noisy and I didn't know what I was looking for. How were the farm tiles stored? Was it even one byte per tile, one byte per pair of tiles, or something else entirely? I didn't even know that part yet, so I gave up on it.
Instead, I tried something way dumber- keep watering a tile with a view of live memory open, and watch for changes. I had an idea of what the storage could be- one byte per tile, arranged sequentially, so I looked for that. And I planted some test plants in an observable pattern. This plus exploiting timing of changes made it way easier to discern signal from noise and I found it.
There were not one, but two places the tile data lived. For the tile I'm standing near, the first was at 7E1100 and that one I found first. When I left the farm and came back I saw that the data got wiped and restored, so that meant it's a cache and not the primary copy.
Looking for a dupe of it in memory, I found that at 7EAC30, more likely to be the primary copy.
From experimenting I found this out about the tile storage:
- It is one byte per tile
- Tiles are stored sequentially. Nothing too crazy.
And as for what tile value means what thing, I found
| Tile Value | What It Means |
| 0x00 | Untilled, unwatered ground |
| 0x01 | Untilled, unwatered ground (different graphic from above) |
| 0x07 | Tilled, unwatered ground |
| 0x08 | Tilled, watered ground |
| 0x58 | Unwatered potato seed |
| 0x59 | Watered potato seed |
| 0x68 | Unwatered turnip seed |
| 0x69 | Watered turnip seed |
(Not exhaustive.)
From the data points there are, watering a tile simply increments its value by 1. So when it rains, something must iterate through all the tiles and increment their value by 1.
To find out what that is, I set a break-on-write of 0x7EAC32, the location of the top-left plant, looking for the value to change from 0x58 to 0x59. This took me right into this code
(Paste below is multiple debugging transcripts spliced together so don't put too much stock in the reg values.)
void ProcessWeather()
...
$82/8390 8F 1E 1F 7F STA $7F1F1E[$7F:1F1E] A:0400 X:0400 Y:0400 P:eNvMxdizc
$82/8394 22 D6 89 82 JSL $8289D6[$82:89D6] A:0400 X:0400 Y:0400 P:eNvMxdizc
// Call UpdateFarmTiles, transcribed below
$82/8398 22 11 A8 82 JSL $82A811[$82:A811] A:0400 X:0400 Y:0400 P:eNvMxdizc
$82/839C 22 09 82 82 JSL $828209[$82:8209] A:0400 X:0400 Y:0400 P:eNvMxdizc
...
void UpdateFarmTiles() - $82/A811
// Preconditions:
// Weather is stored at $7E0196. 0x0 means sunny, 0x2 means rainy.
// Farm data is stored around $7EAC30.
// This function is called when you sleep, no matter the weather or if you save.
$82/A811 E2 20 SEP #$20 A:0007 X:000E Y:0002 P:envmxdizC
$82/A813 C2 10 REP #$10 A:0007 X:000E Y:0002 P:envMxdizC
$82/A815 A9 04 LDA #$04 A:0007 X:000E Y:0002 P:envMxdizC
$82/A817 8D 81 01 STA $0181 [$00:0181] A:0004 X:000E Y:0002 P:envMxdizC
$82/A81A C2 20 REP #$20 A:0004 X:000E Y:0002 P:envMxdizC
$82/A81C A0 00 00 LDY #$0000 A:0004 X:000E Y:0002 P:envmxdizC
$82/A81F A2 00 00 LDX #$0000 A:01E0 X:0400 Y:01E0 P:eNvmxdizc
StartProcessingTile:
$82/A822 5A PHY A:00D0 X:00D0 Y:01D0 P:eNvmxdizc
$82/A823 DA PHX A:00D0 X:00D0 Y:01D0 P:eNvmxdizc
$82/A824 86 82 STX $82 [$00:0082] A:00D0 X:00D0 Y:01D0 P:eNvmxdizc
$82/A826 84 84 STY $84 [$00:0084] A:00D0 X:00D0 Y:01D0 P:eNvmxdizc
$82/A828 20 3C B1 JSR $B13C [$82:B13C] A:00D0 X:00D0 Y:01D0 P:eNvmxdizc
$82/A82B E2 20 SEP #$20 A:074D X:074D Y:01D0 P:envmxdizc
// Load the state for a tile in your farm. We look at just 1 byte
$82/A82D BF E6 A4 7E LDA $7EA4E6,x[$7E:AC33] A:074D X:074D Y:01D0 P:envMxdizc
; Do various things for the different tile types.
$82/A831 D0 03 BNE $03 [$A836] A:0758 X:074D Y:01D0 P:envMxdizc
$82/A836 C9 03 CMP #$03 A:0758 X:074D Y:01D0 P:envMxdizc
$82/A838 B0 03 BCS $03 [$A83D] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A83A 4C 1B A9 JMP $A91B [$82:A91B] A:0701 X:074F Y:01D0 P:eNvMxdizc
$82/A83D C9 A0 CMP #$A0 A:0758 X:074D Y:01D0 P:envMxdizC
$82/A83F 90 03 BCC $03 [$A844] A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A844 C9 06 CMP #$06 A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A846 D0 03 BNE $03 [$A84B] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A84B C9 07 CMP #$07 A:0758 X:074D Y:01D0 P:envMxdizC ; Is tilled soil?
$82/A84D F0 55 BEQ $55 [$A8A4] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A84F C9 08 CMP #$08 A:0758 X:074D Y:01D0 P:envMxdizC
$82/A851 D0 03 BNE $03 [$A856] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A856 C9 1E CMP #$1E A:0758 X:074D Y:01D0 P:envMxdizC
$82/A858 F0 4A BEQ $4A [$A8A4] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A85A C9 1F CMP #$1F A:0758 X:074D Y:01D0 P:envMxdizC
$82/A85C D0 03 BNE $03 [$A861] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A861 C9 1D CMP #$1D A:0758 X:074D Y:01D0 P:envMxdizC
$82/A863 D0 03 BNE $03 [$A868] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A868 C9 20 CMP #$20 A:0758 X:074D Y:01D0 P:envMxdizC
$82/A86A B0 03 BCS $03 [$A86F] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A86F C9 39 CMP #$39 A:0758 X:074D Y:01D0 P:envMxdizC
$82/A871 D0 03 BNE $03 [$A876] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A876 C9 53 CMP #$53 A:0758 X:074D Y:01D0 P:envMxdizC
$82/A878 D0 03 BNE $03 [$A87D] A:0758 X:074D Y:01D0 P:envMxdizC
$82/A87D C9 61 CMP #$61 A:0758 X:074D Y:01D0 P:envMxdizC
$82/A87F D0 03 BNE $03 [$A884] A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A884 C9 6F CMP #$6F A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A886 D0 03 BNE $03 [$A88B] A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A88B C9 79 CMP #$79 A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A88D D0 03 BNE $03 [$A892] A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A892 C9 7C CMP #$7C A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A894 D0 03 BNE $03 [$A899] A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A899 C9 70 CMP #$70 A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A89B B0 69 BCS $69 [$A906] A:0758 X:074D Y:01D0 P:eNvMxdizc
$82/A89D 29 01 AND #$01 A:0758 X:074D Y:01D0 P:eNvMxdizc ; Mask
$82/A89F F0 03 BEQ $03 [$A8A4] A:0700 X:074D Y:01D0 P:envMxdiZc
...
$82/A8A4 C2 20 REP #$20 A:0700 X:074D Y:01D0 P:envMxdiZc
$82/A8A6 AD 96 01 LDA $0196 [$00:0196] A:0700 X:074D Y:01D0 P:envmxdiZc ; Load weather
; 0x0 means sunny.
; 0x2 means rainy.
$82/A8A9 29 02 00 AND #$0002 A:0002 X:074D Y:01D0 P:envmxdizc
; If not rainy, skip ahead--
$82/A8AC F0 03 BEQ $03 [$A8B1] A:0002 X:074D Y:01D0 P:envmxdizc
; If it is rainy, goto IncrementTileValue to mark the tile as watered.
$82/A8AE 4C 06 A9 JMP $A906 [$82:A906] A:0002 X:074D Y:01D0 P:envmxdizc
...
IncrementTileValue:
; This is a common path for all kinds of tile incrementing, it's not just for rain.
$82/A906 E2 20 SEP #$20 A:0002 X:074D Y:01D0 P:envmxdizc
; Load early-out cond
$82/A908 AF 19 1F 7F LDA $7F1F19[$7F:1F19] A:0002 X:074D Y:01D0 P:envMxdizc
$82/A90C C9 03 CMP #$03 A:0000 X:074D Y:01D0 P:envMxdiZc ;
$82/A90E F0 59 BEQ $59 [$A969] A:0000 X:074D Y:01D0 P:eNvMxdizc ;
; Load tile value
$82/A910 BF E6 A4 7E LDA $7EA4E6,x[$7E:AC33] A:0000 X:074D Y:01D0 P:eNvMxdizc
; Apply 'watered' status
$82/A914 1A INC A A:0058 X:074D Y:01D0 P:envMxdizc
WriteRainEffect:
; X=0x74C means just to the right of shipping bin.
; Value of 0x59 means 'watered'.
$82/A915 9F E6 A4 7E STA $7EA4E6,x[$7E:AC32] A:0059 X:074C Y:01D0 P:envMxdizc
; Goto DoneProcessingTile.
$82/A919 80 4E BRA $4E [$A969] A:0059 X:074C Y:01D0 P:envMxdizc
...
OnUntilledSoil:
$82/A91B E2 20 SEP #$20 A:0701 X:074F Y:01D0 P:eNvMxdizc
$82/A91D AF 19 1F 7F LDA $7F1F19[$7F:1F19] A:0701 X:074F Y:01D0 P:eNvMxdizc
$82/A921 C9 02 CMP #$02 A:0700 X:074F Y:01D0 P:envMxdiZc
$82/A923 F0 44 BEQ $44 [$A969] A:0700 X:074F Y:01D0 P:eNvMxdizc
$82/A925 C9 03 CMP #$03 A:0700 X:074F Y:01D0 P:eNvMxdizc
$82/A927 F0 40 BEQ $40 [$A969] A:0700 X:074F Y:01D0 P:eNvMxdizc
$82/A929 AF 1B 1F 7F LDA $7F1F1B[$7F:1F1B] A:0700 X:074F Y:01D0 P:eNvMxdizc
$82/A92D 29 03 AND #$03 A:0706 X:074F Y:01D0 P:envMxdizc
$82/A92F D0 38 BNE $38 [$A969] A:0702 X:074F Y:01D0 P:envMxdizc ; Goto DoneProcessingTile
...
DoneProcessingTile:
$82/A969 C2 30 REP #$30 A:0059 X:074C Y:01D0 P:envMxdizc
$82/A96B FA PLX A:0059 X:074C Y:01D0 P:envmxdizc
$82/A96C 7A PLY A:0059 X:00C0 Y:01D0 P:envmxdizc
$82/A96D 8A TXA A:0059 X:00C0 Y:01D0 P:envmxdizc
$82/A96E 18 CLC A:00C0 X:00C0 Y:01D0 P:envmxdizc
$82/A96F 69 10 00 ADC #$0010 A:00C0 X:00C0 Y:01D0 P:envmxdizc
$82/A972 AA TAX A:00D0 X:00C0 Y:01D0 P:envmxdizc
$82/A973 E0 00 04 CPX #$0400 A:00D0 X:00D0 Y:01D0 P:envmxdizc
$82/A976 F0 03 BEQ $03 [$A97B] A:00D0 X:00D0 Y:01D0 P:eNvmxdizc
$82/A978 4C 22 A8 JMP $A822 [$82:A822] A:00D0 X:00D0 Y:01D0 P:eNvmxdizc
DoneProcessingField:
$82/A97B 98 TYA A:0400 X:0400 Y:01D0 P:envmxdiZC
$82/A97C 18 CLC A:01D0 X:0400 Y:01D0 P:envmxdizC
$82/A97D 69 10 00 ADC #$0010 A:01D0 X:0400 Y:01D0 P:envmxdizc
$82/A980 A8 TAY A:01E0 X:0400 Y:01D0 P:envmxdizc
$82/A981 C0 00 04 CPY #$0400 A:01E0 X:0400 Y:01E0 P:envmxdizc
$82/A984 F0 03 BEQ $03 [$A989] A:01E0 X:0400 Y:01E0 P:eNvmxdizc
$82/A986 4C 1F A8 JMP $A81F [$82:A81F] A:01E0 X:0400 Y:01E0 P:eNvmxdizc
...This provides enough information to understand how the 'watered' status gets applied. So to apply watered status irrespective of rain, you can just change the branch below
$82/A8A9 29 02 00 AND #$0002 A:0002 X:074D Y:01D0 P:envmxdizc
; If not rainy, skip ahead--
$82/A8AC F0 03 BEQ $03 [$A8B1] A:0002 X:074D Y:01D0 P:envmxdizc
; If it is rainy, goto IncrementTileValue to mark the tile as watered.
$82/A8AE 4C 06 A9 JMP $A906 [$82:A906] A:0002 X:074D Y:01D0 P:envmxdizcto no ops. In other words, change
82A8AC: F0
82A8AD: 03to
82A8AC: EA
82A8AD: EAExpressing this as a PAR code, it looks like
82A8ACEA
82A8ADEASee a demo of the change
It's a bit more fun this way. Enjoy
📅January 30th, 2022
On WDC 65816, NMI isn't a "real" instruction.
It's a directive ("non-maskable interrupt") typical 65816 assemblers understand.
You use the directive like
NMI MyHandlerwhere MyHandler is a label in the source code.
I had trouble finding this information written anywhere plainly, so I'm writing this in case you or someone else is in the same position as me where you need to know.
In response to NMI, the assembler doesn't directly emit any opcodes. What it will do for SNES, anyway, is
- After assembly, look at the object code address of MyHandler.
- The short, 16-bit address. Why? Because interrupts have to be in bank 0.
- Write the address to 0x7FEA or 0xFFEA, depending on whether it's LoROM or HiROM.
- The rule is that the vectors live in the last page of the first ROM bank, so that's in 0x7FEA for LoROM or 0xFFEA for HiROM.
Fun fact: in Geiger, you can't set a breakpoint to code inside an NMI. Well, you can try, but it won't hit. If you want to see control flow through an NMI, you can use the Logging-CPU feature.
After you assemble and load your program, and execute to something that entails an interrupt, your interrupt handler will get called automagically.
The choice of "what raises NMI" is up to the computer manufacturer. On SNES, the NMI vector is called when VBlank begins. That's just how it is. So sometimes NMI and VBlank get talked about interchangeably on that platform.
And I wish I had known to don't get hardware and software interrupts confused. NMI is different from BRK and COP. Those are software interrupts. They have an instruction, they launch from an opcode. NMI is a hardware interrupt.
For hardware interrupts, the K (program bank reg) gets automatically pushed, then the 16-bit PC is pushed, then the P (processor flags reg) is pushed, then there's this automatic transfer of control to the interrupt handler. You drop everything you're doing and go right to the handler. At least the CPU has the decency to push the execution state beforehand, I guess.
One detail- in emulation mode, the program bank reg does not get pushed. So you probably want to NOT be executing code in a nonzero bank in emulation mode if there's a hardware interrupt, because you don't know where to return to when the interrupt handler is done.
For NMI, the whole thing is no you can't disable it with a processor flag (that is, 'i') so forget trying to disable them either. And since it's a hardware interrupt, it's set up by special vector not by an instruction like BRK or COP. For those software interrupts, you can predict when they'll happen or make it so they're never happen since you know where there's a BRK or COP in your code. Hardware interrupts are different- you can't decide when they occur like that. The condition that raises them is fixed. Fortunately I guess, they're fixed based on something useful like vertical blank. And fair enough, since there are lots of things that are only safe to do during vertical blank.
I haven't had to write code that chases scanlines. I hope you don't either, although it might happen to everyone at some point.
A lot of the SNES reference material I used emphasize 65816 which is great for a while. But you get to a point in debugging SNES where it's not enough to only know things about the CPU. Eventually you will see things in the debugger you can't explain. Since there's more to a computer than just the CPU.
📅April 6th, 2021
J. R. R. Tolkien's Lord of the Rings for Super Nintendo shipped with a bug as you get toward the later parts of the game.
Short version: use these Pro Action Replay codes to un-glitch the late-game passwords.
81CBF10C
81A3900C
81A35C0CLonger explanation below.
If you're in Moria past the entrance and the first part and request a password, the game will give you one. However, if you write down and try to use that same password later, the game won't accept it.
This is especially troublesome because
a) it's in the most tedious part of the game, a part you wouldn't ever want to re-do, and
b) even if you back-track to the Moria entrance, it won't go back to giving you valid passwords. The game's password system is basically cursed.
I investigated to understand this more. First, the password validation converts this character into a number.
The exact way it does this is described in an earlier post. So for here, L is 9, M would be 10, and so on.
Starting from there, I found out more by
- typing a numerical garbage password like "023741" into the first six characters
- taking memory dump of RAM
- running a relative searcher on the memory dump, looking for a pattern like the one above
- found one result. This was lucky in a bunch of ways. It was lucky how the number was indeed stored contiguously in RAM, not immediately over-written, the password characters' values are sequential (e.g., the value of password character '1' numerically comes right before '2') and that I had picked a unique enough number
- Used that to get the RAM address of the character boxed in red above
- Set a break-on-read of that RAM address in the debugger
- Breakpoint hit when you press the button for password confirm. This also, was a bit lucky. The game only read the password back for initial graphics or when you hit 'confirm'. No reading it back continuously, no noisy breakpoints.
- Stepped through in debugger to see what it did with the password character. When it copied the password character, set break-on-read of that too. This led to un-tangling the password characters from what I called the AreaNumbers below. I saved the code and marked it up with comments and labels.
Password validation calls this function
// Function: ReadPasswordLocationCode()
// Precondition: location code is stored at $81:039C
// Postcondition: result stored in 801CCB, 801CCD, 801CC9.
// The result is what I'm calling an "AreaNumber"
// plus positional information about
// where in the world to load the player.
//
// Early-game AreaNumbers are high-numbered.
// Late-game ones are low.
// Examples:
// Crossroads is 0x12A.
// Rivendell is 0x138.
// Moria Entrance is 0xEF.
// Moria 1 is 0x51.
// Moria 2 is 0x0C.
$81/CBEA B9 84 03 LDA $0384,y[$81:039C] ; Load location code. E.g., the password
; character 'M', which is 0xA
$81/CBED 29 1F 00 AND #$001F ; Ignore upper bits
$81/CBF0 C9 0A 00 CMP #$000A
$81/CBF3 90 02 BCC $02 [$CBF7] ; If the password character is equal or greater than
;'M' (0xA), fall through
; to LocationCodeTooHigh.
; Otherwise, goto LocationCodeOk.
LocationCodeTooHigh:
$81/CBF5 38 SEC
$81/CBF6 6B RTL ; Bail
LocationCodeOk:
$81/CBF7 85 90 STA $90 [$00:0090]
$81/CBF9 A5 90 LDA $90 [$00:0090]
$81/CBFB 0A ASL A
$81/CBFC AA TAX
// Write the output
$81/CBFD BF 18 CC 81 LDA $81CC18,x[$81:CC2A]
$81/CC01 8F CB 1C 80 STA $801CCB[$80:1CCB]
$81/CC05 BF 30 CC 81 LDA $81CC30,x[$81:CC42]
$81/CC09 8F CD 1C 80 STA $801CCD[$80:1CCD]
$81/CC0D BF 48 CC 81 LDA $81CC48,x[$81:CC5A]
$81/CC11 8F C9 1C 80 STA $801CC9[$80:1CC9]
$81/CC15 C8 INY
$81/CC16 18 CLC
$81/CC17 6B RTL It's pretty easy to see the problem. It validates your location code is too high if you specify 'M' or 'N', but those are codes the game gives you. It was clearly a mistake. Changing the line
$81/CBF0 C9 0A 00 CMP #$000Ato
$81/CBF0 C9 0C 00 CMP #$000Cwill fix it, allowing through AreaNumbers up to N (since a password character N = 11 = 0xB), the maximum the game will give you.
This unblocks the password validation code. But, if you were to patch the above change and try it, you'd see the screen fade but hang there forever spinning in a long loop and hard locked not loading the level. So we're not out of the woods yet.
Terminology
Crashed, halted- the game's computer stopped executing instructions
Hard lock- the game's computer is executing instructions, but it appears unresponsive to inputs e.g., the screen is black
Soft lock- the game displays graphics and appears responsive but can not be won
The hang happens because we get past the password-validation and into level-loading yet there's parts of the level loading code that block out AreaNumbers belonging to Moria.
We get here
// Function: AreaLoadStaging()
// Preconditions: Location codes have been written to 801CCB, 801CCD 801CC9
// Expected behavior: Sanitize out bad location codes (e.g., bad
// AreaNumbers) and call a common function AreaLoadHelper().
// AreaLoadHelper() is a common channel used during both password-based
// loading and normal level loading as you move from one place to another
// in the game.
$81/A377 E2 30 SEP #$30
$81/A379 AF 0E 1D 80 LDA $801D0E
$81/A37D CF 72 03 80 CMP $800372
$81/A381 F0 76 BEQ $76
$81/A383 AF 72 03 80 LDA $800372
$81/A387 30 70 BMI $70
$81/A389 C2 20 REP #$20
$81/A38B AF C5 1C 80 LDA $801CC5 ; Load the area number.
$81/A38F C9 54 00 CMP #$0054
$81/A392 B0 52 BCS $52 [$A3E6] ; If area number < 54, fall through to
; InvalidAreaNumber_TooLow.
; Otherwise, goto ValidAreaNumber.
InvalidAreaNumber_TooLow:
$81/A394 E2 20 SEP #$20
$81/A396 AF 0E 1D 80 LDA $801D0E
$81/A39A C9 04 CMP #$04
$81/A39C D0 0E BNE $0E
$81/A3AC E2 20 SEP #$20
$81/A3AE A9 00 LDA #$00
$81/A3B0 48 PHA
$81/A3B1 AF 72 03 80 LDA $800372
$81/A3B5 48 PHA
$81/A3B6 F4 06 00 PEA $0006
$81/A3B9 22 02 80 81 JSL $818002
$81/A3BD 85 34 STA $34 ; Fall through into BadLoop
BadLoop:
$81/A3BF A9 00 LDA #$00
$81/A3C1 48 PHA
$81/A3C2 AF 72 03 80 LDA $800372
$81/A3C6 48 PHA
$81/A3C7 F4 06 00 PEA $0006
$81/A3CA 22 02 80 81 JSL $818002
$81/A3CE C5 34 CMP $34
$81/A3D0 F0 ED BEQ $ED
// This hangs forever :(
ValidAreaIndex:
$81/A3E6 E2 20 SEP #$20
$81/A3E8 A9 00 LDA #$00
//... clipped for brevityThis code snippet makes reference to another function I'm calling AreaLoadHelper. I'm not posting the code to AreaLoadHelper because it's veering a bit off topic. If you want to see the code for that, it's here. Look for 'Function: AreaLoadHelper() - 801D0D'.
Looking through, it's possible they originally intended for bad location codes to do something more elegant than a hang in this function (early out?). Or perhaps not, if they were sure this code wasn't reachable.
Anyway, changing
$81/A38F C9 54 00 CMP #$0054to
$81/A38F C9 0C 00 CMP #$000C fixes it here. The AreaNumbers for the last two levels are 0051 and 000C, so 0C covers it. The fact that it's the same number as patched above is really a coincidence.
If you were to apply this change and run the game, you would still see the same symptom as before where the screen would fade to black yet no level would get loaded. This is because it gets further in the level-loading code before getting stuck again. It was a very loose spin. I had an unpleasant debugging experience. That's because if you break in the debugger while it's hanging, you're too late. The root cause of the hang was here
// Function: CallAreaLoadHelperArg4 ($81:A33A)
// Preconditions: An AreaNumber is passed in through address $80:1CC5.
// Expected result: Validate the AreaNumber.
// If valid, push the argument '4' onto the stack and then call AreaLoadHelper(),
// a common code path shared between password-loading usual traversal
// through the game world.
$81/A33A E2 30 SEP #$30
$81/A33C AF 0E 1D 80 LDA $801D0E
$81/A340 CF 72 03 80 CMP $800372
$81/A344 F0 2E BEQ $2E
$81/A346 AF 72 03 80 LDA $800372
$81/A34A 30 28 BMI $28
$81/A34C C2 20 REP #$20
$81/A34E AF C3 1C 80 LDA $801CC3
$81/A352 C9 EF 00 CMP #$00EF
$81/A355 F0 09 BEQ $09
$81/A357 AF C5 1C 80 LDA $801CC5
$81/A35B C9 54 00 CMP #$0054 ; Load AreaNumber
$81/A35E 90 14 BCC $14 [$A374] ; If too low, goto InvalidLocation.
; If okay, fall through to ValidAreaNumber
ValidAreaNumber:
$81/A360 E2 20 SEP #$20
$81/A362 A9 00 LDA #$00
$81/A364 48 PHA
$81/A365 AF 72 03 80 LDA $800372
$81/A369 48 PHA
$81/A36A F4 00 01 PEA $0100
$81/A36D F4 04 00 PEA $0004 ; Push args
$81/A370 22 02 80 81 JSL $818002[$81:8002] ; Call AreaLoadHelper()
InvalidLocation:
$81/A374 C2 30 REP #$30
$81/A376 6B RTL Another place where the validation is on the wrong bounds.
So, change
$81/A35B C9 54 00 CMP #$0054 to
$81/A35B C9 0C 00 CMP #$000Callowing through both within-Moria area numbers, it works.
It is kind of good password-resuming the last two areas was something superficial like this, and not a deeper problem like a huge swath of level loading being actually not implemented. It turns out, the odds a "not implemented" is low anyway, since that part was written in a reasonable way- i.e., if you can visit an area, you can password-resume to it. They share the same code.
As for the fix since the total amount of changes is small, you could use a ROM patch, but it's even easier as a cheat code like a Pro Action Replay code. Expressing the above changes as SNES Pro Action Replay the codes are
81CBF10C
81A3900C
81A35C0CThese are value changes to ROM code (it is not self modified), so if you're applying cheats in an emulator you don't need to re-start the game to apply them.
Here is a demo of the codes in action
I was gonna post this to GameFaqs but they have this
oh well.
Anyway, you can use the cheat codes in a Pro Action Replay device for Super Nintendo, or any mainstream emulator (tested ZSNES, Snes9x) to unblock the game. Enjoy
📅March 31st, 2021
This is an explanation of the formats of the password used in the game. I found this information by trying different passwords and seeing what is accepted by the game and what the effects were. Since this process didn't involve a debugger it could have been done on the console, but using an emulator sped this up a lot.
This game has a hugely long password (48 characters.)
Each alphanumeric character is one of
.BCDFGHJKLMNPQRSTVWXYZ0123456789That's a '.', the letters of the alphabet with no vowels plus the numbers 0 through 9. This gives 32 choices in total.
The general layout of the password is: (where '.' represents an alphanumeric character)
Samwise Merry Frodo Pippin
[ ][ ] [ ][ ]
. . . . . . . . . . . .
Legolas Aragorn Gimli Gandalf
[ ][ ] [ ][ ]
. . . . . . . . . . . .
Spawn location keys Checksum
[ ][ and events ][ ]
. . . . . . . . . . . .
Inventory
[ ]
. . . . . . . . . . . .
As shown above there's
- 3 characters for each of the 8 people in the fellowship (Boromir isn't joinable)
- 1 character for your spawn location
- 8 characters representing keys and events
- 3 characters for checksum
- and a 12-character inventory code at the bottom labeled 'INVENTORY CODE' in the password input screen.
Following goes into more detail for each of these.
Password characters
The alphanumeric password is a convenience (lol) for the user. Internally the game maps each character in a password to a number.
The mapping is this
Character | Value
------------------
. | 0
B | 1
C | 2
D | 3
F | 4
G | 5
H | 6
J | 7
K | 8
L | 9
M | 10
N | 11
P | 12
Q | 13
R | 14
S | 15
T | 16
V | 17
W | 18
X | 19
Y | 20
Z | 21
0 | 22
1 | 23
2 | 24
3 | 25
4 | 26
5 | 27
6 | 28
7 | 29
8 | 30
9 | 31 In the sections that follow, these numerical representations of password characters get used and there is math done on them.
People in the fellowship
For each joinable person in the fellowship there's a three-character code that encodes their level and equipment.
Firstly, if the three character code is all '.' (value zeroes), that character is not in your party. Otherwise yes they are in your party.
The way in which the codes determine equipment is a bit convoluted and broken. The reason I say that is there are some
passwords that are accepted by the game but will either crash the game or cause corrruption while you're playing. The charts and things below describe passwords which are accepted and also don't crash or corrupt the game.
You can find situations (e.g., what if Code3, described below, is less than 16?) where the password gets accepted, the level gets loaded and things appear okay but corruption happens when you go into the menu for example. I reverse engineered what level/items you get in those cases too, and they're accounted for in the source code of my password editor. I'm leaving them out of this document so that these formulas stay neat and concise as they're specified, because those don't follow the rules listed below. If you want you can see source code here for more info on them
So anyway, each person in the fellowship gets a three-character code in the password. Call the three characters in the code
Code1, Code2, and Code3 in order.
For example if the password contained 'B89' then Code1=1, Code2=30, Code3=31 referring to the chart above. Yes, each of
Code1, Code2 and Code3 is a number between 0 and 31 inclusive.
Level is decided by the following:
if (Code1 < 10)
Level = (Code2 mod 8) * 20 + Code1
else
Level = (Code2 mod 8) * 20 + (Code1 mod 16) + 10The 'mod' operator here is modulus. I.e., A mod B is the remainder when A is divided by B.
Armor is decided by the following:
PW char 2 | Code2 | Armor
--------------------------------------------------------------
. through F | 0 through 4 | If Code3 is even, Cloth Cloak.
| | If Code3 is odd, Plate Mail.
--------------------------------------------------------------
. through F | 0 through 4 | If Code3 is even, Cloth Cloak.
| | If Code3 is odd, Plate Mail.
--------------------------------------------------------------
K through P | 8 through 12 | If Code3 is even, Padded Armor.
| | If Code3 is odd, Mithril Armor
--------------------------------------------------------------
T through Y | 16 through 20 | Leather Armor
--------------------------------------------------------------
2 through 6 | 24 through 28 Chain Mail
Weapons are decided by the following:
PW char 3| Code3 | Weapon
----------------------------
T | 16 | Old Dagger
V | 17 | Old Dagger
W | 18 | Dagger
X | 19 | Dagger
Y | 20 | Barrow Dagger
Z | 21 | Barrow Dagger
0 | 22 | Troll Dagger
1 | 23 | Troll Dagger
2 | 24 | Elvish Dagger
3 | 25 | Elvish Dagger
4 | 26 | Sting
5 | 27 | Sting
6 | 28 | Light Sword
7 | 29 | Light Sword
8 | 30 | Sword
9 | 31 | Sword The password encoding for level, weapon and armor works the same for each of the 8 joinable characters.
Fun fact: if you enter an only-partially-valid password that includes some configuration for a character (e.g., the string is not all '.'), it permanently adds the character to your party until SNES reset. Even if the password is rejected. This leads to a well-known cheesy trick where you can enter a bad password, press start and hear the "invalid password" noise, then delete it and start the game with all the Fellowship unlocked.
Spawn Location
This is the place in the game world your party will be in after the password gets accepted.
It's a 1-character code.
PW char| Code | Location
-------|------|------------
. | 0 | Hobbiton
B | 1 | Brandywine Bridge
C | 2 | Farmer Maggot
D | 3 | Ferry
F | 4 | Crickhollow
G | 5 | Tom Bombadil's House
H | 6 | Barrow Downs Stones
J | 7 | Crossroads
K | 8 | Rivendell
L | 9 | Moria entrance
M | 10 | Moria 1 (glitched)
N | 11 | Moria 2 (glitched) For the last two Moria locations, the game will include those location codes in the passwords it provides to you when you're in Moria.
However, it won't accept the passwords the next time you start the game 🙁 (Update: unless you have my bug fix described in this post)
Might want to keep a map of Moria, you definitely don't want to do it more than once if you can help it
Keys and events
These control the state of various unlockable doors and questlines. I haven't investigated which bits control what because it wasn't important to what I was trying to do.
Checksum
The checksum exists to stop you from trying random passwords and cheating. It's a way of making sure the only passwords accepted are ones the game has actually given to you, not ones you randomly made up yourself.
However, the checksum is pretty easy to understand if you look at the various passwords it gives you. For example, you'll see that leveling up or changing equipment only changes the first character. And using something in your inventory only changes the third character. And, you know how the password characters translate to character codes and there are 32 of them, and modulus kinds of operations are common and inexpensive for computing checksums.
The first character is the 'party checksum':
partySum = the sum of the character codes of the first two lines of the password
checksumCode = remainder when partySum is divided by 32. (For example, if partySum is 33, the checksumCode is 1.)
The second character is the 'event checksum':
eventSum = the sum of the character codes in the "spawn location" and "keys and events" part of the password
checksumCode = remainder when eventSum is divided by 32
The third character is the 'inventory checksum':
inventorySum = the sum of the character codes in the "inventory" part of the password
checksumCode = remainder when inventorySum is divided by 32
This gives you the first, second and third characters of the checksum in order.
I think they put the checksum in the middle of the password to obfuscate it a little bit.
If you're trying to troubleshoot, know that valid checksum doesn't necessarily mean the password will be accepted. The game sometimes rejects passwords for reasons other than invalid checksum. For example, if you specify an invalid location code like 'Z'.
Inventory
These character codes store your inventory state pretty compactly.
Each item corresponds to 1 bit within a byte. Not all the bits are used, which is why a full inventory's password code looks like "9S9S9S 9S9S9S" rather than all 9s (all 9s means all bits set).
There are 12 inventory code characters in all, which I'm calling code 0 through 11.
For readability the bit is written as a hexadecimal flag.
Item |Code #| Bit
--------------------------------
Tomb Key | 0 | 0x1
Moria Key | 0 | 0x2
Red Gateway Gem | 0 | 0x4
Elvish Book | 0 | 0x8
Magic Rock | 0 | 0x10
Bottle | 1 | 0x1
Lost Amulet | 1 | 0x2
Maggot Note | 1 | 0x4
Scroll Of Floi | 1 | 0x8
Gate Key | 2 | 0x1
Moria Key | 2 | 0x2
Yellow Gateway Gem | 2 | 0x4
Book Of The Ages | 2 | 0x8
Gold Piece | 2 | 0x10
Jug Of Honey | 3 | 0x1
Lost Amulet | 3 | 0x2
Old Willow Note | 3 | 0x4
Scroll Of Oin | 3 | 0x8
Tomb Key | 4 | 0x1
Moria Key | 4 | 0x2
Gateway Keystone | 4 | 0x4
Book Of Mazarbul | 4 | 0x8
Gold Pieces | 4 | 0x10
Eye Glasses | 5 | 0x1
Lost Amulet | 5 | 0x2
Note From Gandalf | 5 | 0x4
Color Scoll | 5 | 0x8 Item |Code #| Bit
---------------------------------
Tomb Key | 6 | 0x1
Moria Key | 6 | 0x2
Green Gateway Gem | 6 | 0x4
Bilbo Diary | 6 | 0x8
Gold Pieces | 6 | 0x10
Healing Moss | 7 | 0x1
Lost Amulet | 7 | 0x2
Letter To Elrond | 7 | 0x4
Keystone Scroll | 7 | 0x8
Tomb Key | 8 | 0x1
Boat Oar | 8 | 0x2
Purple Gateway Gem | 8 | 0x4
Jeweled Ring | 8 | 0x8
Gold Pieces | 8 | 0x10
Athelas Major | 9 | 0x1
Lost Amulet | 9 | 0x2
Horn Of Boromir | 9 | 0x4
Long Bow | 9 | 0x8
Key To Bree | 10 | 0x1
Healing Mushroom | 10 | 0x2
Violet Gateway Gem | 10 | 0x4
The Ring | 10 | 0x8
Athelas Minor | 10 | 0x10
Healing Fruit | 11 | 0x1
Lost Amulet | 11 | 0x2
Magic Fern | 11 | 0x4
Orb of Drexle | 11 | 0x8 The inventory codes come from bitwise OR-ing the corresponding bits together for each inventory item you have.
For example, suppose you have the first tomb key and the red gateway gem. This is bit '0x1' and '0x4'. When you bitwise-OR these, you get '5'. Code 5 corresponds to password code 'G', from the chart all the way at the top. So if those two are the only items you have, your inventory code in the password is 'G….. ……'.
For another example, suppose all you have is the first tomb key and the Orb of Drexle. This is bit '0x1' of the first code, and '0x8' of the last. So if those were the only two items you have, your inventory code in the password is 'B….. …..K'.
There's one special case- although there's an inventory bit allocated to the One Ring, the ring is always in your inventory regardless of whether it's encoded in the password or not.
Links
Hope you found this helpful
All this information is used in a password editor I made. That is here
https://github.com/clandrew/lotrpwcheck/
To view this post in text form, it's here
https://raw.githubusercontent.com/clandrew/lotrpwcheck/master/Format.txt
This post is following up from this one where I posted the editor, where someone asked about the information that the editor uses