C에 부호 없는 포화 덧셈을 어떻게 하나요?

C에 부호 없는 포화 덧셈을 어떻게 하나요?

포화 덧셈을 C에 쓰는 가장 좋은 방법(가장 깨끗하고 효율적인 방법)은 무엇입니까?

함수 또는 매크로는 부호 없는 2개의 입력(16비트 버전과 32비트 버전 모두 필요)을 추가하고 합계가 오버플로우되면 all-bits-one(0xFFFF 또는 0xFFFFFF)을 반환해야 합니다.

대상은 gcc(4.1.2)와 Visual Studio를 사용하는 x86 및 ARM입니다(시뮬레이션 전용이므로 폴백 구현은 문제 없습니다).

컴파일러가 적절한 ARM 어셈블리로 변환되는 휴대용 C 코드가 필요할 수 있습니다.ARM에는 조건부 이동이 있으며, 이러한 이동은 오버플로에 따라 달라질 수 있습니다.알고리즘은, 오버플로우가 검출되었을 경우는, 행선지를 add 및 조건부로 unsigned(-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;
}

이는 오버플로를 검출하기 위해 다른 계산에 의존하지 않고 오버플로를 수정한다는 점에서 다른 알고리즘과 다릅니다.

adds32에 대한 x86-64 clang 3.7 -O3 출력: 다른 응답보다 훨씬 우수합니다.

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

ARMv7: adds32의 출력:

adds    r0, r0, r1      @ c, a, b
it      cs
movcs   r0, #-1         @ conditional-move
bx      lr

16bit:아직도 ARM의unsigned-saturating 추가 명령을 사용하지 않는다면(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  @

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 사업자(이 실장에서는 제어 플로우가 사용되지않습니다.campare 연산자(를 사용하지 않습니다.==,!=1개)와?:교환입니다.교환입니다. 그냥 비트사와 논리 연산자를 사용한다.비트 연산자와 논리 연산자를 사용할 뿐입니다.

현재 사용하고 있는 실장은 다음과 같습니다.

#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)))

제로 브런치 솔루션:

uint32_t sadd32(uint32_t a, uint32_t b)
{
    uint64_t s = (uint64_t)a+b;
    return -(s>>32) | (uint32_t)s;
}

좋은 컴파일러 실제 64비트 연산을 하지 않기(뛰어난 컴파일러는 64비트 계산을하지 않도록 최적화합니다 실제 이 최적화할 것이다.s>>32까 단지가 되어 깃발과 단지운반용 깃발일 뿐이고.-(s>>32)의 결과이다의 결과sbb %eax,%eax).

x86asm(AT&T구문, x86asm(AT&T구문)에서는에서.a ★★★★★★★★★★★★★★★★★」b에에eax ★★★★★★★★★★★★★★★★★」ebx결과에, 결과:eax):):

add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax

8비트 및 16비트 버전은 명확합니다.서명된 버전은 좀 더 많은 작업이 필요할 수 있습니다.

branch free x86 asm 솔루션의 대체 방법은 다음과 같습니다(AT&T 구문, eax 및 ebx의 a와 b는 eax가 됩니다).

add %eax,%ebx
sbb $0,%ebx

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-tricks도 있다.이 작은 코드는 dword의 4바이트에 포화상태로 추가됩니다.예를 들어 캐리 오버플로가 없는 숫자를 추가하는 등 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은 가능한 32비트 상수를 한 사이클에 모두 로드할 수 없기 때문에 ARM에서도 신호 마스크 상수를 변경할 수 있습니다.

편집: 병행버전은 스트레이트 방식보다 느릴 가능성이 높지만 여러 값을 동시에 포화시켜야 하는 경우에는 더 빠릅니다.

퍼포먼스를 중시하는 경우는, 이러한 작업을 SIMD 로 실시할 필요가 있습니다.이 SIMD 에서는 x86 의 네이티브 포화 산술이 사용됩니다.

스칼라 산술에서는 이러한 포화 산술이 없기 때문에 4변수 폭의 SIMD에서 연산이 동등한 C보다 4배 이상 빠른 경우(8변수 폭의 SIMD에서 해당)를 얻을 수 있습니다.

sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks

x86의 가장 좋은 방법은 인라인 어셈블러를 사용하여 추가 후 오버플로 플래그를 확인하는 것입니다.예를 들어 다음과 같습니다.

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

휴대성은 떨어지지만 IMHO가 가장 효율적입니다.

플레인 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;
}

거의 거시적이고 직접적으로 의미를 전달하고 있습니다.

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
    }
}

2의 보완 32비트 정수를 사용하여 분기하지 않고 구현 상태를 알고 싶은 경우를 대비합니다.

경고!이 코드는 정의되지 않은 연산 "shift right by -1"을 사용하기 때문에 인텔 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);
 }

지금까지 알려진 것 중 가장 뛰어난 구현입니다.

최고의 퍼포먼스는 보통 인라인어셈블리를 사용합니다(이미 설명한 것처럼).

그러나 휴대용 C의 경우, 이러한 기능은 비교가 1개만 수반되며 타입 캐스팅은 포함되지 않습니다(따라서 최적이라고 생각합니다).

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' 버전은 독자에게 연습용으로 남겨둡니다. ;-)

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또한 시스템에서 고정 너비 정수 유형을 사용할 수 없는 경우도 있습니다.

//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 : 웹페이지에서 사용하는 에디터는 매크로를 투고할 수 없습니다.즉, 비의도 구문 등을 이해하지 못합니다!

포화도 산술은 C에 표준이 아니지만 컴파일러 내장 함수를 통해 구현되는 경우가 많기 때문에 가장 효율적인 방법은 가장 깨끗한 방법이 아닙니다.를 추가해야 합니다.#ifdef적절한 방법을 선택할 수 있습니다.MSalters의 답변은 x86 아키텍처에서 가장 빠릅니다.ARM의 경우,__qadd16기능(ARM 컴파일러)_arm_qadd16(Microsoft Visual Studio) 16비트 버전 및__qadd32비트 버전의 경우.1개의 ARM 명령으로 자동 변환됩니다.

링크:

• __qadd16
• _arm_qadd16
• __qadd

위에 언급되지 않은 솔루션을 추가하겠습니다.

인텔 x86에는 ADC 명령이 있습니다.이 함수는 _addcarry_u32() 고유 함수로 나타납니다.ARM의 경우 유사한 내성이 있어야 합니다.

이를 통해 매우 빠르게 구현할 수 있습니다.uint32_t인텔 x86에 대한 포화 추가:

온라인으로 시험해 보세요!

#include <stdint.h>
#include <immintrin.h>

uint32_t add_sat_u32(uint32_t a, uint32_t b) {
    uint32_t r, carry = _addcarry_u32(0, a, b, &r);
    return r | (-carry);
}

인텔 x86 MMX 포화 추가 명령을 사용하여uint16_t바리안트:

온라인으로 시험해 보세요!

#include <stdint.h>
#include <immintrin.h>

uint16_t add_sat_u16(uint16_t a, uint16_t b) {
    return _mm_cvtsi64_si32(_mm_adds_pu16(
        _mm_cvtsi32_si64(a),
        _mm_cvtsi32_si64(b)
    ));
}

ARM 솔루션은 다른 답변의 일반 솔루션에 의해 구현될 수 있기 때문에 언급하지 않습니다.

언급URL : https://stackoverflow.com/questions/121240/how-to-do-unsigned-saturating-addition-in-c