1

I am reading this C code, and I find it difficult to understand what's going on.

Here is the array:

static const char   gradient[32][4] =
{
{ 1,  1,  1,  0}, { 1,  1,  0,  1}, { 1,  0,  1,  1}, { 0,  1,  1,  1},
{ 1,  1, -1,  0}, { 1,  1,  0, -1}, { 1,  0,  1, -1}, { 0,  1,  1, -1},
{ 1, -1,  1,  0}, { 1, -1,  0,  1}, { 1,  0, -1,  1}, { 0,  1, -1,  1},
{ 1, -1, -1,  0}, { 1, -1,  0, -1}, { 1,  0, -1, -1}, { 0,  1, -1, -1},
{-1,  1,  1,  0}, {-1,  1,  0,  1}, {-1,  0,  1,  1}, { 0, -1,  1,  1},
{-1,  1, -1,  0}, {-1,  1,  0, -1}, {-1,  0,  1, -1}, { 0, -1,  1, -1},
{-1, -1,  1,  0}, {-1, -1,  0,  1}, {-1,  0, -1,  1}, { 0, -1, -1,  1},
{-1, -1, -1,  0}, {-1, -1,  0, -1}, {-1,  0, -1, -1}, { 0, -1, -1, -1},
};

and it's 32*4, this is another part of the code that trying to access this array:

const char * g0000 = gradient[Indice (x1, y1, z1, t1)];

Indice is a function that returns an int. So what is this g0000 (I know it's a pointer), say Indice returns 1, what is the value g0000 holds? I mostly code in C# to my understanding if you want to access multidimensional array you would need several arguments, but here is only one, I am really confused...

Regolith
  • 2,944
  • 9
  • 33
  • 50
Anna
  • 13
  • 2

3 Answers3

3

The type of gradient is static const char[32][4] i.e. a two dimensional array of chars. When you dereference it twice using [] operator you get a char.

But in this case when you deference only once you get const char[4] which can be decayed into const char* and assigned to g0000.

Precisely, g0000 will hold the address of the 2nd sub-array if Indice(x1, y1, z1, t1) returned 1.

Ajay Brahmakshatriya
  • 8,993
  • 3
  • 26
  • 49
2

The way a static multidimensional array is stored in memory as a 1D array (in C).

For example if you have the following array:

int ray[2][3] = {{1, 2, 3}, {4, 5, 6}};

the memory allocation is exactly the same as in:

int ray[6] = {1, 2, 3, 4, 5, 6};

This can be shown by the following snippet:

int ray[2][2] = {1, 2, 3, 4};
int *rayP = (int *) ray;
printf("%d\n", rayP[3]);     //PRINTS 4

The reason that you can use multiple indices is just C making your life easier in using it as a 2D array abstraction.

So if you access the element ray[x][y] of an array ray[a][b], the element you actually access is ray[x * b + y], even though C won't let you do that to keep the abstraction clear.

Instead, if you try to access element ray[x] directly, it will return you &ray[x * b], which is exactly what you want here:

A pointer to the beginning of the desired sub-array, which you can treat as an array.

Kostas
  • 4,061
  • 1
  • 14
  • 32
  • "multidimensional array is stored in memory in C is as a 1D array", and then "multidimensional array is stored in memory in C is as a 1D array"-- this seems a little misleading, because with `ray[2][2]`, `int *rayP = &ray[0];`, `rayP[3]` is undefined behavior. – ad absurdum Dec 06 '17 at 04:34
  • 2
    Misleading because: 1) 2d arrays of `int` are arrays of arrays, not arrays of `int`, and 2) you can't legally access a 2d array as if it were a 1d array. – ad absurdum Dec 06 '17 at 04:39
  • A snippet proves nothing. Quotes from the standard on the other hand do. – Ajay Brahmakshatriya Dec 06 '17 at 04:39
  • You are absolutely right David. The abstraction that is created by C is that a 2D array for example is an array of arrays, so it's kind of tricky to access the memory as it actually is written. When running `*rayP = &ray[0];` in your example, you get a compiler error, as `&ray[0]` is treated as an array of arrays of 3 elements `int(*)[3]`, while `rayP` is treated as `int *`. You need to cast it to an `int *` first for you to access the memory successfully. – Kostas Dec 06 '17 at 04:44
  • 1
    Note that there is debate over whether this access is legal (although everyone agrees that after `int *rayP = (int *)&ray;` , then `rayP[3]` is OK) – M.M Dec 06 '17 at 04:48
  • 2
    @M.M -- "although everyone agrees" -- that looks like a strict aliasing violation, since `int *` and `int (*)[]` are not compatible types. – ad absurdum Dec 06 '17 at 04:51
  • 3
    @DavidBowling Neither of those types are relevant to strict aliasing. The rule is that an object of type `T` may only be accessed by an lvalue of type `T` (plus some exceptions). In this code there is access of `int` objects by lvalue of type `int` and nothing else. There are no `int *` objects being aliased, and there is no access of array objects (which is not even possible in C, only the array elements may be accessed) – M.M Dec 06 '17 at 04:57
  • 1
    @Stargateur the question you link to is about accessing out of bounds of an array, which is nothing to do with strict aliasing. Using bold typeface does not change wrong statements into correct ones . – M.M Dec 06 '17 at 05:25
  • @M.M -- I concede that I was wrong about strict aliasing here. My original point was not about this, but about the dangers of thinking of a 2d array of `int` as a big 1d array of `int` instead of as a 1d array of 1d arrays of `int`. – ad absurdum Dec 06 '17 at 05:50
  • @DavidBowling maybe the discussion here can help. We have tried to look over as many factors as possible – Ajay Brahmakshatriya Dec 06 '17 at 08:23
  • 1
    @Stargateur: The relevant part of the standard is C 2011 [N1570] 6.3.2.3 7: “A pointer to an object type may be converted to a pointer to a different object type. If the resulting pointer is not correctly aligned for the referenced type, the behavior is undefined.…” So converting the pointer is legal if the alignment is satisfied, which of course it would be when going from an array of `int` to `int`. Using the pointer is not defined. – Eric Postpischil Dec 06 '17 at 09:04
  • @EricPostpischil -- "Using the pointer is not defined" are you saying that `rayP[3]` is an illegal access attempt (and UB), [in disagreement with M.M's comment](https://stackoverflow.com/users/1505939/m-m)? – ad absurdum Dec 06 '17 at 11:51
  • @DavidBowling: (a) `rayP[3]` is undefined because the C standard does not define what the resulting value of converting `int (*)[3]` to `int *` is other than that, when converted back, it must compare equivalent to the original pointer. (b) I do not see any comment by M.M. that says `rayP[3]` is legal. There is one that says there is debate, which is literally true, one that says the aliasing rules are not applicable here, which is true, one that says `ray` may be converted to `int *`, which is true, and one that says Stargateur’s link speaks to out-of-bounds access, which is true. – Eric Postpischil Dec 06 '17 at 13:07
  • @EricPostpischil -- in the comment I linked: "although everyone agrees that after `int *rayP = (int *)&ray;` , then `rayP[3]` is OK)". – ad absurdum Dec 06 '17 at 13:09
  • @DavidBowling: Your link was to M.M.’s user profile, not to a comment. But now I see it. Note that that is a different statement. It says not that `rayP[3]` after the original `int *rayP = (int *) ray;` is fine but that `rayP[3]` after `int *rayP = (int *)&ray;` is fine. However, both are not defined, for the same reason, that C does not define the value that results from converting either `int (*)[3]` or `int (*)[2][3]` to `int *` other than that it must convert back to something equivalent to the original. On the other hand, `int *rayP = (int *)*ray;` would produce a usable value. – Eric Postpischil Dec 06 '17 at 13:18
  • @EricPostpischil -- sorry about the mislink; need coffee. My original comment used `int *rayP = &ray[0][0];` (forgot the second `[0]` in the original) to avoid what looked like UB due to dereferencing `rayP` in `int *rayP = (int *) ray;` followed by `printf("%d\n", rayP[3]);` from this answer. I should never have mentioned strict aliasing. – ad absurdum Dec 06 '17 at 13:45
  • @EricPostpischil By your logic , `int *x = malloc(sizeof(int)); x[0] = 0;` is UB because the result of converting `void *` to `int *` is undefined other than that it must give the same value when converted back to `void *`. I feel this is an impractical interpretation of the standard that you take; I follow [this answer](https://stackoverflow.com/a/25570179/1505939) (and not the answer by Anton Savin on the same thread). – M.M Dec 06 '17 at 20:40
  • @M.M: `malloc` is defined to return space for an object of the requested size (if it succeeds), so we know it returns a pointer that may be converted to a pointer to the object. Then rule for storing a value into an object having no declared type (6.5 6) allows us to assign a value to `x[0]`, after which the rule is clear that there is an `int` there and not an object of some other type. Effectively, the specification of `malloc` requires that it be possible to convert the `void *` returned by `malloc` to a pointer to an type that could have been created by that `malloc` (is the right size). – Eric Postpischil Dec 06 '17 at 21:09
  • @M.M: But that does not mean that **any** `void *` can be so converted. The standard makes provision for pointers that compare equal having different representations, for example. Pointers may have different information in them depending on their history. A pointer converted from a `int (*)[2]` might have different data than a pointer converted from `int *`, even if they theoretically pointed to the same byte. So converting a pointer to an array to a pointer to an `int` might not include the data that C implementation needs to work properly. – Eric Postpischil Dec 06 '17 at 21:13
  • @M.M: Additionally, the optimizer might transform the code in ways that preserve valid pointer uses but that break invalid pointer uses. – Eric Postpischil Dec 06 '17 at 21:14
  • @EricPostpischil if you agree that they theoretically point to the same byte, then they can be used to access memory at that location, so long as there is not a strict aliasing violation – M.M Dec 06 '17 at 21:17
  • @M.M: I wrote “**pointed** to”, not “point to”. An `int *` converted to `float *` is not guaranteed to point to anything at all. If `A` is an `int (*)[2]` and `B` is an `int *`, and `B` was created by `B = &(*A)[0]`, so `B` points to the first element of the array that `A` points to, so they point to objects (an array and an `int`) that start at the same byte, and then we do `float *fA = (float *) A` and `float *fB = (float *) B`, there is no guarantee that `fA` and `fB` have the same values (or compare equal) or point to the original byte. All we know is that converting back works. – Eric Postpischil Dec 06 '17 at 21:22
0

That wouldn't be unreasonable to assume Indice() returns the index of the row in gradient that holds the 4 values x1, y1, z1 and t1.

gradient being const char[32][4], say Indice returns an index i used in gradient

gradient[i]

is an address that points to a char ; the calculated address of gradient[i]

g0000 = gradient[i]

is 

gradient + ( i*4*sizeof(gradient[0][0]) )

that is, it points to the first element of gradient at address &gradient[i][0]

In C there is no automatic control of array out of bounds indexes, and in that array, accessing [R][C] is like accessing [R*4+C], meaning while g0000 points to a [4] char area, you might try to access beyond that 4-limit, (e.g. [i][5]) and would access the next row (since it's [i*4+5] or [i+1][1]).

However accessing the array out of bounds leads to undefined behavior (if i+1 > 31 in that case, since an array [X] goes from [0] to [X-1]).

Déjà vu
  • 28,223
  • 6
  • 72
  • 100
  • 1
    `gradient[i]` is an array, not a pointer. Also your address expression is wrong, `x[y]` is equivalent to `*(x + y)`, there are no additional sizeof steps – M.M Dec 06 '17 at 04:49