부호없는 정수 곱하기 오버플로를 어떻게 감지합니까?
a b = c 의 모든 솔루션을 찾기 위해 C ++로 프로그램을 작성했습니다 . 여기서 a , b 및 c는 함께 모든 숫자 0-9를 정확히 한 번 사용합니다. 프로그램의 값 이상 반복 및 B를 , 그리고 숫자 카운팅 루틴을 실행 한 각 시간 , B 및 B 숫자 조건이 만족되었는지를 확인하기 위해.
그러나, 스퓨리어스 솔루션을 생성 할 수 b는 정수 오버플로 제한. 나는 다음과 같은 코드를 사용하여 이것을 확인했습니다.
unsigned long b, c, c_test;
...
c_test=c*b; // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test; // No overflow
오버플로를 테스트하는 더 좋은 방법이 있습니까? 일부 칩에는 오버플로가 발생할 때 설정되는 내부 플래그가 있다는 것을 알고 있지만 C 또는 C ++를 통해 액세스하는 것을 본 적이 없습니다.
조심하십시오 서명 int 오버 플로우가 C와 C에서 정의되지 않은 동작이 ++입니다 , 그래서 당신은 실제로 발생하지 않고이를 감지해야합니다. 추가하기 전에 서명 된 int 오버플로에 대해서는 C / C ++에서 서명 된 오버플로 감지를 참조하세요 .
부호없는 정수를 사용하고 있습니다. 정의 에 따라 C (C ++에 대해 알지 못함)에서는 부호없는 산술이 오버플로되지 않습니다. 따라서 적어도 C의 경우 요점은 논쟁의 여지가 있습니다. :)
부호있는 정수를 사용하면 오버플로 가 발생 하면 정의되지 않은 동작 이 발생하고 프로그램에서 모든 작업을 수행 할 수 있습니다 (예 : 렌더 테스트 미결).
#include <limits.h>
int a = <something>;
int x = <something>;
a += x; /* UB */
if (a < 0) { /* unreliable test */
/* ... */
}
적합한 프로그램을 만들려면 해당 오버플로 를 생성 하기 전에 오버플로를 테스트해야합니다 . 이 메서드는 부호없는 정수에도 사용할 수 있습니다.
// for addition
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;
// for subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */;
if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */;
// for multiplication
#include <limits.h>
int a = <something>;
int x = <something>;
// there may be need to check for -1 for two's complement machines
// if one number is -1 and another is INT_MIN multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;
나눗셈의 경우 ( INT_MIN및 -1특수한 경우 제외 ) INT_MIN또는 INT_MAX.
이 인 작업이 피연산자에서 가장 중요한 1의 비트의 위치와 약간의 기본적인 이진 - 수학 지식을 사용하여, 오버 플로우 가능성이 있는지 여부를 확인하는 방법.
또한 두 피연산자는 가장 큰 피연산자의 가장 높은 1 비트보다 (최대) 1 비트를 더 많이 생성합니다. 예를 들면 :
bool addition_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits<32 && b_bits<32);
}
곱셈의 경우 두 피연산자는 (최대) 피연산자의 비트 합계가됩니다. 예를 들면 :
bool multiplication_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits+b_bits<=32);
}
마찬가지로 결과의 최대 크기를 다음 과 같은 a거듭 제곱으로 추정 할 수 있습니다 b.
bool exponentiation_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a);
return (a_bits*b<=32);
}
(물론 대상 정수를 비트 수로 대체하십시오.)
숫자에서 가장 높은 1 비트의 위치를 결정하는 가장 빠른 방법은 확실하지 않습니다. 여기에 무차별 대입 방법이 있습니다.
size_t highestOneBitPosition(uint32_t a) {
size_t bits=0;
while (a!=0) {
++bits;
a>>=1;
};
return bits;
}
완벽하지는 않지만 작업을 수행하기 전에 두 숫자가 넘칠 수 있는지 여부를 알 수 있습니다. highestOneBitPosition함수 의 루프 때문에 제안한 방식으로 결과를 확인하는 것보다 더 빠를지는 모르겠지만 (특히 사전에 피연산자에 얼마나 많은 비트가 있는지 알고 있다면) 그럴 수도 있습니다.
Clang 3.4+ 및 GCC 5+ 는 확인 된 산술 내장 기능을 제공합니다. 특히 비트 테스트 안전 검사와 비교할 때이 문제에 대한 매우 빠른 솔루션을 제공합니다.
OP의 질문에 대한 예는 다음과 같이 작동합니다.
unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
// returned non-zero: there has been an overflow
}
else
{
// return zero: there hasn't been an overflow
}
Clang 문서는 c_test오버플로가 발생한 경우 오버플로 된 결과를 포함 할지 여부를 지정하지 않지만 GCC 문서에는 포함되어 있다고 나와 있습니다. 이 두 가지가 __builtin호환 되는 것을 좋아한다는 점을 감안할 때 이것이 Clang이 작동하는 방식이라고 가정하는 것이 안전 할 것입니다.
존재하는 __builtinINT 크기 긴 크기 및 긴 긴 크기 서명 부호 변형 넘칠 수있는 각각의 산술 연산 (가산, 감산, 승산), 대. 이름 구문은 __builtin_[us](operation)(l?l?)_overflow다음과 같습니다.
u에 대한 서명 또는s를위한 서명 ;- operation은
add,sub또는 중 하나입니다mul. l접미사 없음 은 피연산자가ints 임을 의미합니다 . 하나의l수단long; 2는l의미long long합니다.
따라서 확인 된 부호있는 긴 정수 추가의 경우 __builtin_saddl_overflow. 전체 목록은 Clang 문서 페이지 에서 확인할 수 있습니다 .
GCC 5+와 연타 3.8+ 추가로 값의 유형을 지정하지 않고 작업이 일반적인 내장 명령을 제공합니다 __builtin_add_overflow, __builtin_sub_overflow하고 __builtin_mul_overflow. 이것들은 int.
내장 기능은 플랫폼에 가장 적합한 것보다 낮습니다. x86에서는 carry, overflow 및 sign 플래그를 확인합니다.
Visual Studio의 cl.exe에는 직접 해당하는 항목이 없습니다. 부호없는 덧셈 및 뺄셈의 경우를 포함 <intrin.h>하면 addcarry_uNN및 subborrow_uNN(여기서 NN은 addcarry_u8또는 같은 비트 수) 를 사용할 수 있습니다 subborrow_u64. 그들의 서명은 약간 둔감합니다.
unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);
c_in/ b_in는 입력시 carry / borrow 플래그이고, 반환 값은 출력시 carry / borrow입니다. 부호있는 연산이나 곱셈에 해당하는 항목이없는 것 같습니다.
그렇지 않으면 Windows 용 Clang이 이제 프로덕션 준비가되었으므로 (Chrome에 충분) 옵션이 될 수도 있습니다.
일부 컴파일러는 CPU의 정수 오버플로 플래그에 대한 액세스를 제공하여 테스트 할 수 있지만 이것은 표준이 아닙니다.
곱셈을 수행하기 전에 오버플로 가능성을 테스트 할 수도 있습니다.
if ( b > ULONG_MAX / a ) // a * b would overflow
경고 : GCC는로 컴파일 할 때 오버플로 검사를 최적화 할 수 있습니다 -O2. 이 옵션 -Wall은 다음과 같은 경우에 경고를 제공합니다.
if (a + b < a) { /* deal with overflow */ }
그러나이 예에서는 그렇지 않습니다.
b = abs(a);
if (b < 0) { /* deal with overflow */ }
유일한 안전한 방법은 CERT 문서에 설명 된대로 오버플로가 발생하기 전에 확인하는 것입니다. 이는 체계적으로 사용하는 것이 매우 지루할 것입니다.
로 컴파일하면 -fwrapv문제가 해결되지만 일부 최적화가 비활성화됩니다.
더 나은 솔루션이 절실히 필요합니다. 오버플로가 발생하지 않는 최적화를 수행 할 때 컴파일러가 기본적으로 경고를 발행해야한다고 생각합니다. 현재 상황은 컴파일러가 오버플로 검사를 최적화 할 수 있도록합니다. 이것은 제 생각에는 받아 들일 수 없습니다.
clang은 이제 부호있는 정수와 부호없는 정수 모두에 대한 동적 오버플로 검사를 지원합니다. -fsanitize = integer 스위치를 참조하십시오 . 현재로서는 디버그 목적으로 완전히 지원되는 동적 오버플로 검사 기능이있는 단 하나의 C ++ 컴파일러입니다.
많은 사람들이 오버플로에 대한 질문에 답한 것을 보았지만 그의 원래 문제를 해결하고 싶었습니다. 그는 문제가 모든 숫자가 반복되지 않고 사용되는 b = c 를 찾는 것이라고 말했다 . 좋아요, 그가이 게시물에서 요청한 것은 아니지만, 저는 여전히 문제의 상한선을 연구하고 그가 오버플로를 계산하거나 감지 할 필요가 없다는 결론을 내릴 필요가 있다고 생각합니다 (참고 : 저는 능숙하지 않습니다 수학에서는이 단계를 단계별로 수행했지만 최종 결과는 매우 간단하여 간단한 공식을 가질 수 있습니다.)
요점은 문제가 a, b 또는 c에 필요한 상한이 98.765.432라는 것입니다. 어쨌든, 문제를 사소하고 사소하지 않은 부분으로 나누는 것으로 시작합니다.
- x 0 == 1 (9, 8, 7, 6, 5, 4, 3, 2의 모든 순열이 해임)
- x 1 == x (가능한 솔루션 없음)
- 0 b == 0 (가능한 솔루션 없음)
- 1 b == 1 (가능한 솔루션 없음)
- a b , a> 1, b> 1 (사소하지 않음)
이제 우리는 다른 해결책이 불가능하고 순열 만 유효하다는 것을 보여 주면됩니다 (그런 다음이를 인쇄하는 코드는 간단합니다). 우리는 상한선으로 돌아갑니다. 실제로 상한은 c ≤ 98.765.432입니다. 8 자리로 된 가장 큰 숫자이기 때문에 상한입니다 (총 10 자리에서 각 a 및 b에 대해 1을 뺀 값). 이 상한은 c에 대한 것입니다. 왜냐하면 우리가 계산할 수 있듯이 b를 2에서 상한으로 변화시키는 지수 성장으로 인해 a와 b의 경계가 훨씬 낮아야하기 때문입니다.
9938.08^2 == 98765432
462.241^3 == 98765432
99.6899^4 == 98765432
39.7119^5 == 98765432
21.4998^6 == 98765432
13.8703^7 == 98765432
9.98448^8 == 98765432
7.73196^9 == 98765432
6.30174^10 == 98765432
5.33068^11 == 98765432
4.63679^12 == 98765432
4.12069^13 == 98765432
3.72429^14 == 98765432
3.41172^15 == 98765432
3.15982^16 == 98765432
2.95305^17 == 98765432
2.78064^18 == 98765432
2.63493^19 == 98765432
2.51033^20 == 98765432
2.40268^21 == 98765432
2.30883^22 == 98765432
2.22634^23 == 98765432
2.15332^24 == 98765432
2.08826^25 == 98765432
2.02995^26 == 98765432
1.97741^27 == 98765432
예를 들어 마지막 줄은 1.97 ^ 27 ~ 98M입니다. 예를 들어, 1 ^ 27 == 1 및 2 ^ 27 == 134.217.728 그리고 9 자리 숫자 (2> 1.97이므로 실제로 테스트해야하는 것보다 큽니다)가 있기 때문에 솔루션이 아닙니다. 보시다시피 a와 b를 테스트하는 데 사용할 수있는 조합은 매우 작습니다. b == 14 인 경우 2와 3을 시도해야합니다. b == 3 인 경우 2에서 시작하여 462에서 멈 춥니 다. 모든 결과는 ~ 98M 미만으로 허용됩니다.
이제 위의 모든 조합을 테스트하고 숫자를 반복하지 않는 조합을 찾으십시오.
['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
['1', '2', '3', '5', '8'] 8^3 = 512
['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
['1', '2', '4', '6'] 4^2 = 16
['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
['1', '2', '4', '6'] 2^4 = 16
['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
['1', '2', '8', '9'] 9^2 = 81
['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
['1', '3', '4', '8'] 3^4 = 81
['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
['2', '3', '6', '7', '9'] 3^6 = 729
['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
['2', '3', '8'] 2^3 = 8
['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
['2', '3', '9'] 3^2 = 9
['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
['2', '4', '6', '8'] 8^2 = 64
['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
['2', '4', '7', '9'] 7^2 = 49
['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)
그들 중 어느 것도 문제와 일치하지 않습니다 ( '0', '1', ..., '9'가 없어도 볼 수 있음).
이를 해결하는 예제 코드는 다음과 같습니다. 또한 임의의 정밀도 정수가 필요하기 때문이 아니라 (코드가 9800 만보 다 큰 것을 계산하지 않음) Python으로 작성되었지만 테스트의 양이 너무 적어서 높은 수준의 언어를 사용해야한다는 사실을 알게 되었기 때문입니다. 내장 된 컨테이너와 라이브러리를 사용합니다 (또한 코드에 28 줄이 있음).
import math
m = 98765432
l = []
for i in xrange(2, 98765432):
inv = 1.0/i
r = m**inv
if (r < 2.0): break
top = int(math.floor(r))
assert(top <= m)
for j in xrange(2, top+1):
s = str(i) + str(j) + str(j**i)
l.append((sorted(s), i, j, j**i))
assert(j**i <= m)
l.sort()
for s, i, j, ji in l:
assert(ji <= m)
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d' % (s, i, j, ji)
# Try with non significant zero somewhere
s = ['0'] + s
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)
다음은 질문에 대한 "휴대용이 아닌"해결책입니다. Intel x86 및 x64 CPU에는 소위 EFLAGS 레지스터 ( http://en.wikipedia.org/wiki/EFLAGS )가 있으며 각 정수 연산 후 프로세서에 의해 채워집니다. 여기서는 자세한 설명을 생략하겠습니다. 관련 플래그는 "Overflow"플래그 (마스크 0x800) 및 "Carry"플래그 (마스크 0x1)입니다. 올바르게 해석하려면 피연산자가 부호있는 유형인지 부호없는 유형인지 고려해야합니다.
다음은 C / C ++에서 플래그를 확인하는 실용적인 방법입니다. 다음 코드는 Visual Studio 2005 이상 (32 비트 및 64 비트 모두)과 GNU C / C ++ 64 비트에서 작동합니다.
#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif
inline size_t query_intel_x86_eflags( const size_t query_bit_mask )
{
#if defined( _MSC_VER )
return __readeflags() & query_bit_mask;
#elif defined( __GNUC__ )
// this code will work only on 64-bit GNU-C machines;
// Tested and does NOT work with Intel C++ 10.1!
size_t eflags;
__asm__ __volatile__(
"pushfq \n\t"
"pop %%rax\n\t"
"movq %%rax, %0\n\t"
:"=r"(eflags)
:
:"%rax"
);
return eflags & query_bit_mask;
#else
#pragma message("No inline assembly will work with this compiler!")
return 0;
#endif
}
int main(int argc, char **argv)
{
int x = 1000000000;
int y = 20000;
int z = x * y;
int f = query_intel_x86_eflags( 0x801 );
printf( "%X\n", f );
}
피연산자가 오버플로없이 곱해지면 query_intel_eflags (0x801)에서 반환 값 0을 얻습니다. 즉, carry 또는 overflow 플래그가 설정되지 않습니다. main ()의 제공된 예제 코드에서 오버플로가 발생하고 두 플래그가 모두 1로 설정됩니다.이 검사는 추가 계산을 의미하지 않으므로 매우 빠릅니다.
테스트하려는 데이터 유형보다 큰 데이터 유형이있는 경우 (예를 들어 32 비트 추가를 수행하고 64 비트 유형이 있음). 그런 다음 오버플로가 발생했는지 감지합니다. 내 예는 8 비트 추가입니다. 하지만 확장 할 수 있습니다.
uint8_t x, y; /* give these values */
const uint16_t data16 = x + y;
const bool carry = (data16 > 0xff);
const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80);
이 페이지에 설명 된 개념을 기반으로합니다. http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html
32 비트 예제의 경우 0xff는 0xffffffff이고 0x80되며 0x80000000최종적 uint16_t으로 uint64_t.
참고 : 이것은 정수 더하기 / 빼기 오버플로를 포착하고 귀하의 질문에 곱셈이 포함된다는 것을 깨달았습니다. 어떤 경우에는 분할이 가장 좋은 방법 일 것입니다. 이것은 일반적으로 calloc구현시 매개 변수가 최종 크기를 얻기 위해 곱해질 때 오버플로되지 않도록 하는 방법입니다 .
가장 간단한 방법은 unsigned longs를 unsigned long longs 로 변환 하고 곱셈을 수행 한 다음 결과를 0x100000000LL과 비교하는 것입니다.
예제에서했던 것처럼 분할을 수행하는 것보다 이것이 더 효율적임을 알 수 있습니다.
아, 그리고 그것은 C와 C ++ 모두에서 작동합니다 (질문에 둘 다 태그를 붙인 것처럼).
방금 glibc 매뉴얼을 살펴 보았습니다 . 의 FPE_INTOVF_TRAP일부로 정수 오버플로 트랩 ( )에 대한 언급이 있습니다 SIGFPE. 매뉴얼의 불쾌한 부분을 제외하고는 이상적입니다.
FPE_INTOVF_TRAP정수 오버플로 (하드웨어 특정 방식으로 오버플로 트래핑을 활성화하지 않는 한 C 프로그램에서 불가능).
정말 부끄러운 일입니다.
2 년이 지났지 만, 적어도 덧셈에 대한 오버플로를 감지하는 정말 빠른 방법을 위해 페니스 워스를 추가하는 것이 좋을 것 같았습니다.
아이디어는 프로세서가 값을 0으로 되돌 리도록하고 C / C ++가 특정 프로세서에서 추상화되기 때문에 다음을 수행 할 수 있다는 것입니다.
uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);
이렇게하면 피연산자가 0이고 1이 아닌 경우 오버플로가 잘못 감지되지 않고 이전에 제안한 많은 NOT / XOR / AND / 테스트 작업보다 훨씬 빠릅니다.
편집 : 지적했듯이이 접근법은 다른 정교한 방법보다 낫지 만 여전히 최적화 할 수 있습니다. 다음은 최적화가 포함 된 원본 코드의 개정판입니다.
uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < x; // Alternatively "value < y" should also work
부호없는 정수의 경우 결과가 인수 중 하나보다 작은 지 확인하십시오.
unsigned int r, a, b;
r = a+b;
if (r < a)
{
// overflow
}
부호있는 정수의 경우 인수와 결과의 부호를 확인할 수 있습니다. 다른 부호의 정수는 오버플로 할 수 없으며 동일한 부호의 정수만 오버플로하면 결과는 다른 부호입니다.
signed int r, a, b, s;
r = a+b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
// overflow
}
C / C ++에서 오버플로 플래그에 액세스 할 수 없습니다.
일부 컴파일러에서는 코드에 트랩 명령을 삽입 할 수 있습니다. GCC에서 옵션은 -ftrapv입니다 (하지만 사용한 적이 없음을 인정해야합니다. 게시 후 확인합니다).
이식 가능하고 컴파일러에 독립적으로 할 수있는 유일한 작업은 직접 오버플로를 확인하는 것입니다. 당신의 예에서했던 것처럼.
편집하다:
방금 확인 : -ftrapv는 최신 GCC를 사용하여 x86에서 아무 작업도 수행하지 않는 것 같습니다. 이전 버전에서 남은 것이거나 다른 아키텍처에 한정된 것 같습니다. 컴파일러가 각 추가 후에 INTO opcode를 삽입 할 것으로 예상했습니다. 불행히도 이것은 이것을하지 않습니다.
비트 마스킹과 시프트가 유망 해 보이지 않는 부동 소수점 숫자에 대해서도 동일한 질문에 답해야했습니다. 내가 정한 접근 방식은 부호있는 숫자와 부호없는 숫자, 정수 및 부동 소수점 숫자에 대해 작동합니다. 중간 계산을 위해 승격 할 더 큰 데이터 유형이없는 경우에도 작동합니다. 이러한 모든 유형에 대해 가장 효율적인 것은 아니지만 모든 유형에서 작동하므로 사용할 가치가 있습니다.
서명 된 오버플로 테스트, 더하기 및 빼기 :
MAXVALUE 및 MINVALUE 유형에 대해 가능한 최대 값과 최소값을 나타내는 상수를 확보하십시오.
피연산자의 부호를 계산하고 비교합니다.
ㅏ. 두 값 중 하나가 0이면 더하기 나 빼기 모두 오버플로 할 수 없습니다. 나머지 테스트를 건너 뜁니다.
비. 기호가 반대이면 덧셈이 넘칠 수 없습니다. 나머지 테스트를 건너 뜁니다.
씨. 부호가 같으면 빼기가 넘칠 수 없습니다. 나머지 테스트를 건너 뜁니다.
MAXVALUE의 양수 오버플로를 테스트합니다.
ㅏ. 두 부호가 모두 양수이고 MAXVALUE-A <B이면 더하기가 오버플로됩니다.
비. B의 부호가 음수이고 MAXVALUE-A <-B이면 빼기가 오버플로됩니다.
MINVALUE의 음수 오버플로를 테스트합니다.
ㅏ. 두 부호가 모두 음수이고 MINVALUE-A> B이면 더하기가 오버플로됩니다.
비. A의 부호가 음수이고 MINVALUE-A> B이면 빼기가 오버플로됩니다.
그렇지 않으면 오버플로가 없습니다.
서명 된 오버플로 테스트, 곱셈 및 나눗셈 :
MAXVALUE 및 MINVALUE 유형에 대해 가능한 최대 값과 최소값을 나타내는 상수를 확보하십시오.
피연산자의 크기 (절대 값)를 1로 계산하고 비교합니다. (아래에서 A와 B는 서명 된 원본이 아니라 이러한 크기라고 가정합니다.)
ㅏ. 두 값 중 하나가 0이면 곱셈이 오버플로 될 수 없으며 나누면 0 또는 무한대가 생성됩니다.
비. 두 값 중 하나가 1이면 곱셈과 나눗셈이 넘칠 수 없습니다.
씨. 한 피연산자의 크기가 하나보다 작고 다른 피연산자의 크기가 1보다 크면 곱셈이 오버플로 될 수 없습니다.
디. 크기가 둘 다 1보다 작 으면 분할이 넘칠 수 없습니다.
MAXVALUE의 양수 오버플로를 테스트합니다.
ㅏ. 두 피연산자가 1보다 크고 MAXVALUE / A <B이면 곱셈이 오버플로됩니다.
비. B가 1보다 작고 MAXVALUE * B <A이면 나누기가 오버플로됩니다.
그렇지 않으면 오버플로가 없습니다.
참고 : MINVALUE의 최소 오버 플로우는 절대 값을 취 했으므로 3으로 처리됩니다. 그러나 ABS (MINVALUE)> MAXVALUE이면 드문 오 탐지가 발생합니다.
언더 플로 테스트는 비슷하지만 EPSILON (0보다 큰 가장 작은 양수)을 포함합니다.
CERT는 "as-if"무한 범위 (AIR) 정수 모델을 사용하여 부호있는 정수 오버 플로우, 부호없는 정수 래핑 및 정수 절단을 감지하고보고하는 새로운 접근 방식을 개발했습니다. CERT는 모델을 설명 하는 기술 보고서 를 발표하고 GCC 4.4.0 및 GCC 4.5.0을 기반으로 작동하는 프로토 타입을 제작했습니다.
AIR 정수 모델은 무한 범위 정수를 사용하여 얻은 것과 동일한 값을 생성하거나 런타임 제약 조건 위반을 초래합니다. 이전 정수 모델과 달리 AIR 정수는 정확한 트랩이 필요하지 않으므로 결과적으로 대부분의 기존 최적화를 중단하거나 금지하지 않습니다.
또 다른 흥미로운 도구 : http://embed.cs.utah.edu/ioc/
이것은 clang컴파일 시간에 코드에 검사를 추가 하는 패치 된 컴파일러입니다. 따라서 다음과 같은 출력이 표시됩니다.
CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
어셈블러를 사용하는 솔루션의 또 다른 변형은 외부 절차입니다. Linux x64에서 g ++ 및 fasm을 사용하는 부호없는 정수 곱셈에 대한이 예제입니다.
이 절차는 두 개의 부호없는 정수 인수 (32 비트)를 곱합니다 ( amd64의 사양 에 따라 (섹션 3.2.3 매개 변수 전달))
클래스가 INTEGER이면 시퀀스 % rdi, % rsi, % rdx, % rcx, % r8 및 % r9의 사용 가능한 다음 레지스터가 사용됩니다.
(edi 및 esi는 내 코드에 등록)) 결과를 반환하거나 오버플로가 발생한 경우 0을 반환합니다.
format ELF64
section '.text' executable
public u_mul
u_mul:
MOV eax, edi
mul esi
jnc u_mul_ret
xor eax, eax
u_mul_ret:
ret
테스트:
extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);
int main() {
printf("%u\n", u_mul(4000000000,2));//0
printf("%u\n", u_mul(UINT_MAX/2,2));//ok
return 0;
}
프로그램을 asm 개체 파일과 연결합니다. Qt Creator의 경우 .pro 파일의 LIBS에 추가하십시오.
이 매크로를 사용하여 32 비트 컴퓨터의 오버플로 비트를 테스트합니다 (Angel Sinigersky 솔루션 수정).
#define overflowflag(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
그렇지 않으면 오버플로 비트를 덮어 썼기 때문에 매크로로 정의했습니다.
그 다음은 위의 코드 부분이있는 작은 응용 프로그램입니다.
#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif
using namespace std;
#define detectOverflow(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
int main(int argc, char **argv) {
bool endTest = false;
bool isOverflow;
do {
cout << "Enter two intergers" << endl;
int x = 0;
int y = 0;
cin.clear();
cin >> x >> y;
int z = x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow occured\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
z = x * x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow ocurred\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;
char c = 0;
do {
c = getchar();
} while ((c == '\n') && (c != EOF));
if (c == 'y' || c == 'Y') {
endTest = true;
}
do {
c = getchar();
} while ((c != '\n') && (c != EOF));
} while (!endTest);
}
복식으로 결과를 계산하십시오. 15 개의 유효 숫자가 있습니다. 요구 사항의 c 에 대한 하드 상한 은 10 8 이며 최대 8 자리까지 가능합니다. 따라서 범위 내에 있으면 결과가 정확하고 그렇지 않으면 오버플로되지 않습니다.
C / C ++에서 오버플로 플래그에 액세스 할 수 없습니다.
나는 이것에 동의하지 않는다. 인라인 asm을 작성하고 jox86에서 오버플로를 트랩한다고 가정 하고 (점프 오버플로) 명령을 사용할 수 있습니다. 물론 코드는 더 이상 다른 아키텍처로 이식 할 수 없습니다.
보고 info as와 info gcc.
C에서 Integer Overflows를 잡는 것은 일부 GCC 확장이 필요하더라도 CERT에서 논의한 것보다 더 일반적인 솔루션을 지적합니다 (처리 된 유형의 관점에서 더 일반적 임).
Head Geek의 답변을 확장하려면 더 빠른 방법이 있습니다 addition_is_safe.
bool addition_is_safe(unsigned int a, unsigned int b)
{
unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
L_Mask >>= 1;
L_Mask = ~L_Mask;
a &= L_Mask;
b &= L_Mask;
return ( a == 0 || b == 0 );
}
이것은 64 비트 및 32 비트 부호없는 정수가 여전히 잘 작동한다는 점에서 기계 아키텍처 안전을 사용합니다. 기본적으로 가장 중요한 부분을 제외한 모든 부분을 가릴 마스크를 만듭니다. 그런 다음 두 정수를 모두 마스킹하고 둘 중 하나에 해당 비트가 설정되어 있지 않으면 추가가 안전합니다.
마스크는 변경되지 않기 때문에 일부 생성자에서 마스크를 미리 초기화하면 더 빠릅니다.
x86 명령어 세트에는 결과를 두 개의 레지스터에 저장하는 부호없는 곱하기 명령어가 포함됩니다. C에서 해당 명령어를 사용하려면 64 비트 프로그램 (gcc)에서 다음 코드를 작성할 수 있습니다.
unsigned long checked_imul(unsigned long a, unsigned long b) {
__int128 res = (__int128)a * (__int128)b;
if ((unsigned long)(res >> 64))
printf("overflow in integer multiply");
return (unsigned long)res;
}
32 비트 프로그램의 경우 결과 64 비트와 매개 변수 32 비트를 만들어야합니다.
대안은 컴파일러 의존 본능을 사용하여 플래그 레지스터를 확인하는 것입니다. 오버플로 본능에 대한 GCC 문서는 https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html 에서 찾을 수 있습니다.
mozilla::CheckedInt<T>정수 유형에 대해 오버플로 검사 된 정수 수학을 제공합니다 T(사용 가능한 경우 clang 및 gcc에서 컴파일러 내장 함수 사용). 코드는 MPL 2.0 아래 세에 따라 ( IntegerTypeTraits.h, Attributes.h과 Compiler.h) 다른 헤더 만이 아닌 표준 라이브러리 헤더 플러스 모질라 고유의 주장 기계 . 코드를 가져 오는 경우 어설 션 기계를 바꾸고 싶을 것입니다.
이를위한 깨끗한 방법은 모든 연산자 (특히 + 및 *)를 재정의하고 작업을 수행하기 전에 오버플로를 확인하는 것입니다.
@MSalters : 좋은 생각입니다.
정수 계산이 필요하지만 (정밀도를 위해) 부동 소수점을 사용할 수있는 경우 다음과 같이 할 수 있습니다.
uint64_t foo( uint64_t a, uint64_t b ) {
double dc;
dc = pow( a, b );
if ( dc < UINT_MAX ) {
return ( powu64( a, b ) );
}
else {
// overflow
}
}
인라인 어셈블리를 사용하면 오버플로 비트를 직접 확인할 수 있습니다. C ++를 사용하려면 어셈블리를 배워야합니다.
용도에 따라 다릅니다. unsigned long (DWORD) 더하기 또는 곱하기를 수행하는 가장 좋은 해결책은 ULARGE_INTEGER를 사용하는 것입니다.
ULARGE_INTEGER는 두 개의 DWORD 구조입니다. 전체 값은 "QuadPart"로 액세스 할 수 있으며 hi DWORD는 "HighPart"로 액세스하고 낮은 DWORD는 "LowPart"로 액세스 할 수 있습니다.
예를 들면 :
DWORD 내 추가 (DWORD Value_A, DWORD Value_B) {ULARGE_INTEGER a, b;
b.LowPart = Value_A; // a 32 bit value(up to 32 bit)
b.HighPart = 0;
a.LowPart = Value_B; // a 32 bit value(up to 32 bit)
a.HighPart = 0;
a.QuadPart += b.QuadPart;
// if a.HighPart
// Then a.HighPart contains the overflow(carry)
return (a.LowPart + a.HighPart)
// 모든 오버플로는 a.HighPart (최대 32 비트)에 저장됩니다.
이식 가능한 방식으로 오버플로하지 않고 부호없는 곱셈을 수행하려면 다음을 사용할 수 있습니다.
... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
product += multiplicand;
if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */
int number_of_leading_zeroes( unsigned value ){
int ctZeroes;
if( value == 0 ) return 32;
ctZeroes = 1;
if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
if( ( value >> 24 ) == 0 ){ ctZeroes += 8; value = value << 8; }
if( ( value >> 28 ) == 0 ){ ctZeroes += 4; value = value << 4; }
if( ( value >> 30 ) == 0 ){ ctZeroes += 2; value = value << 2; }
ctZeroes -= x >> 31;
return ctZeroes;
}
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int mltovf(int a, int b)
{
if (a && b) return abs(a) > MAX/abs(b);
else return 0;
}
main()
{
int a, b;
for (a = 0; a <= MAX; a++)
for (b = 0; b < MAX; b++) {
if (mltovf(a, b) != (a*b > MAX))
printf("Bad calculation: a: %d b: %d\n", a, b);
}
}
참고 URL : https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-multiply-overflow
'programing tip' 카테고리의 다른 글
| git이 자체 서명 된 인증서를 수락하도록하려면 어떻게해야합니까? (0) | 2020.10.03 |
|---|---|
| MySQL에서 외래 키 제약 조건을 일시적으로 비활성화하는 방법은 무엇입니까? (0) | 2020.10.03 |
| Android 개발에 Java 8을 사용할 수 있습니까? (0) | 2020.10.03 |
| 파이썬에서 2 차원 배열을 정의하는 방법 (0) | 2020.10.02 |
| 다른 쉘 스크립트에서 쉘 스크립트를 호출하는 방법은 무엇입니까? (0) | 2020.10.02 |