将short 钳位为无符号字符

Question

我有一个简单的 C 函数，如下所示：

unsigned char clamp(short value){
    if (value < 0) return 0;
    if (value > 0xff) return 0xff;
    return value;
}

是否可以在不使用任何 if / else 分支的情况下重写它，同时保持高效？

编辑：

我基本上希望看看是否可以进行一些基于位算术的钳位实现。目的是在GPU（图形处理单元）上处理图像。这种类型的代码将在每个像素上运行。我猜想如果可以避免分支，那么 GPU 上的总体吞吐量将会更高。

像 (value <0? 0 : ((value > 255) ? 255 : value) ) 这样的解决方案只是用语法糖重新编写 if/else 分支。所以我不寻找它。

编辑 2：

我可以将其缩减为单个 if ，如下所示，但我无法更好地思考：

unsigned char clamp(short value){
    int more = value >> 8;
    if(more){
        int sign = !(more >> 7);
        return sign * 0xff;
    }
    return value;
}

编辑 3：

刚刚在 FFmpeg 代码中看到了一个非常好的实现：

/**
 * Clip a signed integer value into the 0-255 range.
 * @param a value to clip
 * @return clipped value
 */
static av_always_inline av_const uint8_t av_clip_uint8_c(int a)
{
    if (a&(~0xFF)) return (-a)>>31;
    else           return a;
}

这当然有效，并将其缩减为一个 if 很好。

Answer 1

您写道您希望避免在 GPU 上进行分支。确实，在并行环境中分支的成本可能非常高，因为必须评估两个分支或必须应用同步。但如果分支足够小，代码将比大多数算术更快。 CUDA C 最佳实践指南描述了原因：

有时，编译器可能 [..]
优化 if 或 switch 语句
通过使用分支预测来代替。
在这些情况下，任何扭曲都不能
发散。 [..]

当使用分支谓词时，没有
执行的指令
取决于控制条件
被跳过。相反，他们每个人都是
与每线程条件相关
设置为 true 的代码或谓词
或基于控制的错误
条件，虽然这些
指令已安排
执行，只有指令
真正的谓词实际上是
被执行。指令有假
谓词不写结果，并且
也不评估地址或读取
操作数。

分支预测速度很快。真他妈快！如果您查看优化编译器生成的中间 PTX 代码，您会发现它甚至优于普通算术。所以 davmac 的答案中的代码可能是尽可能快的。

我知道您没有具体询问 CUDA，但大多数最佳实践指南也适用于 OpenCL，可能还适用于 AMD GPU 编程的大部分内容。

顺便说一句：在我见过的几乎所有 GPU 代码中，大部分时间都花在内存访问上，而不是算术上。请务必进行简介！ http://en.wikipedia.org/wiki/Program_optimization

Answer 2

如果您只是想避免实际的 if/else，请使用 ? : 运算符：

return value < 0 ? 0 : (value > 0xff ? 0xff : value);

但是，就效率而言，这应该没有什么不同。

在实践中，您不应该担心像这样微不足道的事情的效率。让编译器进行优化。

Answer 3

你可以做一个 2D 查找表：

unsigned char clamp(short value)
{
  static const unsigned char table[256][256] = { ... }

  const unsigned char x = value & 0xff;
  const unsigned char y = (value >> 8) & 0xff;
  return table[y][x];
}

当然这看起来很奇怪（一个 64 KB 的表用于这个微不足道的计算）。然而，考虑到您提到您想在 GPU 上执行此操作，我认为上面的操作可能是纹理查找，我相信这在 GPU 上速度相当快。

此外，如果您的 GPU 使用 OpenGL，您当然可以使用 clamp 直接内置：

clamp(value, 0, 255);

这不会进行类型转换（GLSL 中似乎没有 8 位整数类型），但仍然如此。

Answer 4

您可以在没有显式 if 的情况下通过使用 ?: （如另一张海报所示）或使用 abs() 的有趣属性（它可以让您计算）来完成此操作两个值的最大值或最小值。

例如，表达式 (a + abs(a))/2 对于正数返回 a，否则返回 0（的最大值） a 和 0）。

为了

unsigned char clip(short value)
{
  short a = (value + abs(value)) / 2;
  return (a + 255 - abs(a - 255)) / 2;
}

让自己相信这是有效的，这里有一个测试程序：

#include <stdio.h>

unsigned char clip(short value)
{
  short a = (value + abs(value)) / 2;
  return (a + 255 - abs(a - 255)) / 2;
}

void test(short value)
{
  printf("clip(%d) = %d\n", value, clip(value));
}

int main()
{
  test(0);
  test(10);
  test(-10);
  test(255);
  test(265);
  return 0;
}

运行时，会打印

clip(0) = 0
clip(10) = 10
clip(-10) = 0
clip(255) = 255
clip(265) = 255

当然，有人可能会说 abs() 中可能有一个测试，但是 gcc -例如，O3 线性编译它：

clip:
    movswl  %di, %edi
    movl    %edi, %edx
    sarl    $31, %edx
    movl    %edx, %eax
    xorl    %edi, %eax
    subl    %edx, %eax
    addl    %edi, %eax
    movl    %eax, %edx
    shrl    $31, %edx
    addl    %eax, %edx
    sarl    %edx
    movswl  %dx, %edx
    leal    255(%rdx), %eax
    subl    $255, %edx
    movl    %edx, %ecx
    sarl    $31, %ecx
    xorl    %ecx, %edx
    subl    %ecx, %edx
    subl    %edx, %eax
    movl    %eax, %edx
    shrl    $31, %edx
    addl    %edx, %eax
    sarl    %eax
    ret

但请注意，这比原始函数效率低得多，原始函数编译为：

clip:
    xorl    %eax, %eax
    testw   %di, %di
    js      .L1
    movl    $-1, %eax
    cmpw    $255, %di
    cmovle  %edi, %eax
.L1:
    rep
    ret

但至少它回答了你的问题:)

Answer 5

怎么样：

unsigned char clamp (short value) {
    unsigned char r = (value >> 15);          /* uses arithmetic right-shift */
    unsigned char s = !!(value & 0x7f00) * 0xff;
    unsigned char v = (value & 0xff);
    return (v | s) & ~r;
}

但我严重怀疑它的执行速度是否比涉及分支的原始版本更快。

Answer 6

假设短两个字节，并以代码可读性为代价：

clipped_x =  (x & 0x8000) ? 0 : ((x >> 8) ? 0xFF : x);

Answer 7

你应该为这个丑陋但仅算术的版本计时。

unsigned char clamp(short value){
  short pmask = ((value & 0x4000) >> 7) | ((value & 0x2000) >> 6) |
    ((value & 0x1000) >> 5) | ((value & 0x0800) >> 4) |
    ((value & 0x0400) >> 3) | ((value & 0x0200) >> 2) |
    ((value & 0x0100) >> 1);
  pmask |= (pmask >> 1) | (pmask >> 2) | (pmask >> 3) | (pmask >> 4) |
    (pmask >> 5) | (pmask >> 6) | (pmask >> 7);
  value |= pmask;
  short nmask = (value & 0x8000) >> 8;
  nmask |= (nmask >> 1) | (nmask >> 2) | (nmask >> 3) | (nmask >> 4) |
    (nmask >> 5) | (nmask >> 6) | (nmask >> 7);
  value &= ~nmask;
  return value;
}

Answer 8

提高效率的一种方法是将此函数声明为内联函数，以避免函数调用费用。您还可以使用三级运算符将其转换为宏，但这将删除编译器的返回类型检查。