Всем привет
при написании класса динамического массива озадачился проверкой на переполнение
решил посмотреть известные реализации взял файл garray.c из библиотеки GLIB
рассмотрим любую функцию оттуда например эту
так вот первое переполнение при сложении array->len + len и второе при умножении
elt_size * (i) так вот при использовании GArray можно получать уникальные состояния
например
len = 2147484036
alloc = 1024
тоесть размер занимаемой памяти намного меньше длинны массива абсурд
но при некоторых обстоятельствах запросто подобную фигню получить
вот я пишу сейчас тоже массив и думаю бросить так или проверять на переполнение
если проверять то это тормоза придется к __int64 кастить не хотелось бы этого
оставить так быть неуверенным в правильных результатах всегда
что думаете по этому поводу ?
Здравствуйте, jyuyjiyuijyu, Вы писали:
J>что думаете по этому поводу ?
Для индексации и адресации используется тип вроде size_t, диапазон значений которого перекрывает максимально возможный размер массива, поэтому никто и не проверяет.
Здравствуйте, Кодёнок, Вы писали:
Кё>Здравствуйте, jyuyjiyuijyu, Вы писали:
J>>что думаете по этому поводу ?
Кё>Для индексации и адресации используется тип вроде size_t, диапазон значений которого перекрывает максимально возможный размер массива, поэтому никто и не проверяет.
если использовать size_t да еще на 64 битной машине то и на переполнение
не провериш на 32 битной хоть можно к 64 битам откастить и посмотреть
проблема не в типе (как раз наоборот тип 32 битный специально выбран
как размер массива его можно и на 32 и на 64 кастингом проверить) а в том что приходится
складывать и умножать цифры которые потенциально могут приводить к переполнениям
Здравствуйте, jyuyjiyuijyu, Вы писали:
J>если использовать size_t да еще на 64 битной машине то и на переполнение J>не провериш на 32 битной хоть можно к 64 битам откастить и посмотреть
Здравствуйте, jyuyjiyuijyu, Вы писали:
J>Здравствуйте, Кодёнок, Вы писали:
Кё>>Здравствуйте, jyuyjiyuijyu, Вы писали:
J>>>что думаете по этому поводу ?
Кё>>Для индексации и адресации используется тип вроде size_t, диапазон значений которого перекрывает максимально возможный размер массива, поэтому никто и не проверяет. J>если использовать size_t да еще на 64 битной машине то и на переполнение J>не провериш на 32 битной хоть можно к 64 битам откастить и посмотреть J>проблема не в типе (как раз наоборот тип 32 битный специально выбран J>как размер массива его можно и на 32 и на 64 кастингом проверить) а в том что приходится J>складывать и умножать цифры которые потенциально могут приводить к переполнениям
Мне тоже интересен этот вопрос.
Понятно, что не обязательно иметь тип с удвоенной разрядностью. Можно делать что-то вроде такого:
unsigned int a = ...;
unsigned int b = ...;
...
unsigned int a_half = a / 2;
unsigned int b_half = b / 2;
unsigned int max_half = UINT_MAX / 2;
unsigned int AplusB = 0;
if ( a_half + b_half < max_half )
// a и b можно складывать
AplusB = a + b;
else// возможно переполнениеthrow ...;
BFE>Мне тоже интересен этот вопрос. BFE>Понятно, что не обязательно иметь тип с удвоенной разрядностью. Можно делать что-то вроде такого:
BFE>[ccode] BFE>unsigned int a = ...; BFE>unsigned int b = ...; BFE>... BFE>unsigned int a_half = a / 2; BFE>unsigned int b_half = b / 2; BFE>unsigned int max_half = UINT_MAX / 2;
BFE>unsigned int AplusB = 0;
BFE>А как правильно ?
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, jyuyjiyuijyu, Вы писали:
J>>Здравствуйте, Кодёнок, Вы писали:
Кё>>>Здравствуйте, jyuyjiyuijyu, Вы писали:
J>>>>что думаете по этому поводу ?
Кё>>>Для индексации и адресации используется тип вроде size_t, диапазон значений которого перекрывает максимально возможный размер массива, поэтому никто и не проверяет. J>>если использовать size_t да еще на 64 битной машине то и на переполнение J>>не провериш на 32 битной хоть можно к 64 битам откастить и посмотреть J>>проблема не в типе (как раз наоборот тип 32 битный специально выбран J>>как размер массива его можно и на 32 и на 64 кастингом проверить) а в том что приходится J>>складывать и умножать цифры которые потенциально могут приводить к переполнениям
BFE>Мне тоже интересен этот вопрос. BFE>Понятно, что не обязательно иметь тип с удвоенной разрядностью. Можно делать что-то вроде такого:
BFE>
BFE>unsigned int a = ...;
BFE>unsigned int b = ...;
BFE>...
BFE>unsigned int a_half = a / 2;
BFE>unsigned int b_half = b / 2;
BFE>unsigned int max_half = UINT_MAX / 2;
BFE>unsigned int AplusB = 0;
BFE>if ( a_half + b_half < max_half )
BFE> // a и b можно складывать
BFE> AplusB = a + b;
BFE>else
BFE> // возможно переполнение
BFE> throw ...;
BFE>
BFE>А как правильно ?
Ytz
а умножение ?
B0FEE664
пока вижу или юзать кастинг для проверки переполнения при умножении
или изменить алгоритм чтоб убрать умножение из него сейчас вот ковыряю STL
там кстати реализовано вычитанием и сравнением
вот кусок
тут есть функция _Distance которая считает сколько надо добавить элементов
внутри у нее это _Off += _Last — _First;
и вот что интересно если при вычитании а потом делении на размер типа может
распростринится знаковый бит вместо shr там sar в итоге дает неправильное
количество элементов для например такого кода
vector<short> v;
v.assign((short*)0x2,(short*)0x80000002);
то казалось бы он должен продсчитать 1073741824 элементов между этими адресами
а выдает _Off = 3221225472 следом валит проверку тут (max_size() — size() < _Count)
и выкидывает ассерт но по крайней мере уникальных состояний нет в STL алгоритме
наверное его и реализую у себя
интересно почему правильное количество элементов между указателями выполеяется только
если знаковый бит сброшен у результата который делится на размер типа вот что для этого кода сгенерено
short *_Last = 0x80000002, *_First = 0x2;
_Off += _Last - _First;
00414F72 8B 45 0C mov eax,dword ptr [_Last]
00414F75 2B 45 08 sub eax,dword ptr [_First]
00414F78 D1 F8 sar eax,1 ; вот тут если знаковй бит есть быть беде
00414F7A 8B 4D 10 mov ecx,dword ptr [_Off]
00414F7D 03 01 add eax,dword ptr [ecx]
00414F7F 8B 55 10 mov edx,dword ptr [_Off]
00414F82 89 02 mov dword ptr [edx],eax
Здравствуйте, Sir-G, Вы писали:
_>>При переполнении знакового целочисленного может быть UB. SG>Кстати где это в стандарте написано? И именно знакового?
Именно знакового — не знаю, но есть общий пункт (ANSI ISO IEC 14882 2003):
5.5
If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable
values for its type, the behavior is undefined, unless such an expression is a constant expression
(5.19), in which case the program is ill-formed.
[Note: most existing implementations of C + + ignore integer
overflows. Treatment of division by zero, forming a remainder using a zero divisor, and all floating point
exceptions vary among machines, and is usually adjustable by a library function. ]
Здравствуйте, B0FEE664, Вы писали:
BFE>Именно знакового — не знаю, но есть общий пункт (ANSI ISO IEC 14882 2003):
3.9.1 Fundamental types
4 Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2n where n is the number
of bits in the value representation of that particular size of integer.41)
41) This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer
type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer
type.
BFE>Именно знакового — не знаю, но есть общий пункт (ANSI ISO IEC 14882 2003):
BFE>[q] BFE>5.5 BFE>If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable BFE>values for its type, the behavior is undefined,
беззнаковое переполнение всегда было well-defined, потому что оно определяется по модулю степени двойки.
Соответственно, твой пункт не применим, потому что результат попадает в range по определению
Q>>NB: верно только для беззнаковых типов
BFE>А разве здесь не undefined behavior в соответствии с пунктом 5.5 стандарта 2003-его года ?
Пункт 5.5 называется "5.5 Pointer-to-member operators". В данном случае применяется параграф 4 главы "3.9.1 Fundamental types":
Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2**n where n is the number
of bits in the value representation of that particular size of integer.
Здравствуйте, xor90h, Вы писали:
X>Здравствуйте, quodum, Вы писали:
Q>>При сложении элементарно:
Q>>
if ( a + b < a )
Q>>{
Q>> // overflow!
Q>>}
X>Скорее так:
X>
if ( a + b < MAX(a,b) )
X>{
X> // overflow!
X>}
X>Проверяется элементарно, для беззнаковых 8-ми битных интов: a = 3, b = 0xff. Ваш код переполнения не обнаружит.
3 + 0xff = 2 для беззнаковых 8-ми битных интов. Не?
Здравствуйте, jyuyjiyuijyu, Вы писали:
J>вот я пишу сейчас тоже массив и думаю бросить так или проверять на переполнение J>если проверять то это тормоза придется к __int64 кастить не хотелось бы этого J>оставить так быть неуверенным в правильных результатах всегда J>что думаете по этому поводу ?
1. Задолго до переполнения кончится память
2. Можно и не кастить. Пусть c = a + b. Если произошло переполнение, то c будет меньше a и меньше b. Если переполнения не произошло, c будет больше или равен a и b. Верно для любого целочисленного типа, если арифметика двоичная и работает так, как она везде работает