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

Например, нам необходимо сложить две переменные типа 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);
   }
}


Но является ли этот способ оптимальным? Может, есть что-то лучше?
Re: Проверка выполнения сложения
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 06.04.12 12:47
Оценка: +1 -1
Здравствуйте, Аноним, Вы писали:

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


bool add(int* result, int x, int y)
{
  *result = x + y;
  return *result >= x && *result >= y;
}
Re[2]: Только unsigned int
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 06.04.12 12:49
Оценка:
Re: Проверка выполнения сложения
От: MasterZiv СССР  
Дата: 06.04.12 13:03
Оценка:
> Как можно наиболее грамотно проверить результат выполнения арифметической
> операции (допустим, сложения) на предмет выхода за пределы, предоставляемые
> данными фундаментальными типами?

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

Результат вычитания должен быть меньше уменьшаемого.
Posted via RSDN NNTP Server 2.1 beta
Re[2]: Проверка выполнения сложения
От: Ops Россия  
Дата: 06.04.12 13:21
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>Да блин очень просто.

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

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


(-1)+(-1)
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Re: Проверка выполнения сложения
От: Pzz Россия https://github.com/alexpevzner
Дата: 06.04.12 14:29
Оценка:
Здравствуйте, Аноним, Вы писали:

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


Если не было переполнения, результат сложения будет больше или равен любого из слагаемых (равен, если одно из слагаемых равно 0). Если было переполнения, он будет меньше любого из них. Поэтому достаточно сравнить только с одним, с обеими слагаемыми сравнивать не обязательно.
Re: Проверка выполнения сложения
От: watch-maker  
Дата: 06.04.12 14:46
Оценка:
Здравствуйте, Аноним, Вы писали:

А> Может, есть что-то лучше?

Можно сэкономить время, и взять, например, готовый 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;
}
Re: Проверка выполнения сложения
От: Кодт Россия  
Дата: 09.04.12 21:07
Оценка: 1 (1) +2 -1
Здравствуйте, Аноним, Вы писали:

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


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

Тогда бит переполнения окажется внутри разрядной сетки числа, а не вылетит в бит переноса процессора. Его можно будет легко диагностировать, причём на поздних стадиях (а не только непосредственно сразу операции — тем более, что такая проверка на ассемблере будет обламывать оптимизатора).
Перекуём баги на фичи!
Re: Проверка выполнения сложения
От: rg45 СССР  
Дата: 10.04.12 06:13
Оценка: 3 (1)
Здравствуйте, Аноним, Вы писали:

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


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


Как-то так:

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


Будет работать и для знаковых и для беззнаковых.
--
Справедливость выше закона. А человечность выше справедливости.
Re[2]: Проверка выполнения сложения
От: rg45 СССР  
Дата: 10.04.12 09:58
Оценка:
Здравствуйте, Pzz, Вы писали:

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


Это не работает, если хотя бы одно из слагаемых меньше нуля.
--
Справедливость выше закона. А человечность выше справедливости.
Re[3]: Только unsigned int
От: rg45 СССР  
Дата: 10.04.12 11:17
Оценка:
Здравствуйте, Mystic, Вы писали:

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


Для беззнаковых типов все еще проще — вполне хватило бы сравнения результата только с одним из операндов. Но как я понял, ТС не устраивает такое ограничение — ему нужна максимально простая но в то же время универсальная проверка, которая будет работать со знаковыми и беззнаковыми, положительными и отрицательными числами.
--
Справедливость выше закона. А человечность выше справедливости.
Re[4]: Только unsigned int
От: MasterZiv СССР  
Дата: 10.04.12 11:52
Оценка:
Кстати, по истории вопроса.

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

В Intel есть флаг возникновения переполнения.
Но не помню, можно ли включить обработку этого флага в виде аппаратного прерывания.
Вроде бы было нельзя. Да в интеле традиционно было одно только прерывание, и то
маскируемое. Это конечно было давно, в прошлом веке интел был совсем другой.
Всякие переходы по OF или не OF есть. Но их нужно чтобы компилятор вставлял
после каждой операции. С-шный не будет, естественно. Fortran-овые вставляли.
В других языках (во многих) тоже была такая практика.
Re[2]: Проверка выполнения сложения
От: MasterZiv СССР  
Дата: 11.04.12 08:59
Оценка:
> Наиболее грамотно — осознать, что знаковые числа порядка 2*10^9 (32бит) и
> 4*10^18 (64бит) от хорошей жизни в ходе работы не появятся.

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

Ты не представляешь, на сколько было бы легче, если были бы аппаратные
прерывания по этому поводу.
Posted via RSDN NNTP Server 2.1 beta
Re[3]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 11.04.12 12:20
Оценка:
Здравствуйте, MasterZiv, Вы писали:

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

>> 4*10^18 (64бит) от хорошей жизни в ходе работы не появятся.

MZ>Ты знаешь, вот как раз сейчас пошёл наверное уже второй месяц, как мы

MZ>ищем неуловимый баг именно переполнения. На границе 32 бит.

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

MZ>прерывания по этому поводу.

Взять шелл-хостинг на S/390 и прогнать там? Для чисел со знаком там это очень легко делается, почти автоматически.
Включить один бит в PSW и все результаты с переполнением будут вызывать исключение.
The God is real, unless declared integer.
Re[2]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 11.04.12 12:25
Оценка:
Здравствуйте, Кодт, Вы писали:

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


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

К>Поэтому, вместо того, чтобы ходить по лезвию пороховой бочки, можно договориться, что все входные, выходные и промежуточные данные не вылезут за 10^9 или 10^18.

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

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


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

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


Ну вот и остаётся что-то вроде названного тут SafeInt, но лучше на ассемблере.
The God is real, unless declared integer.
Re[2]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 11.04.12 13:01
Оценка: 6 (1)
Здравствуйте, 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();
}


(тут надо тщательно вычистить реализацию, но идея должна быть понятна)
The God is real, unless declared integer.
Re[4]: Проверка выполнения сложения
От: MasterZiv СССР  
Дата: 11.04.12 14:38
Оценка:
> Взять шелл-хостинг на S/390 и прогнать там?

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



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

А без знака ?

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


Ты имееш в виду на Intel, или это S/390 ?
Posted via RSDN NNTP Server 2.1 beta
Re[5]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 11.04.12 15:43
Оценка:
Здравствуйте, 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.
The God is real, unless declared integer.
Re[5]: Проверка выполнения сложения
От: watch-maker  
Дата: 11.04.12 17:05
Оценка: 14 (2)
Здравствуйте, 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 работают.
Re[6]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 11.04.12 19:07
Оценка:
Здравствуйте, 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 работают.


Наверно, в таком случае не заброшена, а слишком медленно развивается.
The God is real, unless declared integer.
Re[3]: Проверка выполнения сложения
От: rg45 СССР  
Дата: 11.04.12 19:47
Оценка:
Здравствуйте, netch80, Вы писали:

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


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


Не находишь, что мой вариант
Автор: rg45
Дата: 10.04.12
проще и универсальнее? Универсальнее в том плане, что годится и для знаковых и для беззнаковых типов.

P.S. Предложил еще позавчера утром, никто и внимания не обратил, обидно
--
Справедливость выше закона. А человечность выше справедливости.
Re[6]: Проверка выполнения сложения
От: MasterZiv СССР  
Дата: 12.04.12 06:15
Оценка:
> А без знака там, увы, никакого автомата нет.

Вот странно. Чем беззнаковые им так не угодили ?
Posted via RSDN NNTP Server 2.1 beta
Re[4]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 12.04.12 06:27
Оценка: 1 (1) +1
Здравствуйте, rg45, Вы писали:

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

[...]

R>Не находишь, что мой вариант
Автор: rg45
Дата: 10.04.12
проще и универсальнее? Универсальнее в том плане, что годится и для знаковых и для беззнаковых типов.


Загнал в автоматический тест — вроде да, отклонений не замечено. Проверка такого рода будет работать.

С другой стороны, надо ещё измерить, какой из этих вариантов эффективнее в каком случае. Визуально для человека твой однозначно проще. Но мне кажется, что для ARM, например, мой соберётся в более короткую и прямую последовательность. Также у тебя проверка на (y>0) избыточна для беззнаковых; если заменить на >= в обеих сторонах, то левая для беззнаковых вырождается в true и экономится операция сравнения, но компилятор может пожаловаться на condition is always true.

R>P.S. Предложил еще позавчера утром, никто и внимания не обратил, обидно


Почему не заметил — не знаю. Видимо, слишком увлёкся опровержением.
Поставил +1 и 2.

Интересно, почему MS в своём SafeInt не использует такие простые приёмы. Вместо этого, например, для двух 32-разрядных чисел они складывают используя 64 бита (причём это даже при компиляции в 32-битный код) и проверяют результат на выход за границы. И вообще у них пример того, как не надо писать на C++...
The God is real, unless declared integer.
integer overflow
Re[4]: Проверка выполнения сложения
От: MasterZiv СССР  
Дата: 12.04.12 06:31
Оценка: :)
> P.S. Предложил еще позавчера утром, никто и внимания не обратил, обидно

Почему ? Я обратил, хороший вариант. (тебе легче ?)
Posted via RSDN NNTP Server 2.1 beta
Re[7]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 12.04.12 06:50
Оценка:
Здравствуйте, MasterZiv, Вы писали:

>> А без знака там, увы, никакого автомата нет.


MZ>Вот странно. Чем беззнаковые им так не угодили ?


Наверно, решили, что для них и ручной проверки будет достаточно — написать BC 12, label после команды. А ещё, что имеет смысл отделить целевые команды от вспомогательных, которые в основном адресные и потому им переполнение не так важно, а автоматическая проверка проверяет или не то, или не так.

А вообще учти, что эта разработка зафиксировалась в 1964-м году, когда ещё теория была очень слаба. Я не могу сказать, в какой машине и когда была придуманы операции типа ADC и универсальная считалочка NZVC, но до неё не было варианта делать знаковые и беззнаковые операции унифицированно. Подозреваю, что она появилась с PDP-11 (1970-й год), но фактов у меня нет.
Что они после этого не ввели более привычную нам арифметику — не удивляюсь, если родная пусть странно, но работает. Вообще там система команд существенно не менялась, даже таких мелких реформ, как в amd64 по отношению к push/pop, не делалось; можно на ходу переключаться между режимами адресации на 24/31/64 бита без шлюзов, а возможность работы с 64-битными данными AFAIR зависит от модели, но не от режима.
В S/360 и потомках нет аналога ADC (сложение двух операндов и флага переноса), его надо эмулировать. Зато отдельные команды для знаковой арифметики с автодетектом переполнения.

P.S. Кажется, я один из немногих вообще на RSDN, кто эту линию (S/360...S/390) знает и в чём-то любит

P.S.[2]. Я бы вообще сделал что-то вроде того, как сейчас в стандарте IEEE754 — залипающий (sticky) флаг переполнения (в дополнение к обычному).
The God is real, unless declared integer.
Re[5]: Проверка выполнения сложения
От: rg45 СССР  
Дата: 12.04.12 07:35
Оценка: :)
Здравствуйте, MasterZiv, Вы писали:


>> P.S. Предложил еще позавчера утром, никто и внимания не обратил, обидно


MZ>Почему ? Я обратил, хороший вариант. (тебе легче ?)


Вот теперь легче
--
Справедливость выше закона. А человечность выше справедливости.
Re[5]: Проверка выполнения сложения
От: rg45 СССР  
Дата: 12.04.12 08:23
Оценка:
Здравствуйте, netch80, Вы писали:

N>Также у тебя проверка на (y>0) избыточна для беззнаковых; если заменить на >= в обеих сторонах, то левая для беззнаковых вырождается в true и экономится операция сравнения...


В-о-от! Я это чуть позже тоже сообразил, но уже не стал заморачиваться исправлением. Действительно, если a + b = c, где a, b, c — беззнаковые, то выражение: b >= 0 == c >= a оптимизатор с радостью упростит до c >= a

N>Интересно, почему MS в своём SafeInt не использует такие простые приёмы. Вместо этого, например, для двух 32-разрядных чисел они складывают используя 64 бита (причём это даже при компиляции в 32-битный код) и проверяют результат на выход за границы. И вообще у них пример того, как не надо писать на C++...


Да набирают туда непонятно кого
--
Справедливость выше закона. А человечность выше справедливости.
Re[2]: Улучшенный вариант
От: rg45 СССР  
Дата: 12.04.12 08:37
Оценка:
Здравствуйте, rg45, Вы писали:

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


Улучшенный вариант:

R>
R>template<typename T>
R>T add (T a, T b)
R>{
R>  T c = a + b;
R>  assert(b >= 0 == c >= a);
R>  return c;  
R>}
R>


Теперь если T — беззнаковый тип, то выражение b >= 0 == c >= a оптимизатор сможет упростить до c >= a
--
Справедливость выше закона. А человечность выше справедливости.
Re[5]: Проверка выполнения сложения
От: B0FEE664  
Дата: 12.04.12 08:49
Оценка:
Здравствуйте, netch80, Вы писали:

N>Интересно, почему MS в своём SafeInt не использует такие простые приёмы. Вместо этого, например, для двух 32-разрядных чисел они складывают используя 64 бита (причём это даже при компиляции в 32-битный код) и проверяют результат на выход за границы. И вообще у них пример того, как не надо писать на C++...


А что не так с SafeInt ? (кроме того, что они используют 64 бита для 32-разрядных чисел)
И каждый день — без права на ошибку...
Re[7]: Проверка выполнения сложения
От: watch-maker  
Дата: 12.04.12 09:03
Оценка:
Здравствуйте, netch80, Вы писали:

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

Про буквы SI и DI можно прочитать в Machine Modes. И похоже что именно название и есть причина сломанности на 64-х битной архитектуре, ибо на amd64 нужно в этом случае вызывать SI версию функции, а не DI.
Но вообще, это же служебная функция компилятора, по идее не важно как она называется. Если бы она работала, то и писать бы её не пришлось.
Да, проверял на FreeBSD/amd64 компиляторами gcc от 4.2 до 4.7.
Re[3]: Улучшенный вариант
От: Lorenzo_LAMAS  
Дата: 12.04.12 09:09
Оценка: 15 (2) +2
Не понял, вроде до сих пор есть в стандарте:

If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.


R>>
R>>template<typename T>
R>>T add (T a, T b)
R>>{
R>>  T c = a + b;//если это знаковые целые? 
R>>  assert(b >= 0 == c >= a);
R>>  return c;  
R>>}
R>>
Of course, the code must be complete enough to compile and link.
Re[4]: Улучшенный вариант
От: rg45 СССР  
Дата: 12.04.12 09:18
Оценка:
Здравствуйте, Lorenzo_LAMAS, Вы писали:

L_L>Не понял, вроде до сих пор есть в стандарте:


L_L>

L_L>If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.


R>>>
R>>>template<typename T>
R>>>T add (T a, T b)
R>>>{
R>>>  T c = a + b;//если это знаковые целые? 
R>>>  assert(b >= 0 == c >= a);
R>>>  return c;  
R>>>}
R>>>


Строго говоря, это UB. Но в качестве отладочного диагностического средства для конкретных платформ такое решение может приносить пользу. Повышение надежности работы программ как частный случай неопределенного поведения, о как!
--
Справедливость выше закона. А человечность выше справедливости.
Re[4]: Улучшенный вариант
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 12.04.12 09:19
Оценка: +1
Здравствуйте, Lorenzo_LAMAS, Вы писали:

L_L>Не понял, вроде до сих пор есть в стандарте:


L_L>

L_L>If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.


Это в стандарте.
А реальная практика показывает, что на 99.99% встреченных установок сложение целых в C и C++ выполняется как сложение двух чисел в "дополнении до 2" с игнорированием всех переполнений.

Кстати, именно поэтому непонятно, почему стандарт до сих пор не ввёл средства идентификации таких типичных реализаций. Почему-то куча макросов для возможностей stdatomic или fenv — есть, а такой базы — нет.

Недавно тут видел упоминание ещё одного случая — сдвигов знаковых целых. Опять же формально не определено, что при этом будет. Но практика где-то в таком же количестве случаев использует один и тот же метод.
The God is real, unless declared integer.
Re[5]: Улучшенный вариант
От: Lorenzo_LAMAS  
Дата: 12.04.12 09:23
Оценка:
N>Это в стандарте.
N>А реальная практика показывает, что на 99.99% встреченных установок сложение целых в C и C++ выполняется как сложение двух чисел в "дополнении до 2" с игнорированием всех переполнений.

на самом деле, я не дочитал вопрос автора топика он хочет "оптимальнее", так что да, можно игнорировать UB (на бумаге) и т.д.
Of course, the code must be complete enough to compile and link.
Re[8]: Проверка выполнения сложения
От: MasterZiv СССР  
Дата: 12.04.12 12:56
Оценка:
> А вообще учти, что эта разработка зафиксировалась в 1964-м году, когда ещё
> теория была очень слаба.

Какая теория слаба ?


> P.S. Кажется, я один из немногих вообще на RSDN, кто эту линию (S/360...S/390)

> знает и в чём-то любит

Ну я когда-то работал на наших аналогах 360. Ассемблер соотв. учили и писали на
нём в школе. Был курсовик. Вот только не помню уже, что я писал.
Posted via RSDN NNTP Server 2.1 beta
Re[6]: Проверка выполнения сложения
От: MasterZiv СССР  
Дата: 12.04.12 13:01
Оценка:
> MZ>Почему ? Я обратил, хороший вариант. (тебе легче ?)
>
> Вот теперь легче

Я рад
Posted via RSDN NNTP Server 2.1 beta
Re[7]: Проверка выполнения сложения
От: Lieh_Tzu  
Дата: 12.04.12 14:08
Оценка:
Здравствуйте, MasterZiv, Вы писали:


>> MZ>Почему ? Я обратил, хороший вариант. (тебе легче ?)

>>
>> Вот теперь легче

MZ>Я рад


Я бы рекомендовал использовать участок ассемблерного кода:

asm
{
MOV EAx, x
ADD EAx, y
JC OverflowLabel
}
...
OverflowLabel:
...

Поскольку инструкция процессора ADD выполняет операцию сложения и устанавливает флаг переноса/переполнения.

Смотрим документацию Интел:

"The ADD instruction performs integer addition. It evaluates the result for both signed
and unsigned integer operands and sets the OF and CF flags to indicate a carry (overflow)
in the signed or unsigned result, respectively. The SF flag indicates the sign of
the signed result."
Re[6]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 12.04.12 18:28
Оценка: 8 (2)
Здравствуйте, B0FEE664, Вы писали:

BFE>А что не так с SafeInt ? (кроме того, что они используют 64 бита для 32-разрядных чисел)


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

   SafeInt<int> a, b;
   <...>
   a += b;


дало такое сложение:

 804857a:       8d 04 1e                lea    (%esi,%ebx,1),%eax
 804857d:       39 c6                   cmp    %eax,%esi
 804857f:       0f 9e c2                setle  %dl
 8048582:       c1 eb 1f                shr    $0x1f,%ebx
 8048585:       38 da                   cmp    %bl,%dl
 8048587:       74 45                   je     80485ce <main+0xde>


Это я подпилил на сравнение по методу rg45 вместо прежней конверсии к int64 и выходу за границы:

    template < typename E >
    static void AdditionThrow( const T& lhs, const U& rhs, T& result )
    {
        // 32-bit or less - one or both are signed
        __int32 x = (__int32)lhs;
        __int32 y = (__int32)rhs;
        __int32 tmp = x + y;

        if( (y >= 0) == (tmp >= x))
        {
            result = (T)tmp;
            return;
        }
        
        E::SafeIntOnOverflow();


Упрощение получилось невероятное
Так что беру заявление обратно — оно сейчас такое вполне сойдёт.
Осталось вычистить чисто алгоритмические неадекватности.
The God is real, unless declared integer.
Re[8]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 13.04.12 06:06
Оценка:
Здравствуйте, Lieh_Tzu, Вы писали:

L_T>Я бы рекомендовал использовать участок ассемблерного кода:


1) Баян, я уже это писал в данной теме.
2) Hint: уже давно ARM не менее интересен, чем x86 а есть и другие платформы.
The God is real, unless declared integer.
Re[7]: Проверка выполнения сложения
От: rg45 СССР  
Дата: 13.04.12 10:32
Оценка:
Здравствуйте, netch80, Вы писали:

N>Это я подпилил на сравнение по методу rg45 вместо прежней конверсии к int64 и выходу за границы:


N>
N>    template < typename E >
N>    static void AdditionThrow( const T& lhs, const U& rhs, T& result )
N>    {
N>        // 32-bit or less - one or both are signed
N>        __int32 x = (__int32)lhs;
N>        __int32 y = (__int32)rhs;
N>        __int32 tmp = x + y;

N>        if( (y >= 0) == (tmp >= x))
N>        {
N>            result = (T)tmp;
N>            return;
N>        }
        
N>        E::SafeIntOnOverflow();
N>


Гм, а зачем приводить слагаемые к __int32? А что будет в случае, если T — беззнаковый 32-битный тип? В результате интерпретации беззнакового типа как знакового возможны две ошибочные ситуации:
  1. мы "не замечаем" беззнаковое переполнение. Пример: складываем 0xFFFFFFFFU и 1U, переполнение налицо. Но при интерпретации этих слагаемых как знаковых, получим -1 + 1 = 0, т.е. все Ok;
  2. выдаем "ложное срабатывание". Пример: складываем 0x7FFFFFFFU и 1U — для беззнаковых чисел это нормально, переполнения нет. Но при интерпретации этих слагаемых как знаковых, придем к ошибочному заключению, что было переполнение.
--
Справедливость выше закона. А человечность выше справедливости.
Re[8]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 13.04.12 10:47
Оценка:
Здравствуйте, rg45, Вы писали:

N>>Это я подпилил на сравнение по методу rg45 вместо прежней конверсии к int64 и выходу за границы:


R>Гм, а зачем приводить слагаемые к __int32?


Так в оригинале. Это код конкретно для случая template < typename T, typename U > class AdditionHelper < T, U, AdditionState_CastInt64CheckMinMax >, который назначен вызываться для сложения двух SafeInt<int>. По-нормальному надо было бы породить отдельный шаблонный класс, но мне было облом.

R> А что будет в случае, если T — беззнаковый 32-битный тип?


В данном конкретном SafeInt3.hpp вызовётся метод другого шаблонного класса, который я не трогал.

R> В результате интерпретации беззнакового типа как знакового возможны две ошибочные ситуации:


Это очевидно, но не мой случай.
The God is real, unless declared integer.
Re[2]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 13.04.12 19:45
Оценка: 1 (1)
Здравствуйте, rg45, Вы писали:

R>Как-то так:

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

Всё однако хитрее. Может, я поспешил с похвалой?

Clang 3.0 на 32-битке при -O (и выше) твоё выражение под assert'ом считает истинным *всегда*, соответственно проверка не происходит.
Это независимо от того, используется ли '>' или '>=' в обоих сравнениях.

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

На 64-битке такой проблемы нет, проверки честно производятся.

Проверочная программа, чуть более обширная.

Первый файл (разделено, чтобы не инлайнило):

extern void p(int a, int b);

int main() {
  p(1, 1);
  p(0x30000000, 0x30000000);
  p(0x40000000, 0x40000000);
  p(0x50000000, 0x50000000);
  p(0xB0000000, 0xB0000000);
  p(0xC0000000, 0xC0000000);
  p(0xD0000000, 0xD0000000);
  p(-1, -1);
  return 0;
}

Второй файл:
#include <stdio.h>
#include <limits.h>

void p(int a, int b)
{
  int result = a + b;
  int x1 = a ^ b;
  int ovf1, ovf2, ovf3, ovf4;
  if (x1 >= 0)
    ovf1 = ((a ^ result) < 0);
  else
    ovf1 = 0;
  if (b >= 0)
    ovf2 = (a > INT_MAX - b);
  else
    ovf2 = (a < INT_MIN - b);
  ovf3 = ((b >= 0) != (result >= a));
  ovf4 = ((b > 0) != (result > a));
  printf("%8x %8x %8x %1d:%1d:%1d:%1d\n", a, b, result,
      ovf1, ovf2, ovf3, ovf4);
}


Результат под gcc везде, под open64 (он только на 64 бывает), под clang на 32 битах без оптимизации, и под clang на 64 битах:

       1        1        2 0:0:0:0
30000000 30000000 60000000 0:0:0:0
40000000 40000000 80000000 1:1:1:1
50000000 50000000 a0000000 1:1:1:1
b0000000 b0000000 60000000 1:1:1:1
c0000000 c0000000 80000000 0:0:0:0
d0000000 d0000000 a0000000 0:0:0:0
ffffffff ffffffff fffffffe 0:0:0:0


Результат на clang в 32 битах с -O:
       1        1        2 0:0:0:0
30000000 30000000 60000000 0:0:0:0
40000000 40000000 80000000 1:1:0:0
50000000 50000000 a0000000 1:1:0:0
b0000000 b0000000 60000000 1:1:0:0
c0000000 c0000000 80000000 0:0:0:0
d0000000 d0000000 a0000000 0:0:0:0
ffffffff ffffffff fffffffe 0:0:0:0


Заодно померял скорость: вариант через xor'ы на ~4% медленнее варианта с двумя сравнениями.

Надо бы подсказку от гуру стандартов.
The God is real, unless declared integer.
Re[3]: Проверка выполнения сложения
От: rg45 СССР  
Дата: 13.04.12 20:01
Оценка:
Здравствуйте, netch80, Вы писали:

N>Всё однако хитрее. Может, я поспешил с похвалой?


Каждая похвала на учете?


N>Clang 3.0 на 32-битке при -O (и выше) твоё выражение под assert'ом считает истинным *всегда*, соответственно проверка не происходит.

N>Это независимо от того, используется ли '>' или '>=' в обоих сравнениях.

Забавно. Но имеет право, поскольку, в отсутствие переполнения это выражение действительно всегда истинно, а при переполнении компилятор с оптимизатором делают что хотят, потому как UB
--
Справедливость выше закона. А человечность выше справедливости.
Re[4]: Проверка выполнения сложения
От: rg45 СССР  
Дата: 13.04.12 20:27
Оценка:
Здравствуйте, rg45, Вы писали:

N>>Clang 3.0 на 32-битке при -O (и выше) твоё выражение под assert'ом считает истинным *всегда*, соответственно проверка не происходит.

N>>Это независимо от того, используется ли '>' или '>=' в обоих сравнениях.

R>Забавно. Но имеет право, поскольку, в отсутствие переполнения это выражение действительно всегда истинно, а при переполнении компилятор с оптимизатором делают что хотят, потому как UB


А что если попробовать обмануть оптимизатор?

// Определение этой константы вынесено
// в отдельную единицу трансляции, чтобы
// оптимизатор не видел ее значения.
extern const unsigned char zero;

template<typename T>
T add (T a, T b)
{
  T c = a + b;
  assert(b >= zero == c >= a);
  return c;  
}


Конечно, это уже не так заманчиво, как выглядело раньше.
--
Справедливость выше закона. А человечность выше справедливости.
Re[5]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 14.04.12 06:48
Оценка: 7 (1)
Здравствуйте, rg45, Вы писали:

R>>Забавно. Но имеет право, поскольку, в отсутствие переполнения это выражение действительно всегда истинно, а при переполнении компилятор с оптимизатором делают что хотят, потому как UB


R>А что если попробовать обмануть оптимизатор?


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

extern const int foobar;
int ovf3(int a, int b)
{
  int result = a + b;
  return ((b >= foobar) != (result >= a));
}


Получаем:
000000a0 <ovf3>:
  a0:   8b 44 24 08             mov    0x8(%esp),%eax ; это прочли b
  a4:   89 c1                   mov    %eax,%ecx      ; скопировали в %ecx
  a6:   c1 e9 1f                shr    $0x1f,%ecx     ; оставили от него один знак (то есть b<0)
  a9:   39 05 00 00 00 00       cmp    %eax,0x0       ; внешняя переменная foobar, адрес пока неизвестен
  af:   0f 9e c0                setle  %al            ; al - результат (b<foobar)
  b2:   0f b6 c0                movzbl %al,%eax       ; растянули его до полного %eax
  b5:   31 c8                   xor    %ecx,%eax      ; неравенство двух тестов, то есть (b<0) != (b<foobar)
  b7:   83 f0 01                xor    $0x1,%eax      ; булевская инверсия - превратили в равенство тестов
  ba:   c3                      ret


Получается, что clang из (result >= a) сделал ((a+b)>=a), это очевидно упростил до (b>=0), ну а дальше очевидно, что проверка всегда даст (b>=0) == (b>=foobar), если foobar == 0

Так что "в живых" остались сравнение по XOR и по двум границам сравнения с пределами.
The God is real, unless declared integer.
Re[4]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 14.04.12 07:02
Оценка:
Здравствуйте, rg45, Вы писали:

N>>Всё однако хитрее. Может, я поспешил с похвалой?

R>Каждая похвала на учете?

Нет, но если похвалил решение (не человека), а дальше нашлись проблемы с этим решением — то что ещё сказать?

R>Забавно. Но имеет право, поскольку, в отсутствие переполнения это выражение действительно всегда истинно, а при переполнении компилятор с оптимизатором делают что хотят, потому как UB


Вот честно жаль, что нету поддержки в библиотеке.
Какие-то несчастные div() есть, а поддержки простейшего сложения с детектом переполнения — нет.
The God is real, unless declared integer.
Re[6]: Проверка выполнения сложения
От: rg45 СССР  
Дата: 14.04.12 08:55
Оценка:
Здравствуйте, netch80, Вы писали:

N>...

N>Получается, что clang из (result >= a) сделал ((a+b)>=a), это очевидно упростил до (b>=0), ну а дальше очевидно, что проверка всегда даст (b>=0) == (b>=foobar), если foobar == 0

Мда, жестокий оптимизатор, ничего не скажешь. Выходит, что в самом общем случае, использовать результат сложения вообще нельзя, поскольку в случае переполнения его значение может оказаться любым, и кто знает, каким образом этот факт будет учтен тем или другим компилятором. В общем, UB — оно и в Африке UB. Кстати, вариант с xor тоже использует результат сложения, поэтому он также чреват.
--
Справедливость выше закона. А человечность выше справедливости.
Re[7]: Проверка выполнения сложения
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 14.04.12 12:50
Оценка:
Здравствуйте, rg45, Вы писали:

N>>...

N>>Получается, что clang из (result >= a) сделал ((a+b)>=a), это очевидно упростил до (b>=0), ну а дальше очевидно, что проверка всегда даст (b>=0) == (b>=foobar), если foobar == 0
R>Мда, жестокий оптимизатор, ничего не скажешь. Выходит, что в самом общем случае, использовать результат сложения вообще нельзя, поскольку в случае переполнения его значение может оказаться любым, и кто знает, каким образом этот факт будет учтен тем или другим компилятором.

Так-то оно так, но на практике я пока не видел реализаций, где не выполнялось бы правило, что сумма двух чисел размером N (после штатного расширения, например, short -> int), *приведённая к тому же типу* (этот момент тут принципиален), не давала бы N младших бит суммы. Но на практике сейчас невероятно встретить реализацию иную, чем "дополнение до 2", поэтому неудивительно, что оно так.

R> В общем, UB — оно и в Африке UB. Кстати, вариант с xor тоже использует результат сложения, поэтому он также чреват.


Да, но вероятность этой чреватости даже не в разы, а на порядки ниже.
Пока что я не вижу потенциального UB только у двух не-ассемблерных реализаций — с контр-вычитанием (ovf2 в прошлом примере) и с расширением разрядности (как в SafeInt<>), но последняя значительно дороже для всего шириной в int и выше.

Кстати, мы пока что обсуждали только сложение, но есть ещё тема умножения. И вот с ним всё мрачнее — я пока не представляю себе иных вариантов, кроме как ассемблер или проверка на расширенной разрядности.
The God is real, unless declared integer.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.