Как оценить переполнение при добавлении подписанного в неподписанное - PullRequest
Новая
       68

Как оценить переполнение при добавлении подписанного в неподписанное

9 голосов
/ 03 ноября 2011

Я пытаюсь обнаружить переполнение при добавлении смещения со знаком в позицию без знака 

uint32 position;
int32 offset;  // it could be negative
uint32 position = position+offset;

Как проверить, является ли результат переполнением или недостаточным?

Я думалуродливым образом, но не уверен в его правильностиинтересно, есть ли более элегантный способ сделать это.

Обновление:

Какое лучшее решение, если смещение длинное? 

uint32 position;
long offset;  // it could be negative
uint32 position = position+offset;

Ответы [ 3 ]

1 голос
/ 03 ноября 2011

Следующая функция проверяет переполнение / недостаточность при добавлении int32_t к uint32_t. Он также содержит несколько тестов в качестве доказательства правильности. 

#include <stdint.h>
#include <assert.h>

int is_overflow (uint32_t position, int32_t offset)
{
    if (offset > 0 && offset > UINT32_MAX - position) {
        // really we checked (offset + position > UINT32_MAX)
        // overflow
        return 1;
    }
    else if (offset < 0 && (uint32_t)offset <= UINT32_MAX - position) {
        // really we checked  (position + (uint32_t)offset <= UINT32_MAX)
        // the (uint32_t)offset maps negative offset to [2^31, UINT32_MAX]
        // underflow
        return -1;
    }

    // no over/underflow
    return 0;
}

uint32_t abs_of_negative_int32 (int32_t offset)
{
    assert(offset < 0);

    return ((UINT32_MAX - (uint32_t)offset) + 1);
}

int main (int argc, char *argv[])
{
    int r;

    r = is_overflow(0, 0);
    assert(r == 0);

    r = is_overflow(0, 1);
    assert(r == 0);

    r = is_overflow(0, INT32_MAX - 1);
    assert(r == 0);

    r = is_overflow(0, INT32_MAX);
    assert(r == 0);

    r = is_overflow(0, -1);
    assert(r == -1);

    r = is_overflow(0, INT32_MIN + 1);
    assert(r == -1);

    r = is_overflow(0, INT32_MIN);
    assert(r == -1);

    r = is_overflow(UINT32_MAX, 0);
    assert(r == 0);

    r = is_overflow(UINT32_MAX, 1);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - 1, 1);
    assert(r == 0);

    r = is_overflow(UINT32_MAX - 1, 2);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - 1, INT32_MAX);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - INT32_MAX, INT32_MAX);
    assert(r == 0);

    r = is_overflow(UINT32_MAX - INT32_MAX + 1, INT32_MAX);
    assert(r == 1);

    r = is_overflow(abs_of_negative_int32(INT32_MIN), INT32_MIN);
    assert(r == 0);

    r = is_overflow(abs_of_negative_int32(INT32_MIN) - 1, INT32_MIN);
    assert(r == -1);

    return 0;
}
1 голос
/ 03 ноября 2011

Ваши тесты верны. Сейчас я не вижу более элегантного пути, возможно, нет.

Почему условия верны: арифметика на uint32_t является арифметикой по модулю 2 ^ 32. Преобразование из int32_t в uint32_t обычно представляет собой реинтерпретацию битового шаблона (в любом случае, как указал @caf, здесь происходит уменьшение по модулю 2 ^ 32, поэтому оно определенно работает). Рассматривайте position и offset как целые числа произвольной точности. Переполнение происходит тогда и только тогда, когда
position + offset >= 2^32. Но offset < 2^31, то есть position + offset < position + 2^31, что меньше position + 2^32, следующее значение, которое уменьшается до position по модулю 2 ^ 32, так что uint32_t, затем position + offset < position. С другой стороны, если offset > 0 и position + offset < position, очевидно, произошло переполнение. Недостаток происходит тогда и только тогда, когда position + offset < 0 в виде математических чисел. Начиная с offset >= -2^31, аналогичные рассуждения показывают, что недостаточность произошла тогда и только тогда, когда offset < 0 && position + offset > position.

0 голосов
/ 03 ноября 2011

Вот как вы можете это сделать: 

uint32 addui(uint32 position, int32 offset, int* overflow)
{
  *overflow = (((offset >= 0) && (0xFFFFFFFFu - position < (uint32)offset)) ||
               ((offset < 0) && (position < (uint32)-offset)));
  return position + offset;
}

Суффикс u должен гарантировать, что константа 0xFFFFFFFF имеет тип без знака (шестнадцатеричные константы без суффиксов могут быть со знаком или без знака, в зависимости от значения и того, каккомпилятор определяет int, long и long long), и поэтому выражение слева от <не имеет знака.Возможно, в этом нет необходимости, но я немного устал, чтобы понять, если это не так.Это точно не повредит. </p>

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

ОБНОВЛЕНИЕ : Если int32 имеет представление дополнения 2 и смещение = -0x80000000, выражение -offset может вызывать сигнал, определяемый реализацией, или даже вызывать неопределенное поведение в соответствии со стандартом C (см. Разделы 6.3.1.3 Signed and unsigned integers и 7.20.6.1 The abs, labs and llabs functions из C99), но практически этого никогда не происходит, потому что на большинстве платформ отрицание реализовано в виде простой инструкции (или нескольких), которая не вызывает никаких исключений / прерываний / прерываний / событий в ЦП и мало что дает для генерации дополнительныхкод для проверки этого крайнего случая, тем более что целые числа представлены в коде дополнения 2, а абсолютное значение -0x80000000 равно 0x80000000, что может быть удобно (например, для расчета абсолютного значения).Процессор не заботится о целых числах со знаком и даже использует одинаковые инструкции сложения и вычитания для обоих (это преимущество дополнения 2), и он редко заботится о целочисленных переполнениях, потому что они обычно происходят в программном обеспечении и являются способомжизнь.Знайте об этом, но не волнуйтесь.

Пожалуйста, посмотрите, как они реализованы в Microsoft SafeInt для C ++ ( Код , Intro , На MSDN , Видео ) и IntSafe для C ( Intro + Code , На MSDN ).

...