Какой лучший (самый чистый, самый эффективный) способ написать насыщающее дополнение в 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 для add32: значительно лучше, чем любой другой ответ:
add edi, esi
mov eax, -1
cmovae eax, edi
ret
ARMv7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm выводит для add32:
adds r0, r0, r1 @ c, a, b
it cs
movcs r0, #-1 @ conditional-move
bx lr
16bit: по-прежнему не использует 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 у вас уже есть встроенная встроенная арифметика. ARMv5 DSP-расширения могут насыщать регистры любой длины бит. Также на 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 вы также хотите изменить константу signmask, поскольку ARM не может загружать все возможные 32-битные константы за один цикл.
Изменить: Параллельные версии, скорее всего, медленнее, чем прямые методы, но они быстрее, если вам нужно насыщать более одного значения за раз.
Если вы заботитесь о производительности, вы действительно хотите делать подобные вещи в SIMD, где x86 имеет собственную насыщающую арифметику.
Из-за этого отсутствия насыщающей арифметики в скалярной математике можно получить случаи, когда операции, выполняемые на SIM-карте с 4-мя переменными масштабами, более чем в 4 раза быстрее, чем эквивалентный C (и, соответственно, true с 8-переменным SIMD ):
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 asm (синтаксис 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)))
Я полагаю, лучший способ для x86 - использовать встроенный ассемблер, чтобы проверить флаг переполнения после добавления. Что-то вроде:
add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......
Это не очень портативный, но IMHO самый эффективный способ.
Наилучшая производительность, как правило, связана с встроенной сборкой (как уже указывалось ранее).
Но для портативных 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-х целых 32-битных целых чисел.
Внимание! Этот код использует операцию undefined: "сдвиг вправо на -1" и, следовательно, использует свойство Инструкция Intel SAL для Intel Pentium, чтобы замаскировать счетчик операнд до 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);
}
Это лучшая реализация, известная мне
С помощью С++ вы можете написать более гибкий вариант решения 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. Также обратите внимание, что Фиксированные типы целых чисел могут быть недоступны в вашей системе.
Альтернативой бесплатному решению x86 asm для ветвления (синтаксис AT & T, a и b в eax и ebx, приводит к eax):
add %eax,%ebx
sbb $0,%ebx
//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: редактор, используемый на веб-странице, не позволяет мне публиковать макрос, то есть его непонятный синтаксис без указаний и т.д.
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);
}
В этой реализации не используются потоки управления, операторы лагеря (==, !=) и оператор ?:. Он просто использует побитовые операторы и логические операторы.
Арифметика насыщения не является стандартной для C, но она часто реализуется через встроенные функции компилятора, поэтому самый эффективный способ не будет самым чистым. Вы должны добавить блоки #ifdef чтобы выбрать правильный путь. Ответ MSalters является самым быстрым для архитектуры x86. Для ARM вам нужно использовать функцию __qadd16 (компилятор ARM) _arm_qadd16 (Microsoft Visual Studio) для 16-битной версии и __qadd для 32-битной версии. Они будут автоматически переведены в одну инструкцию ARM.
Ссылки: