다음은 int
오버플로가 발생하면 실패하는 다른 함수를 추가하는 C 함수입니다 .
int safe_add(int *value, int delta) {
if (*value >= 0) {
if (delta > INT_MAX - *value) {
return -1;
}
} else {
if (delta < INT_MIN - *value) {
return -1;
}
}
*value += delta;
return 0;
}
불행히도 GCC 또는 Clang에 의해 잘 최적화되지 않았습니다 .
safe_add(int*, int):
movl (%rdi), %eax
testl %eax, %eax
js .L2
movl $2147483647, %edx
subl %eax, %edx
cmpl %esi, %edx
jl .L6
.L4:
addl %esi, %eax
movl %eax, (%rdi)
xorl %eax, %eax
ret
.L2:
movl $-2147483648, %edx
subl %eax, %edx
cmpl %esi, %edx
jle .L4
.L6:
movl $-1, %eax
ret
이 버전 __builtin_add_overflow()
int safe_add(int *value, int delta) {
int result;
if (__builtin_add_overflow(*value, delta, &result)) {
return -1;
} else {
*value = result;
return 0;
}
}
되어 더 나은 최적화 :
safe_add(int*, int):
xorl %eax, %eax
addl (%rdi), %esi
seto %al
jo .L5
movl %esi, (%rdi)
ret
.L5:
movl $-1, %eax
ret
그러나 GCC 또는 Clang과 패턴 일치하는 내장 기능을 사용하지 않는 방법이 있는지 궁금합니다.
답변
아키텍처의 오버플로 플래그에 액세스 할 수없는 경우 가장 좋은 방법은에서 작업을 수행하는 것입니다 unsigned
. 여기서 우리는 최상위 비트에만 관심이 있다는 점에서 모든 비트 산술을 생각해보십시오. 이는 부호있는 값으로 해석 될 때 부호 비트입니다.
(모든 모듈로 부호 오류, 나는 이것을 철저하게 점검하지는 않았지만 아이디어가 분명하기를 바랍니다)
#include <stdbool.h>
bool overadd(int a[static 1], int b) {
unsigned A = a[0];
unsigned B = b;
// This computation will be done anyhow
unsigned AB = A + B;
// See if the sign bits are equal
unsigned AeB = ~(A^B);
unsigned AuAB = (A^AB);
// The function result according to these should be:
//
// AeB \ AuAB | false | true
//------------+-------+------
// false | false | false
// true | false | true
//
// So the expression to compute from the sign bits is (AeB & AuAB)
// This is INT_MAX
unsigned M = -1U/2;
bool ret = (AeB & AuAB) > M;
if (!ret) a[0] += b;
return ret;
}
원자 버전과 같이 UB가없는 추가 버전을 찾으면 어셈블러에는 분기가 없지만 (접두어 접두어가 있음)
#include <stdbool.h>
#include <stdatomic.h>
bool overadd(_Atomic(int) a[static 1], int b) {
unsigned A = a[0];
atomic_fetch_add_explicit(a, b, memory_order_relaxed);
unsigned B = b;
// This computation will be done anyhow
unsigned AB = A + B;
// See if the sign bits are equal
unsigned AeB = ~(A^B);
unsigned AuAB = (A^AB);
// The function result according to these should be:
//
// AeB \ AuAB | false | true
//------------+-------+------
// false | false | false
// true | false | true
//
// So the expression to compute from the sign bits is (AeB & AuAB)
// This is INT_MAX
unsigned M = -1U/2;
bool ret = (AeB & AuAB) > M;
return ret;
}
따라서 우리가 그러한 수술을 받았지만 훨씬 “완화 된”상황이라면 상황을 더욱 개선 할 수 있습니다.
Take3 : 서명되지 않은 결과에서 서명 된 결과까지 특별한 “캐스트”를 사용하면 이제 분기가 없습니다.
#include <stdbool.h>
#include <stdatomic.h>
bool overadd(int a[static 1], int b) {
unsigned A = a[0];
//atomic_fetch_add_explicit(a, b, memory_order_relaxed);
unsigned B = b;
// This computation will be done anyhow
unsigned AB = A + B;
// See if the sign bits are equal
unsigned AeB = ~(A^B);
unsigned AuAB = (A^AB);
// The function result according to these should be:
//
// AeB \ AuAB | false | true
//------------+-------+------
// false | false | false
// true | false | true
//
// So the expression to compute from the sign bits is (AeB & AuAB)
// This is INT_MAX
unsigned M = -1U/2;
unsigned res = (AeB & AuAB);
signed N = M-1;
N = -N - 1;
a[0] = ((AB > M) ? -(int)(-AB) : ((AB != M) ? (int)AB : N));
return res > M;
}
답변
서명 된 작업의 상황은 서명되지 않은 작업보다 훨씬 나쁘며 서명 된 추가 패턴은 clang 및 더 넓은 유형을 사용할 수있는 경우에만 하나의 패턴 만 보입니다.
int safe_add(int *value, int delta)
{
long long result = (long long)*value + delta;
if (result > INT_MAX || result < INT_MIN) {
return -1;
} else {
*value = result;
return 0;
}
}
clang은 __builtin_add_overflow와 동일한 asm 을 제공합니다.
safe_add: # @safe_add
addl (%rdi), %esi
movl $-1, %eax
jo .LBB1_2
movl %esi, (%rdi)
xorl %eax, %eax
.LBB1_2:
retq
그렇지 않으면 내가 생각할 수있는 가장 간단한 해결책은 이것입니다 (Jens가 사용한 인터페이스 사용).
_Bool overadd(int a[static 1], int b)
{
// compute the unsigned sum
unsigned u = (unsigned)a[0] + b;
// convert it to signed
int sum = u <= -1u / 2 ? (int)u : -1 - (int)(-1 - u);
// see if it overflowed or not
_Bool overflowed = (b > 0) != (sum > a[0]);
// return the results
a[0] = sum;
return overflowed;
}
gcc와 clang은 매우 유사한 asm을 생성 합니다. gcc는 이것을 제공합니다 :
overadd:
movl (%rdi), %ecx
testl %esi, %esi
setg %al
leal (%rcx,%rsi), %edx
cmpl %edx, %ecx
movl %edx, (%rdi)
setl %dl
xorl %edx, %eax
ret
의 합을 계산하려고 unsigned
하므로 unsigned
값이 int
서로 달라 붙지 않고 모든 값을 나타낼 수 있어야 합니다. 쉽게에서 결과를 변환하려면 unsigned
에 int
, 반대도 유용하다. 전반적으로 2의 보수가 가정됩니다.
모든 인기있는 플랫폼 우리가에서 변환 할 수 있습니다 생각 unsigned
에 int
같은 간단한 할당에 의해 int sum = u;
옌스가 언급 한 바와 같이, C2x 표준도 최신 변종은 신호를 인상 할 수 있지만. 다음으로 가장 자연스러운 방법은 다음과 같은 작업을 수행하는 것입니다. *(unsigned *)&sum = u;
패딩의 비 트랩 변형은 부호있는 유형과 부호없는 유형에 따라 다를 수 있습니다. 따라서 위의 예는 어렵습니다. 다행히도 gcc와 clang은이 까다로운 변환을 최적화합니다.
PS 위의 두 변형은 동작이 다르기 때문에 직접 비교할 수 없습니다. 첫 번째 질문은 원래의 질문을 따르며 *value
오버플로의 경우를 방해하지 않습니다 . 두 번째 것은 Jens의 답변을 따르고 항상 첫 번째 매개 변수가 가리키는 변수를 클로버하지만 분기는 없습니다.
답변
내가 올릴 수있는 가장 좋은 버전은 다음과 같습니다.
int safe_add(int *value, int delta) {
long long t = *value + (long long)delta;
if (t != ((int)t))
return -1;
*value = (int) t;
return 0;
}
어떤 생산 :
safe_add(int*, int):
movslq %esi, %rax
movslq (%rdi), %rsi
addq %rax, %rsi
movslq %esi, %rax
cmpq %rsi, %rax
jne .L3
movl %eax, (%rdi)
xorl %eax, %eax
ret
.L3:
movl $-1, %eax
ret
답변
패딩 바이트없이 2의 보수 표현을 가정 (및 주장)하여 컴파일러가 부호 플래그를 사용하도록 할 수 있습니다. 이러한 구현 은 주석으로 주석이 달린 행에서 필요한 동작을 산출 해야 하지만 표준 에서이 요구 사항에 대한 긍정적 인 공식 확인을 찾을 수는 없지만 (아마도 없습니다).
다음 코드는 양의 정수 추가 만 처리하지만 확장 할 수 있습니다.
int safe_add(int* lhs, int rhs) {
_Static_assert(-1 == ~0, "integers are not two's complement");
_Static_assert(
1u << (sizeof(int) * CHAR_BIT - 1) == (unsigned) INT_MIN,
"integers have padding bytes"
);
unsigned value = *lhs;
value += rhs;
if ((int) value < 0) return -1; // impl. def., 6.3.1.3/3
*lhs = value;
return 0;
}
safe_add:
add esi, DWORD PTR [rdi]
js .L3
mov DWORD PTR [rdi], esi
xor eax, eax
ret
.L3:
mov eax, -1
ret