Comments (1)
As discussed privately with @DrMcCoy and on DeadlyStream, I have a potential solution to the recursion issue. Copy/pasting my algorithm below:
*** BEGIN QUOTE ***
Hey so I've realized that this heuristic analysis [edit: this is referring to another algorithm I suggested, not the guessing one - I still suspect that might work] 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:
- 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. - 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 ***
To be clear, even though the linear system might be overdetermined, it should still have only one solution. One easy way to implement this is to use a linear algebra solver for overdetermined systems, and check the residual is zero (within a tolerance).
I've implemented this algorithm in my ncs2nss repo if you're interested. It doesn't work all the time, but I suspect this is due to either bugs in the rest of my code (there are still many) or compiler errors. I feel the latter can be resolved with a modification to the algorithm, but we can discuss that later.
from xoreos-tools.
Related Issues (20)
- xml2gff not included in xoreos-tools-0.0.5 release? HOT 7
- XML2GFF: Tool needs to be game/encoding aware HOT 1
- XML2GFF: Serialize color codes HOT 7
- NCSDIS: Control flow analysis failure in do-loop nested in while-loop HOT 15
- FEATURE: Compile xoreos-tools as a DLL/library HOT 6
- FEATURE: Make more tools read stdin for input HOT 5
- FEATURE: "File picker" for RIM/ERF/MOD files HOT 9
- ERF: MOD files have incorrect prefix HOT 4
- ERF: Recursion leads to infinite loop HOT 1
- Clarify XML format for xml2gff HOT 1
- GFF2XML -> XML2GFF (invalid base64 length) HOT 5
- UNOBB: Add support for KotOR2 Android obb archives HOT 29
- Issue running configure to build project: Syntax error near unexpected token `FT2 HOT 3
- xml2gff: NWN:EE invalid file format HOT 12
- error while compiling HOT 6
- another error while compiling HOT 1
- FEATURE: Add tool to convert TGA back to TPC
- CONVERT2DA: Code and documentation mismatch for the parameters HOT 5
- xml2tlk gives error when trying convert back cp1251 xml HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from xoreos-tools.