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

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

74 голосов
/ 15 октября 2010

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

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

Ответы [ 12 ]

0 голосов
/ 16 октября 2010

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

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

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

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 такого нет.

0 голосов
/ 15 октября 2010

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

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

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

Страница:
...