Highly efficient string reversal code

[Ben Bacarisse]

Re: Highly efficient string reversal code

CBFalconer <cbfalconer@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]

Re: Highly efficient string reversal code

Richard<rgrdev@ 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]

Re: Highly efficient string reversal code

Ben Bacarisse <ben.usenet@bsb .me.ukwrites:

Richard<rgrdev@ 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]

Re: Highly efficient string reversal code

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]

Re: Highly efficient string reversal code

pete <pfiland@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.

[pete]

Re: Highly efficient string reversal code

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]

Re: Highly efficient string reversal code

pete <pfiland@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]

Re: Highly efficient string reversal code

Richard<rgrdev@ gmail.comwrites :

pete <pfiland@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]

Re: Highly efficient string reversal code

Richard wrote:

Richard<rgrdev@ gmail.comwrites :
>

>pete <pfiland@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]

Re: Highly efficient string reversal code

pete <pfiland@mindsp ring.comwrites:

Richard wrote:

>Richard<rgrdev @gmail.comwrite s:
>>

>>pete <pfiland@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]

Re: Highly efficient string reversal code

Richard<rgrdev@ gmail.comwrites :

pete <pfiland@mindsp ring.comwrites:
>

>Richard wrote:

>>Richard<rgrde v@gmail.comwrit es:
>>>
>>>pete <pfiland@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]

Re: Highly efficient string reversal code

Richard<rgrdev@ gmail.comwrites :

pete <pfiland@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) kst-u@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]

Re: Highly efficient string reversal code

Richard<rgrdev@ 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) kst-u@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]

Re: Highly efficient string reversal code

Richard<rgrdev@ gmail.comwrites :

Ben Bacarisse <ben.usenet@bsb .me.ukwrites:
>

>Richard<rgrdev @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]

Re: Highly efficient string reversal code

Ben Bacarisse <ben.usenet@bsb .me.ukwrites:

Richard<rgrdev@ gmail.comwrites :
>

>Ben Bacarisse <ben.usenet@bsb .me.ukwrites:
>>

>>Richard<rgrde v@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.