Exetools - Multiply by negative one

Exetools (https://forum.exetools.com/index.php)

- General Discussion (https://forum.exetools.com/forumdisplay.php?f=2)

- - Multiply by negative one (https://forum.exetools.com/showthread.php?t=18090)

chants

01-19-2017 07:51

Arithmetic coerce to negative one, and the like

See below, this was a simple late night mistake.

Just an interesting asm question, since we know that:

mul [val], -1

is inefficient in terms of clock cycles, is there a pure Boolean algebra (and/or/xor/not/neg) way of doing this without doing expensive multiplication?

mcp	01-19-2017 08:23

You can move the value to a register and use NEG on it (assuming x86, 32 bit):

Code:

mov eax, [val]

neg eax

mov [val], eax

Alternatively, subtract from zero:

Code:

xor exc, ecx

mov eax, [val]

sub ecx, eax

mov [val], ecx

chants

01-19-2017 08:47

It is a bit early in the morning :-D

What I really meant to ask, was can we take an expression that is 0 or non-zero and convert it to 0 or -1. Either an all-0 or all-1 bitmask.

0->0
non-zero->-1

With pure arithmetic and no conditional statements. With conditional statements, there are many ways and all are easy. But without, its not as simple.

I noticed that (A OR -A) = 0 for 0, but turns the high bit on except for the sign bit power of 2 value e.g. 0x80000000. Perhaps using CDQ.

Code:

mov eax, [val]

mov edx, eax

neg edx

or eax, edx

cdq

mov eax, edx

Could that really be the simplest algorithm to do it?

The only other interesting property like this I could think of is <0 -> -1, 0 -> 0, >1 ->1 which also would be about as tricky without conditionals and purely arithmetically.

Actually you do something along the lines of multiply the output of previous code by the carry flag after subtracting from 0(sub, adc, mul) and I don't think you can avoid the mul.

Any thoughts

atom0s

01-19-2017 09:05

Using modern compiler optimizations it suggests that doing something like this:

Code:

    int32_t val1 = 1234;

    int32_t val2 = -val1;

Translates to:

Code:

mov     [ebp+var_4], 4D2h

mov     eax, [ebp+var_4]

neg     eax

mov     [ebp+var_4], eax

which is what mcp suggested in his first suggestion. If you write the code out as:

Code:

int32_t val1 = 1234;

val1 *= -1;

It also optimizes to the first suggestion.

mcp	01-19-2017 09:46

IIUC, you want to express something like this in assembly:

Code:

int result = n ? -1 : 0;

In that case, using neg+sbb does the trick:

Code:

mov eax, [val]

neg eax

sbb eax, eax

This works since neg sets the carry flag if its operand is non-zero, and clears it otherwise. The sbb instruction then subtracts the carry flag from zero and thus yields -1 for non-zero inputs, and zero otherwise.

Example:
eax contains a non-zero value, say x. neg eax turns this into -x and sets the CF. sbb eax, eax computes eax = eax - eax - cf <-> eax = 0 - CF.
Same drill when eax is zero initially.

chants

01-19-2017 16:55

Yes, that was the pearl of wisdom needed here. I had long forgotten this old SBB trick. From a C perspective its the casting to bool operation.

It would be nice if all the assembler bit tricks were compiled somewhere as similar to:
https://graphics.stanford.edu/~seander/bithacks.html

BlackWhite

02-07-2017 21:09

I think you may also take advantage of the instruction "setnz":

Code:

mov eax, [val]

or eax, eax

setnz al

neg al

movsx eax, al

mcp	02-08-2017 17:29

@BlackWhite Why would you? It's more code and it's less efficient. Clearly, there is an infinite amount of additional ways to express this, but there is no advantage in doing so!?

BlackWhite

02-08-2017 23:23

Yes, setnz is not as efficient as sbb;
yet, it provides a variant way for the job.
Since sbb is forgotten by someone,
setnz & movsx may also be the case.

All times are GMT +8. The time now is 15:28.