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

D

4

26

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:

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

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.

Debug answered 9/6, 2011 at 9:48 Comment(7)

Posting this as a comment since i'm not sure. AFAIK arrays are guaranteed to be continuous in memory whereas structs might have padding between those members. If you look at the assembler code of the array access you should be able to see that the operation performed on the [][] access is the same as *(array + x * index + y). – Janinejanis 9/6, 2011 at 9:52

I am no language-lawyer so I will not add an answer, however, this is exactly how it works for raster imaging. Basically all you have is bytes and you know how many bytes are in a row. To go to the next row you have to offset the original pointer with the number of rows*width. So in the case of well-defined data, I would say this is perfectly fine coding. – Shorten 9/6, 2011 at 9:52

@Wouter: Oh, I have no doubt that it is fine! I use this principle every day, and so does everyone else. I'm purely asking from a language-lawyer pedantry point of view! – Debug 9/6, 2011 at 9:57

@Oli: Well, lawyers are horrible developers. In memory, the array has no padding and, therefore, indexing multi-dimensional arrays as single dimensional will always work. Your pointer increment is determined from the base array pointer so arr[10] must be arr + 10 * sizeof(arr) which is in the specifications I am sure. This means arr[1][5] with the second dimension always 5 long is: arr + 1 * 5 * sizeof(arrType) + 5 * sizeof (arrType)... – Shorten 9/6, 2011 at 10:1

I don't have the time to write it up, but C99 6.5.2.1 paragraphs 3 and 4 seem to make this well defined – Worser 9/6, 2011 at 10:6

@Hasturkun: Yes, I've been considering those paragraphs. I'm not sure it directly defines this though; all it says is that the name of an N-dimensional array decays to a pointer to an (N-1)-dimensional array. So in my example, mtx is actually an int[5][3], but it decays to an int(*)[3]. – Debug 9/6, 2011 at 10:12

but what about int *p = (int*)&mtx; ? – Holmgren 19/7, 2022 at 11:42

H

13

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.

Hortensehortensia answered 9/6, 2011 at 13:15 Comment(9)

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 – Chinese 9/6, 2011 at 15:40

@Pascal: C99 allows type punning through unions - this is explicitly mentioned in footnote 82 (p. 73), which was added with TC3 – Mcquoid 10/6, 2011 at 8:4

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. – Debug 10/6, 2011 at 14:40

Note that Appendix J.2 in the standard explicitly lists this kind of OOB multi-dimensional array access as an example of UB. – Hortensehortensia 10/6, 2011 at 16:27

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. – Gravettian 21/7, 2016 at 5:55

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. – Gravettian 28/7, 2016 at 11:8

@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. – Hortensehortensia 17/6, 2017 at 13:30

I assume you are saying the only reason for this being UB is aliasing. If that's true, how about using a void pointer to circumvent aliasing rules? Would it be legal to pass (void *)&a[0][0] (considering a is int a[10][10]) to a function which receives a void pointer as argument and then casts it into int * and accesses the 2D array as 1D? I'm asking this because I believe there must be a way for making 1D access legal, given that the C standard guarantees multidimensional arrays are contiguous. – Bride 30/10, 2021 at 19:56

I decided to create a new question related to my comment: #69785590 – Bride 31/10, 2021 at 9:7

M

18

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

Mcquoid answered 9/6, 2011 at 10:46 Comment(7)

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? – Debug 9/6, 2011 at 10:56

@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 – Mcquoid 9/6, 2011 at 11: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? – Debug 9/6, 2011 at 11:34

@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 – Mcquoid 9/6, 2011 at 12:18

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. – Hortensehortensia 9/6, 2011 at 12:19

@Christoph: Yes, that's what I was afraid of! Thanks for your input, and +1. – Debug 9/6, 2011 at 17:21

I'm not sure if (int *)((char *)mtx + 5 * sizeof (int)) is defined. mtx will be a pointer of array of 3 ints which will be overflown by +5*.... The better expression would be (int *)((char *)&mtx + 5 * sizeof (int)) – Holmgren 25/10, 2021 at 8:51