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 »

6 Responses

  1. Kostya Says:

    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.

  2. Reimar Says:

    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*

  3. Multimedia Mike Says:

    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.

  4. Reimar Says:

    Well, I said B = -A, that still gives C = 8*B+A = -8*A + A = -7*A, unless I miss something essential that A

  5. Multimedia Mike Says:

    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.

  6. Reimar Says:

    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 ;-)