将整数钳位到0-255范围的最快方法

我正在处理一些图像处理代码，这些代码可以生成超出0到255正常范围的像素值，并且我想将它们限制在有效范围内。我知道有很多饱和的SIMD指令可以解决这个问题，但是我现在想将其保持在标准C ++代码内。 II是以下内容：

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

此版本使用MSVC 6.0编译为以下程序集：

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

有什么改善的可能吗？

是否必须签名？

为什么不与0xFF进行AND'ing？

@Pubby，是的，值可以小于0或大于255。

@littleadv，其想法是范围外的值采用范围内最接近的值。即您希望-1变为0，而ANDing则无法实现。

@ 200_success，实际上是（sizeof（int）* CHAR_BIT）-1。您当然是正确的，但我不太可能在int不是32位的任何平台上使用此代码。

#1 楼

请尝试

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

我希望它产生类似以下内容的内容：尝试切换到现代版本的Visual Studio。

\ $ \ begingroup \ $
我确实有MSVC 2010 Express，所以可以在那里尝试。不幸的是，我有两个条件要测试-小于0和大于255。
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：26

\ $ \ begingroup \ $
@ 6502，将-1强制转换为无符号将生成一个较大的正值，该值将转换为255。我宁愿将其转换为0。
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：39

\ $ \ begingroup \ $
@ 6502：马克想让负数产生零。
\ $ \ endgroup \ $
–伊拉克·巴克斯特
2011年12月3日，7：45

\ $ \ begingroup \ $
我做到了，但是StackOverflow迁移了问题，并浪费了编辑时间，因此您看不到它。我用简短的（预测的）分支看到了您的修订答案；我认为CMOV仍然是最快的方法，因为从来没有分支。如果MS无法直接生成它，则可以随时编写一些汇编代码。感谢您注意到更改和布朗尼点。
\ $ \ endgroup \ $
–伊拉克·巴克斯特
2011年12月6日下午5:32

\ $ \ begingroup \ $
我很高兴在这种情况下，最简单的代码也是最快的。
\ $ \ endgroup \ $
–大卫·斯通（David Stone）
13-10-27在21:18

#2 楼

这是我的尝试：

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

它可以编译为7条指令-与您当前的版本相同。因此，它可能会或可能不会更快。我还没有计时。但我认为这些都是单周期指令。

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

\ $ \ begingroup \ $
我尝试了一下，这将我的总体基准测试时间从0.24秒减至0.31。不错的尝试。
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：08

\ $ \ begingroup \ $
Awww ...哦，我尝试过，不确定是否可以做得更好...
\ $ \ endgroup \ $
–神秘
2011年12月3日，7：12

\ $ \ begingroup \ $
我只是查看了程序集，由于某种原因，它无法内联您的版本-可能是造成差异的原因。
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：17

\ $ \ begingroup \ $
我尝试将inline关键字添加到函数中，我认为这没有什么不同-编译器应该知道什么时候值得内联而不需要任何提示。它将运行时间从0.31提升到0.23，这比我的快了一点。恭喜你！
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：21

\ $ \ begingroup \ $
用return n替换该函数将时间从0.24秒更改为0.21，因此您的改进比乍一看更有意义。这可能会激励我做一个更好的基准，但今晚不行。
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：49

#3 楼

结论2011-12-05：

我再次使用VS 2010 Express尝试了所有建议。生成的代码变化不大，但是寄存器分配的变化却影响了总体结果。获胜者Ira Baxter建议的简单实现的略微修改就出来了。我从一个假设开始，即比特纠缠将击败包括分支在内的所有事物。我没有真正尝试过任何包含if语句或三元运算符的代码。那是一个错误，因为我没有指望现代CPU内置的分支预测功能。三元解决方案被证明是最快的，特别是当编译器在其中一种情况下用其自己的位纠缠代码替换时。在我的基准算法中，此功能的总体计时从0.24秒减少到0.19。这非常接近我完全卸下夹子时的0.18秒。

\ $ \ begingroup \ $
您是否尝试过使用无符号比较将小于零的检查与大于255的检查相结合？（负数是大的无符号数），例如cmp ecx，255 / jbe .good，因此在不需要钳制的情况下，它是一个单独的熔融比较分支，然后返回到其余代码。或者，将不夹紧的情况设为未取下的分支，然后用其他冷代码将夹紧关闭，然后跳回去。在stackoverflow.com/questions/34071144/…上有一些很好的答案（上面有可变的上限）。
\ $ \ endgroup \ $
– Peter Cordes
15年12月3日在18:46

\ $ \ begingroup \ $
您可以比该代码做得更好。请参阅有关链接的SO问题的答案。 cmp ecx，255 / jbe .no_clamp / mov cl，255 / mov bl，0 / cmovg，bl，cl需要时，您可以将mov bl，0拉出。尽管cmov是Intel上的2 uop指令，但用setcc / dec /仿真cmov是不值得的。
\ $ \ endgroup \ $
– Peter Cordes
2015年12月3日20:05

\ $ \ begingroup \ $
@PeterCordes这个问题是关于C / C ++代码的，而不是汇编的。程序集仅用于帮助理解为什么一个源构造可能比另一个源构造快，并且所有编译器都生成了。
\ $ \ endgroup \ $
– Mark Ransom
15年12月3日在20:39

#4 楼

我很好奇一个简单的分支解决方案将如何执行？

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

\ $ \ begingroup \ $
+1。一些基准测试是有序的。这很可能会利用现代CPU的超标量投机分支执行，并且确实非常快。
\ $ \ endgroup \ $
– Macke
2011年12月3日15:21

\ $ \ begingroup \ $
这几乎与乔纳森·莱夫勒（Jonathan Leffler）的《钳子2》相同，其表现比我预期的要好得多。我想知道是否对订单有所了解？以后我必须让你知道。
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日在16:22

\ $ \ begingroup \ $
我很好奇如何返回std :: min（std :: max（0，n），255）;将公平竞争。
\ $ \ endgroup \ $
–狼人
2011年12月3日在22:24

\ $ \ begingroup \ $
很好：godbolt.org/z/Ni_obb类似于Mark Ransom的：godbolt.org/z/Z4rYdP这个答案中的一个是跳动的，所以我怀疑它会赢：godbolt.org/z/meEuH1
\ $ \ endgroup \ $
–史蒂夫
19-10-1在21:49

#5 楼

在MacOS X上使用GCC / LLVM和64位编译，并生成具有以下内容的汇编器：

gcc -S -Os clamp.c

其中clamp.c包含：

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

这两个函数（带有序言和结语）的汇编器为：

    .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    , %eax
    xorl    , %eax
    negl    %eax
    andl    %edi, %eax
    movl    5, %ecx
    subl    %eax, %ecx
    sarl    , %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    6, %edi
    jl      LBB2_2
    movl    5, %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:

pushq，popq和ret是函数调用开销。您的代码（Clamp_1()）汇编为11条指令；我的跳到9（但是我跳了两次，可能会对流水线执行造成严重破坏）。两种方法都不适合您的优化版本中的7条指令。

有趣的是，当我在同一代码上使用GCC 4.6.1时，汇编器输出为：

    .text
    .globl _Clamp_1
_Clamp_1:
LFB0:
    movl    %edi, %eax
    movl    5, %edx
    notl    %eax
    sarl    , %eax
    andl    %edi, %eax
    subl    %eax, %edx
    sarl    , %edx
    orl     %edx, %eax
    ret
LFE0:
    .globl _Clamp_2
_Clamp_2:
LFB1:
    xorl    %edx, %edx
    testl   %edi, %edi
    movl    5, %eax
    cmovns  %edi, %edx
    cmpl    5, %edx
    cmovle  %edx, %eax
    ret
LFE1:

现在我看到Clamp_1中的8条指令和Clamp_2中的6条指令与ret分开。前者产生优化的（较小的）输出；后者会产生更详细的输出。

\ $ \ begingroup \ $
奇怪的是，我从来没有想过要对您在此处介绍的简单实现进行代码测试。我尝试了一下，时间从0.24秒缩短到0.29，因此没有任何改善。显然，尽管编译器和周围的代码可以产生很大的不同。感谢您的尝试。
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：36

\ $ \ begingroup \ $
我只是尝试了相同的测试，但是包含了inline关键字，它使时间缩短到0.23秒。从现在起，我必须记住将其包括在每个测试中。
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：52

\ $ \ begingroup \ $
我一直在尝试避免使用分支机构花费大量时间的理论，但是显然分支机构的预测比我想象的要先进。感谢您为我的假设加油！
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：56

\ $ \ begingroup \ $
通过单个测试（if（n＆0xFFFFFF00！= 0））查找超出范围的值，让范围内的值仅接受and，test和jump，您可能会获得更快的速度...
\ $ \ endgroup \ $
–jswolf19
2011-12-3 9:38

#6 楼

C ++ 17引入了std::clamp()，因此可以按以下方式实现您的功能：

#include <algorithm>

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

GCC（版本10.2）似乎很好地对其进行了优化，只使用了许多旧版本中所见的比较和条件移动指令答案：

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

但是，在编写本文时，Clang（版本10.0.0）和ICC（版本19.0.1）的汇编输出不是最佳的。 MSVC（19.24版）几乎是最佳选择，但增加了一条分支指令。

\ $ \ begingroup \ $
愚蠢的编译器；我们可以利用无符号比较技巧对cmovae和cmovge使用相同的cmp结果两次，如以下答案所示：x86汇编-将rax夹紧到[0 .. limit）的优化。 GCC的版本特别糟糕，它通过测试第一个cmov的输出而不是原始EDI输入来对关键路径进行测试。是的，叮当声10和11太疯狂了，使用内存并从3个地址中选择一个进行加载。 Clang 9确实接近GCC。
\ $ \ endgroup \ $
– Peter Cordes
12月22日23:15

\ $ \ begingroup \ $
，不，clamp 将负n视为高个无符号数，将其钳位为255而不是0。它的签名钳位为0..255。对于2个可能的钳位值，确实需要2条CMOV指令。
\ $ \ endgroup \ $
– Peter Cordes
12月23日在1:53

#7 楼

结果可能有点取决于像素数据是否在范围之内而不是范围之外。在前一种情况下，这可能会更快：

int clamp(int n)
{
    if ((unsigned) n <= 255) {
        return n;
    }
    return (n < 0) ? 0 : 255;
}

#8 楼

使用您的<0夹并修改> 255夹，该如何堆积？指令，但没有（昂贵的）移位。

inline 
BYTE Clamp(int n)
{
  n &= -(n >= 0);
  return n | ~-!(n & -256);
}

\ $ \ begingroup \ $
与我的大致相同，总共0.24秒，包括许多其他正在进行的事情。我认为自386天以来，移位并不算昂贵，桶形移位器可以在单个时钟周期内进行任何移位计数。
\ $ \ endgroup \ $
– Mark Ransom
2011年12月3日，7：31

\ $ \ begingroup \ $
我想您可以说出我从事x86组装已经有多长时间了。 :)
\ $ \ endgroup \ $
– DocMax
2011年12月3日，7：35

#9 楼

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

如果可以优化-（a> = b）
，则可以优化此设置

#10 楼

怎么办呢？我想知道您的结果中有多少比例需要限制。如果简单却无法解决问题，请尝试以下操作：

x &= 255

\ $ \ begingroup \ $
这已经在评论中建议。不幸的是，对于超出正常范围的值，它并没有做正确的事情-我希望小于0的值变为0，大于255的值变为255。尽管如此，您认为它是有效的。
\ $ \ endgroup \ $
– Mark Ransom
2012年8月9日在17:09

编程黑洞网