c++ - 확인 - 오버플 로 처리




C/C++에서 서명 된 오버플로 감지 (8)

64 비트 정수로 변환하고 비슷한 조건을 테스트하는 것이 더 나을 것입니다. 예 :

#include <stdint.h>

...

int64_t sum = (int64_t)lhs + (int64_t)rhs;
if (sum < INT_MIN || sum > INT_MAX) {
    // Overflow occurred!
}
else {
    return sum;
}

광고 확장이 어떻게 작동하는지 자세히 살펴보고 싶지만 정확하다고 생각합니다.

언뜻보기에이 질문은 정수 오버플로를 감지하는 방법 과 중복되는 것처럼 보일 수 있습니다 . 그러나 실제로는 상당히 다릅니다.

C / C ++에서 서명 된 오버플로를 감지하는 것이 실제로 대부분의 사람들이 생각하는 것보다 어렵다는 것을 알았습니다.

가장 확실하고 순진한 방법은 다음과 같습니다.

int add(int lhs, int rhs)
{
 int sum = lhs + rhs;
 if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
  /* an overflow has occurred */
  abort();
 }
 return sum; 
}

이 문제는 C 표준에 따르면 부호있는 정수 오버플로는 정의되지 않은 동작입니다. 즉, 표준에 따르면 서명 된 오버플로가 발생하는 즉시 널 포인터를 역 참조하는 것처럼 프로그램이 유효하지 않습니다. 따라서 정의되지 않은 동작은 발생시킬 수 없으며 위의 사후 조건 확인 예제 에서처럼 사실 이후에 오버플로를 감지하려고 시도합니다.

위의 검사가 많은 컴파일러에서 작동 할 가능성은 있지만, 그다지 중요하지 않습니다. 실제로 부호있는 정수 오버 플로우가 정의되지 않았기 때문에 컴파일러가 부호있는 오버 플로우가 불가능하다고 가정하기 때문에 GCC와 같은 일부 컴파일러는 최적화 플래그가 설정 될 때 위의 확인 을 최적화합니다. 오버플로를 검사하려는 시도가 완전히 중단됩니다.

따라서 오버플로를 검사 할 수있는 또 다른 방법은 다음과 같습니다.

int add(int lhs, int rhs)
{
 if (lhs >= 0 && rhs >= 0) {
  if (INT_MAX - lhs <= rhs) {
   /* overflow has occurred */
   abort();
  }
 }
 else if (lhs < 0 && rhs < 0) {
  if (lhs <= INT_MIN - rhs) {
   /* overflow has occurred */
   abort();
  }
 }

 return lhs + rhs;
}

이러한 추가 작업을 수행하면 오버플로가 발생하지 않도록 미리 확인할 때까지 실제로 두 정수를 함께 추가하지 않기 때문에 더 유망한 것으로 보입니다. 따라서 우리는 정의되지 않은 동작을 발생시키지 않습니다.

그러나이 솔루션은 안타깝게도 초기 솔루션보다 훨씬 효율적이지 않습니다. 추가 연산이 제대로 작동하는지 테스트하기 위해서 빼기 연산을 수행해야하기 때문입니다. 그리고이 (작은) 퍼포먼스에 관심이 없다고해도, 나는 여전히이 솔루션이 적절하다고 확신하지 못합니다. lhs <= INT_MIN - rhs 라는 표현식은 서명 된 오버 플로우가 불가능하다고 생각하여 컴파일러가 최적화 할 수있는 표현식과 똑같습니다.

여기에 더 나은 해결책이 있습니까? 1) 정의되지 않은 동작을 일으키지 않으며, 2) 컴파일러에게 오버 플로우 검사를 최적화 할 수있는 기회를 제공하지 않을 것입니다. 두 피연산자 모두를 부호없는 변수로 캐스팅하고 자신의 2의 보수 연산을 수행하여 검사를 수행하는 방법이 있을지도 모른다고 생각했지만 실제로 그렇게하는 방법을 모르겠습니다.


IMHO, overflow sentitive C ++ 코드를 다루는 가장 동쪽의 방법은 SafeInt<T> 를 사용하는 SafeInt<T> 입니다. 이것은 여기에 원하는 안전 보장을 제공하는 코드 플렉스에서 호스팅되는 크로스 플랫폼 C ++ 템플릿입니다.

나는 일반적인 수치 연산과 같은 많은 사용 패턴을 제공하고 예외를 통해 초과 및 미만의 흐름을 표현하므로 사용하기가 매우 쉽습니다.


가장 빠른 방법은 내장 GCC를 사용하는 것입니다.

int add(int lhs, int rhs) {
    int sum;
    if (__builtin_add_overflow(lhs, rhs, &sum))
        abort();
    return sum;
}

x86에서 GCC는 이것을 다음과 같이 컴파일합니다.

    mov %edi, %eax
    add %esi, %eax
    jo call_abort 
    ret
call_abort:
    call abort

프로세서의 내장 오버 플로우 감지 기능을 사용합니다.

GCC 내장 함수를 사용하는 것이 좋지 않다면 가장 빠른 방법은 부호 비트에 비트 연산을 사용하는 것입니다. 다음과 같은 경우에도 부호있는 오버플로가 발생합니다.

  • 두 피연산자는 같은 부호를 가지며
  • 결과에는 피연산자와 다른 부호가 있습니다.

~(lhs ^ rhs) 의 부호 비트는 피연산자가 동일한 부호를 갖는 경우 켜지고 결과가 피연산자와 다른 부호를 갖는 경우 lhs ^ sum 의 부호 비트가 켜집니다. 그래서 당신은 정의되지 않은 행동을 피하기 위해 부호가없는 형태로 덧셈을 할 수 있고 ~(lhs ^ rhs) & (lhs ^ sum) 의 부호 비트를 사용할 수 있습니다 :

int add(int lhs, int rhs) {
    unsigned sum = (unsigned) lhs + (unsigned) rhs;
    if ((~(lhs ^ rhs) & (lhs ^ sum)) & 0x80000000)
        abort();
    return (int) sum;
}

이것은 다음과 같이 컴파일됩니다.

    lea (%rsi,%rdi), %eax
    xor %edi, %esi
    not %esi
    xor %eax, %edi
    test %edi, %esi
    js call_abort
    ret
call_abort:
    call abort

이는 gcc를 사용하여 32 비트 머신에서 64 비트 유형으로 변환하는 것보다 훨씬 빠릅니다.

    push %ebx
    mov 12(%esp), %ecx
    mov 8(%esp), %eax
    mov %ecx, %ebx
    sar $31, %ebx
    clt
    add %ecx, %eax
    adc %ebx, %edx
    mov %eax, %ecx
    add $-2147483648, %ecx
    mov %edx, %ebx
    adc $0, %ebx
    cmp $0, %ebx
    ja call_abort
    pop %ebx
    ret
call_abort:
    call abort

나는 이것이 작동한다고 생각한다.

int add(int lhs, int rhs) {
   volatile int sum = lhs + rhs;
   if (lhs != (sum - rhs) ) {
       /* overflow */
       //errno = ERANGE;
       abort();
   }
   return sum;
}

휘발성을 사용하면 sum 가 더하기와 빼기 사이에서 변경되었을 수 있으므로 컴파일러가 테스트를 최적화하지 못하게합니다.

x86_64 용 gcc 4.4.3을 사용하면이 코드의 어셈블리는 더하기, 빼기 및 테스트를 수행하지만 스택에있는 모든 내용과 불필요한 스택 연산을 저장합니다. 나는 register volatile int sum = 시도했지만 어셈블리는 동일했다.

int sum = (휘발성 또는 레지스터 없음) 버전의 경우 함수는 테스트를 수행하지 않고 하나의 lea 명령어 ( lea 는 Load Effective Address이며 플래그 레지스터를 건드리지 않고 추가 작업을 수행하는 데 자주 사용됩니다)를 사용하여 추가를 수행했습니다.

귀하의 버전은 코드가 크고 더 많은 점프가 있지만 어떤 것이 더 좋을지는 잘 모릅니다.


분명한 해결책은 unsigned로 변환하여 잘 정의 된 부호없는 오버플로 비헤이비어를 얻는 것입니다.

int add(int lhs, int rhs) 
{ 
   int sum = (unsigned)lhs + (unsigned)rhs; 
   if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) { 
      /* an overflow has occurred */ 
      abort(); 
   } 
   return sum;  
} 

이렇게하면 정의되지 않은 부호있는 오버플로 비헤이비어가 서명 된 변수와 부호없는 변수 사이의 범위를 벗어난 값에 대한 구현 정의 변환으로 바뀌므로 컴파일러의 설명서를 확인하여 정확히 어떤 결과가 발생 하는지를 확인해야하지만 최소한 잘 정의해야합니다. 지난 20 년 동안 구축 된 거의 모든 머신과 C 컴파일러 인 변환에 대한 신호를 발생시키지 않는 2 중 보완 머신에서 올바른 작업을 수행해야합니다.


뺄셈을 사용한 접근 방식은 정확하고 잘 정의되어 있습니다. 컴파일러는이를 최적화 할 수 없습니다.

다른 올바른 방법은 더 큰 정수 유형을 사용할 수있는 경우 더 큰 유형의 산술 연산을 수행 한 다음 결과를 다시 작은 유형으로 변환하는 것입니다

int sum(int a, int b)
{
    long long c;
    assert(LLONG_MAX>INT_MAX);
    c = (long long)a + b;
    if (c < INT_MIN || c > INT_MAX) abort();
    return c;
}

좋은 컴파일러는 전체 추가 및 if 문을 int 크기의 덧셈과 단일 조건부 점프 온 오버플로로 변환해야하며 실제로 더 큰 덧셈을 수행하지 않아야합니다.

편집 : Stephen이 지적했듯이, 나는 (제법 좋지 않은) 컴파일러 인 gcc가 정상적인 asm을 생성하는 데 어려움을 겪고있다. 그것이 생성하는 코드는 대단히 느리지 만 확실히 차선책은 아닙니다. gcc가 옳은 일을 할 수있게 해주는이 코드의 변형을 아는 사람이라면, 나는 그 코드를보고 싶을 것이다.


어때?

int sum(int n1, int n2)
{
  int result;
  if (n1 >= 0)
  {
    result = (n1 - INT_MAX)+n2; /* Can't overflow */
    if (result > 0) return INT_MAX; else return (result + INT_MAX);
  }
  else
  {
    result = (n1 - INT_MIN)+n2; /* Can't overflow */
    if (0 > result) return INT_MIN; else return (result + INT_MIN);
  }
}

내 생각에 합법적 인 INT_MININT_MAX (대칭 또는 INT_MIN 작동해야한다고 생각합니다. 클립과 같은 기능이지만 다른 동작을 얻는 방법은 분명해야합니다).






integer-overflow