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

[Mark McIntyre]

On Thu, 27 May 2004 14:56:52 -0700, in comp.lang.c , David Mathog
<ma****@caltech .edu> wrote:

By "one past it" is the FAQ referring to both ends of the
memory block or just the "high" end?

one past is (IMHO) unambiguous. If it included one before, it would say
"one past or before"...
--
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 =---

[Old Wolf]

"Stephen L." <sd*********@ca st-com.net> wrote:

Now, the C language does _not_ keep track of
array bounds;

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.

The standard permits implementations to bounds-check their arrays.
I have heard of some which offer this as a debug option.

[Mike Wahler]

"David Mathog" <ma****@caltech .edu> wrote in message
news:2004052714 5652.1f44beb6.m a****@caltech.e du...

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

In <20040527080256 .4fbb14a0.ma*** *@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?
Just the 'high' end. (That is, the highest address).
Either way this would be
ok (calculates an address "one after it"):

int *p;
int *plast;
int sum;
p=malloc(100*si zeof(int));
Nit:
More idiomatic is:

p = malloc(100 * sizeof *p);

If you later change the type of 'p', this line
need not be changed. Also don't forget to
check return value of 'malloc()'.
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
Is definitely not "OK".
(calculates an address "one before it"),
change last line only of previous to:

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

Not only is pointing before the start of the array
invalid, even if it were valid, your loop would
be 'infinite' ( p<=plast would never go false (barring
some platform-specific 'wrapping').

-Mike

[Dan Pop]

In <vE************ *****@newsread2 .news.pas.earth link.net> "Mike Wahler" <mk******@mkwah ler.net> writes:

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

1. Using size_t may be wasteful. Precisely because it is supposed to be
large enough to cover the largest object supported by the
implementation.

2. As you also pointed out, using an unsigned type may be ocasionally
inconvenient. I prefer to use them exclusively for bit manipulation
purposes, unless I have a *real* need for the extended range.

3. Using an unknown type may also be ocasionally inconvenient. You don't
even know whether size_t gets promoted to int by the integral
promotions ;-)

Far too often, it is possible to tell whether int will do the job or not.
If it does the job, there is NO point in using any other type.

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

[David Mathog]

On Fri, 28 May 2004 04:47:41 GMT
"Mike Wahler" <mk******@mkwah ler.net> wrote:

"David Mathog" <ma****@caltech .edu> wrote in message
news:2004052714 5652.1f44beb6.m a****@caltech.e du...

On 27 May 2004 16:25:23 GMT <SNIP> 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

Is definitely not "OK".

(calculates an address "one before it"),
change last line only of previous to:

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

Interesting.

Can anybody explain the reason why the standard
makes 1 above allocated memory special but 1 below not?
Doing that destroys the symmetry of loops controlled by pointer
comparisons (as shown above). What is gained by this
restriction? Does this have something to do with the extra
data that (at least on some platforms) malloc stores just
before the allocated memory?

To make a legal decrementing loop controlled by pointer
comparison something like this must be used instead:

for(sum=0; ; plast--){
sum += *plast;
if(p==plast)bre ak;
}

The incrementing case can be rewritten in this format too,
so the format is symmetric as long as the pointer test is
not inside the for().

Conversely, if an index is used instead the simple for() form
is symmetric, ie:

for(i=0; i<=99; i++){ sum += p[i]; };

and

for(i=99; i>=0; i--){ sum += p[i]; };

Thanks,

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

[CBFalconer]

David Mathog wrote:

.... snip ...
Can anybody explain the reason why the standard makes 1 above
allocated memory special but 1 below not? Doing that destroys
the symmetry of loops controlled by pointer comparisons (as
shown above). What is gained by this restriction? Does this
have something to do with the extra data that (at least on
some platforms) malloc stores just before the allocated memory?
Because, for an array of large items, one before could be a
considerable distance (rather than one byte). Also, if the array
is the first item in a segment, any distance before can easily be
an illegal address and cause traps.

To make a legal decrementing loop controlled by pointer
comparison something like this must be used instead:

for(sum=0; ; plast--){
sum += *plast;
if(p==plast)bre ak;
}

Assuming array a to be scanned, try:

p = &a[0] + sizeof(a)/sizeof(*p); /* one past */
sum = 0;
do {
sum += *(--tp);
} while (tp > &a[0]);

--
fix (vb.): 1. to paper over, obscure, hide from public view; 2.
to work around, in a way that produces unintended consequences
that are worse than the original problem. Usage: "Windows ME
fixes many of the shortcomings of Windows 98 SE". - Hutchison

[David Mathog]

On Thu, 27 May 2004 23:28:27 +0100
Mark McIntyre <ma**********@s pamcop.net> wrote:

On Thu, 27 May 2004 14:56:52 -0700, in comp.lang.c , David Mathog
<ma****@caltech .edu> wrote:

By "one past it" is the FAQ referring to both ends of the
memory block or just the "high" end?

one past is (IMHO) unambiguous. If it included one before, it would say
"one past or before"...

IMHO it is ambiguous. We can probably agree that "one above" and "one below" are unambiguous since these refer to specific memory locations.

However "one past" is ambiguous since the definition
of "past" is vector in nature and the direction of that vector
is not otherwise specified in the FAQ. A pointer could
be either incrementing up through a memory block
or decrementing down through it. In the latter case "one past"
may still be applied (at least grammatically, if not in C code)
and in this case "one past" would generally be understood to
refer to the position immediately below the memory block being traversed.

Ie, if you were directed to "the house adjacent to and one past
the blue Victorian on Elm street" your direction of travel on that
street would determine which of the two possible houses fitting
this description is your destination.

Regards,

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

[Eric Sosman]

David Mathog wrote:

However "one past" is ambiguous since the definition
of "past" is vector in nature and the direction of that vector
is not otherwise specified in the FAQ. [...]

The direction *is* specified in the FAQ, Question 6.17.
The specification is implicit, true: 6.17 says that trying
to form a pointer to an imaginary [-1] element is unreliable,
so negative-going "past" is ruled out. What directions remain?
Sideways, at right angles to the progression of memory addresses?
(Anybody want to submit a C09 proposal for pointer-plus-complex?
Or pointer-times-pointer, yielding the cross product? ;-)

--
Er*********@sun .com

[Mark McIntyre]

On Tue, 1 Jun 2004 12:18:59 -0700, in comp.lang.c , David Mathog
<ma****@caltech .edu> wrote:

On Thu, 27 May 2004 23:28:27 +0100
Mark McIntyre <ma**********@s pamcop.net> wrote:

On Thu, 27 May 2004 14:56:52 -0700, in comp.lang.c , David Mathog
<ma****@caltech .edu> wrote:

>By "one past it" is the FAQ referring to both ends of the
>memory block or just the "high" end?
one past is (IMHO) unambiguous. If it included one before, it would say
"one past or before"...

IMHO it is ambiguous.

.... "one past" is ambiguous since the definition
The definition of past is not ambiguous. Check a dictionary - the adverbial
and prepositional meanings of "past" all relate to after, beyond etc.
of "past" is vector in nature
and an array is a vector. It points upwards. Hence its easy to define
"past"
Ie, if you were directed to "the house adjacent to and one past
the blue Victorian on Elm street" your direction of travel on that
street would determine which of the two possible houses fitting
this description is your destination.

true, but irrelevant, as in either case it means the one beyond. Only a
pathological use would attempt to refer to the point before.

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

[David Mathog]

On Tue, 01 Jun 2004 15:57:57 -0400
Eric Sosman <Er*********@su n.com> wrote:

David Mathog wrote:

However "one past" is ambiguous since the definition
of "past" is vector in nature and the direction of that vector
is not otherwise specified in the FAQ. [...]

The direction *is* specified in the FAQ, Question 6.17.
The specification is implicit, true: 6.17 says that trying
to form a pointer to an imaginary [-1] element is unreliable,
so negative-going "past" is ruled out.

You're right, it does define the direction implicitly, both by
stating that the example, containing a [-1], violates the standard and later in "while subtracting the offset". Which still doesn't
negate the point that using "one above" in that sentence would
make it unambiguous without reference to anything else,
but "one past" is ambiguous without the context of
the implicit information elsewhere in the question.

The rest of that sentence ("perhaps because the address
tried to ``wrap around'' past the beginning of some memory segment")
raises another question. If a block of memory extends up to the
highest possible address in the system (for instance, memory location 65535 on a system with 16 bit memory space and 16 bit unsigned
pointers) then the pointer value "one past" the allocated block
would be 0, and would "wrap around" exactly as described in the
FAQ 6.17 for the other direction.

in ANSI C address 0 (NULL) is special, is address -1 (top of memory)
also special?

This must come up on microcontroller s and other similar small
computing devices. (Yes, those are usually programmed in assembler
but there are C compilers for them too.)

Regards,

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