memmove implementation in C

Question

Hi,

Can some one help me to understand how memmove is implemented in C. I have only one special condition right ?

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

copy from the back

Also does it depend on the way stack grows ?

Answer 1

Does it really copy a byte at a time on modern processors?
I would have thought there was a block memory operation in the memory controller.

Answer 2

Depends on the compiler. Good compilers will use good optimizations dependent on the target processor instruction set and bus width.

Answer 3

memmove can be turned into a memcpy if the two memory regions don't overlap. Obviously memcpy is extremely optimised on most systems (one of the ones I use makes use of almost every trick in the book from unrolled loops to SSE operations where supported for maximum throughput).

If the two memory regions do overlap, for all intents and purposes the region to be copied is moved into a temporary buffer and the temporary buffer is copied (all with memcpy, most likely) back on top of the original buffer. You can't work from the start or work from the back with an overlapping region, because you'll always end up with at least some data being corrupted in the process.

That being said, it's been a long time since I've looked at libc code, so there may be an optimisation for memmove and overlapping regions that I haven't thought of yet.

memmove doesn't depend on the way the stack grows at all - it merely copies one region of memory to another location - exactly like memcpy, except that it handles overlapping regions and memcpy doesn't.

EDIT: Actually, thinking about it some more... Working from the back can work if you go from the right "source" (so to speak), depending on the move itself (eg, is source < dest or not?). You can read newlib's implementation here, and tt's fairly well-commented too.

Answer 4

Mathematically, you don't have to worry about whether they overlap at all. If src is less than dst, just copy from the end. If src is greater than dst, just copy from the beginning.

If src and dst are equal, just exit straight away.

That's because your cases are one of:

1 <-----s-----> <-----d----->  start at end of s
2 <-----s--<==>--d----->       start at end of s
3 <-----sd----->               do nothing
4 <-----d--<==>--s----->       start at beginning of s
5 <-----d-----> <-----s----->  start at beginning of s

Even if there's no overlap, that will still work fine, and simplify your conditions.

If you have a more efficient way to copy forwards than backwards then, yes, you should check for overlap to ensure you're using the more efficient method if possible. In other words, change option 1 above to copy from the beginning.

However, in that case, you may also find that it's faster to copy twice, once from s to some temporary memory then from that temporary memory to d but that depends entirely on your respective algorithms.