A pointer problem from a high school programming contest

Hi experts,

The code below is from a programming contest, the answer must be given without using a compiler(this test is on paper).


The problem: How many '*' does that piece of code prints?
a) 20
b) 25
c) 33
d) 50
e) 100

Code:

---

#include<cstdio>
void f(int i){i--;}
void g(int i){int*p;p=&i;*p--;}
void h(int*p){*p--;}
void i(int*p){int i;i=*p;i--;}
int main()
{
int index=100;
for(;index>0;index--)
{ printf("*"); f(index); g(index); h(&index); i(&index); }
}

---

I found out 50, but when i put it in compiler i saw that i'm mistaken, the answer seems 100. How can it be? shouldn't function h decrease index too?

thanks in advance!

Quote:

---

Originally Posted by kolistivra

I found out 50, but when i put it in compiler i saw that i'm mistaken, the answer seems 100. How can it be? shouldn't function h decrease index too?

---

Look carefully at an operator precedence table. *p-- isn't doing what you think it is.

If I'm not mistaken, each of the *p--'s is generating a bad pointer by decrementing p, then dereferencing the result, either of which generates undefined behavior. So there is no 100% correct answer (though if you assume that *p-- is equivalent to a noop, then it's 100).

Quote:

---

Originally Posted by robatino

If I'm not mistaken, each of the *p--'s is generating a bad pointer by decrementing p, then dereferencing the result, either of which generates undefined behavior. So there is no 100% correct answer (though if you assume that *p-- is equivalent to a noop, then it's 100).

---

It's postfix decrement, so it decrements after the dereference. This is a funny example because although the decrement binds first, its operation happens second.

You typically see this kind of thing in loops which copy data (usually with increment, not decrement):

Code:

---

type *src, *dst, *end;
...
while(src < end)
    *dst++ = *src++;

---

> It's postfix decrement, so it decrements after the dereference.
You're right, I don't know what I was thinking since I do this all the time. So it's just the decrement that generates the undefined behavior (though the conclusion is the same).

Quote:

---

Originally Posted by robatino

> It's postfix decrement, so it decrements after the dereference.
You're right, I don't know what I was thinking since I do this all the time. So it's just the decrement that generates the undefined behavior (though the conclusion is the same).

---

I don't think there's any undefined behavior. The decrement turns the pointer into something undefined, but the function returns immediately so the bogus pointer is never used.

If merely being in possession of an undefined pointer could lead to undefined behavior, then pretty much every program in the universe is undefined, because whenever you declare a pointer there is a brief period of time before it is initialized:

Code:

---

void nuclear_explosion()
{
    int *kaboom;

    printf("I explode now because kaboom is undefined!\n");
    kaboom = NULL;
}

---

Any platform or compiler where that blows up is just ridiculous. Even if the standard implies it.

Actually, I think I remember reading in the standard that there is only one case where you can have a pointer that points to an undefined location, and that is the case of an uninitialized pointer. That is a special case, though, so kaboom is not undefined behavior but decrementing p is.

The part of the standard I was looking at was not specifically related to this, though, so it is possible that the actual wording is different.

Quote:

---

Actually, I think I remember reading in the standard that there is only one case where you can have a pointer that points to an undefined location, and that is the case of an uninitialized pointer.

---

There is at least one other case, that of a pointer that points one past the end of an array.

What about pointers to out-of-scope variables? Or NULL pointers. Or pointers to freed memory.

I believe the undefined behavior only occurs when the pointer is actually _assigned_ a bad value. I found the following (http://gcc.gnu.org/onlinedocs/libstd...ors/howto.html) though I don't have an exact reference in the Standard:

1. You can point anywhere in the array, or to the first element past the end of the array. A pointer that points to one past the end of the array is guaranteed to be as unique as a pointer to somewhere inside the array, so that you can compare such pointers safely.
2. You can only dereference a pointer that points into an array. If your array pointer points outside the array -- even to just one past the end -- and you dereference it, Bad Things happen.
3. Strictly speaking, simply pointing anywhere else invokes undefined behavior. Most programs won't puke until such a pointer is actually dereferenced, but the standards leave that up to the platform.

Edit: Here's a link to the exact part of the Standard that mentions the undefined behavior (see 1161).

http://c0x.coding-guidelines.com/6.5.6.html

Quote:

---

Originally Posted by laserlight

There is at least one other case, that of a pointer that points one past the end of an array.

---

I'm not sure if it also includes a pointer to a position immediately before the beginning of an array as well... But if it doesn't, it should. There's no legitimate reason to prevent people from processing an array backwards instead of forwards.

This is one area where I feel perfectly safe disregarding the standard.

Quote:

---

What about pointers to out-of-scope variables? Or NULL pointers. Or pointers to freed memory.

---

As I understand it, null pointers do not point to any location, so they do not point to any undefined location. The other two look like good examples too.

Quote:

---

I'm not sure if it also includes a pointer to a position immediately before the beginning of an array as well... But if it doesn't, it should.

---

I have been searching the C++ standard for a word on this, but it seems to only deal with one past the end pointers explicitly.

Quote:

---

Originally Posted by laserlight

I have been searching the C++ standard for a word on this, but it seems to only deal with one past the end pointers explicitly.

---

The C and C++ standards irritate me because they were written under the assumption that a computer could be ANYTHING at all. A computer might work via millions of tiny clowns on unicycles. So the standard ends up disallowing tons of completely reasonable code.

Any platform where that nuclear_explosion() function blows up is a platform you'll never see me writing code for. At least not in C/C++.

Quote:

---

Originally Posted by brewbuck

I'm not sure if it also includes a pointer to a position immediately before the beginning of an array as well... But if it doesn't, it should.

---

It doesn't. I don't remember the details, but there was a reason involving much more wasted memory if one-past access was allowed at both ends. In any case, it's possible to write loops so they only require it at one end (of course the choice of which end is arbitrary).

Here's a long and detailed thread on the subject:

http://groups.google.com/group/comp....18f6cccd56427d

Quote:

---

Originally Posted by robatino

Here's a long and detailed thread on the subject:

http://groups.google.com/group/comp....18f6cccd56427d

---

Here's the relevant passage from that discussion:

Quote:

---

The Rationale says the Committee considered defining
the effects at both ends (bilateral dispensations?), but
rejected it for efficiency reasons. Consider an array of
large elements -- structs of 32KB size, say. A system
that actually performed hardware checking of pointer values
could accommodate the one-past-the-end rule by allocating
just one extra byte after the end of the array, a byte that
the special pointer value could point at without setting off
the hardware's alarms. But one-before-the-beginning would
require an extra 32KB, just to hold data that could never
be used ...

---

I can understand the benefit of an architecture with fine-grained access control to memory. Yes, I absolutely can. But this is still ridiculous. What harm is there in POSSESSING a pointer which points out of bounds? If the architecture really is capable of fine-grained access control, then attempting to use this pointer will result in a fault ANYWAY. This is a completely arbitrary restriction that gives no real benefit whatsoever, while disallowing lots of completely reasonable code.

And get this: the standard specifically ALLOWS an uninitialized pointer. So somehow, you're going to have to tell the bounds-checking hardware "Hey, ignore this one particular pointer -- it's okay according to the C standard." Which of course forces language-specific concerns into the hardware, which is completely idiotic.

Quote:

---

And get this: the standard specifically ALLOWS an uninitialized pointer. So somehow, you're going to have to tell the bounds-checking hardware "Hey, ignore this one particular pointer -- it's okay according to the C standard." Which of course forces language-specific concerns into the hardware, which is completely idiotic.

---

It would be relatively easy for a compiler to make uninitialized pointers point to NULL or something if the hardware didn't allow uninitialized pointers, but it would be difficult to do the same sort of thing for one-before-the-start pointers. Just a thought.

Initialisation requires no prior knowledge of the old (undefined) contents.

So saying
p = NULL;
neither loads p into a machine register, nor attempts to dereference it.

p--;
on the other hand has the potential for all sorts of problems (of the undefined variety), if p steps off the beginning of an array, or in this case no longer points at a valid object.

What if said decrement resulted in address underflow, and an immediate trap without even trying to dereference it? The "it hasn't happened to me yet" defence isn't good enough.

You could argue that in this specific program that there won't be a problem, but it still remains undefined (remember, undefined includes producing the correct answer). But one specific example isn't good enough to extrapolate every single instance, in every single program, compiled with every single compiler for any real or abstract machine.

Simply having an uninitialised pointer (or anything else for that matter) in scope isn't undefined behaviour. What you do next however is, if that thing isn't initialisation.
It would be just as dumb to assume that some floating point operation using an uninitialised float would be just as harmless.

Quote:

---

Originally Posted by Salem

What if said decrement resulted in address underflow, and an immediate trap without even trying to dereference it? The "it hasn't happened to me yet" defence isn't good enough.

---

I know of no architecture that would do that. So I admit that the code I write is actually a more restrictive version of C/C++ than the standard would indicate -- the code wouldn't work on such an architecture. But I really don't care. It's no different than writing programs that call getch(). Obviously, such programs are restricted to platforms where getch() is available. Whereas my code is restricted to platforms that don't fault when an invalid pointer value is loaded into a variable.

As I've stated in the past, portability is a spectrum. I understand that some of the code I write is not strictly standard C. But the reality is, it works everywhere. And I'm not talking "I tested it on Windows and Linux." A platform where it didn't work is a platform I would avoid. A system where simply loading an invalid pointer value into a register causes a fault is just plain dumb design.

Quote:

---

It would be just as dumb to assume that some floating point operation using an uninitialised float would be just as harmless.

---

If you look at the newsgroup thread that spawned this discussion, there are others who agree with me. This particular facet of the standard is just plain stupid and largely irrelevant. Don't assume that because I choose to ignore this particular thing that I have no clue what portability means.

I understand the need to sometimes compromise portability for functionality or efficiency. But can you give an example of a situation where allowing invalid pointer assignments is necessary for this? Loops can normally be trivially modified to avoid them with no loss of efficiency.

Edit: A typical example is a backwards loop. Most people would write it like

Code:

---

for (p=c.end()-1; p >= c.begin(); --p) {
  // code
}

---

but this generates an invalid iterator at the last iteration. In fact, if the container has zero length, even the initial assignment is invalid. But it can be rewritten as

Code:

---

for (p=c.end(); p != c.begin();) {
  --p;
  // code
}

---

The trick is that the decrement has to be at the beginning of the body, not the end, so --p has to be separate from the rest of the for statement. But it's just as efficient as the other version.

Edit: Actually, I think only random-access iterators can be compared with >=, and only bidirectional or random-access iterators can be decremented. But the point holds when using arrays and ordinary pointers.

It's nice to see that my ignorance can bring all of you into a constructive argument about all this!!!!!


In the end this is what I did:

Code:

---

void Case::print()
{
        char* templwr = new char[m_length + 1];
        strcpy(templwr, m_buf);

        m_lower = templwr;

        cout << m_name << " \""<< m_buf << "\"  String Length: " << getLength() << endl;
        csis << m_name << " \""<< m_buf << "\"  String Length: " << getLength() << endl;
       
        cout << "Lower Case: " << strlwr(m_lower) <<  endl;
        csis << "Lower Case: " << strlwr(m_lower) <<  endl;

        char* tempupr = new char[m_length + 1];
        strcpy(tempupr, m_buf);
        m_upper = tempupr;

        cout << "Upper Case: "<< strupr(m_upper)<< endl;

        csis << "Upper Case: "<< strupr(m_upper)<< endl;


        delete[]templwr;
        delete[]tempupr;

}

---

And the variables were protected because I needed to access them in this class which is a derived class of String.....

Quote:

---

Originally Posted by robatino

I understand the need to sometimes compromise portability for functionality or efficiency. But can you give an example of a situation where allowing invalid pointer assignments is necessary for this? Loops can normally be trivially modified to avoid them with no loss of efficiency.

---

Here is the basic idiom:

Code:

---

char *start, *end;
start = array - 1; /* Oh no, the HORROR! */
end = array + length;
while(++start < end)
{
    /* Do something */
}

---

This is called "backward biasing," at least where I come from. Why do it this way? Because the value of "start" is the same, both inside the condition and inside the loop. Why does it matter? Reduction of confusion. Try writing a few hundred thousand lines of code and it will become clear. When this same pattern occurs hundreds or thousands (literally) of times in a code base, you aren't going to go through and change everything because of some "hypothetical" architecture where it could be problematic.

There is some funny guy on this board who likes to claim that "walking a pointer is more efficient than indexing an array." This did, in fact, used to be true. And so you see the above pattern in legacy code. All... over... the... place.

It's not like I'm referencing an undefined pointer. It's a syntactic convenience for crap's sake. I'm not giving it up because the standard says so.

Code:

---

for( start = array,  end = array + length; start < end; start++ )

---

To each his own I suppose.


Quzah.

Quote:

---

Originally Posted by quzah

Code:

---

for( start = array,  end = array + length; start < end; start++ )

---

To each his own I suppose.


Quzah.

---

I agree. But I didn't write every line of code I'm responsible for. The fact is, this pattern is everywhere. New code I write usually just uses a for-loop over the index. But I sure as heck am not wasting two years "fixing" all the instances of this.

Quote:

---

There is some funny guy on this board who likes to claim that "walking a pointer is more efficient than indexing an array." This did, in fact, used to be true. And so you see the above pattern in legacy code. All... over... the... place.

---

Actually, I think that discussion was deleted when we had the recent rollback of the forums, heheh.

Quote:

---

The fact is, this pattern is everywhere.

---

I had the impression that the for loop version was clearer and more obvious, even excluding the begin/end idiom in the standard library. Then again, maybe my youth (i.e., less exposure to weird "legacy" stuff) has given me a bias to see the loop as clearer and more obvious.

Code:

---

#define while(x) for( ; x ; )

---

That'll get you started. ;) I've done all the hard work, I'll leave the rest up do you!


Quzah.

I've never seen backward biasing - to me it looks far more confusing than quzah's version, which is basically how I've always seen forward loops done, and which doesn't generate invalid pointers. And if the increment is inside a for loop, instead of a while loop, it gets done at the end of the body instead of the beginning, which means that start has to be initialized to array instead of array-1.

Edit: Then again, I've had the luxury of not having to maintain legacy code. But it's one thing to not want to change thousands of lines of other people's legacy code, and another to write such code yourself.

Quote:

---

Originally Posted by robatino

I've never seen backward biasing - to me it looks far more confusing than quzah's version, which is basically how I've always seen forward loops done, and which doesn't generate invalid pointers.

---

It wasn't invented for clarity's sake ;) I don't claim to have invented it, but I deal with code that uses it on a daily basis. I am not keen on fixing what isn't broke. To me it reads naturally, but as Quzah said, to each his own.

Also, consider that a lot of legacy C code was "hand translated" from other languages during the 80's and early 90's. So a lot of this stuff is a result of directly translating idioms from one language to another, which ends up looking funny. But this particular pattern isn't rare by any means.

Well I am quite new to the entire pointer C++ thing, so this seemed like good practice, can someone tell me if I am following through the program right?

Code:

---

void g (int i) { //Passes a copy of the inputted number?
  int*p; //Creates a pointer
  p=&i; //p Points to the address of i (which is a copy of the original number?);
  *p--; //Points to a non-existing address;
}

void h (int*p) { //Takes a reference to the inputted varible
  *p--; //*Doesnt* deincrement variable since -- is resolved before *
}

void i (int*p) { //Takes a reference to the inputted varible
  int i; //Creates a local varible i
  i=*p; //Assigns i the value of the inputted varible (why was it assigned to p in the first place?)
  i--; //decrements the local copy
}

int main() {
  int index=100;
  for(;index>0;index--) {  //Standard for loop.
      printf("*");
      f(index);
      g(index);
      h(&index);
      i(&index);
  }
  //Prints * 100 times since none of the functions do anything
//Talk about a dumb program
}

---

Quote:

---

which is basically how I've always seen forward loops done, and which doesn't generate invalid pointers

---

What about reverse loops? I think that a naive implementation of reverse iterators for certain standard containers could end up doing something like:

Code:

---

for (rbegin = begin + length - 1, rend = begin - 1; rbegin != rend; --rbegin)

---

Quote:

---

Prints * 100 times since none of the functions do anything

---

That's correct. None of the four functions (main() excluded) has any net effect, assuming that this invalid pointer thing also has no net effect.

I'm trying to follow this discussion, but I'm having a little difficulty understanding what it is that is "allowed" or "not allowed" by the standard. Are we saying that the following code could actually cause a meltdown?

Code:

---

int *p = (int *)rand();

---

Interesting.

As long as p isn't dereferenced, what would be the logic in disallowing a pointer that points to something invalid as long as it is never used (ie. dereferenced)?

Quote:

---

Originally Posted by laserlight

That's correct. None of the four functions (main() excluded) has any net effect, assuming that this invalid pointer thing also has no net effect.

---

Some compilers will even optimize out things that have no effect, so they may not ever even get called.


Quzah.

Quoting from TC++PL, page 557:

Quote:

---

A reverse_iterator is implemented using an iterator called current. That iterator can (only) point to the elements of its sequence plus its one-past-the-end element. However, the reverse_iterator's one-past-the-end element is the original sequence's (inaccessible) one-before-the-beginning element. Thus, to avoid access violations, current points to the element after the one the reverse_iterator refers to. This implies that * returns the value *(current-1) and that ++ is implemented using -- on current.

---

Quote:

---

Originally Posted by MacGyver

As long as p isn't dereferenced, what would be the logic in disallowing a pointer that points to something invalid as long as it is never used (ie. dereferenced)?

---

There is no logic in it. It seems like the designers of the C and C++ standards wanted to forge a language that could conceivably run anywhere, including architectures which are deliberately obtusely designed. I refuse to submit to that kind of stupidity.

Quote:

---

Originally Posted by brewbuck

There is no logic in it. It seems like the designers of the C and C++ standards wanted to forge a language that could conceivably run anywhere, including architectures which are deliberately obtusely designed. I refuse to submit to that kind of stupidity.

---

It seems quite silly, especially considering the fact that no memory accesses are actually performed prior to dereferencing a pointer. How would this be enforced? Would the O/S or hardware actually keep records of all pointers inside a program handy in a table? LOL. That would seem to be such a waste of resources that it makes me sick to even think of it.

You're right when you said that such a system would catch a memory violation when it would occur. That's how a system should be protected imo. I don't understand the motivation to increase the protection anymore.

Anyway, does anyone know of a system that actually performs such checking?

> Anyway, does anyone know of a system that actually performs such checking?
The link I gave earlier

http://groups.google.com/group/comp....18f6cccd56427d

mentions some architectures where this might happen, though I don't understand most of that part of the discussion, not being a hardware expert.

Quote:

---

Originally Posted by MacGyver

Anyway, does anyone know of a system that actually performs such checking?

---

If someone can name one (and virtual machines DON'T count) I'll give them $20, if it's verifiable.

Quote:

---

Originally Posted by James Dow Allen

CBFalconer wrote:
> /* Making fatal hidden assumptions */
> /* Paul Hsiehs version of strlen.


I haven't read your entire treatise, and I surely wouldn't want to
defend
Mr. Hsieh (whose code, he's led us to understand, was written by his
dog)
but I do have some comments.


> #define SW (sizeof (int) / sizeof (char))


The fact that sizeof(char)==1 doesn't make this line bad *if* the
programmer feels that viewing SW as chars per int is important.
I don't defend this particular silliness, but using an expression for
a simple constant is often good if it makes the constant
self-documenting.


> Some sneaky hidden assumptions here:
> 1. p = s - 1 is valid. Not guaranteed. Careless coding.


Mr. Hsieh immediately does p++ and his code will be correct if then
p == s. I don't question Chuck's argument, or whether the C standard
allows the C compiler to trash the hard disk when it sees p=s-1,
but I'm sincerely curious whether anyone knows of an *actual*
environment
where p == s will ever be false after (p = s-1; p++).


Many of us fell in love with C because, in practice, it is so much
simpler
and more deterministic than many languages. Many of the discussions in
comp.lang.c seem like they'd be better in a new newsgroup:
comp.lang.i'd_rather_be_a_lawyer


:-) :-)


James Dow Allen

---

Thanks for the link.

ROFL, I love this post. :D

Quote:

---

Originally Posted by MacGyver

Thanks for the link.

ROFL, I love this post. :D

---

Paul Hsieh, by the way, is the author of pstdint.h, a reasonably portable version (as portable as such a thing can be) of the C99 header stdint.h, for platforms which don't have it.

Another interesting tidbit is that pointer subtraction is done using the type ptrdiff_t, which is NOT guaranteed by the standard to be able to hold the result (!). In fact, it's only guaranteed by the Standard to have a range of between plus and minus 65-thousand something. If the result doesn't fit in a ptrdiff_t, the behavior is undefined. Fortunately, most code involving pointer subtraction can be easily modified to avoid it.

http://www.thescripts.com/forum/thread460624.html