Как реализовать memmove в стандартном C без промежуточной копии?

На странице man в моей системе:

void * memmove (void * dst, const void * src, size_t len);

ОПИСАНИЕ
Функция memmove() копирует len байты из строки src в строку dst.
Две строки могут перекрываться; копия всегда выполняется в неразрушающем режиме манера.

Из стандарта C99:

6.5.8.5 Когда сравниваются два указателя, результат зависит от относительные местоположения в адресе пространство объектов, на которые указывает. Если два указателя на объект или неполный типы указывают на один и тот же объект, или оба указывают один за последний элемент одного и того же объекта массива, они равны. Если объекты указывающие на членов одного и того же совокупный объект, указатели на члены структуры, объявленные позже сравнить больше, чем указатели на участников, ранее заявленных в структура и указатели на массив элементы с большими значениями индекса сравнить больше, чем указатели на элементы того же массива с более низким индексы. Все указатели на члены одного и того же объекта объединения сравните равные. Если выражение Pуказывает на элемент массива объект и выражение Q указывает на последний элемент того же массива объект, выражение указателя Q+1сравнивается больше P. В целом в других случаях поведение undefined.

Акцент мой.

Аргументы dst и src могут быть преобразованы в указатели на char, чтобы облегчить проблемы с строгим псевдонимом, но можно ли сравнить два указателя, которые могут указывать внутри разных блоков, чтобы сделать копию в правильном порядке в случае, если они указывают внутри одного и того же блока?

Очевидным решением является if (src < dst), но это undefined, если src и dst указывают на разные блоки. "Undefined" означает, что вы даже не должны предполагать, что условие возвращает 0 или 1 (это было бы названо "неуказанным" в стандартном словаре).

Альтернативой является if ((uintptr_t)src < (uintptr_t)dst), который по крайней мере не указан, но я не уверен, что стандарт гарантирует, что при src < dst он эквивалентен (uintptr_t)src < (uintptr_t)dst). Сравнение указателей определяется из арифметики указателя. Например, когда я читал раздел 6.5.6 о добавлении, мне кажется, что арифметика указателя может идти в направлении, противоположном арифметике uintptr_t, то есть, что совместимый компилятор может иметь, когда P имеет тип char*:

((uintptr_t)p)+1==((uintptr_t)(p-1)

Это только пример. Как правило, очень мало гарантируется при преобразовании указателей в целые числа.

Это чисто академический вопрос, потому что memmove предоставляется вместе с компилятором. На практике авторы компилятора могут просто продвигать сравнение указателей undefined с неуказанным поведением или использовать соответствующую прагму, чтобы заставить их компилятор правильно компилировать их memmove. Например, эта реализация имеет этот фрагмент:

if ((uintptr_t)dst < (uintptr_t)src) {
            /*
             * As author/maintainer of libc, take advantage of the
             * fact that we know memcpy copies forwards.
             */
            return memcpy(dst, src, len);
    }

Я бы по-прежнему хотел бы использовать этот пример в качестве доказательства того, что стандарт заходит слишком далеко с поведением undefined, если верно, что memmove не может быть эффективно реализовано в стандартном C. Например, никто не отметит, когда отвечает этот вопрос SO.

Ответ 1

Я думаю, что вы правы, невозможно реализовать memmove эффективно в стандартном C.

Единственный по-настоящему портативный способ проверить, перекрывают ли регионы, я думаю, что-то вроде этого:

[Edit: посмотрев это намного позже, я думаю, что это должно быть dst+len-1 в конце второй строки. Но я не могу его проверить, поэтому я уйду, как сейчас, возможно, я знал, о чем я говорил в первый раз.]

for (size_t l = 0; l < len; ++l) {
    if (src + l == dst) || (src + l == dst + len) {
      // they overlap, so now we can use comparison,
      // and copy forwards or backwards as appropriate.
      ...
      return dst;
    }
}
// No overlap, doesn't matter which direction we copy
return memcpy(dst, src, len);

Вы не можете реализовать либо memcpy, либо memmove все, что эффективно в переносном коде, потому что реализация на платформе, скорее всего, приведет вас к тому, что вы делаете. Но портативный memcpy по крайней мере выглядит правдоподобным.

В С++ была введена указательная специализация std::less, которая определена для работы для любых двух указателей того же типа. Теоретически он может быть медленнее, чем <, но, очевидно, на несегментированной архитектуре это не так.

C не имеет такой вещи, поэтому в некотором смысле стандарт С++ согласен с вами в том, что C не имеет достаточно определенного поведения. Но тогда С++ нуждается в нем для std::map и так далее. Скорее всего, вы захотите реализовать std::map (или что-то вроде этого) без знания реализации, чем то, что вы хотели бы реализовать memmove (или что-то вроде этого) без знания реализации.

Ответ 2

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

Причина других ситуаций undefined заключается в том, что два разных объекта могут быть даже не в одном и том же виде с одним и тем же указателем. На архитектуре ПК адреса обычно представляют собой только 32-разрядный адрес в виртуальной памяти, но C поддерживает всевозможные причудливые архитектуры, где память не что иное.

Причина, по которой C оставляет вещи undefined, - дать возможность авторам компилятора, когда ситуация не требуется определять. Способ чтения 6.5.8.5 - это аббревиатура, в котором подробно описываются архитектуры, которые C хочет поддерживать, когда сравнение указателей не имеет смысла, если оно не находится внутри одного и того же объекта.

Кроме того, причина memmove и memcpy предоставлена компилятором в том, что они иногда записываются в настроенной сборке для целевого ЦП с использованием специализированной инструкции. Они не предназначены для реализации на C с такой же эффективностью.

Ответ 3

Для начала стандарт C печально известен наличием проблем в таких деталях. Частью проблемы является то, что C используется на нескольких платформах, а стандартный пытается быть достаточно абстрактным, чтобы охватить все текущие и будущие платформы (которые могут использовать некоторую изогнутую структуру памяти, которая превосходит все, что мы когда-либо видели). Существует много undefined или специфичного для реализации поведения, чтобы писатели компилятора могли "делать правильные вещи" для целевой платформы. Включение деталей для каждой платформы было бы непрактичным (и постоянно устаревшим); вместо этого, стандарт C оставляет его компилятору для документирования того, что происходит в этих случаях. "Неуказанное" поведение означает только то, что в стандарте C не указывается, что происходит, не обязательно, чтобы результат не мог быть предсказан. Результат обычно остается предсказуемым, если вы читаете документацию для своей целевой платформы и вашего компилятора.

Поскольку определение того, указывают ли два указателя на один и тот же блок, сегмент памяти или адресное пространство, зависит от того, как выкладывается память для этой платформы, спецификация не определяет способ сделать это определение. Предполагается, что компилятор знает, как сделать это определение. Часть указанной вами спецификации говорит, что результат сравнения указателя зависит от "относительного местоположения указателей в адресном пространстве". Обратите внимание, что "адресное пространство" здесь является единственным. Этот раздел относится только к указателям, которые находятся в одном и том же адресном пространстве; то есть указатели, которые непосредственно сопоставимы. Если указатели находятся в разных адресных пространствах, результат undefined по стандарту C и определяется в соответствии с требованиями целевой платформы.

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

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

Ответ 4

Вот еще одна идея, но я не знаю, правильно ли она. Чтобы избежать цикла O(len) в ответе Стива, можно поместить его в #else предложение #ifdef UINTPTR_MAX с реализацией cast-to-uintptr_t. При условии, что отбрасывание unsigned char * до uintptr_t коммутирует с добавлением целочисленных смещений всякий раз, когда смещение допустимо с помощью указателя, это делает сравнение указателя корректным.

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

Ответ 5

Я бы по-прежнему хотел бы использовать этот пример в качестве доказательства того, что стандарт заходит слишком далеко с поведениями undefined, если верно, что memmove не может быть эффективно реализован в стандартном C

Но это не доказательство. Нет абсолютно никакого способа гарантировать, что вы можете сравнить два произвольных указателя на произвольной машинной архитектуре. Поведение такого сравнения указателей не может быть регламентировано стандартом C или даже компилятором. Я мог бы представить себе машину с сегментированной архитектурой, которая может привести к другому результату в зависимости от того, как сегменты организованы в ОЗУ или даже может выбрать исключение при сравнении указателей на разные сегменты. Вот почему поведение "undefined". Точная же программа на той же машине может дать разные результаты от запуска для запуска.

Часто заданное "решение" memmove(), использующее отношение двух указателей, чтобы выбрать, следует ли копировать от начала до конца или от конца до начала, работает только в том случае, если все блоки памяти распределены с одного и того же адреса пространство. К счастью, это обычно так, хотя это было не во времена 16-битного x86-кода.