copy bytes without memcpy()

Question

It's a home work. I want to implement memcpy(). I was told memory area must not overlap. Actually I don't understand what that means, because this code works fine, but there is a possibility of memory overlap. How to prevent it?

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;
}

Answer 1

When source and destination memory blocks overlap, and if your loop copies one element after the other starting from index 0, it works for dest < source, but not for dest > source (because you overwrite elements before having copied them) and vice versa.

Your code starts copying from index 0, so you can simply test which situations work and which not. See the following test code; It shows how moving a test string forward fails, whereas moving the string backwards works fine. Further, it shows how moving the test string forward works fine when copying from backward:

#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);
}

Output:

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!

So one could write one function, which decides whether to start copying from index 0 or from index n depending on whether the caller wants to copy forward or backward. The tricky thing is to find out whether the caller will copy forward or backward, since a pointer arithmetic on src and dest like if (src < dest) copy_from_backward(...) is actually not permitted in every case (cf. the standard, e.g. this draft):

6.5.9 Equality operators

When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object or incomplete types both point to the same object, or both point one past the last element of the same array object, they compare equal. If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values. All pointers to members of the same union object compare equal. If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined.

Though I've never been in a situation where src < dest did not give me the desired results, comparing two pointers this way is actually undefined behaviour if they do not belong to the same array.

Hence, if you ask "how to prevent it?", I think that the only correct answer must be: "It's subject to the caller, because function mem_copy cannot decide whether it may compare src and dest correctly."

Answer 2

Actually I don't understand what doest that mean [for memory to overlap]

Consider this example:

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

From the program's point of view, the range of addresses from src to src+n must not overlap the range from dest to dest+n.

if there is possibility of memory overlap, how to prevent it?

You can make your algorithm work with or without an overlap by deciding to copy overlapping regions from the back if src has numerically lower address than dest.

Note: Since you are doing memcpy, not strcpy, forcing null termination with newdest[i]='\0' is incorrect, and needs to be removed.

Answer 3

There are some issues in your re-implementation of memcpy():

• The size argument n should have type size_t. The index variable i should have the same type as the size argument.

• It is OK to pass a count of 0. Indeed your code would behave correctly in this case, remove the test from the assert().

• Avoid casting away the const qualifier unless absolutely necessary.

• Do not tack a '\0' at the end of the destination, it is incorrect and will cause buffer overruns.

Here is a corrected version:

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;
}

Regarding the potential overlap between the source area and the destination area, your code's behavior will be surprising if the destination pointer is greater than the source, but within the source area:

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

Will output:

before: 12345
after: 111111

There is no completely portable way to test for such overlap, but it is quite easy on non exotic architectures at some small cost in execution time and code size. The semantics of memcpy() is that no such test is assumed to be performed by the library, so the programmer should only call this function if there is no possibility for source and destination areas to overlap. When in doubt, use memmove() that handles overlapping areas correctly.

If you wish to add an assert for this, here is a mostly portable one:

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

Here is a simple rewrite of memmove(), albeit not completely portable:

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;
}