Подтвердить что ты не робот

C безопасно принимать абсолютное значение целого числа

Рассмотрим следующую программу (C99):

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int main(void)
{
    printf("Enter int in range %jd .. %jd:\n > ", INTMAX_MIN, INTMAX_MAX);
    intmax_t i;
    if (scanf("%jd", &i) == 1)
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
}

Теперь, насколько я понимаю, это содержит легко запускаемое поведение undefined, например:

Enter int in range -9223372036854775808 .. 9223372036854775807:
 > -9223372036854775808
Result: |-9223372036854775808| = -9223372036854775808

Вопросы:

  • Это действительно поведение undefined, так как в "коду разрешено запускать любой путь кода, какой любой код, который инсулирует компилятор", когда пользователь вводит плохой номер? Или это какой-то другой не совсем определенный?

  • Как бы педантичный программист защищался от этого, не делая никаких предположений, не гарантированных стандартом?

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

4b9b3361

ОТВЕТЫ

Ответ 1

Как педантичный программист будет защищаться от этого, не делая никаких предположений, не гарантированных стандартом?

Один метод - использовать целые числа без знака. Поведение переполнения беззнаковых целых чисел хорошо определено, как и поведение при преобразовании из подписанного в беззнаковое целое.

Итак, я думаю, что следующее должно быть безопасным (получается, что он ужасно разбит на некоторые действительно неясные системы, см. позже в сообщении для улучшенной версии)

uintmax_t j = i;
if (j > (uintmax_t)INTMAX_MAX) {
  j = -j;
}
printf("Result: |%jd| = %ju\n", i, j);

Итак, как это работает?

uintmax_t j = i;

Это преобразует целое число со знаком в беззнаковое. ЕСЛИ это положительное значение остается неизменным, если отрицательное значение увеличивается на 2 n (где n - количество бит). Это преобразует его в большое число (большее, чем INTMAX_MAX)

if (j > (uintmax_t)INTMAX_MAX) {

Если исходное число было положительным (и, следовательно, меньше или равно INTMAX_MAX), это ничего не делает. Если исходный номер был отрицательным, выполняется внутри блока if.

  j = -j;

Число отрицается. Результат отрицания явно отрицательный и поэтому не может быть представлен как целое число без знака. Поэтому он увеличивается на 2 n.

Таким образом, алгебраически результат для отрицательного я выглядит как

j = - (i + 2 n) + 2 n= -i

Умный, но это решение делает предположения. Это не выполняется, если INTMAX_MAX == UINTMAX_MAX, что разрешено стандартом C.

Хмм, давайте посмотрим на это (я читаю https://busybox.net/~landley/c99-draft.html, который, по-видимому, является последним проектом C99 до стандартизации, если что-то изменилось в окончательном стандарте, пожалуйста, скажите мне.

Когда имена typedef, отличающиеся только отсутствием или присутствием начального u, определены, они должны обозначать соответствующие типы с подписью и без знака, как описано в 6.2.5; реализация не должна предоставлять тип без предоставления соответствующего типа.

В 6.2.5 я вижу

Для каждого из подписанных целочисленных типов существует соответствующий (но другой) неподписанный целочисленный тип (обозначенный ключевым словом без знака), который использует ту же самую сумму хранения (включая информацию о знаке) и имеет те же требования к выравниванию.

В 6.2.6.2 я вижу

# 1

Для беззнаковых целочисленных типов, отличных от unsigned char, биты представления объекта должны быть разделены на две группы: биты значений и биты заполнения (их не должно быть ни одного из последних). Если бит N значений бит, каждый бит должен представлять различную мощность 2 между 1 и 2N-1, так что > объекты этого типа должны быть способны представлять значения от 0 до 2N-1 > с использованием чистого двоичного представления; это должно быть известно как представление стоимости. Значения любых битов дополнений не определены .39)

# 2

Для знаковых целых типов биты представления объекта должны быть разделены на три группы: биты значений, биты заполнения и знаковый бит. Не должно быть никаких битов заполнения; должен быть ровно один знаковый бит. Каждый бит, который является битом значения, должен иметь то же значение, что и тот же бит, в представлении объекта соответствующего неподписанного типа (если есть биты значения M в подписанном типе и N в неподписанном типе, то M <= N). Если знаковый бит равен нулю, он не должен влиять на результирующее значение.

Итак, да, кажется, вы правы, в то время как подписанные и неподписанные типы должны быть того же размера, что для неподписанного типа он действительно имеет еще один бит дополнений, чем подписанный тип.

Хорошо, на основании вышеприведенного анализа, выявляющего недостаток в моей первой попытке, я написал более параноидальный вариант. Это имеет два изменения от моей первой версии.

Я использую я < 0 вместо j > (uintmax_t) INTMAX_MAX для проверки отрицательных чисел. Это означает, что алгоритм обрабатывает правильные результаты для чисел, больших или равных -INTMAX_MAX, даже если INTMAX_MAX == UINTMAX_MAX.

Я добавляю обработку для случая ошибки, где INTMAX_MAX == UINTMAX_MAX, INTMAX_MIN == -INTMAX_MAX -1 и я == INTMAX_MIN. Это приведет к тому, что j = 0 внутри условия if, которое мы можем легко проверить.

Из требований стандарта C видно, что INTMAX_MIN не может быть меньше -INTMAX_MAX-1, поскольку имеется только один битовый знак, а число битов значения должно быть таким же или меньше, чем в соответствующем неподписанном типе. Просто нет шаблонов бит для представления меньших чисел.

uintmax_t j = i;
if (i < 0) {
  j = -j;
  if (j == 0) {
    printf("your platform sucks\n");
    exit(1);
  }
}
printf("Result: |%jd| = %ju\n", i, j);

@plugwash Я думаю, что 2501 правильно. Например, значение -UINTMAX_MAX становится равным 1: (-UINTMAX_MAX + (UINTMAX_MAX + 1)) и не попадает в ваш if. - hyde 58 мин назад

Умм,

при условии, что INTMAX_MAX == UINTMAX_MAX и я = -INTMAX_MAX

uintmax_t j = i;

после этой команды j = -INTMAX_MAX + (UINTMAX_MAX + 1) = 1

если (i < 0) {

i меньше нуля, поэтому мы запускаем команды внутри if

j = -j;

после этой команды j = -1 + (UINTMAX_MAX + 1) = UINTMAX_MAX

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

Ответ 2

Если результат imaxabs не может быть представлен, может случиться, если вы используете два дополнения, то поведение undefined.

7.8.2.1 Функция imaxabs

  1. Функция imaxabs вычисляет абсолютное значение целого числа j. Если результат не может быть представленным, поведение undefined. 221)

221) Абсолютное значение наибольшего отрицательного числа не может быть представлено в двух дополнительных дополнениях.

Проверка, которая не делает никаких предположений и всегда определяется:

intmax_t i = ... ;
if( i < -INTMAX_MAX )
{
    //handle error
}

(Этот оператор if не может быть выполнен, если использовать одно дополнение или представление знаковой величины, поэтому компилятор может дать недопустимый код предупреждения. Сам код по-прежнему определен и действителен.)

Ответ 3

В системах с двумя дополнениями, получающих абсолютное число наибольшего отрицательного значения, действительно поведение undefined, так как абсолютное значение будет вне диапазона. И это ничто не может помочь компилятору, поскольку UB происходит во время выполнения.

Единственный способ защитить от этого - сравнить вход с самым отрицательным значением для типа (INTMAX_MIN в коде, который вы показываете).

Ответ 4

Таким образом, вычисление абсолютного значения целого числа вызывает поведение undefined в одном случае. Фактически, в то время как поведение undefined можно избежать, невозможно дать правильный результат в одном случае.

Теперь рассмотрим умножение целого числа на 3: здесь мы имеем гораздо более серьезную проблему. Эта операция вызывает поведение undefined в 2/3rds всех случаев! И для двух третей всех значений int x поиск int со значением 3x просто невозможно. Это гораздо более серьезная проблема, чем проблема абсолютной стоимости.

Ответ 5

Возможно, вы захотите использовать некоторые бит-хаки:

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

Это хорошо работает, когда INT_MIN < v <= INT_MAX. В случае, когда v == INT_MIN, он остается INT_MIN, , не вызывая поведения undefined.

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

Ссылка: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

Ответ 6

в соответствии с этим http://linux.die.net/man/3/imaxabs

Примечания

Попытка взять абсолютное значение самого отрицательного целого не определена.

Чтобы обрабатывать полный диапазон, вы можете добавить что-то вроде этого в свой код

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd\n", i, -(i/10), -(i%10));
    }

edit: Поскольку abs (INTMAX_MIN) не может быть представлен на машине с двумя дополнениями, 2 значения в пределах представленного диапазона конкатенируются на выходе в виде строки. Протестировано с помощью gcc, хотя printf требуется% lld, поскольку% jd не поддерживается.

Ответ 7

  • Это действительно поведение undefined, так как в "коду разрешено запускать какой-либо код, какой код какого-либо кода, который поражает компилятор", когда пользователь вводит плохой номер? Или это какой-то другой аромат не совсем определенного?

Поведение программы - это только undefined, когда неудачный номер успешно введен и передан imaxabs(), который в типичной системе с двумя дополнениями возвращает результат -ve, как вы заметили.

Это поведение undefined в этом случае, реализация также будет разрешена для завершения программы с ошибкой перетока, если ALU устанавливает флаги состояния.

Причиной "поведения undefined" в C является то, что разработчикам компилятора не нужно защищать от переполнения, поэтому программы могут работать более эффективно. Пока он находится в стандарте C для каждой программы на C с помощью abs(), чтобы попытаться убить вашего первого родителя, просто потому, что вы вызываете его с слишком большим значением, запись такого кода в объектный файл будет просто извращенной.

Реальная проблема с этими поведениями undefined заключается в том, что оптимизирующий компилятор может отклонить наивные проверки, поэтому код выглядит следующим образом:

r = (i < 0) ? -i : i;
if (r < 0) {   // This code may be pointless
    // Do overflow recovery
    doRecoveryProcessing();
} else {
    printf("%jd", r);
}

Как оптимизатор компилятора может рассуждать о том, что отрицательные значения отрицаются, он может в принципе определить, что (r < 0) всегда false, поэтому попытка захвата проблемы не выполняется.

  1. Как бы педантичный программист защищался от этого, не делая никаких предположений, не гарантированных стандартом?

Безусловно, лучший способ - просто убедиться, что программа работает с допустимым диапазоном, поэтому в этом случае достаточно проверить правильность ввода (запретить INTMAX_MIN). Программы, печатающие таблицы abs(), должны избегать INT * _MIN и т.д.

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd\n", i, -(i/10), -(i%10));
    }

Появляется, чтобы записать абс (INTMAX_MIN) с помощью fakery, позволяя программе соответствовать обещанию пользователю.