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

Например, нам необходимо сложить две переменные типа int, результат сложения которых будет приводить к переполнению. Что можно сделать?

Итак, что я делал на данный момент:

#include <iostream>
#include <limits>

int add (int x, int y)
{
   if  ((x > 0 && y > 0 && x > (std::numeric_limits <int>::max () - y)) ||
   (x < 0 && y < 0 && x < (std::numeric_limits <int>::min () - y)))
   {
      std::cout << "Error" << std::endl;
      exit (EXIT_FAILURE);
   }
   else
   {
      return (x + y);
   }
}

int main ()
{
   int a = add (25, 10);
   std::cout << a << std::endl; 
   int b = add (std::numeric_limits <int>::max (), std::numeric_limits <int>::max ());
   return 0;
}

Всё это, разумеется, можно шаблонизировать:

template <typename T>
T add (T x, T y)
{
   if  ((x > 0 && y > 0 && x > (std::numeric_limits <T>::max () - y)) ||
   (x < 0 && y < 0 && x < (std::numeric_limits <T>::min () - y)))
   {
      std::cout << "Error" << std::endl;
      exit (EXIT_FAILURE);
   }
   else
   {
      return (x + y);
   }
}

Но является ли этот способ оптимальным? Может, есть что-то лучше?

Здравствуйте, Аноним, Вы писали:

А>Но является ли этот способ оптимальным? Может, есть что-то лучше?

bool add(int* result, int x, int y)
{
  *result = x + y;
  return *result >= x && *result >= y;
}

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

Да блин очень просто.
Результат сложения должен быть БОЛЬШЕ каждого из слагаемых.

Результат вычитания должен быть меньше уменьшаемого.

Здравствуйте, MasterZiv, Вы писали:

MZ>Да блин очень просто.
MZ>Результат сложения должен быть БОЛЬШЕ каждого из слагаемых.

MZ>Результат вычитания должен быть меньше уменьшаемого.

(-1)+(-1)

Здравствуйте, Аноним, Вы писали:

А>Например, нам необходимо сложить две переменные типа int, результат сложения которых будет приводить к переполнению. Что можно сделать?

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

Здравствуйте, Аноним, Вы писали:

А> Может, есть что-то лучше?
Можно сэкономить время, и взять, например, готовый SafeInt, где все эти условия уже расписаны для различных комбинаций типов и операций.

А> Как можно наиболее грамотно проверить результат выполнения арифметической операции (допустим, сложения) на предмет выхода за пределы,
Вообще, у процессора есть способ определить произошло или нет переполнение при выполнении операции. Но если исключить ассемблерные вставки, то узнать об этом из С кода нельзя. Поэтому особенно нет других вариантов кроме как проверять диапазоны вручную. Разве что имеет смысл производить вычисления, если это возможно, с типами большей разрядности и проверять на переполнение в момента преобразования к типу с меньшей разрядностью — так код получается чуть проще и содержит чуть меньше операций:

short add (short x, short y) {
  int tmp = x + y; // можно отложить проверку если short действительно короче чем int
  if (tmp < std::numeric_limits<short>::min() || tmp > std::numeric_limits<short>::max())
    throw "overflow";
  return tmp;
}

Здравствуйте, Аноним, Вы писали:

А>Как можно наиболее грамотно проверить результат выполнения арифметической операции (допустим, сложения) на предмет выхода за пределы, предоставляемые данными фундаментальными типами?

Наиболее грамотно — осознать, что знаковые числа порядка 2*10^9 (32бит) и 4*10^18 (64бит) от хорошей жизни в ходе работы не появятся.
Поэтому, вместо того, чтобы ходить по лезвию пороховой бочки, можно договориться, что все входные, выходные и промежуточные данные не вылезут за 10^9 или 10^18.

Тогда бит переполнения окажется внутри разрядной сетки числа, а не вылетит в бит переноса процессора. Его можно будет легко диагностировать, причём на поздних стадиях (а не только непосредственно сразу операции — тем более, что такая проверка на ассемблере будет обламывать оптимизатора).

Здравствуйте, Аноним, Вы писали:

А>Как можно наиболее грамотно проверить результат выполнения арифметической операции (допустим, сложения) на предмет выхода за пределы, предоставляемые данными фундаментальными типами?

А>Например, нам необходимо сложить две переменные типа int, результат сложения которых будет приводить к переполнению. Что можно сделать?

Как-то так:

template<typename T>
T add (T x, T y)
{
  T result = x + y;
  assert(y > 0 == result > x);
  return result;  
}

Будет работать и для знаковых и для беззнаковых.

Здравствуйте, Pzz, Вы писали:

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

Это не работает, если хотя бы одно из слагаемых меньше нуля.

Здравствуйте, Mystic, Вы писали:

M>

M>bool add(int* result, int x, int y)
M>{
M>  *result = x + y;
M>  return *result >= x && *result >= y;
M>}
M>

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

Кстати, по истории вопроса.

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

В Intel есть флаг возникновения переполнения.
Но не помню, можно ли включить обработку этого флага в виде аппаратного прерывания.
Вроде бы было нельзя. Да в интеле традиционно было одно только прерывание, и то
маскируемое. Это конечно было давно, в прошлом веке интел был совсем другой.
Всякие переходы по OF или не OF есть. Но их нужно чтобы компилятор вставлял
после каждой операции. С-шный не будет, естественно. Fortran-овые вставляли.
В других языках (во многих) тоже была такая практика.

> Наиболее грамотно — осознать, что знаковые числа порядка 2*10^9 (32бит) и
> 4*10^18 (64бит) от хорошей жизни в ходе работы не появятся.

Ты знаешь, вот как раз сейчас пошёл наверное уже второй месяц, как мы
ищем неуловимый баг именно переполнения. На границе 32 бит.

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

Здравствуйте, MasterZiv, Вы писали:

>> Наиболее грамотно — осознать, что знаковые числа порядка 2*10^9 (32бит) и
>> 4*10^18 (64бит) от хорошей жизни в ходе работы не появятся.

MZ>Ты знаешь, вот как раз сейчас пошёл наверное уже второй месяц, как мы
MZ>ищем неуловимый баг именно переполнения. На границе 32 бит.

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

Взять шелл-хостинг на S/390 и прогнать там? Для чисел со знаком там это очень легко делается, почти автоматически.
Включить один бит в PSW и все результаты с переполнением будут вызывать исключение.

Здравствуйте, Кодт, Вы писали:

А>>Как можно наиболее грамотно проверить результат выполнения арифметической операции (допустим, сложения) на предмет выхода за пределы, предоставляемые данными фундаментальными типами?

К>Наиболее грамотно — осознать, что знаковые числа порядка 2*10^9 (32бит) и 4*10^18 (64бит) от хорошей жизни в ходе работы не появятся.
К>Поэтому, вместо того, чтобы ходить по лезвию пороховой бочки, можно договориться, что все входные, выходные и промежуточные данные не вылезут за 10^9 или 10^18.

К сожалению, к уже написанному, а тем более к чужому коду это совет уровня "Мышки, станьте ёжиками".
И вообще это неконструктивно — терять несколько бит на ровном месте.

К>Тогда бит переполнения окажется внутри разрядной сетки числа, а не вылетит в бит переноса процессора. Его можно будет легко диагностировать, причём на поздних стадиях

От ситуаций типа (60000*60000)/15000 это не защитит.

К> (а не только непосредственно сразу операции — тем более, что такая проверка на ассемблере будет обламывать оптимизатора).

Ну вот и остаётся что-то вроде названного тут SafeInt, но лучше на ассемблере.

Здравствуйте, MasterZiv, Вы писали:

MZ>Да блин очень просто.
MZ>Результат сложения должен быть БОЛЬШЕ каждого из слагаемых.
MZ>Результат вычитания должен быть меньше уменьшаемого.

Это неполная логика, пригодная только для чисел без знака. (Я уж молчу, что тут везде надо "больше или равно".)

Логика большинства современных процессоров выглядит следующим образом:

1. При сложении чисел со знаком, переполнение диагностируется, если у обоих слагаемых совпадают старшие биты, но отличаются от старшего (после переноса) бита результата.
Например, в 8 битах:
0x30 + 0x30 == 0x60 — нет переполнения (48 + 48 == 96);
0x60 + 0x60 == 0xC0 — есть переполнение (у слагаемых старший бит был равен 0, у суммы — 1);
0xD0 + 0xD0 == 0x1A0 — нет переполнения (-48 + (-48) == -96);
0xA0 + 0xA0 == 0x140 — есть переполнение (у слагаемых старший бит был равен 1, у суммы — 0);
0x10 + 0xF0 == 0x100 — нет переполнения (16 + (-16) == 0).
Если слагаемые имели разные знаки, переполнения не может быть в принципе.
Признак переполнения ставится во флаге условия V (в x86 он зовётся OF).
Некоторые процессоры также знают флаг "истинного знака результата" (обозначается S; не путать с N — видимый знак, он же SF в x86). При этом выполняется по определению, что N xor V == S.
Проверки результата сравнения со знаком — такие, как jge, jlt в x86 — проверяют истинный знак, поэтому их условия выглядят как (N xor V) == 0 или 1 (в x86, (SF xor OF) == 0 или 1).

2. При вычитании чисел со знаком, повторяется логика сложения, но знак вычитаемого инвертируется.
Таким образом, при вычитании чисел с одним и тем же знаком переполнение невозможно.
Но при разных — возможно (0x50 — 0xB0 == 0xA0, например).
Флаг V (OF) ставится в соответствии с исправленной таким образом логикой.

3. Для чисел без знака, признаком переполнения служит C==1 (CF==1) одинаково для сложения и вычитания (на процессорах, где вычитание с заёмом, как в x86).
Для процессоров, где вычитание с переносом (как в Mostek 6502), при сложении надо проверять на C==1, а при вычитании — на C==0.

Поэтому простейший вариант анализа на переполнение без поддержки аппаратуры выглядит примерно так:

int checked_add(int a, int b) {
  int sum = a + b;
  int ssd = a ^ b; // на самом деле нам нужен только старший бит
  if ((ssd >= 0) && ((ssd ^ sum) < 0))
    throw integer_overflow();
  return sum;
}

Разумеется, при поддержке ассемблера это будет проще:

int checked_add(int a, int b) {
  __asm__((
     " add %0,%1\n"
     " jo overflowed"
     : "=0" (a): "r"(a), "r"(b): "flags"
  ));
  return a;
overflowed:
  throw integer_overflow();
}

(тут надо тщательно вычистить реализацию, но идея должна быть понятна)

> Взять шелл-хостинг на S/390 и прогнать там?

Я бы рад, только сначала нужно перевести всё на
S/390, скомпилять и отладить там нехилую программулину,
специфичную пока что только для Linux/64бит



Для чисел со знаком там это очень
> легко делается, почти автоматически.

А без знака ?

> Включить один бит в PSW и все результаты с переполнением будут вызывать исключение.

Ты имееш в виду на Intel, или это S/390 ?

Здравствуйте, MasterZiv, Вы писали:


>> Взять шелл-хостинг на S/390 и прогнать там?

MZ>Я бы рад, только сначала нужно перевести всё на
MZ>S/390, скомпилять и отладить там нехилую программулину,
MZ>специфичную пока что только для Linux/64бит

MZ>

Linux на S/390 чуть ли не основная платформа, а 64-битность в этой архитектуре есть без проблем (и даже прямее, чем в x86).

Нужна ли вам тут ещё какая-то инфраструктура, я не знаю. Но можно её сэмулировать.

MZ>Для чисел со знаком там это очень
>> легко делается, почти автоматически.
MZ>А без знака ?

А без знака там, увы, никакого автомата нет.
Вообще там арифметика сделана в очень старом стиле. Никаких привычных сейчас NZVC нет. Есть двухбитовое поле CC. Для команды беззнакового сложения (ALR, AL), вычитания (SLR, SL) ставятся condition codes: один из битов — переполнение и второй — равенство результата 0, но никакого автомата исключения по переполнению нет.

Для знакового сложения CC ставится иначе (переполнение, иначе больше, меньше или равно 0).

>> Включить один бит в PSW и все результаты с переполнением будут вызывать исключение.
MZ>Ты имееш в виду на Intel, или это S/390 ?

S/390. PSW (Processor Status Word) это в терминах x86 комбинация Flags, Instruction Pointer и части Control Registers.

Здравствуйте, MasterZiv, Вы писали:

MZ>специфичную пока что только для Linux/64бит

В gcc, кстати говоря, есть ключ -ftrapv который автоматически вставляет проверки на переполнения при сложении, вычитании и умножении.
К сожалению, он вроде как совсем depricated, несовместим с оптимизацией, но как-то пользоваться всё ещё можно:

extern "C" int __addvdi3(int a, int b) { // функция проверки, будет вызываться при сложении двух int
    long long tmp = (long long)a + b;
    int res = a + b;
    if (tmp != res) { // или другой способ проверки
        fprintf(stderr, "Overflow!\n"); // желаемое действие при переполнении
        raise(SIGABRT);
    }
    return res;
}

Соответственно, код функции addvdi3 компилируем без ключа -ftrapv (иначе рекурсия), а тестируемый с -ftrapv и, возможно, с -fwrapv.
После чего 3+5 будет работать нормально, а вот (std::numeric_limits <int>::max() + 1) уже выдавать ошибку.

Вообще, конечно же, функция addvdi3 (и другие) должна предоставляться компилятором, но вследствие того, что поддержка этого дела заброшена, на 64-х битных архитектурах она по умолчанию ничего осмысленного не проверяет, приходится писать самому. Да, и нужную версию компилятора взять необходимо — например, у меня на 4.2 и 4.3 вызовы проверки вообще не генерируются, а вот на 4.4 и 4.5 работают.

Здравствуйте, watch-maker, Вы писали:

WM>К сожалению, он вроде как совсем depricated, несовместим с оптимизацией, но как-то пользоваться всё ещё можно:
WM>extern "C" int __addvdi3(int a, int b) { // функция проверки, будет вызываться при сложении двух int

О, хорошая подсказка — нашлась статья мыщъх'а по этому поводу.
Функция safe_add() у него в статье некорректна — работает только для неотрицательных чисел.
Для отрицательных надо или делать развилку по знаку, или брать другой метод (как мой с xor'ами).

Интересно, чем определяется название функции? Потому что на FreeBSD/i386 мне в таком же случае затребовали __addvsi3. Я правильно понимаю, что __addvdi3 это для двойной длины (64 бита)?
Вызовы этой функции действительно режутся при уровне оптимизации хотя бы 1-м. Обидно.

WM> raise(SIGABRT);

SIGFPE, хотя бы. Потому что оно вызывается и при целочисленном делении на 0, хотя это совсем не "FP" E.

WM>Вообще, конечно же, функция addvdi3 (и другие) должна предоставляться компилятором, но вследствие того, что поддержка этого дела заброшена, на 64-х битных архитектурах она по умолчанию ничего осмысленного не проверяет, приходится писать самому. Да, и нужную версию компилятора взять необходимо — например, у меня на 4.2 и 4.3 вызовы проверки вообще не генерируются, а вот на 4.4 и 4.5 работают.

Наверно, в таком случае не заброшена, а слишком медленно развивается.