Hacker News Reader

Comment by Amnon | Hacker News Reader

Just wondering, what's the solution to the riddle at the end? The test function sets up the input, calls the routine, and then compares its output to the desired output. There doesn't seem to be a place for error there.

View on HN

See http://www.joachimschipper.nl/posts/20100622/answer.txt. (Hidden behind a hyperlink to not spoil the riddle.)

I think I disagree with you. The input you mention is correctly handled by the routine you mention, and is tested correctly.

Certainly there is a bug other than the one you think you've found, and I don't think the circumstances you mention demonstrate a bug at all.

I would certainly be interested in seeing a more detailed analysis.

You're right, that answer isn't correct. I still think that particular input should be tested, though (you say it is - did you leave out that part of your testing program? It should be possible to construct a program that fails on such inputs.)

I don't think I've found a real "bug" yet. You include, but don't use, stdlib.h; you exit with status 0, even on error; but these are nitpicks, not what you mean. I'll think a bit more.

I tested that case when you mentioned it. All routines submitted pass it correctly, so I haven't worried about it too much. To do so would be to stray too far from the original intention. I think it's hard to write a natural looking routine that fails that test.

I return 0 in all cases because my test succeeds, even if the routine it's testing fails. It's up to my shell to decide what to do about that error. As it stands it reports the error, but it has succeeded in doing so, so it hasn't failed.

But that's not the point, as you say.

And the real bug is still there.

Well, I'm stumped. I can think of some other "cosmetic" issues and some things you fail to test (e.g. that the function is in-place, runs in O(strlen(z_terminated)) and does not access memory beyond z_terminated[strlen(z_terminated)]), but that's it. Besides, as you mention, such issues can usually be found just by looking at the function.

Will you give out the answer at some point?

Yes - in the next part of the analysis.

http://en.wikipedia.org/wiki/Integer_overflow

Nope - not integer overflow.

(OK, yes, for exceedingly large inputs there are issues about sizes of integers, etc., but that's not the bug. It's much, much simpler.)

Deleted comment

I quickly realized my mistake, but apparently couldn't delete fast enough. Need more coffee.

Unless I'm sorely mistaken, there's no integer overflow in the program as published. (You could cause an overflow in test() by calling it with a very long output argument, but it's much simpler to cause a buffer overflow, so why bother?)

Reply on news.ycombinator.com