Cheat Engine Forum Index Cheat Engine
The Official Site of Cheat Engine
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 


What data structure would you use to store addresses?

 
Post new topic   Reply to topic    Cheat Engine Forum Index -> General programming
View previous topic :: View next topic  
Author Message
horsedeg
Cheater
Reputation: 0

Joined: 26 Jun 2017
Posts: 27

PostPosted: Tue Sep 05, 2017 11:01 am    Post subject: What data structure would you use to store addresses? Reply with quote

To specify (since there's not very much room in the title) I'm talking about scanning regions of memory multiple times, like how Cheat Engine does with the initial scan, then scanning next a couple times. An array or vector doesn't sound good. Ideally it should be a linked list or something, right? Because removing individual nodes sounds better than the array-style of removing.

Or is there something specific with WinAPI that people use?
Back to top
View user's profile Send private message
ParkourPenguin
I post too much
Reputation: 138

Joined: 06 Jul 2014
Posts: 4275

PostPosted: Tue Sep 05, 2017 2:18 pm    Post subject: Reply with quote

An array/vector wouldn't be bad if you removed elements correctly. If you erase elements one at a time moving all further elements each time, that would take O(n^2) time, which isn't good. Instead, partitioning the array by sending to-be-removed elements to the back (O(n) time) and then erasing all those elements at once (O(1) time) would give you the same complexity as a linked list without the memory overhead.
https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom

You could also look at CE's source and see what it does.

_________________
I don't know where I'm going, but I'll figure it out when I get there.
Back to top
View user's profile Send private message
atom0s
Moderator
Reputation: 198

Joined: 25 Jan 2006
Posts: 8516
Location: 127.0.0.1

PostPosted: Tue Sep 05, 2017 9:42 pm    Post subject: Reply with quote

Which language are you coding in?
_________________
- Retired.
Back to top
View user's profile Send private message Visit poster's website
horsedeg
Cheater
Reputation: 0

Joined: 26 Jun 2017
Posts: 27

PostPosted: Tue Sep 05, 2017 11:13 pm    Post subject: Reply with quote

atom0s wrote:
Which language are you coding in?

C++.
I'm trying to write my own memory scanner based off the really basic one you gave me. I've got a really crappy one working. I'm understanding your code now, though. Basically you're using the MEMORY_BASIC_INFORMATION struct to get a relatively small section of the memory region in a loop, check each address, then iterate to the next section of memory until the max address is reached. I understand that, but how should I hold the found addresses afterwards? Do I need to use MBI at all afterwards? Or is that just for large amounts of memory so it doesn't use too much RAM?
Temporarily I've just put a vector to hold those addresses in a whole new loop after the initial one, but obviously that's not optimal. I mean, it works, I'd just like to expand it, and also the way I'm erasing addresses from the vector is probably not optimal. What ParkourPenguin said might work well.
Back to top
View user's profile Send private message
atom0s
Moderator
Reputation: 198

Joined: 25 Jan 2006
Posts: 8516
Location: 127.0.0.1

PostPosted: Wed Sep 06, 2017 12:28 am    Post subject: Reply with quote

It depends on how you plan on using the scanner. If it is to replicate what CE does and be used in various programs and min/max address ranges, you will probably want to resort to holding results in files rather than memory like CE does.

For small areas of memory, a vector or linked list would be fine. If you are using multiple threads, keep in mind that most of the STL objects are not thread safe on their own. C++'s STL objects are thread safe for reading, but not for writing. The rule set is:
- Multiple concurrent reads on the same container are ok.
- Multiple concurrent writes on the same container are not ok.
- If there is any writing being done to a container, there cannot be any reads or other writes.

There are easy ways to create a class that holds a vector and make it thread safe using things like a mutex, lock guards, etc. if you decide to go that route.

CE's scanning handlers can be found here:
https://github.com/cheat-engine/cheat-engine/blob/master/Cheat%20Engine/memscan.pas
https://github.com/cheat-engine/cheat-engine/blob/master/Cheat%20Engine/SaveFirstScan.pas
https://github.com/cheat-engine/cheat-engine/blob/master/Cheat%20Engine/savedscanhandler.pas

Dark Byte can better explain the specifics of how CE does its file setup if you have more specific questions about it.

_________________
- Retired.
Back to top
View user's profile Send private message Visit poster's website
dl748
Advanced Cheater
Reputation: 0

Joined: 05 Mar 2016
Posts: 75

PostPosted: Wed Sep 06, 2017 10:12 am    Post subject: Reply with quote

depending on what you are using the addresses for

std::vector
std::forward_list
std::list
std::stack
std::queue

Unlike above, i recommend you not to use array's they are static and can't be dynamically resized with ease.
Back to top
View user's profile Send private message
Dark Byte
Site Admin
Reputation: 457

Joined: 09 May 2003
Posts: 25262
Location: The netherlands

PostPosted: Wed Sep 06, 2017 11:53 am    Post subject: Reply with quote

cpus work better if they have to deal with small contiguous chunks of memory as opposed to randomly located memory objects. So if it's about speed, I do recommend static sized arrays and flush them to the disk when full (async)
_________________
Do not ask me about online cheats. I don't know any and wont help finding them.

Like my help? Join me on Patreon so i can keep helping
Back to top
View user's profile Send private message MSN Messenger
horsedeg
Cheater
Reputation: 0

Joined: 26 Jun 2017
Posts: 27

PostPosted: Wed Sep 06, 2017 2:10 pm    Post subject: Reply with quote

What is async? From what I see on Google it has to do with threads and was introduced in C++11. I know nothing about multithreading, but I can learn it, and I suppose it'd be important when handling large amounts of memory.
So I'm guessing what you're saying is to use async to call the function that flushes the array to disk?

Also, what could I use to store files onto disk? There's always ifstream and ofstream, but I'd like them to be temporary. I suppose I could somehow get them to delete on closing of the program or when a new scan is started, but if the program is ended abruptly then it might keep the files.
Back to top
View user's profile Send private message
atom0s
Moderator
Reputation: 198

Joined: 25 Jan 2006
Posts: 8516
Location: 127.0.0.1

PostPosted: Wed Sep 06, 2017 4:43 pm    Post subject: Reply with quote

If you are doing everything through STL methods you can use the various streams. Otherwise, there is the 'f' functions such as 'fopen, fclose, fread, fwrite, etc.' or straight OS level API such as CreateFile/ReadFile/WriteFile, etc on Windows.
_________________
- Retired.
Back to top
View user's profile Send private message Visit poster's website
horsedeg
Cheater
Reputation: 0

Joined: 26 Jun 2017
Posts: 27

PostPosted: Wed Sep 06, 2017 11:08 pm    Post subject: Reply with quote

So I've been learning to use fread, fwrite, fopen, and fclose. It's going well, and I've learned how I can store memory addresses into a file (like a .bin). I'm just thinking there might be a problem when trying to read the files.

Ideally I'd make an array with a size of 1000 for example, have an int variable to keep track of how many I've found so far. If it reaches 1000, the array is full, so put all the addresses into a file using fwrite with "ab" to append the file rather than writing it from the start ("wb"). That sounds like it works, but what about when I have to use the addresses for a next scan? I can use fread, but if I want to, say, take out the first 1000 addresses out of a total of 20,000 in the first iteration of a loop, put them in an array and scan them, then delete it (assuming what I'm looking for isn't in any element), how do I delete those first 1000 addresses from the file, without deleting the whole thing?
Back to top
View user's profile Send private message
atom0s
Moderator
Reputation: 198

Joined: 25 Jan 2006
Posts: 8516
Location: 127.0.0.1

PostPosted: Wed Sep 06, 2017 11:32 pm    Post subject: Reply with quote

Generally, you are going to have to use multiple files to handle deleting parts that are mid-file. You can set the file pointer with the 'f' functions via 'fseek', read the data you need and so on. Then write the data to keep into a 2nd file. The rescan can do the same each step of the way writing to a new file as needed. Your scanner can keep track of which file is currently in use, and where to start reading from via the file pointer etc.
_________________
- Retired.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Cheat Engine Forum Index -> General programming All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2005 phpBB Group

CE Wiki   IRC (#CEF)   Twitter
Third party websites