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(retv al){
if(len>0){
int half=len>>1;
for(;retval<hal f;retval++){
reverseme[retval]^=reverseme[len-(retval+1)];
reverseme[len-(retval+1)]=reverseme[retval];
reverseme[retval]^=reverseme[len-(retval+1)];
}
}
}
return retval;
}

-Phil/CERisE

[pete]

Richard wrote:

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

Is that now defined? or, after a 14 hour day, am I talking rubbish here?

Can e not be decremented to a value "smaller" than s?

That operation would be undefined.

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

--
pete

[Richard]

pete <pf*****@mindsp ring.comwrites:

Richard wrote:

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

>Is that now defined? or, after a 14 hour day, am I talking rubbish here?

Can e not be decremented to a value "smaller" than s?

That operation would be undefined.

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

So whats an indeterminate value in this case?

Since the "--" is done after the compare is this still "undefined
behaviour"?

[Richard]

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

pete <pf*****@mindsp ring.comwrites:

>Richard wrote:

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

>>Is that now defined? or, after a 14 hour day, am I talking rubbish here?

Can e not be decremented to a value "smaller" than s?

That operation would be undefined.

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

So whats an indeterminate value in this case?

Since the "--" is done after the compare is this still "undefined
behaviour"?

or to make my question more clear - does this mean the entire program is
"undefined" ?

I must admit I would need to revisit some code (should I ever think it
will be compiled on a system where this really will not work) if that
"--" causes my frying pan to catch fire.

[pete]

Richard wrote:

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

>pete <pf*****@mindsp ring.comwrites:

>>Richard wrote:

char * my_strrev(char *s){
char t;
char *e = s+strlen(s);
while(e-->s){
Is that now defined? or, after a 14 hour day, am I talking rubbish here?

Can e not be decremented to a value "smaller" than s?
That operation would be undefined.

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

So whats an indeterminate value in this case?

Since the "--" is done after the compare is this still "undefined
behaviour"?

Yes.

or to make my question more clear - does this mean the entire program is
"undefined" ?

Yes.

There is a special rule that allows
the calculation of the "one past" pointer value.

--
pete

[Richard]

pete <pf*****@mindsp ring.comwrites:

Richard wrote:

>Richard<rg**** @gmail.comwrite s:

>>pete <pf*****@mindsp ring.comwrites:

Richard wrote:

char * my_strrev(char *s){
char t;
char *e = s+strlen(s);
while(e-->s){
Is that now defined? or, after a 14 hour day, am I talking rubbish here?
>
Can e not be decremented to a value "smaller" than s?
That operation would be undefined.

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
So whats an indeterminate value in this case?

Since the "--" is done after the compare is this still "undefined
behaviour"?

Yes.

>or to make my question more clear - does this mean the entire program is
"undefined" ?

Yes.

There is a special rule that allows
the calculation of the "one past" pointer value.

Which is?

[Richard]

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

pete <pf*****@mindsp ring.comwrites:

>Richard wrote:

>>Richard<rg*** *@gmail.comwrit es:

pete <pf*****@mindsp ring.comwrites:

Richard wrote:
>
>char * my_strrev(char *s){
> char t;
> char *e = s+strlen(s);
> while(e-->s){
>Is that now defined? or, after a 14 hour day, am I talking rubbish here?
>>
>Can e not be decremented to a value "smaller" than s?
That operation would be undefined.
>
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
So whats an indeterminate value in this case?

Since the "--" is done after the compare is this still "undefined
behaviour" ?

Yes.

>>or to make my question more clear - does this mean the entire program is
"undefined" ?

Yes.

There is a special rule that allows
the calculation of the "one past" pointer value.

Which is?

And which now makes me ask if this is UDB too:

unsigned int i=0;
while(i--){
}

While I would not normally do such things I know they exist all over the
place. Keeping in mind that the -- value is never actually used.

[Keith Thompson]

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

pete <pf*****@mindsp ring.comwrites:

[...]

>There is a special rule that allows
the calculation of the "one past" pointer value.

Which is?

Described in detail in C99 6.5.6p8.

Given:

int arr[5];
int *ptr = &arr[0];

ptr+0 is the address of the first element of the array.
ptr+4 is the address of the last element of the array.
ptr+5 points just past the last element. This address may legally be
computed, compared, etc., but it cannot be dereferenced (more
precisely, attempting to dereference it invokes UB).

Attempting to compute ptr+N, for N outside the range 0..5, invokes
undefined behavior, whether you subsequently attempt to dereference
the resulting pointer value or not.

--
Keith Thompson (The_Other_Keit h) 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]

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

And which now makes me ask if this is UDB too:

(UDB meaning Undefined Behavior; the more common abbreviation around
here is UB.)

unsigned int i=0;
while(i--){
}

While I would not normally do such things I know they exist all over the
place. Keeping in mind that the -- value is never actually used.

No, why would you think the behavior might be undefined? Decrementing
an unsigned object with the value 0 simply sets it to UINT_MAX.

--
Keith Thompson (The_Other_Keit h) 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"

[Ben Bacarisse]

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

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

>Richard<rg**** @gmail.comwrite s:
<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.

>>but it seems more concise and
readable to me. No I didnt test it, but I guess the idea should be self
evident.

Testing it would not reveal the issue.

Why wouldn't it? (and I acknowledge the correction btw).

Had I run this through a debugger with s as an empty string (I must
admit I had assumed s had to be non null and a non empty string but fair
enough point you raise) I would spot it in about 1 second when e is
calculated.

I don't see how, but maybe your debugger is clever. If you take the
view that a pointer is a number (it's not but you have suggested that
simplification here recently) e will be an address one less that s,
the while won't trigger and nothing will (correctly) be done. How can
testing show that such an e is invalid and can't even be constructed
let alone compared to s?

But correction (still no null check):
#include <stdio.h>
#include <string.h>

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

<snip>

Is that now defined? or, after a 14 hour day, am I talking rubbish here?

Can e not be decremented to a value "smaller" than s?

It can't be and your code still does so. You could write:

char *end = str + strlen(str);
while (end str) {
char tmp = *str;
*str++ = *--end;
*end = tmp;
}

although this swaps characters that don't need to be swapped. I think
CBFalconer's test against length being 1 is a good one:

size_t length = strlen(str);
if (length 1) {
char *end = str + length;
while (--end str) {
char tmp = *str;
*str++ = *end;
*end = tmp;
}
}

I've put declarations where I prefer and used my own pet names but it
is essentially the same code.

--
Ben.

[Richard]

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

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

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

>>Richard<rg*** *@gmail.comwrit es:
<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.

but it seems more concise and
readable to me. No I didnt test it, but I guess the idea should be self
evident.

Testing it would not reveal the issue.

Why wouldn't it? (and I acknowledge the correction btw).

Had I run this through a debugger with s as an empty string (I must
admit I had assumed s had to be non null and a non empty string but fair
enough point you raise) I would spot it in about 1 second when e is
calculated.

I don't see how, but maybe your debugger is clever. If you take the
view that a pointer is a number (it's not but you have suggested that
simplification here recently) e will be an address one less that s,

I pointed out that on every single system I have used (and this is one)
a pointer is indeed represented as a number of sorts in the
debugger.

In addition, since the pointers are char * the default is also to
display the strings they point to.

What I would have noticed in the debugger was that e was initialised to
something less than s in the case of empty strings. I also posted the
caveat that I (foolishly) did not consider empty strings and this was
indeed an error on my part. This I would have considered an error
despite me being far more liberal on UDB than many here and that being
something I know I can improve on.

the while won't trigger and nothing will (correctly) be done. How can
testing show that such an e is invalid and can't even be constructed
let alone compared to s?

>But correction (still no null check):
#include <stdio.h>
#include <string.h>

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

<snip>

>Is that now defined? or, after a 14 hour day, am I talking rubbish here?

Can e not be decremented to a value "smaller" than s?

It can't be and your code still does so. You could write:

char *end = str + strlen(str);
while (end str) {
char tmp = *str;
*str++ = *--end;
*end = tmp;
}

I think I did this in another reply. But did the "--" in the while.

I like the code above.

>
although this swaps characters that don't need to be swapped. I think
CBFalconer's test against length being 1 is a good one:

Personally I still dont see the point : the code above is concise.

>
size_t length = strlen(str);
if (length 1) {
char *end = str + length;
while (--end str) {
char tmp = *str;
*str++ = *end;
*end = tmp;
}
}

I've put declarations where I prefer and used my own pet names but it
is essentially the same code.