integer overflow
От: jyuyjiyuijyu  
Дата: 24.05.11 11:26
Оценка:
Всем привет
при написании класса динамического массива озадачился проверкой на переполнение
решил посмотреть известные реализации взял файл garray.c из библиотеки GLIB
рассмотрим любую функцию оттуда например эту
GArray*
g_array_set_size (GArray *farray,
          guint   length)
{
  GRealArray *array = (GRealArray*) farray;
  if (length > array->len)
    {
      g_array_maybe_expand (array, length - array->len);
      
      if (array->clear)
    g_array_elt_zero (array, array->len, length - array->len);
    }
#ifdef ENABLE_GC_FRIENDLY  
  else if (length < array->len)
    g_array_elt_zero (array, length, array->len - length);
#endif /* ENABLE_GC_FRIENDLY */  
  
  array->len = length;
  
  g_array_zero_terminate (array);
  
  return farray;
}

самое в ней интересное это g_array_maybe_expand открываем смотрим
static gint
g_nearest_pow (gint num)
{
  gint n = 1;

  while (n < num)
    n <<= 1;

  return n;
}

static void
g_array_maybe_expand (GRealArray *array,
              gint        len)
{
  guint want_alloc = g_array_elt_len (array, array->len + len + 
                      array->zero_terminated);

  if (want_alloc > array->alloc)
    {
      want_alloc = g_nearest_pow (want_alloc);
      want_alloc = MAX (want_alloc, MIN_ARRAY_SIZE);

      array->data = g_realloc (array->data, want_alloc);

#ifdef ENABLE_GC_FRIENDLY
      memset (array->data + array->alloc, 0, want_alloc - array->alloc);
#endif /* ENABLE_GC_FRIENDLY */

      array->alloc = want_alloc;
    }
}

опять же в ней самое интересное это макрос g_array_elt_len смотрим
#define g_array_elt_len(array,i) ((array)->elt_size * (i))
#define g_array_elt_pos(array,i) ((array)->data + g_array_elt_len((array),(i)))

так вот первое переполнение при сложении array->len + len и второе при умножении
elt_size * (i) так вот при использовании GArray можно получать уникальные состояния
например
len = 2147484036
alloc = 1024
тоесть размер занимаемой памяти намного меньше длинны массива абсурд
но при некоторых обстоятельствах запросто подобную фигню получить
вот я пишу сейчас тоже массив и думаю бросить так или проверять на переполнение
если проверять то это тормоза придется к __int64 кастить не хотелось бы этого
оставить так быть неуверенным в правильных результатах всегда
что думаете по этому поводу ?
Re: integer overflow
От: Кодёнок  
Дата: 24.05.11 11:57
Оценка:
Здравствуйте, jyuyjiyuijyu, Вы писали:

J>что думаете по этому поводу ?


Для индексации и адресации используется тип вроде size_t, диапазон значений которого перекрывает максимально возможный размер массива, поэтому никто и не проверяет.
Re[2]: integer overflow
От: jyuyjiyuijyu  
Дата: 24.05.11 12:08
Оценка:
Здравствуйте, Кодёнок, Вы писали:

Кё>Здравствуйте, jyuyjiyuijyu, Вы писали:


J>>что думаете по этому поводу ?


Кё>Для индексации и адресации используется тип вроде size_t, диапазон значений которого перекрывает максимально возможный размер массива, поэтому никто и не проверяет.

если использовать size_t да еще на 64 битной машине то и на переполнение
не провериш на 32 битной хоть можно к 64 битам откастить и посмотреть
проблема не в типе (как раз наоборот тип 32 битный специально выбран
как размер массива его можно и на 32 и на 64 кастингом проверить) а в том что приходится
складывать и умножать цифры которые потенциально могут приводить к переполнениям
Re[3]: integer overflow
От: Ytz https://github.com/mtrempoltsev
Дата: 24.05.11 12:39
Оценка: 1 (1)
Здравствуйте, jyuyjiyuijyu, Вы писали:

J>если использовать size_t да еще на 64 битной машине то и на переполнение

J>не провериш на 32 битной хоть можно к 64 битам откастить и посмотреть

Да ладно. Только в качестве простого примера:
size_t c = a + b;
assert(c >= std::min(a, b));
Re[3]: integer overflow
От: B0FEE664  
Дата: 24.05.11 12:47
Оценка:
Здравствуйте, 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 ...;


А как правильно ?
И каждый день — без права на ошибку...
Re[4]: integer overflow
От: quodum  
Дата: 24.05.11 13:39
Оценка:
Здравствуйте, B0FEE664, Вы писали:


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>А как правильно ?


При сложении элементарно:

if ( a + b < a )
{
    // overflow!
}


NB: верно только для беззнаковых типов

С умножением уже сложнее.
Re[4]: integer overflow
От: jyuyjiyuijyu  
Дата: 24.05.11 14:04
Оценка:
Здравствуйте, 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
там кстати реализовано вычитанием и сравнением
вот кусок
size_type _Count = 0;
        _Distance(_First, _Last, _Count);
        size_type _Capacity = capacity();

        if (_Count == 0)
            ;
        else if (max_size() - size() < _Count)
            _Xlen();    // result too long
        else if (_Capacity < size() + _Count)
            {    // not enough room, reallocate
            _Capacity = max_size() - _Capacity / 2 < _Capacity
                ? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%
            if (_Capacity < size() + _Count)
                _Capacity = size() + _Count;
            pointer _Newvec = this->_Alval.allocate(_Capacity);
            pointer _Ptr = _Newvec;

            _TRY_BEGIN
            _Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where),
                _Newvec);    // copy prefix
            _Ptr = _Ucopy(_First, _Last, _Ptr);    // add new stuff
            _Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr);    // copy suffix
            _CATCH_ALL
            _Destroy(_Newvec, _Ptr);
            this->_Alval.deallocate(_Newvec, _Capacity);
            _RERAISE;
            _CATCH_END

            _Count += size();
            if (_Myfirst != 0)
                {    // destroy and deallocate old array
                _Destroy(_Myfirst, _Mylast);
                this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
                }

 #if _HAS_ITERATOR_DEBUGGING
            this->_Orphan_all();
 #endif /* _HAS_ITERATOR_DEBUGGING */

            _Myend = _Newvec + _Capacity;
            _Mylast = _Newvec + _Count;
            _Myfirst = _Newvec;
            }
        else
            {    // new stuff fits, append and rotate into place
            _Ucopy(_First, _Last, _Mylast);

            _Reverse(_Where._Myptr, _Mylast);
            _Reverse(_Mylast, _Mylast + _Count);
            _Reverse(_Where._Myptr, _Mylast + _Count);

            _Mylast += _Count;

 #if _HAS_ITERATOR_DEBUGGING
            _Orphan_range(_Where._Myptr, _Mylast);
 #endif /* _HAS_ITERATOR_DEBUGGING */

            }
        }

тут есть функция _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

результат неправильный
Re[5]: integer overflow
От: B0FEE664  
Дата: 24.05.11 14:39
Оценка:
Здравствуйте, quodum, Вы писали:

Q>При сложении элементарно:


Q>
if ( a + b < a )
Q>{
Q>    // overflow!
Q>}

Q>NB: верно только для беззнаковых типов

А разве здесь не undefined behavior в соответствии с пунктом 5.5 стандарта 2003-его года ?
И каждый день — без права на ошибку...
Re: integer overflow
От: Sorc17 Россия  
Дата: 24.05.11 15:35
Оценка:
Здравствуйте, jyuyjiyuijyu, Вы писали:

[skip]

Не лишне будет напомнить, что целочисленного переполнения не существует. Поэтому проверять на него не нужно.
Для нас [Thompson, Rob Pike, Robert Griesemer] это было просто исследование. Мы собрались вместе и решили, что ненавидим C++ [смех].
Re[2]: integer overflow
От: andrey_nado  
Дата: 24.05.11 16:13
Оценка:
Здравствуйте, Sorc17, Вы писали:

S>Не лишне будет напомнить, что целочисленного переполнения не существует. Поэтому проверять на него не нужно.


В смысле, не существует? При переполнении знакового целочисленного может быть UB.
Re[3]: integer overflow
От: Sir-G  
Дата: 24.05.11 17:24
Оценка:
_>При переполнении знакового целочисленного может быть UB.
Кстати где это в стандарте написано? И именно знакового?
Re[4]: integer overflow
От: B0FEE664  
Дата: 24.05.11 19:25
Оценка: 3 (1)
Здравствуйте, 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. ]

И каждый день — без права на ошибку...
Re[5]: integer overflow
От: uzhas Ниоткуда  
Дата: 24.05.11 19:45
Оценка: 4 (2)
Здравствуйте, 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.

Re[5]: integer overflow
От: dilmah США  
Дата: 24.05.11 19:46
Оценка: 3 (1)
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 по определению
Re[6]: integer overflow
От: quodum  
Дата: 25.05.11 05:50
Оценка:
Здравствуйте, B0FEE664, Вы писали:

Q>>
if ( a + b < a )
Q>>{
Q>>    // overflow!
Q>>}

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.

Re[6]: integer overflow
От: Sir-G  
Дата: 25.05.11 05:54
Оценка:
Господа, спасибо за ответы, буду знать!
Re[5]: integer overflow
От: xor90h  
Дата: 10.11.11 09:12
Оценка: -1
Здравствуйте, quodum, Вы писали:

Q>При сложении элементарно:


Q>
if ( a + b < a )
Q>{
Q>    // overflow!
Q>}


Скорее так:

if ( a + b < MAX(a,b) )
{
    // overflow!
}


Проверяется элементарно, для беззнаковых 8-ми битных интов: a = 3, b = 0xff. Ваш код переполнения не обнаружит.
Re[6]: integer overflow
От: Goodhope  
Дата: 10.11.11 09:37
Оценка:
Здравствуйте, 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-ми битных интов. Не?
Re: integer overflow
От: Pzz Россия https://github.com/alexpevzner
Дата: 10.11.11 09:42
Оценка:
Здравствуйте, jyuyjiyuijyu, Вы писали:

J>вот я пишу сейчас тоже массив и думаю бросить так или проверять на переполнение

J>если проверять то это тормоза придется к __int64 кастить не хотелось бы этого
J>оставить так быть неуверенным в правильных результатах всегда
J>что думаете по этому поводу ?

1. Задолго до переполнения кончится память

2. Можно и не кастить. Пусть c = a + b. Если произошло переполнение, то c будет меньше a и меньше b. Если переполнения не произошло, c будет больше или равен a и b. Верно для любого целочисленного типа, если арифметика двоичная и работает так, как она везде работает
Re[4]: integer overflow
От: Pzz Россия https://github.com/alexpevzner
Дата: 10.11.11 09:43
Оценка:
Здравствуйте, Ytz, Вы писали:

Ytz>Да ладно. Только в качестве простого примера:

Ytz>
Ytz>size_t c = a + b;
Ytz>assert(c >= std::min(a, b));
Ytz>


Можно и без min'а.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.