Как сделать насыщающее сложение в Си? - PullRequest
Новая
       64

Как сделать насыщающее сложение в Си?

40 голосов
/ 23 сентября 2008

Какой самый лучший (самый чистый, самый эффективный) способ написать насыщающее дополнение в C?

Функция или макрос должны добавить два входа без знака (нужны 16- и 32-разрядные версии) и возвращать все биты один (0xFFFF или 0xFFFFFFFF), если сумма переполняется.

Цель - x86 и ARM, использующие gcc (4.1.2) и Visual Studio (только для моделирования, так что запасная реализация в порядке).

Ответы [ 17 ]

2 голосов
/ 24 сентября 2008

Для наилучшей производительности обычно требуется встроенная сборка (как некоторые уже заявили).

Но для переносимого C эти функции включают только одно сравнение и не приведение типов (и поэтому я считаю оптимальным): 

unsigned saturate_add_uint(unsigned x, unsigned y)
{
    if (y>UINT_MAX-x) return UINT_MAX;
    return x+y;
}

unsigned short saturate_add_ushort(unsigned short x, unsigned short y)
{
    if (y>USHRT_MAX-x) return USHRT_MAX;
    return x+y;
}

Как макросы, они становятся: 

SATURATE_ADD_UINT(x, y) (((y)>UINT_MAX-(x)) ? UINT_MAX : ((x)+(y)))
SATURATE_ADD_USHORT(x, y) (((y)>SHRT_MAX-(x)) ? USHRT_MAX : ((x)+(y)))

Я оставляю версии для «unsigned long» и «unsigned long long» в качестве упражнения для читателя. ; -)

2 голосов
/ 01 октября 2015

На всякий случай, если кто-то захочет узнать реализацию без ветвления, используя 32-битные целые числа с дополнением до 2.

Внимание! Этот код использует неопределенную операцию: «сдвиг вправо на -1» и поэтому использует свойство инструкции Intel Pentium SAL для маскирования операнда счета до 5 бит. 

int32_t sadd(int32_t a, int32_t b){
    int32_t sum = a+b;
    int32_t overflow = ((a^sum)&(b^sum))>>31;
    return (overflow<<31)^(sum>>overflow);
 }

Это лучшая из известных мне реализаций

0 голосов
/ 19 сентября 2018

Арифметика насыщения не является стандартной для C, но часто она реализуется через встроенные функции компилятора, поэтому наиболее эффективный способ будет не самым чистым. Вы должны добавить блоки #ifdef для выбора правильного пути. Ответ MSalters является самым быстрым для архитектуры x86. Для ARM необходимо использовать функцию __qadd16 (компилятор ARM) _arm_qadd16 (Microsoft Visual Studio) для 16-битной версии и __qadd для 32-битной версии. Он будет автоматически переведен в одну инструкцию ARM.

Ссылки:

__qadd16 http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0491c/CJAICDDF.html

_arm_qadd16 https://msdn.microsoft.com/en-US/library/hh875058.aspx

__qadd http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0472m/chr1359125002575.html

0 голосов
/ 22 сентября 2017 
int saturating_add(int x, int y)
{
    int w = sizeof(int) << 3;
    int msb = 1 << (w-1);

    int s = x + y;
    int sign_x = msb & x;
    int sign_y = msb & y;
    int sign_s = msb & s;

    int nflow = sign_x && sign_y && !sign_s;
    int pflow = !sign_x && !sign_y && sign_s;

    int nmask = (~!nflow + 1);
    int pmask = (~!pflow + 1);

    return (nmask & ((pmask & s) | (~pmask & ~msb))) | (~nmask & msb);
}

Эта реализация не использует потоки управления, операторы Campare (==, !=) и оператор ?:. Он просто использует побитовые операторы и логические операторы.

0 голосов
/ 08 марта 2016 
//function-like macro to add signed vals, 
//then test for overlow and clamp to max if required
#define SATURATE_ADD(a,b,val)  ( {\
if( (a>=0) && (b>=0) )\
{\
    val = a + b;\
    if (val < 0) {val=0x7fffffff;}\
}\
else if( (a<=0) && (b<=0) )\
{\
    val = a + b;\
    if (val > 0) {val=-1*0x7fffffff;}\
}\
else\
{\
    val = a + b;\
}\
})

Я провел быструю проверку и, кажется, сработал, но пока еще не разбил ее! Это работает с SIGNED 32 бит. op: редактор, используемый на веб-странице, не позволяет мне публиковать макрос, т.е. он не понимает синтаксис без отступов и т. д.

0 голосов
/ 21 января 2015

Альтернативой бесплатному x86 asm-решению является филиал (синтаксис AT & T, a и b в eax и ebx, результат в eax): 

add %eax,%ebx
sbb $0,%ebx
0 голосов
/ 17 июня 2014

Используя C ++, вы можете написать более гибкий вариант решения Remo.D : 

template<typename T>
T sadd(T first, T second)
{
    static_assert(std::is_integral<T>::value, "sadd is not defined for non-integral types");
    return first > std::numeric_limits<T>::max() - second ? std::numeric_limits<T>::max() : first + second;
}

Это можно легко перевести на C - используя ограничения, определенные в limits.h. Также обратите внимание, что целочисленные типы с фиксированной шириной могут быть недоступны в вашей системе.

Страница:
...