Page 1 of 2 12 LastLast
Results 1 to 15 of 26
  1. #1
    Master Sergeant
    Reputation
    20
    Join Date
    Feb 2009
    Posts
    78
    CoreCoins
    0

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    0 (0%)

    ObjectManager: why do we have to ensure that the last bit of an object's address is 0



    Donate to Remove Ads, Get ShoutBawx - Elite Forum Access
    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
    Reputation
    14
    Join Date
    Jan 2009
    Posts
    30
    CoreCoins
    49

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    0 (0%)
    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
    New User

    Reputation
    4
    Join Date
    Aug 2009
    Posts
    11
    CoreCoins
    0

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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
    #define true false Jadd's Avatar
    Reputation
    883
    Join Date
    May 2008
    Location
    ntoskrnl.exe
    Posts
    1,825
    CoreCoins
    121

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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 (:
    If Java had true garbage collection, most programs would delete themselves upon execution. Robert Sewell

  5. #5
    Knight-Captain flo8464's Avatar
    Reputation
    27
    Join Date
    Apr 2009
    Location
    Germany
    Posts
    436
    CoreCoins
    1

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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
    CoreCoins
    7

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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
    27
    Join Date
    Apr 2009
    Location
    Germany
    Posts
    436
    CoreCoins
    1

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    0 (0%)
    I am pretty sure next/previous-element pointers get initialized by NULL.

  8. #8
    Master Sergeant
    Reputation
    27
    Join Date
    Mar 2008
    Posts
    94
    CoreCoins
    0

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    0 (0%)
    actually if you walk the list backwards it just loops. that's how i used to enumerate objects in wowbasic

  9. #9
    Master Sergeant
    Reputation
    20
    Join Date
    Feb 2009
    Posts
    78
    CoreCoins
    0

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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
    Contributor

    CoreCoins User


    Reputation
    211
    Join Date
    Sep 2008
    Location
    Hawaii
    Posts
    698
    CoreCoins
    242

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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
    27
    Join Date
    Apr 2009
    Location
    Germany
    Posts
    436
    CoreCoins
    1

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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
    Reputation
    283
    Join Date
    Sep 2006
    Location
    Jaedenar O.o
    Posts
    1,017
    CoreCoins
    155

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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
    Contributor

    CoreCoins User


    Reputation
    211
    Join Date
    Sep 2008
    Location
    Hawaii
    Posts
    698
    CoreCoins
    242

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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
    27
    Join Date
    Apr 2009
    Location
    Germany
    Posts
    436
    CoreCoins
    1

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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
    Contributor

    CoreCoins User


    Reputation
    211
    Join Date
    Sep 2008
    Location
    Hawaii
    Posts
    698
    CoreCoins
    242

    Trade Feedbacks

    Status
    n/a
    Positive
    0 (0%)
    Negative
    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; // 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.

 

 
Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
All times are GMT -4. The time now is 03:58 PM. Powered by vBulletin® Version 4.2.0
Copyright © 2014 vBulletin Solutions, Inc. All rights reserved. Resources saved on this page: MySQL 5.88%
vBulletin Optimisation provided by vB Optimise (Pro) - vBulletin Mods & Addons Copyright © 2014 DragonByte Technologies Ltd.
Digital Point modules: Sphinx-based search