Next tasks?

Discuss coding questions, pull requests, and implementation details.
User avatar
Interkarma
Posts: 3193
Joined: Sun Mar 22, 2015 1:51 am

Re: Next tasks?

Post by Interkarma » Sat Nov 12, 2016 5:33 am

Wow! Legendary work my friend. Looking forward to testing all this out! :)

User avatar
InconsolableCellist
Posts: 90
Joined: Mon Mar 23, 2015 6:00 am

Re: Next tasks?

Post by InconsolableCellist » Sat Nov 12, 2016 7:54 pm

Great, thanks! Let me know if you have any questions.

For the potion stuff, is DFTFU already aware of the ingredients, their IDs, and how they map to the potion recipes?

I see in FALL.EXE there are lists of ingredients and potion recipes. Are these imported somewhere? ItemTemplates.txt has ingredients in it, but I don't see a unique identifier from the game, which is contained somewhere in each potion record.

Does DFTFU do the importing from FALL.EXE, or is the information broken out using a third party utility and put into a JSON format or similar? I might have to reverse engineer the potion recipe information..

User avatar
InconsolableCellist
Posts: 90
Joined: Mon Mar 23, 2015 6:00 am

Re: Next tasks?

Post by InconsolableCellist » Sat Nov 12, 2016 10:18 pm

Re: reading from FALL.EXE, I found that it's doing a lot of what I need to be doing inside of the ReadFallExeFile() in ItemsFile.cs. It even says that it's starting at the Ruby object to determine the offset, which is what I was manually doing. So it's definitely reading the items, grabbing all available information, and putting it in the Items array.

Also your code has much more information than the UESP wiki...only one unknown value, whereas they have seven!

User avatar
Interkarma
Posts: 3193
Joined: Sun Mar 22, 2015 1:51 am

Re: Next tasks?

Post by Interkarma » Sat Nov 12, 2016 10:28 pm

InconsolableCellist wrote:Great, thanks! Let me know if you have any questions.
Will do. I'll sit down to merge PR and review as soon as I get a bit of time. I will say I'm very impressed, and very grateful too. :)
InconsolableCellist wrote: For the potion stuff, is DFTFU already aware of the ingredients, their IDs, and how they map to the potion recipes?
Not yet, I had intended to be part of the spells and effects system which I'm planning to tackle post quests (probably by around mid 2017).

If you'd like to make a start on this, I'm happy to outline what I had in mind and you can run with it how you see fit. Otherwise you're welcome to come over and help with the quest system next. I'm sure we can find a way to mesh together despite the time zone differences. Any time you're willing to give to the project will be most welcome. :)
InconsolableCellist wrote: I see in FALL.EXE there are lists of ingredients and potion recipes. Are these imported somewhere? ItemTemplates.txt has ingredients in it, but I don't see a unique identifier from the game, which is contained somewhere in each potion record.

Does DFTFU do the importing from FALL.EXE, or is the information broken out using a third party utility and put into a JSON format or similar? I might have to reverse engineer the potion recipe information..
The item templates were exported once only by ItemExplorerWindow.cs > ItemDataToJSON.cs > ItemsFile.cs. I had to post-fix several templates due to bad data on Daggerfall's side, so the JSON item templates now represent a cleaner copy of item data than Daggerfall itself.

My goal is to eventually extract everything needed from the .exe rather than connect directly to it at runtime. There are a few different versions of the .exe out there depending on patch and region, it's non-trivial to support all of them. And the data is better off on a format that's easy to fix problems. Being able to fix item bugs by changing a text file has been a huge benefit.

Just let me know where you want to contribute and I'll do my best to support you.

EDIT:
InconsolableCellist wrote:Re: reading from FALL.EXE, I found that it's doing a lot of what I need to be doing inside of the ReadFallExeFile() in ItemsFile.cs. It even says that it's starting at the Ruby object to determine the offset, which is what I was manually doing. So it's definitely reading the items, grabbing all available information, and putting it in the Items array.

Also your code has much more information than the UESP wiki...only one unknown value, whereas they have seven!
You found that as I was writing this reply haha. :)

Getting some of those unknowns was rough. Items have the most densely packed bitfields I've seen to date. Was very satisfying to nut them out though.

User avatar
InconsolableCellist
Posts: 90
Joined: Mon Mar 23, 2015 6:00 am

Re: Next tasks?

Post by InconsolableCellist » Sat Nov 12, 2016 11:39 pm

Will do. I'll sit down to merge PR and review as soon as I get a bit of time. I will say I'm very impressed, and very grateful too. :)
Thanks! Most of the hard work was done already though
If you'd like to make a start on this, I'm happy to outline what I had in mind and you can run with it how you see fit. Otherwise you're welcome to come over and help with the quest system next. I'm sure we can find a way to mesh together despite the time zone differences. Any time you're willing to give to the project will be most welcome. :)
The quest system is more important, and I didn't know that the potion recipes were deferred (but it makes sense, given how it depends on ingredients)

I'll briefly describe what I found from my investigation so far, as it may come in handy when this has to be tackled:

Code: Select all

* I manually exported the bytes in FALL.EXE that have strings that match the potion recipe names. Interestingly "Purification" (001B:A990) seems to prove that the string is last in the record, as no data follows that entry. I tried interpreting the records by both putting the string last in the record as well as first.

* My goal was to ferret out the bytes representing the ingredients. I figured it was represented in one byte without masking, and that they were sequential. (E.g., "this recipe requires pure water, nectar, and ectoplasm," with the ingredients being represented by three sequential bytes in any order) 

* My method of attack was to write down all possible unique sequences of bytes in each record. So if a recipe called for four ingredients, I wrote down all sequential byte sequences that had four unique values. I did this for multiple recipes that shared ingredients, and my goal was to find the intersections. I.e., "suppose that <common ingredient 1> is represented by <value 1>. Is this value shared by all the other potions that have this ingredient? No? How about <value 2>?" And so on.

I wasn't able to map the ingredients in this way, which proves one of two things: the ingredients aren't contained in that section of data; the ingredients are encoded/masked. 

My bet is that this data (001B:A130 - 001B:A9A0) is actually a table of potion/spell effects, and the effect names are referenced as table offsets elsewhere in the data. I'm not quite sure how to find this...maybe attach a debugger and look to see who accesses that table?
Getting some of those unknowns was rough. Items have the most densely packed bitfields I've seen to date. Was very satisfying to nut them out though.
Was memory really that much of a premium, or were the developers just having fun with unnecessary optimizations? I really wish they'd release the Daggerfall source code. It might be that luciusDXL of XLEngine has figured some of this out, but my impression is that he wouldn't reveal it.

Anyway! I'd be happy to contribute to the quest engine stuff, if you think there's a good chunk that could be broken off and worked on separately.

User avatar
Interkarma
Posts: 3193
Joined: Sun Mar 22, 2015 1:51 am

Re: Next tasks?

Post by Interkarma » Sat Nov 12, 2016 11:58 pm

InconsolableCellist wrote: I'll briefly describe what I found from my investigation so far, as it may come in handy when this has to be tackled:

Code: Select all

* I manually exported the bytes in FALL.EXE that have strings that match the potion recipe names. Interestingly "Purification" (001B:A990) seems to prove that the string is last in the record, as no data follows that entry. I tried interpreting the records by both putting the string last in the record as well as first.

* My goal was to ferret out the bytes representing the ingredients. I figured it was represented in one byte without masking, and that they were sequential. (E.g., "this recipe requires pure water, nectar, and ectoplasm," with the ingredients being represented by three sequential bytes in any order) 

* My method of attack was to write down all possible unique sequences of bytes in each record. So if a recipe called for four ingredients, I wrote down all sequential byte sequences that had four unique values. I did this for multiple recipes that shared ingredients, and my goal was to find the intersections. I.e., "suppose that <common ingredient 1> is represented by <value 1>. Is this value shared by all the other potions that have this ingredient? No? How about <value 2>?" And so on.

I wasn't able to map the ingredients in this way, which proves one of two things: the ingredients aren't contained in that section of data; the ingredients are encoded/masked. 

My bet is that this data (001B:A130 - 001B:A9A0) is actually a table of potion/spell effects, and the effect names are referenced as table offsets elsewhere in the data. I'm not quite sure how to find this...maybe attach a debugger and look to see who accesses that table?
Excellent! Thank you for that. I haven't done much along these lines yet, very helpful. I'll keep this to refer back to.
InconsolableCellist wrote: Was memory really that much of a premium, or were the developers just having fun with unnecessary optimizations? I really wish they'd release the Daggerfall source code. It might be that luciusDXL of XLEngine has figured some of this out, but my impression is that he wouldn't reveal it.
Haha, I often think that as well. I started development on a C64, so I know what it's like to scrape together every available byte - but man! I'm not sure the item templates had to be quite that packed. Or in the .exe for that matter.

The Daggerfall source code would be most useful. :/
InconsolableCellist wrote: Anyway! I'd be happy to contribute to the quest engine stuff, if you think there's a good chunk that could be broken off and worked on separately.
For sure! :) Right now, I've nearly finished the basics of parsing the .src structure into classes that will use that information (e.g. messages go to a Message class), and working on a quest debugger to show the components and state of active quests. I'm still a ways of doing serialization and a lot of other key things, but getting close to having some basics in place.

If you can give me up to two weeks to wrap up what I have and post to git (I need to make some spare time), we can sit down together and knuckle out how we can divide and conquer.

User avatar
Nystul
Posts: 1122
Joined: Mon Mar 23, 2015 8:31 am

Re: Next tasks?

Post by Nystul » Sun Nov 13, 2016 5:20 pm

I just want to chime in that I like how you collaborate here - it is nice to have another person involved. Can't wait to contribute as well (although I am completely unexperienced in reverse engineering unfortunately)

User avatar
InconsolableCellist
Posts: 90
Joined: Mon Mar 23, 2015 6:00 am

Re: Next tasks?

Post by InconsolableCellist » Mon Nov 14, 2016 10:31 pm

If you can give me up to two weeks to wrap up what I have and post to git (I need to make some spare time), we can sit down together and knuckle out how we can divide and conquer.
Sure! That sounds good
I just want to chime in that I like how you collaborate here - it is nice to have another person involved. Can't wait to contribute as well (although I am completely unexperienced in reverse engineering unfortunately)
Thanks! And your increased terrain distance improvements are awesome, and I'm glad to see them integrated into DFTFU/DFU

Re: potions...since two weeks is a long time, and I couldn't leave well enough alone...

I tried a bunch of approaches to deciphering the FALL.EXE data, and made the following discoveries:
  • The data at ~001B:A130 to 001B:19A0 appear to be an array of structs that contain spell/potion effects (the same thing perhaps). The structs are variable length, surely because one or more member variables are arrays, probably information describing the way the spell works.
  • Reasoning that other code would contain offsets into this table, and reasoning that the potion recipes would necessarily have to have an index to it, I quested a bunch in Orsinium (running in Dosbox) until I found two potion recipes. Many orcs died to bring you the following information.
  • Using these two recipes and the offsets based on the data in FALL.EXE, I figured out that (hits3 >> 8) encodes the offset into the table! I killed some more orcs and confirmed it with a third recipe.
Thus, I'm now able to create a mapping between the item data and the actual recipe it describes! I also know that the table in FALL.EXE either contains or links to (<-- much more likely, see previous post) another table which describes the ingredients necessary to create that spell effect.

Parsing this table will be essential for the magic system, and I think I have a good method of attack when someone wants to find how items in the spellbook are stored. (Create a spell that indexes a few offsets in the effects table, then search memory/save data for these bytes.)

I also did a crazy thing that might come in handy...

I found a patch someone created for an older version Dosbox that lets you add a memory read breakpoint (instead of just change). I applied the patch, compiled that version with debugging enabled, and put the whole thing in a portable Xen VM with a Debian distribution. With a few other utilities like okteta and qalculate, it should make for a good way to reverse engineer Daggerfall when it's running, should things ever get that desperate. I might also be able to put that Dosbox version into a more easily portable appimage, if I can figure out how that works.

User avatar
Interkarma
Posts: 3193
Joined: Sun Mar 22, 2015 1:51 am

Re: Next tasks?

Post by Interkarma » Mon Nov 14, 2016 10:42 pm

Holy crap, you're amazing! :shock:

Edit: Now that I've calmed down. Do you think it would be possible to use that dosbox patch to see where DF loads the first-person horse overlay (i.e. shown while player is riding horse)? These aren't coming from the usual image files, and previous debugger research shows no files are being loaded when player starts using the horse.

My hypothesis is the horse graphics were embedded in the .exe at the last minute, but I haven't been able to locate using any of my typical methods. I have a backup plan to deal with this, but I'm curious as hell what DF is really doing here.

User avatar
InconsolableCellist
Posts: 90
Joined: Mon Mar 23, 2015 6:00 am

Re: Next tasks?

Post by InconsolableCellist » Tue Nov 15, 2016 2:47 am

Hmm, I tried some more immediate approaches to finding the horse graphics, but I couldn't locate anything.

I figured that the image would be embedded using the ImgHeader/CIF file format, and that it'd match the dimensions of the existing horse graphics (108x98 and 100x97). However, the bytes 006C0062 or 00640061 don't show up anywhere. There are a few 00640064 instances, but if you look at the next UInt16 and assume it's an entry in the compression enumeration table (http://www.uesp.net/wiki/Daggerfall:Image_formats/IMG) it doesn't work.

I also tried taking a screenshot and finding the actual dimensions of the horse graphic (201x210), but couldn't find it using 00C9 00D2 either. In a last ditch effort to find any image data that follows an ImgHeader in the EXE, I wrote a program that does the following:

For each byte in FALL.EXE, grab int16, int16, uint16, int16 and have these represent width, height, compression, and PixelDataLength respectively. It then prints these values out if compression exists in the compression enumeration table (0|2|0x0108|0x1108) and if w*h <= pixDataLength

Of the approximately 25 matches there are only two that have anything approaching reasonable image dimensions:

Code: Select all

	width: 80
	height: 256
	compression: 0
	pixDataLen: 20480 
...

	width: 256
	height: 64
	compression: 0
	pixDataLen: 32002 

The first occurs at 001B:2BF3, 001B:2D0B, and 001B:2D19 and the second at 000C:D7A8.

Unfortunately for the first one, if we're to believe that it has no compression then the "image data" actually spills into strings clearly used for items. So it can't be that.

For the second one there are no obvious strings that the data floods into. There two obvious hiccups though: the four bytes before are supposed to be X and Y offsets. 0x81 0x3D 0x8E 0x70 are coordinates (33085, 36464). This is clearly outside the range of a normal image offset.

Regardless, I've captured 7D02 bytes starting at 000C:D7A4 (to 000C:54A5). According to UESP (where I'm getting all this header information from) this data should be treatable as an RCI file. Note that the data range includes the 14 byte header.

http://pastebin.com/pCuFmwwX (Edit: I'll PM you a link to the binary "RCI" file)

Do you have the ability to view this as an RCI file to see if it actually contains image data?

Believe it not I think this whole process is still easier than trying to use the debugger. The only thing I could think of is to put a breakpoint in the video memory when the horse graphic is on screen, but I bet it'd be a tortuous process to reverse engineer where the bits are being blitted from.

Edit: It's also still possible that your theory is true, and the image is somewhere in the EXE, but the last-minute nature of the hack meant they used a different image format or dumped it in as an encoded byte array and handled it in some way unique to that image. They use RLE all over the place, I wonder if there's a common signature to indicate that RLE is being used?

Post Reply