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

Question

Со страницы руководства в моей системе:

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), но оно не определено, если src и dst указывают на разные блоки.«Не определено» означает, что вы даже не должны предполагать, что условие возвращает 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.На практике авторы компилятора могут просто поощрять сравнение неопределенного указателя с неопределенным поведением или использовать соответствующую прагму, чтобы заставить их компилятор правильно скомпилировать 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);
    }

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

Answer 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, по крайней мере, выглядит правдоподобным.

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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