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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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;
}

Answer 5

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.

Answer 6

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.

Answer 7

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;
}

Answer 8

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

Answer 9

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

You can optimize this if you can optimize -(a >= b)

Answer 10

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.

Answer 11

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