29

Часто в контексте безопасного программирования упоминают проблему целочисленного переполнения (integer overflow). А возможно ли отловить эту ситуацию в C/C++ коде? Ведь процессоры (по крайней мере x86) имеют среди EFLAGS флаг Overflow Flag, получается, что чисто технически такая возможность имеется, да и оверхэд на проверку флага в регистре не должен быть большим (думается так). Либо проблема в постановке вопроса и переполнение нужно не отлавливать, а не допускать никогда? Значит ли последнее, что целочисленные типы принципиально не подходят для любых вычислений?

P.S. Вопрос возник в связи с тем, что в существующем коде (наблюдаемом мной) широко используется int для арифметических расчетов и ничто не защищает от переполнений, гипотетически они могут остаться незамеченными (логикой). И в большинстве случаев с большой вероятностью все в норме (реальные значения невелики), но иногда...

5
  • 1
    Аналогичный вопрос в англоязычной версии: stackoverflow.com/questions/199333/…
    – zed
    16 апр 2016 в 21:03
  • 5
    Можно. См., например Built-in Functions to Perform Arithmetic with Overflow Checking
    – avp
    16 апр 2016 в 21:07
  • 1
    @avp эта группа builtins появилась только в GCC5, которого ещё очень мало вокруг. Clang 3.7 этого не знает, наверно, появилось с 3.9. Хорошо, что сделали, но ещё рано залагаться на них. :(
    – Netch
    17 апр 2016 в 7:17
  • ассоциация: stackoverflow.com/questions/199333/… 14 мар 2018 в 7:49
  • можно указать флаг -ftrapv (при переполнении знаковых целочисленных вызывается abort()), для clang предпочтительно использовать санитайзер: -fsanitize=signed-integer-overflow (stackoverflow.com/a/20851708/5571818)
    – LXA
    2 июл 2020 в 7:55

6 ответов 6

15

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

Т.е. получается примерно так - сам C/C++ встроенных переносимых средств обнаружения переполнения не имеет.

Но всегда можно использовать дополнительные методы, которые позволят по данным операндам выяснить, будет ли переполнение при выполнении операции. Масса таких вещей описана в книге Г. Уоррена Алгоритмические трюки для программистов.

Ну и как иллюстрация, насколько легко пропустить это переполнение - у Страуструпа в Программирование. Принципы и практика... есть одна программка, в которой вычислялся ряд для ex, что ли - и она у него в разнос шла. Он честно написал, что раньше, мол, я думал, что это связано с потерей точности в double, и вроде даже так и написал в первом издании книги, а потом ко второму изданию дошло, что на самом деле это переполнение целочисленных значений при вычислении факториала. Если уж даже Страуструп... :)

12

Действие по умолчанию зависит от процессора, компилятора и настроек. На MIPS, например, его "классические" компиляторы превращали сложение знаковых в команду add, которая генерирует исключение при переполнении, а беззнаковых - addu, которая не генерирует. Но gcc, clang уже такого не делали, всё через addu. На x86 - родные команды add, sub игнорируют переполнение (точнее, ставят флаг CF или OF, но не генерируют исключение).
Компиляторы современного типа считают, что переполнения в операциях с целыми со знаком не должно быть, иногда из-за этого возникают интересные эффекты - вот самый убойный пример из тех, что я видел. Стандарт тут действует по принципу "мы вам даём возможность писать максимально эффективно, потому что это C, а не учебный язык, а защита от кривостей - ваша проблема". В отличие от них, для целых без знака определено поведение как для арифметики по модулю 2**N, где N - количество битов в значении. Это различие возникло из-за того, что не было извесно в общем случае, какое представление целых со знаком будет из набора: прямой код (sign and magnitude), обратный код (1ʼs complement), дополнительный код (0ʼs complement, но на устоявшемся уже жаргоне twoʼs complement), это сейчас можно смело говорить, что кроме дополнительного кода вариантов нет. Но потом это различие было реально заабьюзено на возможность делать хитрые оптимизации на основании предположения о непереполнении.

Для C++ есть, например, библиотечка (шаблонный заголовочный файл) SafeInt3 от Microsoft, под свободной лицензией; ею можно покрыть все основные операции, хотя она весьма стара, не использует специфику процессоров (даже x86) и оттого во многих случаях неэффективна - там, где достаточно одного OF или CF, или overflow builtins от GCC, она городит много сложных расчётов.

Для C придётся всё писать вручную, заменяя обычные операции на свои эквиваленты функциями или макросами.

Про новые встроенные функции последних gcc и clang (__builtin_add_overflow, __builtin_mul_overflow и вся группа) уже писали. На них можно всегда получить урезанное (оно же wrapped) значение операции (как в 16 битах 30000 + 30000 -> -5536), и признак переполнения, и можно получать каждый из них безопасно (не будет неожиданных оптимизаций). Но и без них можно сделать достаточно неплохо. Например, в случае сложения двух int, проверка вида a > INT_MAX - b, если b > 0, иначе a < INT_MIN - b, достаточна, чтобы проверить разрешимость сложения. Самое тяжёлое тут проверка умножения без поддержки компилятора: единственным всегда работающим вариантом считается проверка делением, а это очень дорого. Я считаю, что overflow builtins надо ввести во все стандарты (кроме нынешнего набора add, mul, div добавить ещё shl).

5

Хоть и не приветствуются ответы только из ссылок, но вот нашел хороший материал (в т.ч. там код проверок, вызовет ли переполнение (более обще -- безопасно ли) сложение, вычитание, умножение и деление целых):

https://www.securecoding.cert.org/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow

с обсуждениями и т.п.

Update

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

Проверка перед сложением:

#include <limits.h>

void f(signed int si_a, signed int si_b) {
  signed int sum;
  if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
      ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
    /* Handle error */
  } else {
    sum = si_a + si_b;
  }
  /* ... */
}

Проверка перед вычитанием:

#include <limits.h>

void func(signed int si_a, signed int si_b) {
  signed int diff;
  if ((si_b > 0 && si_a < INT_MIN + si_b) ||
      (si_b < 0 && si_a > INT_MAX + si_b)) {
    /* Handle error */
  } else {
    diff = si_a - si_b;
  }

  /* ... */
}

Проверка перед умножением:

#include <limits.h>

void func(signed int si_a, signed int si_b) {
  signed int result; 
  if (si_a > 0) {  /* si_a is positive */
    if (si_b > 0) {  /* si_a and si_b are positive */
      if (si_a > (INT_MAX / si_b)) {
        /* Handle error */
      }
    } else { /* si_a positive, si_b nonpositive */
      if (si_b < (INT_MIN / si_a)) {
        /* Handle error */
      }
    } /* si_a positive, si_b nonpositive */
  } else { /* si_a is nonpositive */
    if (si_b > 0) { /* si_a is nonpositive, si_b is positive */
      if (si_a < (INT_MIN / si_b)) {
        /* Handle error */
      }
    } else { /* si_a and si_b are nonpositive */
      if ( (si_a != 0) && (si_b < (INT_MAX / si_a))) {
        /* Handle error */
      }
    } /* End if si_a and si_b are nonpositive */
  } /* End if si_a is nonpositive */

  result = si_a * si_b;
}

Проверка перед делением:
(или вычислением остатка)

#include <limits.h>

void func(signed long s_a, signed long s_b) {
  signed long result;
  if ((s_b == 0) || ((s_a == LONG_MIN) && (s_b == -1))) {
    /* Handle error */
  } else {
    result = s_a / s_b;
  }
  /* ... */
}

Ну, если кому не лень вытащить оттуда остальной (относящийся к вопросу ТС) код (а также описание всех существенных моментов) сюда и аккуратно его оформить, милости просим.

1
  • Модераторы, я бы с удовольствием сделал его общим, только не вижу, как этого добиться...
    – avp
    19 апр 2016 в 23:07
1

В Visual C++ можно использовать функции из Intsafe.h, например для умножения:

#include <stdlib.h>
#include <stdio.h>
#include <windows.h>
#include <tchar.h>
#include <Intsafe.h>

int _tmain(int argc, _TCHAR* argv[])
{
    ULONGLONG  a=100000000000, b=5000000000, c;

    HRESULT hr = ULongLongMult(a,b,&c);

    if(SUCCEEDED(hr)) printf("Result is %llu",c);
    else if(hr == INTSAFE_E_ARITHMETIC_OVERFLOW) printf("Overflow");        

    return 0;
}

Данные функции определены как inline, и их реализация зависит от архитектуры. Функция ULongLongMult:

  • На 64-битных архитектурах использует intrinsic-функцию компилятора _umul128, поэтому должна быть довольно эффективной.

  • На 32-битных архитектурах использует специальный алгоритм расчета с разбиением чисел на 2 32-битных части (результат вычисляется по формуле a.b * c.d = (a*c*2^64) + (a*d*2^32) + (b*c*2^32) + (b*d)), и переполнение обнаруживается проверкой определенных битов в промежуточных результатах.

1

Чем плохи эти методы? Да они требуют два раза вычислять одно и то же! По сути вы должны высчитать сам факт того что при сложении или вычитании выйдет за пределы... Но можно иначе постфактум... ведь в случае переполнения вылетевшие биты отбрасываются иначе бы никакого переполнения не было! Поэтому ясно, что если например результат должен уменьшиться, а он увеличился при ненулевой добавке, или наоборот, то это и есть переполнение.

int a = 2147483645, b = 3, c;
c=a+b;

то каково будет при этом с? Ответ -1! Ну я так специально подобрал... Но факт тот, что -1 дб больше чем а, но он меньше. Это критерий. Переполнение так же может произойти, если мы попытаемся инвертировать знак у наименьшего отрицательного числа... ну это не надо считать, а просто проверить!

int a = -2147483648, b;
b=-а;

Чему будет равно в? Оно будет равно опять же -1. Но оно дб положительным!!! Фактически в бинарном представлении оно не поменялось. Операция смены знака эквивалентна 2-ум операциям: инверсия и +1. Переполнение происходит при добавлении 1! Потому что если инвертировать указанное число, то мы получим максимальное положительное число, к которому уже нельзя добавлять 1. Формально это перенос старшего бита... Вот критерий переполнения при смене знака. Преимущество этого метода в том, что если у вас всё нормально, то результат уже есть и его не надо считать второй раз... При умножении и делении тоже самое. Если мы умножаем на число большее 1 это все числа кроме нуля, то результат дб больше, а не меньше 1-го сомножителя... А при делении меньше. А дальше вы сами сообразите как написать код... Этот подход даёт ускорение вычислений особенно когда подсчитываешь сумму или произведение. Что имеет место в расчётах.И ещё... желателен другой критерий того когда надо проверять. А делать надо не при любом вычислении, а только когда вычисления происходят вблизи границ представимого диапазона чисел для результита. Потому что если далеко от границ, то проверка излишняя. Вот желательно это так же учесть. Вот это как раз непросто...

1
  • Если тип int — 32-битный, то поведение приведённого кода: int a = 2147483645, b = 3, c; c=a+b; неопределенно. Ибо переполнение знакового целого вызывает неопределённое поведение.
    – wololo
    16 июн 2020 в 15:59
0

На самом деле это проблема многих компилируемых языков. Платформенно-независимые методы - куча кода. Может оказаться быстрее считать во float/double, а перед round проверять границы. Да, когда каждый такт проца считаешь - не прокатит, но тогда уже и не грех ассемблерную вставку вставить: в любом случае, если из платформы надо выжимать максимум поизводительности - о переносимости можно забыть. Как вариант - если нужно считать целочисленно, то

  1. используем метод, предложенный выше Анатолием
  2. промежуточные результаты храним в переменной, которая минимум вдвое длиннее, чем требуется для представления диапазона данных (например, если данные у Вас 32 бита, то промежуточные расчёты ведём в int64_t). Тогда проверка на выход за представимые границы перед приведением к более "короткому" типу становится тривиальной. Но и это ещё не всё. Если нужно сохранить точность при наличии промежуточных операций деления, то Вам надо не просто положить, например, 16-битное число в 32-битную переменную, а ещё и сдвинуть его, скажем, на 8 бит влево, а после всех расчётов - обратно вправо, чтобы оставть "лишние" биты на как слева (на случай переполнения), так и справа (на случай потери точности при делениях). И количество этих бит надо считать, чтобы во всём диапазоне входных данных на улететь в переполнение/потерю точности на всех промежуточных шагах. Так что "подводных камней" у целочисленной арифметики хватает. Право слово, если ресурсы позволяют - проще считать во float.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.