Branchless MIN/MAX functions

[mageofmaple]

Does anyone have any idea if it is possible to do a MIN or MAX function without a branch?

Thanks!
Greg

[Gerd Isenberg]

Does anyone have any idea if it is possible to do a MIN or MAX function without a branch?

Thanks!
Greg

You may try something like this (of course inlined):

Code: Select all

int minusMask (int a) {return a >> (sizeof(int)*8-1);}
int ifLessZero(int a) {return a & minusMask(a);}

int max(int a, int b) {return a - ifLessZero(a-b);}
int min(int a, int b) {return a + ifLessZero(b-a);}

But likely with the traditional macro

Code: Select all

#define max(a,b) (((a) > (b)) ? (a) : (b))

recent compiler may generate compare plus cmove which is faster and branchless as well.

Gerd

[Allard Siemelink]

And here is a branchless abs():

Code: Select all

inline static int abs(int x) {
    int y = x>>31;
    return (x^y)-y;
}

[mageofmaple]

Does anyone have any idea if it is possible to do a MIN or MAX function without a branch?

Thanks!
Greg

You may try something like this (of course inlined):

Code: Select all

int minusMask (int a) {return a >> (sizeof(int)*8-1);}
int ifLessZero(int a) {return a & minusMask(a);}

int max(int a, int b) {return a - ifLessZero(a-b);}
int min(int a, int b) {return a + ifLessZero(b-a);}

But likely with the traditional macro

Code: Select all

#define max(a,b) (((a) > (b)) ? (a) : (b))

recent compiler may generate compare plus cmove which is faster and branchless as well.

Gerd

Sweet! That code is very cool. I tried to come up with something myself, but wouldn't have thought of that in a dozen years...

Thanks!
Greg

[Gerd Isenberg]

Sweet! That code is very cool. I tried to come up with something myself, but wouldn't have thought of that in a dozen years...

An old bit-twiddling trick based on signed arithmetical shift (sar).
Not strictly specified in C.
http://aggregate.org/MAGIC/#Integer%20M ... %20Maximum

In x86-assembly the other option to get a minus-mask is to sign extend eax to edx:eax. One may try to sign-extend int to long long in C.

Code: Select all

int minusMask (i32 a) {
    i64 a64 = a;
    return (u32)(a64 >> 32); // which is mov eax, edx in 32-bit mode
} 

Integer Selection

A branchless, lookup-free, alternative to code like if (a<b) x=c; else x=d; is ((((a-b) >> (WORDBITS-1)) & (c^d)) ^ d). This code assumes that the shift is signed, which, of course, C does not promise

[Gerd Isenberg]

And here is a branchless abs():

Code: Select all

inline static int abs(int x) {
    int y = x>>31;
    return (x^y)-y;
}

Carefull - there was some patent with exactly this instruction sequence: Conditional two's complement by conditional one's complement plus one! Better use conditional one's complement of decrement

Code: Select all

inline static int abs(int x) {
    int y = x>>31;
    return (x+y)^y;
} 

[Allard Siemelink]

Carefull - there was some patent with exactly this instruction sequence: Conditional two's complement by conditional one's complement plus one! Better use conditional one's complement of decrement

Really?! It would seem rather silly to claim a patent for this simple software routine.

Anyhow, my source is the Hacker's Delight book (http://www.hackersdelight.org/).

So, I guess the patent holder either
a) sued,
b) wrote, or
c) read
this book?

[Gerd Isenberg]

Carefull - there was some patent with exactly this instruction sequence: Conditional two's complement by conditional one's complement plus one! Better use conditional one's complement of decrement

Really?! It would seem rather silly to claim a patent for this simple software routine.

Anyhow, my source is the Hacker's Delight book (http://www.hackersdelight.org/).

So, I guess the patent holder either
a) sued,
b) wrote, or
c) read
this book?

http://patft.uspto.gov/netacgi/nph-Pars ... RS=6073150

[Michael Sherwin]

Carefull - there was some patent with exactly this instruction sequence: Conditional two's complement by conditional one's complement plus one! Better use conditional one's complement of decrement

Really?! It would seem rather silly to claim a patent for this simple software routine.

Anyhow, my source is the Hacker's Delight book (http://www.hackersdelight.org/).

So, I guess the patent holder either
a) sued,
b) wrote, or
c) read
this book?

Sorry but, please forgive me!

But, how do you know that he did not go back in time and patent the routine before he invented it and then back in the future after having forgot about it, then copied it with out having to invent it? I guessed I've watched too many trek episodes!

Thanks for the link!

[Gerd Isenberg]

Sorry but, please forgive me!

But, how do you know that he did not go back in time and patent the routine before he invented it and then back in the future after having forgot about it, then copied it with out having to invent it? I guessed I've watched too many trek episodes!

Thanks for the link!

Intel's revenge on Sun's patent was the P4
They made shift so slow that the mentioned sar trick became rather worthless.

As mentioned one may use cdq instead sar 31.
And there are two ways to define Two's Complement by One's Complement.

Code: Select all

int abs(int x) 
{
  int m = (int)( (unsigned __int64)((__int64)x) >> 32 );
  return (x + m) ^ m;
}

?abs@@YIHH@Z PROC NEAR					; abs, COMDAT
  00000	8b c1		 mov	 eax, ecx
  00002	99		 cdq
  00003	8d 04 0a	 lea	 eax, [edx+ecx]
  00006	33 c2		 xor	 eax, edx
  00008	c3		 ret	 0
?abs@@YIHH@Z ENDP					; abs