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

В статье Арифметика насыщения без ветвей приведены стратегии для этого:

Решение их сложения выглядит следующим образом:

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. Отсутствие 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. Он предоставляет вставные замены для 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-битные вычисления выполняются немного быстрее. Вам решать