Interdependent table - branching

[0x401000]

There are some methods to determine the amount of branching. For example when building code that describes the table needed to calculate the amount of branching (long or short jmp). I do not know how to fully solve this problem, there is a solution but it is false and not a full-fledged (counting the number of branching between the current).

Сonditional branching can be short and long. To know the size of the 1 st branch needs to know the size of the second. If the branch set, then the algorithm requires conversion of their size, just count the number of long jmp is not suitable.

You can list all the series of branching, considering their original brief, to make the current jmp long to scan the entire table for validity branch. This requires a very long time, so this algorithm is not applicable. There was also an idea to solve the system of equations, but it is too difficult, too, and probably not optimal.
Compilers perform it like that. Maybe not quite correct. Give please the essence of the algorithm.

Thanks!

[Slugsnack]

i might be misunderstanding but this is how i would do it. create a recursive function which has the basecase of having no jumps at all in which case it returns 0. otherwise it returns 1 added onto the return of the same function call on the rest of the code. the complexity maybe comes in when you find yourself in an infinite or long loop i suppose

not sure i'm 100% understanding what it is you want though

[Tedd]

If I understand what you mean...

Fix inner jumps first (those without any jumps between them and their target - just fixed linear code) and then you can consider those fixed, and work your way out to jumps around those code chunks, fix them, and so on.
If you make a list of all the jumps and their targets, sorted by source address, then you can go through the table repeatedly, fixing the jumps, and removing the fixed ones as you go - you've finished when the list is empty.

[0x401000]

If I understand what you mean...

Fix inner jumps first (those without any jumps between them and their target - just fixed linear code) and then you can consider those fixed, and work your way out to jumps around those code chunks, fix them, and so on.
If you make a list of all the jumps and their targets, sorted by source address, then you can go through the table repeatedly, fixing the jumps, and removing the fixed ones as you go - you've finished when the list is empty.

It is not clear. You can draw something? schematic?

[Neo]

Do you mean something like this?  If so, the paper there describes a simple way to do it in linear time.  (A summary of the algorithm is on page 3.)  There's a slightly simpler way to do it in quadratic time, and it's probably not noticeably slower (if at all) in the average case.

[hutch--]

If the question was a bit better defined there would be a number of useful ideas to float around. A TREE would be one idea, alternatively an array of addresses of items is another and there are many other possibilities.

[0x401000]

Do you mean something like this?  If so, the paper there describes a simple way to do it in linear time.  (A summary of the algorithm is on page 3.)  There's a slightly simpler way to do it in quadratic time, and it's probably not noticeably slower (if at all) in the average case.

Thank you for your paper! :U

If the question was a bit better defined there would be a number of useful ideas to float around. A TREE would be one idea, alternatively an array of addresses of items is another and there are many other possibilities.

I therefore asked about the possibilities and the best option. The paper describes all true, but I did not notice the dynamic alterations, such as when the minor changes have occurred, one jmp changes addressing the others. That is, I think you need to re-run the algorithm, but this is not an optimized version?

I will try to write an example. It can be scattered issues. Thanks !

[Neo]

Thank you for your paper! :U

You're welcome  :bg

I therefore asked about the possibilities and the best option. The paper describes all true, but I did not notice the dynamic alterations, such as when the minor changes have occurred, one jmp changes addressing the others. That is, I think you need to re-run the algorithm, but this is not an optimized version?

The simple quadratic time algorithm is to encode as all short jumps then run through the list of jumps repeatedly as you suggest (though usually very few times) updating any jumps that now need to be long jumps.  My algorithm is also optimal, but only updates jumps within 128 bytes of any that need to be long jumps, instead of re-running through all of them.  It can get away with this because it doesn't try re-encoding anything until it's used this updating to figure out which jumps are long and which are short.

That said, it's probably so uncommon that the length of one jump being long makes another jump long that just running through the list of jumps until there are no more updates is probably faster on average; I was just curious as to whether there was one guaranteed to be linear time and still pretty good on average.  :wink  The only reasonable case I could think of where the quadratic time algorithm would be bad is if you had a big if/else if/else if/.../else structure, with all of the cases almost 128 bytes and the else case larger than 128 bytes.

There's a Java implementation of my algorithm here, though it may be tough to follow.