Обнаружение подписанного переполнения в C/С++

Ответ 1

Ваш подход с вычитанием правилен и четко определен. Компилятор не может оптимизировать его.

Еще один правильный подход, если у вас есть больший целочисленный тип, - это выполнить арифметику в более крупном типе, а затем проверить, соответствует ли результат меньшему типу при его обратном преобразовании.

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 и единый условный переход на переполнение и никогда не выполнять большее добавление.

Изменить: Как отметил Стивен, у меня возникли проблемы с получением (не очень хорошего) компилятора gcc для генерации разумного asm. Код, который он генерирует, не очень медленный, но, безусловно, субоптимальный. Если кто-нибудь знает варианты этого кода, которые получат gcc, чтобы поступать правильно, я бы хотел их увидеть.

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

Ответ 3

ИМХО, самый восточный способ справиться с переполнением настойчивый код на С++ - это использовать SafeInt<T>. Это кроссплатформенный шаблон С++, размещенный на кодексе plex, который обеспечивает гарантии безопасности, которые вы здесь ищете.

• http://safeint.codeplex.com/

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

Ответ 4

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

Ответ 5

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

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

Например:

__builtin_add_overflow( rhs, lhs, &result )

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

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

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

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

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

__builtin_sadd_overflow( rhs, lhs, &result )

Ответ 6

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

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

Ответ 7

Как насчет:

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

Ответ 8

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

Ответ 9

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

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

Итак, достаточно проверить такую ​​проверку:

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

Изменить: как предложил Нильс, это правильное условие if:

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

И так как когда инструкция

add eax, ebx 

приводит к поведению undefined? В реестре наборов инструкций Intel x86 такого не существует.

Ответ 10

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

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

Ответ 11

В случае добавления двух значений 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'

Ответ 12

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

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 =, но сборка была одинаковой.

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

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