Sujeción corta a sin firma char

Tengo una función C simple de la siguiente manera:

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

¿Es posible reescribirlo sin usar cualquier ramificación if / else siendo eficiente?

EDITAR:

Básicamente, quiero ver si es posible alguna implementación de sujeción basada en aritmética de bits. El objective es procesar imágenes en GPU (unidad de procesamiento de gráficos). Este tipo de código se ejecutará en cada píxel. Supongo que si se pueden evitar las twigs, entonces el rendimiento general sobre la GPU sería mayor.

Una solución como (valor 255)? 255: valor)) es simplemente una repetición de si / else se ramifica con azúcar sintáctica. Así que no la estoy buscando.

EDIT 2:

Puedo reducirlo a uno solo de la siguiente manera pero no puedo pensar mejor:

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

EDITAR 3:

Acabo de ver una muy buena implementación de esto en el código 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; } 

Esto ciertamente funciona y lo reduce a uno si está bien.

Usted escribe que desea evitar la ramificación en la GPU. Es cierto que la bifurcación puede ser muy costosa en un entorno paralelo porque se deben evaluar ambas bifurcaciones o se debe aplicar la sincronización. Pero si las twigs son lo suficientemente pequeñas, el código será más rápido que la mayoría de las operaciones aritméticas. La guía de buenas prácticas de CUDA C describe por qué:

A veces, el comstackdor puede [..] optimizar hacia fuera if o cambiar las declaraciones utilizando la predicación de twig en su lugar. En estos casos, ninguna deformación puede ser divergente. [..]

Cuando se usa la predicción de twig, ninguna de las instrucciones cuya ejecución depende de la condición de control se omite. En su lugar, cada uno de ellos está asociado con un código de condición por hilo o predicado que se establece en verdadero o falso según la condición de control y, aunque cada una de estas instrucciones se progtwig para su ejecución, solo se ejecutan las instrucciones con un predicado verdadero. Las instrucciones con un predicado falso no escriben resultados y tampoco evalúan direcciones ni leen operandos.

La predicación de la twig es rápida. ¡Sangriento rápido! Si observa el código PTX intermedio generado por el comstackdor de optimización, verá que es superior incluso a la aritmética modesta. Por lo tanto, el código como en la respuesta de davmac es probablemente lo más rápido posible.

Sé que no ha preguntado específicamente sobre CUDA, pero la mayoría de las guías de mejores prácticas también se aplican a OpenCL y probablemente a una gran parte de la progtwigción de GPU de AMD.

Por cierto: en prácticamente todos los casos de código de GPU que he visto, la mayor parte del tiempo se dedica al acceso a la memoria, no a la aritmética. Asegúrate de hacer un perfil! http://en.wikipedia.org/wiki/Program_optimization

Si solo quieres evitar el real if / else, usa el ? : ? : operador:

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

Sin embargo, en términos de eficiencia, esto no debería ser diferente.

En la práctica, no debes preocuparte por la eficiencia con algo tan trivial como esto. Deja que el comstackdor haga la optimización.

Podrías hacer una tabla de búsqueda 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]; } 

Claro que esto parece extraño (una tabla de 64 KB para este cálculo trivial). Sin embargo, considerando que mencionaste que querías hacer esto en una GPU, estoy pensando que lo anterior podría ser una búsqueda de texturas, que creo que son bastante rápidas para las GPU.

Además, si su GPU usa OpenGL, podría, por supuesto, usar la clamp incorporada directamente:

 clamp(value, 0, 255); 

Esto no será de conversión de tipo (parece que no hay un tipo de entero de 8 bits en GLSL), pero aún así.

Puede hacerlo sin explícito if usa ?: Como lo muestra otro póster o usando propiedades interesantes de abs() que le permiten calcular el máximo o el mínimo de dos valores.

Por ejemplo, la expresión (a + abs(a))/2 devuelve a para números positivos y 0 caso contrario (máximo de a y 0 ).

Esto da

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

Para convencerse de que esto funciona, aquí hay un progtwig de prueba:

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

Cuando se ejecuta, esto imprime

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

Por supuesto, se puede argumentar que probablemente hay una prueba en abs() , pero gcc -O3 por ejemplo, la comstack de forma lineal:

 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 

Pero tenga en cuenta que esto será mucho más ineficiente que su función original, que se comstack como:

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

Pero al menos responde a tu pregunta 🙂

Qué tal si:

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

Pero dudo seriamente que se ejecute más rápido que su versión original con sucursales.

Suponiendo un cortocircuito de dos bytes, y al costo de legibilidad del código:

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

Debes cronometrar esta versión fea pero solo aritmética.

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

Una forma de hacerlo eficiente es declarar esta función como en línea para evitar gastos de llamadas a funciones. también podría convertirlo en macro usando un operador terciario, pero eso eliminará la verificación de tipo de retorno por comstackdor.