[Dxbx status] API detection

**patrickvl** · July 7th, 2008

Hi there - Here a little story about API detection, for those interested in the inner workings. (Note that all of this is based on what I've learned from Caustic's magnificent achievement : Cxbx) :

To do high-level emulation of an Xbox, some of the code in a game has to be patched. This is necessary because without the patch, the code wouldn't function correctly on the OS running the emulator (Windows XP). So, the first problem we have, is to detect where this code resides.

Lucky for us, most games written for the Xbox use a Development Kit (aka X-SDK or XDK) containing lots of functions doing all sorts of things, amongst which are also functions that put a layer of separation between the hardware and the user. (Those are the prime candidates that need patching, although other functions have to be patched up too).

Because of that, we can do a scan over the assembly-code to detect where those XDK functions are located exactly. For Cxbx, Caustic wrote a super-compact structure for detecting the functions that need patching. The problem with this code is however, that it can't be translated over to Delphi without significant effort.

So, I'm using a different approach: pattern files. A Pattern File contains enough details to detect a function in code - read up about them here : Hex-Rays : Interactive Disassembler Pro - FLIRT Technology

Using pattern files have a few pro's and con's. First the benefits:
- the chance on a false positive detection is extremely small
- the chance on correct detection is extremely high
- it's easy to switch versions : just use another pattern file
The lesser-attractive features are however:
- pattern files take up a lot of space
- debugging the detection code is problematic

The space-problem could be solved by using a pattern-deriviate : signature files. Signature files are formed like a trie and as such a great bit smaller than pattern-files, while still containing enough information to still have a fairly high detection rate (signatures are a bit less accurate because they miss the cross-references and trailing bytes that are available in pattern files).
However, I've spend the better part of a week on trying to figure out the exact .sig format and I failed on that. (Anyone willing to try is welcome!)

So I went back and started doing API-detection using the pattern files. For now, I've included the pattern-files as a resource in the Dxbxkrnl.DLL (which takes up quite a bit of space). When initializing the game, I parse the patterns into a more compact format, sorting them on the go so I can detect them using a fast but standard binary-search algorithm. Detecting all API's in Turok takes me less than a second, so speed is not (yet) a problem here.

Currently I'm stuck on the CRC16 validation however - I don't know what's wrong exactly, but I can think of a few possible reasons :
- we're using the wrong CRC16 algorithm?
- the location to test is one byte off?
- the CRC should use something else than 0 as a starting value?
- the CRC is done over the whole pattern (unlikely)
As soon as I've fixed the CRC16, I'll add cross-reference detection and the trailing-byte detection.

Next, I'll probably invent my own signature-format, so the size of the resource can shrink again. One thing I hope to accomplish is, to somehow throw the patterns of all libraries into one consolidated signature. This will save lots of space, and still enables me to detect all library-functions from all XDK versions I can get my hands on(!)

That all for now folks, I hope this helped you understand the problem's we're dealing with right now.

Stay tuned, and as always : Anyone willing to help is quite welcome!

Cheers,
PatrickvL

gamersat678 · July 7th, 2008

Yeah space might be an issue. God...

Quote:

we easily fall into the tens of gigabytes range.

My hard drive can fit that but 10gbs to download even on a roadrunner connection. That might take a little bit of time.

__________________
Primary: Core 2 Duo E4300 1.8 ghz, 3 gb DDR II ram, Overclock XFX 7900GS 580/745
Secondary: Mod P4 HT 3.18ghz, 1.5gb ram, AGP HIS Radeon X1650 Pro IceQ II / 512MB

Need To Post a Bug? Use This Program PCSX2 Bug Reporter

**patrickvl** · July 8th, 2008

Quick update;
I've succesfully determined what kind CRC we need to calculate - it's officially called : CRC-16 CCITT X-KERMIT (a.ka. X-MODEM).

See revision 234 on sourceforge : SourceForge.net Repository - [dxbx] Log of /

With this, detection of API's became much more reliable, although I still see lots of functions being detected on multiple addresses. That's not what you'd expect ofcourse, so to bring the maximum number of 'hits' per function down to exactly 1 occurrence, we'll have to extend the detection with the cross-reference checks (and trailing-bytes checks too), I presume.

PS: Is anyone listening to this, or should I just shut up until some real progress is made?

**Bobbi** · July 8th, 2008

Reading this on a regular base, very interresting stuff there and cool to see which issues you are facing with such a complex translation!

__________________

Specs: AMD Athlon 64 4000+ • 2048 MB PC400 RAM • Nvidia GeForce 7600 GT PCI-E • WinXP Pro

gamersat678 · July 8th, 2008

Keep giving us info. (Reading daily)

__________________
Primary: Core 2 Duo E4300 1.8 ghz, 3 gb DDR II ram, Overclock XFX 7900GS 580/745
Secondary: Mod P4 HT 3.18ghz, 1.5gb ram, AGP HIS Radeon X1650 Pro IceQ II / 512MB

Need To Post a Bug? Use This Program PCSX2 Bug Reporter

dreampeppers99 · July 8th, 2008

Quote:

Originally Posted by gamersat678

Keep giving us info. (Reading daily)

me too

__________________
OS: Windows XP Professional SP3 (32bits)

CPU: Athlon XP 2400+ (2.0 Ghz)

(non SSE2)
Graphics Card: ATI X1650 Pro 512MB

Memory: 1GB DDR

snickothemule · July 9th, 2008

It is always interesting to read a developers journal, learning the ins and outs of programming an emulator. It is quite enjoyable.

__________________

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

shogun_nihon · July 9th, 2008

I read your and shadow_tj post!!!

Trotterwatch · July 13th, 2008

First I've heard of this emulator. Haven't checked the emulation scene out for a while. I'm all for reading the tech stuff, I seldom understand the intricacies, but it's still interesting. Anyways keep up the great work, bookmarking this forum so I can keep up to date.

RyuRanX · July 13th, 2008

I don't understand anything, but I love to read detailed emulation news. Keep us well informed patrickvl, and good luck working on Dxbx ^~

Last edited by RyuRanX; July 14th, 2008 at 14:08.

**patrickvl** · July 18th, 2008

For those that are keeping tabs on Dxbx development:

In SourceForge.net Repository - [dxbx] Revision 248 I've changed the way Dxbx reads the Patterns for the Xbox library functions.
Previously I linked all pattern-files to the DxbxKrnl.DLL via one big resource. This made the DLL unnecessarily big, and still required the DLL to parse the patterns before it could start detecting them.

To remedy this I've made a tool that generates a Delphi unit containing the pre-parsed patterns in record-form. This unit (uPatterns.pas) is then compiled as part of the DxbxKrnl.DLL project, so it doesn't have to parse the patterns anymore.
The result is a smaller DLL, that loads and runs faster.

As an added bonus, it's now trivial to make two builds of the DLL; One debug-build, containing all patterns we know of (which will be larger and will be much more verbose in the log). And a release-build, which will just contain the patterns we can patch (resulting in a smaller and faster DLL).

Meanwhile, I've also managed to fix the CRC check using a pre-calculated table, which improves the speed of API detection. The way we do API detection is really fast now, so we won't need a detection-cache like Cxbx has.

For me, the next step is probably adding a registry of detected functions. I'll probably add an address-range per function, which I plan to use for debugging purposes; The idea is, when an exception occurs, to look up the exception-address in the detected function-ranges. This way, we can log the name of the failed function in some sort of call-stack. The developers amongst you will understand the huge benefit this will give us. (And yes, I'll try to incorporate this with JclDebug.)

dreampeppers99 · July 18th, 2008

Nice see the progress one more time!!!
Awsome work! Thanks for the hours and concentration. (and for the tech material

me and some guys loves "watch" this)

__________________
OS: Windows XP Professional SP3 (32bits)

CPU: Athlon XP 2400+ (2.0 Ghz)

(non SSE2)
Graphics Card: ATI X1650 Pro 512MB

Memory: 1GB DDR

**shadow_tj** · July 18th, 2008

if someone is interested...

here are some debug loggings.
see the differences yourself

15-07-08 - 304 api calls detected
18-07-08 - 636 api calls detected

Attached Files

	DxbxKrnlDebug15-7-2008.txt (21.4 KB, 30 views)
	DxbxKrnlDebug18-7-2008.txt (43.1 KB, 30 views)

**Chrono Archangel** · July 18th, 2008

lots of double entries in the second file. is that intended?

__________________

When Pigs Fly: The Death of Oink, the Birth of Dissent, and a Brief History of Record Industry Suicide.

**patrickvl** · July 18th, 2008

Quote:

Originally Posted by Chrono Archangel

lots of double entries in the second file. is that intended?

No, but it will improve soon!

dreampeppers99 · July 19th, 2008

Quote:

Originally Posted by Chrono Archangel

lots of double entries in the second file. is that intended?

Chrono Archangel why don't put the EmuAuthor stat for patrickvl?
Is he the author?

__________________
OS: Windows XP Professional SP3 (32bits)

CPU: Athlon XP 2400+ (2.0 Ghz)

(non SSE2)
Graphics Card: ATI X1650 Pro 512MB

Memory: 1GB DDR

**patrickvl** · July 20th, 2008

Quote:

Originally Posted by dreampeppers99

Chrono Archangel why don't put the EmuAuthor stat for patrickvl?
Is he the author?

What's an EmuAuthor stat if I may ask?

Well, I'm not _the_ Dxbx author, that would be Shadow_tj - as he started the project and all

.
About a year ago I donated a small XML-related patch, but didn't do much else up until about two months ago, which was when I joined the project 'full time' (read: with as much spare time as I can offer).
In the first few weeks I made Shadow_tj very happy, as I managed to overcome a few hurdles he was stuck at. Since then I've tried to keep contributing regularly. Currently I'm working on library-function detection code, which will enable us to patch code that can't run natively on win32.

FYI : Both Shadow_tj and me are Delphi coders in our day-time jobs, but about a month ago another (non-Delphi) developer, Robert, joined us just for the fun of it. I had come in contact with him because he had released an add-on for IDA-Pro that made it possible to debug Cxbx-converted Xbox-executables with symbols for all library functions. Since then Robert got intrigued, and is now working on a totally different approach on the LDT emulation, by patching all opcodes that accesses the FS-register in an 'Xbox-way', to the 'win32-way' of doing things. We hope that this will enable Dxbx to run on Vista 64 too (!)

As for the double entries ppl are seeing right now in the Dxbx debug logs, it's because I don't yet take the version of each library into account. I'm working on a rather large revision that will fix that, and bring a few other nice improvements too;
- an optimized Dxbx.DLL (as opposed to the current debug DxbxKrnl.DLL)
- callstack information on all detected Xbox Library functions (nice for debugging)
- the very first few working patches (taking Dxbx one step further to the actual emulation of an Xbox)

That all for now. Cheers!

dreampeppers99 · July 21st, 2008

Quote:

Originally Posted by patrickvl

I donated a small XML-related patch, didn't do much else up until about two months ago, which was when I joined the project 'full time' (read: with as much spare time as I can offer).

Well I think you are one of the Authors ! Then deserve the EmuAuthor stat.

Lino (one great dev behind ideas emu) has the emu author .... see http://forums.ngemu.com/members/92705.html It seems just a big quantity of red stars... and give you a special look!

__________________
OS: Windows XP Professional SP3 (32bits)

CPU: Athlon XP 2400+ (2.0 Ghz)

(non SSE2)
Graphics Card: ATI X1650 Pro 512MB

Memory: 1GB DDR

**Chrono Archangel** · July 21st, 2008

Quote:

Originally Posted by patrickvl

What's an EmuAuthor stat if I may ask?

Red stars

see?

__________________

When Pigs Fly: The Death of Oink, the Birth of Dissent, and a Brief History of Record Industry Suicide.

dreampeppers99 · July 21st, 2008

Quote:

Originally Posted by Chrono Archangel

Red stars

see?

Now he knows...

(I believe)

__________________
OS: Windows XP Professional SP3 (32bits)

CPU: Athlon XP 2400+ (2.0 Ghz)

(non SSE2)
Graphics Card: ATI X1650 Pro 512MB

Memory: 1GB DDR

July 7th, 2008	#1 (permalink)
patrickvl Emu author Join Date: May 2008 Location: Netherlands Posts: 55	[Dxbx status] API detection Hi there - Here a little story about API detection, for those interested in the inner workings. (Note that all of this is based on what I've learned from Caustic's magnificent achievement : Cxbx) : To do high-level emulation of an Xbox, some of the code in a game has to be patched. This is necessary because without the patch, the code wouldn't function correctly on the OS running the emulator (Windows XP). So, the first problem we have, is to detect where this code resides. Lucky for us, most games written for the Xbox use a Development Kit (aka X-SDK or XDK) containing lots of functions doing all sorts of things, amongst which are also functions that put a layer of separation between the hardware and the user. (Those are the prime candidates that need patching, although other functions have to be patched up too). Because of that, we can do a scan over the assembly-code to detect where those XDK functions are located exactly. For Cxbx, Caustic wrote a super-compact structure for detecting the functions that need patching. The problem with this code is however, that it can't be translated over to Delphi without significant effort. So, I'm using a different approach: pattern files. A Pattern File contains enough details to detect a function in code - read up about them here : Hex-Rays : Interactive Disassembler Pro - FLIRT Technology Using pattern files have a few pro's and con's. First the benefits: - the chance on a false positive detection is extremely small - the chance on correct detection is extremely high - it's easy to switch versions : just use another pattern file The lesser-attractive features are however: - pattern files take up a lot of space - debugging the detection code is problematic The space-problem could be solved by using a pattern-deriviate : signature files. Signature files are formed like a trie and as such a great bit smaller than pattern-files, while still containing enough information to still have a fairly high detection rate (signatures are a bit less accurate because they miss the cross-references and trailing bytes that are available in pattern files). However, I've spend the better part of a week on trying to figure out the exact .sig format and I failed on that. (Anyone willing to try is welcome!) So I went back and started doing API-detection using the pattern files. For now, I've included the pattern-files as a resource in the Dxbxkrnl.DLL (which takes up quite a bit of space). When initializing the game, I parse the patterns into a more compact format, sorting them on the go so I can detect them using a fast but standard binary-search algorithm. Detecting all API's in Turok takes me less than a second, so speed is not (yet) a problem here. Currently I'm stuck on the CRC16 validation however - I don't know what's wrong exactly, but I can think of a few possible reasons : - we're using the wrong CRC16 algorithm? - the location to test is one byte off? - the CRC should use something else than 0 as a starting value? - the CRC is done over the whole pattern (unlikely) As soon as I've fixed the CRC16, I'll add cross-reference detection and the trailing-byte detection. Next, I'll probably invent my own signature-format, so the size of the resource can shrink again. One thing I hope to accomplish is, to somehow throw the patterns of all libraries into one consolidated signature. This will save lots of space, and still enables me to detect all library-functions from all XDK versions I can get my hands on(!) That all for now folks, I hope this helped you understand the problem's we're dealing with right now. Stay tuned, and as always : Anyone willing to help is quite welcome! Cheers, PatrickvL

July 8th, 2008	#3 (permalink)
patrickvl Emu author Join Date: May 2008 Location: Netherlands Posts: 55	Pattern CRC's start working! Quick update; I've succesfully determined what kind CRC we need to calculate - it's officially called : CRC-16 CCITT X-KERMIT (a.ka. X-MODEM). See revision 234 on sourceforge : SourceForge.net Repository - [dxbx] Log of / With this, detection of API's became much more reliable, although I still see lots of functions being detected on multiple addresses. That's not what you'd expect ofcourse, so to bring the maximum number of 'hits' per function down to exactly 1 occurrence, we'll have to extend the detection with the cross-reference checks (and trailing-bytes checks too), I presume. PS: Is anyone listening to this, or should I just shut up until some real progress is made?

July 18th, 2008	#11 (permalink)
patrickvl Emu author Join Date: May 2008 Location: Netherlands Posts: 55	API detection speedups For those that are keeping tabs on Dxbx development: In SourceForge.net Repository - [dxbx] Revision 248 I've changed the way Dxbx reads the Patterns for the Xbox library functions. Previously I linked all pattern-files to the DxbxKrnl.DLL via one big resource. This made the DLL unnecessarily big, and still required the DLL to parse the patterns before it could start detecting them. To remedy this I've made a tool that generates a Delphi unit containing the pre-parsed patterns in record-form. This unit (uPatterns.pas) is then compiled as part of the DxbxKrnl.DLL project, so it doesn't have to parse the patterns anymore. The result is a smaller DLL, that loads and runs faster. As an added bonus, it's now trivial to make two builds of the DLL; One debug-build, containing all patterns we know of (which will be larger and will be much more verbose in the log). And a release-build, which will just contain the patterns we can patch (resulting in a smaller and faster DLL). Meanwhile, I've also managed to fix the CRC check using a pre-calculated table, which improves the speed of API detection. The way we do API detection is really fast now, so we won't need a detection-cache like Cxbx has. For me, the next step is probably adding a registry of detected functions. I'll probably add an address-range per function, which I plan to use for debugging purposes; The idea is, when an exception occurs, to look up the exception-address in the detected function-ranges. This way, we can log the name of the failed function in some sort of call-stack. The developers amongst you will understand the huge benefit this will give us. (And yes, I'll try to incorporate this with JclDebug.)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

July 8th, 2008	#4 (permalink)
Bobbi Administrator Join Date: Apr 2001 Location: Germany Posts: 2,380	Reading this on a regular base, very interresting stuff there and cool to see which issues you are facing with such a complex translation! __________________ Specs: AMD Athlon 64 4000+ • 2048 MB PC400 RAM • Nvidia GeForce 7600 GT PCI-E • WinXP Pro

July 8th, 2008	#5 (permalink)
gamersat678 Registered User Join Date: Nov 2007 Location: In the Neighbor's Trash Can (USA) Posts: 464	Keep giving us info. (Reading daily) __________________ Primary: Core 2 Duo E4300 1.8 ghz, 3 gb DDR II ram, Overclock XFX 7900GS 580/745 Secondary: Mod P4 HT 3.18ghz, 1.5gb ram, AGP HIS Radeon X1650 Pro IceQ II / 512MB Need To Post a Bug? Use This Program PCSX2 Bug Reporter

July 9th, 2008	#7 (permalink)
snickothemule Registered Mule Join Date: Apr 2008 Location: Coffs Harbour, Australia Posts: 819	It is always interesting to read a developers journal, learning the ins and outs of programming an emulator. It is quite enjoyable. __________________ "If you wish to make an apple pie truly from scratch, you must first invent the universe." - Carl Sagan

July 9th, 2008	#8 (permalink)
shogun_nihon 将軍 Join Date: Feb 2008 Location: 秋葉原 Posts: 303	I read your and shadow_tj post!!!

July 13th, 2008	#9 (permalink)
Trotterwatch Registered User Join Date: Jul 2002 Location: Chester, UK Posts: 28	First I've heard of this emulator. Haven't checked the emulation scene out for a while. I'm all for reading the tech stuff, I seldom understand the intricacies, but it's still interesting. Anyways keep up the great work, bookmarking this forum so I can keep up to date.

July 13th, 2008	#10 (permalink)
RyuRanX Registered User Join Date: Apr 2007 Location: Brazil Posts: 32	I don't understand anything, but I love to read detailed emulation news. Keep us well informed patrickvl, and good luck working on Dxbx ^~ Last edited by RyuRanX; July 14th, 2008 at 14:08.

July 18th, 2008	#12 (permalink)
dreampeppers99 Eric Cartmenez Join Date: Jul 2006 Location: you know... Posts: 400	Nice see the progress one more time!!! Awsome work! Thanks for the hours and concentration. (and for the tech material me and some guys loves "watch" this) __________________ OS: Windows XP Professional SP3 (32bits) CPU: Athlon XP 2400+ (2.0 Ghz) (non SSE2) Graphics Card: ATI X1650 Pro 512MB Memory: 1GB DDR

July 18th, 2008	#14 (permalink)
Chrono Archangel Administrator Join Date: Dec 2001 Location: Montreal, Canada Posts: 7,462	lots of double entries in the second file. is that intended? __________________ When Pigs Fly: The Death of Oink, the Birth of Dissent, and a Brief History of Record Industry Suicide.