# 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?

• 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

Try

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


I'd expect this to produce something like:

 mov     ebx, 255
mov     eax, n
cmp     eax, ebx
cmovg   eax, ebx ; conditional mov instruction
test    eax, eax
mov     ebx, 0
cmovl   eax, ebx


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
• @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
• @6502: Mark wanted negative numbers to produce zero. – Ira Baxter Dec 3 '11 at 7:45
• I did, but StackOverflow migrated the question, and lost the edit times, so you couldn't see it. I see your revised answer with the short (predicted) branch; the CMOV I think is still the fastest way to do this because there is no branch ever. If MS won't generate it directly, you can always make a bit of assembler code. Thanks for noticing the changes, and for the brownie point. – Ira Baxter Dec 6 '11 at 5:32
• I'm glad that we're at the point where the most straightforward code is also the fastest in this situation. – David Stone Oct 27 '13 at 21:18

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

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.

• Did you try using unsigned compare to combine the check for less-than-zero with the check for >255? (negative numbers are large unsigned numbers) e.g. cmp ecx, 255 / jbe .good, so in the case where clamping it not needed, it's a single taken fused-compare-and-branch , then back to the rest of your code. Or, make the no-clamping case the not-taken branch, and put the clamping off with other cold code, followed by a jump back. There are some good answers on stackoverflow.com/questions/34071144/…, (where there's a variable upper-bound). – Peter Cordes Dec 3 '15 at 18:46
• You can do better than that code. See my answer on the SO question I linked. cmp ecx, 255 / jbe .no_clamp / mov cl, 255 / mov bl, 0 / cmovg bl, cl If you can spare a register to hold a zero constant, or want to cmov from a memory constant for the rare case when clamping is needed, you can pull the mov bl, 0 out. Emulating cmov with setcc/dec/and isn't worth it, even though cmov is a 2-uop instruction on Intel. – Peter Cordes Dec 3 '15 at 20:05
• @PeterCordes this question is about C/C++ code, not assembly. The assembly is only there to help understand why one source construct might be faster than another, and it's all compiler generated. – Mark Ransom Dec 3 '15 at 20:39

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
• It's quite good: godbolt.org/z/Ni_obb Similar to Mark Ransom's: godbolt.org/z/Z4rYdP The one in this answer is jumpy so I doubt it would win: godbolt.org/z/meEuH1 – Steve Oct 1 '19 at 21:49

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

C++17 introduces std::clamp(), so your function can be implemented as follows:

#include <algorithm>

inline BYTE Clamp(int n) {
return std::clamp(n, 0, 255);
}


Which seems well optimized by GCC (version 10.2), using only comparison and conditional move instructions as seen in many of the older answers:

clamp(int):
cmp     edi, 255
mov     eax, 255
mov     edx, 0
cmovle  eax, edi
test    eax, eax
cmovs   eax, edx
ret


However, at the time of writing, the assembler output of Clang (version 10.0.0) and ICC (version 19.0.1) are suboptimal. MSVC (version 19.24) is almost optimal but adds one branch instruction.

• Silly compilers; we can take advantage of the unsigned compare trick to use the same cmp result twice for both cmovae and cmovge, as shown in this answer: x86 assembly - optimization of clamping rax to [ 0 .. limit ). GCC's version is especially bad, putting test on the critical path by testing the first cmov's output instead of the original EDI input. And yeah, clang 10 and 11 are insane, using memory and selecting one of 3 addresses to load from. Clang 9 does close to what GCC does. – Peter Cordes Dec 22 '20 at 23:15
• No, clamp<unsigned> treats negative n as high unsigned numbers, clamping them to 255 not 0. That's not what the OP wants for this question; it's signed clamping to 0..255. That does need 2 CMOV instructions for the 2 possible clamp values. – Peter Cordes Dec 23 '20 at 1:53

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)

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

This may be a worthwhile function, despite the existence of std::clamp, since it's likely that the 0-255 range is open to optimisations that don't apply to the general function (e.g. more SIMD-friendly code). I'd give it a different, more specific name, though.

The hardcoded 31-bit shift is only appropriate if int happens to be 32 bits wide. Instead of embedding that assumption, it would be better to make it explicit in the function signature (and that also allows us to overload the function for other integer types):

#include <cstdint>
inline BYTE clamp_pixel(std::int32_t n);


As an added bonus, it will no longer compile on platforms that don't have a 32-bit integer type, alerting us to the need to modify this function.

Although it's declared elsewhere, the typename BYTE is a poor choice, especially for an arithmetic type, given that std::byte is not an arithmetic type. You probably want std::uint_fast8_t there, I think.

• The definition of BYTE came from Microsoft, and it's either a macro or a typedef for unsigned char. Your change to the parameter type is a good idea though. – Mark Ransom Feb 3 at 17:12
• Ah, I didn't realise it was imposed by your platform (not being a Microsoft user myself). Sorry to accuse you of that! – Toby Speight Feb 3 at 17:16
• It wasn't imposed so much as it became a habit. Microsoft created their types before the equivalents were available in the standard. At the time I asked the question I wasn't as familiar with the std types as I am today. – Mark Ransom Feb 3 at 17:50