Обнаружение переполнения со знаком в C / C++

нет, ваш 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 по обе стороны неравенств, и это дает вам точно арифметические условия, что ваш результат выходит за пределы.

IMHO, самый восточный способ справиться с переполнением sentsitive C++ - это использовать SafeInt<T>. Это кросс-платформенный шаблон C++, размещенный на Code plex, который обеспечивает гарантии безопасности, которые вы хотите здесь.

• http://safeint.codeplex.com/

Я нахожу его очень интуитивным в использовании, поскольку он обеспечивает многие из тех же шаблонов использования, что и обычные числовые операции, и выражает над и под потоками через исключения.

для случая gcc, от примечания к выпуску gcc 5.0 мы видим, что теперь он обеспечивает __builtin_add_overflow для проверки переполнения дополнительно:

новый набор встроенных функций для арифметики с переполнением проверки добавлен: __строение_добавить_переполнения, __строение_суб_переполнения и __строение_ООО_переполнения, а также для совместимости с лязгом и другие варианты. Эти встроенные элементы имеют два интегральных аргумента (которые не должны иметь один и тот же тип), аргументы расширяются для бесконечной точности знаковый тип,+, - или * выполняется на тех, и результат хранится в целочисленной переменной, на которую указывает последний аргумент. Если сохраненное значение равно результату бесконечной точности, встроенные функции возвращают false, в противном случае true. Тип целочисленной переменной, которая будет содержать результат, может отличаться от типов первых двух аргументов.

например:

__builtin_add_overflow( rhs, lhs, &result )

мы можем видеть из документа gcc встроенные функции для выполнения арифметики с проверкой переполнения что:

[...]эти встроенные функции имеют полностью определенное поведение для всех значений аргументов.

clang также предоставляет набор проверенные арифметические встроенные:

Clang предоставляет набор встроенных функций, которые реализуют проверенную арифметику для критически важных приложений безопасности таким образом, что это быстро и легко выражается в С.

в этом случае строение будет:

__builtin_sadd_overflow( rhs, lhs, &result )

Если вы используете встроенный ассемблер, вы можете проверить флаг переполнения. Другая возможность заключается в том, что вы можете использовать тип safeint. Я рекомендую прочитать эту статью на Целое Число Безопасности.

как насчет:

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 (симметрично или нет); функция, как показано клипы, но это должно быть очевидно, как получить другие поведения).

возможно, Вам повезет с преобразованием в 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;
}

вы можете поближе взглянуть на то, как расширение знака будет работать здесь, но я думаю, что это правильно.

самый быстрый способ-использовать встроенный 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) находится на iff операнды имеют тот же знак, и знак бит lhs ^ sum находится на iff результат имеет другой знак, чем операнды. Таким образом, вы можете сделать добавление в неподписанной форме, чтобы избежать неопределенного поведения, а затем использовать знаковый бит ~(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

что намного быстрее, чем приведение к 64-разрядному типу на 32-разрядной машине (с gcc):

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

по мне, самая простая проверка будет проверка знаков операндов и результатов.

рассмотрим sum: переполнение может происходить в обоих направлениях, + или -, только когда оба операнда имеют одинаковый знак. И, очевидно, переполнение будет, когда знак результата не будет таким же, как знак операндов.

Итак, такой чек будет достаточно:

int a, b, sum;
sum = a + b;
if  (((a ^ ~b) & (a ^ sum)) & 0x80000000)
    detect_oveflow();

Edit: как предложил Нильс, это правильно if состояние:

((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)

и с каких пор инструкция

add eax, ebx 

приводит к неопределенному поведению? Нет такой вещи в наборе инструкций Intel x86 refference..

очевидным решением является преобразование в 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;  
} 

это заменяет неопределенное поведение переполнения со знаком с определенным реализацией преобразованием значений вне диапазона между подписанными и беззнаковыми, поэтому вам нужно проверить документацию вашего компилятора, чтобы точно знать, что произойдет, но она должна быть по крайней мере хорошо определена и должна делать правильные вещи на любой машине с двумя дополнениями, которая не вызывает сигналов о преобразованиях, которые в значительной степени являются каждой машиной и компилятором C, построенным за последние 20 лет.

в случае добавления двух long значения, портативный код может разделить 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'

использование встроенной сборки-это самый быстрый способ, если вы нацелены на конкретный процессор:

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'

Я думаю, что это работает:

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

использование volatile не позволяет компилятору оптимизировать тест, потому что он думает, что sum может измениться между сложением и вычитанием.

использование gcc 4.4.3 для x86_64 сборка для этого кода выполняет сложение, вычитание и тест, хотя она хранит все в стеке и ненужных операциях стека. Я даже пытался register volatile int sum = но сборка была такой же.

для a версия только с int sum = (нет летучих или регистр) функция не делала тест и сделал добавление, используя только один lea инструкции (lea является эффективным адресом загрузки и часто используется для добавления, не касаясь регистра флагов).

ваша версия больше кода и имеет гораздо больше прыжков, но я не знаю, что будет лучше.