Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

This problem was given to me on previous job interview test. It is over now, but I would like to go through my mistakes and hopefully be more prepared next time!

// Identify as many bugs and assumptions as you can in the following code.
// NOTE that there is/are (at least):
// 1 major algorithmic assumption
// 2 portability issues
// 1 syntax error

// Function to copy 'nBytes' of data from src to dst.
void myMemcpy(char* dst, const char* src, int nBytes)
{

// Try to be fast and copy a word at a time instead of byte by byte

    int* wordDst = (int*)dst;
    int* wordSrc = (int*)src;
    int numWords = nBytes >> 2;
    for (int i=0; i < numWords; i++)
    {
        *wordDst++ = *wordSrc++;
    }

    int numRemaining = nBytes - (numWords << 2);
    dst = (char*)wordDst;
    src = (char*)wordSrc;
    for (int i=0 ; i <= numRemaining; i++);
    {
        *dst++ = *src++;
    }
}

All I found was a syntax error on line

    for (int i=0 ; i <= numRemaining; i++);

Also the first for loop looks fishy.

Can you guys find any other mistakes?

share|improve this question
23  
Ludicrous question! Compilers are what you use for finding syntax errors, not your eyes! –  Neil Butterworth May 29 '11 at 18:24
3  
src = (char*)wordSrc; SRC was declared as const, so can't be changed. –  Cristy May 29 '11 at 18:25
2  
int* wordSrc = (int*)src; needs to be const int*, not int* –  MMavipc May 29 '11 at 18:25
4  
@Cristy, src can be changed. The following would be valid: src = (const char *) wordSrc; (from a const-correctness point-of-view at least). If you wanted to disallow this, declare src as const char * const src. –  Aaron McDaid May 29 '11 at 18:30
3  
@Neil a semi colon after a loop isn't a syntax error though you'd need to use your eyes here though granted you'd probably first isolate that the loop isnt working properly with a debugger –  jk. May 29 '11 at 18:49
show 7 more comments

migrated from stackoverflow.com May 31 '11 at 0:55

This question came from our site for professional and enthusiast programmers.

7 Answers

void myMemcpy(char* dst, const char* src, int nBytes)

int can hold negative values. The proper type here is size_t.

{
    // Try to be fast and copy a word at a time instead of byte by byte
    int* wordDst = (int*)dst;
    int* wordSrc = (int*)src;

Not every char * is also a valid int *. Many architectures only allow an int * to point at an address divisible by sizeof int, which is usually a power of two.

    int numWords = nBytes >> 2;

Whatever a word is, it is not guaranteed to be equal to an int.

If nBytes is negative, the result of the >> operator is undefined. (At least in C.)

    for (int i=0; i < numWords; i++)
    {
        *wordDst++ = *wordSrc++;

When interpreting arbitrary memory as an int, there may be trap representations which lead to undefined behavior. So if you must, use an unsigned int for data transfers. The above point about alignment still holds.

    }

    int numRemaining = nBytes - (numWords << 2);
    dst = (char*)wordDst;
    src = (char*)wordSrc;
    for (int i=0 ; i <= numRemaining; i++);

The trailing semicolon is not a syntax error, but a logical error. Nevertheless, it was not intended.

    {
        *dst++ = *src++;
    }
}

[Note: I didn't find all aspects that are wrong with the code, I only rushed over the code. See the other answers for more things.]

share|improve this answer
3  
+1 for "When interpreting arbitrary memory as an int, there may be trap representations which lead to undefined behavior."! –  Johannes Schaub - litb May 29 '11 at 18:43
7  
"int can hold negative values. The proper type here is size_t" - right solution, wrong reason. There's nothing wrong with a parameter for which certain values are invalid - src must not be a null pointer and nBytes must not be negative, it's reasonable for this to be the caller's problem. The issue with int is that INT_MAX might not be big enough for some regions that a caller would want to copy, and that's not a reasonable problem to leave to the caller to solve (they'd have to do size checks and call this function in a loop). –  Steve Jessop May 29 '11 at 22:30
2  
@x4u: consult 6.2.6.2 in the C99 standard, but the short version is that the standard doesn't require that every bit pattern that can be taken by sizeof(int) consecutive bytes actually represents a value of type int. Integer types can have "padding bits", and padding bits are allowed (for example) to contain a checksum of the other bits, such that if the checksum is wrong the CPU throws a hardware fault (aka "traps") when you try to load that bit pattern into an integer register. It's rare, but permitted, and for that matter it's permitted for unsigned int too... –  Steve Jessop May 29 '11 at 22:40
1  
@Jonathan: I'd say that it happens actually on arcane and obsolete hardware. It can happen theoretically in any C or C++ implementation ;-) Oh, and a slight correction to myself: I cited C because everyone agrees this code looks C-like, but since this is tagged C++, that says in 3.9.1/1 "For unsigned character types, all possible bit patterns of the value representation represent numbers. These requirements do not hold for other types". The C standard is a bit more forthcoming with the explanation how and why they might not hold. –  Steve Jessop May 29 '11 at 22:50
1  
also (not bothering to put it as an answer) - when casting back from int* to char* before the second loop, not sure that you'll get the "leftover" byte that you want. I think that based on the Endian-ity you may get a different one –  davka May 30 '11 at 14:32
show 8 more comments

Algorithmic assumptions:

  • The pointers are both aligned on integer boundaries so the integer part of the copy can work.
  • The memory regions do not overlap.

Portability assumptions:

  • sizeof(int) == 4.
  • nBytes >= 0.
  • (Restatement of algorithmic assumption): Pointers can be misaligned without incurring performance cost. They lead to segmentation violation on some machines (SPARC, PowerPC), extra memory reads on others. IIRC, on DEC Alpha, it was a whole system trap to handle the misaligned access - incredibly slow. There was a user-level command uac (unaligned access control) to manipulate how the system handled unaligned memory accesses.

Bugs:

  • (You identified semi-colon after for loop).
  • i <= numRemaining should be i < numRemaining.
  • Casting away of const was not necessary.
share|improve this answer
1  
"The memory regions do not overlap" - to be fair, probably not a bug in the code since this is called MyMemcpy rather than MyMemmove. It's just that the function is under-documented. –  Steve Jessop May 29 '11 at 22:33
    
@Steve: correct - it is an unstated assumption rather than a bug per se, not least because of its name. –  Jonathan Leffler May 29 '11 at 22:36
add comment
  1. You can't assume that an int is always 4 bytes (as discussed in this question).

  2. I think that

    for (int i=0 ; i <= numRemaining; i++);
    

    should be changed to

    for (int i=0 ; i < numRemaining; i++)
    

    because otherwise it would go one character past the end of src and dst.

  3. nBytes must be greater than 0 because the right shift operator does not have defined behavior for negative numbers (for example, "the arithmetic right shift of the number -1 (which is represented as all ones) in a two's complement representation [...] yields -1").

  4. As others have mentioned,

    int* wordSrc = (int*)src;
    

    should be

    const int* wordSrc = (const int*)src;
    

    to preserve const-correctness (likewise, src = (char*)wordSrc; should be src = (const char*)wordSrc;.

share|improve this answer
2  
Your number 3 is wrong. ideone.com/r6uhh –  Benjamin Lindley May 29 '11 at 18:43
1  
@Benjamin Whoops! You're right. I'll fix that. :) –  Chris May 29 '11 at 19:02
add comment

One obvious portability issue: On (older/smaller) Motorola machines, it is not allowed to cast a char* to int*, as integer must be properly aligend. E.g. char* pChar = 0x1001; is allowed whereas int* pInt = 0x1001; would segfault.

share|improve this answer
add comment
// Function to copy 'nBytes' of data from src to dst.

That documentation doesn't say whether the areas are allowed to overlap. Not good.

void myMemcpy(char* dst, const char* src, int nBytes)
{
    // Try to be fast and copy a word at a time instead of byte by byte
    int* wordDst = (int*)dst;
    int* wordSrc = (int*)src;
    int numWords = nBytes >> 2;
    for (int i=0; i < numWords; i++)
    {
        *wordDst++ = *wordSrc++;
    }

This assumes that the initial memory is aligned (otherwise, either it would run slow because of unaligned accesses, or crash because of a processor that only does aligned accesses).

It also assumes that int has 4 bytes, which is common but not a requirement by C or C++ at all. It's also a good idea to make wordSrc an int const*, because you don't want to write through it.

In fact, the memory is not allowed to overlap with this algorithm.

int numRemaining = nBytes - (numWords << 2);
dst = (char*)wordDst;
src = (char*)wordSrc;
for (int i=0 ; i <= numRemaining; i++);

This semicolon after the for-head is not a syntax error. It's a semantic problem. A semicolon as the for-body and a lonely block in a function is fine. Another semantic problem is i <= numRemaining, which should be i < numRemaining.

{
    *dst++ = *src++;
}

}

share|improve this answer
add comment

In addition to the other points mentioned, I would say that the major algorithmic assumption is that there is a need to write a "myMemcpy"

share|improve this answer
1  
Not really an algorithmic assumption. I'd still shoot anyone who decided to write their own. –  Winston Ewert May 30 '11 at 1:44
    
@Winston -- you're right. Maybe I should have said "major failed assumption" +1 for shooting! –  TomG May 31 '11 at 0:50
add comment
  • It assumes an int is 4 bytes (as other people have said)

  • I'm inclined to give it a pass on the inability for some architectures to cast pointers to different objects back and forth. This is a problem on few modern architectures.

  • It assumes the underlying system doesn't have alignment issues (SIGBUS). Some systems require word alignment for word accesses.

  • The <= (as other people have said) in the last loop

  • No error checking for bad (negative) values of length

  • Pointers may overlap (dst might be one byte above src). Copying in that order might make neither a good copy.

  • Extra ; on for loop

  • Requires C99 (not strictly a flaw)

  • Doesn't use Duff's device (manual loop unrolling, for speed :-)

  • Doesn't use standard library which will be less buggy and faster (potentially using special hardware instructions)

share|improve this answer
    
SPARC, PowerPC - both those require types to be properly aligned. Even within the Intel hegemony, misaligned access costs time. –  Jonathan Leffler May 29 '11 at 18:57
    
@Jonathan Leffler: No, I wasn't talking about the word alignment issue—that is another bullet. I was talking about how some architectures have different sized pointers to characters and to words, and you literally cannot effectively/safely/correctly cast them back and forth, or at least not without taking great care. –  Seth Robertson May 29 '11 at 19:07
    
I worked on one machine a long time ago (1983-1986, ICL Perq, microcoded) where the basic addresses were (2-byte) word addresses. You could cast between char * and int * (there was no void * back then, at least on those machines), but the bit representation of the char * address bore little resemblance to the bit representation of the int * address. The cast was not a 'no-op' at the machine level. If you did not get a declaration for malloc() in place, all hell broke loose. But you seem to be making a stronger assertion; can you give specific examples of machines and compilers? –  Jonathan Leffler May 29 '11 at 19:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.