A New DeNCS

[lachjames 24]

Hi

@DrMcCoy thanks for “@ing” me - I rarely post on forums but this has given me motivation to do so

I’ve made the GitHub repo for my implementation of “ncs2nss” public at https://github.com/lachjames/ncs2nss.

There are a few things to know:

 - Firstly, it’s a work in progress and isn’t perfect. However, all the fundamental components are implemented and the code runs most of the time without error (as in runtime error - it may well make decompilation errors)

 - I would be not just happy but “double plus happy” if this were ported into C++ and included in xoreos-tools - I say in the readme that one of my goals is to demonstrate how this can be done in Python (using tools I’m familiar with such as rply) so others can implement the same (e.g. in xoreos-tools). I haven’t put an official license on it yet but like DrMcCoy I’m a big believer in open source so consider it open with attribution.

 - My version works with ncsdis and I encourage you to do the same (and include your improvements in xoreos-tools) as one perfect library for disassembly is better than two that work most of the time. This is just my opinion and I don’t mean to diminish the work you’ve done on the disassembler (I’m sure it’s great, just like xoreos-tools is great) - I just feel that if we all merge our efforts we can make a better final product 

@DrMcCoy feel free to post/copy anything from our conversations if you’d like. I’m an open book; just didn’t want to annoy you on GitHub by cluttering up your inbox with posts on issues

In particular, let me copy-paste my latest message to him on Discord below:

*** BEGIN QUOTE ***
Hey so I've realized that this heuristic analysis is not reliable enough to be used properly, but I came up with another solution which works every time. The problem is that the Skywing documentation is incorrect, and JSR does in fact work just like ACTION in that it modifies the stack pointer by popping off arguments. It doesn't push on a return value though (if there is one, space for that must have been allocated by the caller function before calling the callee). Perhaps what they mean is that the JSR does not do anything "intrinsically", but the function calling convention appears to be that functions pop their own arguments (which is more reasonable than making the caller do it every time; this is something I've actually taught before in computer science classes).

In any case, what you can do is the following (after constructing a call graph):
For each subroutine in the call-graph, iterating with DFS reverse post-order traversal:
    1. If the current subroutine is part of a cycle in the call graph:
        1.a. Collect all the subroutines in the cycle
        1.b. Trace both the final stack pointer and subroutine calls from every possible path from the start block of each subroutine to a block with no successors.
        1.c. For each of these paths, we can form an entry in a system of simultaneous equations, where the final stack pointer is on the RHS and the subroutine calls are on the LHS. For example, if a path through subA calls subB 2 times and subC 2 times, and the final stack pointer is -8,  our equation would be "0a + 4b + 2c = 8".
        1.d. Solve this (potentially overdetermined) system of linear equations for a, b, c, ... which are the number of arguments for subroutines A, B, C, ... respectively.
    2. Otherwise, compute the number of arguments as per usual for non-recursive functions. Can then also determine if there's a return value after finding the number of arguments.

One issue with this is the problem of vector/struct arguments. This method will tell you the size of the stack space which is popped from the stack after calling each subroutine; however, it does not tell you the structure of said space. However, this is easy to calculate once you know the number of arguments - when you call the function in another subroutine, you can use the state of the stack at that call to determine the types of the sub's arguments (including how much space they take up).

*** END QUOTE ***

Don’t mean to take over this thread so I’ll make a new one if you want. I’d also be more than happy to talk to anyone on discord about this - feel free to message me (Lachjames#6269 - if you’re on the DS discord server you should be able to message me).

[AmanoJyaku 184]

31 minutes ago, lachjames said:

Hi

Welcome! It's great to meet a fellow victim programmer!

35 minutes ago, lachjames said:

 - My version works with ncsdis and I encourage you to do the same (and include your improvements in xoreos-tools) as one perfect library for disassembly is better than two that work most of the time. This is just my opinion and I don’t mean to diminish the work you’ve done on the disassembler (I’m sure it’s great, just like xoreos-tools is great) - I just feel that if we all merge our efforts we can make a better final product 

I'm unfamiliar with NCSDIS, so I read a man page. As far as I can tell, it produces an assembly-like output, DOT output, stack information, and control structures?

My binary does all of that, too. 🤣

Not sure how NCSDIS helps here or can be integrated, but I'm interested in looking at it to see what I might have missed.

36 minutes ago, lachjames said:

The problem is that the Skywing documentation is incorrect, and JSR does in fact work just like ACTION in that it modifies the stack pointer by popping off arguments. It doesn't push on a return value though (if there is one, space for that must have been allocated by the caller function before calling the callee). Perhaps what they mean is that the JSR does not do anything "intrinsically", but the function calling convention appears to be that functions pop their own arguments (which is more reasonable than making the caller do it every time; this is something I've actually taught before in computer science classes).

The documentation is accurate. It says the JSR instruction doesn't modify the stack. However, before you even get to the instruction description the section "Calling Subroutines and Engine Routines (ACTIONS)" states that "Invoking subroutines [Amano: that means JSR] or engine routines [Amano: that means ACTION] is done basically in the same manner.  Arguments are placed on the stack in reverse order.  The call is then made and the callee removes all the arguments from the stack prior to returning." So, somewhere inside the called function is where the arguments are popped.

This makes sense given that NCS was patterned after machine code, and the most common calling convention at that time, stdcall, had the callee clean the stack.

45 minutes ago, lachjames said:

Don’t mean to take over this thread so I’ll make a new one if you want. I’d also be more than happy to talk to anyone on discord about this

No worries, this is my thread to discuss the development of whatever this will be named. I'm not on Discord, but I will send you direct messages here if I run into any issues. You can also subscribe to this thread in case anyone else replies, particularly from DP, Salk, or DrMcCoy since they directly work with NCS files. 😊

[lachjames 24]

1 hour ago, AmanoJyaku said:

Welcome! It's great to meet a fellow victim programmer!

Thanks Great to meet you too!

1 hour ago, AmanoJyaku said:

Not sure how NCSDIS helps here or can be integrated, but I'm interested in looking at it to see what I might have missed.

Thanks for taking a look - my point was not so much that it does anything that your code doesn't, but more that you might be better off joining forces with @DrMcCoy by contributing to xoreos-tools, rather than both of you buliding separate NCS assembly readers (e.g. you suggested previously that you have suggestions for ncsdis). All code has bugs (especially mine...), including ncsdis and (I have to imagine) your assembler as well, so wouldn't it be better to combine the two and learn from each of them rather than keeping the implementations separate?

I just submitted a feature request on the xoreos-tools GitHub, discussing compiling xoreos-tools as a DLL rather than as executables. This might help your project too?

1 hour ago, AmanoJyaku said:

The documentation is accurate. It says the JSR instruction doesn't modify the stack. However, before you even get to the instruction description the section "Calling Subroutines and Engine Routines (ACTIONS)" states that "Invoking subroutines [Amano: that means JSR] or engine routines [Amano: that means ACTION] is done basically in the same manner.  Arguments are placed on the stack in reverse order.  The call is then made and the callee removes all the arguments from the stack prior to returning." So, somewhere inside the called function is where the arguments are popped.

This makes sense given that NCS was patterned after machine code, and the most common calling convention at that time, stdcall, had the callee clean the stack.

Sure, I agree with what you said; however, the issue I have is not so much their description of JSR in itself (which I agree from a certain point of view is correct), but rather how that clashes with the description of ACTION - in essence, it says ACTION pops variables and pushes the return value to the stack if there is one, but JSR does not modify the stack. The return value part is clear and true, but this might indicate to the reader (as it did for me) that the JSR calling convention requires the caller to remove arguments after the call. It's because of how ACTION is described that I misinterpreted the description of JSR. There are significant differences between how ACTION and JSR work (the main one being that JSR does not push a return value to the stack but ACTION does) so the section saying that invoking subroutines and engine routines is done "basically in the same manner" is, IMO, incorrect.

To be clear, I'm not meaning to rag on the Skywing documentation by any means - it's the only reason I've been able to get this far with my implementation of ncs2nss! It's brilliant and I'm very grateflu that it exists. Anyway, it's not a huge deal now as I figured it out in the end

[AmanoJyaku 184]

9 hours ago, lachjames said:

Thanks for taking a look - my point was not so much that it does anything that your code doesn't, but more that you might be better off joining forces with @DrMcCoy by contributing to xoreos-tools, rather than both of you buliding separate NCS assembly readers (e.g. you suggested previously that you have suggestions for ncsdis). All code has bugs (especially mine...), including ncsdis and (I have to imagine) your assembler as well, so wouldn't it be better to combine the two and learn from each of them rather than keeping the implementations separate?

That's the goal, yes. I only started this because @DrMcCoymade an appeal on another site I frequent, and I got swept up in the 15th anniversary of KOTOR modding euphoria. 😄

One potential challenge is that xoreos-tools' changelog states a need to update to C++11. My code is written in C++17; xoreos-tools may need a drastic overhaul before it can be integrated with my project.

9 hours ago, lachjames said:

I just submitted a feature request on the xoreos-tools GitHub, discussing compiling xoreos-tools as a DLL rather than as executables. This might help your project too?

I'll have to use first to see what it does and determine how I might use it. DLLs are a pain to deal with, I try to avoid them whenever possible.

[DrMcCoy 40]

xoreos and xoreos-tools are C++11 now, Phaethon is C++14. Though there are still vestiges of old stuff in there, like our own ScopedPtr which isn't necessary anymore now with std::unique_ptr. Gradually replacing that is on the TODO.

As for newer standards, these are also gradually on my purview. Moving over xoreos and xoreos-tools to C++14 shouldn't be that much trouble. C++17 needs some more evaluations. Probably still a bit off, just to make sure. And I need to check if our CI systems (Travis CI and AppVeyor) and my personal cross-compilers can be upgraded. And probably also need to wait on Coverity Scan, that has a few issues with some C++14 stuff in Phaethon already, from verdigris we pull in (which lets you write Qt code without moc).

Oh, and about the library request, I've written down my thoughts about it here: https://github.com/xoreos/xoreos-tools/issues/58#issuecomment-662419079

TL;DR: That's planned, but I don't think the time for that is now.

[AmanoJyaku 184]

I'm a suspicious person by nature, and I never like to promise anything before I deliver... But, I may be done by the end of September. I just completed a few tests and things are going well. Like, "woah, did that actually decompile???" well. There are three tasks remaining:

• Differentiating the different types of loops (they look really similar in byte code)
• Pairing the logic with the stack to refer to the proper variables
• Generating output whose style doesn't offend the reader

When that's complete I'll test against all 2,500+ K1/K2 NCS files. As long as life doesn't get in the way, I'll have a beta for K1/K2 soon. 😣

 

Wakanda Forever

[AmanoJyaku 184]

What's Taking So Long?

CPUs and NCS Bytecode

Spoiler

If you're reading this, I assume you have some experience with scripting and/or programming and an interest in NWScript. As such, you should be familiar with a basic concept: you supply a list of commands typically referred to as statements, and those statements are normally executed in sequence from top to bottom. For example:

Line 1) int i1;
Line 2) i1 = 5;
Line 3) int i2;
Line 4) i2 = 7;
Line 5) int i3;
Line 6) i3 = i1 + i2;

I program in C++, and this behavior is defined in subclause [stmt.stmt]: "Except as indicated, statements are executed in sequence." That means 1->2->3->4->5->6.

There are benefits to this behavior. First, CPUs perform best when working in sequence. Instructions and data can be loaded from memory into the CPU cache ahead of time, thus minimizing or eliminating entirely the time a CPU waits. The CPU is generally the fastest component in a device (a case can be made for the modern GPU), so we want to avoid accessing data from outside of the CPU as much as possible. Sequential loading from memory is done in chunks, thus lines 1-4 might be loaded when line 1 is accessed. Then, when the CPU accesses line 3 lines 5-6 are loaded before line 4 completes, allowing the CPU to immediately proceed to line 5. This is an oversimplification of CPU operation (there are no lines in compiled code, and all of the above fits into a modern CPU in one load), but the concepts are valid.

The second benefit is debugging. As seen in the example above, if the program throws an error at line 4 we know we can ignore lines 5 and 6, and concentrate on lines 1-4. If the program was changed so that i2 is assigned a value from a function, we know to look at the function. Why do we know this? Because, lines 1-3 cannot possibly fail unless the CPU is broken.

 

NWScript and NCS

Spoiler

OK, so what's this got to do with KoTOR? You write scripts in NWScript, which is based on C, and those scripts are compiled into a bytecode, NCS, that resembles CPU instructions. Thus, any game based on NWScript/NCS behaves similarly to a CPU. OK, fine. But, what's this got to do with your decompiler? The problem with scripting and programming languages is they aren't guaranteed to have compiled instructions that are identical to the language statements. The example above would normally be written in NWScript as follows:

Line 1) int i1 = 5;
Line 3) int i2 = 7;
Line 5) int i3 = i1 + i2;

Nice and tidy. Unfortunately, it doesn't look like this in NCS. The compiled code looks somewhat like the first example:

Brackets indicate annotated lines
[Line 1]
RSADDI                [int i1, integer variable declaration, 4 bytes (1 value) placed onto the top of the stack]
CONSTI 5            [an immediate value, 4 bytes (1 value) placed onto the the top of the  stack]
CPDOWNSP -8 4        [assignment, = in C-like languages, 4 bytes (1 value) copied down 8 bytes (2 values) into the stack]
MOVSP -4            [destruction of bytes on the stack, 4 bytes (1 value) destroyed]
[Line 2]
RSADDI                [int i2, integer variable declaration, 4 bytes (1 value) placed onto the top of the stack]
CONSTI 7            [an immediate value, 4 bytes (1 value) placed onto the the top of the  stack]
CPDOWNSP -8 4        [assignment, = in C-like languages, 4 bytes (1 value) copied down 8 bytes (2 values) into the stack]
MOVSP -4            [destruction of bytes on the stack, 4 bytes (1 value) destroyed]
[Line 3]
RSADDI                [int i3, integer variable declaration, 4 bytes (1 value) placed onto the top of the stack]
CPTOPSP -12 4        [copy bytes to the top of the stack, 4 bytes (1 value) copied from 12 bytes (3 values, i1) down in the stack]
CPTOPSP -12 4        [copy bytes to the top of the stack, 4 bytes (1 value) copied from 12 bytes (3 values, i2) down in the stack]
ADDII                [addition, + in C-like languages, destroy 2 values on the top of the stack, place the result on the top of the stack]
CPDOWNSP -8 4        [assignment, = in C-like languages, 4 bytes (1 value) copied down 8 bytes (2 values) into the stack]
MOVSP -4            [destruction of bytes on the stack, 4 bytes (1 value) destroyed]

That's 14 NCS operations, compared to 3 consolidated NWScript lines and 6 unconsolidated lines!

Before we look at another example, it's important to address something we ignored above: "those statements are normally executed in sequence" and "Except as indicated, statements are executed in sequence". When are statements not executed in sequence? When we use control structures.

 

Control Structures

Spoiler

Control structures are a high-level language concept. They allow us to break from the sequential execution of code. In C-like languages, including NWScript, those structures include:

Selection statements

• if (condition)
• if (condition) else
• switch (condition)

Iteration statements

• for (; condition; )
• while (condition)
• do while(condition)

Jump statements

• break
• continue
• return

Naturally, control structures complicate things. A lot. Especially since some operators look like control structures, for example logical AND and logical OR.

 

Difficulties and Errors

Spoiler

Now, let's look at another example:

int nDC;
object oTarget;
int nTrapID = GetTrapBaseType(OBJECT_SELF);
location lTrap = GetLocation(OBJECT_SELF);

Db_PostString("Trap Fired", 5,5,4.0);

if( nTrapID == TRAP_BASE_TYPE_FLASH_STUN_MINOR ||
    nTrapID == TRAP_BASE_TYPE_FLASH_STUN_AVERAGE ||
    nTrapID == TRAP_BASE_TYPE_FLASH_STUN_DEADLY )

Simple enough. Just imagine what this looks like in NCS:

RSADDI                    [int nDC]
RSADDO                    [object oTarget]
RSADDI                    [int nTrapID]
CONSTO 0                [OBJECT_SELF]
ACTION 531 1            [GetTrapBaseType]
CPDOWNSP -8 4            [nTrapID = GetTrapBaseType(OBJECT_SELF)]
MOVSP -4
RSADD Location            [location lTrap]
CONSTO 0                [OBJECT_SELF]
ACTION 213 1            [GetLocation]
CPDOWNSP -8 4            [lTrap = GetLocation(OBJECT_SELF)]
MOVSP -4
CONSTF 4.000000
CONSTI 5
CONSTI 5
CONSTS 10 Trap Fired
JSR Db_PostString        [Db_PostString("Trap Fired", 5, 5, 4.0)]
CPTOPSP -8 4            [nTrapID]
CONSTI 0                [TRAP_BASE_TYPE_FLASH_STUN_MINOR]
EQUALII                    [==]
CPTOPSP -4 4            [No good!!!]
JZ 161                    [No good!!!]
CPTOPSP -4 4
JZ 177
CPTOPSP -12 4            [nTrapID]
CONSTI 1                [TRAP_BASE_TYPE_FLASH_STUN_AVERAGE]
EQUALII                    [==]
LOGORII                    [||]
CPTOPSP -4 4            [No good!!!]
JZ 207                    [No good!!!]
CPTOPSP -4 4
JZ 223
CPTOPSP -12 4            [nTrapID]
CONSTI 2                [TRAP_BASE_TYPE_FLASH_STUN_DEADLY]
EQUALII                    [==]
LOGORII                    [||]
JZ 728                    [if]

We see five Jump-if-zero's (JZ). JZ is used for if (condition) selection statements, and for (; condition; ) and while (condition) iteration statements. (I have yet to find a do-while statement in any of the game files, I have no idea what it looks like.) Right off the bat, there's a need to differentiate the last JZ [the if (condition)] from the first four. The first four JZ's are part of the logical OR chain. Which means we need to group them together since they make up the condition!

There are two more problems, which I put into the annotations. The first is that two of those JZs are superfluous, they don't do anything. The second is worse: the logical OR isn't short-circuiting. As soon as an expression evaluates to "true" the logical OR chain should break, but it doesn't. The result is that someone who ignores best practices (or has a compelling need) and uses the chain to produce side effects will produce a script that does the wrong thing!

So, I have to do more than just decompile code. I must also decompile code that is incorrect, and decide on whether or not to fix this. Which means reaching out to the license holder to get them to introduce the fix into all NWScript/NCS games!!!

All of this was taken into account when I said I think I can get this done by the end of September. Just thought people might be interested in the gory details.

Also, as I work on this I'm encountering what appears to be poorly coded scripts. For example:

Spoiler

 

    //FLASH STUN MINE
    if( nTrapID == TRAP_BASE_TYPE_FLASH_STUN_MINOR ||
        nTrapID == TRAP_BASE_TYPE_FLASH_STUN_AVERAGE ||
        nTrapID == TRAP_BASE_TYPE_FLASH_STUN_DEADLY )

    //FRAGMENTATION MINE
    else if(nTrapID == TRAP_BASE_TYPE_FRAGMENTATION_MINE_MINOR  ||
            nTrapID == TRAP_BASE_TYPE_FRAGMENTATION_MINE_AVERAGE ||
            nTrapID == TRAP_BASE_TYPE_FRAGMENTATION_MINE_DEADLY)

    //LASER SLICING TRAP - THIS IS NOW THE PLASMA MINE
    else if(nTrapID == TRAP_BASE_TYPE_LASER_SLICING_MINOR ||
            nTrapID == TRAP_BASE_TYPE_LASER_SLICING_AVERAGE ||
            nTrapID == TRAP_BASE_TYPE_LASER_SLICING_DEADLY )

    //GAS POISON TRAP
    else if(nTrapID == TRAP_BASE_TYPE_POISON_GAS_MINOR ||
                       TRAP_BASE_TYPE_POISON_GAS_AVERAGE ||
                       TRAP_BASE_TYPE_POISON_GAS_DEADLY)

 

That last one is doesn't look right. May need to create a second WIP: the Script-Fixing Project. Sigh...

[Salk 374]

Just wanted to thank you for a very interesting and detailed examination of NWScript and how its flaws could actually hurt people creating new code without knowledge that sometimes it could turn into something wrong (the "OR" condition - it would be great if your decompiler could fix this).

Thanks for all the hard work you're putting into this.

[JCarter426 1,215]

14 hours ago, AmanoJyaku said:

So, I have to do more than just decompile code. I must also decompile code that is incorrect, and decide on whether or not to fix this.

I would say fix it where possible. I can't imagine a situation where someone would purposefully write a condition with side effects as a secondary condition with the intent that short-circuit evaluation would be ignored, or more importantly, any situation where that would be needed. It's far more likely that there are scripts that are taking performance hit from the lack of short-circuit evaluation, and could potentially be causing bugs. The random loot in KOTOR 2 overflows the stack if you spawn too many items at once, for example. There could be more intensive operations, like in the AI, that could potentially be causing problems. Maybe that would even account for bugs such as creatures randomly not attacking in the middle of combat.

I'm certainly worried I might've written code under the assumption that short-circuit evaluation would be obeyed. I suppose if that's true, I could invert the logic to use && in the meantime, since that does seem to short-circuit properly.

14 hours ago, AmanoJyaku said:

Jump statements

• break
• continue
• return

I'm almost afraid to ask, but does NWScript have a goto statement? I haven't seen any example of it in code, or any reference to it, so I assume not.

14 hours ago, AmanoJyaku said:

Also, as I work on this I'm encountering what appears to be poorly coded scripts.

Oh, I hadn't seen this one before, but I've seen problems like it. It's understandable considering that not all the developers were computer scientists, and even designers like David Gaider and Chris Avellone did incidental scripting to take some of the burden off the programmers, but the downside to that is not everybody necessarily knew what they were doing. Plus the one you quoted looks like it might've been a copy/paste error, considering that it's only the last branch that's wrong. Stupid mistakes can happen to anyone.

[AmanoJyaku 184]

11 hours ago, JCarter426 said:

I would say fix it where possible. I can't imagine a situation where someone would purposefully write a condition with side effects as a secondary condition with the intent that short-circuit evaluation would be ignored, or more importantly, any situation where that would be needed. It's far more likely that there are scripts that are taking performance hit from the lack of short-circuit evaluation, and could potentially be causing bugs. The random loot in KOTOR 2 overflows the stack if you spawn too many items at once, for example. There could be more intensive operations, like in the AI, that could potentially be causing problems. Maybe that would even account for bugs such as creatures randomly not attacking in the middle of combat.

I doubt performance is a concern. We're talking dozens of wasted cycles out of billions. It wasn't a problem back in 2003, it's even less of a problem today.

OTOH, bugs need to be dealt with.

11 hours ago, JCarter426 said:

I'm certainly worried I might've written code under the assumption that short-circuit evaluation would be obeyed. I suppose if that's true, I could invert the logic to use && in the meantime, since that does seem to short-circuit properly.

Tsk tsk. Placing side effects into your conditions. Shame on you. 😛

11 hours ago, JCarter426 said:

I'm almost afraid to ask, but does NWScript have a goto statement? I haven't seen any example of it in code, or any reference to it, so I assume not.

Fortunately, I haven't seen any in scripts, nor do I see it in NWLexicon. Goto is bad, anyway, so I would just be an ass an not translate it. 😜

[DrMcCoy 40]

Interesting that you're encountering the same short-circuiting bug I've seen in NWN (I wrote about it here, though everyone reading is probably aware: https://xoreos.org/blog/2016/01/12/disassembling-nwscript-bytecode/).

Up until now, I had assumed they fixed that bug by the time they moved to other games. I know that the bug is in some scripts in NWN, but not in all. And I know that the compiler in the last released toolset does not have that bug anymore. I'd be interested to know when exactly it was fixed...

[AmanoJyaku 184]

Could be someone used an old version of the compiler, even for the official game.

[JCarter426 1,215]

1 hour ago, AmanoJyaku said:

Tsk tsk. Placing side effects into your conditions. Shame on you. 😛

Nah, it's not side effects I'm worried about, it's stuff like checking if an object is valid, and only doing something if so. Safe navigation. I don't remember any specific code I wrote where that might be a problem, but I can definitely imagine the possibility. I probably would've used && and it would be safe though.

1 hour ago, DrMcCoy said:

Up until now, I had assumed they fixed that bug by the time they moved to other games. I know that the bug is in some scripts in NWN, but not in all.

@DarthParametric and I observed in some tests that the compiler we have is definitely not the most up-to-date one, and it seems like it was the case with the one BioWare used as well because the game scripts are full of unused garbage included from header files that the same update to the NWN compiler was supposed to scrub out.

[AmanoJyaku 184]

54 minutes ago, JCarter426 said:

Nah, it's not side effects I'm worried about, it's stuff like checking if an object is valid, and only doing something if so. Safe navigation. I don't remember any specific code I wrote where that might be a problem, but I can definitely imagine the possibility. I probably would've used && and it would be safe though.

@DarthParametric and I observed in some tests that the compiler we have is definitely not the most up-to-date one, and it seems like it was the case with the one BioWare used as well because the game scripts are full of unused garbage included from header files that the same update to the NWN compiler was supposed to scrub out.

*flips table*

I am not fixing the game scripts. I am NOT fixing the game scripts!!!

OK, I'll fix the game scripts.

[AmanoJyaku 184]

On 9/5/2020 at 6:33 AM, JCarter426 said:

The random loot in KOTOR 2 overflows the stack if you spawn too many items at once, for example.

 

Edit: I think the following is wrong. I haven't worked on subroutines yet, so I think the [?????] is the reserved space for the return value of GetTreasureBundle().

 

I'm not sure if this is the source of the stack bug, but I did find something interesting:

Spoiler

//Snippet from k_contain_unlock.nss
void PlaceTreasureDisposable(object oContainer = OBJECT_SELF, int numberOfItems = 1, int nItemType = 900)
{
    string sItem;
    string sItemName;
    int nItemQuantity = 1;
    int j;

    sItem = GetTreasureBundle(nItemLevel, nItemType);
}

 

Now, compare the compiled code:

Spoiler

//Snippet from k_contain_unlock.ncs
Block   1444, 1474
1444    RSADDS					[string sItem]
1446    RSADDS					[string sItemName]
1448    RSADDI					[int nItemQuantity]
1450    CONSTI 1				[1]
1456    CPDOWNSP -8 4				[int nItemQuantity = 1]
1464    MOVSP -4

1470    RSADDI					[int j]

1472    RSADDS					[?????]

Block   1474, 1550
1474    CPTOPSP -44 4				[nItemType]
1482    CPTOPSP -28 4				[nItemLevel]
1490    JSR 1766				[GetTreasureBundle(nItemLevel, nItemType)]
1496    CPDOWNSP -20 4				[sItem = GetTreasureBundle(nItemLevel, nItemType)]
1504    MOVSP -4

 

That [?????] is a string, and an extra stack object that doesn't exist in the NSS! Might not have seen this if I hadn't been using this file to test my decompiler for the last 6 months. I guess it could be changed to a NOP, which is the same size and doesn't do anything. Still, I now need to count the stack objects and confirm it isn't doing anything weird.

[JCarter426 1,215]

Hmm, is that not just from from GetTreasureBundle()? That function calls another function that returns a string containing both the item template and the amount of items, and then extracts the the template from it.

My guess is that the stack issue is from the recursive function GetTreasureSpecific(). It still happens with my cleaned up version, and actually it happens with a critical capacity of fewer items due to my changes that eat up more of the stack.

In my tests I think the original code failed at somewhere between 100 and 200 items, while my code fails at about 60. It's should be fine for all realistic use cases but it would also be nice if the problem could be avoided.

[AmanoJyaku 184]

2 hours ago, JCarter426 said:

Hmm, is that not just from from GetTreasureBundle()? That function calls another function that returns a string containing both the item template and the amount of items, and then extracts the the template from it.

Yeah, that was what I wrote in my edit. I left the original post up in case someone with experience could explain what I'm seeing. Thanks!

[JCarter426 1,215]

I've fixed a lot of bugs in that code and documented it, which might help. Although I have to get around to fixing the bugs I introduced to it by foolishly forgetting how switch cases work... I'll get back to you.

[AmanoJyaku 184]

@JCarter426

Nah, I just read some more code and confirmed that my original post was wrong. The "extra" RSADDx is for subroutine return values.

Speaking of which, once I confirm that I know what the hell I'm doing I plan on documenting NCS. So far, the best resources are:

1. Tim Smith’s documentation on the op codes, which is incomplete and has a few errors
2. Ken Johnson (Skywing)'s documentation on his own unfinished decompiler
3. DrMcCoy's documentation on their own unfinished decompiler

I will explain how NWScript translates to NCS op codes. For example, it seems as if the only use of JNZ is for switch statements. There's no reason I can think of for why it couldn't be used in other ways, but it looks like the compilers all default to JZ for boolean conditions. Even if JZ ! true could be optimized to JNZ true. So wasteful...

[DarthParametric 3,785]

Concerning k_trp_generic...

On 9/5/2020 at 5:13 AM, AmanoJyaku said:

That last one is doesn't look right

    else if(nTrapID == TRAP_BASE_TYPE_POISON_GAS_MINOR ||
                       TRAP_BASE_TYPE_POISON_GAS_AVERAGE ||
                       TRAP_BASE_TYPE_POISON_GAS_DEADLY)

Yet it does actually work in-game:

The poison damage applied per-tick is the correct amount

int POISON_DAMAGE_VIRULENT        = 5;

 

[AmanoJyaku 184]

On 9/13/2020 at 10:40 AM, DarthParametric said:

Concerning k_trp_generic...

Yet it does actually work in-game:

 

The poison damage applied per-tick is the correct amount

Yes, because identification of the mine level occurs inside the if block. The problem is the if condition to get to that block always evaluates to "true".

int TRAP_BASE_TYPE_POISON_GAS_MINOR             = 9;
int TRAP_BASE_TYPE_POISON_GAS_AVERAGE           = 10;
int TRAP_BASE_TYPE_POISON_GAS_DEADLY            = 11;

nTrapID == TRAP_BASE_TYPE_POISON_GAS_MINOR ||
                       TRAP_BASE_TYPE_POISON_GAS_AVERAGE ||
                       TRAP_BASE_TYPE_POISON_GAS_DEADLY

  
(nTrapID == 9) || 10 || 11
  
  
(true or false) || true || true

In practice, this isn't a problem because it's the last statement in the chain of if-else statements. By this point, the only mine type that hasn't been checked is poison gas. The condition isn't even necessary, since it must be a poison gas mine.

However, if the poison gas test was ahead of any other mine type test then all subsequent types would be treated as poison gas.

//FLASH STUN MINE
if( nTrapID == TRAP_BASE_TYPE_FLASH_STUN_MINOR ||
		nTrapID == TRAP_BASE_TYPE_FLASH_STUN_AVERAGE ||
        nTrapID == TRAP_BASE_TYPE_FLASH_STUN_DEADLY )
{}
//GAS POISON TRAP
//BAD!!!
else if(nTrapID == TRAP_BASE_TYPE_POISON_GAS_MINOR ||
        TRAP_BASE_TYPE_POISON_GAS_AVERAGE ||
        TRAP_BASE_TYPE_POISON_GAS_DEADLY)
{}
//FRAGMENTATION MINE
else if(nTrapID == TRAP_BASE_TYPE_FRAGMENTATION_MINE_MINOR  ||
        nTrapID == TRAP_BASE_TYPE_FRAGMENTATION_MINE_AVERAGE ||
        nTrapID == TRAP_BASE_TYPE_FRAGMENTATION_MINE_DEADLY)
{}
//LASER SLICING TRAP - THIS IS NOW THE PLASMA MINE
else if(nTrapID == TRAP_BASE_TYPE_LASER_SLICING_MINOR ||
        nTrapID == TRAP_BASE_TYPE_LASER_SLICING_AVERAGE ||
        nTrapID == TRAP_BASE_TYPE_LASER_SLICING_DEADLY )
{}

I'm being a nitpick, because the game is unlikely to be modified to add new mine types. But, with things like Xoreos it's not impossible.

[DarthParametric 3,785]

It is modified in TSL, but Obsidian fixed the If statement in their version. We were evaluating whether or not to fix the K1 version as part of K1CP, but there seems to be no need, since the vanilla version works as-is. Anyone wanting to add custom ones would need their own version of the script anyway, so it would be up to them to fix it.

[AmanoJyaku 184]

@DarthParametric

I did say I will not fix the game scripts, right?

When I'm done with the decompiler, I will look into each script to determine what, if anything, needs to be fixed. It's entirely possible that the NCS files are different from the NSS files, such as k_trp_generic which has a bit of dead code.

Of course, with 2,500+ files I'm in no rush to try and fix things. Especially since I haven't even completed the decompiler. Which now has a name, btw: FEANCS. You get a cookie if you can figure out the origin.

[AmanoJyaku 184]

Sometimes, I learn more from failure than from success...

I spent two weeks troubleshooting an algorithm that didn't always work. So, I added some functionality to assist in diagnosing the problem. Which lead to a few features updates!

Directory Mode

Now, when you supply a path the type is detected as either a file or directory. If it's a directory, all subdirectories are scanned and all files are processed!

Version Detection

The algorithm was fine, the problem was the input. I was using K2 function definitions, some of which had changed from K1. Now, NCS files are identified as K1 or K2!

Conditional Input Detection

The algorithm in question was alluded to in the September 4 post section about control structures. You will often see code like this:

Spoiler

if(sModule == "851NIH" ||
sModule == "852NIH" ||
sModule == "901MAL" ||
sModule == "902MAL" ||
sModule == "903MAL" ||
sModule == "904MAL" ||
sModule == "905MAL" ||
sModule == "906MAL")
{
	//block of code
}

 

This is a pain to parse. The programmer sees one if statement, but the NCS file has 15 potential if statements! Seven of those appear to be extra, I haven't tested the logic to see if I can safely remove them from the compiled code. Still, that leaves us with eight potential if statements [e.g. if (sModule == "851NIH") { /*do stuff*/ }], which must be evaluated to see if they can be combined. That's what the algorithm does. And now that K1 and K2 functions are correctly identified, the algorithm correctly combines them as input to the actual if statement!

To Do

That leaves the following tasks:

1. Evaluation of switch statements
   1. I haven't done this yet because ignoring them doesn't change the way the rest of an NCS file is processed, and my time is better spent on other tasks
2. Evaluation of for and while loops
   1. They look identical, with the only potential difference being an incremented or decremented value at the end of a for loop
   2. Now that the algorithm described above has been completed, it should be easy to determine the rest of the code that makes a for loop unique
   3. I've temporarily given up on do-while loops because only one file has one, and I'm not entirely certain it's in the compiled NCS file
3. Merging the algorithm with the virtual stack
   1. Once all control structures have been correctly identified, it will be necessary to identify variables created and destroyed inside scopes
   2. This will allow for the identification of subroutine input parameters and return values
   3. I've avoided using the virtual stack since I believe this is what has caused problems working with recursive functions for other decompilers
4. Evaluating subroutines
   1. This is a big one, because callee input parameters and return values affect the caller subroutines
   2. I've been hard-coding both as a shortcut, but that only works for the files I'm currently testing
5. Figuring out the DESTRUCT op code
   1. I've seen this used to destroy variables on the stack that aren't necessary, but prevent the top-of-stack behavior used by NCS
   2. Although this shouldn't be necessary, since the desired variable could just be copied to the top of the stack using the CPTOPSP op code...

I should clarify that the algorithm does more than detect conditional input. It combines NCS op codes that make up NWScript statements. For example:

RSADDS
CPTOPSP -8 4
string IntToString(int)
CPDOWNSP -8 4
MOVSP -4

Is correctly grouped as:

string String = IntToString(Int);

[DarthParametric 3,785]

19 minutes ago, AmanoJyaku said:

Now, NCS files are identified as K1 or K2

Is there a game-specific identifier in the NCS header? I thought both were flagged as NCS V1.0B.