# Fastest way to clamp an integer to the range 0-255

I'm working on some image processing code that can generate pixel values outside of the normal range of 0 to 255, and I'd like to clamp them back into the valid range. I know that there are saturating SIMD instructions that make this a moot point, but I'm trying to stay within standard C++ code for the moment.

The fastest I've been able to do on my Athlon II is the following:

inline
BYTE Clamp(int n)
{
n &= -(n >= 0);
return n | ((255 - n) >> 31);
}


This compiles down into the following assembly with MSVC 6.0:

setns dl
neg   edx
and   eax, edx
mov   edx, 255
sub   edx, eax
sar   edx, 31
or    dl, al


Is there any improvement possible?

-

## migrated from stackoverflow.comDec 3 '11 at 9:02

This question came from our site for professional and enthusiast programmers.

Does it have to be signed? –  Pubby Dec 3 '11 at 6:26
why AND'ing with 0xFF is not an option? –  littleadv Dec 3 '11 at 6:27
@Pubby, yes the values can be less than 0 or greater than 255. –  Mark Ransom Dec 3 '11 at 6:27
@littleadv, the idea is that values outside the range take on the closest value within the range. I.e. you want -1 to become 0, and ANDing will not accomplish that. –  Mark Ransom Dec 3 '11 at 6:28
@200_success, actually it would be (sizeof(int)*CHAR_BIT)-1. You're correct of course, but I'm unlikely to use this code on any platform where an int isn't 32 bits. –  Mark Ransom Dec 20 '13 at 3:55

## 9 Answers

Try

 int x=n>255?255:n;
... x<0?0:x ...


I'd expect this to produce

 mov eax,n
cmp eax,255
cmovgt eax,255 ; conditional mov instruction
test eax,eax
cmovlt  eax,0


If you are using MSVC SIX, you may not get the conditional move instruction. Try switching to a modern version of visual studio.

-
I do have MSVC 2010 express, so I could try it there. Unfortunately I have two conditions to test for - less than 0, and greater than 255. –  Mark Ransom Dec 3 '11 at 7:26
If this is a pixel value, why are you working with signed values? –  Ira Baxter Dec 3 '11 at 7:27
@MarkRansom: the casting to unsigned takes care of negative values –  6502 Dec 3 '11 at 7:34
@6502, casting -1 to unsigned will generate a large positive value which will be converted to 255. I'd rather it convert to 0. –  Mark Ransom Dec 3 '11 at 7:39
@MarkRansom: you are 100% right. I'll blame for this being on fever in a saturday morning :-) –  6502 Dec 3 '11 at 7:41

Here's my attempt:

unsigned char clamp(int n){
int a = 255;
a -= n;
a >>= 31;
a |= n;
n >>= 31;
n = ~n;
n &= a;
return n;
}


It compiles to 7 instructions - which is the same as your current version. So it may or may not be faster. I haven't timed it though. But I think these are all single-cycle instructions.

mov eax, 255
sub eax, ecx
sar eax, 31
or  al , cl
sar ecx, 31
not cl
and al , cl

-
I tried this out, and it slowed my overall benchmark time from 0.24 seconds to 0.31. Nice attempt though. –  Mark Ransom Dec 3 '11 at 7:08
Awww... Oh well... I tried, not sure if I can do any better... –  Mysticial Dec 3 '11 at 7:12
I just looked at the assembly and for some reason it would not inline your version - that probably accounts for the difference. –  Mark Ransom Dec 3 '11 at 7:17
I tried adding the inline keyword to the function, which I thought wouldn't make any difference - the compiler is supposed to know when it's worthwhile to inline without needing any hints. It brought the runtime from 0.31 to 0.23, which is a hair faster than mine. Congratulations! –  Mark Ransom Dec 3 '11 at 7:21
Replacing the function with return n changed the time from 0.24 seconds to 0.21, so your improvement is more significant than it appears at first glance. This might motivate me to do a better benchmark, but not tonight. –  Mark Ransom Dec 3 '11 at 7:49

I'd be curious how a simple branched solution would perform?

inline char Clamp(int n)
{
if(n < 0)
return 0;
else if(n > 255)
return 255;
return n;
}

-
+1. Some benchmarks are in order. This could very well take advantage of the superscalar speculative branch execution of modern CPUs, and be quite fast indeed. –  Macke Dec 3 '11 at 15:21
This is nearly the same as Jonathan Leffler's Clamp_2, which performed much better than I expected. I wonder if fiddling with the order makes a difference? I'll have to let you know later. –  Mark Ransom Dec 3 '11 at 16:22
I'm curious to see how return std::min(std::max(0, n), 255); will fair against the competition. –  greatwolf Dec 3 '11 at 22:24

Using GCC/LLVM on MacOS X, and 64-bit compilation, and generating assembler with:

gcc -S -Os clamp.c


where clamp.c contains:

typedef unsigned char BYTE;

BYTE Clamp_1(int n)
{
n &= -(n >= 0);
return n | ((255 - n) >> 31);
}

BYTE Clamp_2(int n)
{
if (n > 255)
n = 255;
else if (n < 0)
n = 0;
return n;
}


The assembler for the two functions (with prologue and epilogue) is:

    .section        __TEXT,__text,regular,pure_instructions
.globl  _Clamp_1
_Clamp_1:
Leh_func_begin1:
pushq   %rbp
Ltmp0:
movq    %rsp, %rbp
Ltmp1:
movl    %edi, %eax
shrl    $31, %eax xorl$1, %eax
negl    %eax
andl    %edi, %eax
movl    $255, %ecx subl %eax, %ecx sarl$31, %ecx
orl     %eax, %ecx
movzbl  %cl, %eax
popq    %rbp
ret
Leh_func_end1:

.globl  _Clamp_2
_Clamp_2:
Leh_func_begin2:
pushq   %rbp
Ltmp2:
movq    %rsp, %rbp
Ltmp3:
cmpl    $256, %edi jl LBB2_2 movl$255, %edi
jmp     LBB2_4
LBB2_2:
testl   %edi, %edi
jns     LBB2_4
xorl    %edi, %edi
LBB2_4:
movzbl  %dil, %eax
popq    %rbp
ret
Leh_func_end2:


The pushq, popq and ret are the function call overhead. Your code (Clamp_1()) assembles to 11 instructions; mine to 9 (but there are two jumps in mine, which might wreak havoc on pipelined execution). Neither approaches the 7 instructions in your optimized version.

Interestingly, though, when I use GCC 4.6.1 on the same code, the assembler output is:

    .text
.globl _Clamp_1
_Clamp_1:
LFB0:
movl    %edi, %eax
movl    $255, %edx notl %eax sarl$31, %eax
andl    %edi, %eax
subl    %eax, %edx
sarl    $31, %edx orl %edx, %eax ret LFE0: .globl _Clamp_2 _Clamp_2: LFB1: xorl %edx, %edx testl %edi, %edi movl$255, %eax
cmovns  %edi, %edx
cmpl    $255, %edx cmovle %edx, %eax ret LFE1:  Now I see 8 instructions in Clamp_1 and 6 in Clamp_2 apart from the ret. Further experimentation shows that there is a difference in the output between gcc -Os -S clamp.c and gcc -S -Os clamp.c; the former generates the optimized (smaller) outputs; the latter generates the more verbose output. - Strangely it never occurred to me to test my code against the straightforward implementation you presented here. I tried it and the time went from 0.24 seconds to 0.29, so no improvement there. Obviously though the compiler and surrounding code can make a huge difference. Thanks for the attempt. – Mark Ransom Dec 3 '11 at 7:36 I just tried the same test but including the inline keyword and it brought the time down to 0.23 seconds. I must remember to include it in every test from now on. – Mark Ransom Dec 3 '11 at 7:52 I had been trying to avoid branches on the theory that they took an an inordinate amount of time, but obviously branch prediction is more advanced than I had assumed. Thanks for rattling my assumptions! – Mark Ransom Dec 3 '11 at 7:56 You might get even better speed with a single test (if(n & 0xFFFFFF00 != 0)) to look for out of range and let the in-range values only take the and, test and jump... – jswolf19 Dec 3 '11 at 9:38 The result may depend a bit upon whether the pixel data is predictably more often in-range than out of range. This might be quicker in the former case: int clamp(int n) { if ((unsigned) n <= 255) { return n; } return (n < 0) ? 0 : 255; }  - Using your < 0 clamp and modifying the > 255 one, how does this stack up? inline BYTE Clamp(int n) { n &= -(n >= 0); return n | ~-!(n & -256); }  The disassembly of the second line (below) on my machine has one extra instruction, but no (expensive) shifts. mov eax, ecx and eax, -256 neg eax sbb eax, eax or eax, ecx  - About the same as mine, 0.24 seconds overall including a lot of other stuff going on. I don't think shifts have been expensive since the 386 days, the barrel shifter makes any shift count possible within a single clock cycle. – Mark Ransom Dec 3 '11 at 7:31 I guess you can tell how long I've been doing x86 assembly. :) – DocMax Dec 3 '11 at 7:35 unsigned char clamp(int n) { return (-(n >= 0) & n) | -(n >= 255); }  You can optimize this if you can optimize -(a >= b) - what about this? x &= 255  It is very efficient and has no effect on values in the normal range. I would like to know what proportion of your results need clamping. If a simple and won't do the trick, try this: x &= (~x) >> 8  - This was already suggested in the comments. Unfortunately it doesn't do the right thing with values outside the normal range - I want values less than 0 to become 0 and values greater than 255 to become 255. You're right about it being efficient though. – Mark Ransom Aug 9 '12 at 17:09 Conclusion 2011-12-05: I tried all of the suggestions again with VS 2010 Express. The generated code didn't change much, but the register assignments did which affected the overall results. A slight modification of the straightforward implementation suggested by Ira Baxter came up the winner. inline BYTE Clamp(int n) { n = n>255 ? 255 : n; return n<0 ? 0 : n; } cmp ecx, 255 jle SHORT$LN8
mov  ecx, 255
\$LN8:
test ecx, ecx
sets bl
dec  bl
and  bl, cl


I learned a valuable lesson with this. I started with an assumption that bit-twiddling would beat anything that included a branch; I hadn't really tried any code that included an if statement or ternary operator. That was a mistake, as I hadn't counted on the power of the branch prediction built into a modern CPU. A ternary solution turned out to be the fastest, especially when the compiler substituted its own bit-twiddling code for one of the cases. The overall timing for this function within my benchmark algorithm went from 0.24 seconds to 0.19. This is very close to the 0.18 seconds that resulted when I removed the clamp entirely.

-

## protected by Jamal♦Dec 21 '13 at 17:20

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?