How does C know the bounds of a multi-dimensional array?

Question

Coming from Python, if C does not have array bounds, how does it know where a[1] starts?

int a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
b = a[1][1];

Answer 1

C knows the bound of an array at compile time, as opposed to Python which knows the bound of an array at runtime.

The compiler basically rewrite array access into pointer operations. It knows at compile time that the size of a the first dimension of the array is int[3], i.e. sizeof(int)*3. So:

b = a[x][y];

Is basically rewritten to

b = *(a + x * 3 + y);

So the knowledge about the dimension (the number 3) is encoded into the code, even if the dimensions are not explicitly available at runtime. Arguably, arrays are purely a compile-time construct in C.

Answer 2

C stores your 2D array as a contiguous bloc of 9 integers:

1 2 3 4 5 6 7 8 9 

C uses compile time type and dimension information for generating the pointer arithmetic to access the elements.

In your example a[i] is a pointer to the start of the i-th row. Knowing that's a is a 2D array of int, and knowing that the last dimension has a size of 3, it can determine that a[i] is an array of 3 int starting at the i*3 th integer in a.

1 2 3 4 5 6  | 7 8 9 |
             ^
             Start of a[2]

Similarly, For accessing a[i][j] the compiler will generate code that uses the 3*i+j th integer in a.

However C consider that the programmer knows what he's doing. It will not check bounds. If i would be 5 and j 120, the code would execute blindly, causing undefined behaviour such as for example memory corruption, core dumps, and other bad things.

So if bounds are important for your algorithm, you should either use fixed bounds, or pass the bounds as extra parameter to your function.

If you'd use C++ instead of C, you could use vectors, which are dynamic arrays that know their size ( but it would still be up to you to check the bounds)

Answer 3

C knows because it knows the size of an int. So array[1] starts one int size up from array[0]. The same applies to array[1][1]

| size of an int |  
01011101 01101110 10...  
^                 ^  
array[0]          array[1]  

Note that the size of an int is dependant on the platform, this was just an example.

Answer 4

C knows where the next storage location for a given type is for the packing at the time of declaration so if you have an array of 16 bit integers the 'next' index in a single dimension array will be, usually, two bytes higher address but on some machines and with some compiler settings it might be the first 2 bytes of the next 64 bit word.
For a 2D array the next in the other direction normally would be the length of the single, lower, dimension as declared times the step for adjacent members of the lower order array, possibly plus some padding. For a 3D array the next element in the 3rd Dimension would normally be the size of the lower order 2D array aways, again possibly plus some padding.

The good news is that the compiler takes care of this if you use the normal indexing mechanisms, the bad is that, since the mechanism is not specified in the ANSI specification, it is up to the compiler manufacturer and how this is done and/or controlled. If you decide to try to access data in such structures directly then you are likely to have major issues. As a result of this ambiguity storing such data or exchanging it between programs that are possibly compiled with a different compiler, or even the same compiler but with different settings, on a single machine become a nightmare and given issues such as base component size and endianness exchanging data between machines or even times becomes even more so.

This is the reason that good data storage and exchange specifications are so verbose and often include the need to pack data in specific structures.

I had an issue several years ago where the data was being received as a bitfield 24 bits long, (in a telecommunications application), but on the Solaris machine we were using, with the default compiler, rather than being 3 bytes long this structure was 192 bytes. This was because, for speed, even an int:1 was stored in a 64 bit word. Several hours of researching the compiler settings showed that controlling this changed between versions of the compiler and we eventually switched to gcc instead. See the gcc manual for type attributes here for some more information.

Also be aware that C does not of itself have any array boundaries and not all compilers check against the array size. As a result if an array is defined as being int MyArray[8][12][20]; in one module but another shows it as extern int MyArray[]; then the second module will happily set MyArray[50000] = 0 with resulting problems.