O(1) Guid Searches

[_chase]

The object manager is backed by a hashmap where guids are keys.
Many developers are iterating the whole object manager when they need to find the guid's owning object which is O(total_objects).
This becomes a larger issue when reversing the inventory system, containers simply maintain a list of guids not object pointers. So to search a container you're looking at O(total_objects*container_items).
By reversing the hash function you can very easily, and efficiently iterate and query the object manager.

in the below code there are two hashing constants: 0xD6D018F5 , 0xA2AA033B;
To maintain these offsets yourself, you can search for those immediate values and readily find hashmap query/insertion functions to explore

Thank you EJT: https://www.ownedcore.com/forums/wor...ml#post4315126 ([Retail] Shadowlands 9.0.1.36230 Offsets)
For making me aware of this technique

3.4.1.49345 Wotlk Classic Offsets

pub mod object_manager {
    pub const BUCKET_COUNT: usize = 0x00;
    pub const BUCKETS: usize = 0x08;
    pub const OBJECT_COUNT: usize = 0x10;
}

pub mod bucket {
    pub const NEXT: usize = 0x00;
    pub const VALUE: usize = 0x18;
}

pub mod cgobject {
    pub const OBJECT_TYPE: usize = 0x10;
    pub const GUID: usize = 0x18;
    pub const ENTRY_ID: usize = 0xD8;
}

pub struct Bucket;

impl Bucket {
    // *Bucket
    nullable_ref!(self, pub next, Bucket, pyres_offsets::fields::bucket::NEXT);

    // &CGObject
    owned_ref!(self, pub value, CGObject, pyres_offsets::fields::bucket::VALUE);

    pub fn iter(&self) -> BucketIterator<'_> {
        BucketIterator {
            current: Some(self),
        }
    }
}

pub struct BucketIterator<'a> {
    current: Option<&'a Bucket>,
}

impl<'a> Iterator for BucketIterator<'a> {
    type Item = &'a Bucket;

    fn next(&mut self) -> Option<Self::Item> {
        match self.current {
            Some(entry) => {
                self.current = entry.next();
                Some(entry)
            }
            None => None,
        }
    }
}


pub struct ObjectManager;

impl ObjectManager {

    // u32
    prim!(
        self,
        pub object_count,
        u32,
        pyres_offsets::fields::object_manager::OBJECT_COUNT
    );

    // u32
    prim!(
        self,
        pub bucket_count,
        u32,
        pyres_offsets::fields::object_manager::BUCKET_COUNT
    );

    // &[*const Bucket; self::bucket_count()]
    slice_ref_prop!(
        self,
        pub buckets,
        *const Bucket,
        bucket_count,
        pyres_offsets::fields::object_manager::BUCKETS
    );


    pub fn objects_iter(&self) -> impl Iterator<Item = &CGObject> {
        self.buckets()
            .iter()
            // make sure bucket head is populated
            .filter_map(|b| unsafe { b.as_ref() })
            // make sure the bucket value chain is populated
            .flat_map(|b| b.iter())
            // map the bucket chain to its internal value
            .map(|b| b.value())
    }

    pub fn active_player(&self) -> Option<&CGActivePlayer> {
        self.find_by_guid(active_player_guid())
            // todo, unchecked casts for known object types
            .and_then(|o| o.try_cast_active_player())
    }

    pub fn active_target(&self) -> Option<&CGUnit> {
        self.find_by_guid(target_guid())
            .and_then(|o| o.try_cast_unit())
    }


    /// Given a guid, attempt to identify the owning object's backing object
    pub fn find_by_guid(&self, guid: &Guid) -> Option<&CGObject> {
        if guid.is_empty() {
            return None;
        }

        let k3 = (guid.high() as u32).overflowing_mul(0xD6D018F5).0;
        let k4 = (guid.low() as u32).overflowing_mul(0xA2AA033B).0;

        let hash = k3.overflowing_add(k4).0;
        let index = hash & (self.bucket_count() - 1);
        let bucket = self.buckets().get(index as usize)?;
        let bucket_ref = unsafe { bucket.as_ref()? };

        return bucket_ref
            .iter()
            .map(|b| b.value())
            .find(|&value| value.guid().high() == guid.high() && value.guid().low() == guid.low());
    }
}

[ejt]

Thank you EJT: https://www.ownedcore.com/forums/wor...ml#post4315126 ([Retail] Shadowlands 9.0.1.36230 Offsets)
For making me aware of this technique

Thank you.

[_chase]

Thank you.

Cheers, appreciate your earlier work such as: Ian / WoWOffsetDumper . GitLab
Back when I first started this got me over the initial learning curve

[klumpen]

Beautiful stuff. Hella curious about the .try_cast methods & the macros used.
I'm going the ECS route and just, y'know, enumerating the object manager & name caches like a brute.

// 'pseudo main'
fn main() -> Result<(), Box<dyn Error>> {
Ok(App.new()
  .add_system(object_manager_system)
  .add_system(pathfinding_system)
  // w2s, overlay, kbd input etc
  .run())
}

fn object_manager_system(
  object_manager: Res<ObjectManager>, 
  commands: mut Commands,
) {
  let objects = object_manager.tick().expect("eek");
  commands.spawn_batch(objects);
}

fn pathfinding_system(
  map: Res<Map>,
  navigators: Res<DivertNavigators>,
  player: Query<&ScreenPosition, With<ActivePlayerMarker>>,
  mut query: Query<
    (&ScreenPosition, &mut Path), 
    Or<(
      With<PlayerMarker>,
      With<FocusTargetMarker>,
      With<MouseoverTargetMarker>,
      With<TargetMarker>,
      With<TargetOfTargetMarker>,      
      With<PartyMarker>,
     )>,
  >
) {
  let navigator = navigators.get_or_create(map.id).expect("eek");
  let src = player.single();
  for (dst, mut path) in &query {
    if let Ok(dt_path) = navigator.find_path(src.to_dt_vec(), dst.to_dt_vec()) {
      path.0 = dt_path.iter().map(|dtv| Vec3::new(dtv.x, dtv.y, dtv.z));
    }
  }
}

Very different, still a bit alien. Especially so when plugging decision making & AI into it. Fun though.
Thanks again for your work on divert And now I've gone and derailed from the topic at hand.
I can see how a `do I have still have <X> in my inventory?` and similar queries would benefit from a direct lookup over iterating.

[scizzydo]

The object manager is backed by a hashmap where guids are keys.
Many developers are iterating the whole object manager when they need to find the guid's owning object which is O(total_objects).
This becomes a larger issue when reversing the inventory system, containers simply maintain a list of guids not object pointers. So to search a container you're looking at O(total_objects*container_items).
By reversing the hash function you can very easily, and efficiently iterate and query the object manager.

in the below code there are two hashing constants: 0xD6D018F5 , 0xA2AA033B;
To maintain these offsets yourself, you can search for those immediate values and readily find hashmap query/insertion functions to explore

Thank you EJT: https://www.ownedcore.com/forums/wor...ml#post4315126 ([Retail] Shadowlands 9.0.1.36230 Offsets)
For making me aware of this technique

Good stuff. For those who want to get the hashes quickly, here's a pattern

4C 8B 0E B8 ? ? ? ? 4C 8B 46 08 BA ? ? ? ? 48 8B 2F

The two wildcard areas respectively.

[_chase]

Beautiful stuff. Hella curious about the .try_cast methods & the macros used.
I'm going the ECS route and just, y'know, enumerating the object manager & name caches like a brute.

// 'pseudo main'
fn main() -> Result<(), Box<dyn Error>> {
Ok(App.new()
  .add_system(object_manager_system)
  .add_system(pathfinding_system)
  // w2s, overlay, kbd input etc
  .run())
}

fn object_manager_system(
  object_manager: Res<ObjectManager>, 
  commands: mut Commands,
) {
  let objects = object_manager.tick().expect("eek");
  commands.spawn_batch(objects);
}

fn pathfinding_system(
  map: Res<Map>,
  navigators: Res<DivertNavigators>,
  player: Query<&ScreenPosition, With<ActivePlayerMarker>>,
  mut query: Query<
    (&ScreenPosition, &mut Path), 
    Or<(
      With<PlayerMarker>,
      With<FocusTargetMarker>,
      With<MouseoverTargetMarker>,
      With<TargetMarker>,
      With<TargetOfTargetMarker>,      
      With<PartyMarker>,
     )>,
  >
) {
  let navigator = navigators.get_or_create(map.id).expect("eek");
  let src = player.single();
  for (dst, mut path) in &query {
    if let Ok(dt_path) = navigator.find_path(src.to_dt_vec(), dst.to_dt_vec()) {
      path.0 = dt_path.iter().map(|dtv| Vec3::new(dtv.x, dtv.y, dtv.z));
    }
  }
}

Very different, still a bit alien. Especially so when plugging decision making & AI into it. Fun though.
Thanks again for your work on divert And now I've gone and derailed from the topic at hand.
I can see how a `do I have still have <X> in my inventory?` and similar queries would benefit from a direct lookup over iterating.

Cool stuff with the ecs, I had tinkered around with that idea but so far my scripts have been simple enough not to warrant the dev work.
Having the by guid query is super nice, because you can save/copy guids between game ticks safely.
For instance in a combat bot, when you're in combat with a current target and casting or whatever (essentially a nop tick). I do in total two O(1) queries, get my player ptr with the static guid and get my target ptr with the static guid.
Without the query by guid you'd be doing an O(n) query and have to update your whole world state matching over the static player guid and target guid etc. This also already becomes obnoxious to provide an api for. Have to check both player and target guid on every iteration so you don't have to reiterate and now make it O(2n). Overtime that can stack up especially if you're poc'ing and don't cache things or have a performant api.

[Razzue]

~~

Nice share! and thanks for the example code and link to old thread :3
Noticed this also seems to work on the player name cache (and I'm assuming a few other things?)

[StructLayout(LayoutKind.Explicit, Pack = 1)]
public struct PlayerNameCache
{
    [FieldOffset(0x8)]
    public TSArray ActiveObjects;


    public string GetName(Guid input)
    {
        try
        {
            if (input.IsEmpty()) return string.Empty;
            var v1 = 0xD6D018F5 * input.High;
            var v2 = 0xA2AA033B * input.Low;


            var index = (v1 + v2) & (ActiveObjects.Size - 1);
            var pointer = ActiveObjects.Pointers[index];
            if (pointer.ToInt64() == 0) return string.Empty;


            var entry = Memory.Read<NameEntry>(pointer);
            do
            {
                if (entry.Guid.Equals(input)) break;
                Memory.Read(entry.Next, ref entry);

            } while (entry.Next.ToInt64() != 0);


            return entry.Value;
        }
        catch (Exception e)
        {
            Console.WriteLine(e);
            return string.Empty;
        }
    }
}

[Glitt]

Rust? That's pretty neato!

I want to figure this out a bit, but I'm curious about performance. I would imagine this is the best method for finding/iterating objects, but isn't just using an unordered_map map also O(1)? Not trying to be smart here.. mostly just curious if you think the extra trouble is worth it. My current OM just does a pulse and sets the whole thing in a global. The only optimization I use is the filter (object type), and the stuff that uses it is either comparing a name or guid. I've tried various things like persistence and removing old objects, but the best for me is this on-demand system as described. Currently dumping this update that just delivered, so I'll take a look at the pattern scizzydo posted. Ty

[_chase]

Rust? That's pretty neato!

I want to figure this out a bit, but I'm curious about performance. I would imagine this is the best method for finding/iterating objects, but isn't just using an unordered_map map also O(1)? Not trying to be smart here.. mostly just curious if you think the extra trouble is worth it. My current OM just does a pulse and sets the whole thing in a global. The only optimization I use is the filter (object type), and the stuff that uses it is either comparing a name or guid. I've tried various things like persistence and removing old objects, but the best for me is this on-demand system as described. Currently dumping this update that just delivered, so I'll take a look at the pattern scizzydo posted. Ty

Yep, this seems to be the end state for most devs. I too explored pulse systems, tracking removals, managing my own hashmap etc. In the end, it just became a huge time sink. With the hashmap gets, even when used inefficiently my scripts are so low resource now. If you optimize and store guids across game ticks you can get really efficient with it, and not be committing any heinous thread / memory crimes. Guids can be copied across threads and safely mapped to the object's pointer on demand, storing direct object pointers is dangerous.

Below is the gmvision debug function annotated which demonstrates the full hashmap traversal

__int64 ObjectManagerDebug()
{
  unsigned int activeObjects; // r15d
  int itemCount; // esi
  unsigned int unitCount; // ebp
  unsigned int gameObjectCount; // r14d
  unsigned int visibleObjects; // edi
  CGBucket *current_visible_bucket; // rax
  CGBucket **buckets; // rax
  CGBucket *current_bucket; // r8
  CGBucket **sentinel_bucket; // r9
  int typeCode; // r10d
  unsigned __int32 waitToBeFreed; // ebx

  activeObjects = 0;
  itemCount = 0;
  unitCount = 0;
  gameObjectCount = 0;
  visibleObjects = 0;
  for ( current_visible_bucket = s_ObjMgr->visibleList.next;
        current_visible_bucket != (CGBucket *)&s_ObjMgr->visibleList;
        ++visibleObjects )
  {
    current_visible_bucket = current_visible_bucket->next;
  }
  buckets = s_ObjMgr->activeMap.buckets;
  if ( buckets )
  {
    current_bucket = *buckets;
    sentinel_bucket = &buckets[*(_QWORD *)&s_ObjMgr->activeMap.bucketCount];
    if ( !*buckets )
    {
      if ( ++buckets >= sentinel_bucket )
        goto FINISHED_LABEL;
      while ( 1 )
      {
        current_bucket = *buckets;
        if ( *buckets )
          break;
        if ( ++buckets >= sentinel_bucket )
          goto FINISHED_LABEL;
      }
    }
    while ( 1 )
    {
      do
      {
        ++activeObjects;
        typeCode = s_TypeMap[current_bucket->value->_type];
        if ( (typeCode & 6) != 0 )
        {
          ++itemCount;
        }
        else if ( (typeCode & 0x20) != 0 )
        {
          ++unitCount;
        }
        else if ( (typeCode & 0x100) != 0 )
        {
          ++gameObjectCount;
        }
        current_bucket = current_bucket->next;
      }
      while ( current_bucket );
      if ( ++buckets >= sentinel_bucket )
        break;
      while ( 1 )
      {
        current_bucket = *buckets;
        if ( *buckets )
          break;
        if ( ++buckets >= sentinel_bucket )
          goto FINISHED_LABEL;
      }
    }
  }
FINISHED_LABEL:
  waitToBeFreed = s_ObjMgr->waitingToBeFreedCount;
  actorCount = 0;
  iterateActors((unsigned __int8 (__fastcall *)(__int64, __int64))onActorFn, 0i64);
  s_DebugPrintln(7i64, "Object manager list status: (use gmvision to see server onlys)");
  s_DebugPrintf(7u, "    Active objects:    %u (%u visible)", activeObjects, visibleObjects);
  s_DebugPrintf(
    7u,
    "    Units: %u,   GameObjs: %u    Items: %u,    Other: %u Actors: %u",
    unitCount,
    gameObjectCount,
    itemCount,
    activeObjects - gameObjectCount - unitCount - itemCount,
    actorCount);
  s_DebugPrintf(7u, "    Objects waiting to be freed: %u objects", waitToBeFreed);
  return 1i64;
}

Otherwise, on the Rust note I have had an awesome experience with it so far and it has really helped me make the step from just low level system access to the game's client to a full fledged ergonomic api.
Additionally, I've been building a general video game modding ecosystem with Rust, and am excited to shared my 'Pyres' project soon. Think curseforge for mods. Pyres provides a platform handling all the injection (dll/so/android-bionic), and will intelligently provide you a thread safe environment for updating/rendering your mods. Here is the cool part, by the power of webassembly my hopes are that third party developers will be able to provide Rust lang bindings for games d3, skyrim, minecraft, runescape, etc... and with some proc macros and boilerplate the libraries should be compilable to a webassembly dist allowing for scripting to be done in any language which compiles to webassembly (python, javascript, ever expanding). Pyres bootstrap alongside providing a hub for thread safe updating/rendering will also have the ability to provision a web assembly runtime in the game and load custom scripts.

the ideal vision, is a general video game modding scene where more seasoned developers can build low level system bindings and handle all the nitty gritty and allow for hobbiest, new programmers, and kids to play around with programming in a more fun way. Obviously its going to be disliked for multiplayer games, but Pyres will simply be an open source third party mod loader if someone wants to provide system bindings for wotlk classic on their own repo go ham.

windows:
GitHub - ohchase/shroud: Universal Windows library for discovering common render engines functions. Supports DirectX9 (D3D9), DirectX10 (D3D10), DirectX11 (D3D11), DirectX12 (D3D12).
GitHub - ohchase/yai: Yet Another Injector for windows dlls supports x32 and x64

unix/android:
GitHub - ohchase/plt-rs: Rust library for iterating and hooking linux and android applications PLT (Procedure Linkage Table) at runtime
GitHub - ohchase/ptrace-do: Featureful library for interacting with unix processes through ptrace, supports x86_64, i686, arm, aarch64 remote function calls
Page not found . GitHub . GitHub (soon, yet another unix injector)

[thateuler]

Thanks for this. Very nice.

It seems that the hash table is reasonably balanced. Using wrath and standing in ghostlands i get these numbers.

- 1024 buckets
- 186 objects
- 1 bucket w/ 3 objects
- 11 buckets w/ 2 objects
- 161 buckets w/ 1 object

struct omObj *
get_obj(wGUID guid) {

    uint32_t k2 = 0xA2AA033B * guid.high;
    uint32_t k1 = 0xD6D018F5 * guid.low;
    uint32_t index = (k1 + k2) & ((*ps_curMgr)->numslots - 1);

    struct hashent *pent;
    for(pent = (*ps_curMgr)->slots[index]; pent != NULL; pent = pent->next) {
        if (pent->obj->guid.low == guid.low && pent->obj->guid.high == guid.high) {
            return pent->obj;
        }
    }

    return NULL;
}

I guess that the number of buckets is always a power of 2 hey. If so then `& (num_buckets - 1)` == `% num_buckets`.

Seems that this info was known back in 2019 https://www.ownedcore.com/forums/wor...t-manager.html (8.2.5.32028 Object Manager)

[_chase]

Just wanted to flag, rust 1.70 added alignment checks to pointers. the hashmap doesn't always align values to 0x08 so there is panics on rust 1.69+ for unaligned value access (buckets are all aligned, the value references are not always aligned).
Will need to figure out how to make this work, but until then just stick to 1.69-

Don&#39;t check for misaligned raw pointer derefs inside Rvalue::AddressOf by saethlin . Pull Request #112026 . rust-lang/rust . GitHub

[Glitt]

Just wanted to flag, rust 1.70 added alignment checks to pointers. the hashmap doesn't always align values to 0x08 so there is panics on rust 1.69+ for unaligned value access (buckets are all aligned, the value references are not always aligned).
Will need to figure out how to make this work, but until then just stick to 1.69-

Don't check for misaligned raw pointer derefs inside Rvalue::AddressOf by saethlin . Pull Request #112026 . rust-lang/rust . GitHub

I'm still slightly confused at the rig described through all of this. Is it essentially to mimic a code structure that allows the ability to query the object collection that the client maintains from its own firing of the EVO callback (via hash)? It seems ideal, but for the sake of simplicity because I can't yet figure this out, I do want to say it is possible to call a method to get the exact object you are looking for (ending the callback pulse there) without doing strange things like searching by name or creating your own temp collection or non-demand pulses. With a little care it's then possible to use thread safety. Not really a brag post or anything but it is exciting to see overtime my complexity simplifying and proper handling of objects improving. Your work inspired these changes in me so thank you now that my OM is rougly 3x faster.

Aight peace!

[_chase]

I'm still slightly confused at the rig described through all of this. Is it essentially to mimic a code structure that allows the ability to query the object collection that the client maintains from its own firing of the EVO callback (via hash)? It seems ideal, but for the sake of simplicity because I can't yet figure this out, I do want to say it is possible to call a method to get the exact object you are looking for (ending the callback pulse there) without doing strange things like searching by name or creating your own temp collection or non-demand pulses. With a little care it's then possible to use thread safety. Not really a brag post or anything but it is exciting to see overtime my complexity simplifying and proper handling of objects improving. Your work inspired these changes in me so thank you now that my OM is rougly 3x faster.

Aight peace!

Happy to hear you found a performance boost and were able to get it implemented into your project.
On the topic of what this does;

So same way you had your world pulse HashMap<Guid, Entity> you would reupdate, the client does as well.
HashMaps all work the same generally. A list of Linked List head nodes in a finite array. Obtaining that list of linked list head nodes is where all the offsets come in.
Once we have the map (list of linked list head nodes), all we need to do now is understand how the client decided to convert the guid into an index into that list of linked list head nodes.
Reversing the hash algorithm lets us convert the guid to an array index in the same tongues the client does.
We go to the index and the target entity/value is either at that linked list head node, or like any other hashmap if its not there we gotta just iterate that list.
Since the hashing algorithm is consistent, that guid will HAVE to be at that same index no matter what. A good hashing algorithm makes sure it spreads out the keys/guids it expects into a lot of indexes spread evenly.
This way most of the time the entity is just right at the head, but still say generally the lists are 2-3 nodes still much better than having to go over every list node and its children and manually compare guids.
Now we know the short cut, and can jump right to a bucket and know the entity owning that guid is contractually obligated by mafs to always be in that bucket.

[unsigned]

Could anyone possibly share a struct for GUIDs? stumped at the moment as things like players / items work fine with retrieving bucket index but things like units & game objects don't?

https://i.imgur.com/dInVxcu.png

e.g. above, seems like Items & container types work but other units don't.

Still learning & appreciate any information I can get. Here are my current structs:

struct WoWGUID {
	uint32_t high;
	uint32_t low;

	bool empty() {
		return high == 0 && low == 0;
	};

	bool operator!=(const WoWGUID& a) const {
		return (this->high != a.high && this->low != a.low);
	};

	bool operator==(const WoWGUID& a) const {
		return (this->high == a.high && this->low == a.low);
	};

	uint32_t getIndex(const uint32_t maxObjects) const {
		uint32_t k1 = 0xD6D018F5 * high;
		uint32_t k2 = 0xA2AA033B * low;
		return (maxObjects - 1) & (k1 + k2);
	};
};

class ObjectGame
{
public:
	char pad_0000[16]; //0x0000
	uint8_t type; //0x0010
	char pad_0011[7]; //0x0011
	WoWGUID guid; //0x0018
	char pad_0020[128]; //0x0020
	uint32_t flags; //0x00A0
	char pad_00A4[100]; //0x00A4
	D3DXVECTOR3 position; //0x0108
	char pad_0114[288]; //0x0114
}; //Size: 0x0234

[Razzue]

Could anyone possibly share a struct for GUIDs? stumped at the moment as things like players / items work fine with retrieving bucket index but things like units & game objects don't?

https://i.imgur.com/dInVxcu.png

e.g. above, seems like Items & container types work but other units don't.

Still learning & appreciate any information I can get. Here are my current structs:

struct WoWGUID {
	uint32_t high;
	uint32_t low;

	bool empty() {
		return high == 0 && low == 0;
	};

	bool operator!=(const WoWGUID& a) const {
		return (this->high != a.high && this->low != a.low);
	};

	bool operator==(const WoWGUID& a) const {
		return (this->high == a.high && this->low == a.low);
	};

	uint32_t getIndex(const uint32_t maxObjects) const {
		uint32_t k1 = 0xD6D018F5 * high;
		uint32_t k2 = 0xA2AA033B * low;
		return (maxObjects - 1) & (k1 + k2);
	};
};

class ObjectGame
{
public:
	char pad_0000[16]; //0x0000
	uint8_t type; //0x0010
	char pad_0011[7]; //0x0011
	WoWGUID guid; //0x0018
	char pad_0020[128]; //0x0020
	uint32_t flags; //0x00A0
	char pad_00A4[100]; //0x00A4
	D3DXVECTOR3 position; //0x0108
	char pad_0114[288]; //0x0114
}; //Size: 0x0234

Close, 2x int 64 or an int128
Trinity GitHub has a good example