Page 1 of 2 12 LastLast
Results 1 to 15 of 26
  1. #1
    Member Ellesar1's Avatar
    Reputation
    20
    Join Date
    Feb 2009
    Posts
    78
    Thanks G/R
    0/0
    CoreCoins
    0
    Trade Feedback
    0 (0%)

    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.

  2. #2
    Corporal Oowafas's Avatar
    Reputation
    14
    Join Date
    Jan 2009
    Posts
    31
    Thanks G/R
    0/0
    CoreCoins
    49
    Trade Feedback
    1 (100%)
    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?

  3. #3
    Private RiotInferno's Avatar
    Reputation
    4
    Join Date
    Aug 2009
    Posts
    10
    Thanks G/R
    0/0
    CoreCoins
    0
    Trade Feedback
    0 (0%)
    I also don't have a concrete answer, but my theory is that it represents the end of the Object list?

  4. #4
    hello world CoreCoins User Jadd's Avatar
    Reputation
    1182
    Join Date
    May 2008
    Location
    http://ntoskr.nl/
    Posts
    2,168
    Thanks G/R
    44/114
    CoreCoins
    396084
    Trade Feedback
    0 (0%)
    Quote Originally Posted by Oowafas View Post
    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 (:
    I'm not a trade moderator. Please don't message me regarding trade threads, you will be ignored!

  5. #5
    Knight-Captain flo8464's Avatar
    Reputation
    30
    Join Date
    Apr 2009
    Location
    Germany
    Posts
    434
    Thanks G/R
    0/0
    CoreCoins
    1
    Trade Feedback
    0 (0%)
    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.

  6. #6
    Master Sergeant Kryso's Avatar
    Reputation
    37
    Join Date
    Jul 2009
    Posts
    94
    Thanks G/R
    0/0
    CoreCoins
    7
    Trade Feedback
    0 (0%)
    IMO because invalidating pointer to next node by setting one bit is faster than setting 4 bytes to 0?

  7. #7
    Knight-Captain flo8464's Avatar
    Reputation
    30
    Join Date
    Apr 2009
    Location
    Germany
    Posts
    434
    Thanks G/R
    0/0
    CoreCoins
    1
    Trade Feedback
    0 (0%)
    I am pretty sure next/previous-element pointers get initialized by NULL.

  8. #8
    Master Sergeant bigtimt's Avatar
    Reputation
    27
    Join Date
    Mar 2008
    Posts
    96
    Thanks G/R
    0/0
    CoreCoins
    0
    Trade Feedback
    0 (0%)
    actually if you walk the list backwards it just loops. that's how i used to enumerate objects in wowbasic

  9. #9
    Member Ellesar1's Avatar
    Reputation
    20
    Join Date
    Feb 2009
    Posts
    78
    Thanks G/R
    0/0
    CoreCoins
    0
    Trade Feedback
    0 (0%)
    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!)

  10. #10
    Elite User CoreCoins User Authenticator enabled namreeb's Avatar
    Reputation
    330
    Join Date
    Sep 2008
    Location
    Hawaii
    Posts
    820
    Thanks G/R
    2/40
    CoreCoins
    5732
    Trade Feedback
    0 (0%)
    Quote Originally Posted by Oowafas View Post
    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.

  11. #11
    Knight-Captain flo8464's Avatar
    Reputation
    30
    Join Date
    Apr 2009
    Location
    Germany
    Posts
    434
    Thanks G/R
    0/0
    CoreCoins
    1
    Trade Feedback
    0 (0%)
    Quote Originally Posted by bierstud View Post
    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?

  12. #12
    Contributor MaiN's Avatar
    Reputation
    323
    Join Date
    Sep 2006
    Location
    Jaedenar O.o
    Posts
    1,026
    Thanks G/R
    0/5
    CoreCoins
    187
    Trade Feedback
    0 (0%)
    Quote Originally Posted by Ellesar1 View Post
    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

  13. #13
    Elite User CoreCoins User Authenticator enabled namreeb's Avatar
    Reputation
    330
    Join Date
    Sep 2008
    Location
    Hawaii
    Posts
    820
    Thanks G/R
    2/40
    CoreCoins
    5732
    Trade Feedback
    0 (0%)
    Quote Originally Posted by flo8464 View Post
    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.

  14. #14
    Knight-Captain flo8464's Avatar
    Reputation
    30
    Join Date
    Apr 2009
    Location
    Germany
    Posts
    434
    Thanks G/R
    0/0
    CoreCoins
    1
    Trade Feedback
    0 (0%)
    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.

  15. #15
    Elite User CoreCoins User Authenticator enabled namreeb's Avatar
    Reputation
    330
    Join Date
    Sep 2008
    Location
    Hawaii
    Posts
    820
    Thanks G/R
    2/40
    CoreCoins
    5732
    Trade Feedback
    0 (0%)
    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; // [email protected]
      int v3; // [email protected]
      int v4; // [email protected]
      eWOWOBJECTTYPE v5; // [email protected]
    
      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.

 

 
Page 1 of 2 12 LastLast
All times are GMT -5. The time now is 12:42 PM. Powered by vBulletin® Version 4.2.2
Copyright © 2016 vBulletin Solutions, Inc. All rights reserved. Digital Point modules: Sphinx-based search