## A Spoiled Riddle

### February 8, 2009

tags: ,

Here’s a C riddle: The following program was obviously expected to assign 1 to all the prime indices in the array and 0 to all the others.  However, it enters an infinite loop.  Explain.

#define ARR_SIZE 10

IsPrime(n)

int n;

{

int i;

for (i = 1; i < n; ++i)

if (n % i == 0) return 0;

return 1;

}

main()

{

int arr[ARR_SIZE];

int it;

for (it = 0; it <= ARR_SIZE; ++it)

arr[it] = IsPrime(it);

}

My first intuition about this was obviously something like “hey, it’s an off-by-one with the array index”.  But an infinite loop?

Let’s cut to the chase: The obvious intent of the riddle’s authors is that arr[10] is essentially the stack location that holds it, our loop variable.  So basically when we overflow the array we reset the index back to IsPrime(10) which happens to be 0 and the loop restarts, indefinitely.

However, the riddle was totally spoiled for me by the following thoughts:

• Had I run it in Visual Studio, Debug mode, I’d toggle a runtime check failure when the stack around the arr array is corrupted (debug runtime checks would have a canary set up to catch this).
• Had I run it in Visual Studio, Debug mode, without runtime checks, it would simply exit doing nothing because in Debug there’s enough stack space around each local variable to accommodate a small family.
• Had I run it in Visual Studio, Release mode, one (or two) of two things would ruin the riddle:
• The it loop variable is most likely to sit in a register, so overflowing the stack will have no effect on its value whatsoever.
• Even if it doesn’t sit in a register, the assignments to arr are likely to be eliminated by the optimizer because the program doesn’t seem to need them.  In fact, a smart-enough optimizer would optimize this whole program into a nop.

Running these tests in Visual Studio verified, indeed, that this programming riddle has failed to amuse me.  🙂