Здравствуйте, 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, Вы писали:
N>>Поэтому простейший вариант анализа на переполнение без поддержки аппаратуры выглядит примерно так:
[...]
R>Не находишь, что мой вариант
проще и универсальнее? Универсальнее в том плане, что годится и для знаковых и для беззнаковых типов.
Загнал в автоматический тест — вроде да, отклонений не замечено. Проверка такого рода будет работать.
С другой стороны, надо ещё измерить, какой из этих вариантов эффективнее в каком случае. Визуально для человека твой однозначно проще. Но мне кажется, что для ARM, например, мой соберётся в более короткую и прямую последовательность. Также у тебя проверка на (y>0) избыточна для беззнаковых; если заменить на >= в обеих сторонах, то левая для беззнаковых вырождается в true и экономится операция сравнения, но компилятор может пожаловаться на condition is always true.
R>P.S. Предложил еще позавчера утром, никто и внимания не обратил, обидно
Почему не заметил — не знаю. Видимо, слишком увлёкся опровержением.
Поставил +1 и 2.
Интересно, почему MS в своём SafeInt не использует такие простые приёмы. Вместо этого, например, для двух 32-разрядных чисел они складывают используя 64 бита (причём это даже при компиляции в 32-битный код) и проверяют результат на выход за границы. И вообще у них пример того, как не надо писать на C++...
Здравствуйте, 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) флаг переполнения (в дополнение к обычному).
Здравствуйте, netch80, Вы писали:
N>Также у тебя проверка на (y>0) избыточна для беззнаковых; если заменить на >= в обеих сторонах, то левая для беззнаковых вырождается в true и экономится операция сравнения...
В-о-от! Я это чуть позже тоже сообразил, но уже не стал заморачиваться исправлением. Действительно, если a + b = c, где a, b, c — беззнаковые, то выражение: b >= 0 == c >= a оптимизатор с радостью упростит до c >= a
N>Интересно, почему MS в своём SafeInt не использует такие простые приёмы. Вместо этого, например, для двух 32-разрядных чисел они складывают используя 64 бита (причём это даже при компиляции в 32-битный код) и проверяют результат на выход за границы. И вообще у них пример того, как не надо писать на C++...
Да набирают туда непонятно кого
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, 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
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, netch80, Вы писали:
N>Интересно, почему MS в своём SafeInt не использует такие простые приёмы. Вместо этого, например, для двух 32-разрядных чисел они складывают используя 64 бита (причём это даже при компиляции в 32-битный код) и проверяют результат на выход за границы. И вообще у них пример того, как не надо писать на C++...
А что не так с SafeInt ? (кроме того, что они используют 64 бита для 32-разрядных чисел)
Здравствуйте, netch80, Вы писали:
N>Интересно, чем определяется название функции? Потому что на FreeBSD/i386 мне в таком же случае затребовали __addvsi3. Я правильно понимаю, что __addvdi3 это для двойной длины (64 бита)?
Про буквы SI и DI можно прочитать в Machine Modes. И похоже что именно название и есть причина сломанности на 64-х битной архитектуре, ибо на amd64 нужно в этом случае вызывать SI версию функции, а не DI.
Но вообще, это же служебная функция компилятора, по идее не важно как она называется. Если бы она работала, то и писать бы её не пришлось.
Да, проверял на FreeBSD/amd64 компиляторами gcc от 4.2 до 4.7.
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.
Здравствуйте, 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. Но в качестве отладочного диагностического средства для конкретных платформ такое решение может приносить пользу. Повышение надежности работы программ как частный случай неопределенного поведения, о как!
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, 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 — есть, а такой базы — нет.
Недавно тут видел упоминание ещё одного случая — сдвигов знаковых целых. Опять же формально не определено, что при этом будет. Но практика где-то в таком же количестве случаев использует один и тот же метод.
N>Это в стандарте. N>А реальная практика показывает, что на 99.99% встреченных установок сложение целых в C и C++ выполняется как сложение двух чисел в "дополнении до 2" с игнорированием всех переполнений.
на самом деле, я не дочитал вопрос автора топика он хочет "оптимальнее", так что да, можно игнорировать UB (на бумаге) и т.д.
Of course, the code must be complete enough to compile and link.
>> 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."
Здравствуйте, 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();
Упрощение получилось невероятное
Так что беру заявление обратно — оно сейчас такое вполне сойдёт.
Осталось вычистить чисто алгоритмические неадекватности.
Здравствуйте, 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-битный тип? В результате интерпретации беззнакового типа как знакового возможны две ошибочные ситуации: мы "не замечаем" беззнаковое переполнение. Пример: складываем 0xFFFFFFFFU и 1U, переполнение налицо. Но при интерпретации этих слагаемых как знаковых, получим -1 + 1 = 0, т.е. все Ok;
выдаем "ложное срабатывание". Пример: складываем 0x7FFFFFFFU и 1U — для беззнаковых чисел это нормально, переполнения нет. Но при интерпретации этих слагаемых как знаковых, придем к ошибочному заключению, что было переполнение.
--
Справедливость выше закона. А человечность выше справедливости.
