Author
|
Topic: GBA Pointer searching? (Read 2 times)
|
rmco2003
Guest
|
 |
« on: March 10, 2009, 03:57:18 pm » |
|
I've been working on a GBA project recently, but I've got loads of pointers for text that I need to search for and manually doing it takes a lot of time, is there any way to automate this? The game uses standard GBA pointers, I just need to speed this up a bit, I've tried coding my own utility to search for pointers in a rom but it's painfully slow, I can't think of any other way to search than by comparing the pointer to a 3 byte value and iterating the position every byte which obviously causes a lot of slowdown, it took half an hour to find 5 pointers  |
|
|
|
|
KaioShin
Guest
|
|
« Reply #1 on: March 10, 2009, 04:08:08 pm » |
|
The game uses standard GBA pointers, I just need to speed this up a bit, I've tried coding my own utility to search for pointers in a rom but it's painfully slow, I can't think of any other way to search than by comparing the pointer to a 3 byte value and iterating the position every byte which obviously causes a lot of slowdown, it took half an hour to find 5 pointers 1. Don't read the file byte for byte, use a buffer and work in RAM. 2. The pointers should always be word aligned. If the first byte doesn't match, skip the next 3 right away. |
|
|
|
|
Tauwasser
Guest
|
|
« Reply #2 on: March 10, 2009, 04:45:00 pm » |
|
2. The pointers should always be word aligned. If the first byte doesn't match, skip the next 3 right away.
Not necessarily. For asm etc, yes. But when it comes to the game having it's own subset of features that are not read by multiples of four bytes, e.g. ingame scripting, tables, then it's no good. The worst case for a search is that you have to look at each item, that is byte, once and cannot skip it! So now you can produce a fairly good heuristic in which you check if byte x + 3 is 0x08 or 0x09 (if standard pointers are used) and work from there. Also, once you read four bytes, just have routines do the same checks for the next four and not read again from memory etc. Lots of code, but speeds things up because of the reads. Also, be aware that it is awfully slow and you will get false positives by chance! cYa, Tauwasser |
|
|
|
|
rmco2003
Guest
|
|
« Reply #3 on: March 10, 2009, 05:41:55 pm » |
|
I do work in ram and unfortunately still get the major slowdowns, I've tried various speedups such as not searching from the top of the file for subsequent pointers, etc, but it still is unbelievably slow. The code works perfectly, it just takes so long it's faster to replace it manually even with the very possible chances of human error which I experience on a daily basis with manual pointer hacking :banghead: I coded an inserter for this game in .net which works perfectly as far as dumping + inserting goes, I basically feed in a list of offsets to the pointers themselves and it'll proceed to dump the text and format it into a handy XML file perfect for editing and reinserting, and when it inserts it just uses the offset stored in the file to repoint directly instead of searching for it, this makes inserting much faster and I actually coined the idea from a similar inserter for a older translation project for the game that died out. At my count I have at least 200 blocks of text to manually record pointers for, I might try my hand at coding a utility from scratch to just find pointers, it seems whenever I do it I always end up writing really slow code, so we'll see how it goes  |
|
|
|
|
creaothceann
Guest
|
|
« Reply #4 on: March 10, 2009, 07:05:41 pm » |
|
You could post the code...
|
|
|
|
|
rmco2003
Guest
|
|
« Reply #5 on: March 10, 2009, 07:12:07 pm » |
|
It'd probably fill up the entire server - yes I admit it I write bloated code   [edit] Smaller than I thought, but here's my inserting code for another game using the algorithm (if it can even be called that) I usually go for: Dim f As FolderItem
Dim b As BinaryStream
Const PointerTable = &hA33B38
f = GetOpenFolderItem("")
b = f.OpenAsBinaryFile()
Dim f2 As FolderItem
Dim t As TextInputStream
f2 = GetOpenFolderItem("")
t = f2.OpenAsTextFile()
Dim mb As New MemoryBlock(0)
Dim bs As New BinaryStream(mb)
bs.Write(b.Read(b.Length))
b.Close
bs.Position = Val(txOffset.Text)
Dim done as boolean
Dim dumptext As String
Dim sbracketpos As Integer
Dim offset As Integer
Dim newoffset As Integer
Dim pointer As String
Dim newpointer As String
newoffset = Val(txOffset.Text)
Dim qwe As String = t.ReadAll
t.Close
t = f2.OpenAsTextFile()
Do Until done = True Or t.EOF = True
Progress.Value = (t.PositionB / qwe.LenB) * 100
App.DoEvents
dumptext = t.ReadLine
sbracketpos = InStr(dumptext,"{")
If sbracketpos > 0 Then
offset = Val(dumptext.Left(sbracketpos - 1))
pointer = CalcPointer(offset)
newpointer = CalcPointer(newoffset)
bs.Position = newoffset
dumptext = dumptext.Mid(sbracketpos + 1,dumptext.Len - sbracketpos)
If InStr(dumptext,"}") = 0 Then
Dim temp As String
temp = t.ReadLine
Do Until InStr(temp,"}") > 0
App.DoEvents
dumptext = dumptext + Chr(&h0A) + temp
temp = t.ReadLine
Loop
dumptext = dumptext + Chr(&h0A) + temp.Left(temp.Len - 1)
Else
dumptext = dumptext.Mid(1,dumptext.Len - 1)
End If
bs.Write(dumptext)
bs.Position = PointerTable
Dim found As Boolean
Do Until found = True Or bs.EOF = True
Progress2.Value = (bs.Position / bs.Length) * 100
App.DoEvents
Dim b1, b2, b3 As Byte
Dim t1, t2, t3, cont As String
b1 = bs.ReadByte
b2 = bs.ReadByte
b3 = bs.ReadByte
t1 = Hex(b1)
t2 = Hex(b2)
t3 = Hex(b3)
If t1.Len = 1 Then t1 = "0" + t1
If t2.Len = 1 Then t2 = "0" + t2
If t3.Len = 1 Then t3 = "0" + t3
cont = t1 + t2 + t3
If cont = pointer Then
bs.Position = bs.Position - 3
found = true
End If
Loop
If found = True Then
bs.WriteByte(Val("&h" + newpointer.Left(2)))
bs.WriteByte(Val("&h" + newpointer.Mid(3,2)))
bs.WriteByte(Val("&h" + newpointer.Right(2)))
newoffset = newoffset + 1 + dumptext.Len
Else
'couldn't find pointer for this entry of the script dump
beep
End If
Else
done = True 'cannot find bracket, the script has finished or is corrupted
End If
Loop
b = f.CreateBinaryFile("")
bs.Position = 0
b.Write(bs.Read(bs.Length))
b.Close
bs.Close
Return True It's in realbasic, not vb.net which is my current language of choice. |
|
|
|
|
BRPXQZME
Guest
|
|
« Reply #6 on: March 10, 2009, 07:40:32 pm » |
|
I don’t claim to be the sharpest tool in the shed when it comes to optimization, but I have a hunch that you might want to at least use string operations instead this concatenation magic you’re doing...  \ |
|
|
|
|
rmco2003
Guest
|
|
« Reply #7 on: March 10, 2009, 07:47:26 pm » |
|
The concatenation is to rebuild the pointer since realbasic (and vb.net I assume) likes to strip the 0's from decimal numbers forcing me to reconstruct them since I'll be inserting that value into the game.
|
|
|
|
|
BRPXQZME
Guest
|
|
« Reply #8 on: March 10, 2009, 10:55:51 pm » |
|
Okay, so why would you need any of these conversions at all, though? You should only convert to human-readable anything when a human actually needs to be able to read it, or at least outside of tight loops. I don’t know if it’s the root of the problem, but it certainly looks like a source of serious performance hits. Moreover, why would you ever approach things a byte at a time? Block reading and writing functions may not be efficient enough in generic implementations to satisfy true speed freaks, but they certainly have their advantages, not the least of which is comprehensibility. For example, I’d approach this loop specifically:    Do Until found = True Or bs.EOF = True
    Progress2.Value = (bs.Position / bs.Length) * 100
    App.DoEvents
    Dim b1, b2, b3 As Byte
    Dim t1, t2, t3, cont As String
    b1 = bs.ReadByte
    b2 = bs.ReadByte
    b3 = bs.ReadByte
    t1 = Hex(b1)
    t2 = Hex(b2)
    t3 = Hex(b3)
    If t1.Len = 1 Then t1 = "0" + t1
    If t2.Len = 1 Then t2 = "0" + t2
    If t3.Len = 1 Then t3 = "0" + t3
    cont = t1 + t2 + t3
    If cont = pointer Then
     bs.Position = bs.Position - 3
     found = true
    End If
   Loop
like this, and instead of having to compare pointer as some hex value, pointer would just be the actual value. Â Â Â Do Until found = True Or bs.EOF = True
    Progress2.Value = (bs.Position / bs.Length) * 100
    App.DoEvents
    Dim cont As String
    cont = bs.Read(3)
    If cont = pointerBinStr Then
     bs.Position = bs.Position - 3
     found = true
    End If
   Loop
Perfect? Certainly not; I don’t know RealBasic at all and didn’t write code turning pointer into pointerBinStr, and may have even made a syntax error. But at least I know I’m not having to convert a few things over and over and over again all for naught. |
|
|
|
« Last Edit: March 11, 2009, 05:40:38 am by BRPXQZME »
|
|
|
|
rmco2003
Guest
|
|
« Reply #9 on: March 11, 2009, 02:46:35 am » |
|
Now that I think about it that's true I can cut that out completely, that may be one of the main slowdowns in my code.
I'm approaching the searching a byte at a time because for example what if I search at 0x100, but the pointer's actually at 0x101? Yes I could speed things up by jumping 3 bytes at a time but these issues would cause me to miss several pointers.
I don't see any other way to get around this, that's the main problem.
|
|
|
|
|
BRPXQZME
Guest
|
|
« Reply #10 on: March 11, 2009, 03:28:49 am » |
|
No it wouldn’t. If that were an issue, you’d just search three at a time, then add one, then three at a time, then add one, then three at a time, and you’ve searched every possible position  (and it shouldn’t be an issue: refer to the below two posts) |
|
|
|
« Last Edit: March 11, 2009, 05:41:24 am by BRPXQZME »
|
|
|
|
Markliujy
Guest
|
|
« Reply #11 on: March 11, 2009, 03:40:14 am » |
|
1. Don't read the file byte for byte, use a buffer and work in RAM.
2. The pointers should always be word aligned. If the first byte doesn't match, skip the next 3 right away.
I think KaioShin meant that instead of doing the ReadByte stuff all the time, you'd just read the entire file into a string or something, and work from there. And you might want to check the word alignment, might save a fair bit of needless processing time. I'm also thinking it might run better if instead of going through the file for each pointer, you instead put all the pointers you're looking for into an array (or list, or whatever its called), and only go through the file once, deleting each pointer to be found as its found. |
|
|
|
|
KaioShin
Guest
|
|
« Reply #12 on: March 11, 2009, 04:15:20 am » |
|
2. The pointers should always be word aligned. If the first byte doesn't match, skip the next 3 right away.
Not necessarily. For asm etc, yes. But when it comes to the game having it's own subset of features that are not read by multiples of four bytes, e.g. ingame scripting, tables, then it's no good. But he said he is looking for standard GBA pointers, they always have the form xxyyzz08 and they will always be word aligned. The CPU couldn't use those pointers otherwise. You will never find such a pointer at address 0101 to 0104 for example. The CPU can only read from either 0100 or 0104, but not starting from the 3 bytes in between. |
|
|
|
|
rmco2003
Guest
|
|
« Reply #13 on: March 11, 2009, 05:46:16 am » |
|
Right I understand now, so if I searched at 0x100 and it wasn't there, I could skip 4 bytes and then search again since the GBA can't use misaligned pointers? That'd make it 4x faster at least Also fyi I do work in ram which can be seen here: Dim mb As New MemoryBlock(0)
Dim bs As New BinaryStream(mb)
bs.Write(b.Read(b.Length)) That loads the entire rom into ram to be modified/sifted through. |
|
|
|
|
Tauwasser
Guest
|
|
« Reply #14 on: March 11, 2009, 09:25:13 am » |
|
2. The pointers should always be word aligned. If the first byte doesn't match, skip the next 3 right away.
Not necessarily. For asm etc, yes. But when it comes to the game having it's own subset of features that are not read by multiples of four bytes, e.g. ingame scripting, tables, then it's no good. But he said he is looking for standard GBA pointers, they always have the form xxyyzz08 and they will always be word aligned. The CPU couldn't use those pointers otherwise. You will never find such a pointer at address 0101 to 0104 for example. The CPU can only read from either 0100 or 0104, but not starting from the 3 bytes in between. They don't need to be word-aligned for code that isn't word-aligned ( not talking ASM/thumb!, but ingame scripting etc). I've seen it before (e.g. Pokemon Advanced) so while the advice is fairly good, it might not serve its purpose. Also, the pointers can end with 0x09 if you have a really large rom (over 0x01000000 bytes obviously). You are right if you talk about asm code that directly uses the pointers, but it wasn't said if that is the case, especially now that was posted that pointers were found at 0x101 for instance. cYa, Tauwasser |
|
|
|
|
|
