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

[Richard]

Jens Stueckelberger <JS************ *@nowhere.orgwr ites:

On Mon, 22 Sep 2008 11:42:37 -0700, dominantubergee k 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!

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]

<dj******@csclu b.uwaterloo.ca. invalidwrote in message
news:gb******** **@rumours.uwat erloo.ca...

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[i];
s[i]=s[j];
s[j]=c;
++i;
--j;
}

}

--
Bartc

[CBFalconer]

do************* *@ymail.com 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(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;
}

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

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

[dj3vande]

In article <9D************ ******@text.new s.virginmedia.c om>,
Bartc <[e-mail] rote:

>
<dj******@cscl ub.uwaterloo.ca .invalidwrote in message
news:gb******* ***@rumours.uwa terloo.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.

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".)

--
Dave Vandervies dj3vande at eskimo dot com

None of my copies of K&R have a "screen". Should I apply for a refund?
--Chris Dollin in comp.lang.c

[Richard]

CBFalconer <cb********@yah oo.comwrites:

do************* *@ymail.com 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(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;
}

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]

CBFalconer <cb********@yah oo.comwrites:
<snip code>

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

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

--
Ben.

[Ben Bacarisse]

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.

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.

--
Ben.

[Richard]

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

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.

>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.

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",s 1);
char s2[]="";
my_strrev(s2);
printf("%s\n",s 2);
char s3[]="c.l.c";
my_strrev(s3);
printf("%s\n",s 3);
}

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?

[pete]

Richard wrote:

#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.

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

--
pete

[Richard]

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

Richard wrote:

>#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.

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

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