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

 

[Martin Ambuhl]

Hello, I'm a highly experienced expert C programmer

No, you are not.

and I've written
this code to reverse a string in place. I think you could all learn
something from it!

I doubt it. You should rethink it. It is not, as you subject line
claims "highly efficient".

 

[Lew Pitcher]

Hello, I'm a highly experienced expert C programmer

Apparently, you are
a) egotistical, and
b) wrong

and I've written
this code to reverse a string in place.

I am /so/ sorry, both for you and your employer.

I think you could all learn
something from it!

I'm sure that you are right. After all, /I/ learned that you are much less
than the C programmer that you claim to be.

int reverse(char* reverseme){
int retval=-1;
if(retval!=NULL)

Useless test, as retval was initialized (and never altered) to a value
that will not equate to NULL

{
int len=strlen(retval)

First real failure. retval is an integer, and the argument to
strlen() is a pointer-to-char. You can't get a valid result from
taking the "string length" of an integer.

Second failure: you did not #include the header that declares the
strlen() function. Thus, your compiler did not flag the above
assignment as an error (argument of incompatable type)

{
if(len>0)

So, what is the "string length" of an integer? And when would it be
greater than zero?

{
int half=len>>1;

Style hack: To be clearer to the intent of what sort of number
half represents, you should have coded this as
int half = len / 2;
Of course, since len is a nonsense value, half will also be a
nonsense value.

for(;retval<half;retval++){
reverseme[retval]^=reverseme[len-(retval+1)];

Undefined behaviour on first iteration, when retval == -1
reverseme[-1] is out of bounds.

reverseme[len-(retval+1)]=reverseme[retval];

Undefined behaviour on first iteration - same reason

reverseme[retval]^=reverseme[len-(retval+1)];

Undefined behaviour on first iteration - same reason

Plus, you've screwed up the "xor trick", and wiped out /both/
ends of the string with invalid values.

The head end now contains an array of 0x00 (up to
the ill-computed "midpoint"), while the tail end contains the
results of the head end xor the tail end.

}
}
}
return retval;

Of what use is this return value?

}

-Phil/CERisE

--
Lew Pitcher

Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------

 

[Default User]

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!

You should learn some better trolling techniques. I suggest studying
under Bill Cunningham.




Brian

 

[Flash Gordon]

Lew Pitcher wrote, On 22/09/08 20:06:

Apparently, you are
a) egotistical, and
b) wrong

Agreed. Although you missed some of the problems...

I am /so/ sorry, both for you and your employer.

You think s/he is employed?

I'm sure that you are right. After all, /I/ learned that you are much less
than the C programmer that you claim to be.


Useless test, as retval was initialized (and never altered) to a value
that will not equate to NULL

<snip load more broken code>

You forgot to mention that as retval is an int it won't actually compile
on all implementations.

I think it was a troll. However, it was amusing for how bad the code
was. I wonder how many other errors it has that have been missed?

 

[Keith Thompson]

On September 22, 2008 14:42, in comp.lang.c, (e-mail address removed)
([email protected]) wrote: [...]

int retval=-1;
if(retval!=NULL)

Useless test, as retval was initialized (and never altered) to a value
that will not equate to NULL

[...]

It's not just useless. retval is an int; NULL expands to a null
pointer constant. If NULL happens to be #defined as 0, the test is
merely useless; if it's #defined as ((void*)0) or something similar,
the test is a constraint violation.

 

[Keith Thompson]

I think it was a troll. However, it was amusing for how bad the code
was. I wonder how many other errors it has that have been missed?

I don't think anybody has mentioned the syntax error yet.
int len=strlen(retval){
should be
int len=strlen(retval);

I'd call it a comedy of errors, but that would require it to be funny.

 

[dj3vande]

Apparently, you are
a) egotistical, and
b) wrong


I am /so/ sorry, both for you and your employer.


I'm sure that you are right. After all, /I/ learned that you are much less
than the C programmer that you claim to be.

Since the subject has come up, here's one I've been waiting for an
excuse to post:
--------
typedef struct l{char a;struct l*b;}l;
static void x(char*a,l*b) {if(b){(-1)[a]=b->a;x(--a,b->b);}}
static void y(char*a,l*b,l*c) {if(b){l*d=b->b;b->b=c;y(a,d,b);}else{x(a,c);}}
static void z(char*a,l*b) {if(*a){l c;c.a=*a;c.b=b;z(a+1,&c);}else{y(a,b,0);}}
void reverse(char *s) { z(s,0); }
--------
Unlike the one that started the thread, this has actually been tested
and verified to work.

It also uses advanced implementation techniques that allow programs
with certain properties (especially in languages with properties that
make those program properties easy to detect and exploit) to be
compiled to highly efficient code.

Somebody who spends enough time untangling it might even learn
something useful from it (for sufficiently, but not comically, loose
values of "useful").


dave
(bonus points if you can figure out where the idea to do it that way came from)

 

[Jens Stueckelberger]

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!

Boy, that last sure is going to endear you to people here!

 

[Richard]

Boy, that last sure is going to endear you to people here!

Suggesting people show new programmers pointers at work in a debugger
endears you to some of the dustier c.l.c dweller ... :-;

 

[Bartc]

Since the subject has come up, here's one I've been waiting for an
excuse to post:
--------
typedef struct l{char a;struct l*b;}l;
static void x(char*a,l*b) {if(b){(-1)[a]=b->a;x(--a,b->b);}}
static void y(char*a,l*b,l*c)
{if(b){l*d=b->b;b->b=c;y(a,d,b);}else{x(a,c);}}
static void z(char*a,l*b) {if(*a){l
c;c.a=*a;c.b=b;z(a+1,&c);}else{y(a,b,0);}}
void reverse(char *s) { z(s,0); }
--------
Unlike the one that started the thread, this has actually been tested
and verified to work.

It also uses advanced implementation techniques that allow programs
with certain properties (especially in languages with properties that
make those program properties easy to detect and exploit) to be
compiled to highly efficient code.

Somebody who spends enough time untangling it might even learn
something useful from it (for sufficiently, but not comically, loose
values of "useful").

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.

void myreverse(char *s) {
int i,j;
char c;

if (s==NULL) return;

j=strlen(s)-1;
i=0;

while (i<j) {
c=s;
s=s[j];
s[j]=c;
++i;
--j;
}

}

 

[CBFalconer]

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;
}

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 */

 

[dj3vande]

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.

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.


dave
(specifically NOT claiming that "nifty" implies "useful in production code".)

 

[Richard]

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;
}

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 */

You know I really had to look hard at this to understand it. Horrible
variables names almost purposely made "no standard" as far as C around
the world goes for such a function. Unnecessary length
check. Unnecessary size_t. Multiple assignments on one line
making perusal with a debugger almost impossible.

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, but it seems more concise and
readable to me. No I didnt test it, but I guess the idea should be self
evident.

 

[Ben Bacarisse]

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

I'd include <string.h> instead. I haven't seen strings.h for decades.

 

[Ben Bacarisse]

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.

 

[Richard]

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


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.

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;
}
}

int main() {
char s1[]="hello";
my_strrev(s1);
printf("%s\n",s1);
char s2[]="";
my_strrev(s2);
printf("%s\n",s2);
char s3[]="c.l.c";
my_strrev(s3);
printf("%s\n",s3);
}

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?

 

[Richard]

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

Yes, I acknowledged that in my reply to Ben. Careless of me.

 

[Richard]

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]

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.