6 Aralık 2019 Cuma

Signed Integer Overflow - Undefined Behavior Oluşturur

Unsigned Integer Overflow C ve C++ standartları tarafından tanımlı. Yani dilin bir parçası. Açıklaması şöyle.
C’s unsigned integer types are “modulo” in the LIA−1 sense in that overflows or out-of-bounds results silently wrap.
Unsigned Integer Overflow için açıklama şöyle.
A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.
Ancak Signed Integer Overflow C ve C++ standartları tarafından tanımlı değil. Açıklaması şöyle. Singed Integer Overflow Java'da tanımlı ve böyle bir problem yok :)
Integer overflow (on plain int or long or other signed integral type) is an instance of undefined behavior, so the compiler can optimize as it please against it. Be scared. If you depend on UB you are no more coding in standard C++ and your program is tied to a particular compiler and system, so is not portable at all (even to other compilers, other compiler versions, other compilation flags, other computers and OSes). So Clang (or GCC) is allowed to optimize against integer overflow, and sometimes does.
Neden Böyle ?
Sanırım en makul açıklama geçmişin bir mirası olması. Açıklaması şöyle.
Of course, the real reason why signed-integer overflow is undefined is that when C was developed, there were at least three different representations of signed integers in use (one's-complement, two's-complement, sign-magnitude, and perhaps offset binary), and each gives a different result for INT_MAX+1. Making overflow undefined permits a + b to be compiled to the native add b a instruction in every situation, rather than potentially requiring a compiler to simulate some other form of signed integer arithmetic.
Unsinged Integer Varsa Overflow Olsa Bile Döngü Optimizasyonu Yapılabilir
Elimizde şöyle bir kod olsun. Burada i aslında INT_MAX'ı geçse bile  eksi değere düşmeyeceği için derleyici döngünün tam olarak kaç defa döneceğini bilir.
for (i = 0; i <= N; ++i) { ... }
Açıklaması şöyle.
In this loop, the compiler can assume that the loop will iterate exactly N+1 times if "i" is undefined on overflow, which allows a broad range of loop optimizations to kick in. On the other hand, if the variable is defined to wrap around on overflow, then the compiler must assume that the loop is possibly infinite (which happens if N is INT_MAX) - which then disables these important loop optimizations. This particularly affects 64-bit platforms since so much code uses "int" as induction variables.
Gcc bir sürü built-in metod sağlıyor. İmzaları şöyle.
bool __builtin_add_overflow (type1 a, type2 b, type3 *res)
bool __builtin_sadd_overflow (int a, int b, int *res)
bool __builtin_saddl_overflow (long int a, long int b, long int *res)
bool __builtin_saddll_overflow (long long int a, long long int b, long long int *res)
bool __builtin_uadd_overflow (unsigned int a, unsigned int b, unsigned int *res)
bool __builtin_uaddl_overflow (unsigned long int a, unsigned long int b,
  unsigned long int *res)
bool __builtin_uaddll_overflow (unsigned long long int a, unsigned long long int b,
  unsigned long long int *res)
Kendimi kodlarsak şöyle yaparız.
#include <limits.h>

int safe_add(int a, int b) 
  if (a >= 0) {
    if (b > (INT_MAX - a)) {
      /* handle overflow */
  } else {
    if (b < (INT_MIN - a)) {
      /* handle underflow */
  return a + b;
Signed Integer Overflow ve Optimizasyon Seviyesi
Elimizde şöyle bir kod olsun
#include <stdio.h>
#include <limits.h>

int foo ( int x) {
  printf ("% d\n" ,  x );   //2147483647
  printf ("% d\n" ,  x+1 ); //-2147483648  overflow
  return ( x+1 ) > x ;      // 1 but How????

int main ( void ) {
  printf ("% d\n" ,  INT_MAX );     //2147483647
  printf ("% d\n" ,  INT_MAX+1 );   //-2147483648  overflow
  printf ("% d\n" , ( INT_MAX+1 ) > INT_MAX );  //0  makes sense, since -ve < +ve
  printf ("% d\n" ,  foo(INT_MAX) );  //1
  return 0;
Bu kod -O0 ve -O1 seviyesinde şu çıktıyı verir
-O2 ve -O3 seviyesinde şu çıktıyı verir
Açıklaması şöyle. Yani derleyici optimizasyon seviyesi artınca farklı bir varsayımda bulunup direkt 1 dönmeye karar verebiliyor.
Given that x has type int, the compiler knows that signed overflow is UB and works under the assumption that it will not occur. With that in mind, there is no value for x where this expression could be false, so the compiler could optimize away the expression and replace it with the value 1.
Elimizde şöyle bir kod olsun. factor değişkeni döngünun sayısına göre INT_MAX'ı çok rahat geçebilir.
int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
return result;
x * y'nin taşma olmadan çarpılabildiğini anlamak için şöyle yaparız.
#include <limits>

template <typename T>
bool predict_mul_overflow(T x, T y)
  static_assert(std::numeric_limits<T>::is_integer, "expects integral types");

  if constexpr (std::numeric_limits<T>::is_bounded)
    return ((x != T{0}) && ((std::numeric_limits<T>::max() / x) < y));
    return false;
Elimizde şöyle bir kod olsun.
int a = 1;
int b = INT_MIN;
compare metodunu şöyle yaparsak u kod hatalı sonuç verir
int compare (const void * a, const void * b)
  return ( *(int*)a - *(int*)b );
Şöyle yaparız
int compare(const void *a, const void *b) {
  const int *aa = a;
  const int *bb = b;
  return (*aa > *bb) - (*aa < *bb);

Hiç yorum yok:

Yorum Gönder