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?

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 1

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.

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

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 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 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 6

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

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

Answer 7

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