Highly efficient string reversal code

[Ben Bacarisse]

Re: Highly efficient string reversal code

Richard Heathfield <rjh@see.sig.in validwrites:

Nick Keighley said:
>

>On 23 Sep, 07:40, Richard<rgr...@ gmail.comwrote:

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

Re: Highly efficient string reversal code

CBFalconer <cbfalconer@yah oo.comwrites:

"lovecreatesbea ...@gmail.com" 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]

Re: Highly efficient string reversal code

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

CBFalconer <cbfalconer@yah oo.comwrites:
>

>"lovecreatesbe a...@gmail.com" 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]

Re: Highly efficient string reversal code

Ben Bacarisse said:

Richard Heathfield <rjh@see.sig.in validwrites:
>

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

Re: Highly efficient string reversal code

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

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

>CBFalconer <cbfalconer@yah oo.comwrites:
>>

>>"lovecreatesb ea...@gmail.com " 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@verizon.net]

Re: Highly efficient string reversal code

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...@gmail.com]

Re: Highly efficient string reversal code

On Sep 23, 10:11 am, Ben Bacarisse <ben.use...@bsb .me.ukwrote:

"lovecreatesbea ...@gmail.com" <lovecreatesbea ...@gmail.comwr ites:

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...@gmail.com]

Re: Highly efficient string reversal code

On Sep 23, 12:55 pm, CBFalconer <cbfalco...@yah oo.comwrote:

"lovecreatesbea ...@gmail.com" 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]

Re: Highly efficient string reversal code

Nick Keighley <nick_keighley_ nospam@hotmail. comwrites:

On 23 Sep, 05:51, CBFalconer <cbfalco...@yah oo.comwrote:

>"lovecreatesbe a...@gmail.com" wrote:

pete <pfil...@mindsp ring.comwrote:

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

vippstar@gmail. com writes:

On Sep 23, 11:19 am, Nick Keighley <nick_keighley_ nos...@hotmail. com>
wrote:

>On 23 Sep, 05:51, CBFalconer <cbfalco...@yah oo.comwrote:
>>

"lovecreatesbea ...@gmail.com" 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_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

Nick Keighley <nick_keighley_ nospam@hotmail. comwrites:

On 22 Sep, 19:42, dominantuberg.. .@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)];

>
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 "dominantuberge ek". 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_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"

[lovecreatesbeauty@gmail.com]

Re: Highly efficient string reversal code

On Sep 23, 11:23 pm, Keith Thompson <ks...@mib.orgw rote:

Nick Keighley <nick_keighley_ nos...@hotmail. comwrites:

On 23 Sep, 05:51, CBFalconer <cbfalco...@yah oo.comwrote:

"lovecreatesbea ...@gmail.com" wrote:
pete <pfil...@mindsp ring.comwrote:

>

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

Re: Highly efficient string reversal code

jameskuyper@ver izon.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]

Re: Highly efficient string reversal code

Richard<rgrdev@ 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_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"

[Kenny McCormack]

Re: Highly efficient string reversal code

In article <lnk5d2ddfj.fsf @nuthaus.mib.or g>,
God's Representative on Earth <kst-u@mib.orgprocla imed 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.