One-dimensional access to a multidimensional array: is it well-defined behaviour?

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 c99 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.

Solution 1:

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].

Solution 2:

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.

Solution 3:

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).