Highly efficient string reversal code

[lovecreatesbeauty]

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]

Richard wrote:
...

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]

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.

 

[Kenny McCormack]

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.

 

[jameskuyper]

I'm willing to concede anything when its true and there is some proof.

What would you accept as proof? Ben Bacarisse has already identified
the Cambridge CAP Machine as an machine that terminates a program upon
the loading of an invalid address into an address register. Do you
think he's lying? What do you require - detailed documentation of this
feature? The output from a program that failed for this reason? An in-
person demonstration of the failure?

 

[Richard]

What would you accept as proof? Ben Bacarisse has already identified
the Cambridge CAP Machine as an machine that terminates a program upon
the loading of an invalid address into an address register. Do you

I did not see that before. What do you want from me? to accept
everything on face value? There has been many instances of regs being
wrong here. I can accept that too. God knows I'm no angle either.

think he's lying? What do you require - detailed documentation of this

No I do not think he is lying. What is it with this group and people so
ready to assume people are accusing other of "lying"?!?!?!

feature? The output from a program that failed for this reason? An in-
person demonstration of the failure?

No. Reasonable discourse and pointers to real life situations. Simple
enough.

 

[jameskuyper]

I did not see that before. What do you want from me? to accept
everything on face value?

No, I only ask that if, for instance, someone says (as Ben did on
another thread) that the Cambridge CAP machine has this
characteristic, that you would not go out of your way to contradict
him without at least first looking for and finding evidence that his
claim was wrong.

...There has been many instances of regs being
wrong here. I can accept that too. God knows I'm no angle either.


No I do not think he is lying. What is it with this group and people so
ready to assume people are accusing other of "lying"?!?!?!

I'm not accusing you of lying, nor am I accusing Ben of lying. You
responded to Ben's message on a different thread mentioning the CAP
machine, which left me with the impression that you had actually read
it. Then, in a later message on this thread you wrote " I doubt
there's anywhere it actually does actually cause an issue". To me, it
seems that possessing such a doubt, after having read Ben's message,
implies either that you also doubt Ben's veracity, or that you didn't
realize what he was saying. I'm now favoring the second possibility,
but it is not the first one that came to mind.

No. Reasonable discourse and pointers to real life situations. Simple
enough.

We give your precisely those things, and you dismiss them as
"unreasonable" and "unreal", respectively. It's pretty hard to figure
out how to respond to that.

 

[dj3vande]

Richard wrote:

We give your precisely those things, and you dismiss them as
"unreasonable" and "unreal", respectively. It's pretty hard to figure
out how to respond to that.

Find a VAX^WPC^WLinux/x86^WLinux/x64 implementation that does it that
way, of course!


dave
(those are the only computers in the world, aren't they?)

 

[CBFalconer]

.... snip ...

Hold on - I still dont hold with the other version from cbf.
Frankly any prodding he gets is his own fault - he spends 90% of
his posts doing much the same. And I dont slag off correct code
either. 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.

Good for you. Of course the fact that my code works, and that
yours doesn't, shouldn't affect that attitude.

 

[CBFalconer]

... snip ...

My version

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!

I think that is OK. The above for does nothing except set p1 == p.

No, it dereferences p+1. If p points at an empty string "", then p+1
points one past the end of the array, and the behavior of dereferencing
p+1 is undefined. Furthermore, if p points at "\0Hello, world!", the
loop given above will leave p1 pointing at the '!', which is not where
it should be pointing.

Well done. I missed that.

 

[CBFalconer]

.... snip ...


...is only an error of opinion

Well, I described why I have that opinion earlier (with a printf
example). Did you read that?

 

[CBFalconer]

.... snip, avoiding requoting my mistake ...

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.

Well, at least it won't affect anything I write, since I will use
my own routine. Which just proves, once more, that eyeballing
source is not a positive debugger.

 

[CBFalconer]

.... snip ...


which I consider a bug

Why? If you want to detect that usage passing the 'reversed'
string to printf or fwrite will blow up quickly enough.

 

[CBFalconer]

CBFalconer wrote:

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

I have edited it a little bit to get pointer to pointer as
function argument and combined it with my get_single_word
program and it works little strange though. Also, your function
is much easier to read IMHO:
.... snip ...

=================== OUTPUT =====================
[arnuld@dune ztest]$ gcc -ansi -pedantic -Wall -Wextra reverse-string.c
[arnuld@dune ztest]$ ./a.out
Ben
Reversed: [ neB ]
CBFalconer
Reversed: [ rBFalconeC ] <--** should be renoclaFBC here. Etc.
comp.kang.c++
Reversed: [ +omp.kang.c+c ]
[arnuld@dune ztest]$

Just looking at your output, your code is obviously failing to
reverse strings correctly.

 

[Ben Bacarisse]

Thank you very much. I correct it as follow:

char *reverse(char *p)
{
char *p1, *p2, ch;

for (p1 = p; *p1; p1++) ;
p1--;

Now you have gone back to the UB I thought you were trying to avoid.
If *p is zero, p1-- will be invalid

for (p2 = p; p2 < p1; p2++, p1--)

and can't be compared to p2.

 

[Peter Nilsson]

Not an object pointer.

Quite so. I was distracted in thinking about what other
pointer values there could be in general.

Would you consider a pointer to write-only memory (e.g.
memory mapped output) to be the address of an object,
an indeterminate value, or something else? Footnote
115 in N1256 suggests they are object pointers, though
that somewhat conflicts with the definition of object.

 

[lovecreatesbeauty]

Now you have gone back to the UB I thought you were trying to avoid.
If *p is zero, p1-- will be invalid

Ben, thank you very much.

and can't be compared to p2.

I don't understand this. Does my new version below avoid this problem?


char *reverse(char *p)
{
char *p1, *p2, ch;

p1 = p;
if (!*p) return p;
while (*p1) p1++;
p1--;
for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}


#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define LEN 1024

int main(int argc, char *argv[])
{
char a[LEN] = {'\0'};

if (argv[1] && strlen(argv[1]) < LEN)
strncpy(a, argv[1], LEN - 1);
else {
printf("please provide at least one argument with
length of "
"less than %d chars
\n", LEN);
return EXIT_FAILURE;
}
printf("%s\n", reverse(a));
return EXIT_SUCCESS;
}

 

[Ben Bacarisse]

Ben, thank you very much.


I don't understand this.

There are two problems with a pointer that points "before" the first
element of an array (I have to put "before" in quotes because since
the pointer is ill-formed it is not possible to say where it really
points). The first is that the pointer value might trap. The second
is that you are not permitted to compare it with other pointers -- or
to be more accurate, the comparison is undefined.

Is is worth saying that, because the behaviour is undefined, an
implementation is free to permit both and to give pointers a meaning.
Reversing a string can be done without having to any such extension to
standard C -- hence so much fuss about it here.

Does my new version below avoid this problem?

Yes. There is an implied contract -- that a string be passed -- and
provided that is that case then the code is properly defined.

 

[Pilcrow]

It also has the fatal error (to me) of returning a char*. This
encourages the silly mistake of trying to print a string and its
reverse with:

printf("%s & %s\n", s, strrev(s));

In fact it is even worse than that - it fails to return the
declared object. My version returns strlen, which it needs to
evaluate to find the end of the string, and thus avoids the caller
needing to call it again. Also note that my code returns a NULL if
the passed string is NULL, and correctly handles strings of length
0 and 1.

You are distinguishing between strings of length 0 and NULL strings.
How does one pass a NULL string?

 

[Nick Keighley]

God knows I'm no angle either.

you can be a bit obtuse though