c++ - Restar/sumar saturación para bytes sin signo

optimization bit-manipulation

Question

Imagine que tengo dos bytes sin firmar b x . Necesito calcular bsub como b - x y badd como b + x . Sin embargo, no quiero que ocurra un desbordamiento / desbordamiento durante estas operaciones. Por ejemplo (pseudocódigo):

b = 3; x = 5;
bsub = b - x; // bsub must be 0, not 254

y

b = 250; x = 10;
badd = b + x; // badd must be 255, not 4

La forma obvia de hacer esto incluye la ramificación:

bsub = b - min(b, x);
badd = b + min(255 - b, x);

Solo me pregunto si hay mejores maneras de hacer esto, es decir, mediante algunas manipulaciones poco hacky.

Answer 1

El artículo Branchfree Saturating Arithmetic proporciona estrategias para esto:

Su solución de adición es la siguiente:

u32b sat_addu32b(u32b x, u32b y)
{
    u32b res = x + y;
    res |= -(res < x);

    return res;
}

modificado para uint8_t:

uint8_t  sat_addu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x + y;
    res |= -(res < x);

    return res;
}

y su solución de resta es:

u32b sat_subu32b(u32b x, u32b y)
{
    u32b res = x - y;
    res &= -(res <= x);

    return res;
}

modificado para uint8_t:

uint8_t sat_subu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x - y;
    res &= -(res <= x);

    return res;
}

Answer 2

Para la adición:

// *c = a - (b + borrow)
// borrow_flag is set to 1 if (a < (b + borrow))
borrow_flag = _subborrow_u64(borrow_flag, a, b, c);

Para restar:

uint64_t sub_no_underflow(uint64_t a, uint64_t b){
    uint64_t result;
    borrow_flag = _subborrow_u64(0, a, b, &result);
    return result * !borrow_flag;
}

No se requieren operadores de comparación o multiplicadores.

Answer 3

Para restar:

diff = (a - b)*(a >= b);

Adición:

sum = (a + b) | -(a > (255 - b))

Evolución

// sum = (a + b)*(a <= (255-b)); this fails
// sum = (a + b) | -(a <= (255 - b)) falis too

Gracias a @R_Kapp

Gracias a @NathanOliver

Este ejercicio muestra el valor de la simple codificación.

sum = b + min(255 - b, a);

Answer 4

Si desea hacer esto con dos bytes, use el código más simple posible.

Si desea hacer esto con veinte mil millones de bytes, verifique qué instrucciones de vector están disponibles en su procesador y si se pueden usar. Es posible que su procesador pueda realizar 32 de estas operaciones con una sola instrucción.

Answer 5

Si está dispuesto a usar ensamblaje o intrínseco, creo que tengo una solución óptima.

Para restar:

Podemos usar la instrucción sbb

En MSVC podemos usar la función intrínseca _subborrow_u64 (también disponible en otros tamaños de bits).

Así es como se usa:

// *c = a + b + carry
// carry_flag is set to 1 if there is a carry bit
carry_flag = _addcarry_u64(carry_flag, a, b, c);

Así es como podríamos aplicarlo a su situación.

uint64_t add_no_overflow(uint64_t a, uint64_t b){
    uint64_t result;
    carry_flag = _addcarry_u64(0, a, b, &result);
    return !carry_flag * result - carry_flag;
}

Para la adición:

Podemos usar la instrucción adcx

En MSVC podemos usar la función intrínseca _addcarry_u64 (también disponible en otros tamaños de bits).

Así es como se usa:

unsigned temp = a+b;  // temp>>8 will be 1 if overflow else 0
unsigned char c = temp | -(temp >> 8);

Así es como podríamos aplicarlo a su situación.

unsigned temp = a-b;  // temp>>8 will be 0xFF if neg-overflow else 0
unsigned char c = temp & ~(temp >> 8);

Este no me gusta tanto como el de resta, pero creo que es bastante ingenioso.

Si la adición se desborda, carry_flag = 1 . Si no se carry_flag obtiene 0, por lo que !carry_flag * result = 0 cuando hay un desbordamiento. Y dado que 0 - 1 establecerá el valor integral sin signo en su valor máximo, la función devolverá el resultado de la suma si no hay carry y devolverá el valor máximo del valor integral elegido si hay carry.

Answer 6

Si está utilizando una versión lo suficientemente reciente de gcc o clang (tal vez también algunas otras), podría usar built-ins para detectar el desbordamiento.

if (__builtin_add_overflow(a,b,&c))
{
  c = UINT_MAX;
}

Answer 7

Si llama mucho a esos métodos, la forma más rápida no sería la manipulación de bits, sino probablemente una tabla de búsqueda. Defina una matriz de longitud 511 para cada operación. Ejemplo para menos (resta)

static unsigned char   maxTable[511];
memset(maxTable, 0, 255);           // If smaller, emulates cutoff at zero
maxTable[255]=0;                    // If equal     - return zero
for (int i=0; i<256; i++)
    maxTable[255+i] = i;            // If greater   - return the difference

La matriz es estática y se inicializa solo una vez. Ahora su resta se puede definir como método en línea o usando el precompilador:

#define MINUS(A,B)    maxTable[A-B+255];

¿Cómo funciona? Bueno, desea calcular previamente todas las posibles restas para caracteres sin signo. Los resultados varían de -255 a +255, total de 511 resultados diferentes. Definimos una matriz de todos los resultados posibles, pero debido a que en C no podemos acceder desde índices negativos, usamos +255 (en [A-B + 255]). Puede eliminar esta acción definiendo un puntero al centro de la matriz.

const unsigned char *result = maxTable+255;
#define MINUS(A,B)    result[A-B];

úsalo como:

bsub  = MINUS(13,15); // i.e 13-15 with zero cutoff as requested

Tenga en cuenta que la ejecución es extremadamente rápida. Solo una resta y una deferencia de puntero para obtener el resultado. Sin ramificaciones. Las matrices estáticas son muy cortas, por lo que se cargarán completamente en la memoria caché de la CPU para acelerar aún más el cálculo.

Lo mismo funcionaría para la suma, pero con una tabla un poco diferente (los primeros 256 elementos serán los índices y los últimos 255 elementos serán iguales a 255 para emular el límite más allá de 255.

Si insiste en la operación de bits, las respuestas que usan (a> b) son incorrectas. Esto aún podría implementarse como ramificación. Utiliza la técnica de bit de signo

// (num1>num2) ? 1 : 0
#define        is_int_biggerNotEqual( num1,num2) ((((__int32)((num2)-(num1)))&0x80000000)>>31)

Ahora puede usarlo para calcular la resta y la suma.

Si desea emular las funciones max (), min () sin bifurcación, use:

inline __int32 MIN_INT(__int32 x, __int32 y){   __int32 d=x-y; return y+(d&(d>>31)); }              

inline __int32 MAX_INT(__int32 x, __int32 y){   __int32 d=x-y; return x-(d&(d>>31)); }

Mis ejemplos anteriores usan números enteros de 32 bits. Puede cambiarlo a 64, aunque creo que los cálculos de 32 bits se ejecutan un poco más rápido. Depende de usted

Answer 8

También puede usar la biblioteca de números seguros en Boost Library Incubator . Proporciona reemplazos directos para int, long, etc ... que garantizan que nunca obtendrá un desbordamiento, subflujo, etc.

Answer 9

Todo se puede hacer en aritmética de bytes sin signo

// Addition without overflow
return (b > 255 - a) ? 255 : a + b

// Subtraction without underflow
return (b > a) ? 0 : a - b;

Answer 10

Un método simple es detectar el desbordamiento y restablecer el valor como se muestra a continuación.

bsub = b - x;
if (bsub > b)
{
    bsub = 0;
}

badd = b + x;
if (badd < b)
{
    badd = 255;
}

GCC puede optimizar la verificación de desbordamiento en una asignación condicional al compilar con -O2.

Medí cuánta optimización en comparación con otras soluciones. Con 1000000000+ operaciones en mi PC, esta solución y la de @ShafikYaghmour promediaron 4.2 segundos, y la de @chux promedió 4.8 segundos. Esta solución también es más legible.

Answer 11

que hay de esto:

bsum = a + b;
bsum = (bsum < a || bsum < b) ? 255 : bsum;

bsub = a - b;
bsub = (bsub > a || bsub > b) ? 0 : bsub;