Assembling Progress and a Paper

I’ve been making lots of progress on assembling support for Inventor IDE in the past couple of weeks.  In particular, I’ve looked at what I’m calling the x86 jump encoding problem.  The only piece of literature I’ve found referring to this problem calls it branch displacement optimization, but it allows convoluted declarations that are never useful, making the problem NP-complete.  There is a simple quadratic-time algorithm to solve the problem optimally (assuming there are no declarations of arrays whose size depends on the negative of the size of any code; if you do, you’ve got bigger problems than a few extra bytes of data), and I went in search of a simple linear-time algorithm to solve it optimally.

In the past week I managed to create such an algorithm. 🙂  It is simple, using no obscure data structures, no recursion, and no randomization, plus it should be as fast or faster than the quadratic-time algorithms on average.  I’ve also since come up with a simple way to eliminate most jumps from consideration in the single pass through to determine the initial jump distances.  Simplicity is nice.

On a semi-related note, I won’t have the next video in my video tutorial on assembly language out by year’s end because of my current lack of internet access at home and all of the time I’ve been spending on Inventor IDE, but it should be out no later than January 5th or 6th.  Sorry for the delay.

~ by Neil Dickson on December 30, 2008.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: