Pointers and matrices
Author Message
Pointers and matrices

Hi fellows,

This is REALLY bugging me. Consider

#define N 4

and

int a[N][N], as[(N*(N+1)/2];

scanf("%d", &a[i][j]);

works fine and

scanf("%d", (a + j + i*N));

does not work at all.

Thanks,
Arnaldo

Mon, 30 Aug 2004 22:16:47 GMT
Pointers and matrices

Quote:

>   scanf("%d", &a[i][j]);

> works fine and

>   scanf("%d", (a + j + i*N));

> does not work at all.

`a + j + i*N' is the same as `&a[j + i*N]'. You probably meant
`a[0] + j + i*N'.

-------------+
Sven Sandberg

Mon, 30 Aug 2004 22:22:46 GMT
Pointers and matrices

Quote:
> Hi fellows,
> This is REALLY bugging me. Consider
>   #define N 4
> and
>   int a[N][N], as[(N*(N+1)/2];
>   scanf("%d", &a[i][j]);
> works fine and
>   scanf("%d", (a + j + i*N));
> does not work at all.

This is because &a[i][j] is not equal to a+j+i*N.
a is of type int a[N][N], when you use this as an rvalue it is used
as if it were of type int (*a)[N], i.e. a pointer to an array of N
ints.
This means that a+j points to j*N ints after a, and a+j+i*N points to
(j+i*N)*N ints after a, i.e. j*N + i*N*N ints after a.
You are apparently thinking that a would be of type int *a above,
which would mean that a+j would point to j ints after a, and a+j+i*N
would point to j+i*N ints after a. This is not the case.
It can be made to work by telling the C compiler that a's type is
understood to be something else. To do this, cast a into (int *):
scanf("%d", ((int *)a + j + i*N));
This may or may not generate Undefined Behaviour. I don't know enough
C to be sure about that.

--

| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste       W++ B OP+                     |
\----------------------------------------- Finland rules! ------------/
"And according to Occam's Toothbrush, we only need to optimise the most frequent
instructions."
- Teemu Kerola

Mon, 30 Aug 2004 22:23:45 GMT
Pointers and matrices

Quote:

> Hi fellows,

> This is REALLY bugging me. Consider

>   #define N 4

> and

>   int a[N][N], as[(N*(N+1)/2];

I want to add that this is not correct,

N*N != N*(N+1)/2

Jirka

Mon, 30 Aug 2004 22:39:12 GMT
Pointers and matrices

Quote:

> Hi fellows,

> This is REALLY bugging me. Consider

>   #define N 4

> and

>   int a[N][N], as[(N*(N+1)/2];

There are mismatched parentheses in the declaration of 'as'. Since you
don't use 'as' below, why declare it at all?

Quote:

>   scanf("%d", &a[i][j]);

> works fine and

>   scanf("%d", (a + j + i*N));

I find constructing a table of each step in the evaluation quite helpful.
(A monospaced font will help the columns line up.)

STEP  EXPRESSION     C TYPE    TYPE IN ENGLISH
1     a              int[4][4] "array 4 of array 4 of int"
2     [implicit conversion to int(*)[4] before addition]
3     a + j          int(*)[4] "pointer to array 4 of int"
4     a + j + i*N    int(*)[4] "pointer to array 4 of int"

Oops, here we are at the end, and we still have type "pointer to array 4 of
int". Scanf is expecting type "pointer to int". Therefore we have a
dereferencing missing.

a is of type int[4][4] "array 4 of array 4 of int" which converts to
int(*)[4] "pointer to array 4 of int".

a + j is a pointer to the (j+1)th element of a; ie. the (j+1)th array of
four ints. Now you go hopelessly wrong when adding on i*N.

What you want is

*(a + i) + j

That is, construct a pointer to the (i+1)th array of 4 ints, dereference
it, then construct a pointer to the (j+1)th int element of that array.

STEP  EXPRESSION     C TYPE    TYPE IN ENGLISH
1     a              int[4][4] "array 4 of array 4 of int"
2     [implicit conversion to int(*)[4] before addition]
3     a + i          int(*)[4] "pointer to array 4 of int"
4     *(a + i)       int[4]    "array 4 of int"
5     [implicit conversion to int* before addition]
6     *(a + i) + j   int *     "pointer to int"

PS. Some might suggest you use (*a + i*N + j). But as far as I can tell
that has undefined behaviour since it constructs a pointer outside the
bounds of the array *a.

--
Simon.

Tue, 31 Aug 2004 04:05:33 GMT
Pointers and matrices

Quote:

> > Hi fellows,

> > This is REALLY bugging me. Consider

> >   #define N 4

> > and

> >   int a[N][N], as[(N*(N+1)/2];

> > Now I ask, why

> >   scanf("%d", &a[i][j]);

> > works fine and

> >   scanf("%d", (a + j + i*N));

> > does not work at all.

> This is because &a[i][j] is not equal to a+j+i*N.
> a is of type int a[N][N], when you use this as an rvalue it is used
> as if it were of type int (*a)[N], i.e. a pointer to an array of N
> ints.
> This means that a+j points to j*N ints after a, and a+j+i*N points to
> (j+i*N)*N ints after a, i.e. j*N + i*N*N ints after a.
> You are apparently thinking that a would be of type int *a above,
> which would mean that a+j would point to j ints after a, and a+j+i*N
> would point to j+i*N ints after a. This is not the case.
> It can be made to work by telling the C compiler that a's type is
> understood to be something else. To do this, cast a into (int *):
> scanf("%d", ((int *)a + j + i*N));
> This may or may not generate Undefined Behaviour. I don't know enough
> C to be sure about that.

I was wandering this too. It seems Lawrence has provided an answer in

- Show quoted text -

Quote:
> >First, the c bit (the OT stuff is later for background info). Are static
> >arrays guaranteed to have contiguous memory adresses? for example:

> The bytes within any object of any type irrespective of how it is
> allocated are requored by C to be contiguous, at least from the
> perspective of the program.

> >double foo[10][10];

> >if (&foo[6][0] == 1+ &foo[5][9]) printf("yes!\n"); else printf("no.\n");

> Yes, that is required to be true, but it only works because C
> allows you to create a pointer to 1 place past the end of an array.

> >For me, on my system, this appears true. But I am in a situation where I
> >like to write ISO C because my code has to run on several
> >implementations, all of which I cannot test. So in summary, if I define
> >foo as above, can I simply refer to foo as a continuous portion of
> >memory "100*sizeof double" bytes long?

> Yes, with some caveats. C recognises that objects have bounds. C has
> no multidimensional arrays and foo above is an array of arrays which
> is important here. foo is an array of 10 elements. Each of those
> elements is an array of 10 doubles. So foo[5] selects the 6th element
> of foo. (foo[5])[9] (which can be shortened to foo[5][9]) selects to
> 10th element of foo[5]. &foo[5][9]+1 creates a pointer to 1 place past the
> end of the array foo[5] so any attempt to dereference it invokes
> undefined behaviour, even though it is pointing at a valid object.
> The reason is that pointers in C are allowed to contain boundary
> information and &foo[5][9]+1 violates the bounds of the array foo[5].

So given...

int a[N][N];

dereferencing the expression...

(int *)a + j + i*N

would seem to potentially invoke undefined behaviour because of the access
via an inappropriate pointer. Even if the calculation is seemingly correct,
the "boundary" and perhaps other information of the pointers formed from
(a) and (a[i]) may be required for indexing to work correctly.

Although I'd love to see an implementation, other than the Deathstation,
where the pointer arithmetic didn't work. :)

--
Peter

Thu, 02 Sep 2004 18:56:09 GMT
Pointers and matrices

Quote:

> Joona I Palaste

> > scanf("%d", ((int *)a + j + i*N));
> > This may or may not generate Undefined Behaviour. I don't
> > know enough C to be sure about that.

> I was wandering this too. It seems Lawrence has provided an

>: Lawrence Kirby explained in another thread:
>:
>: dereferencing the expression...
>:
>:   (int *)a + j + i*N
>:
>: would seem to potentially invoke undefined behaviour because
>: of the access via an inappropriate pointer. Even if the
>: calculation is seemingly correct, the "boundary" and perhaps
>: other information of the pointers formed from a) and (a[i])
>: may be required for indexing to work correctly.

> Although I'd love to see an implementation, other than the
> Deathstation, where the pointer arithmetic didn't work. :)

Even though I seldom doubt Lawrence's opinion, I would very
much like to know where the standard mentions the possibility
for pointers to contain boundary information. At least I never
heard of these boundery-aware pointers, and thus far I could
not find anything in them in the standard either.

It might be something like the 'drive-through penalty' in
today's Formula 1 Grand Prix though. I've watched the GP for
over twenty years, but never heart of it, and neither did the
experienced commentator on Dutch TV :)

willem

Thu, 02 Sep 2004 19:52:11 GMT
Pointers and matrices

Quote:

... snip ...

> Even though I seldom doubt Lawrence's opinion, I would very
> much like to know where the standard mentions the possibility
> for pointers to contain boundary information. At least I never
> heard of these boundery-aware pointers, and thus far I could
> not find anything in them in the standard either.

No need for it.  The standard says out of range accesses are
undefined behavior, or words to that effect.  The rest is quality
of implementation.

More mature languages, such as Ada and Pascal, generally can
perform runtime checks on all accesses that have not been proven
correct by source analysis.  C usually cannot, because of the
indiscriminate way in which pointers can be constructed, such as
flexibility and allows simple compilers to generate good code.

Actually most implementations contain a partial, and simplified,
version of bounds checking.  That is where the SIGSEGV traps
occur, if you are lucky.

A C implementation that performed full runtime checking would
probably be much too slow to be popular, and would also suffer
from code bloat.  In fact, complete checking may well be virtually
impossible, and better partial checking would give a false sense
of security.

--

Available for consulting/temporary embedded and systems.

Thu, 02 Sep 2004 20:39:00 GMT
Pointers and matrices

...

Quote:
>much like to know where the standard mentions the possibility
>for pointers to contain boundary information. At least I never
>heard of these boundery-aware pointers,

Try a Google search on "bounds checking gcc"

Quote:
>and thus far I could
>not find anything in them in the standard either.

The standard makes the behaviour of exceeding bounds undefined
(except for ussies relating to 1 place past the end of the array).
That allows a compiler to do what it likes in such
circumstances including test boundary conditions.

Quote:
>It might be something like the 'drive-through penalty' in
>today's Formula 1 Grand Prix though. I've watched the GP for
>over twenty years, but never heart of it, and neither did the
>experienced commentator on Dutch TV :)

I think that is a new rule, they keep on tweaking them.

--
-----------------------------------------

-----------------------------------------

Wed, 08 Sep 2004 23:13:01 GMT

 Page 1 of 1 [ 9 post ]

Relevant Pages