Implementing my own memcpy

[Rajan]

Hi,
I am trying to simulate a memcpy like this
void* mem_cpy(void* dest, void* src, int bytes)
{
dest = malloc(bytes);
}
Now if I want to copy the bytes from src to dest, how do I copy these
bytes.
I am stuck here.

 

[Netocrat]

Hi,
I am trying to simulate a memcpy like this void* mem_cpy(void* dest, void*
src, int bytes) {
dest = malloc(bytes);
}
Now if I want to copy the bytes from src to dest, how do I copy these
bytes.
I am stuck here.

Why can't you use memcpy itself? I'll assume you have a reason that
isn't "it's a homework assignment".

Are you trying to achieve the exact same behaviour as memcpy? If so,
then don't allocate memory - memcpy requires that the memory is already
allocated. The second parameter needs to be qualified with const. Also
the type of the third parameter is size_t not int - this requires that
you include stddef.h. Even if it were declared as int it should be
unsigned.

Here is an implementation:

#include <stddef.h>

void *mem_cpy(void *dest, const void *src, size_t bytes)
{
unsigned char *srcmax = dest + bytes;

while (src < srcmax)
*(unsigned char *)dest++ = *(unsigned char *)src++;
return dest;
}

 

[Ben Pfaff]

I am trying to simulate a memcpy like this
void* mem_cpy(void* dest, void* src, int bytes)
{
dest = malloc(bytes);
}
Now if I want to copy the bytes from src to dest, how do I copy these
bytes.

This does not make sense. If you are going to copy bytes from
src to dest, then replacing dest by something else (such as the
return value of malloc()) is not going to help, because it means
that you won't be able to refer to the destination buffer any
longer.

Have you tried reading a C tutorial?

 

[Rajan]

Hi Netocrat ,
With your code fragment, I find that you are using unsigned char* , but
I may have to copy a structure.
We certainly cannot do *dest++ = *src++ ; if they are void pointers.
So how do we deal with this?

 

[Ben Pfaff]

With your code fragment, I find that you are using unsigned char* , but
I may have to copy a structure.

Any object may be copied as an array of characters.

 

[Netocrat]

Hi Netocrat ,
With your code fragment, I find that you are using unsigned char* , but I
may have to copy a structure.
We certainly cannot do *dest++ = *src++ ; if they are void pointers. So
how do we deal with this?

I believe that there is no portable, generic way to copy a structure - you
need to write a specific routine that copies each element.

A non-portable way that will probably work would be to call the mem_cpy
function with the addresses of the destination and source structures as
the first and second parameters ie &your_struct_variable1 and
&your_struct_variable2 and with the third parameter as sizeof(struct
your_struct). I'll probably get jumped on for suggesting that though...

Regarding your comment about dest and src being void pointers:

In the code, unsigned char * is used as a cast. It doesn't change the
fact that the original pointers are void *, it just instructs the compiler
to treat them as unsigned char pointers. So you are right that *dest++ =
*src++ is invalid, because you can't dereference a pointer to void. But
typecasting them to unsigned char pointers and then dereferencing them is
guaranteed to always be valid. In this way unsigned char pointers are
unique. Interpret it like this:
1) we are given two pointers which can point to anything
2) we treat the pointers as though they each point to a single byte
(unsigned char can be interpreted as being a single byte)
3) we copy the data from the byte that the source pointer points to into
to the byte that the destination pointer points to
4) we move each pointer on to the next byte
5) we repeat steps 3 and 4 'bytes' times.

 

[Clark S. Cox III]

I believe that there is no portable, generic way to copy a structure

Of course there is; in fact, there are several:

Assuming a and b are of the same complete type, any of the following
will copy the contents of a into b:

#include <stdlib.h>
#include <string.h>

/*1*/ b = a;
/*2*/ memcpy(&b, &a, sizeof b);
/*3*/ memmove(&b, &a, sizeof b);
/*4*/ const unsigned char *src = (const unsigned char*)&a;
unsigned char *dst = (unsigned char*)&b;
for(size_t i=0; i<sizeof b; ++i)
{
dst = src;
}

 

[Netocrat]

Of course there is; in fact, there are several:

Assuming a and b are of the same complete type, any of the following will
copy the contents of a into b:

I'm glad to be corrected. I know of those approaches but with all the
buzzwords - unbounded this and unspecified that - going around in this
group and without a copy of the standard - or any other authoritative
source - to refer to I'm finding it hard to know what's "conforming" - to
use another buzzword.

 

[Stan Milam]

Hi,
I am trying to simulate a memcpy like this
void* mem_cpy(void* dest, void* src, int bytes)
{
dest = malloc(bytes);
}
Now if I want to copy the bytes from src to dest, how do I copy these
bytes.
I am stuck here.

What I think you are trying to do here is duplicate some object in
memory using dynamically allocated memory to store the duplicate. If
that is the case try this:

/**********************************************************************/
/* File Id: dupobj.c. */
/* Author: Stan Milam. */
/* Date Written: 28-Aug-1999. */
/* Description: */
/* Implement a function to duplicate an object in memory. */
/* */
/* (c) Copyright 2005 by Stan Milam. */
/* All rights reserved. */
/* */
/**********************************************************************/

#include <errno.h>
#include <stdlib.h>
#include <string.h>

/**********************************************************************/
/* Name: */
/* dupobj() - Duplicate an lvalue with allocated memory. */
/* */
/* Synopsis: */
/* #include "strtools.h." */
/* void *dupobj( void *obj, size_t objsize ); */
/* */
/* Description: */
/* Use the calloc() and memcpy() functions to allocate memory */
/* large enough to hold an object in memory, then use memcpy() */
/* to copy the contents of the object to the allocated memory. */
/* */
/* Arguments: */
/* void *obj */
/* size_t objsize - The size of the object in memory. */
/* */
/* Return Value: */
/* The address of the duplicated object. NULL when a memory */
/* allocation error occurs, or the *obj address is NULL. When */
/* the *obj address is NULL the global errno variable is set */
/* to EINVAL. */
/* */
/**********************************************************************/

void *
dupobj( void *obj, size_t objsize )
{
void *rv = NULL;

if ( obj == NULL || objsize == 0 )
errno = EINVAL;
else {
if ( ( rv = calloc( 1, objsize ) ) != NULL )
memcpy( rv, obj, objsize );
}
return rv;
}

 

[CBFalconer]

Hi Netocrat ,
With your code fragment, I find that you are using unsigned char* , but
I may have to copy a structure.
We certainly cannot do *dest++ = *src++ ; if they are void pointers.
So how do we deal with this?

Always include adequate quotation from previous articles, so that
your message stands by itself. There is no reason to assume any
previous material is available to the reader.

One of my sigs reads as follows - heed it if you must use the foul
google interface. Better, get yourself a real newsreader.

"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

The point about memcpy is that it copies memory areas, measured in
bytes, with no regard for the types involved. I gather you wish
the same thing, but with automatic creation of the destination. In
this case you need a different signature, such as:

void *dupmem(void *src, size_t sz);

The void * type can point at arbitrary things, and a size_t can
specify a size on any machine. But to use void* you have to
convert to other types, thus:

void *dupmem(void *src, size_t sz)
{
unsigned char *sp = src;
unsigned char *dst;

if (dst = malloc(sz)) /* memory is available */
while (sz--) *dst++ = *sp++; /* copy away */
return dst; /* will be NULL for failure */
} /* dupmem, untested */

Note how src is typed into sp, without any casts. Similarly the
reverse typing for the return value of dupmem. The usage will be,
for p some type of pointer:

if (p = dupmem(whatever, howbig)) {
/* success, carry on */
}
else {
/* abject failure, panic */
}

 

[Robert W Hand]

)

#include <stddef.h>

void *mem_cpy(void *dest, const void *src, size_t bytes)
{
unsigned char *srcmax = dest + bytes;

while (src < srcmax)

I don't understand this line. You are comparing one array src to
another srcmax. Perhaps I missed something, but I do not believe that
they are looking into the same array. Did you mean to define srcmax
differently?

unsigned char* srcmax = src + bytes;

 

[Nils Weller]

[...]
void *
dupobj( void *obj, size_t objsize )

Why not ``const void *obj''?

{
void *rv = NULL;

if ( obj == NULL || objsize == 0 )
errno = EINVAL;

EINVAL is not a Standard C macro (the UNIX and POSIX standards do define
it, however.) In addition, I would argue that it is the caller's
responsibility to pass valid arguments. Have you noticed that even in
Unix, library-only functions tend not to set EINVAL much, and certainly
not for invalid pointer arguments? This is because such a requirement
would needlessly slow down and bloat correctly written code, i.e. code
that always passes valid arguments. It is usually functions invoking
system calls that set errno to EINVAL because the operating system
kernel *has to* check all arguments for correctness, so as to avoid
accidental or malicious system corruption.

I will also point out that your check is incomplete anyway because
``obj'' may contain an invalid address that isn't NULL; Which, for the
purpose of setting EINVAL in Unix, is an unmapped address.

else {
if ( ( rv = calloc( 1, objsize ) ) != NULL )

This will likely execute slower than necessary, since calloc() is
conceptually a malloc() + memset(); A plain malloc() will suffice
because you immediately overwrite the memory anyway.

 

[Netocrat]

I don't understand this line. You are comparing one array src to another
srcmax. Perhaps I missed something, but I do not believe that they are
looking into the same array. Did you mean to define srcmax differently?

unsigned char* srcmax = src + bytes;

Yes - typo, I don't know how that snuck in there - it's obvious from the
naming that it's wrong.

Cheers.

 

[Chris Torek]

void *mem_cpy(void *dest, const void *src, size_t bytes)
{
unsigned char *srcmax = dest + bytes;

while (src < srcmax)
*(unsigned char *)dest++ = *(unsigned char *)src++;
return dest;
}

This is flawed for three reasons:

- As someone else pointed out, "srcmax" is computed from "dest"
but is used for comparison with "src".

- The "dest++" and "src++" operations are invalid because dest
and src have type "void *", and thus need to increment by
sizeof(void), as it were. (There are some non-C compilers,
such as gcc, that define sizeof(void)==1 just to make this
work anyway. There are some other non-C compilers that fail
to catch the error -- a diagnostic is required in ANSI/ISO
C, either C89 or C99 -- and treat sizeof(void) as 0, and
thus produce an infinite loop!)

- Finally, the return value (dest) would be modified from the
original input value: you would have to retract it by "bytes"
bytes first.

The easiest fix for all of these is to use auxiliary variables.
I prefer to leave the input parameters unmodified, and create
auxiliaries of type "unsigned char *":

void *like_memcpy(void *restrict dst0, const void *restrict src0,
size_t n) {
unsigned char *restrict dst = dst0;
unsigned char *restrict src = src0;

if (n)
do
*dst++ = *src++;
while (--n != 0);
return dst0;
}

(you can also write the loop as "while (n--) *dst++ = *src++" but I
find the above easier to read and think about).

This is strictly conforming C code because it is always allowed to
examine or copy objects' representations one "C byte" (unsigned
char) at a time.

 

[Kevin Bagust]

Are you trying to achieve the exact same behaviour as memcpy? If so,
then don't allocate memory - memcpy requires that the memory is already
allocated. The second parameter needs to be qualified with const. Also
the type of the third parameter is size_t not int - this requires that
you include stddef.h. Even if it were declared as int it should be
unsigned.

Here is an implementation:

#include <stddef.h>

void *mem_cpy(void *dest, const void *src, size_t bytes)
{
unsigned char *srcmax = dest + bytes;

while (src < srcmax)
*(unsigned char *)dest++ = *(unsigned char *)src++;
return dest;
}

You cannot perform pointer arithmetic on void pointers, you need to
convert them to pointers to another type before you perform the
addition. memcpy should return the value of dest that is passed into the
function. So the code should be something like this:

#include <stddef.h>

void *mem_cpy( void *dest, const void *src, size_t bytes )
{
unsigned char *destPtr = dest;
unsigned char const *srcPtr = src;
unsigned char const *srcEnd = srcPtr + bytes;

while ( srcPtr < srcEnd ) {
*destPtr++ = *srcPtr++;
}
return dest;
}

Kevin.

 

[Netocrat]

This is flawed for three reasons:

- As someone else pointed out, "srcmax" is computed from "dest"
but is used for comparison with "src".

- The "dest++" and "src++" operations are invalid because dest
and src have type "void *", and thus need to increment by
sizeof(void), as it were. (There are some non-C compilers, such as
gcc, that define sizeof(void)==1 just to make this work anyway.
There are some other non-C compilers that fail to catch the error --
a diagnostic is required in ANSI/ISO C, either C89 or C99 -- and
treat sizeof(void) as 0, and thus produce an infinite loop!)

Yes thoughts about what type the increment operator was operating on did
pass through my mind as I was writing it. When it worked (I use gcc) I
assumed that it was because the cast to unsigned char * had informed the
compiler how to properly apply pointer arithmetic - that had I left it
uncast as void * the increment operator would not have worked at all. Now
that I reconsider that assumption I can see that it's flawed because had
the cast been taken into account the result would no longer have been a
modifiable lvalue and the increment could not have been applied.

And indeed checking this shows that gcc still doesn't complain about
incrementing a void pointer.

- Finally, the return value (dest) would be modified from the
original input value: you would have to retract it by "bytes" bytes
first.

Obviously. A silly error.

The easiest fix for all of these is to use auxiliary variables. I prefer
to leave the input parameters unmodified, and create auxiliaries of type
"unsigned char *":

I've got into the habit of trying to minimise variable usage and required
calculations (sometimes orthogonal aims). That's the main reason I didn't
use variables in this case. It's not so big a deal with an optimising
compiler because little details like that all get ironed out in the wash,
but in this forum you can't make any assumptions about whether or not code
will be compiled with optimisations.

Obviously my code won't function without change. Your suggestion works.
The other option is to maintain the cast and use indexing instead of
pointer arithmetic. I don't like that option though because it requires
more calculations to index for a non-optimising compiler.

Whilst decrementing n and testing it for loop end works fine, I prefer to
test against a maximum pointer and save the cost of the decrement
operation. I think it's also more readable.

void *like_memcpy(void *restrict dst0, const void *restrict src0,
size_t n) {
unsigned char *restrict dst = dst0;
unsigned char *restrict src = src0;

if (n)
do
*dst++ = *src++;
while (--n != 0);
return dst0;
}
(you can also write the loop as "while (n--) *dst++ = *src++" but I find
the above easier to read and think about).

I prefer the conciseness of the second, but I prefer even more testing
against a maximum pointer.

 

[Netocrat]

Netocrat wrote: [snip code]

You cannot perform pointer arithmetic on void pointers, you need to
convert them to pointers to another type before you perform the addition.
memcpy should return the value of dest that is passed into the function.
So the code should be something like this:

#include <stddef.h>

void *mem_cpy( void *dest, const void *src, size_t bytes ) {
unsigned char *destPtr = dest;
unsigned char const *srcPtr = src;
unsigned char const *srcEnd = srcPtr + bytes;

while ( srcPtr < srcEnd ) {
*destPtr++ = *srcPtr++;
}
return dest;
}

Great - that's just how I would have rewritten it to correct the bugs -
apart from naming conventions; and I may not have thought to qualify the
pointers with const but it is appropriate and good practice.

 

[Chris Torek]

I prefer the conciseness of the second, but I prefer even more testing
against a maximum pointer.

My thinking is perhaps colored by too many years of assembly coding
and instruction sets that include "decrement and branch if nonzero":

test r3
bz Laround
Lloop:
mov (r1)+,(r2)+
sobgtr r3,Lloop # cheating (but this is OK)
Laround:

and:

tst d1
bz Laround
addq #-1,d1 # dbcc/dbra uses -1 instead of 0
Lloop:
mov a1@+,a2@+
dbra d1,Lloop
# insert fixup code for 16-bit dbra instructions
...
Laround:

and so on. (The first loop is VAX assembly, and "cheating" is OK
because r1 and/or r2 should never cross from P0/P1 space to S space,
nor vice versa, so the maximum block size never exceeds 2 GB; the
second loop is 680x0 assembly and uses a special trick in the
original 68000, in which a one-instruction dbcc loop never re-fetches
the instructions over the bus, so that the loop runs about twice
as fast as any other version. You *have* to use the dbcc instructions,
no other loop construct does the trick! If you can force-fit any
repeated memory operation into a dbra, even if there is no reason
to decrement, it is worth it, on the 68000. Later CPUs had
instruction caches, making the trick obsolete, though.)

Modern CPUs have "branch on register not zero" but also may have
"branch on r1 not equal to r2". MIPS and SPARCv9 lack the latter,
so the counted loop is still better; but on SPARCv9 at least, you
really want to implement large block-copy operations using the
special cache-conserving streaming load operations, through the
floating point registers. (But that assembly code is far too
large to post off-topically to comp.lang.c )

 

[Netocrat]

My thinking is perhaps colored by too many years of assembly coding and
instruction sets that include "decrement and branch if nonzero":

Interesting where the differences lead us. I did some x86 assembly way
back - not much but enough to get the general idea. As for any other
architectures - I've used them but haven't coded their assembly.

So my thinking is based mainly on my own concepts of an 'abstract machine'
and the operations it would perform with my own idea of the abstract cost
of those operations.

In practice your thinking is likely to lead to code that is efficient on a
given set of architectures.

My approach will be more efficient on a machine in my head. Whether
that translates into efficiency on real machines depends on
a) the natural fit of my abstract machine to the real hardware
b) of the ability of the compiler to optimise my semantics for the real
hardware.
There is another dependency - optimising my semantics for the abstract
machine. But that's a step I deem it upon myself to take and prefer not
to rely on the compiler to provide. And that's the point where according
to my abstract concepts, the 'maximum pointer test' is cheaper than the
separate counter.

But it's only valid for my personal abstract machine. Another
programmer might have their own personal abstract machine with a
different cost weighting. And your cost calculations are valid for the
machines you know have that type of instruction.

In the end when we're talking about non-platform-specific C as on this
forum, apart from blazingly obvious inefficiencies, and representations
that can only be implemented by hardware in one particular way, things
like this are a matter of personal preference and style, would you not
agree?

[snip assembly and explanation]

Modern CPUs have "branch on register not zero" but also may have "branch
on r1 not equal to r2". MIPS and SPARCv9 lack the latter, so the
counted loop is still better; but on SPARCv9 at least, you really want
to implement large block-copy operations using the special
cache-conserving streaming load operations, through the floating point
registers. (But that assembly code is far too large to post
off-topically to comp.lang.c
)

From vague memory I know x86 has the jump on zero, jump on less than etc
but I have no recollection of whether this can be combined with a
decrement in a single instruction.

We're wandering somewhat off-topic here but these are things to consider
in the context of writing non-specific code and being aware that it must
ultimately run on an implementation which will have strengths and
weaknesses. How much should you abstract those implementation-specific
strengths and weaknesses into generic ones and code for those? Is there
any validity to the concept of a generic strength or weakness for an
abstract machine?

 

[Stan Milam]

[...]
void *
dupobj( void *obj, size_t objsize )

Why not ``const void *obj''?

{
void *rv = NULL;

if ( obj == NULL || objsize == 0 )
errno = EINVAL;

EINVAL is not a Standard C macro (the UNIX and POSIX standards do define
it, however.) In addition, I would argue that it is the caller's
responsibility to pass valid arguments. Have you noticed that even in
Unix, library-only functions tend not to set EINVAL much, and certainly
not for invalid pointer arguments? This is because such a requirement
would needlessly slow down and bloat correctly written code, i.e. code
that always passes valid arguments. It is usually functions invoking
system calls that set errno to EINVAL because the operating system
kernel *has to* check all arguments for correctness, so as to avoid
accidental or malicious system corruption.

All well and good. However, I choose to use it. I will endevor to
remove it if I post it here to mollify all the useless UBP types.

I will also point out that your check is incomplete anyway because
``obj'' may contain an invalid address that isn't NULL; Which, for the
purpose of setting EINVAL in Unix, is an unmapped address.

Well, this part I have no way of knowing so I must take it in good
faith. That does not mean I can't be defensive where I can.

This will likely execute slower than necessary, since calloc() is
conceptually a malloc() + memset(); A plain malloc() will suffice
because you immediately overwrite the memory anyway.

Again, this is true, but I am comforted that the memory is clean when I
get it. Got it?

Regards,
Stan Milam.