Branchless unsigned minimum of 2 values

[hopcode]

Hallo people,
i was thinking about it using the sum and the difference of
2 values, and the capability to isolate the second value.
i dont know, but i didnt see this application in my readings,
also i set it now in the public domain.

my snippet,

mov eax,v1
mov edx,v2
;--- v1=10 v2=15 v1=4 v2=3
mov ecx,eax ;--- ECX 10 ECX 4
sub eax,edx ;--- EAX -5 EAX 1
sbb edx,edx ;--- EDX -1 EDX 0
and edx,eax ;--- EDX -5 EDX 0
sub ecx,eax ;--- ECX 10-(-5)=15 ECX 4-1=3
add ecx,edx ;--- ECX 15+(-5)=10 ECX 3+0=3
mov eax,ecx ;--- EAX 10 EAX 3
nop

do you see the theory behind it ?
improve ?

Cheers,
:-)



.:mrk[hopcode]
.:x64lab:.
group http://groups.google.com/group/x64lab
site http://sites.google.com/site/x64lab

[Terje Mathisen]

hopcode wrote:
> Hallo people,
> i was thinking about it using the sum and the difference of
> 2 values, and the capability to isolate the second value.
> i dont know, but i didnt see this application in my readings,
> also i set it now in the public domain.
>
> my snippet,
>
> mov eax,v1
> mov edx,v2
> ;--- v1=10 v2=15 v1=4 v2=3
> mov ecx,eax ;--- ECX 10 ECX 4
> sub eax,edx ;--- EAX -5 EAX 1
> sbb edx,edx ;--- EDX -1 EDX 0
> and edx,eax ;--- EDX -5 EDX 0
> sub ecx,eax ;--- ECX 10-(-5)=15 ECX 4-1=3
> add ecx,edx ;--- ECX 15+(-5)=10 ECX 3+0=3
> mov eax,ecx ;--- EAX 10 EAX 3
> nop
>
> do you see the theory behind it ?
> improve ?

The theory is of course obvious, but as long as you're writing for a
32-bit platform I would simplify this a _lot_:

cmp eax,edx
cmovb eax,edx

I.e. "eax = edx IF (eax < edx)"

This is 2-3 cycles on all those cpus which implements CMOVcc.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[Bobby Bingham]

On Sun, 27 Jan 2013 11:08:03 +0100, hopcode wrote:
> Hallo people,

> i dont know, but i didnt see this application in my readings,
> also i set it now in the public domain.
>

This looks similar to the "quick and dirty" version seen at
http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax


Bobby

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[hopcode]

> The theory is of course obvious, but as long as you're writing for a 32-bit platform I would simplify this a _lot_:
> cmp eax,edx
> cmovb eax,edx
> I.e. "eax = edx IF (eax < edx)"
> This is 2-3 cycles on all those cpus which implements CMOVcc.
> Terje

------------------

> This looks similar to the "quick and dirty" version seen at
> http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
> Bobby

of course yes on both. i forgot completely about that paper; then
i was there reinventing the wheel using a bit of algebra :-)

Cheers,


--

[Terje Mathisen]

hopcode wrote:
>> The theory is of course obvious, but as long as you're writing for a
>> 32-bit platform I would simplify this a _lot_:
>> cmp eax,edx
>> cmovb eax,edx
>> I.e. "eax = edx IF (eax < edx)"
>> This is 2-3 cycles on all those cpus which implements CMOVcc.

Oops!

You asked for minimum, not max, so that CMOV should be CMOVA instead of
CMOVB!

> ------------------
>> This looks similar to the "quick and dirty" version seen at
>> http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
>> Bobby
>
> of course yes on both. i forgot completely about that paper; then
> i was there reinventing the wheel using a bit of algebra :-)

The main step of algorithms that don't use CMOV is of course the CMP/SBB
combo:

This leaves a full-register flag value, at which point you can either
use it twice, as-is and after inversion, on both inputs, or you can use
it on the difference between the two values, and add/sub that:

cmp edx,eax
sbb ebx,ebx ; -1 IFF EDX < EAX
sub edx,eax ; Negative difference...
and edx,ebx
add eax,edx

The alternative:

cmp edx,eax
sbb ebx,ebx ; -1 IFF EDX < EAX

and edx,ebx
xor ebx,-1
and eax,ebx
or eax,edx

This is one more instruction and one more cycle of minimum latency!

If I calculate the flag twice...

cmp edx,eax
sbb ebx,ebx ; -1 IFF EDX < EAX

cmp eax,edx
sbb ecx,ecx

and edx,ebx
and eax,ecx

or eax,edx

then I end up with yet another instruction (7), but the absolute minimum
latency is actually just 4 cycles if both of the CMP/SBB combinations
can execute in parallel!

[hopcode]

Il 27.01.2013 21:25, Terje Mathisen ha scritto:
>
> This leaves a full-register flag value, at which point you can either
> use it twice, as-is and after inversion, on both inputs, or you can use
> it on the difference between the two values, and add/sub that:
>
> cmp edx,eax
> sbb ebx,ebx ; -1 IFF EDX < EAX
> sub edx,eax ; Negative difference...
> and edx,ebx
> add eax,edx
>

or the following

sub edx,eax ; Negative difference...
sbb ecx,ecx ; -1 IFF EDX < EAX
and edx,ecx
add eax,edx

cutting the CMP on top should run 2,3 cycles, if am not wrong.
in both cases they destroy EDX and CF results inverted, though always
correct. i mean: CF doesnt follow the visuality of the layout
in both cases,

i.e: CF=1 when V1(eax) > V2(edx) and CF=0 when V1 < V2.
it should be the contrary,imo, because implementing it in a macro
simplifies readability by making the macro less opaque.
pseudocode

7 2 CF=1 (but 7-2 > 0)
@min eax,edx

4 5 CF=0 (but 4-5 < 0)
@min eax,edx

how to invert it without CMC ?

[hopcode]

ok, i admit it with the CF is a matter of style ;-)
but found the solution, preserving EDX and returning the CF as i would
like. example macro

macro @min v1,v2{
mov eax,v1
mov edx,v2

sub eax,edx
sbb ecx,ecx
and eax,ecx
add eax,edx
}

the macro should look like in the layout of a CMP/SUB instruction,
so that

@min 7,2 EAX=2, CF=0
@min 4,5 EAX=4, CF=1

[Rosario1903]

On Sun, 27 Jan 2013 11:08:03 +0100, hopcode

<hop...@nospicedham.invalid.de> wrote:

>Hallo people,
>i was thinking about it using the sum and the difference of
>2 values, and the capability to isolate the second value.
>i dont know, but i didnt see this application in my readings,
>also i set it now in the public domain.
>
>my snippet,
>
> mov eax,v1
> mov edx,v2
> ;--- v1=10 v2=15 v1=4 v2=3
> mov ecx,eax ;--- ECX 10 ECX 4
> sub eax,edx ;--- EAX -5 EAX 1
> sbb edx,edx ;--- EDX -1 EDX 0
> and edx,eax ;--- EDX -5 EDX 0
> sub ecx,eax ;--- ECX 10-(-5)=15 ECX 4-1=3
> add ecx,edx ;--- ECX 15+(-5)=10 ECX 3+0=3
> mov eax,ecx ;--- EAX 10 EAX 3
> nop
>
>do you see the theory behind it ?
>improve ?
>
>Cheers,
>:-)

; a=eax, r=edx, c=ecx, "--="="sbb"
a=v1|r =v2
a-=r|c--=c ; a=v1-v2 c=(v1-v2)>=0?0:-1
a&=c|a +=r ; v1>=v2 => v1-v2>=0 => a=v2=min(v1, v2)
; v1< v2 => v1-v2< 0 => a=v1=min(v1, v2)

[Stanley Daniel de Liver]

assuming that in the following ";" is a comment delimiter and "|" is a
line feed

> ; a=eax, r=edx, c=ecx, "--="="sbb"
> a=v1|r =v2

mov eax,v1
mov edx,v2

> a-=r|c--=c ; a=v1-v2 c=(v1-v2)>=0?0:-1

sub eax,edx
sbb ecx,ecx

> a&=c|a +=r ; v1>=v2 => v1-v2>=0 => a=v2=min(v1, v2)

and eax,ecx
add eax,edx

> ; v1< v2 => v1-v2< 0 => a=v1=min(v1, v2)
>

It'd be simpler for me as, an uneducated type, to see raw Intel asm. I'm
not very confident in my interpretation of your syntax.

--
It's a money /life balance.

[Rosario1903]

yes correct traslation for me
but someone find that solution first

[Terje Mathisen]

hopcode wrote:
> Il 27.01.2013 21:25, Terje Mathisen ha scritto:
>>
>> This leaves a full-register flag value, at which point you can either
>> use it twice, as-is and after inversion, on both inputs, or you can use
>> it on the difference between the two values, and add/sub that:
>>
>> cmp edx,eax
>> sbb ebx,ebx ; -1 IFF EDX < EAX
>> sub edx,eax ; Negative difference...
>> and edx,ebx
>> add eax,edx
>>
>
> or the following
>
> sub edx,eax ; Negative difference...

Ouch! I should have seen that one!

> sbb ecx,ecx ; -1 IFF EDX < EAX
> and edx,ecx
> add eax,edx
>
> cutting the CMP on top should run 2,3 cycles, if am not wrong.

Here you are wrong: The code above is a classic 4-cycle minimum latency
since each and every instruction depends directly on the result of the
previous one:

SUB -> carry -> SBB
SBB -> ecx -> AND
AND -> edx -> ADD

> in both cases they destroy EDX and CF results inverted, though always
> correct. i mean: CF doesnt follow the visuality of the layout
> in both cases,

That doesn't matter IMHO.

[Rosario1903]

On Mon, 28 Jan 2013 14:00:49 -0000, "Stanley Daniel de Liver"
<notag...@nospicedham.invalid.org.invalid> wrote:

the easy code, the code one human has for me to use-understand
would sound as

a=v1|a<v2#.1|a=v2
.1:
_______________________________________
would be somethign as: "jb .1" would mean if "<" goto to .1
mov eax, v1|cmp eax, v2|jb .1| mov eax, v2
.1:
__________________________

debug the just below is easier
i always had use it without any problems
and for this never use a macro...

[Rosario1903]

On Mon, 28 Jan 2013 14:00:49 -0000, "Stanley Daniel de Liver"
<notag...@nospicedham.invalid.org.invalid> wrote:

[Rosario1903]

On Tue, 29 Jan 2013 10:30:20 +0100, Rosario1903
<Ros...@nospicedham.invalid.invalid> wrote:

>would be somethign as: "jb .1" would mean if "<" goto to .1
> mov eax, v1|cmp eax, v2|jb .1| mov eax, v2
>.1:
>__________________________
>
>debug the just below is easier
>i always had use it without any problems
>and for this never use a macro...

i make the wrong word "below" --> "above"
Buon Giorno