Вычитание / добавление насыщения для беззнаковых байтов

Представьте, что у меня есть два байта без знака bи x. Мне нужно рассчитать bsubкак b - xи baddкак b + x. Однако я не хочу, чтобы во время этих операций происходило переполнение / переполнение. Например (псевдокод):

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

и

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

Очевидный способ сделать это включает ветвление:

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

Мне просто интересно, есть ли какие-нибудь лучшие способы сделать это, например, с помощью каких-то хитрых манипуляций?

В статье Branchfree Saturating Arithmetic представлены стратегии для этого:

Их дополнительный раствор выглядит следующим образом:

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

    return res;
}

изменено для uint8_t:

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

    return res;
}

и их решение вычитания:

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

    return res;
}

изменено для uint8_t:

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

    return res;
}

Простой метод - обнаружить переполнение и соответственно сбросить значение, как показано ниже.

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

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

GCC может оптимизировать проверку переполнения в условное присвоение при компиляции с -O2.

Я замерил, насколько оптимизация по сравнению с другими решениями. При более чем 1000000000 операций на моем компьютере это решение и решение @ShafikYaghmour в среднем занимали 4,2 секунды, а решение @chux - 4,8 секунды. Это решение также более читабельно.

Для вычитания:

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

Дополнение:

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

Эволюция

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

Спасибо @R_Kapp

Спасибо @NathanOliver

Это упражнение показывает ценность простого кодирования.

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

Если вы используете достаточно свежую версию gcc или clang (возможно, также некоторые другие), вы можете использовать встроенные модули для обнаружения переполнения.

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

Для дополнения:

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

Для вычитания:

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

Операторы сравнения или умножения не требуются.

Если вы хотите использовать сборку или встроенные функции, я думаю, что у меня есть оптимальное решение.

Для вычитания:

Можем воспользоваться sbbинструкцией

В MSVC мы можем использовать встроенную функцию _subborrow_u64 (также доступна в других битовых размерах).

Вот как это используется:

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

Вот как мы можем применить это к вашей ситуации

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

Для дополнения:

Можем воспользоваться adcxинструкцией

В MSVC мы можем использовать встроенную функцию _addcarry_u64 (также доступна в других битовых размерах).

Вот как это используется:

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

Вот как мы можем применить это к вашей ситуации

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

Мне этот метод не нравится так сильно, как метод вычитания, но я думаю, что он довольно изящный.

Если добавить переполняется, carry_flag = 1. Not-ing carry_flagдает 0, поэтому !carry_flag * result = 0при переполнении. А поскольку 0 - 1установит максимальное целое значение без знака, функция вернет результат сложения, если нет переноса, и вернет максимум выбранного интегрального значения, если есть перенос.

что насчет этого:

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

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

Все может быть выполнено в беззнаковой байтовой арифметике

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

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

Если вы хотите сделать это с двумя байтами, используйте самый простой из возможных код.

Если вы хотите сделать это с двадцатью миллиардами байтов, проверьте, какие векторные инструкции доступны на вашем процессоре и можно ли их использовать. Вы можете обнаружить, что ваш процессор может выполнять 32 из этих операций с помощью одной инструкции.

Вы также можете использовать безопасную цифровую библиотеку в Boost Library Incubator . Он обеспечивает замену для int, long и т. Д., Что гарантирует, что вы никогда не получите необнаруженного переполнения, потери значимости и т. Д.

Если вы будете часто вызывать эти методы, самым быстрым способом будет не битовая манипуляция, а, вероятно, таблица поиска. Определите массив длиной 511 для каждой операции. Пример на минус (вычитание)

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

Массив статичен и инициализируется только один раз. Теперь ваше вычитание можно определить как встроенный метод или с помощью прекомпилятора:

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

Как это устроено? Ну, вы хотите предварительно вычислить все возможные вычитания для беззнаковых символов. Результаты варьируются от -255 до +255, всего 511 различных результатов. Мы определяем массив всех возможных результатов, но поскольку в C мы не можем получить к нему доступ по отрицательным индексам, мы используем +255 (в [A-B + 255]). Вы можете удалить это действие, указав указатель на центр массива.

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

используйте это как:

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

Обратите внимание, что выполнение происходит очень быстро. Только одно вычитание и одно указание, чтобы получить результат. Нет ветвления. Статические массивы очень короткие, поэтому они будут полностью загружены в кеш процессора для дальнейшего ускорения вычислений.

То же самое будет работать для сложения, но с немного другой таблицей (первые 256 элементов будут индексами, а последние 255 элементов будут равны 255, чтобы имитировать отсечение выше 255.

Если вы настаиваете на работе с битами, ответы, в которых используется (a> b), неверны. Это все еще может быть реализовано как ветвление. Используйте знаковый бит

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

Теперь вы можете использовать его для вычисления вычитания и сложения.

Если вы хотите эмулировать функции max (), min () без разветвления, используйте:

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

В моих примерах выше используются 32-битные целые числа. Вы можете изменить его на 64, хотя я считаю, что 32-битные вычисления выполняются немного быстрее. Вам решать