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

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

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

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

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

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

Ответы [ 17 ]

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

В простой 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;}

, который почти макросизирован и прямо передает значение

18 голосов
/ 03 октября 2008

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

    add     edi, esi
    mov     eax, -1
    cmovae  eax, edi
    ret

ARMv7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm вывод для сложений32 : 

    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  @
18 голосов
/ 23 сентября 2008

В 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
}
11 голосов
/ 23 сентября 2008

В 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-битные константы за один цикл.

Редактировать: Скорее всего, параллельные версии медленнее, чем прямые методы, но они быстрее, если вам нужно насыщать более одного значения за раз.

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

Если вы заботитесь о производительности, вы действительно хотите делать подобные вещи в SIMD, где x86 имеет собственную насыщающую арифметику.

Из-за отсутствия насыщающей арифметики в скалярной математике можно получить случаи, когда операции, выполняемые на SIMD с 4 переменными, в больше в 4 раза быстрее, чем эквивалентный C (и, соответственно, справедливо для SIMD шириной 8 переменных): 

sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks
9 голосов
/ 07 августа 2010

Решение с нулевой ветвью: 

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

7 голосов
/ 23 сентября 2008 
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 */

Редактировать: Теперь, когда вы разместили свою версию, я не уверен, что у меня она чище / лучше / эффективнее / более понятна.

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

Я не уверен, что это быстрее, чем решение Skizz (всегда в профиле), но вот альтернативное решение для сборки без веток. Обратите внимание, что для этого требуется инструкция условного перемещения (CMOV), которая, я не уверен, доступна для вашей цели. 


uint32_t sadd32(uint32_t a, uint32_t b)
{
    __asm
    {
        movl eax, a
        addl eax, b
        movl edx, 0xffffffff
        cmovc eax, edx
    }
}
2 голосов
/ 23 сентября 2008

Текущая реализация, которую мы используем: 

#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)))
2 голосов
/ 23 сентября 2008

Полагаю, лучший способ для x86 - использовать встроенный ассемблер для проверки флага переполнения после добавления. Что-то вроде: 

add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......

Это не очень портативный, но ИМХО самый эффективный способ.

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