C/C++에서 서명된 오버플로를 감지하는 중
이 질문은 얼핏 정수 오버플로를 검출하는 방법의 복제처럼 보일 수 있지만 실제로는 크게 다릅니다.
부호 없는 정수 오버플로를 검출하는 것은 매우 간단한 일이지만, 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 표준에 따르면 서명된 정수 오버플로는 정의되지 않은 동작이라는 것입니다.즉, 표준에 따르면 서명된 오버플로를 발생시키는 즉시 프로그램은 Null 포인터를 참조한 것처럼 비활성화됩니다.따라서 위의 사후 조건 체크 예시와 같이 정의되지 않은 동작을 유발하고 그 후 오버플로를 검출할 수 없습니다.
위의 체크는 많은 컴파일러에서 동작할 가능성이 높지만 신뢰할 수 없습니다.실제로 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) 컴파일러에 어웨이 오버플로우 체크를 최적화할 수 있는 기회를 제공하지 않는 것이 보증됩니다.두 피연산자를 모두 부호 없이 만들고, 두 피연산자를 둘로 나눠서 체크하는 방법이 있을 것 같은데, 어떻게 해야 할지 잘 모르겠어요.
아니요, 두 번째 코드는 정확하지 않지만, 근접해 있습니다.
int half = INT_MAX/2;
int half1 = half + 1;
가 되다INT_MAX ( . )INT_MAX는 항상 홀수입니다).이것은 유효한 입력입니다.에는 '일상'이 있을 이다.INT_MAX - half == half1 긍정입니다잘못된 긍정.
는, 「포토」를 할 수 있습니다.<<=두 가지 수표로요
하지만 당신의 코드도 최적이 아닙니다.다음과 같습니다.
int add(int lhs, int rhs)
{
if (lhs >= 0) {
if (INT_MAX - lhs < rhs) {
/* would overflow */
abort();
}
}
else {
if (rhs < INT_MIN - lhs) {
/* would overflow */
abort();
}
}
return lhs + rhs;
}
으로 '부호적'을 붙여야 돼요.lhs부등식의 양쪽에서 계산하면 결과가 범위를 벗어난다는 정확한 산술 조건을 얻을 수 있습니다.
가능한 가장 빠른 방법은 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결과가 오퍼랜드와 다른 부호를 갖는 경우 on이 됩니다.않은 동작을 위해 한할 수 .~(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
32비트 머신(gcc 탑재)의 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
gcc 케이스의 경우 gcc 5.0 릴리즈 노트에서 다음 정보를 확인할 수 있습니다.__builtin_add_overflow오플로 플크오 :
오버플로우 체크를 수반하는 산술용 빌트인 함수 세트 __builtin_add_overflow, __builtin_sub_overflow 및 __builtin_mul_overflow가 추가되었습니다.또한 clang과의 호환성도 있습니다.이러한 빌트인에는 2개의 정수형 인수(같은 타입일 필요는 없습니다)가 있습니다.인수는 무한정 정밀도 부호형까지 확장됩니다.+, - 또는 *는 이들 인수에 대해 실행되며 결과는 마지막 인수가 가리키는 정수형 변수에 저장됩니다.저장된 값이 무한 정밀도 결과와 같으면 내장 함수가 false를 반환하고 그렇지 않으면 true를 반환합니다.결과를 유지하는 정수 변수의 유형은 처음 두 개의 인수 유형과 다를 수 있습니다.
예를 들어 다음과 같습니다.
__builtin_add_overflow( rhs, lhs, &result )
gcc 문서에서 Overflow Checking을 통한 산술 수행을 위한 빌트인 함수에서 다음을 확인할 수 있습니다.
[...이러한 기본 제공 함수는 모든 인수 값에 대해 완전히 정의된 동작을 가집니다.
Clang은 C에서 빠르고 쉽게 표현할 수 있는 방법으로 보안 크리티컬 애플리케이션에 대해 체크된 계산을 구현하는 일련의 빌트인을 제공합니다.
이 경우 기본 제공은 다음과 같습니다.
__builtin_sadd_overflow( rhs, lhs, &result )
뺄셈 접근법은 정확하고 명확합니다.컴파일러는 최적화할 수 없습니다.
더 큰 정수 유형을 사용할 수 있는 경우 다른 올바른 방법은 큰 유형으로 연산을 수행한 다음 다시 변환할 때 결과가 더 작은 유형에 맞는지 확인하는 것입니다.
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가 올바른 작업을 수행할 수 있는 변종을 아는 사람이 있다면 보고 싶습니다.
그 문제라는 것입니다.lhs + rhs2개의 의향이 수 있습니다.를 들어, 여러분이 함수가 있다고 .to_int_modularunsigned로로 합니다.int변환의 역수가 되는 것이 보증되는 방법으로int로로 합니다.unsigned(실행 는 아래를 해 주세요
용장 하는 .lhs >= 0 ★★★★★★★★★★★★★★★★★」lhs < 0후가 .
int add(int lhs, int rhs)
{
int sum = to_int_modular((unsigned)lhs + rhs);
if (lhs >= 0) {
if (sum < rhs)
abort();
} else {
if (sum > rhs)
abort();
}
return sum;
}
유사한 구조를 가지지만 산술 연산이 적게 필요하기 때문에 현재 상위 응답보다 성능이 우수합니다.
( )의 재편성if필수는 아니지만 Godbolt 테스트에서는 ICC와 MSVC가 자체적으로 중복 테스트를 배제하지만 GCC와 Clang은 그렇지 않습니다.)
결과를 더 넓은 크기로 계산한 다음 한계 검사를 수행하는 한 가지 방법은 다음과 같습니다.
long long sum = (long long)lhs + rhs;
if ((int)sum != sum)
abort();
...동작이 오버플로우에서 정의되지 않은 것을 제외합니다.그러나 동일한 도우미 기능을 사용하여 이 문제를 해결할 수 있습니다.
if (to_int_modular(sum) != sum)
이는 오버플로 플래그 테스트에 최적화하기에 충분히 스마트하지 않은 컴파일러에서 현재 승인된 답변을 능가할 수 있습니다.
유감스럽게도 테스트(godbolt에 대한 육안 검사) 결과, GCC, ICC 및 MSVC는 승인된 답변의 코드보다 위의 코드를 사용하는 것이 더 낫지만 Clang은 승인된 답변의 코드를 사용하는 것이 더 낫습니다.여느 때처럼 쉬운 일은 없다.
이 접근방식은 다음과 같은 아키텍처에서만 사용할 수 있습니다.int ★★★★★★★★★★★★★★★★★」unsigned마찬가지로 대규모이며, 아래의 구체적인 구현도 그 2개의 보완 여부에 따라 달라집니다.사양에 맞지 않는 기계는 거의 없습니다만, 어쨌든 확인해 보겠습니다.
static_assert(INT_MIN + INT_MAX == -1 && UINT_MAX + INT_MIN == INT_MAX);
「 」를 실장하기 to_int_modular하고 있다
inline int to_int_modular(unsigned u) {
int i;
memcpy(&i, &u, sizeof(i));
return i;
}
메이저 데및는 MSVC ICC에 대한 합니다.memcpy이 기능을 많이 사용하면 속도가 느려질 수 있습니다., 이 은, 「이러다」의 한 것에 .unsigned ★★★★★★★★★★★★★★★★★」int아마 기준에 의해 보장되지 않을 것입니다.
또 다른 방법은 다음과 같습니다.
inline int to_int_modular(unsigned u) {
return u <= INT_MAX ? (int)u : (int)(u - INT_MIN) + INT_MIN;
}
모든 주요 x64 컴파일러는 ICC를 제외하고 아무것도 최적화하지 않습니다. ICC는 ICC를 완전히 엉망으로 만들고 제가 생각할 수 있는 모든 변형을 만듭니다.ICX는 정상적으로 동작하고 있으며, 인텔은 ICC를 포기하고 ICX로 이행하고 있기 때문에, 이 문제는 자동적으로 수정될 가능성이 있습니다.
명백한 해결책은 서명되지 않은 상태로 변환하여 제대로 정의된 서명되지 않은 오버플로 동작을 얻는 것입니다.
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;
}
이렇게 하면 정의되지 않은 서명 오버플로 동작이 서명된 값과 서명되지 않은 값 사이의 범위를 벗어난 값의 구현 정의 변환으로 대체됩니다.따라서 어떤 일이 일어날지 정확히 알기 위해서는 컴파일러의 문서를 확인해야 합니다.그러나 적어도 정의되어 있어야 하며, 그렇지 않은 2개의 보완 머신에서 올바른 작업을 수행해야 합니다.지난 20년간 만들어진 거의 모든 기계와 C 컴파일러의 변환 신호입니다.
인라인 어셈블러를 사용하면 오버플로 플래그를 확인할 수 있습니다.또 다른 방법은 안전한 데이터형을 사용할 수 있다는 것입니다.Integer Security에 대한 이 문서를 읽을 것을 권장합니다.
++ 코드를 에 있는 은 IMHO를 사용하는 입니다.SafeInt<T>코드 플렉스에서 호스트되는 크로스 플랫폼 C++ 템플릿으로, 여기서 원하는 안전 보장을 제공합니다.
일반적인 수치 연산과 동일한 사용 패턴을 다수 제공하고 예외를 통해 오버플로우를 표현하기 때문에 직관적으로 사용할 수 있습니다.
가장 간단한 검사는 오퍼랜드와 결과의 징후를 확인하는 것입니다.
합계를 조사합니다.양쪽 오퍼랜드의 부호가 같은 경우에만 오버플로는 + 또는 - 양방향으로 발생할 수 있습니다.결과 부호가 오퍼랜드의 부호와 같지 않을 때 오버플로가 발생합니다.
따라서 다음과 같은 체크로 충분합니다.
int a, b, sum;
sum = a + b;
if (((a ^ ~b) & (a ^ sum)) & 0x80000000)
detect_oveflow();
한 바와 같이 Nils입니다.if★★★★
((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)
그리고 언제부터 지시가
add eax, ebx
정의되지 않은 행동으로 이어지나요?인텔 x86 명령어 세트 차이에는 그런 것이 없습니다.
그럼 어떻게 해?
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_MIN ★★★★★★★★★★★★★★★★★」INT_MAX(대칭 여부에 관계없이) 표시된 클립과 같은 기능을 하지만 다른 동작을 얻는 방법은 분명해야 합니다.
이 방법이 효과가 있다고 생각합니다.
int add(int lhs, int rhs) {
volatile int sum = lhs + rhs;
if (lhs != (sum - rhs) ) {
/* overflow */
//errno = ERANGE;
abort();
}
return sum;
}
는 volatile이 volatile이라고 하기 때문에 할 수 .sum덧셈과 뺄셈 사이에서 변화했을 수 있습니다.
4. x86_64를 하면 이 및단, 이 조작의 모든 합니다.gcc 4.4.3 for x86_64 는 이 코드입니다.는 심지어 i i i력 tried tried tried iregister volatile int sum =립은은똑똑똑똑똑
만 있는 경우int sum =( register 없음) 1개('volatile' 또는 'register만 lea명령)lea는 유효 주소 로드이며, 플래그 레지스터를 터치하지 않고 추가하는 데 자주 사용됩니다).
당신의 버전은 더 큰 코드이고 더 많은 점프를 가지고 있지만, 어느 것이 더 좋을지 모르겠습니다.
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;
}
여기서 간판 확장자가 어떻게 작동하는지 자세히 살펴보는 것이 좋을 것 같습니다만, 저는 그것이 옳다고 생각합니다.
의 2를 long는 ,, 터 the the 、 터 、 터 、 터 、 터 、 터 、 the 、 。long 것과 것으로 을 매기다int부분(또는 안으로)short의 경우의 long와 같은 사이즈를 가지다int
static_assert(sizeof(long) == 2*sizeof(int), "");
long a, b;
int ai[2] = {int(a), int(a >> (8*sizeof(int)))};
int bi[2] = {int(b), int(b >> (8*sizeof(int))});
... use the 'long' type to add the elements of 'ai' and 'bi'
특정 CPU를 대상으로 하는 경우 인라인어셈블리를 사용하는 것이 가장 빠른 방법입니다.
long a, b;
bool overflow;
#ifdef __amd64__
asm (
"addq %2, %0; seto %1"
: "+r" (a), "=ro" (overflow)
: "ro" (b)
);
#else
#error "unsupported CPU"
#endif
if(overflow) ...
// The result is stored in variable 'a'
언급URL : https://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c
'programing' 카테고리의 다른 글
| 세트에서 랜덤 요소 선택 (0) | 2022.07.16 |
|---|---|
| pthreads의 조건 변수 함수에 뮤텍스가 필요한 이유는 무엇입니까? (0) | 2022.07.16 |
| 세그멘테이션 장애의 일반적인 이유의 최종 목록 (0) | 2022.07.16 |
| C에서 scanf가 버퍼 오버플로를 발생시키지 않도록 하려면 어떻게 해야 합니까? (0) | 2022.07.16 |
| 이 플로트 제곱근 근사치는 어떻게 작동합니까? (0) | 2022.07.16 |