UB? Avoiding ``object'' before array's start

[Bob Nelson]

It's been a long time since I've posed a query here on c.l.c. My work
environment evolved to primarily C++ and Perl with very little C, so I've
forgotten quite a lot over time.

This revisits the much-discussed topic of decrementing a pointer to the
non-existent location before the start of an array. I've been re-reading
K.N. King's ``C Programming: A Modern Approach'' and came across
``reverse2.c'' on page 228, which raised a red flag. I presume most of the
regulars have access to the book or to the code (it's on the web).

Is the following, alternate approach (yes, I know there are other ways)
correct to interate backwards through the array without sniffing at the
non-existent element before the start of ``a''?

#include <stdio.h>

int main(void)
{
int *p, a[] = { 1, 2, 3 };
size_t n = sizeof a / sizeof *a;

for (p = a + n - 1; p + 1 >= a + 1; --p)
printf ("%i\n", *p);

return 0;
}

 

[Richard Heathfield]

Bob Nelson said:

Is the following, alternate approach (yes, I know there are other ways)
correct to interate backwards through the array without sniffing at the
non-existent element before the start of ``a''?

#include <stdio.h>

int main(void)
{
int *p, a[] = { 1, 2, 3 };
size_t n = sizeof a / sizeof *a;

for (p = a + n - 1; p + 1 >= a + 1; --p)

a + n gives an only-just-legal but nevertheless legal reference to the
non-existent element a[n]. a + n - 1 is therefore fine. p + 1, on the first
iteration, points to that same only-just-legal non-existent element. And p
is never decremented below a. So yes, it's fine.

 

[Guest]

Bob Nelson said:

Is the following, alternate approach (yes, I know there are other ways)
correct to interate backwards through the array without sniffing at the
non-existent element before the start of ``a''?

#include <stdio.h>

int main(void)
{
int *p, a[] = { 1, 2, 3 };
size_t n = sizeof a / sizeof *a;

for (p = a + n - 1; p + 1 >= a + 1; --p)

a + n gives an only-just-legal but nevertheless legal reference to the
non-existent element a[n]. a + n - 1 is therefore fine. p + 1, on the first
iteration, points to that same only-just-legal non-existent element. And p
is never decremented below a. So yes, it's fine.

p is never decremented below a? How can p + 1 >= a + 1 (p >= a) ever be
false, then?

 

[Eric Sosman]

Richard Heathfield wrote On 07/25/06 15:19,:

Bob Nelson said:

Is the following, alternate approach (yes, I know there are other ways)
correct to interate backwards through the array without sniffing at the
non-existent element before the start of ``a''?

#include <stdio.h>

int main(void)
{
int *p, a[] = { 1, 2, 3 };
size_t n = sizeof a / sizeof *a;

for (p = a + n - 1; p + 1 >= a + 1; --p)

a + n gives an only-just-legal but nevertheless legal reference to the
non-existent element a[n]. a + n - 1 is therefore fine. p + 1, on the first
iteration, points to that same only-just-legal non-existent element. And p
is never decremented below a. So yes, it's fine.

"Let's play computer!"

Init: p = a+3-1 ==> p = a+2 (*p == 3)
Test: p+1 >= a+1 ==> a+3 >= a+1 ==> true
Body executes
Step: p = (a+2)-1 ==> p = a+1 (*p == 2)
Test: p+1 >= a+1 ==> a+2 >= a+1 ==> true
Body executes
Step: p = (a+1)-1 ==> p = a+0 (*p == 1)
Test: p+1 >= a+1 ==> a+1 >= a+1 ==> true
Body executes
Step: p = (a+0)-1 ==> UNDEFINED BEHAVIOR
Test: p+1 >= a+1 ==> UNDEFINED BEHAVIOR

The pair of "plus ones" in the test don't seem to have
any useful effect. Whenever they are valid (that is, whenever
p points to an actual element of a) they can be subtracted
from both sides, so the test is the same as `p >= a' in the
sense that both produce the same result or both are invalid.
The decorations do not expand the valid range.

To run a pointer backwards through an array, I suggest
writing the loop this way:

for (p = a + n; p > a; ) {
--p;
/* loop body */
}

A slightly riskier form is

for (p = a + n; p-- > a; ) {
/* loop body */
}

.... which sins by trying to compute the invalid pointer
value a-1, but avoids compounding the sin by doing further
arithmetic with that invalid value.

(I don't know what formulation King's book recommends.)

 

[Richard Heathfield]

Eric Sosman said:

Richard Heathfield wrote On 07/25/06 15:19,:

Bob Nelson said:

for (p = a + n - 1; p + 1 >= a + 1; --p)

a + n gives an only-just-legal but nevertheless legal reference to the
non-existent element a[n]. a + n - 1 is therefore fine. p + 1, on the
first iteration, points to that same only-just-legal non-existent
element. And p is never decremented below a. So yes, it's fine.

"Let's play computer!"

Ouch. I lose. My apologies to the OP. I wasn't reading closely enough.

<snip>

 

[Eric Sosman]

Richard Heathfield wrote On 07/25/06 16:16,:

Eric Sosman said:

Richard Heathfield wrote On 07/25/06 15:19,:

Bob Nelson said:

for (p = a + n - 1; p + 1 >= a + 1; --p)

a + n gives an only-just-legal but nevertheless legal reference to the
non-existent element a[n]. a + n - 1 is therefore fine. p + 1, on the
first iteration, points to that same only-just-legal non-existent
element. And p is never decremented below a. So yes, it's fine.

"Let's play computer!"

Ouch. I lose. My apologies to the OP. I wasn't reading closely enough.

Let him who has never committed an off-by-one error
cast the -1th stone.

 

[Old Wolf]

Let him who has never committed an off-by-one error
cast the -1th stone.

Should that be the -1st ?

 

[Eric Sosman]

Should that be the -1st ?

See Figure abs(-1).

 

[Joe Wright]

It's been a long time since I've posed a query here on c.l.c. My work
environment evolved to primarily C++ and Perl with very little C, so I've
forgotten quite a lot over time.

This revisits the much-discussed topic of decrementing a pointer to the
non-existent location before the start of an array. I've been re-reading
K.N. King's ``C Programming: A Modern Approach'' and came across
``reverse2.c'' on page 228, which raised a red flag. I presume most of the
regulars have access to the book or to the code (it's on the web).

Is the following, alternate approach (yes, I know there are other ways)
correct to interate backwards through the array without sniffing at the
non-existent element before the start of ``a''?

#include <stdio.h>

int main(void)
{
int *p, a[] = { 1, 2, 3 };
size_t n = sizeof a / sizeof *a;

for (p = a + n - 1; p + 1 >= a + 1; --p)
printf ("%i\n", *p);

return 0;
}

#include <stdio.h>

int main(void)
{
int a[] = { 1, 2, 3 };
size_t i, n = sizeof a / sizeof *a;

for (i = n - 1; i < n; --i)
printf ("%i\n", a);

return 0;
}

 

[Tak-Shing Chan]

It's been a long time since I've posed a query here on c.l.c. My work
environment evolved to primarily C++ and Perl with very little C, so I've
forgotten quite a lot over time.

This revisits the much-discussed topic of decrementing a pointer to the
non-existent location before the start of an array. I've been re-reading
K.N. King's ``C Programming: A Modern Approach'' and came across
``reverse2.c'' on page 228, which raised a red flag. I presume most of the
regulars have access to the book or to the code (it's on the web).

Is the following, alternate approach (yes, I know there are other ways)
correct to interate backwards through the array without sniffing at the
non-existent element before the start of ``a''?

#include <stdio.h>

int main(void)
{
int *p, a[] = { 1, 2, 3 };
size_t n = sizeof a / sizeof *a;

for (p = a + n - 1; p + 1 >= a + 1; --p)
printf ("%i\n", *p);

return 0;
}

#include <stdio.h>

int main(void)
{
int a[] = { 1, 2, 3 };
size_t i, n = sizeof a / sizeof *a;

for (i = n - 1; i < n; --i)
printf ("%i\n", a);

return 0;
}

Are you taking the subject line literally? Your program
does in fact invoke UB, but I suspect that the OP wants
something /other/ than UB. For the subtitle was: `Avoiding
``object'' before array's start'.

Tak-Shing

 

[Tak-Shing Chan]

It's been a long time since I've posed a query here on c.l.c. My work
environment evolved to primarily C++ and Perl with very little C, so I've
forgotten quite a lot over time.

This revisits the much-discussed topic of decrementing a pointer to the
non-existent location before the start of an array. I've been re-reading
K.N. King's ``C Programming: A Modern Approach'' and came across
``reverse2.c'' on page 228, which raised a red flag. I presume most of the
regulars have access to the book or to the code (it's on the web).

Is the following, alternate approach (yes, I know there are other ways)
correct to interate backwards through the array without sniffing at the
non-existent element before the start of ``a''?

#include <stdio.h>

int main(void)
{
int *p, a[] = { 1, 2, 3 };
size_t n = sizeof a / sizeof *a;

for (p = a + n - 1; p + 1 >= a + 1; --p)
printf ("%i\n", *p);

return 0;
}

#include <stdio.h>

int main(void)
{
int a[] = { 1, 2, 3 };
size_t i, n = sizeof a / sizeof *a;

for (i = n - 1; i < n; --i)
printf ("%i\n", a);

return 0;
}

Are you taking the subject line literally? Your program
does in fact invoke UB, but I suspect that the OP wants
something /other/ than UB. For the subtitle was: `Avoiding
``object'' before array's start'.

Sorry---I have overlooked the fact that you are using
size_t's. I retract my previous statement.

Your use of size_t in this context is quite clever (but the
loop condition of i < n is a bit misleading).

Tak-Shing

 

[Joe Wright]

Bob Nelson wrote:
It's been a long time since I've posed a query here on c.l.c. My work
environment evolved to primarily C++ and Perl with very little C, so
I've
forgotten quite a lot over time.

This revisits the much-discussed topic of decrementing a pointer to the
non-existent location before the start of an array. I've been
re-reading
K.N. King's ``C Programming: A Modern Approach'' and came across
``reverse2.c'' on page 228, which raised a red flag. I presume most
of the
regulars have access to the book or to the code (it's on the web).

Is the following, alternate approach (yes, I know there are other ways)
correct to interate backwards through the array without sniffing at
the non-existent element before the start of ``a''?

#include <stdio.h>

int main(void)
{
int *p, a[] = { 1, 2, 3 };
size_t n = sizeof a / sizeof *a;

for (p = a + n - 1; p + 1 >= a + 1; --p)
printf ("%i\n", *p);

return 0;
}




#include <stdio.h>

int main(void)
{
int a[] = { 1, 2, 3 };
size_t i, n = sizeof a / sizeof *a;

for (i = n - 1; i < n; --i)
printf ("%i\n", a);

return 0;
}

Are you taking the subject line literally? Your program
does in fact invoke UB, but I suspect that the OP wants
something /other/ than UB. For the subtitle was: `Avoiding
``object'' before array's start'.

Sorry---I have overlooked the fact that you are using
size_t's. I retract my previous statement.

Your use of size_t in this context is quite clever (but the
loop condition of i < n is a bit misleading).

Thank you.