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

c++ c undefined-behavior signed integer-overflow

22342 просмотра

12 ответа

10502 Репутация автора

На первый взгляд, этот вопрос может показаться дубликатом Как обнаружить целочисленное переполнение? Однако на самом деле это значительно отличается.

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

Самый очевидный, но наивный способ сделать это будет что-то вроде:

int add(int lhs, int rhs)
{
 int sum = lhs + rhs;
 if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
  /* an overflow has occurred */
  abort();
 }
 return sum; 
}

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

Несмотря на то, что приведенная выше проверка может работать на многих компиляторах, вы не можете рассчитывать на нее. Фактически, поскольку стандарт C говорит, что целочисленное переполнение со знаком не определено, некоторые компиляторы (например, GCC) оптимизируют проверку, указанную выше, когда установлены флаги оптимизации, поскольку компилятор предполагает, что переполнение со знаком невозможно. Это полностью нарушает попытку проверки на переполнение.

Итак, еще один возможный способ проверить переполнение:

int add(int lhs, int rhs)
{
 if (lhs >= 0 && rhs >= 0) {
  if (INT_MAX - lhs <= rhs) {
   /* overflow has occurred */
   abort();
  }
 }
 else if (lhs < 0 && rhs < 0) {
  if (lhs <= INT_MIN - rhs) {
   /* overflow has occurred */
   abort();
  }
 }

 return lhs + rhs;
}

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

Однако это решение, к сожалению, намного менее эффективно, чем первоначальное решение, так как вам нужно выполнить операцию вычитания, чтобы проверить, будет ли работать ваша операция сложения. И даже если вы не заботитесь об этом (небольшом) падении производительности, я все еще не совсем уверен, что это решение адекватно. Выражение lhs <= INT_MIN - rhsвыглядит точно так же, как выражение, которое компилятор может оптимизировать, думая, что переполнение со знаком невозможно.

Так есть ли лучшее решение здесь? Что-то, что гарантировано: 1) не вызывает неопределенного поведения, и 2) не предоставляет компилятору возможность оптимизировать проверку переполнения? Я думал, что мог бы быть какой-то способ сделать это, приведя оба операнда к беззнаковому, и выполнив проверки, свернув арифметику с двумя собственными дополнениями, но я не совсем уверен, как это сделать.

Автор: Channel72 Источник Размещён: 15.10.2010 05:16

Ответы (12)


1 плюс

11399 Репутация автора

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

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

Автор: Jonathan Размещён: 15.10.2010 05:31

10 плюса

48905 Репутация автора

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

Автор: rook Размещён: 15.10.2010 05:32

16 плюса

610430 Репутация автора

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

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

Автор: JaredPar Размещён: 15.10.2010 05:32

23 плюса

166942 Репутация автора

Решение

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

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

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

Автор: R.. Размещён: 15.10.2010 05:57

-1 плюса

10829 Репутация автора

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

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это Load Effective Address и часто используется для сложения, не касаясь регистра флагов).

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

Автор: nategoose Размещён: 15.10.2010 07:39

-1 плюса

12766 Репутация автора

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

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

Итак, такой проверки будет достаточно:

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 

приводит к неопределенному поведению? В ссылках на набор команд Intel x86 такого нет.

Автор: ruslik Размещён: 15.10.2010 08:46

2 плюса

60912 Репутация автора

Как насчет:

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

Автор: supercat Размещён: 15.10.2010 08:47

0 плюса

86794 Репутация автора

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

Автор: Chris Dodd Размещён: 15.10.2010 10:22

34 плюса

67656 Репутация автора

Нет, ваш второй код неверен, но вы близки: если вы установите

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

Автор: Jens Gustedt Размещён: 16.10.2010 06:41

13 плюса

131752 Репутация автора

В случае 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 )
Автор: Shafik Yaghmour Размещён: 31.08.2015 06:18

0 плюса

210 Репутация автора

В случае добавления двух 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'
Автор: atomsymbol Размещён: 06.06.2017 01:18

6 плюса

12340 Репутация автора

Самый быстрый способ - использовать встроенный 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включен, если результат имеет знак, отличный от операндов. Таким образом, вы можете выполнить сложение в беззнаковой форме, чтобы избежать неопределенного поведения, а затем использовать знаковый бит ~(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
Автор: tbodt Размещён: 29.06.2017 04:35
Вопросы из категории :
32x32