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 »
August 6th, 2007 at 12:07 am
Hmm, in another piece of code there was a construction like this:
if(a &1)
t[1-var64]++;
if(a & 2)
t[var64^-1]++;
But A XOR -1 = 1-A on most of the modern architectures (including x86).
And avoiding ‘imul’ mostly results in many lea’s, especially I remember Truespeech codec which has the longest series of such multiplications I’m aware of.
Also don’t forget to look at one of the Michael’s favourite pages (at least I think so) for hints.
August 7th, 2007 at 1:49 am
So was B used somewhere else as well? Because otherwise setting B = -A seems like giving the same result to me (assuming you only use the lowest 32 bits of the result C).
Or did someone just attempt a bit of obfuscation? *g*
August 7th, 2007 at 6:21 am
Remember, there’s also the multiplication by 7 in this operation. Otherwise, yeah, a straight two’s complement negation would be easiest.
They could have meant for obfuscation. But I’m pretty sure that’s just a side effect of their speed freakery.
August 7th, 2007 at 7:48 am
Well, I said B = -A, that still gives C = 8*B+A = -8*A + A = -7*A, unless I miss something essential that A
August 7th, 2007 at 9:35 am
The mathematical definition that I posted obscured the fact that the original ASM uses a series of lea instructions to perform the implicit multiplications. The route the coders took is likely more conducive to fewer total ASM instructions, and has no actual imul instructions.
August 7th, 2007 at 12:02 pm
Sure, I only don’t get how the 2 ** 29 comes in to it.
I would have thought they’d do something like
mov ebx,eax
neg ebx
lea ecx,[8*ebx+eax]
which I think should still give -7*eax in ecx.
Well, not important anyway though ;-)