New possible memorytable replacement

[SpiralV]

I guess 0x8 looks forward and 0x0 backward (in ID direction) if the id is skipped then it searched backwards, works like a trap.
I've looked in the assembler code and I thought it could be.

Code: Select all

005E3F6F - CC                         - int 3 
005E3F70 - 8B 51 04                   - mov edx,[ecx+04]
005E3F73 - 8B 42 04                   - mov eax,[edx+04]
005E3F76 - 83 EC 10                   - sub esp,10
005E3F79 - 80 78 15 00                - cmp byte ptr [eax+15],00
005E3F7D - 56                         - push esi
005E3F7E - 57                         - push edi
005E3F7F - 8B 7C 24 20                - mov edi,[esp+20]	
005E3F83 - 75 16                      - jne 005E3F9B
005E3F85 - 8B 37                      - mov esi,[edi]
005E3F87 - 39 70 0C                   - cmp [eax+0C],esi   ---copare current ID
005E3F8A - 7D 05                      - jnl 005E3F91
005E3F8C - 8B 40 08                   - mov eax,[eax+08]  ---0x8
005E3F8F - EB 04                      - jmp 005E3F95
005E3F91 - 8B D0                      - mov edx,eax
005E3F93 - 8B 00                      - mov eax,[eax]         ---0x0
--EAX=022427E0 EDX=0B07A240 EBP=78177664 EBX=7C809F91 ESI=0009771C ESP=0012D318 ECX=022BF650 EDI=0012D358 EIP=005E3F95
005E3F95 - 80 78 15 00                - cmp byte ptr [eax+15],00
005E3F99 - 74 EC                      - je 005E3F87
005E3F9B - 8B 41 04                   - mov eax,[ecx+04] 
005E3F9E - 3B D0                      - cmp edx,eax
005E3FA0 - 89 54 24 0C                - mov [esp+0C],edx
005E3FA4 - 89 4C 24 08                - mov [esp+08],ecx
005E3FA8 - 74 0D                      - je 005E3FB7
005E3FAA - 8B 37                      - mov esi,[edi]
005E3FAC - 3B 72 0C                   - cmp esi,[edx+0C]
005E3FAF - 7C 06                      - jnge 005E3FB7
005E3FB1 - 8D 4C 24 08                - lea ecx,[esp+08]
005E3FB5 - EB 0C                      - jmp 005E3FC3
005E3FB7 - 89 4C 24 10                - mov [esp+10],ecx	
005E3FBB - 89 44 24 14                - mov [esp+14],eax
005E3FBF - 8D 4C 24 10                - lea ecx,[esp+10]
005E3FC3 - 8B 11                      - mov edx,[ecx]
005E3FC5 - 8B 44 24 1C                - mov eax,[esp+1C]
005E3FC9 - 8B 49 04                   - mov ecx,[ecx+04]
005E3FCC - 5F                         - pop edi
005E3FCD - 89 10                      - mov [eax],edx
005E3FCF - 89 48 04                   - mov [eax+04],ecx
005E3FD2 - 5E                         - pop esi
005E3FD3 - 83 C4 10                   - add esp,10
005E3FD6 - C2 0800                    - ret 0008
005E3FD9 - CC                         - int 3 

and more good news if ID does not exist then the search goes into an table end, I feared it running into an endless loop.
in the meantime I have written a new memorytable.lua for testing and on my 3 pcs it works very well.

edit: I've removed some useless stuff

[rock5]

Great!

A few points though.

1. Administator removed all "proc"s and replaced them with "getProc()". It was causing issues for him with something she was working on apparently. So we should remove that.

2. I would have thought that all we needed to do was to keep the GetItemAddress and GetIdName functions and replace the first part of GetItemId with the guts of your findID function, after getting the start address. Looks like you've done a lot more than that. I can't quite follow it all. Looks like you are doing more than what you were doing in just findID.

BTW, I tested every curent id in the cache file with the original findID and they all returned an address. So it 100% works. There were over 108000 ids.

[rock5]

This is how I would have done it using your original findID function.

memorytable.lua

(2.32 KiB) Downloaded 135 times

Did I miss anything?

[SpiralV]

This is how I would have done it using your original findID function.

memorytable.lua

Did I miss anything?

ah now I see the differences
hmm only one thing the performance

I thought is a good idea to use a cache there are several reasons for a cache tabe (IdAddressTables i=id v=IdAddressLine)
- the search starts from the nearest known address (it can be started from any IdAddressLine)
- save the addresses during the searching process
- and finally to give fast answer

I have also considered what happens if the ID not exists. could not be could be I'm not sure.

[rock5]

ah now I see the differences
hmm only one thing the performance

Yeh like I said. But it's still very fast. What did I say, 0.008 seconds per search? Sure it's might be faster if you find the closest of the 27 addresses but is it really worth the added complexity and difficulty to maintain?

I have also considered what happens if the ID not exists. could not be could be I'm not sure.

Easy to test. Just try "GetIdName(badid)" and see what happens. It's easy to add a check then. For instance I tested mine with a bad id and just got the "Failed to find correct address in range" message. No crashing.

So what are these changes you made to the findid function? I see you added "if dataPointer % 0x10000 ~= 0 then". I'm not sure what that means. And this line "if offset8 == 0x708 or offset8 == 0x424 then". Does this mean the end is always one of those numbers?

[SpiralV]

Yeh like I said. But it's still very fast. What did I say, 0.008 seconds per search? Sure it's might be faster if you find the closest of the 27 addresses but is it really worth the added complexity and difficulty to maintain?

I understand but it's so funny to play around with the lua tables^^

So what are these changes you made to the findid function? I see you added "if dataPointer % 0x10000 ~= 0 then". I'm not sure what that means.

dataPointer % 0x10000 == 0 hits every multiple of 0x10000 usually ends the memory table here but I've never seen the print output so it's not necessary.

And this line "if offset8 == 0x708 or offset8 == 0x424 then". Does this mean the end is always one of those numbers?

Yes forward and backward in the object file string.

[rock5]

Ok so I finally tested the files with a script. I ran my version with my Course of Terror(cot) script but it didn't work. It kept going past the waypoints and not stopping. I had to restart the script each time I entered the room. So I guess the worse performance is an issue. Unless there's a bug in it somewhere.

Your version worked perfectly. I really wish I could follow it better. Am I right in thinking it collects ids and addresses that it encounters to improve future searches? How much does it improve searches of ids it hasn't found before? How big can the table get over prolonged use?

Is there any chance you could go over your file and tidy it up a bit and add a few more comments explaining the steps of what's happening?

[rock5]

edit: I've removed some useless stuff

I just tested this version and if I use an invalid id it gets stuck.

[rock5]

Here's a shorter version of "findnearestIDAddress".

Code: Select all

	 local function findnearestIDAddress(_id)
		local closestID
		for i,v in pairs(IdAddressTables) do
			if closestID == nil or math.abs(_id - i) < math.abs(_id - closestID) then
				closestID = i
			end
		end

		return IdAddressTables[closestID]
	end

[rock5]

edit: I've removed some useless stuff

I just tested this version and if I use an invalid id it gets stuck.

I spoke too soon. I added print statement for "currentID" on line 12 and this was the out put. It got stuck but eventually came back.

Code: Select all

        RomBot command line
Type in 'q' (without quotes) to quit.
Command> GetItemAddress(539999)
540567
513071
520567
540055
521079
521335
530100
530356
530484
530612
530676
540023
530708
540007
530724
530740
530748
540003
530752
540001
530754
540000
530755
207771407
5631152
-858993460
>>>>==== GOT STUCK HERE FOR ABOUT 5 MIN
nil
current ID not number
ID 539999 not found
Command>

Not sure what it means. I note that 530755 is the last id in that range.

Ok this works. Replace line 12 with this

Code: Select all

			if type(currentID) ~= "number" or currentID < 1 or currentID > 999999 then

[SpiralV]

Here's a shorter version of "findnearestIDAddress".

great ty
I think that's not enough, these numbers are not ids
207771407
5631152
but the table end at 0x8 is 0x428 and not 0x708 or 0x424. seems to be random. after I restarted the client , it's another number 0x424 again hm but 0x0 is the same 0x96d184.
and it's not a pointer. I check this on a different computer.
edit: ah sry I forgot to say that means the search running out of an id-address-range.

[rock5]

Those offsets are normally addresses right? Addresses have to be at least a certain size. So why not just say

Code: Select all

if offset8 < minimumrealisticaddress then end of table

?

Edit 1: I found one of those end table values, it was 0x3C8. So it looks like you can't count on it being any certain values.

Edit 2: Tried

Code: Select all

if offset8 < 0x100000 then dataPointer = 0 printf("End of Table\n") break end

That worked. It said

Code: Select all

End of Table
ID 539999 not found

Which is what you want it to say right? That way you know it has looked through the whole table.

[rock5]

Noticed another thing. You don't need to call findID just to initialize the table. Just do this,

Code: Select all

	if not IdAddressTables then
		local tablePointer = memoryReadIntPtr( getProc(), addresses.tablesBase, addresses.tablesBaseOffset )
		local startAddressOffsets = {0,addresses.tableStartPtrOffset, addresses.tableDataStartPtrOffset}
		
		local dataPointer = memoryReadIntPtr( getProc(), tablePointer, startAddressOffsets) - Line
		local id = memoryReadIntPtr(getProc(), dataPointer + addresses.idOffset )

		IdAddressTables = {[id] = dataPointer)
	end

This is using my updated version to get the datapointer.

[rock5]

Done a bit more work on it. I'm just about happy enough with it to commit it. Tell me what you think.

memorytable.lua

(3.34 KiB) Downloaded 163 times

The only thing I'm not really happy with is the IdAddressTables. I'm worried that it could get very large under some circumstances and affect performance. I wish we could do it another way. Maybe I'll do some heavy duty testing to see if it holds up.

[SpiralV]

Done a bit more work on it. I'm just about happy enough with it to commit it. Tell me what you think.

The attachment memorytable.lua is no longer available

The only thing I'm not really happy with is the IdAddressTables. I'm worried that it could get very large under some circumstances and affect performance. I wish we could do it another way. Maybe I'll do some heavy duty testing to see if it holds up.

good work rock good work

I have tried something to find out how the search works
First, the search begins slowly
then comes a jumping point which makes a big jump there is another jumping point makes a bigger jump ... until the id was skipped
then the same in the other direction. I think you're right this is the fastest possible solution to find something in the memory so I think the cache feature makes it slower than faster.
I've tested it I've never seen more than 100 search cycles that's really impressive.

what do you mean?
edit: btw:I am assuming that lua must also search to find a table value

[rock5]

First, the search begins slowly
then comes a jumping point which makes a big jump there is another jumping point makes a bigger jump ... until the id was skipped
then the same in the other direction.

It's still hard to understand but I think I can just about imagine how it works now. Thanks.

I think you're right this is the fastest possible solution to find something in the memory so I think the cache feature makes it slower than faster.
I've tested it I've never seen more than 100 search cycles that's really impressive.

I noticed that too. That's why I was hoping we could just use the search without saving in the table. But when I didn't use the idaddresstable I wasn't able to run my Course of Terror script at all.

what do you mean?

What do you mean "what do you mean"? Are you asking what I was worried about? I'm worries about how large "IdAddressTables" can get. Most likely, for a given waypoint file, you wont be exposed to more than a certain number of ids so it should reach a maximum size and plateau. But I want to test it first. I think, how large it will get will depend on how far reaching a waypoint file is. I'm currently running a test to see how large it gets when grinding for long periods of time. I might also do a test to see how it handles IdAddressTables being very, very large.

[rock5]

Ok so I ran a bot grinding mobs for about 5 hours. During that time I had it print out the size of IdAddressTables on a regular basis. It started at 613 and ended at 1113. It steadily grew the whole time and was still running fine when I stopped it. I'm sure it would have gone higher if I'd left it running longer but this gives me a baseline.

Tomorrow I'll arteficially increase the size of the table to see how large it needs to be before I notice a drop in the bots performance.

[rock5]

I ran it again today while I was away from home. When I got home the IdAddressesTable count was 1172 after about 6 hours. After 8 hours it was 1179. So it looks like it does level off. It was still running fine.

Then I tried initially inflating the table by searching for a bunch of random ids. Wasn't so easy but I managed to get the table to over 5000. It still ran fine. I even ran the Course of Terror script with it at 5000 and it worked fine. Personally I don't think it would ever get to 2000, let alone 5000, in normal use.

During the above tests I discovered that when searching for bad ids, it can get stuck in a loop visiting the same addresses so I had to add a check for that.

I can keep tweaking it till the cows come home so I'm just going to commit it now. Should be up soon.

Thanks SpiralV for your great work. Lots of people will be thanking you when they discover the progress bar is gone.

[rock5]

New memorytables.lua committed in rev 638.

[SpiralV]

looks really good.
I fear we will no longer have problems with memorytable.lua