不使用memcpy()复制字节

Question

这是一个编程作业，我想要实现memcpy()函数。我被告知内存区域不能重叠。实际上，我不明白这是什么意思，因为代码可以正常工作，但存在内存重叠的可能性。如何避免重叠？

void *mem_copy(void *dest, const void *src, unsigned int n) {
    assert((src != NULL) && (n > 0));  
    int i = 0;
    char *newsrc = (char*)src;
    char *newdest = (char*)dest;
    while (i < n) {
        newdest[i] = newsrc[i];
        i++;
    }
    newdest[i]='\0';
    return newdest;
}

- surjit

---

删除 newdest[i]='\0';。 - BLUEPIXY

“无重叠”意味着范围[dest..dest+n-1]中的任何地址都与范围[src..src+n-1]中的任何地址不同。要以可移植的方式确定这一点实际上相当困难 - 正式地说，您只能比较单个数组中的地址，但通常当地址范围不重叠时，这些区域不是同一数组的一部分。 - Jonathan Leffler

您可以通过指针算术运算来检查并防止重叠。 - Sebastian Walla

“assert(n > 0)”是错误的。允许复制0个字节。 - melpomene

memcpy不是一个字符串函数。它不关心'\0'。 - melpomene

Answer 1

当源内存块和目的内存块重叠，并且如果您的循环从索引0开始逐个复制元素，则对于dest < source，它可以工作，但对于dest > source则不行(因为您在复制之前覆盖了元素)反之亦然。

您的代码从索引0开始复制，因此您可轻松测试哪些情况可行和哪些情况不可行。请参阅以下测试代码；它展示了如何向前移动测试字符串失败，而向后移动字符串却正常工作。此外，它还展示了从后向前复制时向前移动测试字符串是如何正常工作的：

#include <stdio.h>
#include <string.h>

void *mem_copy(void *dest, const void *src, size_t n) {
    size_t i = 0;
    char* newsrc = (char*)src;
    char* newdest = (char*)dest;
    while(i < n) {
        newdest[i] = newsrc[i];
        i++;
    }
    return newdest;
}

void *mem_copy_from_backward(void *dest, const void *src, size_t n) {
    size_t i;
    char* newsrc = (char*)src;
    char* newdest = (char*)dest;
    for (i = n; i-- > 0;) {
        newdest[i] = newsrc[i];
    }
    return newdest;
}

int main() {

    const char* testcontent = "Hello world!";
    char teststr[100] = "";

    printf("move teststring two places forward:\n");
    strcpy(teststr, testcontent);
    size_t length = strlen(teststr);
    printf("teststr before mem_copy: %s\n", teststr);
    mem_copy(teststr+2, teststr, length+1);
    printf("teststr after mem_copy: %s\n", teststr);

    printf("\nmove teststring two places backward:\n");
    strcpy(teststr, testcontent);
    length = strlen(teststr);
    printf("teststr before mem_copy: %s\n", teststr);
    mem_copy(teststr, teststr+2, length+1);
    printf("teststr after mem_copy: %s\n", teststr);

    printf("move teststring two places forward using copy_from_backward:\n");
    strcpy(teststr, testcontent);
    length = strlen(teststr);
    printf("teststr before mem_copy: %s\n", teststr);
    mem_copy_from_backward(teststr+2, teststr, length+1);
    printf("teststr after mem_copy: %s\n", teststr);
}

输出：

move teststring two places forward:
teststr before mem_copy: Hello world!
teststr after mem_copy: HeHeHeHeHeHeHeH

move teststring two places backward:
teststr before mem_copy: Hello world!
teststr after mem_copy: llo world!

move teststring two places forward using copy_from_backward:
teststr before mem_copy: Hello world!
teststr after mem_copy: HeHello world!

因此，可以编写一个函数，根据调用者是要向前复制还是向后复制，决定从索引0或索引n开始复制。棘手的事情是找出调用者是否要向前或向后复制，因为对src和dest进行指针算术运算，例如if (src < dest) copy_from_backward(...)在每种情况下实际上并不被允许（参见标准，例如这个草案）：

6.5.9 相等运算符

当比较两个指针时，结果取决于所指对象在地址空间中的相对位置。如果两个指向对象或不完整类型的指针都指向同一对象，或都指向同一数组对象的最后一个元素之后，它们相等。如果所指对象是同一聚合对象的成员，则以后声明的结构成员的指针比先前声明的成员的指针更大，并且具有较大下标值的数组元素的指针比具有较小下标值的同一数组的元素的指针更大。所有指向同一联合对象的成员的指针都相等。如果表达式P指向数组对象的元素，并且表达式Q指向同一数组对象的最后一个元素，则指针表达式Q+1比P大。 在所有其他情况下，行为是未定义的。

虽然我从来没有遇到过src < dest不能给我想要的结果的情况，但是这种方式比较两个指针实际上是未定义行为，如果它们不属于同一数组。

因此，如果您问“如何防止它？”，我认为唯一正确的答案必须是：“这取决于调用者，因为函数mem_copy无法确定是否可以正确比较src和dest。”

- Stephan Lechner

---

当我使用--track-origins=yes标志时，出现了Conditional jump or move depends on uninitialised value(s)错误。我得到的信息是Uninitialised value was created by a stack allocation。 - surjit

@surjit：没错，在第一次执行mem_copy(teststr+2, teststr, length+1);之后，teststr偏移量为length处由strcpy()设置的空终止符被覆盖了，因此在未初始化的区域之前，该数组不再有空终止符。通过初始化数组解决这个问题：char teststr[100] = "";。 - chqrlie

Answer 2

实际上我不明白“内存重叠”是什么意思。

考虑以下示例：

char data[100];
memcpy(&data[5], &data[0], 95);

从程序的角度来看，从 src 到 src+n 的地址范围不能与从 dest 到 dest+n 的范围重叠。

如果存在内存重叠的可能性，如何避免它？

如果 src 的地址数值小于 dest，则可以通过决定从后面复制重叠区域使算法能够处理有或没有重叠的情况。 注意：由于使用的是 memcpy 而不是 strcpy，因此强制使用 newdest[i]='\0' 进行空终止是不正确的，需要将其删除。

- Sergey Kalinichenko

---

@surjit 请看一下这个问答，它讨论了memmove，这是一个允许区域重叠的memcpy版本。 - Sergey Kalinichenko

如何向后复制？ - surjit

@surjit 从src + n-1开始，到src，包括这两个位置，使用--而不是++。我在评论中提供的Q&A使用此方法，在进入循环之前设置operation、current和end。 - Sergey Kalinichenko

当我使用 --track-origins=yes 标志时，我遇到了错误 Conditional jump or move depends on uninitialised value(s)，并且得到了 Uninitialised value was created by a stack allocation 的提示。 - surjit

@surjit：你会收到这个警告，是因为data[]未初始化，因此memcpy()读取了未初始化的字节，而你程序中其他地方的一些代码可能依赖于这些字节值... - chqrlie

Answer 3

你的重新实现memcpy()存在一些问题：

• 大小参数n应该具有类型size_t。索引变量i应该与大小参数具有相同的类型。

• 传递计数为0是可以的。事实上，在这种情况下，您的代码将正确运行，请从assert()中删除测试。

• 除非绝对必要，否则避免强制转换const限定符。

• 不要在目标末尾添加'\0'，这是不正确的，并且会导致缓冲区溢出。

以下是已更正的版本：

void *mem_copy(void *dest, const void *src, size_t n) {
    assert(n == 0 || (src != NULL && dest != NULL));  
    size_t i = 0;
    const char *newsrc = (const char *)src;
    char *newdest = (char *)dest;
    while (i < n) {
        newdest[i] = newsrc[i];
        i++;
    }
    return dest;
}

关于源区域和目标区域之间的潜在重叠，如果目标指针大于源指针但在源区域内，您的代码行为将会令人惊讶：

char buffer[10] = "12345";
printf("before: %s\n", buffer);
mem_copy(buffer + 1, buffer, 5);
printf("after: %s\n", buffer);

将输出：

before: 12345
after: 111111

没有完全可移植的方法来测试这种重叠，但在非异构架构上，以一些执行时间和代码大小的小成本很容易实现。 memcpy() 的语义是库不会假设进行此类测试，因此程序员只有在源区域和目标区域不存在重叠的可能性时才应调用此函数。 如果有疑问，请使用正确处理重叠区域的memmove()。

如果您希望为此添加一个assert，则可以使用以下大多数可移植的方法：

assert(n == 0 || newdest + n <= newsrc || newdest >= newsrc + n);

这是一个简单的memmove()重写，虽然不完全可移植:

void *mem_move(void *dest, const void *src, size_t n) {
    assert(n == 0 || (src != NULL && dest != NULL));  
    const char *newsrc = (const char *)src;
    char *newdest = (char *)dest;
    if (newdest <= newsrc || newdest >= newsrc + n) {
        /* Copying forward */
        for (size_t i = 0; i < n; i++) {
            newdest[i] = newsrc[i];
        }
    } else {
        /* Copying backwards */
        for (size_t i = n; i-- > 0;) {
            newdest[i] = newsrc[i];
        }
    }
    return dest;
}

- chqrlie