By Oliver Charlesworth


2011-06-09 09:48:40 8 Comments

I imagine we all agree that it is considered idiomatic C to access a true multidimensional array by dereferencing a (possibly offset) pointer to its first element in a one-dimensional fashion, e.g.:

void clearBottomRightElement(int *array, int M, int N)
{
    array[M*N-1] = 0;  // Pretend the array is one-dimensional
}


int mtx[5][3];
...
clearBottomRightElement(&mtx[0][0], 5, 3);

However, the language-lawyer in me needs convincing that this is actually well-defined C! In particular:

  1. Does the standard guarantee that the compiler won't put padding in-between e.g. mtx[0][2] and mtx[1][0]?

  2. Normally, indexing off the end of an array (other than one-past the end) is undefined (C99, 6.5.6/8). So the following is clearly undefined:

    struct {
        int row[3];           // The object in question is an int[3]
        int other[10];
    } foo;
    int *p = &foo.row[7];     // ERROR: A crude attempt to get &foo.other[4];
    

    So by the same rule, one would expect the following to be undefined:

    int mtx[5][3];
    int (*row)[3] = &mtx[0];  // The object in question is still an int[3]
    int *p = &(*row)[7];      // Why is this any better?
    

    So why should this be defined?

    int mtx[5][3];
    int *p = &(&mtx[0][0])[7];
    

So what part of the C standard explicitly permits this? (Let's assume for the sake of discussion.)

EDIT

Note that I have no doubt that this works fine in all compilers. What I'm querying is whether this is explicitly permitted by the standard.

4 comments

@R.. 2011-06-09 13:15:42

The only obstacle to the kind of access you want to do is that objects of type int [5][3] and int [15] are not allowed to alias one another. Thus if the compiler is aware that a pointer of type int * points into one of the int [3] arrays of the former, it could impose array bounds restrictions that would prevent accessing anything outside that int [3] array.

You might be able to get around this issue by putting everything inside a union that contains both the int [5][3] array and the int [15] array, but I'm really unclear on whether the union hacks people use for type-punning are actually well-defined. This case might be slightly less problematic since you would not be type-punning individual cells, only the array logic, but I'm still not sure.

One special case that should be noted: if your type were unsigned char (or any char type), accessing the multi-dimensional array as a one-dimensional array would be perfectly well-defined. This is because the one-dimensional array of unsigned char that overlaps it is explicitly defined by the standard as the "representation" of the object, and is inherently allowed to alias it.

@Pascal Cuoq 2011-06-09 15:40:45

Type-punning through unions is no more defined than through pointer casts, but GCC's documentation does beyond the standard for the former and guarantees that the program will do what the programmer expects. "Even with -fstrict-aliasing, type-punning is allowed, provided the memory is accessed through the union type." gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

@Christoph 2011-06-10 08:04:47

@Pascal: C99 allows type punning through unions - this is explicitly mentioned in footnote 82 (p. 73), which was added with TC3

@Oliver Charlesworth 2011-06-10 14:40:38

I was hoping that someone would answer with "No no! You're wrong! Look the standard explicitly allows it here...", but apparently not. So I've accepted this answer, as this phrases the issue (about aliasing) most succinctly.

@R.. 2011-06-10 16:27:52

Note that Appendix J.2 in the standard explicitly lists this kind of OOB multi-dimensional array access as an example of UB.

@2501 2016-07-21 05:55:30

I agree with the answer except with the part that claims that character types get away with it. Specifically when a character pointer is incremented to point to another object, in this case another element of the outer array. Can you elaborate or provide a Standard citation. 6.5 doesn't make any exceptions for char. Thanks.

@2501 2016-07-28 11:08:54

I stumbled again upon this answer accidentally. I would really appreciate if you could respond to my previous comment, or at least say that you don't want to if that is the case. Thank you.

@R.. 2017-06-17 13:30:24

@2501: It's a consequence of Representaton of Types (overlaid unsigned char [sizeof T]) and application of equivalence/convertability of pointers between representation, struct, and struct members. In short, the same unsigned char * legitimately points to both an element of the representation array for the whole struct, and an element of the member array inside the struct. By virtue of the former, a wider range of arithmetic is valid.

@Christoph 2011-06-09 10:46:26

All arrays (including multidimensional ones) are padding-free. Even if it's never explicitly mentioned, it can be inferred from sizeof rules.

Now, array subscription is a special case of pointer arithmetics, and C99 section 6.5.6, §8 states clearly that behaviour is only defined if the pointer operand and the resulting pointer lie in the same array (or one element past), which makes bounds-checking implementations of the C language possible.

This means that your example is, in fact, undefined behaviour. However, as most C implementations do not check bounds, it will work as expected - most compilers treat undefined pointer expressions like

mtx[0] + 5 

identically to well-defined counterparts like

(int *)((char *)mtx + 5 * sizeof (int))

which is well-defined because any object (including the whole two-dimensional array) can always be treated as a one-dimensinal array of type char.


On further meditation on the wording of section 6.5.6, splitting out-of-bounds access into seemingly well-defined subexpression like

(mtx[0] + 3) + 2

reasoning that mtx[0] + 3 is a pointer to one element past the end of mtx[0] (making the first addition well-defined) and as well as a pointer to the first element of mtx[1] (making the second addition well-defined) is incorrect:

Even though mtx[0] + 3 and mtx[1] + 0 are guaranteed to compare equal (see section 6.5.9, §6), they are semantically different. For example, the former can't be dereferenced and thus does not point to an element of mtx[1].

@Oliver Charlesworth 2011-06-09 10:56:48

I agree with most of what you said. I'm not sure I can agree with the notion that (mtx[0] + 3) + 2) is valid, because all out-of-bounds pointer additions could be recursively expressed as (((p+1)+1)+1) etc. And if it were well-defined to express them this way, then what would be the point of 6.5.6/8?

@Christoph 2011-06-09 11:26:09

@Oli: C arithmetics is not associative - (a+b)+c is not necessarily identical to a+(b+c); the crux of the matter is that in case of multi-dimensional arrays, a pointer can 'belong' to two arrays at the same time, and pointer arithmetic does not keep track of the originating array, so you only have to validate each subexpression; as far as I can tell, it is indeed possible to iterate over a multi-dimensional array by single-step increments

@Oliver Charlesworth 2011-06-09 11:34:26

@Christoph: I agree with your point about associativity. I guess the only point remaining is whether it's valid to alias an object with a pointer to the one-past-the-end element for the previous object. For example, in my struct example, is the behaviour well-defined for an implementation that guarantees no padding between row and other?

@Christoph 2011-06-09 12:18:44

@Oli: upon re-reading section 6.5.6 and some further meditation, I changed my mind ;) pointers past the last element of an array are 'special' and can't be used in the way I originally described

@R.. 2011-06-09 12:19:06

Yes the pointer addition is what's potentially problematic. Note that it's not a problem if the base type is a char type, since then any pointer into it is also a pointer into the representation array, which is an array of type unsigned char [sizeof whole_multi_dim_array], and thus all the arithmetic is valid.

@Oliver Charlesworth 2011-06-09 17:21:32

@Christoph: Yes, that's what I was afraid of! Thanks for your input, and +1.

@nimrodm 2011-06-09 10:19:12

My understanding of the C99 standard is that there is no requirement that multidimensional arrays must be laid out in a contiguous order in memory. Following the only relevant information I found in the standard (each dimension is guaranteed to be contiguous).

If you want to use the x[COLS*r + c] access, I suggest you stick to single dimension arrays.

Array subscripting

Successive subscript operators designate an element of a multidimensional array object. If E is an n-dimensional array (n ≥ 2) with dimensions i × j × . . . × k, then E (used as other than an lvalue) is converted to a pointer to an (n − 1)-dimensional array with dimensions j × . . . × k. If the unary * operator is applied to this pointer explicitly, or implicitly as a result of subscripting, the result is the pointed-to (n − 1)-dimensional array, which itself is converted into a pointer if used as other than an lvalue. It follows from this that arrays are stored in row-major order (last subscript varies fastest).

Array type

— An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. 36) Array types are characterized by their element type and by the number of elements in the array. An array type is said to be derived from its element type, and if its element type is T , the array type is sometimes called ‘‘array of T ’’. The construction of an array type from an element type is called ‘‘array type derivation’’.

@Wouter Simons 2011-06-09 11:00:07

Exactly, so if you treat a contiguous memory buffer as multidimensional array, it is fine, but the other way around it might not be fine. That sounds about right to me.

@Oliver Charlesworth 2011-06-09 11:06:25

@nimrodm: Your interpretation of the standard largely matches mine. (Which is reassuring, I guess!)

@nimrodm 2011-06-09 11:58:04

@oli - This sort of wording is what you get when you form a committee :) If I were you I would still use multidimensional arrays and just add some sort of static assert to verify that they are contiguous.

@R.. 2011-06-09 12:15:56

The first sentence is blatantly false. The layout in memory is exactly determined by the semantics of sizeof and pointer arithmetic. It's only due to the aliasing rules that this usage is undefined, and thus only for non-char types.

@RedX 2011-06-09 12:20:46

I disagree about the mutli-dimensions not requiring to be contiguous. An array with 3 elements inside an array with 3 elements (arr[3][3]) will have to be contiguous to match the description else the second "array" (the one containing the other 3 arrays) would not be allowed to call itself an array since it's layout would not be contiguous. The "inner" array (arr[3]) has array of X whereas the "outer" array is an array of X[sizeof("inner array")].

@detly 2011-06-09 12:47:17

@RedX - are you sure the "outer" array is not, in fact, an array like X[sizeof("inner array type"*)]? (Genuine question, I can't remember.)

@R.. 2011-06-09 13:16:41

@detly: The "outer" array in OP's example is an array of 5 int [3] objects, not 15 int objects.

@detly 2011-06-10 01:29:23

@R.. - no, I get that — the asterisk meant "pointer to" ie. my question was whether the outer array is actually implemented as an array of pointers to the start of each inner array, or as an array of entire int[3] objects.

@R.. 2011-06-10 01:50:02

It's the latter - an array of int[3] objects.

@curiousguy 2018-07-02 09:42:34

@detly Arrays are NOT pointers!

@AProgrammer 2011-06-09 10:12:55

  1. It is sure that there is no padding between the elements of an array.

  2. There are provision for doing address computation in smaller size than the full address space. This could be used for instance in the huge mode of 8086 so that the segment part would not always be updated if the compiler knew that you couldn't cross a segment boundary. (It's too long ago for me to remind if the compilers I used took benefit of that or not).

With my internal model -- I'm not sure it is perfectly the same as the standard one and it is too painful to check, the information being distributed everywhere --

  • what you are doing in clearBottomRightElement is valid.

  • int *p = &foo.row[7]; is undefined

  • int i = mtx[0][5]; is undefined

  • int *p = &row[7]; doesn't compile (gcc agree with me)

  • int *p = &(&mtx[0][0])[7]; is in the gray zone (last time I checked in details something like this, I ended up by considering invalid C90 and valid C99, it could be the case here or I could have missed something).

@Oliver Charlesworth 2011-06-09 10:17:34

You're right, I got the syntax wrong for int *p = &row[7]. I will edit my question.

@Oliver Charlesworth 2011-06-09 10:20:06

What I'm really looking for is an argument based on the wording in the standard...

Related Questions

Sponsored Content

16 Answered Questions

41 Answered Questions

[SOLVED] How can I create a two dimensional array in JavaScript?

9 Answered Questions

[SOLVED] How to Sort Multi-dimensional Array by Value?

2 Answered Questions

11 Answered Questions

[SOLVED] Syntax for creating a two-dimensional array

9 Answered Questions

1 Answered Questions

5 Answered Questions

[SOLVED] Multidimensional Array [][] vs [,]

5 Answered Questions

[SOLVED] Can "sizeof(arr[0])" lead to undefined behavior?

3 Answered Questions

[SOLVED] Does C99 guarantee that arrays are contiguous?

Sponsored Content