Restar / sumar saturación para bytes sin firmar

Imagina que tengo dos bytes sin firmar by x. Necesito calcular bsubcomo b - xy baddcomo b + x. Sin embargo, no quiero que se produzca subdesbordamiento / 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);

Me pregunto si hay mejores formas de hacer esto, es decir, mediante algunas manipulaciones de bits hacky.

El artículo Aritmética de saturación sin ramas 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;
}

Un método simple es detectar el desbordamiento y restablecer el valor en consecuencia 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í la cantidad de optimización en comparación con otras soluciones. Con más de 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.

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 simplemente codificar.

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

Si está usando una versión lo suficientemente reciente de gcc o clang (tal vez también algunas otras), puede usar incorporados para detectar desbordamientos.

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

Por adición:

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

Para restar:

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

No se requieren operadores de comparación ni multiplicaciones.

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

Para restar:

Podemos usar la sbbinstrucción

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 + borrow)
// borrow_flag is set to 1 if (a < (b + borrow))
borrow_flag = _subborrow_u64(borrow_flag, a, b, c);

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

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

Por adición:

Podemos usar la adcxinstrucción

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:

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

No me gusta tanto este como el de resta, pero creo que es bastante ingenioso.

Si el complemento se desborda, carry_flag = 1. Not-ing carry_flagproduce 0, por lo que !carry_flag * result = 0cuando hay desbordamiento. Y dado 0 - 1que establecerá el valor integral sin firmar a su máximo, la función devolverá el resultado de la suma si no hay acarreo y devolverá el máximo del valor integral elegido si hay acarreo.

que hay de esto:

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

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

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

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

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

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 vectoriales están disponibles en su procesador y si pueden usarse. Puede encontrar que su procesador puede realizar 32 de estas operaciones con una sola instrucción.

También puede usar la biblioteca numérica segura en Boost Library Incubator . Proporciona reemplazos directos para int, long, etc., lo que garantiza que nunca obtendrá un desbordamiento, un desbordamiento, etc., no detectados.

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 de 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 sustracciones de caracteres sin firmar. Los resultados varían de -255 a +255, total de 511 resultados diferentes. Definimos una matriz de todos los resultados posibles, pero como en C no podemos acceder a ella 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 adición 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 todavía podría implementarse como ramificación. Usa la técnica del bit de signo

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

Ahora puedes usarlo para calcular restas y sumas.

Si desea emular las funciones max (), min () sin ramificar, 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