СИ. Указатели. Можно ли к указателю прибавить любое число?

[bondkim137]

venco в сообщении #1073475 писал(а):

Проблема в том, что выбранный вами метод преобразования в стандарте определён как "undefined behavior"

Почему? Разве стандартом не определяется разность указателей? А исходя из аддитивности указателей можно обойти и такое корючкотворство, как использование указателей на непонятно что - например, вычитать не NULL, а фиксированный указатель на какой-нить элемент любого живого массива. В итоге сами приведения изменятся, но работоспособность всей неэкзотики останется

-- 14.11.2015, 22:33 --

venco в сообщении #1073475 писал(а):

Здесь на некоторых новых версиях gcc, которые слишком строго следуют букве стандарта языка, не срабатывал assert(). Т.к. по стандарту переполнениые знаковых целых - "undefined behavior", оптимизатор выкинул проверку и диагностику, которую проверка должна вызвать. Так вот многие операции с указателями на разные объекты или массивы по стандарту тоже - "undefined behavior", и то, что они сейчас работают - следствие доброты авторов компиляторов. Они пока прощают такое, но т.к. это мешает оптимизатору, могут и закрутить гайки в будущем.

скорее подкрутят стандарт

вот пример функции условного присвоения:

Используется синтаксис C++

int32 BaseSignMove(int32 a, int32 b, int32 a1, int32 b1) {
        #ifdef BASE_COND_MOVE
                return (a1 - b1 < 0) ? a : b;
        #else
                i32 mask = ((a1 - b1) >> 31);
                return (a & mask) | (b & ~mask);
        #endif
}
 

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

[venco]

bondkim137 в сообщении #1073478 писал(а):

venco в сообщении #1073475 писал(а):

Проблема в том, что выбранный вами метод преобразования в стандарте определён как "undefined behavior"

Почему? Разве стандартом не определяется разность указателей?

Стандартом определяются арифметические операции с указателями только в пределах одного массива, увы.

[bondkim137]

venco в сообщении #1073490 писал(а):

Стандартом определяются арифметические операции с указателями только в пределах одного массива, увы.

понятно.

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

я не высасываю кейз из пальца: например, при построении дерева с ключами-указателями, вообще необходимо сравнивать указатели из разных массивов (если быть точным, указатели на одиночные объекты)

[venco]

Сравнивать можно, результат сравнения для несвязанных указателей по стандарту "unspecified", т.е. зависит от обстоятельств, например порядка вызова operator new, или порядка файлов в командной строке линкера.
А вот сложение и вычитание гарантируются только в пределах одного массива.

[bondkim137]

venco в сообщении #1073547 писал(а):

Сравнивать можно, результат сравнения для несвязанных указателей по стандарту "unspecified", т.е. зависит от обстоятельств, например порядка вызова operator new, или порядка файлов в командной строке линкера.
А вот сложение и вычитание гарантируются только в пределах одного массива.

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

[Munin]

Представим себе такую реализацию:
- каждый указатель состоит из двух чисел: ID блока памяти, и номер байта в блоке;
- при сравнении указателей внутри одного блока, они сравниваются как обычные целые числа; все массивы, разумеется, в пределах одного блока;
- при сравнении указателей с разными ID блоков, если указатели равны - результат сравнения "равны";

если указатели не равны, то поднимаются одновременно флаги и "больше", и "меньше", так что:
p1 == p2 - false
p1 != p2 - true
p1 < p2   - true
p1 >= p2 - false (поскольку то же, что !(p1 < p2))
p1 > p2   - true
p1 <= p2 - false (поскольку то же, что !(p1 > p2))

Противоречит ли такая реализация стандарту?

[venco]

bondkim137 в сообщении #1073573 писал(а):

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

А оно упорядоченное. "unspecified" значит, что конкретный результат сравнения не определён стандартом. Там перечислены варианты, где порядок определён, например, элементы одного массива, или не-статические члены одного объекта, или сравнение с NULL, и т.п. А если указатели относятся к разным объектам, то стандарт не обещает, что, например, указатель на объект, выделенный в куче раньше, будет меньше. Или какой порядок у указателей на статические объекты даже в одном исходном файле.

-- Сб ноя 14, 2015 21:58:49 --

Munin в сообщении #1073579 писал(а):

Противоречит ли такая реализация стандарту?

Оказывается, нет:

Цитата:

Although the results of comparing pointers of random origin (e.g. not all pointing to members of the same array) is unspecified, many implementations provide strict total ordering of pointers, e.g. if they are implemented as addresses within continuous virtual address space. Those implementations that do not (e.g. where not all bits of the pointer are part of a memory address and have to be ignored for comparison, or an additional calculation is required or otherwise pointer and integer is not a 1 to 1 relationship), provide a specialization of std::less for pointers that has that guarantee. This makes it possible to use all pointers of random origin as keys in standard associative containers such as std::set or std::map.

Т.е. даже если встроенные операции сравнения указателей плохие, то стандартная библиотека должна определить правильный функтор std::less, который и будет использоваться в стандартных классах и алгоритмах. Понятно, что обычные архитектуры определяют хороший оператор сравнения. Тем не менее, если хочется гарантированной переносимости, то кроме == и != других сравнений несвязанных указателей использовать нельзя.

[bondkim137]

venco в сообщении #1073584 писал(а):

Munin в сообщении #1073579 писал(а):

Противоречит ли такая реализация стандарту?

Оказывается, нет:

Но ведь еще определен оператор приведения указателя к целому числу и назад. По стандарту для любого указателя конверсия туда-обратно вернет исходный указатель?
Если да, то можно (и нужно наверное) определить 'хороший', транзитивный оператор сравнения.

Приземляясь в практическую плоскость: во времена перехода с 16-ти разрядных на 32-х разрядные компьютеры (MS-DOS) использовалась сегментная адресация памяти. Указатель состоял из 16-битного дескриптора и 16-разрядного смещения в массиве. Как был определен оператор сравнения? Если (и скорее всего) он был определен, как сравнение смещений внутри одинаковых дескрипторов (массивов), а для разных дескрипторов просто сравнивались двоичные представления этих дескрипторов - то транзитивность сохранялась. Но! Т.к. адресная область различных дескрипторов могла пересекаться, то можно было сжульничать и адресовать один и тот же элемент массива разными неравными указателями - правда пришлось бы выйти за пределы стандарта C++ в архитектуру x86

[aa_dav]

bondkim137 в сообщении #1073667 писал(а):

правда пришлось бы выйти за пределы стандарта C++ в архитектуру x86

Да в общем то это было сразу же сделано в 16-битных x86.
Сегментная модель памяти ввела в язык расширения связанные как раз с длинными указетелями - ключевые слова near/far и специфику работы с ними.
Причём если в DOS из сегмент:смещение можно было получить физический адрес нехитрой арифметикой, но в защищенном режиме 16-битного Windows 1/2/3 сегмент был именно ничем иным как ID дескриптора - структуры в памяти ядра, то честное сравнение длинных указателей могло бы превратится в вызов системных функций, что довольно таки тяжело.
Но в этой среде программировать не довелось, так что не знаю как реализовано было.

[bondkim137]

aa_dav в сообщении #1073692 писал(а):

Но в этой среде программировать не довелось, так что не знаю как реализовано было.

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

[aa_dav]

bondkim137 в сообщении #1073702 писал(а):

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

Да тут в общем то нет противоречия стандарту - который собственно так и говорит, что если не получил указатели из одного эм... "источника", т.е. массива или структуры - то для них ничего не обещается. В общем то с оглядкой на это он такое и заявляет.
С другой стороны иная программа из DOS при компиляции сейчас где нибудь под просто откажет на "необъявленный идентификатор" near или far. С этой стороны они сразу же вне стандарта наверное.

[Munin]

venco в сообщении #1073584 писал(а):

Тем не менее, если хочется гарантированной переносимости, то кроме == и != других сравнений несвязанных указателей использовать нельзя.

И std::less, как вы только что сказали. Ну, это и решает проблему, imho.

bondkim137 в сообщении #1073667 писал(а):

Но ведь еще определен оператор приведения указателя к целому числу и назад.

Но вот сравнение чисел после такой конверсии не обязано совпадать со сравнением указателей.

bondkim137 в сообщении #1073667 писал(а):

Приземляясь в практическую плоскость: во времена перехода с 16-ти разрядных на 32-х разрядные компьютеры (MS-DOS) использовалась сегментная адресация памяти. Указатель состоял из 16-битного дескриптора и 16-разрядного смещения в массиве.

Это вы забыли про указатели, состоящие из 16-битного дескриптора и 32-битного смещения :-)

bondkim137 в сообщении #1073667 писал(а):

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

Ещё хуже было чуть раньше, когда дескрипторы ещё не были дескрипторами, а были адресами сегментов, и складывались со смещением чисто арифметически...

Эхъ, ностальгия... Ладно, если по делу: щас это нам грозит? Если да, то видимо, реализация (компайлер + стандартная библиотека + исполняющая система) должны давать какие-то гарантии на этот счёт, а если не могут - то не носить им гордого звания реализации стандарта.

[bondkim137]

Munin в сообщении #1073713 писал(а):

bondkim137 в сообщении #1073667 писал(а):

Но ведь еще определен оператор приведения указателя к целому числу и назад.

Но вот сравнение чисел после такой конверсии не обязано совпадать со сравнением указателей.

А вроде и не надо. Строгое равенство будет совпадать, т.к. конверсия однозначная. А нестрогое сравнение будет однозначно обладать транзитивностью. Хоть и своей транзитивностью, но для решения практических задач (при работе с коллекциями) этого более чем достаточно.

Munin в сообщении #1073713 писал(а):

Это вы забыли про указатели, состоящие из 16-битного дескриптора и 32-битного смещения

Не забыл, засорять эфир не стал.
Но нереальный режим, вроде как, осознанно не поддерживался компиляторами и остался в хрониках джедаев, практиковавших ассемблер, и был быстро замещен честным FLAT, в котором мы и живет до сих пор, расширив его до 64-х бит.

Munin в сообщении #1073713 писал(а):

Ещё хуже было чуть раньше, когда дескрипторы ещё не были дескрипторами, а были адресами сегментов, и складывались со смещением чисто арифметически...

Особенно замечательно, что этим все пользовались вопреки стандартам C++. В частности, делая паттерны для реализации больших (более 64K) массивов.

Munin в сообщении #1073713 писал(а):

Эхъ, ностальгия... Ладно, если по делу: щас это нам грозит? Если да, то видимо, реализация (компайлер + стандартная библиотека + исполняющая система) должны давать какие-то гарантии на этот счёт, а если не могут - то не носить им гордого звания реализации стандарта.

Щас на всех неэкзотических платформах, включая смартфоны и wifi-коробочки, мы живем в FLAT64 (иногда FLAT32), на практике все указатели и есть прямые адреса в адресном пр-ве процесса и все замечательно.

Также знаковые числа представлены как дополнение до двойки, их переполнение при сложении/вычитании определено и аналогично беззнаковым. А при умножении почти всегда остается остаток по степени двойки и почти везде уже LITTLE-ENDIAN

[Munin]

bondkim137 в сообщении #1073719 писал(а):

А вроде и не надо. Строгое равенство будет совпадать, т.к. конверсия однозначная.

Как мы только что выяснили на примере "реального режима" архитектуры 386, это не так: конверсия может быть взаимно-однозначной, но строгое равенство при этом не совпадает. И наоборот, при совпадении строгого равенства, не будет взаимно-однозначной конверсии. Что не подходит к стандарту.

bondkim137 в сообщении #1073719 писал(а):

Но нереальный режим, вроде как, осознанно не поддерживался компиляторами

Как раз ровно в нём-то вся Винда и существовала и продолжает существовать (x32).

Ладно, я из разговора выхожу. venco молчит, а понтующихся невежд мне в этом мире давным-давно хватило.

[bondkim137]

Munin в сообщении #1073722 писал(а):

Как мы только что выяснили на примере "реального режима" архитектуры 386, это не так: конверсия может быть взаимно-однозначной, но строгое равенство при этом не совпадает. И наоборот, при совпадении строгого равенства, не будет взаимно-однозначной конверсии. Что не подходит к стандарту.

Нет, я имел в виду строгое равенство указателей друг-другу (что достаточно для коллекций).
Я не имел в виду соответсвие физических адресов и указателей. Эту задачу приведение к int естесвенно не решает, и в общем случае ее решить невозможно.

-- 15.11.2015, 16:48 --

Munin в сообщении #1073722 писал(а):

Как раз ровно в нём-то вся Винда и существовала и продолжает существовать (x32).

Для нас, как разработчиков пользовательского ПО, это не видно. С появления расширителей DOS и Win95 можно считать, что мы живем в FLAT.