Breaking Eggs And Making Omelettes

Topics On Multimedia Technology and Reverse Engineering


Archives:

RE Math Puzzle

August 5th, 2007 by Multimedia Mike

It’s late and it has been a long day, but I’m still trying to reverse engineer a particular math function. RE is such a wonderful endeavor for those who are keen on bizarre little number puzzles. Check this out and see if you can understand the overall effect:

  • pick some number, we’ll call it A
  • shift A left by 29, effectively multiplying A by 229
  • subtract A from the result, assign to B, so now B = A * 229 – A
  • multiply B by 8 and add A, assign to C: C = B * 8 + A

What is the net result of the bit shifts and subtractions? I have a feeling that there must be multiple operations combined into one, sort of like when a DCT-based video codec dequantizes and reorders coefficients at the same time. Time for some more math:

  C = B * 8 + A
  C = 8 * (A * 229 - A) + A
  C = 8 * A * 229 - 8 * A + A
  C = 23 * 229 * A - 7 * A
  C = 232 * A - 7 * A

In order to negate an N-bit integer in 2s complement arithmetic, you can subtract that integer from 2N. For example, to negate 1 as a 32-bit integer: (232 = 0x100000000) – 1 = (0xFFFFFFFF = -1). So the algorithm above appears to negate a number while multiplying it by 7 at the same time. These people were resolute to never ever use an actual ‘imul’ instruction unless absolutely necessary.

Well, I’m glad we had that little talk. I can sleep soundly tonight. I just hope this still makes sense to me in the morning.

Posted in Reverse Engineering | 6 Comments »

Next Entries »