Saturday, June 11, 2011

Achieivng memcpy and memmove in single function

Somebody asked me is it possible to simulate memcpy and memmove in a single function. Initially I did not get it. I thought for a while and finally came up with the following solution. This is quite crude code however satisfies the functionality. glibc expects that for memcpy, pointers should not overlap even after copying. If they overlap, then memmove must be used.

As shown in figure there are three cases



Here:

s = source pointer
d = destination pointer
b = boundary
size = number of bytes to copy

1) d >= s+size
2) d < s
3) d < s+size

If d=s, we do not do anything. simply return

The cases 1 and 2 are trivial. In the sense, plain copying does not corrupt destination 'd' buffer. However in case '2', source 's' data will be modified.
The problem is with case 3. When we do plain copy, the source data buffer at the tail gets corrupted and destination 'd' will not have replica of source 's'. We can avoid this by copying from the last i.e. copy from 's+size' to 'd+size' and move towards 's' and 'd'.

Here is the program. The example may be trivial however I hope this works.

#include<stdio.h>

void my_memcpy(void* src, void* dst, size_t bytes);

void my_memcpy(void* src, void* dst, size_t bytes)
{
unsigned char* s = (unsigned char*)src;
unsigned char* d = (unsigned char*)dst;

if(s == d)
{
//same
return;
}

size_t k = 0;
if(s+bytes > d)
{
//Overlapping
k = bytes;
while(k > 0)
{
d[k-1] = s[k-1];
k--;
}
return;
}

//Other cases
while(k < bytes)
{
d[k] = s[k];
k++;
}
}

int main()
{
int i[10] = {0x1234, 0x2345, 0x3456, 0x4567};
my_memcpy(i, &i[2], sizeof(int) * 4);
int j = 0;
for(;j<6;j++)
printf("%x\n", i[j]);
}


When I browsed through glibc code, it used page copy technique in case of memcpy. It tries to get page boundary and copies data in pages. This technique is quite faster for huge data. For data which are not page aligned, it does plain copy. For i386, seems like it uses inline assembly.