Что такое переполнение и зависит ли его определение от языка?
Кратко:
- Что такое переполнение и различается ли его определение для разных языков программирования? Например, что мы не считаем переполнением signed-unsigned-приведения в Си++, но считаем в C#?
- Можно ли вообще применять термин "переполнение" к действиям с вещественными числами, когда результатом становится бесконечность? Если моя изначальная формулировка про превышение максимального представимого значения верна, то какую роль в ответе играет представимость бесконечности в вещественных типах?
А теперь подробно:
Я всегда воспринимал переполнение как ситуацию, в которой получаемое или присваиваемое значение оказывается меньше минимального или больше максимального значения для используемого типа.
C++
Однако при обсуждении вопроса возникла ситуация с подобным кодом на си:
int x = -10;
unsigned y = x;
Два участника сказали мне (раз и два), что этот код не содержит переполнения. В качестве аргументации используется то, что:
- Этот код делает битовую копию значения без каких либо вычислений.
- Флаги процессора CF и OF при этом не заполняются.
При обдумывании этой ситуации мне пришёл в голову другой аналогичный код:
unsigned x = ~0U;
int y = x; // -1
У такого кода добавляется интересный момент: насколько я знаю, он не содержит UB, однако, знаковое переполнение является UB, поэтому логично заявить, что и переполнения он не содержит. Хотя присваиваемое значение и превышает максимальное значение типа int.
А что если преобразование будет не формальным, а реально присутствующим, например, из вещественного типа?
unsigned x = (unsigned)1e12;
Это всё ещё не переполнение, или уже переполнение?
Компилятор на код
#include <iostream>
using namespace std;
int main()
{
int x = 1e12;
cout << x << endl;
return 0;
}
warning: overflow in conversion from ‘double’ to ‘int’ changes value from ‘1.0e+12’ to ‘2147483647’ [-Woverflow]
Получается, такой код он считает переполнением. Впрочем, на UB не похоже, потому что по сути прямо написано, что значение заменяется на максимально допустимое.
Википедия
Википедия содержит две подходящие статьи:
Арифмети́ческое переполне́ние — специфичная для компьютерной арифметики ситуация, когда при арифметическом действии результат становится больше максимально возможного значения для переменной, использующейся для хранения результата.
Я не уверен, что приведение типа можно назвать арифметической операцией...
Целочи́сленное переполне́ние (англ. integer overflow) — ситуация в компьютерной арифметике, при которой вычисленное в результате операции значение не может быть помещено в n-битный целочисленный тип данных. Различают переполнение через верхнюю границу представления и через нижнюю (англ. Underflow).
Под это определение вроде приведение типа бы подходит, но тут есть два нюанса:
При конвертации между int и unsigned битность одинаковая, и в обоих типах значение, как бы, представимо - несмотря на то, что в этих типах это разное значение.
Завязка на целочисленность. Как быть с вариантом
float x = 1e300;
Тут вообще нет ничего целочисленного, но на мой взгляд выглядит как переполнение. Впрочем, тут ещё один нюанс - получается значение infinity, про которое затруднительно сказать, что оно непредставимо.
C#
А вот если изначальный код написать на C#
checked
{
int i = -10;
uint u = (uint)i;
}
То он кидает исключение
System.OverflowException: Arithmetic operation resulted in an overflow.
Получается, что для C# во-первых, это переполнение, а во-вторых, он рассматривает приведение типа как арифметическую операцию.
В то же время с вещественными числами его всё устраивает:
checked
{
Console.WriteLine((float)1e300);
}
Infinity
Zig
Zig на код
const std = @import("std");
const builtin = @import("builtin");
pub fn main() !void {
const x: i32 = -10;
const y: u32 = x;
std.debug.print("Zig {}\n", .{builtin.zig_version});
std.debug.print("x {}\n", .{x});
std.debug.print("y {}\n", .{y});
}
error: type 'u32' cannot represent integer value '-10'
но при этом не называет произошедшее переполнением.
Вопросы были в самом начале :)
Ответы (1 шт):
Поскольку “определение”, с математической точки зрения, ограничено документом в котором оно используется, то и определение понятия “переполнения” для разных языков программирования может быть различным. Далее рассмотрим, что такое переполнение в С/С++.
Начнём со второго вопроса, благо С/С++ предполагает возможность реализации IEC 60559 (IEEE 754), который писали видные математики.
С23 (ISO/IEC 9899:2023) в случае IEC 60559 (IEEE 754):
- Переполнение (
FE_OVERFLOW
/Overflow
) это исключение, которое возникает при выполнении тех или иных операций, которое, по умолчанию, регистрируется во флагах статуса и/или, возможно, вызывает прерывание программы; - Обычные операции (
+
/addition(x, y)
,fma()
/fusedMultiplyAdd(x, y, z)
или ,sqrt()
/squareRoot(x)
…), а так же приведение целого типа к плавающему типуconvertFromInt(int)
, должны выполнятся “абсолютно точно”, а результат округляться. При этом, как результат округления, может получиться ±∞; - В случае, если при округлении получается ±∞, возникает исключение переполнения. Как следствие, для операций с точным результатом равным ±∞, например,
0 + +∞ -> +∞
такового исключения не возникает; - Для операций преобразования к целому, таких как
lround()
/convertToIntegerTiesToAway(source)
и др., при невозможности представления в указанном целом формате, возникает исключение некорректной операции (FE_INVALID
/Invalid operation
); - Доступ к флагам статуса исключений с плавающей точкой (
fetestexcept()
,feclearexcept()
, …) гарантируется, если прагма FENV_ACCESS “on”; - Исключения с плавающей точкой должны учитываться в константных выражениях, если прагма FENV_ACCESS “on”;
- Указывается зависимыми от реализации (Unspecified behavior):
- Состояние флагов статуса исключений с плавающей точкой при передаче управления между частями с прагмой FENV_ACCESS “on” и “off”;
- Результат при преобразовании плавающего к целому, если возникло исключение некорректной операции (
FE_INVALID
/Invalid operation
);
С23 (ISO/IEC 9899:2023) безотносительно к IEC 60559 (IEEE 754):
- Указывается зависимыми от реализации (Unspecified behavior):
- Результат округления, если значение выходит за границы диапазона;
- Результат функций
lrint()
,llrint()
,lround()
иllround()
, если значение непредставимо соответствующим типом;
C++23 (ISO/IEC 14882:2023) холодно ссылается на актуальный ISO C.
Итого ответ на второй вопрос:
- Можно применять термин "переполнение" к действиям с плавающими числами, даже когда результатом может становится бесконечность (можно опросить флаги статуса исключений);
- Ваша изначальная формулировка про превышение максимального представимого значения в случае преобразования плавающего типа к целым типам неверна;
- Правда, в некоторых редких случаях, преобразования целых типов к плавающим типам, например
unsigned long
кfloat16_t
/binary16
, может возникать именно переполнение.
—
Относительно первого вопроса, к сожалению, ни C23, ни C++23 не содержат явного определения “переполнения” применительно к целым типам. Однако, “По плодам их узнаете их”.
Слово “overflow” встречается в С23 (ISO/IEC 9899:2023) всего на 42 страницах из 742, причём те из них, которые относятся к целым типам, описывают арифметические операции или вычисления выражений. Кроме, быть может, примечания к clock(void)
, но и там, скорее всего имеются ввиду переполнения при внутренних вычислениях.
С другой стороны, п. 6.3.1.3 описывает преобразование из знакового целого типа в беззнаковый без использования понятия “переполнения”. И обратное преобразование из беззнакового в знаковый, так же описывается без использования понятия “переполнения”, но как зависимое от реализации с возможным возникновением сигнала неопределённой природы.
Таким образом, с целым переполнениям дела обстоят примерно так же, как и с плавающим переполнением и, более менее, обоснованным ответом на первый вопрос в части C/C++ будет:
- беззнаковых переполнений не бывает, т.к. операции выполняются по модулю 2n;
- целые переполнения могут возникать при арифметических операциях и вычислении выражений целых знаковых типов;
- при преобразованиях между беззнаковыми и знаковыми целыми переполнений нет, но может возникать сигнал определяемый реализацией (соответственно, реализация его вправе назвать как угодно, в т.ч. и “overflow”, но это название уже за пределами языка С/С++).
—
В части реализаций можно отметить:
clang
поддерживает прагму FENV_ACCESS, поэтому в рамках C/C++ сравнительно легко доступны любые способы обработки любых исключений плавающей точки;gcc
не поддерживает прагму FENV_ACCESS, поэтому всё непросто. Можно ли обрабатывать исключение в константных выражениях, лично мне, совсем неясно. Опрашивать флаги статуса надо с оглядкой на оптимизатор, по базеvolatile
и т.п. нет, но тот жеNumPy
справляется. Ну или, как вариант, для исключения FE_INVALID включать работу сигнала SIGFPE с помощьюfeenableexcept()
,_controlfp_s()
или какой-то матери в зависимости от платформы.
-- Для экспериментов:
#define _GNU_SOURCE
#include <assert.h>
#include <fenv.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#ifndef NOT_FENV_ACCESS
#pragma STDC FENV_ACCESS ON
#endif
#ifndef USE_FEENABLEEXCEPT
#define FEENABLEEXCEPT(excepts)
#else
#define FEENABLEEXCEPT(excepts) feenableexcept(excepts)
#if defined(__APPLE__) && defined(__MACH__)
// Public domain polyfill for feenableexcept on OS X
// http://www-personal.umich.edu/~williams/archive/computation/fe-handling-example.c
#include <fenv.h>
static
inline int feenableexcept(unsigned int excepts)
{
static fenv_t fenv;
unsigned int new_excepts = excepts & FE_ALL_EXCEPT;
// previous masks
unsigned int old_excepts;
if (fegetenv(&fenv)) {
return -1;
}
old_excepts = fenv.__control & FE_ALL_EXCEPT;
// unmask
fenv.__control &= ~new_excepts;
fenv.__mxcsr &= ~(new_excepts << 7);
return fesetenv(&fenv) ? -1 : old_excepts;
}
#elif defined(_WIN32)
// https://stackoverflow.com/a/30175525/8585880
void feenableexcept(uint16_t fpflags){
/*edit 2015-12-17, my attempt at ASM code was giving me
*problems in more complicated scenarios, so I
*switched to using _controlfp_s. I finally posted it here
*because of the upvote to the ASM version.*/
/*{// http://stackoverflow.com/questions/247053/
uint16_t mask(FE_ALL_EXCEPT & ~fpflags);
asm("fldcw %0" : : "m" (mask) : "cc");
} //https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html */
unsigned int new_word(0);
if (fpflags & FE_INVALID) new_word |= _EM_INVALID;
if (fpflags & FE_DIVBYZERO) new_word |= _EM_ZERODIVIDE;
if (fpflags & FE_OVERFLOW) new_word |= _EM_OVERFLOW;
unsigned int cw(0);
_controlfp_s(&cw,~new_word,_MCW_EM);
}
#endif
#endif
void outtestexcept()
{
int e = fetestexcept(-1);
int unknown = ~(FE_DIVBYZERO|FE_INEXACT|FE_INVALID|FE_OVERFLOW|FE_UNDERFLOW);
printf("%s%s%s%s%s%s\n",
(e&FE_DIVBYZERO ? "FE_DIVBYZERO " : ""),
(e&FE_INEXACT ? "FE_INEXACT " : ""),
(e&FE_INVALID ? "FE_INVALID " : ""),
(e&FE_OVERFLOW ? "FE_OVERFLOW " : ""),
(e&FE_UNDERFLOW ? "FE_UNDERFLOW " : ""),
(e&unknown ? "unknown " : "")
);
}
int main()
{
feclearexcept(-1);
FEENABLEEXCEPT(~FE_INEXACT);
feclearexcept(-1);
const unsigned long cx = 1e20;
outtestexcept();
printf("cx: %lu\n", cx);
feclearexcept(-1);
unsigned long x = 1e20;
outtestexcept();
printf("x: %lu\n", x);
double dr = rand() + 1e20;
assert(dr >= 1e20);
feclearexcept(-1);
x = dr;
outtestexcept();
printf("%lg -> %lu\n", dr, x);
feclearexcept(-1);
x = lround(dr);
outtestexcept();
printf("%lg lround %lu\n", dr, x);
for(int i = 0; i < 4; i++) {
feclearexcept(-1);
dr *= 1e100;
outtestexcept();
printf("%lg\n", dr);
}
return 0;
}