Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: Reversing SHR EAX,1F

  1. #1

    Question Reversing SHR EAX,1F

    OK maybe this was too hard, or stupid or something, got several views but no help so moderator feel free to delete?
    ------


    I'm trying to figure out what some lines of assembly language would look like in a higher level language such as C but also understand the WHY the compiler optimizer would code it like this verses something more direct.

    Code:
    IMUL ECX <- EDX:EAX = EAX * ECX
    SAR EDX, 5 <- EDX / 32
    MOV EAX, EDX 
    SHR EAX, 1F <--- 1F being 31 doesn't this always just clear out the register?
    ADD EAX, EDX <- so basically 0 + EDX
    CDQ <- wipes out EDX extends EAX so EDX:EAX?
    I'm finding one of the best ways to figure this stuff out is to put the code to a test? Take values and plug them in and see what happens?

    SO I try to take the extremes
    EAX = 7FFFFFFF
    ECX = 7FFFFFFF

    3FFFFFFF00000001

    3FFFFFFF S
    EDX:EAX = 3FFFFFFF00000001
    EDX = 3FFFFFFF / 20(32 Decimal)

    SAR, 5 = 1FFFFFF

    SHR EAX, 1F (so 0)
    ADD EAX, EDX
    EAX = 1FFFFFF
    CDQ -- EDX = 00000000 EAX = 01FFFFFF

    however negative makes it a bit tricky.... worst case the SHR seems to leave a 1 in EAX
    SO
    EAX = 80000000
    ECX = 7FFFFFFF

    EDX:EAX = EDX:C0000000 EAX:80000000
    SAR EDX, 5 - EDX:FE000000
    MOV EAX, EDX
    SHR EAX, 1F EAX = 1

    EAX = FE000001

    CDQ creates
    EDX:EAX = FFFFFFFF:FE000001

    So it's not any kinda absolute function or anything? I hope someone has worked this one out before or can figure it out.
    Last edited by captcpsc; May 2nd, 2012 at 13:28.

  2. #2
    Naides is Nobody
    Join Date
    Jan 2002
    Location
    Planet Earth
    Posts
    1,647

    Look at the SIGN bit

    Without going into a step by step, this piece of code is isolating the sign bit of a 32 bit variable and "sticking" it into the result. Think: how do you assure that: ( -3) * (-4) == (+12)?

  3. #3
    Quote Originally Posted by naides View Post
    Without going into a step by step, this piece of code is isolating the sign bit of a 32 bit variable and "sticking" it into the result. Think: how do you assure that: ( -3) * (-4) == (+12)?
    I'm kinda a newbie to assembly so I think in this case some step by step would help? See when I take your example and apply it,

    Code:
    	mov eax, -3
    	mov ecx, -4
    	imul ecx
    	sar edx, 5
    	shr eax, 1fh
    	add eax, edx
    	cdq
    	retn
    after the imul instruction

    EDX: 00000000
    EAX: 0000000C

    the sar instruction then is useless on edx, then the shr basically empties eax, because it's not negative then the add is 0 + 0... CDQ just extends EAX which again will result in no change because EDX is already 0? I'm not sure what you are saying?

  4. #4
    the SAR instruction preserves your sign.
    make +a*-b/+c, where +c is a power of 2 (>32)
    I want to know God's thoughts ...the rest are details.
    (A. Einstein)
    --------
    ..."a shellcode is a command you do at the linux shell"...

  5. #5
    Quote Originally Posted by Maximus View Post
    the SAR instruction preserves your sign.
    make +a*-b/+c, where +c is a power of 2 (>32)

    Are you sure you don't mean the SHR instruction preserves your sign? If I do

    Code:
    .code
    start:
    	mov eax, 3
    	mov ecx, -4
    	imul ecx
    	sar edx, 5
    	shr eax, 1fh
    	add eax, edx
    	cdq
    	retn	
    
    end start
    So A = 3, B = (-4) C = 5 which is 32 (decimal) after executing the SAR instruction EDX is still FFFFFFFF
    "The sar instruction shifts all the bits in the destination operand to the right one bit, replicating the H.O. bit'

    so FFFFFFFF is of course 11111111111111111111111111111111 (32 of em) so SAR EDX, 5 is still going to be 11111111111111111111111111111111 or FFFFFFFF.

  6. #6
    Try to divide by 2 a negative number with SHR.
    I want to know God's thoughts ...the rest are details.
    (A. Einstein)
    --------
    ..."a shellcode is a command you do at the linux shell"...

  7. #7
    I'm not sure I understand your repsonse maximus? The "SHR EAX, 1Fh" basically keeps the HO bit. Indicating the sign of the IMUL operation.

    So playing around a little with math and such. the SAR EDX, 5 (for positve numbers) will move the lowest 5 bits. But combined with the EAX value you end up with 137, 438, 953, 472 = 1 after the SAR EDX, 5. Then since it's positive no digit is added. So you would end up with the results after CDQ of EDX:EAX 00000000:00000001

    So could you start switching this back into code by doing something like

    int eax = 2147483648d
    int ecx = 64d

    result = eax * ecx;

    result = result - 137438953471 (Which of course is interesting cuz it happens to be 2^37 - 1) so
    result = result - ( (2^37) - 1)

    ---- ok now to try and figure out negative?
    Last edited by captcpsc; May 4th, 2012 at 11:03. Reason: Lightbulb came on.

  8. #8
    ah, ok.
    a*b/c--->a*(b/c)==> a/d-->a*(b/c) where d=b/c

    now, go on and see what happens...
    I want to know God's thoughts ...the rest are details.
    (A. Einstein)
    --------
    ..."a shellcode is a command you do at the linux shell"...

  9. #9

    Confused.

    Two's compliment is really messing with my head for the negatives. It seems like every (-137438953472) in the value after the imul increases the final value by -1. But how that's going to look along with the plus and no jumps or anything to be used to differentiate the positive and the negative I'm really struggling to reverse that to c or some pseudo algorithm.


    Quote Originally Posted by Maximus View Post
    ah, ok.
    a*b/c--->a*(b/c)==> a/d-->a*(b/c) where d=b/c

    now, go on and see what happens...
    I totally am confused.

    I follow along at first a*b/c then add the parens to ensure correct order of operations. a*(b/c)

    now you bring in d and make it stand for b/c

    so after the ==> shouldn't it be a*d?


    ------ Your original response to me was

    Here is the message that has just been posted:
    ***************
    you didnt follow me:
    a*b/c--->a*(b/c)

    However, in such code you didnt SEE any division, right? now think how could you do a division without using a division... it is not hard. With an arithmetic shift.
    Imagine you want to divide a number by say 15. You can use a div, OR you can multiply by a fraction that is EQUIVALENT to 1/15, it could be 2/30, 3/45... eventually, raising up the lower factor, you will end up in a fraction with a minimal rounding loss for the precision you are looking for.
    Now, go on with your math and try to understand what happens.
    ***************


    And yes I do understand how shifting does division :-) AND would be faster then actual assembly division as far as clock cycles etc go.

    and adding the parens to enforce order of operations in this message made sense to. Also switching up the problem to make it run faster makes sense as well with the precision and fractions.
    Last edited by captcpsc; May 4th, 2012 at 15:05.

  10. #10
    aargh, you'd have to reach the solution by yourself, i didnt edit it in time -.-
    well, with the original answer you have all the pieces, but that would have been your work to do :P

    hint: a/b can be done as a*(1/b).
    Last edited by Maximus; May 4th, 2012 at 15:23.
    I want to know God's thoughts ...the rest are details.
    (A. Einstein)
    --------
    ..."a shellcode is a command you do at the linux shell"...

  11. #11
    Teach, Not Flame Kayaker's Avatar
    Join Date
    Oct 2000
    Posts
    4,084
    Blog Entries
    5
    Just to mess things up further, and for something to play with, some may remember the little app by the asm guru The Svin, called Magic Divider. You enter the divisor you want and it gives you a Magic Number and a set of instructions to use it, for unsigned integers and non-fractional results.

    For example, to divide X by 15, the following works

    Code:
    MagicNumber = 2290649225
    
    mov eax, X
    mov edx, MagicNumber
    mul edx
    SHR edx, 3
    To divide X by 14:

    Code:
    MagicNumber = 2454267026
    
    mov eax, X
    mov edx, MagicNumber
    inc eax
    mul edx
    SHR edx, 3

    This thread started by The Svin introduced the app:

    http://www.asmcommunity.net/board/index.php?topic=4855.0

    There is some further discussion on the algo here which also mentions that the theory behind the Magic Number was mentioned in an AMD optimization manual, and there's also a link to a paper on the underlying maths involved (albeit Greek to me) - "Integer Division Using Reciprocals" by Robert Alverson.

    http://www.masm32.com/board/index.php?topic=5821.0


    The Svin's app with source can be downloaded here or here:

    http://www.wasm.ru/tools/22/magicnumber.zip
    http://apihooks.com.sweb.cz/EliCZ/import/Magic.zip

  12. #12
    Hi Kayaker,
    since you're interested in magic numbers, see http://en.wikipedia.org/wiki/Fast_inverse_square_root

    if i remember well, the magic number is obtained by (ab)using the logarithm relationship in order to obtain a raw approximation under log2, then later refined using newton method.
    I want to know God's thoughts ...the rest are details.
    (A. Einstein)
    --------
    ..."a shellcode is a command you do at the linux shell"...

  13. #13
    Wow? You post that and I was on that page less then a half hour ago. I find all kinda places that are more then willing to do the Magic Number even show the assembly code just like the program Kayacker posted but no one was doing a given the magic number give me the original number? Then it hit me wait if I put the magic number in then it will spit back the original? ( http://www.hackersdelight.org/magic.htm ) Well this works for lots of numbers like 5, 13 etc... But here is my code

    Code:
    Address   Hex dump          Command                                  Comments
    0046214A  |.  B8 555555D5   MOV EAX,D5555555
    0046214F  |.  F7EE          IMUL ESI
    00462151  |.  C1FA 02       SAR EDX,2
    00462154  |.  8BC2          MOV EAX,EDX
    00462156  |.  C1E8 1F       SHR EAX,1F
    00462159  |.  03C2          ADD EAX,EDX
    0046215B  |.  8D0440        LEA EAX,[EAX*2+EAX]
    0046215E  |.  8D34C6        LEA ESI,[EAX*8+ESI]
    00462161  |.  8BD9          MOV EBX,ECX
    00462163  |.  83E1 0F       AND ECX,0000000F
    00462166  |.  83C1 F9       ADD ECX,-7
    00462169  |.  894C24 18     MOV DWORD PTR SS:[LOCAL.9],ECX
    0046216D  |.  894C24 24     MOV DWORD PTR SS:[LOCAL.6],ECX
    Which seems much more complex then

    Code:
    MagicNumber = 3616814565
    mov eax,X
    mov edx, MagicNumber
    inc eax
    mul edx
    SHR edx, 4
    I'm really interested in figuring out how DFFFFFFF is found and what this would have looked like before the compiler optimization?

    And why can't I find a table with these anywhere? I feel like I should take one of these programs and generate a table with it?

  14. #14
    son of Bungo & Belladonna bilbo's Avatar
    Join Date
    Mar 2004
    Location
    Rivendell
    Posts
    310
    well, I don't know where you extracted the code from, but from this http://pastebin.com/zMPg6ckP, it seems to be some custom encryption/decryption algorithm...
    so maybe there is no "traditional" mathematic behind it...
    again, I did not studied the code because I don't know what it is intended for: compiling the decryptor from the above link gives no understable results...

    Thanks to Kayaker and Maximus for your links, they deserve more attention...

    Best regards, bilbo
    Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt.[Seneca, Epistulae Morales 104, 26]

  15. #15
    Thanks to Kayaker and Maximus for your links, they deserve more attention...
    No doubt both are awesome and have helped me a tremendous amount. As well as increased my education on such subjects.

    The code I have is from a game. The "serial protection" can be completely avoided with 1 change to the code. So as far as "hacking" it or "cracking" it whatever you want to say that's far from the issue. The issue was more in being able to reverse something to what it resembled in C++. It's a learning exercise.

    Code:
    AND ECX,0000000F
    Simply becomes ECX = ECX % 10 (hex)(16, decimal)

    But the PRETTY cool thing about compiling and optimization is a good compiler and optimizer is able to take division and various things and switch it around to faster more optimized code. MY thoughts are if I can LEARN better what the optimizer is doing for more efficient code it'll help me be a better more efficient programmer. Maybe code in a way that I take better advantages of optimization... It also of course allows me to look at other code and then reverse it and gain further understanding on how others did things and stuff. SURE reversing can be used for evil for profit to hurt a companies bottom line etc... but in a nicer pure form it's an awesome very fun way to learn stuff.

Similar Threads

  1. DOS/4GW , DOS/16M Reversing Help !
    By visions_of_eden in forum The Newbie Forum
    Replies: 6
    Last Post: December 1st, 2010, 07:49
  2. InTether Protection System Reversing...Reversing Kernel Code
    By tHE mUTABLE in forum Advanced Reversing and Programming
    Replies: 1
    Last Post: December 20th, 2007, 10:48
  3. Reversing VMs
    By Maximus in forum Mini Project Area
    Replies: 17
    Last Post: August 22nd, 2006, 10:38
  4. About Reversing
    By Joda in forum Advanced Reversing and Programming
    Replies: 12
    Last Post: July 11th, 2001, 13:28
  5. Reversing
    By A_m_A in forum Advanced Reversing and Programming
    Replies: 11
    Last Post: May 3rd, 2001, 14:43

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •