Целочисленное переполнение в C: стандарты и компиляторы

Question

Отредактировано, чтобы включить надлежащую стандартную ссылку благодаря Карлу Норуму.

Стандарт C указывает

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

Существуют ли переключатели компилятора, которые гарантируют определенное поведение при целочисленном переполнении? Я хотел бы избежать носовых демонов. В частности, я хотел бы заставить компилятор переноситься при переполнении.

Ради уникальности, давайте возьмем стандарт C99, а компилятор - GCC. Но меня будут интересовать ответы для других компиляторов (icc, cl) и других стандартов (C1x, C89). На самом деле, просто чтобы раздражать толпу C / C ++, я бы даже оценил ответы для C ++ 0x, C ++ 03 и C ++ 98.

Примечание: международный стандарт ISO / IEC 10967-1 может быть уместен здесь, но, насколько я могу судить, он упоминался только в информативном приложении.

Answer 1

Взгляните на -ftrapv и -fwrapv:

-ftrapv

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

-fwrapv

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

Answer 2

Для вашего ответа C99, я думаю 6,5 выражений , пункт 5 - это то, что вы ищете:

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

Это означает, что если вы переполнены, вам не повезло - никакое поведение не гарантируется. Типы без знака являются особым случаем и никогда не переполняются ( 6.2.5 Типы , параграф 9):

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

C ++ имеет те же операторы, сформулированные немного по-другому:

• 5 Выражения , пункт 4:

  Если во время вычисления выражения результат не определен математически или не находится в диапазоне представимых значений для его типа, поведение не определено. [ Примечание: большинство существующих реализаций C ++ игнорируют целочисленные переполнения. Обработка деления на ноль, формирования остатка с использованием делителя нуля и всех исключений с плавающей запятой варьируется в зависимости от машины и обычно настраивается библиотечной функцией. -endnote ]

• 3.9.1 Основные типы , пункт 4:

  Целые числа без знака, объявленные unsigned, должны подчиняться законам арифметики по модулю 2 ^ n , где n - количество бит в представлении значения этого конкретного размера целого числа .

Answer 3

В C99 общее поведение описано в 6.5 / 5

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

Поведение типов без знака описано в 6.2.5 / 9, в котором в основном говорится, что операции с типами без знака никогда не приводят к исключительному условию

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

Компилятор GCC имеет специальную опцию -ftrapv, которая предназначена для отслеживания переполнения во время выполнения целочисленных операций со знаком.

Answer 4

Для полноты я хотел бы добавить, что в Clang теперь есть «проверенные арифметические встроенные функции» в качестве расширения языка. Вот пример использования проверенного умножения без знака:

unsigned x, y, result;
...
if (__builtin_umul_overflow(x, y, &result)) {
    /* overflow occured */
    ...
}
...

http://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins

Answer 5

6.2.5, пункт 9 - это то, что вы ищете:

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

Answer 6

Все предыдущие публикации комментировали стандарт C99, но на самом деле эта гарантия уже была доступна ранее.

Пятый абзац раздела 6.1.2.5 Типы

стандартных состояний C89

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

Обратите внимание, что это позволяет программистам на С заменять все беззнаковые деления на некоторую константу, которая должна быть заменена умножением на обратный элемент кольца, образованный C арифметикой по модулю 2 ^ N.

И это можно сделать без какого-либо «исправления», поскольку это было бы необходимо путем аппроксимации деления умножением с фиксированной запятой на обратное значение.

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

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

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

Answer 7

Я не уверен, есть ли какие-нибудь переключатели компилятора, которые вы можете использовать, чтобы обеспечить единообразное поведение для переполнений в C / C ++. Другой вариант - использовать шаблон SafeInt<T>. Это кроссплатформенный шаблон C ++, который обеспечивает определенную проверку переполнения / недостаточности для всех типов целочисленных операций.

• http://safeint.codeplex.com/