Reversing SHR EAX,1F

[captcpsc]

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.

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.

[naides]

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

[captcpsc]

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,

	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?

[Maximus]

the SAR instruction preserves your sign.
make +a*-b/+c, where +c is a power of 2 (>32)

[captcpsc]

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
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.

[Maximus]

Try to divide by 2 a negative number with SHR.

[captcpsc]

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?

[Maximus]

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

now, go on and see what happens...

[captcpsc]

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.

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.

[Maximus]

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

[Kayaker]

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

MagicNumber = 2290649225

mov eax, X
mov edx, MagicNumber
mul edx
SHR edx, 3

To divide X by 14:

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

[Maximus]

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.

[captcpsc]

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

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

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?

[bilbo]

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

[captcpsc]

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.

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.