34

私のシステムのmanページから：

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

説明
memmove() 関数は、文字列 src から文字列 dst に len バイトをコピーします。
2 つの文字列が重複する場合があります。コピーは常に非破壊的な方法で行われ
ます。

C99 標準から:

6.5.8.5 2 つのポインターを比較すると、結果は、指しているオブジェクトのアドレス空間内の相対位置によって異なります。オブジェクト型または不完全型への 2 つのポインターが両方とも同じオブジェクトを指している場合、または両方が同じ配列オブジェクトの最後の要素の 1 つ後ろを指している場合、それらは等しいと見なされます。指しているオブジェクトが同じ集合体オブジェクトのメンバーである場合、後で宣言された構造体メンバーへのポインターは、構造体で以前に宣言されたメンバーへのポインターよりも大きく、添字値が大きい配列要素へのポインターは、同じ配列の要素へのポインターよりも大きくなります。より低い添字値で。同じ共用体オブジェクトのメンバーへのすべてのポインターは等しいと比較されます。式の場合P が配列オブジェクトの要素を指し、式 Q が同じ配列オブジェクトの最後の要素を指している場合、ポインター式はQ+1 より大きいと比較 されますP。それ以外の場合、動作は undefinedです。

強調は私のものです。

厳密なエイリアシングの問題を軽減するために、引数dstとsrcをポインターに変換できますがchar、同じブロック内を指している場合に正しい順序でコピーを行うために、異なるブロック内を指している可能性のある 2 つのポインターを比較することは可能ですか? ?

明らかな解決策は ですが、 と が異なるブロックを指しているif (src < dst)場合は未定義です。「未定義」とは、条件が 0 または 1 を返すと想定してはならないことを意味します (これは、標準の語彙では「未指定」と呼ばれていました)。srcdst

代替手段は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 で効率的に実装できないことが本当である場合、標準が未定義の動作で行き過ぎていることの証明として、この例を引き続き使用したいと思います。

4

5 に答える 5

23

おっしゃるとおりmemmove、標準 C で効率的に実装することは不可能です。

領域が重複しているかどうかをテストする真に移植可能な唯一の方法は、次のようなものだと思います。

for (size_t l = 0; l < len; ++l) {
    if (src + l == dst) || (src + l == dst + len - 1) {
      // 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、同じ型の任意の 2 つのポインターに対して機能するように定義されている のポインターの特殊化が導入されました。理論的には より遅いかもしれませんが、<セグメント化されていないアーキテクチャでは明らかにそうではありません。

Cにはそのようなものがないので、ある意味では、C++標準は、Cには十分に定義された動作がないというあなたの意見に同意しています。しかし、C++ はそれを必要とstd::mapします。std::map実装の知識がなくても実装(またはそれに類するもの) を実装するよりも、実装に関する知識がなくても実装 (またはそれに類するもの) を実装したいと思う可能性がはるかに高くなりますmemmove。

于 2010-10-26T12:18:52.867 に答える
7

2 つのメモリ領域が有効でオーバーラップするためには、6.5.8.5 で定義された状況のいずれかである必要があると思います。つまり、配列、共用体、構造体などの 2 つの領域です。

他の状況が定義されていない理由は、2 つの異なるオブジェクトが、同じ種類のポインターを持つ同じ種類のメモリにさえない可能性があるためです。PC アーキテクチャでは、通常、アドレスは仮想メモリへの 32 ビット アドレスにすぎませんが、C ではあらゆる種類の奇妙なアーキテクチャがサポートされており、メモリはそのようなものではありません。

C が未定義のままにしておく理由は、状況を定義する必要がない場合に、コンパイラの作成者に余裕を与えるためです。6.5.8.5 の読み方は、C がサポートしたいアーキテクチャーを注意深く説明しているパラグラフであり、ポインターの比較は同じオブジェクト内にない限り意味がありません。

また、memmove と memcpy がコンパイラによって提供される理由は、特殊な命令を使用してターゲット CPU 用に調整されたアセンブリで記述される場合があるためです。これらは、C で同じ効率で実装できるようには意図されていません。

于 2010-10-26T11:59:35.200 に答える
2

まず第一に、C 標準はこのような細部に問題があることで有名です。問題の一部は、C が複数のプラットフォームで使用されており、標準が現在および将来のすべてのプラットフォームをカバーできるように抽象化しようとしているためです (これまでに見たことのない複雑なメモリ レイアウトを使用する可能性があります)。コンパイラの作成者がターゲット プラットフォームに対して「正しいことを行う」ために、多くの未定義または実装固有の動作があります。すべてのプラットフォームの詳細を含めることは非現実的です (そして常に時代遅れです)。代わりに、C 標準では、これらの場合に何が起こるかを文書化するのはコンパイラの作成者に任されています。「指定されていない」動作は、C 標準が何が起こるかを指定していないことを意味するだけであり、必ずしも結果が予測できないことを意味するわけではありません。

2 つのポインタが同じブロック、メモリ セグメント、またはアドレス空間を指しているかどうかは、そのプラットフォームのメモリがどのように配置されているかによって決まるため、仕様ではその判定方法を定義していません。これは、コンパイラがこの決定を行う方法を知っていることを前提としています。引用した仕様の一部は、ポインター比較の結果はポインターの「アドレス空間内の相対位置」に依存すると述べています。ここでは「アドレス空間」が単数形であることに注意してください。このセクションでは、同じアドレス空間にあるポインターのみを参照しています。つまり、直接比較可能なポインターです。ポインターが異なるアドレス空間にある場合、結果は C 標準では定義されておらず、代わりにターゲット プラットフォームの要件によって定義されます。

の場合memmove、実装者は通常、アドレスが直接比較可能かどうかを最初に判断します。そうでない場合、関数の残りの部分はプラットフォーム固有です。ほとんどの場合、領域がオーバーラップせず、関数がmemcpy. アドレスが直接比較可能な場合は、最初のバイトから開始して前方に進むか、最後のバイトから後方に進む単純なバイト コピー プロセスです (何も破壊せずにデータを安全にコピーする方)。

全体として、C 標準では、ターゲット プラットフォームで機能する単純なルールを記述できない多くの部分が意図的に指定されていません。ただし、標準的な作成者は、一部のものが定義されていない理由を説明し、「アーキテクチャ依存」などのより説明的な用語を使用することで、より良い仕事をすることができたはずです。

于 2010-10-26T13:13:49.593 に答える
1

ここに別のアイデアがありますが、それが正しいかどうかはわかりません。O(len)スティーブの答えでループを回避するには、キャストから実装を使用して#elsean の句に入れることができます。toのキャストが、オフセットがポインターで有効な場合はいつでも整数オフセットを追加して変換される場合、これにより、ポインターの比較が明確になります。#ifdef UINTPTR_MAXuintptr_tunsigned char *uintptr_t

この可換性が標準で定義されているかどうかはわかりませんが、ポインターの下位ビットのみが実際の数値アドレスであり、上位ビットがある種のブラックボックスであっても機能するため、意味があります。

于 2010-10-26T15:45:53.280 に答える
0

標準 C で memmove を効率的に実装できないことが本当である場合、標準が未定義の動作で行き過ぎていることの証明として、この例を引き続き使用したいと思います。

しかし、それは証拠ではありません。任意のマシン アーキテクチャで任意の 2 つのポインタを比較できることを保証する方法はまったくありません。このようなポインター比較の動作は、C 標準やコンパイラーによって規定することはできません。セグメントが RAM でどのように構成されているかによって異なる結果を生成する可能性がある、または異なるセグメントへのポインターが比較されるときに例外をスローすることを選択する可能性がある、セグメント化されたアーキテクチャを備えたマシンを想像できます。これが、動作が「未定義」である理由です。まったく同じマシンでまったく同じプログラムを実行しても、実行ごとに異なる結果が生じる可能性があります。

2 つのポインターの関係を使用して最初から最後にコピーするか、最後から最初にコピーするかを選択する memmove() のよくある「解決策」は、すべてのメモリ ブロックが同じアドレス空間から割り当てられている場合にのみ機能します。幸いなことに、16 ビット x86 コードの時代にはありませんでしたが、これは通常のケースです。

于 2010-10-26T13:54:28.553 に答える