Как выполнить беззнаковое насыщающее сложение в C?
https://stackoverflow.com/questions/121240
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Каков наилучший (самый чистый и эффективный) способ написать насыщающее сложение на C?
Функция или макрос должны добавить два беззнаковых входа (нужны как 16-, так и 32-битные версии) и вернуть все биты — единицу (0xFFFF или 0xFFFFFFFF), если сумма переполняется.
Целью является x86 и ARM с использованием gcc (4.1.2) и Visual Studio (только для моделирования, поэтому здесь можно использовать резервную реализацию).
Решение
Вы, вероятно, хотите портативный C здесь код, который ваш компилятор превратит в правильную сборку ARM.В ARM есть условные перемещения, и они могут быть обусловлены переполнением.Затем алгоритм добавляется и условно устанавливает место назначения в значение без знака (-1), если обнаружено переполнение.
uint16_t add16(uint16_t a, uint16_t b)
{
uint16_t c = a + b;
if (c<a) /* Can only happen due to overflow */
c = -1;
return c;
}
Обратите внимание, что он отличается от других алгоритмов тем, что исправляет переполнение, а не полагается на другие вычисления для обнаружения переполнения.
x86-64 вывод clang 3.7 -O3 для adds32:значительно лучше, чем любой другой ответ:
add edi, esi
mov eax, -1
cmovae eax, edi
ret
ARMv7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm вывод для adds32:
adds r0, r0, r1 @ c, a, b
it cs
movcs r0, #-1 @ conditional-move
bx lr
16бит:до сих пор не использует инструкцию добавления беззнакового насыщения ARM (UADD16)
add r1, r1, r0 @ tmp114, a
movw r3, #65535 @ tmp116,
uxth r1, r1 @ c, tmp114
cmp r0, r1 @ a, c
ite ls @
movls r0, r1 @,, c
movhi r0, r3 @,, tmp116
bx lr @
Другие советы
В простом C:
uint16_t sadd16(uint16_t a, uint16_t b)
{ return (a > 0xFFFF - b) ? 0xFFFF : a + b; }
uint32_t sadd32(uint32_t a, uint32_t b)
{ return (a > 0xFFFFFFFF - b) ? 0xFFFFFFFF : a + b;}
который почти макрозирован и прямо передает смысл.
В IA32 без условных переходов:
uint32_t sadd32(uint32_t a, uint32_t b)
{
#if defined IA32
__asm
{
mov eax,a
xor edx,edx
add eax,b
setnc dl
dec edx
or eax,edx
}
#elif defined ARM
// ARM code
#else
// non-IA32/ARM way, copy from above
#endif
}
В ARM у вас уже может быть встроена насыщенная арифметика.Расширения DSP ARMv5 могут насыщать регистры до любой разрядности.Кроме того, насыщение ARM обычно обходится дешево, поскольку вы можете выполнять большинство инструкций условно.
В ARMv6 даже есть насыщенное сложение, вычитание и все остальное для 32-битных и упакованных чисел.
На x86 вы получаете насыщенную арифметику либо через MMX, либо через SSE.
Для всего этого нужен ассемблер, так что это не то, что вы просили.
Существуют также C-трюки для выполнения насыщенной арифметики.Этот небольшой код выполняет насыщенное сложение четырех байтов двойного слова.Он основан на идее параллельного расчета 32 полусумматоров, напримердобавление чисел без переполнения переноса.
Это делается в первую очередь.Затем переносы вычисляются, добавляются и заменяются маской, если сложение приведет к переполнению.
uint32_t SatAddUnsigned8(uint32_t x, uint32_t y)
{
uint32_t signmask = 0x80808080;
uint32_t t0 = (y ^ x) & signmask;
uint32_t t1 = (y & x) & signmask;
x &= ~signmask;
y &= ~signmask;
x += y;
t1 |= t0 & x;
t1 = (t1 << 1) - (t1 >> 7);
return (x ^ t0) | t1;
}
Вы можете получить то же самое для 16 бит (или любого битового поля), изменив константу маски знака и сдвиги внизу следующим образом:
uint32_t SatAddUnsigned16(uint32_t x, uint32_t y)
{
uint32_t signmask = 0x80008000;
uint32_t t0 = (y ^ x) & signmask;
uint32_t t1 = (y & x) & signmask;
x &= ~signmask;
y &= ~signmask;
x += y;
t1 |= t0 & x;
t1 = (t1 << 1) - (t1 >> 15);
return (x ^ t0) | t1;
}
uint32_t SatAddUnsigned32 (uint32_t x, uint32_t y)
{
uint32_t signmask = 0x80000000;
uint32_t t0 = (y ^ x) & signmask;
uint32_t t1 = (y & x) & signmask;
x &= ~signmask;
y &= ~signmask;
x += y;
t1 |= t0 & x;
t1 = (t1 << 1) - (t1 >> 31);
return (x ^ t0) | t1;
}
Приведенный выше код делает то же самое для 16- и 32-битных значений.
Если вам не нужна функция, позволяющая функциям параллельно добавлять и насыщать несколько значений, просто замаскируйте нужные вам биты.В ARM вам также необходимо изменить константу маски знака, поскольку ARM не может загрузить все возможные 32-битные константы за один цикл.
Редактировать: Параллельные версии, скорее всего, медленнее, чем прямые методы, но они быстрее, если вам приходится насыщать более одного значения одновременно.
Если вас волнует производительность, вы Действительно хочу сделать подобные вещи в SIMD, где x86 имеет встроенную арифметику насыщения.
Из-за отсутствия насыщающей арифметики в скалярной математике можно получить случаи, когда операции, выполняемые над SIMD с 4 переменными, более более чем в 4 раза быстрее, чем эквивалентный C (и, соответственно, верно для SIMD с 8 переменными):
sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks
Решение с нулевым ответвлением:
uint32_t sadd32(uint32_t a, uint32_t b)
{
uint64_t s = (uint64_t)a+b;
return -(s>>32) | (uint32_t)s;
}
Хороший компилятор оптимизирует это, чтобы избежать выполнения каких-либо реальных 64-битных арифметических операций (s>>32 будет просто флагом переноса, и -(s>>32) является результатом sbb %eax,%eax).
В ассемблере x86 (синтаксис AT&T, a и b в eax и ebx, результат в eax):
add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax
8- и 16-битные версии должны быть очевидны.Подписанная версия может потребовать немного больше работы.
uint32_t saturate_add32(uint32_t a, uint32_t b)
{
uint32_t sum = a + b;
if ((sum < a) || (sum < b))
return ~((uint32_t)0);
else
return sum;
} /* saturate_add32 */
uint16_t saturate_add16(uint16_t a, uint16_t b)
{
uint16_t sum = a + b;
if ((sum < a) || (sum < b))
return ~((uint16_t)0);
else
return sum;
} /* saturate_add16 */
Редактировать: Теперь, когда вы опубликовали свою версию, я не уверен, что моя чище/лучше/эффективнее/продуманнее.
Я не уверен, что это быстрее, чем решение Skizz (всегда профиль), но вот альтернативное решение для сборки без ветвей.Обратите внимание, что для этого требуется инструкция условного перемещения (CMOV), которая, я не уверен, доступна на вашей цели.
uint32_t sadd32(uint32_t a, uint32_t b)
{
__asm
{
movl eax, a
addl eax, b
movl edx, 0xffffffff
cmovc eax, edx
}
}
Текущая реализация, которую мы используем:
#define sadd16(a, b) (uint16_t)( ((uint32_t)(a)+(uint32_t)(b)) > 0xffff ? 0xffff : ((a)+(b)))
#define sadd32(a, b) (uint32_t)( ((uint64_t)(a)+(uint64_t)(b)) > 0xffffffff ? 0xffffffff : ((a)+(b)))
Наилучшая производительность обычно достигается при встроенной сборке (как уже говорили некоторые).
Но для переносимого 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» в качестве упражнения для читателя.;-)
На всякий случай кто-то захочет узнать реализацию без ветвления с использованием 32-битных целых чисел с дополнением до двух.
Предупреждение!Этот код использует неопределенную операцию:«сдвинуть вправо на -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);
}
Это лучшая реализация, известная мне
Я полагаю, что лучший способ для x86 — использовать встроенный ассемблер для проверки флага переполнения после добавления.Что-то вроде:
add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......
Это не очень портативно, но, ИМХО, самый эффективный способ.
Альтернативой решению asm x86 без ветвей является (синтаксис AT&T, a и b в eax и ebx, результат в eax):
add %eax,%ebx
sbb $0,%ebx
Используя C++, вы можете написать более гибкий вариант Ремо.Дрешение:
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.Также обратите внимание, что Целочисленные типы фиксированной ширины может быть недоступно в вашей системе.
//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 бит.оп:редактор, используемый на веб-странице, не позволяет мне публиковать макросы, т. е. он не понимает синтаксис без отступов и т. д.!
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(==, !=) и ?: оператор.Он просто использует побитовые операторы и логические операторы.
Арифметика насыщения не является стандартной для C, но она часто реализуется через встроенные функции компилятора, поэтому самый эффективный способ не будет самым чистым.Вы должны добавить #ifdef блоки, чтобы выбрать правильный путь.Ответ MSalters является самым быстрым для архитектуры x86.Для ARM вам нужно использовать __qadd16 функция (компилятор ARM) _arm_qadd16 (Microsoft Visual Studio) для 16-битной версии и __qadd для 32-битной версии.Они будут автоматически преобразованы в одну инструкцию ARM.
Ссылки:
