integer clamp
category: code [glöplog]
What's a good way to clamp an integer in c without using a conditional?
like
if(number>0xff) number = 0xff;
if(number<0) number = 0;
but without the ifs. any ideas?
like
if(number>0xff) number = 0xff;
if(number<0) number = 0;
but without the ifs. any ideas?
Why no ifs? A good compiler should be able to create branchless code for you if the target processor supports it.
out of practice I suppose, just wondering of there's another way to do it.
the only thing I can think of is shifting the upper bits to one bit and using that to inverse a mask for the correct size and xor that with the integer. sounds like too much work however.
Code:
#define CLAMP(number, low, high) min(high, max(low, number)):P
at least that's what I use, as it's so much shorter than all those if statements.
@mic checking my compiler... huh, you're right it doesn't introduce conditional branches. That's interesting- I always assumed it did. thanks
or ask winden for its nasty integer clamp trick (no tests, just a few logic operators)
you could use a ternary expression:
number = number < 0 ? 0 : (number > 0xff ? 0xff : number);
number = number < 0 ? 0 : (number > 0xff ? 0xff : number);
kusma that's conditional branching.
You could do the min/max thing and use the following:
http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
You could do the min/max thing and use the following:
http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
las: Sure it is, but it's without the "ifs". most min/max implementations use conditional branches, as min/mas isn't a c-primitive. It's possible to do clamping by other means (like described in bit twiddling hacks), but it usually ends up becoming both slower and less obvious than conditionals.
You asked a good way so people obviously point to the ternary operator. But I'm going to tell the bad way instead:
number |= -(number>>8);
Underflow? Too much overflow? What about the highbits? Who the fuck cares? You're going to use this in additive pre-mmx overlay effect, right?
number |= -(number>>8);
Underflow? Too much overflow? What about the highbits? Who the fuck cares? You're going to use this in additive pre-mmx overlay effect, right?
Quote:
You're going to use this in additive pre-mmx overlay effect, right?
thanks for your input and actually yeah
... I avoided it all together... sorry fellas. nice thread though
@las: thank you for the link, it's a really valuable doc! :)
Quote:
most min/max implementations use conditional branches, as min/mas isn't a c-primitive
I know, but I provided a link for branch free min/max implementations :)
kusma: okay, yes I also guess it will become slower. It's often better to write the code as simple as possible and let the damn compiler do it's job.
Code:
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <stdint.h>
// Clamps a given integer x into the interval [a, b] with a <= b
// Assuming INT_MIN <= x - a <= INT_MAX & INT_MIN <= r - b <= INT_MAX
int clamp(int x, int a, int b) {
// r = max(x, a)
int r = x - ((x - a) & ((x - a) >> (sizeof(int) * CHAR_BIT - 1)));
// min(r, b)
return b + ((r - b) & ((r - b) >> (sizeof(int) * CHAR_BIT - 1)));
}
static inline int max(int a, int b) {
return a > b ? a : b;
}
static inline int min(int a, int b) {
return a < b ? a : b;
}
int clampBranch(int x, int a, int b) {
return min(max(x, a), b);
}
static int64_t utime() {
static struct timeval value;
gettimeofday(&value, NULL);
return (int64_t)value.tv_sec * 1000000 + (int64_t)value.tv_usec;
}
int main(int argc, char** argv) {
// -Wall...
argc += 0;
argv += 0;
int64_t startTime, endTime;
int rangeStart = -2000000;
int rangeEnd = +2000000;
int clampStart = -10000;
int clampEnd = +10000;
int tmp = 0;
// Just some not so serious testing...
startTime = utime();
for (int i = rangeStart; i < rangeEnd; ++i) {
tmp = clamp(tmp + i, clampStart, clampEnd);
}
endTime = utime();
printf("Time without branching: %ld %d\n", endTime - startTime, tmp);
startTime = utime();
for (int i = rangeStart; i < rangeEnd; ++i) {
tmp = clampBranch(tmp + i, clampStart, clampEnd);
}
endTime = utime();
printf("Time with branching: %ld %d\n", endTime - startTime, tmp);
return 0;
}
=>
Quote:
Time without branching: 26970 10000
Time with branching: 14413 10000
=> Just let the compiler do it's job.
Las: Nice link. I remember figuring out some of those tricks my self 15 years ago.
+ ignore the off by one (should be i <= rangeEnd) and the other little things :)
(+ resetting tmp for the 2nd testrun does of course not change the result)
No problem. :)
I used some bit twiddling lately - trust me bit twiddling and using swizzling (in GLSL) can get really confusing :)
I used some bit twiddling lately - trust me bit twiddling and using swizzling (in GLSL) can get really confusing :)
Slightly off-topic, my favorite ARM assembler trick:
can be written as
Code:
if(number<0) number = 0;can be written as
Code:
bic r0,r0,r0, ASR#31
Inopia, that's a good one, but:
Even a old GCC knows this 'trick'. :-)
Code:
1 int blubb (int i)
2 {
3 if (i<0) i=0;
4 return i;
5 }
6
Code:
nils@doofnase:~$ arm-none-linux-gnueabi-gcc -O3 -S x.c
nils@doofnase:~$ cat x.s
Code:
blubb:
.fnstart
.LFB2:
@ args = 0, pretend = 0, frame = 0
@ frame_needed = 0, uses_anonymous_args = 0
@ link register save eliminated.
bic r0, r0, r0, asr #31
bx lr
Even a old GCC knows this 'trick'. :-)
mmx? :p
i thought this was comon knowledge now a days:
1) write code clear and understanable. if you do so, both the compiler and yourself will have easier interpreting the code.
2) if 1) fails in case of speed - change the design or algorithm
3) if 2) fails in case of speed - measure and sub-optimize
4) if 3) fails in case of speed - wait untill cpus get bigger and try again :-)
1) write code clear and understanable. if you do so, both the compiler and yourself will have easier interpreting the code.
2) if 1) fails in case of speed - change the design or algorithm
3) if 2) fails in case of speed - measure and sub-optimize
4) if 3) fails in case of speed - wait untill cpus get bigger and try again :-)