C에서 서명되지 않은 포화 첨가를 수행하는 방법?

Question

C에서 포화 첨가를 작성하는 가장 (가장 깨끗하고 효율적인) 방법은 무엇입니까?

함수 또는 매크로는 서명되지 않은 두 개의 입력 (16 비트 및 32 비트 버전이 필요)을 추가하고 합계가 오버플로 된 경우 모든 비트 1 (0xffff 또는 0xffffffff)을 반환해야합니다.

Target은 x86이고 GCC (4.1.2)와 Visual Studio를 사용하는 ARM입니다 (시뮬레이션 만 있으므로 폴백 구현은 괜찮습니다).

Answer 1

당신은 아마 휴대용을 원할 것입니다 C 여기에서 코드는 컴파일러가 적절한 암 어셈블리로 바뀝니다. 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의 부호없는 포화 ADD 명령을 사용하지 않습니다 (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  @

Answer 2

평범한 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;} 

거의 매크로이드이며 의미를 직접 전달합니다.

Answer 3

조건부 점프없이 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
}

Answer 4

팔에 이미 포화 된 산술 내장이있을 수 있습니다. ARMV5 DSP- 확장은 레지스터를 비트 길이로 포화시킬 수 있습니다. 또한 팔 포화 상태는 일반적으로 대부분의 지시 사항을 조건부로 축하 할 수 있기 때문에 저렴합니다.

ARMV6은 포화 된 첨가, 뺄셈 및 기타 모든 것들을 32 비트 및 포장 된 숫자로 가지고 있습니다.

X86에서는 MMX 또는 SSE를 통해 포화 산술을받습니다.

이 모든 것이 어셈블러가 필요하므로 요청한 것이 아닙니다.

포화 산술을 수행 할 C- 트릭도 있습니다. 이 작은 코드는 4 바이트의 dword에 포화 된 추가 기능을합니다. 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;
}

Signmask 상수를 변경하고 바닥의 변속을 다음과 같이 변경하여 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 비트 상수를 모두로드 할 수 없기 때문에 SignMask 상수를 변경하려고합니다.

편집하다: 병렬 버전은 간단한 방법보다 느리게 가능하지만 한 번에 둘 이상의 값을 포화시켜야한다면 더 빠릅니다.

Answer 5

성능에 관심이 있다면, 당신은 당신입니다 진짜 x86에는 기본 포화 산술이있는 Simd에서 이런 종류의 작업을 원합니다.

스칼라 수학에서 포화 산술이 부족하기 때문에 4 변수의 SIMD에서 작업이 수행되는 경우를 얻을 수 있습니다. 더 등가 C보다 4 배 더 빠릅니다 (그리고 8- 변수 전역의 SIMD와 함께 해당) :

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

Answer 6

제로 브랜치 솔루션 :

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 비트 버전은 분명해야합니다. 서명 된 버전에는 좀 더 많은 작업이 필요할 수 있습니다.

Answer 7

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 */

편집하다: 이제 버전을 게시 했으므로 내 것이 더 깨끗하고 더 나은/더 효율적/더 스터드인지 확실하지 않습니다.

Answer 8

이것이 스위이즈 솔루션보다 빠른지 확실하지 않지만 (항상 프로필) 대체되지 않은 조립 솔루션이 있습니다. 이를 위해서는 조건부 이동 (CMOV) 명령이 필요하며 대상에서 사용할 수 없습니다.

uint32_t sadd32(uint32_t a, uint32_t b)
{
    __asm
    {
        movl eax, a
        addl eax, b
        movl edx, 0xffffffff
        cmovc eax, edx
    }
}

Answer 9

우리가 사용하고있는 현재 구현은 다음과 같습니다.

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

Answer 10

최상의 성능은 일반적으로 인라인 어셈블리와 관련이 있습니다 (일부는 이미 언급했듯이).

그러나 휴대용 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)))

나는 독자의 운동으로 '부호없는 길다'와 '서명되지 않은 장거리'버전을 남겨 둡니다. ;-)

Answer 11

누군가가 2의 보완 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);
 }

그것은 나에게 알려진 최고의 구현입니다

Answer 12

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

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

그것은 매우 휴대 성이 아니지만 가장 효율적인 방법입니다.

Answer 13

브랜치 프리 X86 ASM 솔루션의 대안은 (AT & T 구문, A 및 B의 EAX 및 EBX, EAX를 초래 함) :

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

Answer 14

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. 또한에 유의하십시오 고정 너비 정수 유형 시스템에서 사용할 수 없었을 수 있습니다.

Answer 15

//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;\
}\
})

나는 빠른 테스트를했고 작동하는 것 같지만 아직 광범위하게 강타하지는 않았다! 이것은 서명 된 32 비트와 함께 작동합니다. OP : 웹 페이지에 사용 된 편집기는 매크로를 게시 할 수 없습니다.

Answer 16

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

이 구현은 Control Flows, Campare 운영자를 사용하지 않습니다 (==, !=) 그리고 ?: 운영자. 그것은 단지 BitWise 연산자와 논리 연산자 만 사용합니다.

Answer 17

포화 산술은 C의 표준이 아니지만 종종 컴파일러 인스틱스를 통해 구현되므로 가장 효율적인 방법은 가장 깨끗하지 않습니다. 추가해야합니다 #ifdef 올바른 방법을 선택하기 위해 블록. MSALTERS의 답변은 X86 아키텍처에서 가장 빠릅니다. 팔의 경우 사용해야합니다 __qadd16 기능 (ARM 컴파일러) _arm_qadd16 (Microsoft Visual Studio) 16 비트 버전 및 __qadd 32 비트 버전의 경우. 그들은 자동으로 하나의 팔 명령으로 번역됩니다.

연결:

• __qadd16
• _arm_qadd16
• __qadd