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.
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.
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*
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.
Well, I said B = -A, that still gives C = 8*B+A = -8*A + A = -7*A, unless I miss something essential that A
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.
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 ;-)