Re: generic strncpy - off-by-one error

[Timothy Miller <miller@techsource.com>]

Peter Kjellerstedt wrote:

>>While I can understand that certain architectures may benefit 
>>from that alteration, I am curious as to what SPECIFICALLY it 
>>is doing that is different.  How do they differ?
> 
> 
> I do not know if this will give you anything, but here is
> the disassembled CRIS version of your first while loop 
> (note that the branch instructions have one delay slot,
> and that dest, src and count are in $r10, $r11 and $r12):
> 
>   while (count && *src)
>    805d8:       6cc6                    test.d $r12
>    805da:       1830                    beq 805f4
 >    805dc:       6a96                    move.d $r10,$r9

Ok, test count and exit if count is zero.

I take it that this move is the copy of the dst to a temporary variable?

>    805de:       8b0b                    test.b [$r11]
>    805e0:       1230                    beq 805f4
>    805e2:       0f05                    nop 

Test *s and exit if zero.

>   {
>     count--;
>    805e4:       81c2                    subq 1,$r12


>     *tmp++ = *src++;
>    805e6:       4bde                    move.b [$r11+],$r13

Fetch *s and increment.  This is redundant.  Why didn't it know to fetch 
  *s above and keep it in a register?

>    805e8:       6cc6                    test.d $r12
>    805ea:       0830                    beq 805f4
>    805ec:       c9df                    move.b $r13,[$r9+]

Test count and exit if count is zero.  Why is it doing this again?  Why 
not jump back to the top?  Oh, wait... in that case, for the loop to 
exit, it would jump to the top and then jump back to past the end, 
rather than just failing one branch.

I see that the delay slot was filled with the store to *dst.  But is 
there also some pipeline latency that makes this worth while?

>    805ee:       8b0b                    test.b [$r11]
>    805f0:       f320                    bne 805e4
>    805f2:       0f05                    nop 

Test *src AGAIN and loop if nonzero.  Redundant.

>   }
> 
> And here is my first while loop:
> 
>   while (count)
>    8062c:       6cc6                    test.d $r12
>    8062e:       1030                    beq 80640
>    80630:       6a96                    move.d $r10,$r9

Test count and bypass if zero.  Also, copy dst.

>   {
>     count--;
>     if (!(*tmp++ = *src++))
>    80632:       4bde                    move.b [$r11+],$r13
>    80634:       c9db                    move.b $r13,[$r9]

Move data

>    80636:       890f                    test.b [$r9+]

Interesting how (a) it moved the increment to the test, and (b) it makes 
a redundant read of the dest.

Does this arch not get condition codes from things other than test and 
compare?

And why didn't it test $r13 instead?  Wouldn't that have been a lot more 
efficient?

>    80638:       0630                    beq 80640
>    8063a:       81c2                    subq 1,$r12

Exit on zero and decrement count.

>       break;
>    8063c:       f520                    bne 80632
>    8063e:       0f05                    nop 

Loop.

>   }
> 
> 
>>>Also note that your version
>>>of the second loop needs an explicit  comparison with -1,
>>>whereas mine uses an implicit comparison with 0.
>>
>>I don't understand why you say I need an explicit comparison 
>>with -1. My first loop exits either with the number of bytes 
>>remaining in the buffer or with zero if it's copied count 
>>number of bytes.
> 
> 
> I was talking about the second loop. The object code the compiler
> produces for your version actually tests the count variable after
> it decreases it, which is why it tests for -1.

Why does it do that?  Is that somehow more optimal?  Why doesn't it test 
BEFORE it decrements?  Isn't that more straightforward?

In any event, couldn't that be fixed by moving the decrement into the loop?

> 
>>The second loop WOULD require a comparison with -1 IF the 
>>"count--" were not inside of the loop body.  As it IS in the 
>>loop body, there is no need for that.  My second loop has an 
>>implicit comparison against zero.
> 
> 
> Hmm, your second loop from above looks like:
> 
> 	while (n--) {
> 		*s++ = 0;
> 	}
> 
> whereas mine looks like:
> 
>  	while (count) {
>  		*tmp++ = '\0';
>  		count--;
>  	}
> 
> You seem to be referring to my version, where what you say is true.

And what I was saying was that since what the while should test is the 
value before the decrement, I assumed that the test would be before the 
decrement.


>>
>>I agree that this is definately a more elegant look to the 
>>code, and I would prefer what you have done here.  But what 
>>puzzles me is that this is functionally and logically 
>>equivalent to my code.
>>
>>So, this code:
>>
>>for (A; B; C) {}
>>
>>is the same as this:
>>
>>A;
>>while (B) {
>>	...
>>	C;
>>}
>>
>>
>>So why is it that this mere syntactic difference causes the 
>>compiler to produce a better result?
> 
> 
> I wish I new. Actually in the CRIS case, it seems to be an
> optimizer thing. If I change your first loop from
> 
> 	while (n && *s2) {
> 		n--;
> 		*s++ = *s2++;
> 	}
> 
> to
> 
> 	while (n && *s2) {
> 		*s++ = *s2++;
> 		n--;
> 	}
> 
> it gives the expected object code, i.e., the same as my
> first for loop. So here is a modified version of your
> code that gives exactly the same object code (for CRIS) 
> as my version with the for loops:

A decent optimizer should know that the "n--" and the "*s++ = *s2++" are 
independent and migrate them to optimal positions.

Furthermore, I put the "n--" first because I assumed that the compiler 
might be stupid about it.  The idea is to order the statements so that 
the results of a given instruction are being computed while the next one 
is being decoded.

My assumption was that the code would branch back to the loop test 
(rather than make a second one) at the end of the loop and then test n. 
  Therefore, decrementing n earlier would be a win in terms of having 
the result earlier for the test, reducing pipline stall.

> 
> char *strncpy(char * s1, const char * s2, size_t n)
> {
> 	register char *s = s1;
> 
> 	while (n && *s2) {
> 		*s++ = *s2++;
> 		n--;
> 	}
> 	while (n) {
> 		*s++ = 0;
> 		n--;
> 	}
> 	return s1;
> }
> 
> //Peter
> 
>