Saharah When?

Motivation

I had an interesting idea for a service that would tell you outside of the game when Saharah or Crazy Redd are going to visit town. Is this something that can be determined just by knowing what seed the game uses, or does it depend on user input or the time that they log in? Let’s find out.

Starting with Strings

Doing a similar string search as our last project, we quickly find the line that Copper tells you with the date in it; going up the stack even higher, we see the date string isolated in memory at 0x81297f00. Breaking on that, we see that it’s copied from 0x812f94d0.

Darn, it’s being used while we’re still at Copper’s prompt, so let’s just go up the stack until we find when “22nd” is written there.

It’s not written at the time we call 0x8056acdc, so we can step into there and see when it’s being called. Just before I did that, though, I decided to peep at the call stack and see if any of the registers scream “July 22nd” in one format or another, but no such shortcut exists here.

Let’s step through, then. It’s being copied at 0x803eee7c from a string of 20 counts: 20th21st22nd23rd24th25th26th27th. The offset into this string is 8 as we expect, coming from r30.

Let’s just try and take a shortcut here. Going up one call in the stack, we see r6 with a value of 0x663, which looks like it may be some form of time representation. Let’s fiddle with it a bit and bump it up one and see what happens.

So it appears to operate on granularity of days, but… 0x664 is entirely too high to be “day within the year”. Idea: perhaps it’s an offset from when the save file was created? 1636 days before July 23rd, 2011 was January 29, 2007. It’s conceivable; maybe I’ll try on a fresh save file later. For now, I think we have enough to go on; let’s figure out where this value comes from.

First call that appears to throw it on the stack is 0x803eefc8. In there, we see this instruction that loads 0x663 into r5:

0x803ef000    addi r5, r4, 1613

So there seems to be some hard offset that we add 22 onto. I wonder if we’re not actually operating on the level of dates yet and this is merely a string table index computation, so by bumping it to 0x664 we technically didn’t change the date computation, just bumped the string offset. Just for the heck of it, lets add more than 32; that should bump us past the numeric strings.

Whoops, looks like we’re still dealing with string offsets. An amusing result, but in any case, our next step is to trace where r4 comes from. Actually, I’m already having nightmares of having to step through code that handles leap years. Let’s just step up the stack and see if we can manipulate any of these registers/stack values to bump the date.

Date Get

While stepping around this code, I got excited after spotting 0x81286400 because I recognized 86400 as the number of seconds in a day, but then… I realized this is in hexadecimal, so it represents a totally different value. Anyway, I spotted that a value of 0x716 gets loaded from a seemingly fixed address 0x81286960. Here’s a hunch… 0x7 = July. 0x16 = 22. Let’s try and tweak it to August 7 by setting it to 0x0807!

Now we’re getting somewhere! Okay, so now let’s see… does this value get written to when we talk to Copper or when we load the save file? A simple breakpoint reveals… no writes while we’re talking to Copper, so it must have been written earlier. I bet it happens when you “log in”, since it’d definitely have to evaluate how much time has passed and bump up the visit date if you missed the previous one. So let’s get out and jump back in.

Okay, I’ve hit a point here where I’m seeing it compare that value to others, but… I don’t remember what date I have the emulator set to. Need to restart one more time…

Okay, I definitely saw some 0x0714 value there which would represent July 20th. Stepping back in, we can see it being compared with 0x0717. This seems to be one day after the next scheduled visit. Just as a wild guess, this is perhaps checking if the last scheduled Saharah visit already happened, since that’s the day after.

At this point, the best course of action would probably be to change the date to after Saharah’s “future” visit and see what we do upon entry. Restarting the emulator, we’re on the 28th of July, so this should do fine. Let’s save state and jump in.

Okay, just tracking as I step through:

1. 0x8039bd3c: r11 gets set to Saharah’s old scheduled date 0x0716.
2. 0x8039bd48: r3 and r4 have 0x14 and 0x7 respectively. This is perhaps our last play date?
3. 0x8039bd4c: our last play date is compared with 0x0717, which is the day after Saharah’s previously scheduled visit.
4. At 0x8039bbe0, a value of 0x4f is being compared with a bunch of others. 0x4f is 79, so let’s follow where this goes.
5. For a value of 79, this function returns 5. Can we guess that this is maybe the visit interval?

Just as an impatient check, let’s jump ahead and see what date ultimately gets computed for her next visit: 0x71f which puts her at… the 31st of July. Hm, it doesn’t seem immediately clear how the 5 is involved, 5 days after the 22nd would be the 27th. Alright, impatience didn’t pay off, as usual, let’s jump back.

I got to a point where I could just keep reloading and it would generate the same “next” date 3 times in a row, so chances are there’s some determinism to this. Let’s litter some breakpoints and try to catch the date generation in the act.

Who’s On The Way?

Okay, I had to delete a bit of stuff here, because there’s something I missed: that same memory location that stores the date is used regardless of which visitor is coming, and there’s another field that seems to determine who’s coming, just before the date at 0x81286954 which is subtracted with 74 at 0x8056adbc.

Following these values in memory a little more, we come upon a little loop at 0x8039ed30 which seems to copy an array of these integers in the following order: 0x4e, 0x4c, 0x4b, 0x4a, 0x4f, 0x4d. Perhaps this is a cyclic order of events that occur in the town? Later, we check an index that’s currently 4 (which lines up with the fact that our value is 0x4f in memory).

Again, I had to delete a bunch of stuff that led nowhere because I eventually came to a point where I performed the following steps:

1. Load the 2011 save file with the date set to the 22nd.
2. Copper says that Wendell is visiting on the 23rd.
3. Change the date to the 24th.
4. Copper says that Katrina is visiting on the 26th.

Then I restored the save file back to 2011 state and did:

1. Load the 2011 save file with the date set to the 24th.
2. Copper says that Gracie is coming on the 26th.

So the current date seems to matter here for determining who’s next and when.

Determinism in Question

So this immediately threw out the suggestion that the order was fixed or cyclic and it seems to just be randomly seeded at the time that you check in since the last one. However, this is actually kind of a nicer result, because it means that if the seed doesn’t change too quickly, we can predict when you should turn the game on to schedule the visitor that you’re interested in.

My preliminary findings there were promising as well; setting a memory breakpoint on our “next visit date” at 0x81286960 and following it up, I spotted a certain value being used to compute the arrival date of the next visitor and after a series of following that seemed to be fixed as 9.

It took a fair bit of tracking down to figure out where it came from, but ultimately: it’s the hour of the day. It’s possible a more granular date value gets used as well, but given our previous results where we managed to produce the same visitor and date 3 times in a row, I’d say the hour is probably the fastest thing that changes the seed.

Planting/Generating a Seed

So, let’s step back into the bit of code that I started tracking for the computation of “next visit date” and see if that also has a determination for who the next visitor will be. This starts around 0x8039bd38. I moved the emulator’s time up to the modern world just so that it’s easier to differentiate old from new data, and here, we see all manner of date values on the stack: previous visit, current year, year of last visit, etc.

In this run, after a few instructions, we have the following registers and values of interest:

These get pushed around on the stack and then it gets the value of the last visitor into r0, which in this case is 0x4e (78). We call the same helper we saw before that returned 5. I restarted the emulation and stepped through again, just because I thought a breakpoint on the above values would be useful. This time we return 0x17 in r3.

At this point, we jump into a function with three different values being compared:

r3: 0x14041509
r4: 0x0b071000
r5: 0x0b071217

These seem constructed as: YYMMDDHH and it’s not immediately clear what the second two dates are. Perhaps one is last visitor visit date and one is last login date, but it’s difficult to say which is which. Anyway, current date gets compared against r4 and r5 and jumps to 0x8039b2f0 when we realize we’ve jumped ahead in time, which just returns 0. Perhaps this is a boolean expiration check.

The outside call checks the result, and jumps to 0x8039bde0 due to the time skip-ahead. A yet-mysterious value gets read into r23 from a hard-coded address at 0x81266420 that ultimately resolves to 0xf08d. This value is actually present in the save file immediately after the name of the character and town: this may be our magic seed.

Then this, starting at instruction 0x8039be00:

lbz r5, 0x6125 (r25) # M: 0x4
addi r7, r23, 1 # Magic + 1: 0xf08e
lhz r0, 0x6126 (r25) # Y: 0x7e4
li r3, 11 # Hard coded at 11
lbz r6, 0x6123 (r25) # D: 0x15
li r4, 164 # Hard coded at 164
sub r0, r0, r5 # r0 = Y - M
lbz r5, 0x6122 (r25) # H: 0x9
add r0, r0, r6 # r0 = (Y - M) + D
add r23, r0, r5 # r23 = (Y - M) + D + H
add r23, r7, r23 # r23 = Magic + 1 + (Y - M) + D + H
bl 0x8039b464 # Jump somewhere else?

And we currently are left with a value of 0xf88c. Stepping into that last function call… there’s at least a 77% chance we’re dealing with a random number generator.

Setting a Target

Assembly analysis beyond this point probably doesn’t make a great deal of sense. Ultimately, it seems like it’s some kind of random number generator, so it depends entirely on the seed it’s given and we can’t do much without figuring out what seed we’re using.

So here are the next steps for us:

1. Figure out how the generated number is used to pick the next visitor and visit date.
2. Reimplement that generation in a separate program.
3. Collect enough data points that we can reverse engineer the seed based on which visitors/dates are generated.
4. This’ll probably a weeks long process, since the seed is 16-bit, which is basically the maximum “information” or “entropy” (I never know if I’m using that word right) of our random number generator, no matter how complicated the code is.

Time cut goes here…

Oh, hello there. You missed a whole lot. I stepped through a bunch of functions, annotated a ton of useless assembly, and can say with confidence now: it’s not much of a random number generator at all, more like an index generator. Here’s where the seed usage actually starts, at 0x8039be44:

lis r4, 0x8126
lis r5, 0x8065
addi r6, r4, 25600 # r6 = 0x81266400
lis r4, 0x8065
mr r29, r3 # r29 = 0xb1b
addi r30, r5, 8152 # r30 = 0x80651fd8
addis r27, r6, 2 # r27 = 0x81286400
addi r31, r4, 8140 # r31 = 0x80651fcc
lwz r4, 0 (r30) # r4 = 6
lbz r0, 0x554 (r28) # r0 = 0x4e
divw r3, r23, r4 # r3 = 0xf88c (seed) / 6 = 0x296c
mullw r3, r3, r4 = 0x296c * 6 = 0xf888 # Round to multiple of 6?
sub r3, r23, r3 # r3 = 0xf88c - 0xf888 = 4 # Is this modulus?
addi r23, r23, 1 # Add one to the seed
rlwinm r3, r3, 1, 0, 30 # r3 = r3 * 2 = 8
lhax r26, r31, r3 # Loads the next visitor code = 0x4f!
cmpw r26, r0 # Compares with previous visitor code = 0x4e!
beq+ 0x8039be64 # Jump to the lwz r4 above.
bl 0x803a2140

I deleted yet another insane wall of assembly here because I realized that now that we know it’s not fully deterministic regardless of log-in time, we don’t particularly care about the date that gets generated, we just want to be able to schedule the visitor of our choosing. Let’s re-implement the seed assembly two blocks above in C/C++.

const unsigned int accountSeed = 0xf08d;
const unsigned int hour = 9;
const unsigned int day = 21;
const unsigned int month = 4;
const unsigned int year = 2020;
const unsigned int dateSeed = (year - month) + day + hour;
unsigned int finalSeed = (accountSeed + 1) + dateSeed;
cout << hex << finalSeed << endl;

Accuracy confirmed so far, as that prints 0xf88c. Now, let’s proceed to reimplementing the actual visitor selection (simplified the modulus a bit).

Note: I’m revising this blog-post years later and I realized I may have reimplemented it slightly incorrectly below, since in the original loop we weren’t doing the “add one to the seed” step in the assembly above. That has now been corrected!

const unsigned int lastVisitor = 0x4e;
constexpr unsigned int visitorCount = 6;
const unsigned int visitors[visitorCount] =
{
    0x4e,
    0x4c,
    0x4b,
    0x4a,
    0x4f,
    0x4d
};

int nextVisitor;
do
{
    int nextVisitorIndex = (finalSeed % visitorCount);
    ++finalSeed; // In case we have a conflict, try the next visitor
    nextVisitor = visitors[nextVisitorIndex];
} while (nextVisitor == lastVisitor);
cout << hex << nextVisitor << endl;

Which does indeed print 0x4f like the game generates. So basically what this reveals at this point is that because + hour + day is the last part of the seed generation, you have an opportunity every 6 hours to get the visitor you want to come (assuming they didn’t visit last time).

Now there’s an important step in executing this that I haven’t gone over yet: which of the 0x4f, 0x4e, etc. corresponds to which visitor? This should be pretty easy to fix in memory and ask Copper, so let’s do it.

Before we break apart the generation and figure out how to rig it, let’s confirm our understanding by fixing the hour value in such a way that it attempts to generate 0x4e again, fails, and move one up to 0x4c. Since our generated visitor at 9 a.m. was Saharah, we merely have to dial back 4 hours to 5 a.m.

Stepping with the debugger, we get a final seed of 0xf888, which, modulo 6 is 0, and so the compare at 0x8039be84 succeeds this time, and the generation is done again with a seed of 0xf889 and we generate 0xfc this time. Easy peasy!

Wall of Text: The Finale

Now, the difficulty with determining the order at this point is just that there’s a bit of ambiguity. Without accessing the memory yourself or remembering who the previous visitor was, it’s difficult to distinguish between two cases:

1. Generated Crazy Redd, but he was the last visitor, so we rerolled to Wendell.
2. Generated Wendell on the first try.

However, there’s a fairly easy way to work around this which will help you determine what your save file’s seed is modulo 6. Here’s an example:

1. Allow a visitor to come to your town, noting down who it was.
2. Enter town the day after they visited, and note down the hour and day of the month; later in the evening will make the next steps easier. Let’s say it’s 9 p.m. on the 21st of April. Ask Copper again when the next visitor will be arriving and note down who it is.
3. If the next visitor that’s scheduled to arrive is not immediately after the previous visitor in the table above (note that the first entry of Nothing is considered after Katrina for this purpose), skip to step 6.
4. If the next visitor is immediately after the previous visitor in the table above, then we have one of two possibilities: either it tried to generate that same visitor again and bumped up to the one after it, or it cleanly generated with no conflict. We resolve which one of these it is by entering town the day after that second visitor visits, say, on April 24th, choosing an hour such that the sum of the hour and the day of the month is the same as it was in step 2. So in this case, step 2 was at 9 p.m. on the 21st, so 21 + 21 = 42; so if we’re entering on the 24th of April, we want to enter at hour 42 – 24 = 18 = 6 p.m.
5. Knowing what we do about the seed generation, the seed when it rolled last two visitors should be the exact same. So if the third visitor is the same as the first, we know that the second one attempted to roll that same first visitor, but bumped up due to the conflict, and then the third visitor cleanly generated the same as the first one. If the third visitor is one after the second, then we know the second visitor cleanly generated with no conflict, but the third attempted to re-roll that same one and got bumped ahead.
6. After we determine which case we fall under, we can work back to determine who the initially generated visitor was for day 2 (before conflicts, if any, were resolved), and denoting their index with Y, we compute: accountSeed = (6001 - Y - dateSeed)

The 6001 above is just a dummy base seed of 6000 to make sure we’re positive once we subtract our date seed without changing where we would land modulo 6, plus the 1 that gets added in the final seed computation. Therefore, we can simply plug that accountSeed in the above code, allowing us to compute which visitor will be generated if we log in at a given hour on a given day, given a certain previous visitor.

Before I fully confirm the above, however, I’m going to put it to the test with my town on my actual GameCube over the next few days and then I’ll write an easy web page that can compute your seed and when you should log in to get the visitor you want. Pretty pleased with the results so far, though!