One-dimensional access to a multidimensional array

Question

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.

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

Answer 2

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

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

Answer 4

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.