What does the standard say about array access wraparound?

[David Mathog]

If this:

int i,sum;
int *array;
for(sum=0, i=0; i<len; i++){
sum += array[i];
}

is converted to this (never mind why for the moment):

int i,sum;
int *array;
int *arrl;
arl=&array[-len];
for(sum=0,i=len ; i<2*len; i++){
sum += arrl[i];
}

it should give the same result. But there are some funny
things that can happen. For instance, if &array is 1000 and
len is 100000. In that case arrl will hold an address
(1000-100000) which presumably wraps around since the
pointer should be an unsigned int (whatever size int is).
The address it points to will be MAX_POINTER - 100000 + 1000.
When the second form loop loop begins i=len (100000) so
arrl[100000] will wrap back around and point to the same
place as array[0].

Or will it?

It seems possible that this sort of array access "off the top of
memory" could trigger a fault.

What does the C standard say about this (if anything)?

Thanks,

David Mathog
ma****@caltech. edu
Manager, Sequence Analysis Facility, Biology Division, Caltech

[Mike Wahler]

"David Mathog" <ma****@caltech .edu> wrote in message
news:2004052708 0256.4fbb14a0.m a****@caltech.e du...

If this:

int i,sum;
int *array;
Note that the object you've named 'array' is
*not* an array, it's a pointer. Also note that
you've not given this pointer a valid value,
so evaluating it will produce undefined behavior.
for(sum=0, i=0; i<len; i++){
You haven't defined 'len'.
Also note that if you want to use them to index
(or record the size of) an array, the objects 'i'
and 'len' should be of type 'size_t', not 'int'.
sum += array[i];
Undefined behavior.
}

is converted to this (never mind why for the moment):

int i,sum;
int *array;
int *arrl;
Two pointers. No arrays.
arl=&array[-len];
Undefined behavior. Even if the pointer named 'array'
had a valid value, the behavior is still undefined.
The only valid indices are those which refer within
the same object.
for(sum=0,i=len ; i<2*len; i++){
sum += arrl[i];
}

it should give the same result.
Well, yes, undefined == undefined.
But there are some funny
things that can happen.
That's essentially what 'undefined behavior' is.
Another 'funny thing' that might happen is that
your keyboard could emit 100,000 volts.
For instance, if &array is 1000 and
len is 100000. In that case arrl will hold an address
(1000-100000) which presumably wraps around
There is no such thing as 'wrapping around' of arrays in C.
since the
pointer should be an unsigned int (whatever size int is).
A pointer is *not* an integer. It's a pointer. Its
representation and structure is implementation-specific.

The address it points to will be MAX_POINTER
There's no such thing as 'MAX_POINTER' in C.
- 100000 + 1000.
When the second form loop loop begins i=len (100000) so
arrl[100000] will wrap back around and point to the same
place as array[0].

Or will it?
Yes. No. Maybe. Sometimes. Never. Only on Wednesdays
when it rains in Tokyo. Your code produces undefined behavior.

It seems possible that this sort of array access "off the top of
memory" could trigger a fault.
The fault is with your code.

What does the C standard say about this (if anything)?

It says your code is not valid C.

Which C book(s) are you reading?

-Mike

[Case]

Mike Wahler wrote:

"David Mathog" <ma****@caltech .edu> wrote in message
news:2004052708 0256.4fbb14a0.m a****@caltech.e du...

for(sum=0, i=0; i<len; i++){

Also note that if you want to use them to index
(or record the size of) an array, the objects 'i'
and 'len' should be of type 'size_t', not 'int'.

sum += array[i];

Huh, why should a variable used as array index be of
type 'size_t'? K&R-2nd/ANSI uses 'int' quite often
to index arrays.

Case

[Dan Pop]

In <20************ *************** *@caltech.edu> David Mathog <ma****@caltech .edu> writes:

If this:

int i,sum;
int *array;
for(sum=0, i=0; i<len; i++){
sum += array[i];
}

is converted to this (never mind why for the moment):

int i,sum;
int *array;
int *arrl;
arl=&array[-len];
for(sum=0,i=len ; i<2*len; i++){
sum += arrl[i];
}

it should give the same result.

Do yourself a favour and read the FAQ. Don't come back until you've
finished it!

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Default User]

David Mathog wrote:

[a bunch of crazy bad code with undefined behavior]
I suggest to thoroughly learn the language before trying this sort of
whacky stuff. Once you become familiar with using arrays and pointers,
then you'll also find you don't need to ask these questions, you'll
already have the answers.


Brian Rodenborn

[Stephen L.]

David Mathog wrote:

If this:

int i,sum;
int *array;
for(sum=0, i=0; i<len; i++){
sum += array[i];
}

is converted to this (never mind why for the moment):

int i,sum;
int *array;
int *arrl;
arl=&array[-len];
for(sum=0,i=len ; i<2*len; i++){
sum += arrl[i];
}

it should give the same result. But there are some funny
things that can happen. For instance, if &array is 1000 and
len is 100000. In that case arrl will hold an address
(1000-100000) which presumably wraps around since the
pointer should be an unsigned int (whatever size int is).
The address it points to will be MAX_POINTER - 100000 + 1000.
When the second form loop loop begins i=len (100000) so
arrl[100000] will wrap back around and point to the same
place as array[0].

Or will it?

It seems possible that this sort of array access "off the top of
memory" could trigger a fault.

What does the C standard say about this (if anything)?

Thanks,

David Mathog
ma****@caltech. edu
Manager, Sequence Analysis Facility, Biology Division, Caltech

This is a little bit better of a starting point...

int
main (void)
{
int the_array[100]; /* Note, we're not initializing the
array... */
int i,sum;
int *array = the_array; /* same as ... = &the_array[ 0 ]; */
int len = sizeof (the_array) / sizeof (the_array[ 0 ]);

for(sum=0, i=0; i<len; i++){
sum += array[i];
}

return (0);
}

Now, the C language does _not_ keep track of
array bounds; arrays decay to a pointer (to
the 1st element of the object). As such, "indexing"
through an array in C will not "wrap-around"
to the beginning/end when either the end/beginning
is reached. It is the programmer's responsibility
to keep track of his array(s) and their bounds.

I believe standard (I can't cite the exact paragraph
- para-phrased) says that if the result of any
pointer calculation is not within the object,
the results are undefined.

For example, using the above -

array[ -1 ]

would be undefined. There are some languages
that would produce a nice run-time diagnostic
for such a reference; C is not one of them.
A reference like the above may do nothing
meaningful (it may access memory not part of the
object), or produce a "memory violation" error.
It could do both in the same program, at different
times. Those are just a couple of examples of
"undefined behavior".

Having said all of that, you can do something like -
int
main (void)
{
int the_array[100]; /* Note, we're not initializing the
array... */
int i,sum;
int len = sizeof (the_array) / sizeof (the_array[ 0 ]);
int *array = &the_array[ len - 1 ];
for(sum=0, i=0; i < len; i++){
sum += array[ -i ];
}

return (0);
}

Personally, I avoid constructs like the above
because it "looks" like I'm advancing through the
array instead of going from the end to the beginning.

I'm not sure how you arrived at the "translatio n"
you provided, though.
HTH,

Stephen

[Dan Pop]

In <40************ ***********@new s.xs4all.nl> Case <[e-mail]> writes:

Mike Wahler wrote:

"David Mathog" <ma****@caltech .edu> wrote in message
news:2004052708 0256.4fbb14a0.m a****@caltech.e du...

for(sum=0, i=0; i<len; i++){

Also note that if you want to use them to index
(or record the size of) an array, the objects 'i'
and 'len' should be of type 'size_t', not 'int'.

sum += array[i];

Huh, why should a variable used as array index be of
type 'size_t'? K&R-2nd/ANSI uses 'int' quite often
to index arrays.

For indexing purposes, any integer type does the job:

6.5.2.1 Array subscripting

Constraints

1 One of the expressions shall have type ``pointer to object type'',
the other expression shall have integer type, and the result
has type ``type''.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Mike Wahler]

"Case" <[e-mail]> wrote in message
news:40******** *************** @news.xs4all.nl ...

Mike Wahler wrote:

"David Mathog" <ma****@caltech .edu> wrote in message
news:2004052708 0256.4fbb14a0.m a****@caltech.e du...

for(sum=0, i=0; i<len; i++){

Also note that if you want to use them to index
(or record the size of) an array, the objects 'i'
and 'len' should be of type 'size_t', not 'int'.

sum += array[i];

Huh, why should a variable used as array index be of
type 'size_t'? K&R-2nd/ANSI uses 'int' quite often
to index arrays.

If the range is sufficient (and usage is valid), 'int'
will work. But 'size_t' is specifically guaranteed to
be able to represent the largest possible size object
(and by corollary, the largest possible number of (byte-sized)
objects.) Also, since 'size_t' is an unsigned type, sometimes
one might need a signed type like 'int', if one needs to
index 'backward' from a point other than the beginning of
an array. (I've never needed to do this, but I suppose
certain applications might).

I always use 'size_t', then I need not be concerned about
whether 'int' is (or will be) sufficient if my code changes
later.

-Mike

[David Mathog]

On 27 May 2004 16:25:23 GMT
Da*****@cern.ch (Dan Pop) wrote:

In <20************ *************** *@caltech.edu> David Mathog <ma****@caltech .edu> writes:

Do yourself a favour and read the FAQ. Don't come back until you've
finished it!

Good advice. The answer is in 6.17 where it says:

(snip)
Although this technique is attractive (and was used in old editions of the book Numerical Recipes in C), it does not conform to the C standards. Pointer arithmetic is defined only as long as the pointer points within the same allocated block of memory, or to the imaginary ``terminating'' element one past it; otherwise, the behavior is undefined, even if the pointer is not dereferenced. The code above could fail if, while subtracting the offset, an illegal address were generated (perhaps because the address tried to ``wrap around'' past the beginning of some memory segment).

References: K&R2 Sec. 5.3 p. 100, Sec. 5.4 pp. 102-3, Sec. A7.7 pp. 205-6
ANSI Sec. 3.3.6
ISO Sec. 6.3.6
Rationale Sec. 3.2.2.3

By "one past it" is the FAQ referring to both ends of the
memory block or just the "high" end? Either way this would be
ok (calculates an address "one after it"):

int *p;
int *plast;
int sum;
p=malloc(100*si zeof(int));
plast=&(p[99]);
/* code which stores values into those 100 positions */
for(sum=0; p<=plast; p++){ sum += *p; }

but this might not be ok (calculates an address "one before it"),
change last line only of previous to:

for(sum=0; p<=plast; plast--){ sum += *plast; }

Thanks,

David Mathog
ma****@caltech. edu
Manager, Sequence Analysis Facility, Biology Division, Caltech

[Mark McIntyre]

On Thu, 27 May 2004 18:35:37 +0200, in comp.lang.c , Case <[e-mail]> wrote:

Huh, why should a variable used as array index be of
type 'size_t'?
because size_t is designated to be large enough to hold the maximum size of
an object, hence you can guarantee to access every member of any
concievable array. An int may be smaller than size_t (and is, on some
popular implementations ).
K&R-2nd/ANSI uses 'int' quite often to index arrays.

K&R != ISO Standard.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.c om/ms3/bchambless0/welcome_to_clc. html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---