Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > multi dimensional arrays as one dimension array

Reply
Thread Tools

multi dimensional arrays as one dimension array

 
 
vippstar@gmail.com
Guest
Posts: n/a
 
      08-29-2008
The subject might be misleading.
Regardless, is this code valid:

#include <stdio.h>

void f(double *p, size_t size) { while(size--) printf("%f\n", *p++); }
int main(void) {
double array[2][1] = { { 3.14 }, { 42.6 } };
f((double *)array, sizeof array / sizeof **array);
return 0;
}

Assuming casting double [2][1] to double * is implementation defined
or undefined behavior, replace the cast with (void *).

Since arrays are not allowed to have padding bytes in between of
elements, it seems valid to me.
 
Reply With Quote
 
 
 
 
vippstar@gmail.com
Guest
Posts: n/a
 
      08-29-2008
On Aug 29, 6:39 am, pete <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > The subject might be misleading.
> > Regardless, is this code valid:

>
> > #include <stdio.h>

>
> > void f(double *p, size_t size) { while(size--) printf("%f\n", *p++); }
> > int main(void) {
> > double array[2][1] = { { 3.14 }, { 42.6 } };
> > f((double *)array, sizeof array / sizeof **array);
> > return 0;
> > }

>
> > Assuming casting double [2][1] to double * is implementation defined
> > or undefined behavior, replace the cast with (void *).

>
> > Since arrays are not allowed to have padding bytes in between of
> > elements, it seems valid to me.

>
> Stepping through a one dimensional array
> and on through a consecutive one dimensional array
> is only defined for elements of character type
> and only because
> any object can be treated as an array of character type.


So as I understand it you are saying my code invokes undefined
behavior.
In which hypothetical (or real, if such implementation does exist)
implementation my code won't work, and why?
 
Reply With Quote
 
 
 
 
Barry Schwarz
Guest
Posts: n/a
 
      08-29-2008
On Aug 28, 8:15 pm, (E-Mail Removed) wrote:
> The subject might be misleading.
> Regardless, is this code valid:
>
> #include <stdio.h>
>
> void f(double *p, size_t size) { while(size--) printf("%f\n", *p++); }
> int main(void) {
> double array[2][1] = { { 3.14 }, { 42.6 } };
> f((double *)array, sizeof array / sizeof **array);
> return 0;
>
> }
>
> Assuming casting double [2][1] to double * is implementation defined
> or undefined behavior, replace the cast with (void *).


Changing the cast to void* only creates more work for the compiler.
Unless it is smart enough to optimize away the first step, it must
first convert array (which in this context is identical to &array[0]
and has type "double (*)[1]") to void* to satisfy the cast and then
convert that to double* to satisfy the prototype.

The only issue about pointer conversions is if the value is properly
aligned for the resulting type and the value of the expression array
is guaranteed to be properly aligned for a double* since the value
(disregarding type) is exactly the same as &array[0][0]..

>
> Since arrays are not allowed to have padding bytes in between of
> elements, it seems valid to me.


If your system has built in hardware assist for bounds checking, it
would be reasonable for the "bounds registers" to contain the start
and end addresses of array[0]. Eventually your p++ would be outside
this range (even though it is still within array as a whole). While
this is a perfectly valid value attempts to dereference it should be
trapped by the bounds checking logic in the hardware.

Whether such a system exists is a practical issue
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      08-29-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> On Aug 29, 6:39 am, pete <(E-Mail Removed)> wrote:
>> (E-Mail Removed) wrote:
>>> The subject might be misleading.
>>> Regardless, is this code valid:
>>> #include <stdio.h>
>>> void f(double *p, size_t size) { while(size--) printf("%f\n", *p++); }
>>> int main(void) {
>>> double array[2][1] = { { 3.14 }, { 42.6 } };
>>> f((double *)array, sizeof array / sizeof **array);
>>> return 0;
>>> }
>>> Assuming casting double [2][1] to double * is implementation defined
>>> or undefined behavior, replace the cast with (void *).
>>> Since arrays are not allowed to have padding bytes in between of
>>> elements, it seems valid to me.

>> Stepping through a one dimensional array
>> and on through a consecutive one dimensional array
>> is only defined for elements of character type
>> and only because
>> any object can be treated as an array of character type.

>
> So as I understand it you are saying my code invokes undefined
> behavior.
> In which hypothetical (or real, if such implementation does exist)
> implementation my code won't work, and why?


The key point is the pointer conversion. At the point where that
conversion occurs, the compiler knows that (double*)array == array[0].
It's undefined if any number greater than 1 is added to that pointer
value, and also if that pointer is dereferenced after adding 1 to it.

Because the behavior is undefined, it's possible for a conforming
implementation to provide a run-time bounds check. This would require
the use of some mechanism such as a "fat" pointer, which contains not
only the information about where it points, but also information about
the upper and lower limits on where it can point. The implementation can
set the limits on the pointer value created by that conversion, based
upon the limits for array[0].

Implementations with support for run-time bounds checking are rare; the
performance cost is significant, it's almost always optional, and
usually not the default option, so you're unlikely to run into this
issue by accident.

The more tricky possibility is also something you're far more likely to
run into. Because the behavior is undefined in those cases, a compiler
is allowed to generate code which is optimized in a way that assumes
that those cases don't actually come up; because it makes that
assumption, such code can fail catastrophically if that assumption is
violated.

This is most likely to occur as the result of anti-aliasing assumptions.
The compiler is allowed to generate code which assumes that array[0][i]
is never an alias for array[1][j], regardless of the values of i and j.
As a result, it can drop anti-aliasing checks from code that would need
such checks if that assumption could be violated without making the
behavior undefined.

I don't see any way for that to come up in this particular example, but
in more complicated cases it can come up. If 'p' and 'array' were both
in scope at the same place somewhere in the code, the compiler would not
be required to prevent the problems that might occur if p[j] and
array[1][i] happened to refer to the same location in memory. It is
required to cover the possibility that p[j] and array[0][i] refer to the
same object, but only if 'i' and 'j' are both 0. It's also required to
handle the possibility that p+j refers to the same location as
array[0][i], but only if 'i' and 'j' are both in the range [0,1].
 
Reply With Quote
 
vippstar@gmail.com
Guest
Posts: n/a
 
      08-29-2008
On Aug 29, 6:15 am, (E-Mail Removed) wrote:
Message-ID: <38b37f10-252e-48f8-bffa-
(E-Mail Removed)>

Thanks everyone.
 
Reply With Quote
 
James Tursa
Guest
Posts: n/a
 
      08-31-2008
On Thu, 28 Aug 2008 23:39:54 -0400, pete <(E-Mail Removed)>
wrote:
>
>Stepping through a one dimensional array
>and on through a consecutive one dimensional array
>is only defined for elements of character type
>and only because
>any object can be treated as an array of character type.


I am trying to understand your answer. Are you saying that the
original code will not necessarily work in a conforming compiler
because there is no guarantee in the standard that the row slices will
be exactly next to each other in memory (i.e., there may be padding
added to each row that may not be a multiple of sizeof(double))? But
at the same time if double was replaced with char, i.e.,

#include <stdio.h>
void f(char *p, size_t size) { while(size--) printf("%c\n", *p++); }
int main(void) {
char array[2][1] = { { 'a' }, { 'b' } };
f((char *)array, sizeof array / sizeof **array);
return 0;
}

then for this particular case the row slices are required by the
standard to be next to each other in memory so the individual stepping
will work in the called function? Or are you saying that for the char
case there may still be padding between the row slices but the
individual stepping will work because the padding will always be a
multiple of sizeof(char) (i.e., 1), and that the stepping in the
called function will just include the padded characters if they are
present?

i.e., in either case the called function may not be doing what you
intended if there is padded memory present between the rows, but in
the case of double or other non-character type it may even bomb.

Do I understand your answer correctly?

James Tursa
 
Reply With Quote
 
James Tursa
Guest
Posts: n/a
 
      08-31-2008
On Fri, 29 Aug 2008 11:08:00 GMT, James Kuyper
<(E-Mail Removed)> wrote:
>
>The key point is the pointer conversion. At the point where that
>conversion occurs, the compiler knows that (double*)array == array[0].
>It's undefined if any number greater than 1 is added to that pointer
>value, and also if that pointer is dereferenced after adding 1 to it.
>


Trying to understand your answer as it relates to the original post. I
don't see how the original function gets an address 2 beyond the end,
or 1 beyond the end and attempts to dereference it, as you seem to be
saying. Can you point this out? Did I misunderstand you?

James Tursa
 
Reply With Quote
 
vippstar@gmail.com
Guest
Posts: n/a
 
      08-31-2008
On Aug 31, 8:02 pm, James Tursa <(E-Mail Removed)>
wrote:
> On Thu, 28 Aug 2008 23:39:54 -0400, pete <(E-Mail Removed)>
> wrote:
>
>
>
> >Stepping through a one dimensional array
> >and on through a consecutive one dimensional array
> >is only defined for elements of character type
> >and only because
> >any object can be treated as an array of character type.

>
> I am trying to understand your answer. Are you saying that the
> original code will not necessarily work in a conforming compiler
> because there is no guarantee in the standard that the row slices will
> be exactly next to each other in memory (i.e., there may be padding
> added to each row that may not be a multiple of sizeof(double))? But
> at the same time if double was replaced with char, i.e.,
>
> #include <stdio.h>
> void f(char *p, size_t size) { while(size--) printf("%c\n", *p++); }
> int main(void) {
> char array[2][1] = { { 'a' }, { 'b' } };
> f((char *)array, sizeof array / sizeof **array);
> return 0;
>
> }
>
> then for this particular case the row slices are required by the
> standard to be next to each other in memory so the individual stepping
> will work in the called function? Or are you saying that for the char
> case there may still be padding between the row slices but the
> individual stepping will work because the padding will always be a
> multiple of sizeof(char) (i.e., 1), and that the stepping in the
> called function will just include the padded characters if they are
> present?
>
> i.e., in either case the called function may not be doing what you
> intended if there is padded memory present between the rows, but in
> the case of double or other non-character type it may even bomb.
>
> Do I understand your answer correctly?


That code of yours invokes undefined behavior, if char is signed.
You have to change the type of p to unsigned char.
Also, it would only be meaningful if you did not divide by sizeof
**array.

'pete' did not really answer my question. Instead he spoke for object
representations.
What pete really meant is that you can treat any pointer to object as
an array of unsigned char, to observe its representation.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      08-31-2008
James Tursa <(E-Mail Removed)> writes:
> On Thu, 28 Aug 2008 23:39:54 -0400, pete <(E-Mail Removed)>
> wrote:
>> Stepping through a one dimensional array
>> and on through a consecutive one dimensional array
>> is only defined for elements of character type
>> and only because
>> any object can be treated as an array of character type.

>
> I am trying to understand your answer. Are you saying that the
> original code will not necessarily work in a conforming compiler
> because there is no guarantee in the standard that the row slices will
> be exactly next to each other in memory (i.e., there may be padding
> added to each row that may not be a multiple of sizeof(double))?


No. There cannot be padding between array elements; in particular,
given:

double arr[10][10];

the size of arr is guaranteed to be exactly 100*sizeof(double).

Padding isn't the issue. The issue is that the standard doesn't
require implementations to support indexing past the end of an array.
So if I write

arr[0][15]

I'm trying to refer to an element of arr[0] that doesn't exist.
There's a valid object, accessible as arr[1][5], at the intended
location in memory -- and *most* C compilers will let you access that
object either as arr[0][15] or as arr[1][5]. But arr[1][5] is
guaranteed to work, and arr[0][15] isn't, because it attempts to index
beyond the end of the double[10] array arr[0].

In other words, implementations are allowed, but not required, to
perform bounds checking.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
James Tursa
Guest
Posts: n/a
 
      08-31-2008
On Sun, 31 Aug 2008 10:35:05 -0700 (PDT), (E-Mail Removed) wrote:

>On Aug 31, 8:02 pm, James Tursa <(E-Mail Removed)>
>wrote:
>> On Thu, 28 Aug 2008 23:39:54 -0400, pete <(E-Mail Removed)>
>> wrote:
>>
>>
>>
>> >Stepping through a one dimensional array
>> >and on through a consecutive one dimensional array
>> >is only defined for elements of character type
>> >and only because
>> >any object can be treated as an array of character type.

>>
>> I am trying to understand your answer. Are you saying that the
>> original code will not necessarily work in a conforming compiler
>> because there is no guarantee in the standard that the row slices will
>> be exactly next to each other in memory (i.e., there may be padding
>> added to each row that may not be a multiple of sizeof(double))? But
>> at the same time if double was replaced with char, i.e.,
>>
>> #include <stdio.h>
>> void f(char *p, size_t size) { while(size--) printf("%c\n", *p++); }
>> int main(void) {
>> char array[2][1] = { { 'a' }, { 'b' } };
>> f((char *)array, sizeof array / sizeof **array);
>> return 0;
>>
>> }
>>
>> then for this particular case the row slices are required by the
>> standard to be next to each other in memory so the individual stepping
>> will work in the called function? Or are you saying that for the char
>> case there may still be padding between the row slices but the
>> individual stepping will work because the padding will always be a
>> multiple of sizeof(char) (i.e., 1), and that the stepping in the
>> called function will just include the padded characters if they are
>> present?
>>
>> i.e., in either case the called function may not be doing what you
>> intended if there is padded memory present between the rows, but in
>> the case of double or other non-character type it may even bomb.
>>
>> Do I understand your answer correctly?

>
>That code of yours invokes undefined behavior, if char is signed.
>You have to change the type of p to unsigned char.
>Also, it would only be meaningful if you did not divide by sizeof
>**array.
>


What don't you like about sizeof **array ?

>'pete' did not really answer my question. Instead he spoke for object
>representations.
>What pete really meant is that you can treat any pointer to object as
>an array of unsigned char, to observe its representation.


OK, that's fine for objects, but that doesn't answer my question. What
is it about 2-dimensional (or multi-dimensional) arrays of double that
does not allow them to be stepped through with a double* ? And
ultimately, I would also ask if it is safe/conforming to use memcpy or
the like to copy values from/to such an array wholesale. e.g., is it
OK to have the following and be guaranteed to get all of the values
copied correctly and get at them with dp[0], dp[1], etc.:

double x[2][3];
double *dp;
dp = malloc(6*sizeof(double));
(some code to fill in values of x)
memcpy(dp,x,6*sizeof(double));

James Tursa
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
To convert a one dimensional array into a two dimensional array using C amrutha0303 Software 0 08-03-2010 10:02 PM
a question about 1-dimension and 2-dimension array Luuk C Programming 15 02-11-2010 02:45 AM
multi-dimensional arrays to 2-dimensional arrays Wirianto Djunaidi Ruby 2 04-29-2008 07:31 AM
multiD-vhdl: Multi Dimensional Arrays (allowing generics on each dimension) for VHDL (including ports) albert.neu@gmail.com VHDL 2 03-21-2006 04:05 PM
How do copy Strings from a single dimensional array to double dimensional array Venkat C++ 4 12-05-2003 09:23 AM



Advertisments