Зажимных короткий неподписанный символ

Question

У меня есть простая функция C следующим образом:

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

Можно ли переписать его без использования какого-либо если/другое разветвления в то же время эффективным?

EDIT:

Я в основном хотел бы видеть, если некоторые побитовое арифметика на основе реализации зажима возможно. Цель состоит в обработке изображений на графическом процессоре (графическом процессоре). Этот тип кода будет работать на каждом пикселе. Я предполагаю, что если ветви можно избежать, общая пропускная способность по сравнению с графическим процессором будет выше.

Решение, подобное (значение < 0? 0: ((значение> 255)? 255: значение)) - это просто перефразирование if/else, ветвящегося синтаксическим сахаром. Поэтому я не ищу его.

EDIT 2:

Я могу сократить его до одного, если так, но я не могу думать лучше:

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

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

Это, безусловно, работает и сводит его к одному, если славно LY.

Answer 1

Вы пишете, что вы хотите, чтобы избежать ветвления на GPU. Верно, что ветвление может быть очень дорогостоящим в параллельной среде, потому что либо обе ветви должны быть оценены, либо требуется синхронизация. Но если ветви достаточно малы, код будет быстрее, чем большинство арифметических. CUDA C best practices guide описывает, почему:

Иногда компилятор может [..] оптимизировать, если или переключить ЗАЯВЛЕНИЯ с помощью ветви предикацию вместо. В этих случаях никакая деформация никогда не может расходиться. [..]

Когда не используя филиальную предикации ни один из инструкции, выполнение зависит от управляющего состояния получает пропущено. Вместо этого, каждый из них связан с каждым потоком условием кодом или предикатом, который устанавливается истина или ложь на основе контрольного состояния и хотя каждый из этих инструкций получает запланированную для исполнения, только инструкций с истинный предикат фактически выполнен .Инструкции с ложным предикатом не записывают результаты, а также не оценивают адреса или не читают операндов.

Прецизионность филиала быстро. Кровавый быстро! Если вы посмотрите на промежуточный код PTX, созданный оптимизирующим компилятором, вы увидите, что он превосходит даже скромную арифметику. Таким образом, код, похожий на ответ davmac, вероятно, так же быстро, как может быть.

Я знаю, что вы не спрашивали конкретно о CUDA, но большинство руководств по лучшим практикам также относится к OpenCL и, вероятно, к большим частям программирования графического процессора AMD.

BTW: практически в каждом случае кода графического процессора, который я когда-либо видел, большую часть времени тратит на доступ к памяти, а не по арифметике. Удостоверьтесь, что профиль! http://en.wikipedia.org/wiki/Program_optimization

Answer 2

Если вы просто хотите, чтобы избежать фактического если/другое, используя оператор ? ::

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

Однако, с точки зрения эффективности это не должно быть иначе.

На практике вы не должны беспокоиться об эффективности с чем-то таким тривиальным, как это. Пусть компилятор выполнит оптимизацию.

Answer 3

Один из способов сделать его эффективным - объявить эту функцию как встроенную, чтобы избежать расходов на вызов функций. вы также можете превратить его в макрос, используя третичный оператор, но который удалит проверку возвращаемого типа компилятором.

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, например, компилирует его l inearly:

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

Вы могли бы сделать таблица 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 КБ для этого тривиального вычисления ион). Однако, учитывая, что вы упомянули о том, что хотите сделать это на графическом процессоре, я думаю, что вышеизложенное может быть результатом поиска текстур, который, как я считаю, довольно быстро работает на графических процессорах.

Кроме того, если ваш GPU использует OpenGL, вы могли бы, конечно, просто использовать clamp встроенной команды непосредственно:

clamp(value, 0, 255); 

Это не печатает-обращенного (нет 8-разрядного целого числа типа в GLSL, его похоже), но все еще.

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

Как насчет:

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

Но я серьезно сомневаюсь, что он выполняет быстрее, чем ваши оригинальные версии с участием филиалов.