[Dxbx status] API detection (part 2)

[patrickvl]

A little update in Dxbx progress for those of you lurking around here regularly

Now that we've got another method of API function detection working, I've spend some more time on it.

The current approach has the disadvantage that it's using a data structure that's not really space-efficient. Function patterns have much overlap in common, and the "don't care" bytes in there are also taking up precious space. With the current approach, I estimate that we would need about 50 MiB to store the patterns of just the 6 or 7 most important libraries from all XDKs in existence. (Which are 23 versions if I'm not mistaken).

Because of this, I'm now working on building up a much more compact structure, that will hold the same patterns in about 1/10th the space. Key to this is, to store shared parts only once, leaving all the "don't care" bytes away (by just telling how many of them there are) and by referring to a string-table, so no string appears more than once.

As an additional step, I'm considering to compress the strings in the same way as the patterns, by using a suffix-trie. But that's not very high on my priority-list right now.

The nice thing about all this is, that it not only reduces the volume of the pattern-data, but at the same time speeds up pattern-detection!

Please read the links I provided, (including this one) it will help you understand the algorithms involved. Cheers!

---

Last edited by patrickvl; August 14th, 2008 at 12:48.

[shogun_nihon]

Really interesting the progress you´ve made.

[dreampeppers99]

Dxbx is going well!

__________________
OS: Windows XP Professional SP3 (32bits)
CPU: Athlon XP 2400+ (2.0 Ghz) (non SSE2)
Graphics Card: ATI X1650 Pro 512MB
Memory: 1GB DDR

[Frog186]

To Shadow-tj and Patrickvl
Hi guys it's Frog once again I just wanted to ask what can I help you both as a job for the xbox emulator I am still interested don't worry even though I am not an expert or professional I still want to help just tell me what to do and I will try my best in helping out also in the process of fooling around with java programming language I found a good compiler for that so what have you guys been up to recently? also how are you guys doing in general? I am doing good for now just busy doing other things at the moment well get back to me don't worry I am not in a hurry or a rush but let me know for sure what's going on and great luck on everything you both are doing well I will talk with you later on see ya later!

[patrickvl]

Originally Posted by Frog186

I just wanted to ask what can I help you

Hi Frog, thanks for offering your help (again) - I can't really tell you what to do. In my previous reply I already suggested that we would best be helped by people that can help in translating the C++ sources of Cxbx over to Delphi.

Surely, anyone working on that will need to have Delphi (2007) installed, must have good knowledge about both programming languages, and should have enough experience in translating code.

The point is, that even though we indeed would appreciate any help we can get here, we also need people to be self-supporting - because else it would take us way too much time; Time we could better spend on our own tasks.

So if you spot a task that suits you, just tell us and start doing your thing.

so what have you guys been up to recently?

For this, I'd recommend you read the regular status updates we post here on NGEmu, and you could also keep an eye on the changes we submit to the Dxbx sourcecode archive, over at sourceforge.

also how are you guys doing in general?

Fine, thanks


But, Frog, I do want to ask you to write shorter sentences and use punctuation, so to make your posts more readable. Much appreciated if you do.

[patrickvl]

I've been making good progress - the new radix trie-based approach for detecting functions is starting to work!
However, I'm not yet happy with the quality of the code, so I guess it'll be another few days before I submit this to the SVN.

In the mean time I've recuited a new member for the project : Max.
Max is very experienced in translating C to Delphi, and I'm really happy he joined us!
Let's see what he comes up with!

PS: Hasn't anybody noticed yet that blueshogun uploaded his own private copy of his patched-up Cxbx sources?!? He's added a lot of code - I think we (the Dxbx team) will be working with his code as our base for translation. Cheers mate!

[shogun_nihon]

Originally Posted by patrickvl

In the mean time I've recuited a new member for the project : Max.
Max is very experienced in translating C to Delphi, and I'm really happy he joined us!
Let's see what he comes up with!

Great the team is getting bigger and bigger, now shodow_tj isn´t alone with the translation.

Originally Posted by patrickvl

PS: Hasn't anybody noticed yet that blueshogun uploaded his own private copy of his patched-up Cxbx sources?!? He's added a lot of code - I think we (the Dxbx team) will be working with his code as our base for translation. Cheers mate!

Yeah I noticed!!!

__________________
私はヴェクター·インダストリー製,対グノーシス専用ヒト型掃討兵器,KOS-MOS Ver.4です

CV:鈴木 麻里子(すずき まりこ)

"Yo, hecha por la Industria Vector, para uso exclusivo contra GNOSIS, humanoide de armas arrasadoras, soy KOS-MOS version 4".

スゴイ麻里子さん、あなたの声が大好きですよ。
http://www.aoni.co.jp/actress/sa/suzuki-mariko.html

[snickothemule]

Great to hear that you are reaching some of your targets with your project and keeping us updated is greatly appreciated and interesting to read. It is also great to hear that there is a new member to the project.

Awesome that blueshogun uploaded his work.

__________________

"If you wish to make an apple pie truly from scratch, you must first invent the universe." - Carl Sagan

---

Last edited by snickothemule; August 20th, 2008 at 04:23.

[patrickvl]

Rather than laying back on the changes I'm working on, I've decided to submit them already (even though there are still a few rough edges).
I do so because of a short holiday, and I'd like people to look into the change I've made up 'till now.

In this new revision, the function-detection works again, but much faster.
Although I should note that the actual library versions aren't taken into account yet, we now detect 1243 functions in Turok. Even though some of those are false hits, it's really shaping up now!

Some of this is because 21 pattern files where added in the same revision too, while still shrinking the size of our DLL with about 2 MB (!)
A nice property of this trie of function patterns is, that adding more functions will decrease the additional storage costs! This is, because for every new addition there's a bigger chance that large chunks of this pattern are already in the trie. I estimate that average storage costs will rapidly shrink to around 16 bytes per added function pattern.

Don't hesitate to ask if you want to know more about this. Cheers!

[shogun_nihon]

Originally Posted by patrickvl

Rather than laying back on the changes I'm working on, I've decided to submit them already (even though there are still a few rough edges).
I do so because of a short holiday, and I'd like people to look into the change I've made up 'till now.

In this new revision, the function-detection works again, but much faster.
Although I should note that the actual library versions aren't taken into account yet, we now detect 1243 functions in Turok. Even though some of those are false hits, it's really shaping up now!

Some of this is because 21 pattern files where added in the same revision too, while still shrinking the size of our DLL with about 2 MB (!)
A nice property of this trie of function patterns is, that adding more functions will decrease the additional storage costs! This is, because for every new addition there's a bigger chance that large chunks of this pattern are already in the trie. I estimate that average storage costs will rapidly shrink to around 16 bytes per added function pattern.

Don't hesitate to ask if you want to know more about this. Cheers!

Lets see if I get it, thats the way you are emulating the XBOX kernel functions? You catch the system calls made to Xbox kernel and then tranlate it to windows system calls?

__________________
私はヴェクター·インダストリー製,対グノーシス専用ヒト型掃討兵器,KOS-MOS Ver.4です

CV:鈴木 麻里子(すずき まりこ)

"Yo, hecha por la Industria Vector, para uso exclusivo contra GNOSIS, humanoide de armas arrasadoras, soy KOS-MOS version 4".

スゴイ麻里子さん、あなたの声が大好きですよ。
http://www.aoni.co.jp/actress/sa/suzuki-mariko.html

[patrickvl]

Originally Posted by shogun_nihon

Lets see if I get it, thats the way you are emulating the XBOX kernel functions? You catch the system calls made to Xbox kernel and then tranlate it to windows system calls?

Well, yes and no, actually.

Yes, we're planning on implementing most of the Xbox kernel API's by redirecting them to the corresponding win32 kernel API's.
But no, that's not what the function detection is for.

Let me explain some more by first giving you an overview of the Kernel API patching :

Inside an XBE (Xbox executable) file, the kernel API's are already present in a structure called a 'Thunk table'.
So, to 'patch' the Xbox kernel API's, all we have to do is overwrite the thunk table with our own version. Following that, we need provide the implementation for each API in that table, although as-of now, in Dxbx, most of these are nothing more than empty stubs.
Cxbx has implemented quite a few of them already, so all we have to do is translate that from C to Delphi (yeah, I know, I make it sound like an easy thing, but trust me : It's not!).

Now, back to the function detection I've been writing about for the past few days :

Apart from calling into the Xbox kernel, games also contain so-called library functions. These functions are linked into the executable, and have their origin in some version of an Xbox Development Kit (XDK).
There have been about 23 XDK's, and each of them offers about 60 libraries. These libraries contain lots (sometimes thousands) of functions, some of which might need patching.

Now, if we want to patch a function, where do we start? First thing, we need to know where the function resides in the code-section of the executable. Only when we know it's location, we can place a patch over it.

As you might have realized by now, the potential number of functions that could exist inside a game are huge. Just do the math : 23 XDK's * 60 libraries * 1000 functions ~= 1.400.000 functions.

Sure, that's probably over-estimating it, but even when in reality there only exist 1/10th or even 1/20th of that, we still have quite a large number of functions to detect.

Before the radix trie, we needed to store 42 bytes per function, plus some 20 bytes for the name of each function. The sheer volume of that data made me consider a more efficient storage structure, which I think I've realized now.


Currently, I have patterns for about 30.000 functions, which (when stored in the new Trie structure) takes less than 900 KB, which means ~30 bytes per function. So that's roughly a 50% reduction. Not much profit you would say? Well indeed, but this approach opens up two other possibilities :

I can put the names of the functions in a trie (just like I did with the patterns) and save another big chunk of storage (I would say about 30%).

But an even better idea is, to skip the function names completly! I'm already working on a way to achieve just that - I'll keep you posted on the progress.


I hope that explained it a bit better. Cheers!

[shogun_nihon]

Originally Posted by patrickvl

I hope that explained it a bit better. Cheers!

Yeah much better now, thanks.

__________________
私はヴェクター·インダストリー製,対グノーシス専用ヒト型掃討兵器,KOS-MOS Ver.4です

CV:鈴木 麻里子(すずき まりこ)

"Yo, hecha por la Industria Vector, para uso exclusivo contra GNOSIS, humanoide de armas arrasadoras, soy KOS-MOS version 4".

スゴイ麻里子さん、あなたの声が大好きですよ。
http://www.aoni.co.jp/actress/sa/suzuki-mariko.html