Highly efficient string reversal code

[dominantubergeek]

Hello, I'm a highly experienced expert C programmer and I've written
this code to reverse a string in place. I think you could all learn
something from it!

int reverse(char* reverseme){
int retval=-1;
if(retval!=NULL){
int len=strlen(retval){
if(len>0){
int half=len>>1;
for(;retval<half;retval++){
reverseme[retval]^=reverseme[len-(retval+1)];
reverseme[len-(retval+1)]=reverseme[retval];
reverseme[retval]^=reverseme[len-(retval+1)];
}
}
}
return retval;
}

-Phil/CERisE

[Nick Keighley]

On 23 Sep, 05:51, CBFalconer <[e-mail]:

"[e-mail]" wrote:

pete <[e-mail]:

... snip ...

It's undefined when attempting to reverse a zero length string.

How to reverse a zero length string for it has only a single
NULL terminating character : )

note: NULL is not a character. '\0' *is* a character.

The reverse function quits if this is the case.

Not mine, which was posted earlier. *It also considers a NULL
passed in as indicating an empty string, and returns 0 (for input
length).

which I consider a bug
--
Nick Keighley

[Nick Keighley]

On 22 Sep, 19:42, [e-mail] wrote:

Hello, I'm a highly experienced expert C programmer and I've written
this code to reverse a string in place. I think you could all learn
something from it!

int reverse(char* reverseme){
* *int retval=-1;
* *if(retval!=NULL){
* * * int len=strlen(retval){
* * * if(len>0){
* * * * *int half=len>>1;
* * * * *for(;retval<half;retval++){
* * * * * * reverseme[retval]^=reverseme[len-(retval+1)];
* * * * * * reverseme[len-(retval+1)]=reverseme[retval];
* * * * * * reverseme[retval]^=reverseme[len-(retval+1)];

for newbies: don't do this. It is a very stupid way to swap two
integers.

* * * * *}
* * * }
* *}
* *return retval;

}

missing }

--
Nick Keighley

[Bartc]

<dj******@csclub.uwaterloo.ca.invalidwrote in message
news:gb**********@rumours.uwaterloo.ca...

In article <9D******************@text.news.virginmedia.com> ,
Bartc <[e-mail]:

>>
<dj******@csclub.uwaterloo.ca.invalidwrote in message
news:gb**********@rumours.uwaterloo.ca...

>>Since the subject has come up, here's one I've been waiting for an
excuse to post:

[...]

>>I tested your reverse function against the simplest reverse function of my
own I could knock up. Mine was 6 to 20 times faster that yours, to reverse
a
77-character string one million times on my machine.

So if there is a point to your version, I haven't quite grasped it.

I'd rather give my version to somebody who's posting an obvious
homework problem than yours.

Nobody mentioned homework. Anyway there are plenty of versions of this
around; my code is practically identical to that in K&R2.

>
Once you untangle it, it also demonstrates a few code-structure ideas
that are quite useful to have wrapped your brain around (not that
reversing a string in C is really a _good_ way to illustrate those),
and I like to think it provides a nifty example of how to build working
approximations to some high-level abstractions that C doesn't provide
natively.

I've had a brief look, although I really think you need to lay out your code
better.

--
Bartc

[vippstar]

On Sep 23, 11:19 am, Nick Keighley <[e-mail]>
wrote:

On 23 Sep, 05:51, CBFalconer <[e-mail]:

"[e-mail]" wrote:

The reverse function quits if this is the case.

Not mine, which was posted earlier. It also considers a NULL
passed in as indicating an empty string, and returns 0 (for input
length).

which I consider a bug

Depends on the documentation. Do you consider it a bug if strlen(NULL)
returns 0?
I'd just document that NULL shouldn't be passed to such function; what
it does after that is not important. (ie returning 0 or dereferencing
a null pointer)

[James Kuyper]

Richard wrote:

Peter Nilsson <ai***@acay.com.auwrites:

>Richard<[e-mail]:

....

>>while(p-- s)

Where does "undefined" in any shape or form indicate that there will be
knock on effects outside of the value of the variable in question
considering it is not used anymore? And if that variable is not used
anymore does it really matter? Its like using (or not using rather) an
uninitialised pointer.

Yes, I know "undefined" can mean "anything", but lets stay real here for
a moment. Possibly "undefined" is "defined" to mean "undefined for that
variable in question".

Or?

Or, it means that the compiler is allowed to perform optimizations
elsewhere in your program, based upon the assumption that your code does
not have undefined behavior.

Specifically, your use of 'p--' at that point in the program can be used
by the compiler as an indication that p does NOT point at the start of
the array. As a result, if there is a previous statement that uses 'p',
and the compiler can verify that the value of 'p' should not be changed
between that previous statement and the entry to your while() loop, then
the compiler is free to optimize that previous use of 'p', by making
that same assumption.

For example, if that previous statement were

q = (p+3)-1;

the compiler would be free to rearrange that as

q = (p-1)+3;

Now, I'm not claiming that this is actually an optimization. There's no
obvious benefit to that rearrangement, it's just the simplest example I
could think of, of a legal rearrangement with potentially fatal
consequences. The point is, that because you use 'p--' later on in the
code, the compiler is free to investigate such rearrangements at this
earlier point in the code. If it finds a rearrangement that it prefers
over the original code, it is permitted to use it.

This is true even if the compiler is compiling for a platform where
calculating p-1 would abort the program if p happens to point at the
beginning of a memory segment. The original version of the code is
carefully written to avoid that problem, but because of the later use of
'p--', the compiler is allowed to rearrange it on the assumption that
p-1 has defined behavior. If p-1 and p+3 both have defined behavior,
then the behavior of (p+3)-1 and (p-1)+3 are both guaranteed to be
identical to p+2.

This is an example of why it's a mistake to assume that the consequences
of writing a code construct with undefined behavior are restricted to
the execution of that particular code construct. This is why the
standard standard specifies that it is the behavior of your ENTIRE
program that is undefined, not just the behavior of the particular
construct that makes it undefined.

And yes, this is a "real world" issue; modern compiler technology does
include the ability to perform optimizations at locations in the code
that are far away from the site of the code construct that gives them
permission to perform the optimization.

[Chris Dollin]

vi******@gmail.com wrote:

On Sep 23, 11:19 am, Nick Keighley <[e-mail]>
wrote:

>On 23 Sep, 05:51, CBFalconer <[e-mail]:

"[e-mail]" wrote:

The reverse function quits if this is the case.

Not mine, which was posted earlier. It also considers a NULL
passed in as indicating an empty string, and returns 0 (for input
length).

which I consider a bug

Depends on the documentation. Do you consider it a bug if strlen(NULL)
returns 0?
I'd just document that NULL shouldn't be passed to such function; what
it does after that is not important. (ie returning 0 or dereferencing
a null pointer)

Or exploding.

--
'It changed the future .. and it changed us.' /Babylon 5/

Hewlett-Packard Limited registered office: Cain Road, Bracknell,
registered no: 690597 England Berks RG12 1HN

[James Kuyper]

CBFalconer wrote:

Ben Bacarisse wrote:

>"[e-mail]" <lo***************@gmail.comwrites:

... snip ...

>>My version

char *reverse(char *p) {
char *p1, *p2, ch;

for (p1 = p; *(p1 + 1); p1++) ;

If p points to an empty string this, too, is probably UB. It may
not be -- one would have to see the call, but you should not even
risk this. A call like: char test[10]; test[0] = 0; reverse(test);
is bad news!

I think that is OK. The above for does nothing except set p1 == p.

No, it dereferences p+1. If p points at an empty string "", then p+1
points one past the end of the array, and the behavior of dereferencing
p+1 is undefined. Furthermore, if p points at "\0Hello, world!", the
loop given above will leave p1 pointing at the '!', which is not where
it should be pointing.

[Richard Heathfield]

Nick Keighley said:

On 23 Sep, 07:40, Richard<[e-mail]:

<snip>

>I do however
slag off ridiculous bullying and silly preening with such claims as "I
dont need a debugger and neither do you" or "your debugger uses numbers
for pointers? Really"? etc etc etc . It makes this group a very tense
and strange place to be at times.

well you don't exactly help

Well, it doesn't exactly matter, since nobody with any sense pays the
slightest attention to what he says. The above paragraph is so exaggerated
that it would not be unreasonable to accuse him of lying. The "bullying"
claims are just ludicrous, and he's far more sinning than sinned against
in this respect. As for debuggers, I don't recall *anyone* saying that
they don't need a debugger, and I certainly don't recall anyone saying
that "you" (FWVO "you") don't need a debugger either. And the reason I
don't recall anyone saying these things is extraordinarily likely to be
because nobody did.

If he wants to talk to grownups, he's going to have to learn to treat them
like grownups, and to behave like a grownup - which, among other things,
means learning to understand and respect the opinions of others, even
though one might disagree with them.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[pete]

CBFalconer wrote:

Ben Bacarisse wrote:

>"[e-mail]" <lo***************@gmail.comwrites:

... snip ...

>>My version

char *reverse(char *p) {
char *p1, *p2, ch;

for (p1 = p; *(p1 + 1); p1++) ;

If p points to an empty string this, too, is probably UB. It may
not be -- one would have to see the call, but you should not even
risk this. A call like: char test[10]; test[0] = 0; reverse(test);
is bad news!

I think that is OK. The above for does nothing except set p1 == p.

If p points to a null byte
which is also the last byte of an object,
then *(p1 + 1) is undefined.

--
pete

[pete]

Peter Nilsson wrote:

Richard<[e-mail]:

>>>>>An

>>>>>object pointer

>>>>> can have only 4 different kinds of
>values:
>1 Address of an object
>2 One more than the address of an object
>3 null pointer value
>4 indeterminate value

5 Address of a function

Not an object pointer.

--
pete

[Ben Bacarisse]

Richard Heathfield <rj*@see.sig.invalidwrites:

Nick Keighley said:

>On 23 Sep, 07:40, Richard<[e-mail]:

<snip>

>>I do however
slag off ridiculous bullying and silly preening with such claims as "I
dont need a debugger and neither do you" or "your debugger uses numbers
for pointers? Really"? etc etc etc . It makes this group a very tense
and strange place to be at times.

well you don't exactly help

Well, it doesn't exactly matter, since nobody with any sense pays the
slightest attention to what he says.

For the moment (unless you correct me) I'll assume that did not intend
to imply that I (and a few others) don't have any sense. Maybe
reading his posts and correcting as yet uncorrected technical errors
falls somehow below the radar of paying "the slightest attention", or
maybe it was slip of the fingers.

--
Ben.

[Ben Bacarisse]

CBFalconer <cb********@yahoo.comwrites:

"[e-mail]" wrote:

>>

... snip ...

>>
My version

char *reverse(char *p) {
char *p1, *p2, ch;

for (p1 = p; *(p1 + 1); p1++) ;
for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}

Much better.

Odd definition of "better". You don't mind the undefined behaviour then?

--
Ben.

[Ben Bacarisse]

Ben Bacarisse <be********@bsb.me.ukwrites:

CBFalconer <cb********@yahoo.comwrites:

>"[e-mail]" wrote:

>>>

... snip ...

>>>
My version

char *reverse(char *p) {
char *p1, *p2, ch;

for (p1 = p; *(p1 + 1); p1++) ;
for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}

Much better.

Odd definition of "better". You don't mind the undefined behaviour
then?

I should have read the thread to the end (I usually do) since after
pete and James's comments I am sure you understand the UB, but there
is another way it can show up:

char string[100];
string[0] = 0;
reverse(string);

There is no guarantee that *(p1 + 1) is not, in fact, non-zero for all
the remaining 99 characters if the string. The loop will run off the
end.

--
Ben.

[Richard Heathfield]

Ben Bacarisse said:

Richard Heathfield <rj*@see.sig.invalidwrites:

>Well, it doesn't exactly matter, since nobody with any sense pays the
slightest attention to what he says.

For the moment (unless you correct me) I'll assume that did not intend
to imply that I (and a few others) don't have any sense.

Despite his wisdom, even a wise man can do unwise things.

And it just occurred to me, after having written that sentence, that it
actually cuts both ways. I'll leave you to guess which way I intended it
to cut. :-)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Richard]

Ben Bacarisse <be********@bsb.me.ukwrites:

Ben Bacarisse <be********@bsb.me.ukwrites:

>CBFalconer <cb********@yahoo.comwrites:

>>"[e-mail]" wrote:

... snip ...

My version

char *reverse(char *p) {
char *p1, *p2, ch;

for (p1 = p; *(p1 + 1); p1++) ;
for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}

Much better.

Odd definition of "better". You don't mind the undefined behaviour
then?

I should have read the thread to the end (I usually do) since after
pete and James's comments I am sure you understand the UB, but there
is another way it can show up:

char string[100];
string[0] = 0;
reverse(string);

There is no guarantee that *(p1 + 1) is not, in fact, non-zero for all
the remaining 99 characters if the string. The loop will run off the
end.

I'm surprised this condition raised its head again in the same
thread. Not so much about what is hiding at *p+1 but the case
of zero length strings in general.

I must admit to still being a bit shell shocked to find while(p-- s) can
cause undefined behaviour. I doubt there's anywhere it actually does
cause an issue but its interesting none the less.

[jameskuyper]

Richard wrote:
....

I must admit to still being a bit shell shocked to find while(p-- s) can
cause undefined behaviour. I doubt there's anywhere it actually does
cause an issue but its interesting none the less.

In another thread recently, at least one real machine was identified
by name as having the characteristic of aborting a program when an
invalid pointer was loaded into a pointer register (not just when the
pointer is dereferenced). p-- when p points to the beginning of a
array is just another way of creating a pointer that might trigger
such behavior. Machines with that characteristic may be rare, but I
would hope by now that you're at least willing to concede that they
exist.

[lovecreatesbea...]

On Sep 23, 10:11*am, Ben Bacarisse <[e-mail]:

"[e-mail]" <[e-mail]:

char *reverse(char *p)
{
* * * * char *p1, *p2, ch;

* * * * for (p1 = p; *(p1 + 1); p1++) ;

If p points to an empty string this, too, is probably UB. *It may not
be -- one would have to see the call, but you should not even risk
this. *A call like: char test[10]; test[0] = 0; reverse(test); is bad
news!

* * * * for (p2 = p; p2 < p1; p2++, p1--)
* * * * * * * * ch = *p2, *p2 = *p1, *p1 = ch;
* * * * return p;
}

Thank you very much. I correct it as follow:

char *reverse(char *p)
{
char *p1, *p2, ch;

for (p1 = p; *p1; p1++) ;
p1--;
for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}

[lovecreatesbea...]

On Sep 23, 12:55*pm, CBFalconer <[e-mail]:

"[e-mail]" wrote:

char *reverse(char *p) {
* * * * char *p1, *p2, ch;

* * * * for (p1 = p; *(p1 + 1); p1++) ;
* * * * for (p2 = p; p2 < p1; p2++, p1--)
* * * * * * * * ch = *p2, *p2 = *p1, *p1 = ch;
* * * * return p;
}

Much better. *It still doesn't handle a NULL input, and has the
error of returning the string pointer rather than the string
length. *Which is only an error in optimization, not coding.

Thanks for read. And I made another mistake. The object one step past
the the end of the array was dereferenced in my old code. I post a
revision and comments are welcome as usual.

[Keith Thompson]

Nick Keighley <ni******************@hotmail.comwrites:

On 23 Sep, 05:51, CBFalconer <[e-mail]:

>"[e-mail]" wrote:

pete <[e-mail]:

... snip ...

>It's undefined when attempting to reverse a zero length string.

How to reverse a zero length string for it has only a single
NULL terminating character : )

note: NULL is not a character. '\0' *is* a character.

Even though NULL may legally be #define'd as '\0', and even if it's
#define'd as 0 it has the same value and type as '\0'.

But yes, the point is that NULL is *intended* to be used as a pointer
value, not as a character value, and it *can* be defined in such a way
((void*)0) as to make the latter illegal.

[snip]

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Keith Thompson]

vi******@gmail.com writes:

On Sep 23, 11:19 am, Nick Keighley <[e-mail]>
wrote:

>On 23 Sep, 05:51, CBFalconer <[e-mail]:

"[e-mail]" wrote:

The reverse function quits if this is the case.

Not mine, which was posted earlier. It also considers a NULL
passed in as indicating an empty string, and returns 0 (for input
length).

which I consider a bug

Depends on the documentation. Do you consider it a bug if strlen(NULL)
returns 0?

Depends on what you mean by "bug".

Anything strlen(NULL) does is consistent with the standard's
requirements. But as a quality-of-implementation issue, it *should*
either be written for maximum efficiency for non-NULL arguments (which
typically means that strlen(NULL) will trap), or it should explicitly
check for NULL and abort (or possibly use some other system-specific
error reporting mechanism).

If I call strlen(NULL), that's a bug in my program. If the
implementation deliberately goes out of its way to hide that from me,
it's not being user-friendly, it's being programmer-hostile.

I'd just document that NULL shouldn't be passed to such function; what
it does after that is not important. (ie returning 0 or dereferencing
a null pointer)

In theory, you're right. In practice, returning 0 is unhelpful.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Keith Thompson]

Nick Keighley <ni******************@hotmail.comwrites:

On 22 Sep, 19:42, [e-mail] wrote:

>Hello, I'm a highly experienced expert C programmer and I've written
this code to reverse a string in place. I think you could all learn
something from it!

int reverse(char* reverseme){
* *int retval=-1;
* *if(retval!=NULL){
* * * int len=strlen(retval){
* * * if(len>0){
* * * * *int half=len>>1;
* * * * *for(;retval<half;retval++){
* * * * * * reverseme[retval]^=reverseme[len-(retval+1)];
* * * * * * reverseme[len-(retval+1)]=reverseme[retval];
* * * * * * reverseme[retval]^=reverseme[len-(retval+1)];

for newbies: don't do this. It is a very stupid way to swap two
integers.

The xor trick is a stupid way to swap two integers. But the quoted
code doesn't even get the xor trick right (and I suspect it's
deliberate).

>

>* * * * *}
* * * }
* *}
* *return retval;

}

missing }

Actually there's an extra '{', and a missing ';', on the declaration
of "len".

Newbies should disregard all the code posted by this person calling
himself "dominantubergeek". More experienced programmers might amuse
themselves by cataloging all the errors (I've seen worse, BTW), but I
think we've covered it suffiently here.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[lovecreatesbeauty]

On Sep 23, 11:23 pm, Keith Thompson <[e-mail]:

Nick Keighley <[e-mail]:

On 23 Sep, 05:51, CBFalconer <[e-mail]:

"[e-mail]" wrote:
pete <[e-mail]:

... snip ...

It's undefined when attempting to reverse a zero length string.

How to reverse a zero length string for it has only a single
NULL terminating character : )

note: NULL is not a character. '\0' *is* a character.

Even though NULL may legally be #define'd as '\0', and even if it's
#define'd as 0 it has the same value and type as '\0'.

But yes, the point is that NULL is *intended* to be used as a pointer
value, not as a character value, and it *can* be defined in such a way
((void*)0) as to make the latter illegal.

I'm sorry to use the all UPPER case word NULL there and bring the
confusion. But the "null character" doesn't have to refer to the macro
NULL :)

[Richard]

ja*********@verizon.net writes:

Richard wrote:
...

>I must admit to still being a bit shell shocked to find while(p-- s) can
cause undefined behaviour. I doubt there's anywhere it actually does
cause an issue but its interesting none the less.

In another thread recently, at least one real machine was identified
by name as having the characteristic of aborting a program when an
invalid pointer was loaded into a pointer register (not just when the
pointer is dereferenced). p-- when p points to the beginning of a
array is just another way of creating a pointer that might trigger
such behavior. Machines with that characteristic may be rare, but I
would hope by now that you're at least willing to concede that they
exist.

I'm willing to concede anything when its true and there is some proof.

See other post "UDB and...". I would value your comments.

[Keith Thompson]

Richard<rg****@gmail.comwrites:
[...]

I'm willing to concede anything when its true and there is some proof.

[...]

Not always. See the recent argument over incrementing an
uninitialized variable, in which you tried to refute the claim that
"it is not incremented" while refusing to acknowledge that nobody had
ever made such a claim.

If you're really interested in having constructive discussions here,
you need to be able to acknowledge when you've made a mistake. I'm
glad to see some willingness to try.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Kenny McCormack]

In article <ln************@nuthaus.mib.org>,
God's Representative on Earth <ks***@mib.orgproclaimed his pleasure thusly:
....

>If you're really interested in having constructive discussions here,
you need to be able to acknowledge when you've made a mistake. I'm
glad to see some willingness to try.

My irony meter is going bonkers.

[jameskuyper]

Richard wrote:

ja*********@verizon.net writes:

Richard wrote:
...

I must admit to still being a bit shell shocked to find while(p-- s) can
cause undefined behaviour. I doubt there's anywhere it actually does
cause an issue but its interesting none the less.

In another thread recently, at least one real machine was identified
by name as having the characteristic of aborting a program when an
invalid pointer was loaded into a pointer register (not just when the
pointer is dereferenced). p-- when p points to the beginning of a
array is just another way of creating a pointer that might trigger
such behavior. Machines with that characteristic may be rare, but I
would hope by now that you're at least willing to concede that they
exist.

I'm willing to concede anything when its true and there is some proof.

What would you accept as proof? Ben Bacarisse has already identified
the Cambridge CAP Machine as an machine that terminates a program upon
the loading of an invalid address into an address register. Do you
think he's lying? What do you require - detailed documentation of this
feature? The output from a program that failed for this reason? An in-
person demonstration of the failure?

[Richard]

ja*********@verizon.net writes:

Richard wrote:

>ja*********@verizon.net writes:

Richard wrote:
...
I must admit to still being a bit shell shocked to find while(p-- s) can
cause undefined behaviour. I doubt there's anywhere it actually does
cause an issue but its interesting none the less.

In another thread recently, at least one real machine was identified
by name as having the characteristic of aborting a program when an
invalid pointer was loaded into a pointer register (not just when the
pointer is dereferenced). p-- when p points to the beginning of a
array is just another way of creating a pointer that might trigger
such behavior. Machines with that characteristic may be rare, but I
would hope by now that you're at least willing to concede that they
exist.

I'm willing to concede anything when its true and there is some proof.

What would you accept as proof? Ben Bacarisse has already identified
the Cambridge CAP Machine as an machine that terminates a program upon
the loading of an invalid address into an address register. Do you

I did not see that before. What do you want from me? to accept
everything on face value? There has been many instances of regs being
wrong here. I can accept that too. God knows I'm no angle either.

think he's lying? What do you require - detailed documentation of this

No I do not think he is lying. What is it with this group and people so
ready to assume people are accusing other of "lying"?!?!?!

feature? The output from a program that failed for this reason? An in-
person demonstration of the failure?

No. Reasonable discourse and pointers to real life situations. Simple
enough.

[jameskuyper]

Richard wrote:

ja*********@verizon.net writes:

Richard wrote:

ja*********@verizon.net writes:

Richard wrote:
...
I must admit to still being a bit shell shocked to find while(p-- s) can
cause undefined behaviour. I doubt there's anywhere it actually does
cause an issue but its interesting none the less.

In another thread recently, at least one real machine was identified
by name as having the characteristic of aborting a program when an
invalid pointer was loaded into a pointer register (not just when the
pointer is dereferenced). p-- when p points to the beginning of a
array is just another way of creating a pointer that might trigger
such behavior. Machines with that characteristic may be rare, but I
would hope by now that you're at least willing to concede that they
exist.

I'm willing to concede anything when its true and there is some proof.

What would you accept as proof? Ben Bacarisse has already identified
the Cambridge CAP Machine as an machine that terminates a program upon
the loading of an invalid address into an address register. Do you

I did not see that before. What do you want from me? to accept
everything on face value?

No, I only ask that if, for instance, someone says (as Ben did on
another thread) that the Cambridge CAP machine has this
characteristic, that you would not go out of your way to contradict
him without at least first looking for and finding evidence that his
claim was wrong.

...There has been many instances of regs being
wrong here. I can accept that too. God knows I'm no angle either.

think he's lying? What do you require - detailed documentation of this

No I do not think he is lying. What is it with this group and people so
ready to assume people are accusing other of "lying"?!?!?!

I'm not accusing you of lying, nor am I accusing Ben of lying. You
responded to Ben's message on a different thread mentioning the CAP
machine, which left me with the impression that you had actually read
it. Then, in a later message on this thread you wrote " I doubt
there's anywhere it actually does actually cause an issue". To me, it
seems that possessing such a doubt, after having read Ben's message,
implies either that you also doubt Ben's veracity, or that you didn't
realize what he was saying. I'm now favoring the second possibility,
but it is not the first one that came to mind.

feature? The output from a program that failed for this reason? An in-
person demonstration of the failure?

No. Reasonable discourse and pointers to real life situations. Simple
enough.

We give your precisely those things, and you dismiss them as
"unreasonable" and "unreal", respectively. It's pretty hard to figure
out how to respond to that.

[dj3vande]

In article <61**********************************@m44g2000hsc. googlegroups.com>,
<ja*********@verizon.netwrote:

>Richard wrote:

>No. Reasonable discourse and pointers to real life situations. Simple
enough.

We give your precisely those things, and you dismiss them as
"unreasonable" and "unreal", respectively. It's pretty hard to figure
out how to respond to that.

Find a VAX^WPC^WLinux/x86^WLinux/x64 implementation that does it that
way, of course!
dave
(those are the only computers in the world, aren't they?)

--
Dave Vandervies dj3vande at eskimo dot com
Fortunately, the Exchange server is well protected from the big bad Internet
by proper mail servers run by some incredibly competent people.
--John Burnham in the scary devil monastery

[CBFalconer]

Richard wrote:

>

.... snip ...

>
Hold on - I still dont hold with the other version from cbf.
Frankly any prodding he gets is his own fault - he spends 90% of
his posts doing much the same. And I dont slag off correct code
either. I do however slag off ridiculous bullying and silly
preening with such claims as "I dont need a debugger and neither
do you" or "your debugger uses numbers for pointers? Really"?
etc etc etc . It makes this group a very tense and strange place
to be at times.

Good for you. Of course the fact that my code works, and that
yours doesn't, shouldn't affect that attitude.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[CBFalconer]

James Kuyper wrote:

CBFalconer wrote:

>Ben Bacarisse wrote:

>>"[e-mail]" <lo***************@gmail.comwrites:

... snip ...

>>>
My version

char *reverse(char *p) {
char *p1, *p2, ch;

for (p1 = p; *(p1 + 1); p1++) ;

If p points to an empty string this, too, is probably UB. It may
not be -- one would have to see the call, but you should not even
risk this. A call like: char test[10]; test[0] = 0; reverse(test);
is bad news!

I think that is OK. The above for does nothing except set p1 == p.

No, it dereferences p+1. If p points at an empty string "", then p+1
points one past the end of the array, and the behavior of dereferencing
p+1 is undefined. Furthermore, if p points at "\0Hello, world!", the
loop given above will leave p1 pointing at the '!', which is not where
it should be pointing.

Well done. I missed that.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[CBFalconer]

Nick Keighley wrote:

CBFalconer <[e-mail]:

.... snip ...

>

>and has the error of returning the string pointer rather than
the string length. Which is only an error in optimization, not
coding.

...is only an error of opinion

Well, I described why I have that opinion earlier (with a printf
example). Did you read that?

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[CBFalconer]

Ben Bacarisse wrote:

>

.... snip, avoiding requoting my mistake ...

>
I should have read the thread to the end (I usually do) since
after pete and James's comments I am sure you understand the UB,
but there is another way it can show up:

char string[100];
string[0] = 0;
reverse(string);

There is no guarantee that *(p1 + 1) is not, in fact, non-zero
for all the remaining 99 characters if the string. The loop
will run off the end.

Well, at least it won't affect anything I write, since I will use
my own routine. :-) Which just proves, once more, that eyeballing
source is not a positive debugger.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[CBFalconer]

Nick Keighley wrote:

CBFalconer <[e-mail]:

>"[e-mail]" wrote:

.... snip ...

>

>>The reverse function quits if this is the case.

Not mine, which was posted earlier. It also considers a NULL
passed in as indicating an empty string, and returns 0 (for
input length).

which I consider a bug

Why? If you want to detect that usage passing the 'reversed'
string to printf or fwrite will blow up quickly enough.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[CBFalconer]

arnuld wrote:

>CBFalconer wrote:

>This is so horrible and faulty that I have to attach the
following. Don't forget to #include <strings.h>. Note that it
returns strlen.

/* ======================= */
/* reverse string in place */
size_t revstring(char *stg)
{
char *last, temp;
size_t lgh;

lgh = strlen(stg);
if (lgh 1) {
last = stg + lgh; /* points to '\0' */
while (last-- stg) {
temp = *stg; *stg++ = *last; *last = temp;
}
}
return lgh;
} /* revstring */

I have edited it a little bit to get pointer to pointer as
function argument and combined it with my get_single_word
program and it works little strange though. Also, your function
is much easier to read IMHO:

.... snip ...

>
=================== OUTPUT =====================
[arnuld@dune ztest]$ gcc -ansi -pedantic -Wall -Wextra reverse-string.c
[arnuld@dune ztest]$ ./a.out
Ben
Reversed: [ neB ]
CBFalconer
Reversed: [ rBFalconeC ] <--** should be renoclaFBC here. Etc.
comp.kang.c++
Reversed: [ +omp.kang.c+c ]
[arnuld@dune ztest]$

Just looking at your output, your code is obviously failing to
reverse strings correctly.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[Ben Bacarisse]

"[e-mail]" <lo***************@gmail.comwrites:

On Sep 23, 10:11Â*am, Ben Bacarisse <[e-mail]:

>"[e-mail]" <[e-mail]:

char *reverse(char *p)
{
Â* Â* Â* Â* char *p1, *p2, ch;

Â* Â* Â* Â* for (p1 = p; *(p1 + 1); p1++) ;

If p points to an empty string this, too, is probably UB.

<snip>

Thank you very much. I correct it as follow:

char *reverse(char *p)
{
char *p1, *p2, ch;

for (p1 = p; *p1; p1++) ;
p1--;

Now you have gone back to the UB I thought you were trying to avoid.
If *p is zero, p1-- will be invalid

for (p2 = p; p2 < p1; p2++, p1--)

and can't be compared to p2.

ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}

--
Ben.

[Peter Nilsson]

pete <[e-mail]:

Peter Nilsson wrote:

>>>>An
object pointer
*can have only 4 different kinds of
values:
1 * *Address of an object
2 * *One more than the address of an object
3 * *null pointer value
4 * *indeterminate value

* * * *5 * *Address of a function

Not an object pointer.

Quite so. I was distracted in thinking about what other
pointer values there could be in general.

Would you consider a pointer to write-only memory (e.g.
memory mapped output) to be the address of an object,
an indeterminate value, or something else? Footnote
115 in N1256 suggests they are object pointers, though
that somewhat conflicts with the definition of object.

--
Peter

[blargg]

In article <t6**************@nwrddc02.gnilink.net>, James Kuyper
<ja*********@verizon.netwrote:

[...]

Yes, I know "undefined" can mean "anything", but lets stay real here for
a moment. Possibly "undefined" is "defined" to mean "undefined for that
variable in question".

Or?

Or, it means that the compiler is allowed to perform optimizations
elsewhere in your program, based upon the assumption that your code does
not have undefined behavior.

[snip example]

Here's a related example I've come up with, regarding multi-dimensional arrays.

char a [2] [3276] [10];
int i;

for ( i = 0; i < 2 * 3276; ++i )
a [0] [i] [0] = '\0';

This code invokes undefined behavior, since the sub-arrays only have 3276
elements each yet the loop accesses through element 6551. Sure, they are
contiguous, but the standard makes this undefined. Only fictional, you
say? On a platform where a 16x16->16 (signed) multiply is more efficient,
a compiler should calculate the address using such a multiply, since it
knows that 3276*10 won't overflow a 16-bit value. The M68K was one such
platform where 16-bit operations were often faster.

Or even simpler,

char a [2] [1];
int i;

for ( i = 0; i < 2; ++i )
a [0] [i] = '\0';

a compiler could ignore i as an index and just do a [0] [0] = '\0' in the
loop, since the index could never legally be anything but 0. Or following
James Kuyper's lead, the compiler could redefine the value 2 as being
equal to 1, by assuming that the [i] access was valid and working
backwards. :-)

[pete]

Peter Nilsson wrote:

Would you consider a pointer to write-only memory (e.g.
memory mapped output) to be the address of an object,
an indeterminate value, or something else? Footnote
115 in N1256 suggests they are object pointers, though
that somewhat conflicts with the definition of object.

The footnote says
"even if they are never actually
defined as objects in the program"

I think it would make most sense
to treat a pointer to write-only memory,
as the address of an object.

You can write to where it points, right?

--
pete

[lovecreatesbeauty]

On Sep 24, 5:50*am, Ben Bacarisse <[e-mail]:

"[e-mail]" <[e-mail]:

On Sep 23, 10:11*am, Ben Bacarisse <[e-mail]:

"[e-mail]" <[e-mail]:
char *reverse(char *p)
{
* * * * char *p1, *p2, ch;

* * * * for (p1 = p; *(p1 + 1); p1++) ;

If p points to an empty string this, too, is probably UB.

<snip>

Thank you very much. I correct it as follow:

char *reverse(char *p)
{
* * * * char *p1, *p2, ch;

* * * * for (p1 = p; *p1; p1++) ;
* * * * p1--;

Now you have gone back to the UB I thought you were trying to avoid.
If *p is zero, p1-- will be invalid

Ben, thank you very much.

* * * * for (p2 = p; p2 < p1; p2++, p1--)

and can't be compared to p2.

I don't understand this. Does my new version below avoid this problem?

* * * * * * * * ch = *p2, *p2 = *p1, *p1 = ch;
* * * * return p;
}

char *reverse(char *p)
{
char *p1, *p2, ch;

p1 = p;
if (!*p) return p;
while (*p1) p1++;
p1--;
for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define LEN 1024

int main(int argc, char *argv[])
{
char a[LEN] = {'\0'};

if (argv[1] && strlen(argv[1]) < LEN)
strncpy(a, argv[1], LEN - 1);
else {
printf("please provide at least one argument with
length of "
"less than %d chars
\n", LEN);
return EXIT_FAILURE;
}
printf("%s\n", reverse(a));
return EXIT_SUCCESS;
}

[Ben Bacarisse]

"lo***************@gmail.com" <lo***************@gmail.comwrites:

On Sep 24, 5:50Â*am, Ben Bacarisse <[e-mail]:

>"[e-mail]" <[e-mail]:

On Sep 23, 10:11Â*am, Ben Bacarisse <[e-mail]:
"[e-mail]" <[e-mail]:
char *reverse(char *p)
{
Â* Â* Â* Â* char *p1, *p2, ch;

Â* Â* Â* Â* for (p1 = p; *(p1 + 1); p1++) ;

>If p points to an empty string this, too, is probably UB.

<snip>

Thank you very much. I correct it as follow:

char *reverse(char *p)
{
Â* Â* Â* Â* char *p1, *p2, ch;

Â* Â* Â* Â* for (p1 = p; *p1; p1++) ;
Â* Â* Â* Â* p1--;

Now you have gone back to the UB I thought you were trying to avoid.
If *p is zero, p1-- will be invalid

Ben, thank you very much.

Â* Â* Â* Â* for (p2 = p; p2 < p1; p2++, p1--)

and can't be compared to p2.

I don't understand this.

There are two problems with a pointer that points "before" the first
element of an array (I have to put "before" in quotes because since
the pointer is ill-formed it is not possible to say where it really
points). The first is that the pointer value might trap. The second
is that you are not permitted to compare it with other pointers -- or
to be more accurate, the comparison is undefined.

Is is worth saying that, because the behaviour is undefined, an
implementation is free to permit both and to give pointers a meaning.
Reversing a string can be done without having to any such extension to
standard C -- hence so much fuss about it here.

Does my new version below avoid this problem?

Yes. There is an implied contract -- that a string be passed -- and
provided that is that case then the code is properly defined.

char *reverse(char *p)
{
char *p1, *p2, ch;

p1 = p;
if (!*p) return p;
while (*p1) p1++;
p1--;
for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}

--
Ben.

[Pilcrow]

On Mon, 22 Sep 2008 21:03:00 -0400, CBFalconer <cb********@yahoo.com>
wrote:

>Ben Bacarisse wrote:

>Richard<rg****@gmail.comwrites:

<snip>

>>Much nicer IMO:

#include <string.h>

char * my_strrev(char *s){
char t;
char *e = s+strlen(s)-1;
while(e>s){
t = *s;
*s++ = *e;
*e-- = t;
}
}

I'm sure it breaks some sort of ISO magic,

Not "magic" but it has undefined behaviour on empty strings.

It also has the fatal error (to me) of returning a char*. This
encourages the silly mistake of trying to print a string and its
reverse with:

printf("%s & %s\n", s, strrev(s));

In fact it is even worse than that - it fails to return the
declared object. My version returns strlen, which it needs to
evaluate to find the end of the string, and thus avoids the caller
needing to call it again. Also note that my code returns a NULL if
the passed string is NULL, and correctly handles strings of length
0 and 1.

You are distinguishing between strings of length 0 and NULL strings.
How does one pass a NULL string?

[Richard Heathfield]

Pilcrow said:

On Mon, 22 Sep 2008 21:03:00 -0400, CBFalconer <cb********@yahoo.com>
wrote:

<snip>

>>
In fact it is even worse than that - it fails to return the
declared object. My version returns strlen, which it needs to
evaluate to find the end of the string, and thus avoids the caller
needing to call it again. Also note that my code returns a NULL if
the passed string is NULL, and correctly handles strings of length
0 and 1.

You are distinguishing between strings of length 0 and NULL strings.

NULL isn't a string, and Chuck was incorrect to suggest that it was,
although in this case I think it was just careless typing - he probably
meant to say "value", not "string", in "the passed string is NULL".

How does one pass a NULL string?

One doesn't. But it's easy enough to pass a null pointer value /instead of/
a string.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Nick Keighley]

On 23 Sep, 18:41, Richard<[e-mail]:

God knows I'm no angle either.

you can be a bit obtuse though

:-)

--
Nick Keighley

[Nick Keighley]

On 23 Sep, 16:28, Keith Thompson <[e-mail]:

[e-mail] writes:

On Sep 23, 11:19 am,Nick Keighley<[e-mail]>
wrote:

On 23 Sep, 05:51, CBFalconer <[e-mail]:
"[e-mail]" wrote:

The reverse function quits if this is the case.

Not mine, which was posted earlier. *It also considers a NULL
passed in as indicating an empty string, and returns 0 (for input
length).

which I consider a bug

Depends on the documentation.

Bug: an instance of program behaviour that is not in the user's
reasonable expectation.

I think it's a bad idea to encourage users to expect defined
behaviour when a functions reasonable pre-condictions are
violated. reverse() operates on strings. NULL is not a string.
reverse(NULL) shouldn't have definend behaviour. This only
encourages people to rely on the behaviour.

Do you consider it a bug if strlen(NULL) returns 0?

There is no defined behaviour so I don't think
anyone should write code that relies on strlen(NULL)
doing anything in particular.

Depends on what you mean by "bug".

Anything strlen(NULL) does is consistent with the standard's
requirements. *But as a quality-of-implementation issue, it *should*
either be written for maximum efficiency for non-NULL arguments (which
typically means that strlen(NULL) will trap),

but may not on a system without memory protection

or it should explicitly
check for NULL and abort (or possibly use some other system-specific
error reporting mechanism).

If I call strlen(NULL), that's a bug in my program.

yes

>*If the
implementation deliberately goes out of its way to hide that from me,
it's not being user-friendly, it's being programmer-hostile.

yes. But on a non-memory protected system it may be expensive
to detect.

I'd just document that NULL shouldn't be passed to such function; what
it does after that is not important. (ie returning 0 or dereferencing
a null pointer)

and it could then return the length of the string it finds
at address zero.

In theory, you're right. *In practice, returning 0 is unhelpful.

yes. And I think reverse(NULL) is equally odd
--
Nick Keighley

[Malcolm McLean]

"Ben Bacarisse" <be********@bsb.me.ukwrote in message

There are two problems with a pointer that points "before" the first
element of an array (I have to put "before" in quotes because since
the pointer is ill-formed it is not possible to say where it really
points). The first is that the pointer value might trap. The second
is that you are not permitted to compare it with other pointers -- or
to be more accurate, the comparison is undefined.

Consider this one.

void reverse(char *str)
{
char temp;
int start = 0;
int end = strlen(str) - 1;
while(start < end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}

Of course strlen() returns a size_t. So we'll replace those ints with
size_t's. What horrible thing have I now done to this function?

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Richard Heathfield]

Malcolm McLean said:

<snip>

Consider this one.

void reverse(char *str)
{
char temp;
int start = 0;
int end = strlen(str) - 1;
while(start < end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}

Of course strlen() returns a size_t. So we'll replace those ints with
size_t's. What horrible thing have I now done to this function?

Revealed that it was badly written in the first place?

#include <string.h>
/* pre-condition: str != NULL - feel free to add a check */
void reverse(char *str)
{
char temp;
size_t start = 0;
size_t end = strlen(str);
while(end-- start)
{
temp = str[start];
str[start] = str[end];
str[start++] = temp;
}
}

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Ben Bacarisse]

"Malcolm McLean" <re*******@btinternet.comwrites:

"Ben Bacarisse" <be********@bsb.me.ukwrote in message

>There are two problems with a pointer that points "before" the first
element of an array (I have to put "before" in quotes because since
the pointer is ill-formed it is not possible to say where it really
points). The first is that the pointer value might trap. The second
is that you are not permitted to compare it with other pointers -- or
to be more accurate, the comparison is undefined.

Consider this one.

void reverse(char *str)
{
char temp;
int start = 0;
int end = strlen(str) - 1;
while(start < end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}

Of course strlen() returns a size_t. So we'll replace those ints with
size_t's. What horrible thing have I now done to this function?

I don't get your point. You know the above is wrong and that
switching to size_ t does not make it right, so what are you driving
at?

--
Ben.

[Bartc]

"Ben Bacarisse" <be********@bsb.me.ukwrote in message
news:87************@bsb.me.uk...

"Malcolm McLean" <re*******@btinternet.comwrites:

>"Ben Bacarisse" <be********@bsb.me.ukwrote in message

>>There are two problems with a pointer that points "before" the first
element of an array (I have to put "before" in quotes because since
the pointer is ill-formed it is not possible to say where it really
points). The first is that the pointer value might trap. The second
is that you are not permitted to compare it with other pointers -- or
to be more accurate, the comparison is undefined.

Consider this one.

void reverse(char *str)
{
char temp;
int start = 0;
int end = strlen(str) - 1;
while(start < end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}

Of course strlen() returns a size_t. So we'll replace those ints with
size_t's. What horrible thing have I now done to this function?

I don't get your point. You know the above is wrong and that
switching to size_ t does not make it right, so what are you driving
at?

What's wrong about it? It works fine, provided str points to a valid string.

--
Bartc

[oksid]

Bartc wrote:

>
"Ben Bacarisse" <be********@bsb.me.ukwrote in message
news:87************@bsb.me.uk...

>"Malcolm McLean" <re*******@btinternet.comwrites:

>>"Ben Bacarisse" <be********@bsb.me.ukwrote in message
void reverse(char *str)
{
char temp;
int start = 0;
int end = strlen(str) - 1;
while(start < end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}

Of course strlen() returns a size_t. So we'll replace those ints with
size_t's. What horrible thing have I now done to this function?

I don't get your point. You know the above is wrong and that
switching to size_ t does not make it right, so what are you driving
at?

What's wrong about it? It works fine, provided str points to a valid
string.

If "str" points to an empty string "strlen()" will return 0...
"end" will be equal to -1 or 0xFFFFFFFF