-
Member
ObjectManager: why do we have to ensure that the last bit of an object's address is 0
I'm currently trying to understand WoW's object manager and built some basic object manager based on different posts here on MMOwned.
However, I don't understand why we have to check whether the last bit of an object pointer is set to 1 or 0 and to cancel our loop if it is 1. I've tried and it bugs if we omit the check. But why? What does this 1 represent?
Code:
// Iterate through objects
Object * current;
_asm {
mov eax, objectManagerBase;
add eax, 0xac; // Credits: jbrauman
mov eax, [eax];
mov current, eax;
}
while (current && (((unsigned int)current & 1) == 0)) { // Credits: EmilyStrange
cache.push_back(*current);
current = (*current).nextObject;
}
objectCache = cache;
the (((unsigned int)current & 1) == 0) is what I don't understand.
-
Member
The one bit can be set to represent an invalid pointer because an object will never be created without being 4 byte aligned (both the last and 2nd to last bits will always be 0). I don't actually know why it does it that way, maybe because they can only test 1 byte for an invalid pointer as opposed to a 4 byte operand?
-
Member
I also don't have a concrete answer, but my theory is that it represents the end of the Object list?
-
Originally Posted by
Oowafas
The one bit can be set to represent an invalid pointer because an object will never be created without being 4 byte aligned (both the last and 2nd to last bits will always be 0).
This.
Have fun (:
-
Active Member
The object manager is a linked list. A linked list ends with a NULL-pointer to the next element.
Normally checking for a NULL-pointer should be enough. As far as I know invalid pointers should never occur (well, except its implementation is incorrect which isn't the case), the CPU makes no mistakes. So I don't really get why it's checked.
-
Active Member
IMO because invalidating pointer to next node by setting one bit is faster than setting 4 bytes to 0?
-
Active Member
I am pretty sure next/previous-element pointers get initialized by NULL.
-
Active Member
actually if you walk the list backwards it just loops. that's how i used to enumerate objects in wowbasic
-
Member
what do you understand with "walking backwards"? There is only a next - pointer, not a previous-pointer, as far as I know.
And they have to be initialized to 0 since an invalid pointer can be everything random (also even number!)
-
Originally Posted by
Oowafas
The one bit can be set to represent an invalid pointer because an object will never be created without being 4 byte aligned (both the last and 2nd to last bits will always be 0). I don't actually know why it does it that way, maybe because they can only test 1 byte for an invalid pointer as opposed to a 4 byte operand?
This is the correct answer.
-
Active Member
Originally Posted by
bierstud
This is the correct answer.
But how can it happen that something like that fails ?
Code:
Object someObject;
ObjectList.getCurrentObject()->nextObject = &someObject;
(I know, bad example but should show what I mean).
Is that check something the compiler adds to the code?
-
Elite User
Originally Posted by
Ellesar1
what do you understand with "walking backwards"? There is only a next - pointer, not a previous-pointer, as far as I know.
And they have to be initialized to 0 since an invalid pointer can be everything random (also even number!)
Hmm, isn't it a double linked list?
[16:15:41] Cypher: caus the CPU is a dick
[16:16:07] kynox: CPU is mad
[16:16:15] Cypher: CPU is all like
[16:16:16] Cypher: whatever, i do what i want
-
Post Thanks / Like - 1 Thanks
renaxi (1 members gave Thanks to MaiN for this useful post)
-
Originally Posted by
flo8464
But how can it happen that something like that fails ?
Code:
Object someObject;
ObjectList.getCurrentObject()->nextObject = &someObject;
(I know, bad example but should show what I mean).
Is that check something the compiler adds to the code?
What do you mean? Is it failing for you? I'm pretty sure this is how the game does it.
-
Active Member
Yeah, but I still don't get how an invalid address can be assigned to that pointer.
Maybe I think overcomplicated, could you please explain it to me.
-
It's fairly simple. Rather than null terminating their linked list they chose to set it to an 'odd' value. Alignment says this value is invalid.
EnumVisibleObjects() from WoW:
Code:
signed int __cdecl EnumVisibleObjects(int (__cdecl *pCallback)(WGUID, _DWORD), eWOWOBJECTTYPE filter)
{
int v2; // eax@1
int v3; // esi@1
int v4; // ebx@3
eWOWOBJECTTYPE v5; // edi@5
v3 = *(_DWORD *)(*MK_FP(__FS__, 44) + 4 * TlsIndex);
v2 = *(_DWORD *)(*(_DWORD *)(v3 + 8) + 172);
if ( !(v2 & 1) && v2 )
v4 = *(_DWORD *)(*(_DWORD *)(v3 + 8) + 172);
else
v4 = 0;
v5 = filter;
while ( !(v4 & 1) && v4 )
{
if ( !((int (__cdecl *)(_DWORD, _DWORD, eWOWOBJECTTYPE))pCallback)(*(_DWORD *)(v4 + 48), *(_DWORD *)(v4 + 52), v5) )
return 0;
v4 = *(_DWORD *)(v4 + *(_DWORD *)(*(_DWORD *)(v3 + 8) + 164) + 4);
}
return 1;
}
The line of interest there is the while statement. v4 is their iterator. It's anyone's guess why they did it this way.. but they did. Perhaps they use other bits there for something else? It's unimportant.