Блог

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

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

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

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

• недостаточный поток: offset < 0 amp;amp; position offset >= position
• переполнение: offset > 0 amp;amp; position offset <= position

И мне также интересно, есть ли более элегантный способ сделать это.

Обновить:

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

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

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

Почему условия верны: арифметика on 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 amp;amp; position offset > position .

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

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

int is_overflow (uint32_t position, int32_t offset)
{
    if (offset > 0 amp;amp; offset > UINT32_MAX - position) {
        // really we checked (offset   position > UINT32_MAX)
        // overflow
        return 1;
    }
    else if (offset < 0 amp;amp; (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;
}
  

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

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

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

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

ОБНОВЛЕНИЕ: если 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), и он редко заботится о переполнении целых чисел, потому что они происходят регулярно в программном обеспечении и являются образом жизни. Имейте это в виду, но не переживайте.

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