Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Dec 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
3  
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
4  
@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
1  
@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

8 Answers 8

up vote 20 down vote accepted

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.

share|improve this answer
    
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
share|improve this answer
    
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
1  
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
4  
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
1  
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;
}
share|improve this answer
1  
+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
2  
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.

share|improve this answer
    
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
1  
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

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
share|improve this answer
    
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)

share|improve this answer

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
share|improve this answer
    
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

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;
}
share|improve this answer

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?

Not the answer you're looking for? Browse other questions tagged or ask your own question.