C++ Interview question

Question

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?

Answer 1

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"

Answer 2

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;.

Answer 3

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.

Answer 4

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.]

Answer 5

• 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)

Answer 6

// 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++;
}

}

Answer 7

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.