Обнаружение переполнения со знаком в C/C++
На первый взгляд, этот вопрос может показаться дубликатом Как обнаружить целочисленное переполнение? Однако на самом деле это значительно отличается.
Я обнаружил, что, хотя обнаружение переполнения целого без знака довольно тривиально, обнаружить переполнение со знаком в 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) не предоставляет компилятору возможность оптимизировать проверку переполнения? Я думал, что мог бы быть какой-то способ сделать это, приведя оба операнда к беззнаковому, и выполнив проверки, свернув арифметику с двумя собственными дополнениями, но я не совсем уверен, как это сделать.
13 ответов
Ваш подход с вычитанием является правильным и четко определенным. Компилятор не может его оптимизировать.
Другой правильный подход, если у вас есть доступный целочисленный тип большего размера, состоит в том, чтобы выполнить арифметику в большем типе и затем проверить, соответствует ли результат меньшему типу при преобразовании его обратно.
int sum(int a, int b)
{
long long c;
assert(LLONG_MAX>INT_MAX);
c = (long long)a + b;
if (c < INT_MIN || c > INT_MAX) abort();
return c;
}
Хороший компилятор должен конвертировать все дополнение и if заявление в intсложного размера и единственное условное переходное переполнение и никогда не выполняет большее сложение.
Изменить: Как Стивен указал, у меня проблемы с получением (не очень хороший) компилятор, GCC, чтобы генерировать вменяемый ассм. Код, который он генерирует, не очень медленный, но, безусловно, неоптимальный. Если кто-нибудь знает варианты в этом коде, которые заставят gcc сделать правильные вещи, я хотел бы увидеть их.
Нет, ваш второй код неверен, но вы близки: если вы установите
int half = INT_MAX/2;
int half1 = half + 1;
результат сложения INT_MAX, (INT_MAX всегда нечетное число). Так что это действительный вклад. Но в вашей рутине у вас будет INT_MAX - half == half1 и вы бы прервали. Ложный позитив.
Эту ошибку можно исправить, поставив < вместо <= в обеих проверках.
Но тогда и ваш код не оптимален. Следующее сделало бы:
int add(int lhs, int rhs)
{
if (lhs >= 0) {
if (INT_MAX - lhs < rhs) {
/* would overflow */
abort();
}
}
else {
if (rhs < INT_MIN - lhs) {
/* would overflow */
abort();
}
}
return lhs + rhs;
}
Чтобы увидеть, что это действительно так, вы должны символически добавить lhs по обе стороны неравенства, и это дает вам именно те арифметические условия, что ваш результат выходит за пределы.
Самый быстрый способ - использовать встроенный GCC:
int add(int lhs, int rhs) {
int sum;
if (__builtin_add_overflow(lhs, rhs, &sum))
abort();
return sum;
}
На x86 GCC компилирует это в:
mov %edi, %eax
add %esi, %eax
jo call_abort
ret
call_abort:
call abort
который использует встроенное обнаружение переполнения процессора.
Если вы не согласны с использованием встроенных функций GCC, следующий самый быстрый способ - использовать битовые операции со знаковыми битами. Подписанное переполнение дополнительно происходит, когда:
- два операнда имеют одинаковый знак, и
- результат имеет другой знак, чем операнды.
Знаковый бит ~(lhs ^ rhs) если операнды имеют один и тот же знак, а бит знака lhs ^ sum если результат имеет другой знак, чем операнды. Таким образом, вы можете выполнить сложение в виде без знака, чтобы избежать неопределенного поведения, а затем использовать знаковый бит ~(lhs ^ rhs) & (lhs ^ sum):
int add(int lhs, int rhs) {
unsigned sum = (unsigned) lhs + (unsigned) rhs;
if ((~(lhs ^ rhs) & (lhs ^ sum)) & 0x80000000)
abort();
return (int) sum;
}
Это компилируется в:
lea (%rsi,%rdi), %eax
xor %edi, %esi
not %esi
xor %eax, %edi
test %edi, %esi
js call_abort
ret
call_abort:
call abort
что намного быстрее, чем приведение к 64-битному типу на 32-битной машине (с gcc):
push %ebx
mov 12(%esp), %ecx
mov 8(%esp), %eax
mov %ecx, %ebx
sar $31, %ebx
clt
add %ecx, %eax
adc %ebx, %edx
mov %eax, %ecx
add $-2147483648, %ecx
mov %edx, %ebx
adc $0, %ebx
cmp $0, %ebx
ja call_abort
pop %ebx
ret
call_abort:
call abort
В случае с gcc из заметок о выпуске gcc 5.0 мы видим, что теперь __builtin_add_overflow для проверки переполнения дополнительно:
Добавлен новый набор встроенных функций для арифметики с проверкой переполнения: __builtin_add_overflow, __builtin_sub_overflow и __builtin_mul_overflow, а также для совместимости с clang и другими вариантами. Эти встроенные функции имеют два целочисленных аргумента (которые не обязательно должны иметь одинаковый тип), аргументы расширяются до знакового типа бесконечной точности, +, - или * выполняется для них, а результат сохраняется в целочисленной переменной, указывающей на по последнему аргументу. Если сохраненное значение равно результату бесконечной точности, встроенные функции возвращают false, в противном случае - true. Тип целочисленной переменной, которая будет содержать результат, может отличаться от типов первых двух аргументов.
Например:
__builtin_add_overflow( rhs, lhs, &result )
Из документа gcc видно, что встроенные функции для выполнения арифметики с переполнением проверяют, что:
[...] эти встроенные функции имеют полностью определенное поведение для всех значений аргументов.
clang также предоставляет набор проверенных арифметических встроенных функций:
Clang предоставляет набор встроенных функций, которые реализуют проверенную арифметику для критически важных приложений безопасным способом, который быстро и легко выражается на C.
в этом случае встроенным будет:
__builtin_sadd_overflow( rhs, lhs, &result )
ИМХО, самый простой способ справиться с избыточным чувствительным кодом C++ - это использовать SafeInt<T>, Это кроссплатформенный шаблон C++, размещенный на code plex, который обеспечивает необходимые вам гарантии безопасности.
Я нахожу это очень интуитивно понятным в использовании, так как он предоставляет множество тех же шаблонов использования, что и обычные числовые операции, и выражается в потоках через и при исключениях.
Если вы используете встроенный ассемблер, вы можете проверить флаг переполнения. Другая возможность заключается в том, что вы можете использовать безопасный тип данных. Я рекомендую прочитать эту статью о Integer Security.
Очевидное решение - преобразовать в unsigned, чтобы получить четко определенное поведение переполнения unsigned:
int add(int lhs, int rhs)
{
int sum = (unsigned)lhs + (unsigned)rhs;
if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
/* an overflow has occurred */
abort();
}
return sum;
}
Это заменяет неопределенное поведение переполнения со знаком преобразованием значений, выходящих за пределы диапазона, между подписанным и неподписанным, определяемым реализацией, поэтому вам нужно проверить документацию вашего компилятора, чтобы точно знать, что произойдет, но, по крайней мере, оно должно быть четко определено, и должен делать правильные вещи на любой машине с двумя комплементами, которая не генерирует сигналы при конверсиях, что практически во всех машинах и компиляторах C, созданных за последние 20 лет.
Ваша основная проблема в том, что
lhs + rhsне поступает правильно. Но если вы готовы принять машину с дополнением до двух, мы можем это исправить. Предположим, у вас есть функция, которая преобразуется в способ, который гарантированно является обратным преобразованию из в, и оптимизируется до нуля во время выполнения. (См. Ниже, как это реализовать.)
Если вы используете его для исправления неопределенного поведения в исходной попытке, а также переписываете условное выражение, чтобы избежать избыточного теста
lhs >= 0 а также
lhs < 0, тогда вы получите
int add(int lhs, int rhs)
{
int sum = to_int_modular((unsigned)lhs + rhs);
if (lhs >= 0) {
if (sum < rhs)
abort();
} else {
if (sum > rhs)
abort();
}
return sum;
}
который должен превзойти текущий ответголосов , получивший наибольшее количество , поскольку он имеет аналогичную структуру, но требует меньше арифметических операций.
(Реорганизация
ifне должно быть обязательным, но в тестах на Godbolt ICC и MSVC действительно устраняют избыточный тест самостоятельно, но GCC и Clang, что удивительно, этого не делают.)
Если вы предпочитаете вычислять результат в более широком размере, а затем проверять границы, можно выполнить проверку границ.
long long sum = (long long)lhs + rhs;
if ((int)sum != sum)
abort();
... за исключением того, что поведение не определено при переполнении. Но вы можете исправить это с помощью той же вспомогательной функции:
if (to_int_modular(sum) != sum)
Это, вероятно, превзойдет текущий принятый ответ для компиляторов, которые недостаточно умны, чтобы оптимизировать его для проверки флага переполнения.
К сожалению, тестирование (визуальный осмотр на Godbolt) показывает, что GCC, ICC и MSVC лучше справляются с кодом выше, чем с кодом в принятом ответе, но Clang лучше справляется с кодом в принятом ответе. Как обычно, все не так просто.
Этот подход может работать только на архитектурах, где диапазоны значений и одинаково велики, а конкретные реализации ниже также зависят от того, являются ли они дополнением до двух. Машины, не соответствующие этим требованиям, исчезающе редки, но я все равно их проверю:
static_assert(INT_MIN + INT_MAX == -1 && UINT_MAX + INT_MIN == INT_MAX);
Один из способов реализации
to_int_modular является
inline int to_int_modular(unsigned u) {
int i;
memcpy(&i, &u, sizeof(i));
return i;
}
Все основные компиляторы x64 без проблем оптимизируют это до нуля, но когда оптимизации отключены, MSVC и ICC генерируют вызов
memcpy, что может быть немного медленным, если вы часто используете эту функцию. Эта реализация также зависит от деталей представления
unsigned а также
int это, вероятно, не гарантируется стандартом.
Другой способ:
inline int to_int_modular(unsigned u) {
return u <= INT_MAX ? (int)u : (int)(u - INT_MIN) + INT_MIN;
}
Все основные компиляторы x64 не оптимизируют это ни для чего, кроме ICC, что делает из него полный беспорядок и все варианты, которые я мог придумать. ICX работает нормально, и похоже, что Intel отказывается от ICC и переходит на ICX, так что, возможно, эта проблема решится сама собой.
Как насчет:
int sum(int n1, int n2)
{
int result;
if (n1 >= 0)
{
result = (n1 - INT_MAX)+n2; /* Can't overflow */
if (result > 0) return INT_MAX; else return (result + INT_MAX);
}
else
{
result = (n1 - INT_MIN)+n2; /* Can't overflow */
if (0 > result) return INT_MIN; else return (result + INT_MIN);
}
}
Я думаю, что это должно работать для любого законного INT_MIN а также INT_MAX (симметрично или нет); функция, как показано клипы, но должно быть очевидно, как получить другое поведение).
Возможно, вам повезет больше, если вы перешли на 64-битные целые числа и протестировали подобные условия. Например:
#include <stdint.h>
...
int64_t sum = (int64_t)lhs + (int64_t)rhs;
if (sum < INT_MIN || sum > INT_MAX) {
// Overflow occurred!
}
else {
return sum;
}
Возможно, вы захотите поближе взглянуть на то, как расширение знака будет работать здесь, но я думаю, что это правильно.
В случае добавления двух long значения, переносимый код может разбить long значение в низком и высоком int части (или в short части в случае long имеет тот же размер, что и int):
static_assert(sizeof(long) == 2*sizeof(int), "");
long a, b;
int ai[2] = {int(a), int(a >> (8*sizeof(int)))};
int bi[2] = {int(b), int(b >> (8*sizeof(int))});
... use the 'long' type to add the elements of 'ai' and 'bi'
Использование встроенной сборки - самый быстрый способ, если он предназначен для конкретного процессора:
long a, b;
bool overflow;
#ifdef __amd64__
asm (
"addq %2, %0; seto %1"
: "+r" (a), "=ro" (overflow)
: "ro" (b)
);
#else
#error "unsupported CPU"
#endif
if(overflow) ...
// The result is stored in variable 'a'
Я думаю, что это работает:
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 Загрузить эффективный адрес и часто используется для добавления, не затрагивая регистр флагов).
Ваша версия имеет больший код и имеет гораздо больше переходов, но я не знаю, что будет лучше.
По моему мнению, самой простой проверкой будет проверка знаков операндов и результатов.
Давайте рассмотрим сумму: переполнение может произойти в обоих направлениях, + или -, только когда оба операнда имеют одинаковый знак. И, безусловно, переполнение произойдет, когда знак результата не будет совпадать со знаком операндов.
Итак, такой проверки будет достаточно:
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 такого нет.