реализация memmove на C

Может ли кто-нибудь помочь мне понять, как memmove реализован в C. У меня есть только одно особое условие, верно?

if((src<dst)&&((src+sz) > dst))

copy from the back

Также это зависит от того, как растет стек?


c memmove
person brett    schedule 26.08.2010    source источник
comment
Если src, dst и sz все положительные значения, условие невыполнимо. Если src > dst, добавление к нему положительного sz не сделает его меньше.   -  person Edmund    schedule 26.08.2010
comment
У меня всегда было сомнение. Можно ли сравнивать адреса, как это делали вы? Я где-то слышал, что они не могут быть, если они не принадлежат к одному и тому же массиву или структуре. Кто-нибудь, проясните!   -  person aniztar    schedule 25.12.2018

Ответы (3)


arrow_upward
32
arrow_downward

Математически вам не нужно беспокоиться о том, перекрываются ли они вообще. Если src меньше dst, просто скопируйте с конца. Если src больше, чем dst, просто скопируйте с самого начала.

Если src и dst равны, сразу выходите.

Это потому, что ваши дела являются одним из:

1) <-----s----->                start at end of s
                 <-----d----->

2) <-----s----->                start at end of s
            <-----d----->

3) <-----s----->                no action
   <-----d----->

4)          <-----s----->       start at beginning of s
   <-----d----->

5)               <-----s----->  start at beginning of s
   <-----d----->

Даже если нет перекрытия, это все равно будет работать нормально и упростит ваши условия.

Если у вас есть более эффективный способ копирования вперед, чем назад, тогда да, вам следует проверить наложение, чтобы убедиться, что вы используете более эффективный метод, если это возможно. Другими словами, измените вариант 1 выше, чтобы скопировать с самого начала.

person paxdiablo    schedule 26.08.2010
comment
Обратите внимание, что здесь есть еще одно скрытое предположение, заключающееся в том, что вы копируете только байт за раз. - person caf; 27.08.2010
comment
Что ж, копируете ли вы байт за раз, четверное слово или какое-то массивное 1024-битное значение гиперслова SSE9, теория остается неизменной. Вы должны убедиться, что вы не копируете в область перекрытия, из которой вы еще не скопировали из. Все параметры N-is-wider-than-char представляют собой несколько более сложное обнаружение перекрытия (и окончательный перенос) в случае, когда оно не является прямым кратным значению N. - person paxdiablo; 27.08.2010
comment
@caf: Если src и dest имеют одинаковое выравнивание по отношению к более крупному типу, который вы можете скопировать, вам никогда не придется беспокоиться о затирании области, которую вы еще не скопировали, поскольку позиции всегда будут отличаться как минимум на этот размер. Если они не имеют одинакового выравнивания, вы все равно застряли при копировании как байты... если только вы не хотите использовать какой-то неприятный невыровненный x86 io... - person R.. GitHub STOP HELPING ICE; 04.09.2010
comment
@R..: Во многих системах, по крайней мере, если вы используете разумный диалект C, который позволяет обойти ограничения псевдонимов, операции копирования, которые изменяют выравнивание, все еще могут выполняться путем чтения и записи нескольких слов за раз, если, например, один захватывает слово и извлекает части, а затем при каждом проходе цикла считывает (например) четыре 32-битных регистра, сдвигает их, объединяя с неполным словом, и захватывая выпавшие биты, затем сохраняет четыре 32-битных регистра и т. д. На многих процессорах ARM производительность даже в невыровненном случае может быть в два раза выше, чем при использовании байтов. - person supercat; 18.05.2016
comment
@R..: Например, на ARM7-TDMI, не считая накладных расходов на цикл, копирование каждой группы из четырех слов с кодом коррекции выравнивания заняло бы 20 циклов. Без коррекции выравнивания это заняло бы 12. Копирование байтов или слов по отдельности заняло бы 5 циклов каждый. Нет необходимости в невыровненном доступе (который ARM7-TDMI не поддерживает) в любом случае. - person supercat; 18.05.2016

arrow_upward
6
arrow_downward

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

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

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

memmove вообще не зависит от того, как растет стек — он просто копирует одну область памяти в другую — точно так же, как memcpy, за исключением того, что он обрабатывает перекрывающиеся области, а memcpy — нет.

РЕДАКТИРОВАТЬ: На самом деле, подумав об этом еще немного... Работа со спины может работать, если вы идете из правильного "источника" (так сказать), в зависимости от самого движения (например, является ли источник ‹ местом назначения или нет?). Вы можете прочитать реализацию newlib здесь, и она также довольно хорошо прокомментирована.

person Matthew Iselin    schedule 26.08.2010

arrow_upward
2
arrow_downward

Зависит от компилятора. Хорошие компиляторы будут использовать хорошие оптимизации в зависимости от набора инструкций целевого процессора и ширины шины.

person jacknad    schedule 26.08.2010
comment
я считаю, что это должно быть в комментарии, а не в отдельном ответе - person YeenFei; 26.08.2010