News:

As a consequence of the forum being updated and repaired, the chatbox has been lost.
However, you can still come say hi on our Discord server!

Main Menu

Questions about Space Manager

Started by Daddy Poi's Oily Gorillas, 20, June, 2017, 07:39:05 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Daddy Poi's Oily Gorillas

I went through the space manager code... and I get that it is mostly a simple thing with a lot of code... but a small portion of it confuses me.

For those who don't know, here are details of the space manager functions.
Quote#pragma once
#import "includes.h"

class spacemanager
{
public:
    static int list_num;
    static int organizeList(int *list);
    static int mapSpace(int *list);
    static int findSpace(int *list, int size);
    static int confirmSpace(int *list, int index, int size);
    static int freeSpace(int *list, int pos, int size);
    static int claimSpace( int *list, int pos, int size);
};
list_num is the total number of entries in Atrius's free space table.
orgaizeList - pretty self-explanatory, but is where my question(s) are.
mapSpace will either load the free space table, or if there isn't one, scan for free space. (Based on MFT pointers that point before MFT address. And after those, will scan from end of ROM.) It scan backwards, though, so once there is a non-zero, the space for that section is known. (32-bit aligned size.)
findSpace is simple, looks for the first entry in the free space list that has enough size that is needed.
confirmSpace checks if the entire section has 00s or not. (Depending on a flag) (It may also check if the freeSpace being used is all in freeSpace, but that's probably pointless with the findSpace function.) - It is obvious that this helps reduce overwritting any hex editor related edits... but otherwise is not required to have.
freeSpace literally adds another entry of freeSpace. (Checks each of the freeSpace entries to see whether that space can be added to it, if not, it will be added as a separate entry.)
claimSpace is similar to freeSpace, except that it removes the freeSpace.



My question is with organizeList.
I get that it sorts the list from least to greatest size... but I don't get the next part:
Quoteif (pos!=i)
         {
              val=list[pos<<1];
              size=list[(pos<<1)+1];
              list[pos<<1]=list[i<<1];
              list[(pos<<1)+1]=list[(i<<1)+1];
              if (val==list[i<<1])
              { list[i<<1]=val|0x40000000; }
              else
              { list[i<<1]=val; }
              list[(i<<1)+1]=size;
         }
         if (list[i<<1]==list[(i-1)<<1])
         {
              list_num--;
              for (ii=i; ii<list_num; ii++)
              {
                   list[ii<<1]=list[(ii+1)<<1];
                   list[(ii<<1)+1]=list[((ii+1)<<1)+1];
              }
              list[list_num<<1]=0; list[(list_num<<1)+1]=0;
              i--;
         }
The bolded sections.... Do those ever happen? And if so how? Otherwise, is it free to remove without problems?
The top section is for switching entries (For the small to large sizes)
The bottom section looks like it removes an entry for when two addresses next to each other match.

And after this code is basically the stuff that frees the old free space table from the ROM and puts the updated free space table back into the ROM.



When doing this for the C# version, I think I'll try to make it a little simpler if I can... by removing confirmSpace, and also that the freeSpace table shouldn't "claim space" for itself. If table is going to be managed outside the ROM data. Maybe.)
Golden Sun Docs: Broken Seal - The Lost Age - Dark Dawn | Mario Sports Docs: Mario Golf & Mario Tennis | Misc. Docs
Refer to Yoshi's Lighthouse for any M&L hacking needs...

Sometimes I like to compare apples to oranges. (Figuratively) ... They are both fruits, but which one would you eat more? (If taken literally, I'd probably choose apples.)
Maybe it is over-analyzing, but it doesn't mean the information is useless.


The only GS Discord servers with significance are:
Golden Sun Hacking Community
GS Speedrunning
/r/Golden Sun
GS United Nations
Temple of Kraden

Can you believe how small the Golden Sun Community is?

2+2=5 Don't believe me? Those are rounded decimal numbers. Take that, flat earth theorists! :)

Luna_blade

Oof that is some tangled code.

I am not really sure what I am looking at here.
I would like to help out, but I am really too tired currently.
That first if is very puzzling.
"Hear the sounds and melodies
Of rilets flowing down
They're the verlasting songs
Whispering all the time
As a warning that behind some rocks
There's a rigid grap even
Oreads fear the tread"

Daddy Poi's Oily Gorillas

#2
First if? Don't try to understand it without seeing the rest of it: (From Atrius's Source code... C++ Space Manager code file.)

The code before it is about looking for an entry that is of a lower size. Whether one is found or not, depends on how that "if" statement is true or false.
If one is found... the code inside the if block shown in the first post basically swaps them. I'm not sure why there's an "|0x40000000" though...

[spoiler]#include "spacemanager.h"

int spacemanager::list_num;

int spacemanager::organizeList(int *list)
{
    int i, ii, pos, val, size;
    for (i=0; i<list_num-1; i++)
    {
         val=list[(i<<1)+1]; pos=i;
         for (ii=i+1; ii<list_num; ii++)
         {
              if (list[(ii<<1)+1]<val)
              {
                   pos=ii; val=list[(ii<<1)+1];
              }
         }
         if (pos!=i)
         {
              val=list[pos<<1];
              size=list[(pos<<1)+1];
              list[pos<<1]=list[i<<1];
              list[(pos<<1)+1]=list[(i<<1)+1];
              if (val==list[i<<1])
              { list[i<<1]=val|0x40000000; }
              else
              { list[i<<1]=val; }
              list[(i<<1)+1]=size;
         }
         if (list[i<<1]==list[(i-1)<<1])
         {
              list_num--;
              for (ii=i; ii<list_num; ii++)
              {
                   list[ii<<1]=list[(ii+1)<<1];
                   list[(ii<<1)+1]=list[((ii+1)<<1)+1];
              }
              list[list_num<<1]=0; list[(list_num<<1)+1]=0;
              i--;
         }
    }
    //return list_num;
    if ((LOAD_INT(FileTable())>>24)!=8)
    { return list_num; }
    if ((LOAD_INT(FileTable())&0x1FFFFFF)!=0)
    {
         int tlist[32768]; int tnum, tnum2; tnum=list_num;
         pos=LOAD_INT(FileTable());
         WRITE_INT(FileTable(), pos|0x70000000);
         tnum2=spacemanager::mapSpace(tlist); list_num=tnum;
         spacemanager::freeSpace(list, pos,(tnum2<<3)+4);
    }
    else
    { WRITE_INT(FileTable(), 0x7FFFFFFF); }
    pos=spacemanager::findSpace(list, (list_num<<3)+4);
    if (pos>0)
    {
         spacemanager::claimSpace(list, pos, (list_num<<3)+4);
         i=0;
         for (i=0; i<list_num; i++)
         {
              val=list[i<<1];
              WRITE_INT(pos+(i<<3),list[i<<1]);
              WRITE_INT(pos+(i<<3)+4,list[(i<<1)+1]);
         }
         WRITE_INT(pos+(list_num<<3),0x7FFFFFFF);
         WRITE_INT((FileTable()),pos);
         //WRITE_INT(0,0x12345678);
    }
    else
    {
         WRITE_INT(FileTable(),0x08000000);
    }
    return list_num;
}

int spacemanager::mapSpace(int *list)
{
    int pos, val, size;
    for (list_num=0; list_num<32768; list_num++)
    { list[list_num]=0; }
    list_num=0;
    pos=LOAD_INT(FileTable())&0x09FFFFFF;
    if ((pos&0x1FFFFFF)!=0x0)
    {
         val=LOAD_INT(pos+(list_num<<3));
         while (val!=0x7FFFFFFF)
         {
              list[list_num<<1]=val;
              list[(list_num<<1)+1]=LOAD_INT(pos+4+(list_num<<3)); list_num++;
              val=LOAD_INT(pos+(list_num<<3));
              if (val==0)
              { val=0x7FFFFFFF; }
         }
         list[list_num<<1]=0;
         list[(list_num<<1)+1]=0;
         return list_num;
    }
    val=0;
    do
    {
         if (val==1)
         { val++; continue; }
         pos=LOAD_INT(FileTable()+0x4+(val<<2))&0x1FFFFFF;
         if (pos>(FileTable()&0x1FFFFFF))
         {
              pos=FileSize();
         }
         size=0;
         do
         { size++; }
         while (LOAD_BYTE(pos-size)==0);
         size--;
         size=size&0xFFFFFFFC;
         pos-=size;
         if (pos+size==FileSize())
         {
              size+=(32<<20)-FileSize();
         }
         if (size>0)
         {
              list[list_num<<1]=pos|0x08000000;
              list[(list_num<<1)+1]=size;
              list_num++;
         }
         val++;
    }
    while (pos<=(FileTable()&0x1FFFFFF));
    spacemanager::organizeList(list);
    return list_num;
}

int spacemanager::findSpace(int*list, int size)
{
    //size=(size+3)&0xFFFFFFFC;
    int pos, i;
    do
    {
         pos=0;
         for (i=0; i<list_num; i++)
         {
              if (list[(i<<1)+1]>=size)
              {
                   if (spacemanager::confirmSpace(list,list[i<<1],int(size)))
                   {
                        pos=list[i<<1]; i=list_num;
                   }
                   else
                   {
                        pos=-1; i=list_num;
                   }
              }
         }
    }
    while (pos==-1);
    if (pos==0)
    { return pos; }
    return (pos&0x1FFFFFF)|0x08000000;
}
   
int spacemanager::confirmSpace(int *list, int pos, int size)
{
    //size=(size+3)&0xFFFFFFFC;
    int i, index; index=-1;
    for (i=0; i<list_num; i++)
    {
         if ((list[i<<1]&0x1FFFFFF)<=(pos&0x1FFFFFF))
         {
              if (((list[i<<1]+list[(i<<1)+1])&0x1FFFFFF)>=((pos+size)&0x1FFFFFF))
              {
                   index=i; i=list_num;
              }
         }
    }
    if (index<0)
    { return -list_num; }
    if ((list[index<<1]>>28)==1)
    { return list_num; }
    int length, ppos; ppos=pos;
    pos=list[index<<1];
    for (length=0; length<size+(ppos-list[index<<1]); length++)
    {
         if  (LOAD_BYTE(pos+length)!=0)
         {
              size=list[(index<<1)+1]; length--;
              list[(index<<1)+1]=length;
              pos+=size; length=0;
              do
              {
                   length++;
              }
              while (LOAD_BYTE(pos-length)==0);
              length--;
              pos-=length;
              list[list_num<<1]=pos|0x08000000;
              list[(list_num<<1)+1]=length;
              list_num++;
              spacemanager::organizeList(list);
              return -list_num;
         }
    }
    return list_num;
}

int spacemanager::freeSpace(int *list, int pos, int size)
{
    int i, ii, index, pos2, pos3; index=-1; pos2=pos+size;
    pos|=0x10000000;
    for (i=0; i<list_num; i++)
    {
         if ((list[i<<1]&0x1FFFFFF)>(pos&0x1FFFFFF))
         {
              if ((pos2&0x1FFFFFF)>=(list[i<<1]&0x1FFFFFF))
              {
                   pos=pos&0x09FFFFFF|(list[i<<1]&0xF6000000);
                   pos3=list[i<<1]+list[(i<<1)+1];
                   if ((pos3&0x1FFFFFF)>(pos2&0x1FFFFFF))
                   {
                       pos2=pos3;
                       size=(pos2&0x09FFFFFF)-(pos&0x09FFFFFF);
                   }
                   list_num-=1;
                   for (ii=i; ii<list_num; ii++)
                   {
                       list[ii<<1]=list[(ii+1)<<1];
                       list[(ii<<1)+1]=list[((ii+1)<<1)+1];
                   }
                   list[list_num<<1]=0;
                   list[(list_num<<1)+1]=0;
                   i=-1;
              }
         }
         else
         {
              pos3=list[i<<1]+list[(i<<1)+1];
              if ((pos&0x1FFFFFF)<=(pos3&0x1FFFFFF))
              {
                   pos=list[i<<1];
                   if ((pos3&0x1FFFFFF)>(pos2&0x1FFFFFF))
                   {
                       pos2=pos3;
                   }
                   size=(pos2&0x09FFFFFF)-(pos&0x09FFFFFF);
                   list_num-=1;
                   for (ii=i; ii<list_num; ii++)
                   {
                       list[ii<<1]=list[(ii+1)<<1];
                       list[(ii<<1)+1]=list[((ii+1)<<1)+1];
                   }
                   list[list_num<<1]=0;
                   list[(list_num<<1)+1]=0;
                   i=-1;
              }
         }
    }
   
    list[list_num<<1]=(pos&0x1FFFFFF)|0x08000000;
    if ((pos>>28)==1)
    { list[list_num<<1]|=0x10000000; }
    else
    {
         for (i=0; i<size; i++)
         { WRITE_BYTE(pos+i,0); }
    }
    list[(list_num<<1)+1]=size;
    list_num++;
    spacemanager::organizeList(list);
    return list_num;
}

int spacemanager::claimSpace(int *list, int pos, int size)
{
    //size=(size+3)&0xFFFFFFFC;
    if (pos<=0 || size<=0)
    { return -list_num; }
    if (spacemanager::confirmSpace(list, pos, size)<=0)
    { return -list_num; }
    int i, index; index=-1;
    for (i=0; i<list_num; i++)
    {
         if ((list[i<<1]&0x1FFFFFF)<=(pos&0x1FFFFFF))
         {
              if (((list[i<<1]+list[(i<<1)+1])&0x1FFFFFF)>=((pos+size)&0x1FFFFFF))
              {
                   index=i; i=list_num;
              }
         }
    }
    if (index<0)
    { return -list_num; }
    if ((pos&0x1FFFFFF)==(list[index<<1]&0x1FFFFFF))
    {
         if (size<list[(index<<1)+1])
         {
              list[index<<1]+=size;
              list[(index<<1)+1]-=size;
              spacemanager::organizeList(list);
              return list_num;
         }
         else
         {
              list_num-=1;
              for (i=index; i<list_num; i++)
              {
                   list[i<<1]=list[(i+1)<<1];
                   list[(i<<1)+1]=list[((i+1)<<1)+1];
              }
              list[list_num<<1]=0; list[(list_num<<1)+1]=0;
              spacemanager::organizeList(list);
              return list_num;
         }
    }
    else
    {
         i=list[(index<<1)+1]-((pos&0x1FFFFFF)-(list[index<<1]&0x1FFFFFF))-size;
         if (i>0)
         {
              list[list_num<<1]=((pos+size)&0x1FFFFFF)|0x08000000;
              list[(list_num<<1)+1]=i;
              list_num+=1;
         }
         list[(index<<1)+1]=(pos&0x1FFFFFF)-(list[index<<1]&0x1FFFFFF);
    }
    spacemanager::organizeList(list);
    return list_num;
}
[/spoiler]
Golden Sun Docs: Broken Seal - The Lost Age - Dark Dawn | Mario Sports Docs: Mario Golf & Mario Tennis | Misc. Docs
Refer to Yoshi's Lighthouse for any M&L hacking needs...

Sometimes I like to compare apples to oranges. (Figuratively) ... They are both fruits, but which one would you eat more? (If taken literally, I'd probably choose apples.)
Maybe it is over-analyzing, but it doesn't mean the information is useless.


The only GS Discord servers with significance are:
Golden Sun Hacking Community
GS Speedrunning
/r/Golden Sun
GS United Nations
Temple of Kraden

Can you believe how small the Golden Sun Community is?

2+2=5 Don't believe me? Those are rounded decimal numbers. Take that, flat earth theorists! :)

Luna_blade

Quote from: Fox on 20, June, 2017, 04:26:10 PM
First if?
Yeah "if (list[i<<1]==list[(i-1)<<1])".
so when i = 0x00005000 for example,
list[0x00012000] == list[0x0005FFE] (correct me if I am wrong, still very tired)
that would make little sense to me. I am sure there is some reason that range between the two indices makes sense, but I simply don't know it.
Quote from: Fox link
Don't try to understand it without seeing the rest of it: (From Atrius's Source code... C++ Space Manager code file.)
Mmhh... aha, so this takes the ROM passed to it by another program/code, then is able to tell you where free space is?
Quote from: Fox link
If one is found... the code inside the if block shown in the first post basically swaps them. I'm not sure why there's an "|0x40000000" though..
I guess the bitwise OR is some kind of marking that methods afterwards can use.
"Hear the sounds and melodies
Of rilets flowing down
They're the verlasting songs
Whispering all the time
As a warning that behind some rocks
There's a rigid grap even
Oreads fear the tread"

Daddy Poi's Oily Gorillas

#4
QuoteYeah "if (list[i<<1]==list[(i-1)<<1])".
so when i = 0x00005000 for example,
list[0x00012000] == list[0x0005FFE] (correct me if I am wrong, still very tired)
that would make little sense to me. I am sure there is some reason that range between the two indices makes sense, but I simply don't know it.
When i=0x5000
if list[0xA000] == list[0x9FFE]

<<1 is like multiplying by 2.

If you do the calculation for any i, the two address will always be the same distance apart (The entry before and the current one... for when the two addresses match... The problem is I'm not sure how they'd ever match based on the rest of the code used? But I'm sure I could have easily missed something.)

list[0] = The first entry's free space address
list[1] = The first entry's free space size
list[2] = second entry's free space address
list[3] = and size (and so on.)

Also, any i that is 0x4000 or above could be out of bounds. Since he has 0x8000 elements. Although, if it turns out that all the list variable is just a pointer to the data (That's the way I think of * after a type)... (As in, no bounds checking), there may still not be an actual error message....

Only the LOAD_INTs and WRITE_INTs / etc. read/write from the ROM, he puts the contents of interest into a "list" variable instead of messing with it directly from the ROM.

QuoteI guess the bitwise OR is some kind of marking that methods afterwards can use.
I get that he's basically adding the bit 0x40000000 for some reason, just wasn't sure why it was needed in this case. (As again, it requires addresses to match to even get to that part. It makes it feel like it is so that next bolded code doesn't get executed or something. But not sure what the reason for all this is.)

---
My WIP code for C# idea:  (A function that may do similar to Atrius's Repointing system... As for right now, we can't assume that any data in a file table has already been repointed from a hex hacker anyway... that, and patch-friendliness (keeping a smaller patch size than my alternative idea.)....However, I do plan to look into the table resizing idea further, just I was thinking I'll probably want to support both ways. (If possible.) )

int claimSpace(int size)
{
//Find space in a possibly "unorganized" list of the lowest size we can get away with.
//Increased free space address/decreases free space size, if new freeSpace size of entry is 0 , remove entry. (Could be set to the last entry's rather than moving everything over.)
//POSSIBLY after a base is done and if I ever feel like it ... if there's enough free space, but there's not one single section that has enough, then do code to organize some data a bit. - It's possible the function that frees space could have something similar as well. Especially if you can run out of free space entries.  (Not sure how I intend to do that yet, so can be ignored.)
//return that address.
}

Might change it to take an address (and maybe another size value) as well, if I decide it should also be responsible for freeing up the invalidated data... and perhaps even updating the pointer. (e.g. freespace and claimspace function often used together?)
But most of that can probably be done via a separate function... Hmm... freeSpace, claimSpace, reallocate....
Golden Sun Docs: Broken Seal - The Lost Age - Dark Dawn | Mario Sports Docs: Mario Golf & Mario Tennis | Misc. Docs
Refer to Yoshi's Lighthouse for any M&L hacking needs...

Sometimes I like to compare apples to oranges. (Figuratively) ... They are both fruits, but which one would you eat more? (If taken literally, I'd probably choose apples.)
Maybe it is over-analyzing, but it doesn't mean the information is useless.


The only GS Discord servers with significance are:
Golden Sun Hacking Community
GS Speedrunning
/r/Golden Sun
GS United Nations
Temple of Kraden

Can you believe how small the Golden Sun Community is?

2+2=5 Don't believe me? Those are rounded decimal numbers. Take that, flat earth theorists! :)

Luna_blade

Quote from: Fox on 21, June, 2017, 05:43:59 AM
When i=0x5000
if list[0xA000] == list[0x9FFE]
<<1 is like multiplying by 2.
Yeah I know shifts, I just did it wrong... not an expert with Hex.

Quote from: Fox
If you do the calculation for any i, the two address will always be the same distance apart (The entry before and the current one... for when the two addresses match... The problem is I'm not sure how they'd ever match based on the rest of the code used? But I'm sure I could have easily missed something.)

list[0] = The first entry's free space address
list[1] = The first entry's free space size
list[2] = second entry's free space address
list[3] = and size (and so on.)
Pretty interesting.
"Hear the sounds and melodies
Of rilets flowing down
They're the verlasting songs
Whispering all the time
As a warning that behind some rocks
There's a rigid grap even
Oreads fear the tread"

Daddy Poi's Oily Gorillas

@1: Okay. It's always worth making sure, though... Right?
@2: For which? The fact that he did it address, size, address, size, etc. or???
Golden Sun Docs: Broken Seal - The Lost Age - Dark Dawn | Mario Sports Docs: Mario Golf & Mario Tennis | Misc. Docs
Refer to Yoshi's Lighthouse for any M&L hacking needs...

Sometimes I like to compare apples to oranges. (Figuratively) ... They are both fruits, but which one would you eat more? (If taken literally, I'd probably choose apples.)
Maybe it is over-analyzing, but it doesn't mean the information is useless.


The only GS Discord servers with significance are:
Golden Sun Hacking Community
GS Speedrunning
/r/Golden Sun
GS United Nations
Temple of Kraden

Can you believe how small the Golden Sun Community is?

2+2=5 Don't believe me? Those are rounded decimal numbers. Take that, flat earth theorists! :)

Luna_blade

Quote from: Fox on 21, June, 2017, 11:44:05 AM
@1: Okay. It's always worth making sure, though... Right?
yeah
Quote from: Fox
@2: For which? The fact that he did it address, size, address, size, etc. or???
Well, the whole process of finding free space. I have true trouble grasping this right now (and maybe because some parts are not really written the way I usually write) but still pretty interesting.
"Hear the sounds and melodies
Of rilets flowing down
They're the verlasting songs
Whispering all the time
As a warning that behind some rocks
There's a rigid grap even
Oreads fear the tread"

Daddy Poi's Oily Gorillas

#8
@1: Okay.
@2: Oh.

If no free space table:
Generate one by going through a number of addresses in MFT. (The ones at the beginning.)
Using these addresses, work your way backwards.
For each byte is free space as long as it is a 00. (Once there is a non-zero, go to next MFT address or end of file.... and keep scanning backwards.)
If there is already a table, we can use that to determine free space...
His confirmSpace function will check for 00s, again, though... And if there is a non-zero... Then he'll split the entry into two (The general idea is that the first and last chucks are kept as freespace, anything in the middle isn't)... to ensure that data is only containing zeros.
However, the 00 checks in confirmSpace only applies when (freeSpace address)>>28 does not equal 1. .... Makes sense b/c that could mean things that are repointed (the old data) does not need to be checked for 00s... ... And there may be code that can set an entire section to 00s as well. But I'm thinking/guessing that only applies to what was originally found to be 00. (My guess is that he was aiming to keep the size of patches low.... A lot of that is guessing, though... when I actually look at tha data, I'm like..... Huh? Doesn't look like old/outdated freespace tables are cleared out....


Hmmm.....
Golden Sun Docs: Broken Seal - The Lost Age - Dark Dawn | Mario Sports Docs: Mario Golf & Mario Tennis | Misc. Docs
Refer to Yoshi's Lighthouse for any M&L hacking needs...

Sometimes I like to compare apples to oranges. (Figuratively) ... They are both fruits, but which one would you eat more? (If taken literally, I'd probably choose apples.)
Maybe it is over-analyzing, but it doesn't mean the information is useless.


The only GS Discord servers with significance are:
Golden Sun Hacking Community
GS Speedrunning
/r/Golden Sun
GS United Nations
Temple of Kraden

Can you believe how small the Golden Sun Community is?

2+2=5 Don't believe me? Those are rounded decimal numbers. Take that, flat earth theorists! :)

Atrius (He/Him)

Oh wow, this is embarrassing...  I do remember putting code in there to prevent problems that probably wouldn't happen, but I don't even remember a lot of this.  I definitely would have written it very differently if I knew then what I know now...


So...  I'm not entirely sure this was related to it, but there was some trickery going on to solve recursion issues...  The way most of the functions are written they're recursive, so for example findSpace calls confirmSpace which calls organizeList which calls findSpace starting the cycle over.  The 0x40000000 was a bit tag marking the address for some purpose that I can't remember, but it may have been to solve a recursion problem, I doubt it was meant solely for the organizeList function...


Fox has the right idea with the list array.  Even locations in the array (list[i<<1]) are addresses, and odd locations (list[(i<<1)+1]) are sizes.
[sprite=220,4,0]I'm shaking my head in general disapproval of everything[/sprite]