Making multiple copies of a pattern

Question

Here's a function for making multiple copies of a block of memory in another block of memory. It handles the case when the size of the target is smaller than or not a perfect multiple of the source pattern.

It proceeds by copying the pattern once, twice, four times, eight times, etc. until it can make a last 'massive' copy and fill the target buffer.

The protocol on this site is (apparently) to answer your own question with the improved code rather than edit original question. That makes sense otherwise other answers and feedback may be difficult to understand!

#include <string.h> //This is where memcpy() hangs out. I know! I know!

///Fills a block of memory with a specified pattern. 
///The target block starts at pToFill and extends for pToFillSize bytes.
///The source pattern starts at pFillWith and extends for pFillWithSize bytes.
///Will fill the whole buffer including a trailing partial pattern at the end (if necesssary).
///pFillWithSize must not be 0. pFillWith must not be NULL.
///If Either pToFill is NULL or pToFillSize is 0, does nothing and returns without error.
///The area to fill and pattern must not overlap or behaviour is undefined.
void memcopyfill(void*const pToFill,const size_t pToFillSize,void*const  pFillWith,const size_t pFillWithSize){
    if(pToFill==NULL||pToFillSize==0){
        return;//Nothing to do.
    }
    if(pFillWith==NULL||pFillWithSize==0){
        return;//Can do nothing...
    }
    if(pToFillSize<pFillWithSize){
        memcpy(pToFill,pFillWith,pToFillSize);
        return;//Short buffer.
    }
    //The to buffer is bigger so we start with a full copy of pattern.  
    //Now we keep doubling the copies by copying and copying from the target onto itself.
    char*lFillFrom=((char*)pToFill)+pFillWithSize;
    size_t lFilledSoFar=pFillWithSize;
    char*lFillEnd=((char*)pToFill)+pToFillSize;
    while(lFilledSoFar<(lFillEnd-lFillFrom)){//Overflow safe.
        memcpy(lFillFrom,pToFill,lFilledSoFar);
        lFillFrom+=lFilledSoFar;
        lFilledSoFar=lFilledSoFar<<1;//Doubling....
    }
    //No we can fill the end of the buffer in one final step. Could be half the job.
    memcpy(lFillFrom,pToFill,pToFillSize-lFilledSoFar);
}

Can it be bettered?

One use is to fill an array with a default structure. If that is the purpose you don't need the initial fannying about with the short buffer special case.

There is no guarantee that NULL has a bit-pattern of all zeros so if you wanted to be ultra-ultra portable you ought to be doing something like this to get an array full of NULL.

I think most people use calloc(.) and don't even think about it.

If you use it for strings don't forget your null terminator!

Bonus question

Does anyone know of an extant platform where NULL doesn't have a zero filled bit-pattern?

I half remember one where it was 0xFFF...FF and that was clever because the hardware could detect overflow easily and handle all sorts of wrap-around errors gracefully. I'm damned if I can remember what it was. It may have been a hypothetical example to show why standards should give implementers freedom.

Answer 1

Here are some things I see that might help you improve your code:

Use more whitespace

Lines like this one:

char*lFillEnd=((char*)pToFill)+pToFillSize;

make my eyes bleed.

char *lFillEnd = ( (char*)pToFill ) + pToFillSize;

That version is much easier for humans to parse because of the judicious use of whitespace.

Use better names

The code has an odd characteristic in that every variable names begins with either p or l rendering the names unprounceable and impeding readability. I can only guess that these might have been intended to signify parameter and local but those distinctions are quite obvious to anyone who knows C and not helpful. Also memcopyfill isn't a terrible name, but perhaps patternfill would be more descriptive? I'd suggest using memcpy inspired names that are terse but easier to read for the parameters: dst, dstsize, src and srcsize.

Combine conditions for early bailout

It's good to have the early bailout in the case of NULL pointers or zero-length but it makes less sense for those to be two separate if statements. Because of short-circuit evaluations, the resulting code will be just as efficient if you write just a single if statement and it is, I think, a little easier to see what is going on in the code.

Think carefully about size comparisons

The code currently has a line:

if(pToFillSize<pFillWithSize){

But shouldn't that comparison be <=?

Consider returning an error code

In the case of an early bailout, it might be handy to return an error code indicating that something was wrong. This might also be used in the case that the buffers overlap, violating your stated calling conditions.

Don't use const inappropriately

Normally I find myself advocating for more use of const in code I review, but in this case, I see two instances where it might be better omitted. Specifically, having the size parameters declared as merely size_t rather than const size_t makes sense and mirrors the declaration of the library routine memcpy. Also, we are clearly going to alter the memory pointed to by pToFill so it's inappropriate to declare it const.

Remove the local variables

Most of the local variables are actually not needed in this code. Don't forget that your parameters are actually local copies that can be used instead:

Put it all together

Here's one alternative that incorporates all of these changes:

bool patternfill(char *dst, size_t dstsize, const char *src, size_t srcsize)
{
    if (dst == NULL || dstsize == 0 || src == NULL || srcsize == 0) {
        return false;  //Can do nothing...
    }
    size_t remaining = dstsize;
    if (remaining <= srcsize) {
        memcpy(dst, src, remaining);
        return true;  
    }
    // make one full copy
    memcpy(dst, src, srcsize);
    dst += srcsize;
    remaining -= srcsize;
    // now copy from destination buffer, doubling size each iteration
    for (src = dst; remaining > srcsize; srcsize *= 2) {
        memcpy(dst, src, srcsize);
        dst += srcsize;
        remaining -= srcsize;
    }
    // copy any remainder
    memcpy(dst, src, remaining);
    return true;
}

Perform tests

I wrote some simple test code to exercise the two versions of this function (with some minor changes to the original to have the same signature). Here is the code. First, a simple verification function to check that the pattern was successfully copied:

bool verifyfill(const char *buff, size_t buffsize,
        const char *pattern, size_t patternsize)
{
    if (buff == NULL || pattern == NULL || buffsize == 0 || patternsize == 0)
        return true;
    const char *pattend = (char *)pattern+patternsize; 
    for (const char *p = pattern; buffsize && *buff == *p; buff++, --buffsize) 
        if (++p == pattend)
            p = pattern;
    return buffsize == 0;
}

Then a bit more test harness to collect and compare the two functions:

typedef bool (*TestFunc)(char *, size_t, const char *, size_t);

bool checkpatternfill(TestFunc test, char *buffer, size_t buffsize,
        const char *pattern, size_t patternsize)
{
    memset(buffer, 'x', buffsize);
    test(buffer, buffsize, pattern, patternsize);
    return (verifyfill(buffer, buffsize, pattern, patternsize));

}

struct {
    TestFunc fn;
    const char *name;
} tests[] = {
    { memcopyfill, "original" },
    { patternfill, "improved" }
};

Finally, a main routine to check both accuracy and performance:

int main()
{
    const size_t buffsize = 100;
    const char pattern[]="Pattern";
    const size_t patternsize = strlen(pattern);
    const int testCount = sizeof(tests)/sizeof(tests[0]);
    char *buffer = malloc(buffsize);
    if (buffer == NULL) {
        perror("Can' allocate buffer");
        return 1;
    }

    // basic functionality tests
    for (int i=0; i < testCount; ++i) {
        if (checkpatternfill(tests[i].fn, buffer, buffsize, pattern, patternsize))
        {
            printf("%s Test passed\n", tests[i].name);
        } else {
            printf("%s Test failed!\n", tests[i].name);
            char *buffend = buffer+buffsize;
            for (char *p = buffer; p < buffend; ++p)
                putc(*p, stderr);
        }
    }

    // speed tests
    for (int i=0; i < testCount; ++i) {
        clock_t start = clock(), diff;
        for (int j=10000000; j; --j) {
            tests[i].fn(buffer, buffsize, pattern, patternsize);
        }
        diff = clock() - start;
        printf("%s took %f seconds\n", tests[i].name, 1.0 * diff / CLOCKS_PER_SEC);
    }
    free(buffer);
}

Test results:

On my 64-bit Linux box using gcc with -O2 optimization, I get this result:

 original Test passed
 improved Test passed
 original took 0.338862 seconds
 improved took 0.270134 seconds

Answer 2

Following very helpful feedback from @Edward here is the revised function.

///memcopyfill:Fills a block of memory with a specified pattern.
/// Starts from the address pToFill and fills for pToFillSize bytes.
///Will fill the whole buffer including a trailing partial pattern at the end (if necessary).
///pFillWithSize must not be 0. pFillWith must not be NULL. 
///If Either pToFill is NULL or pToFillSize is 0, does nothing and returns without error.
///The area to fill and pattern must not overlap or behaviour is undefined.
///Returns 0 on success and non-zero on error.
int memcopyfill(void*const pToFill,const size_t pToFillSize,const void*const  pFillWith,const size_t pFillWithSize){
    if(pToFill==NULL||pToFillSize==0){
        return 0; //Nothing to do.
    }
    if(pFillWith==NULL||pFillWithSize==0){
        return 1; //ERROR! Something to fill and nothing to fill it with.
    }
    if(pToFillSize<=pFillWithSize){
        memcpy(pToFill,pFillWith,pToFillSize);
        return 0; //Complete in one (possibly short) copy.
    }
    //The to buffer is bigger so we start with a full copy of pattern.
    memcpy(pToFill,pFillWith,pFillWithSize);

    //Now we keep doubling the copies by copying and copying from the target onto itself.
    char*lFillFrom=((char*)pToFill)+pFillWithSize;
    size_t lFilledSoFar=pFillWithSize;
    char*lFillEnd=((char*)pToFill)+pToFillSize;
    while(lFilledSoFar<(lFillEnd-lFillFrom)){//Overflow safe.
        memcpy(lFillFrom,pToFill,lFilledSoFar);
        lFillFrom+=lFilledSoFar;
        lFilledSoFar=lFilledSoFar<<1;//Doubling....
    }
    //No we fill the rest of the buffer. 
    memcpy(lFillFrom,pToFill,pToFillSize-lFilledSoFar);
    return 0;//That went well!
}

The most relevant change is the 'early exit' when the pattern is exactly the same size as the target. My version went that way when the main body couldn't be executed but this version also makes the early exit when the main-body can be avoided.

It's the classic anatomy of a function that part of the pre-amble is to identify both 'degenerate' , 'edge' or 'special' cases that the main body can't handle and common 'easy' cases that it improves performance to identify and also handle as special cases.

if(pToFillSize<=pFillWithSize){ is now helping cover both those bases quite neatly.

I also made the parameter toFillWith const as it should always have been.

Finally I added an error-code return. The standard C library functions don't tend to consider internal integrity (e.g. invalid arguments) so I was in two-minds about how to respond to a call to fill an non-empty target with an empty pattern. That's clearly a catastrophic condition that can't be ignored so on reflection I've added an return code in the most general style of C - 0 for success, non-zero for failure.