Amiga.org
Operating System Specific Discussions => Amiga OS => Amiga OS -- Development => Topic started by: Sidewinder on March 14, 2003, 01:32:20 AM
-
Hello all,
I am attempting to devise a formula to compute the memory address of a multi-dimensional array of arbitrary dimensions and size. So far the solution has been eluding me and I thought maybe you all could help point me in the right direction. Here's the problem:
I have a function that reserves a block of memory that is used to hold values in an array-like method. The function takes sizes of an arbitrary number of dimensions and reserves space to hold as many 4 byte integers. The trouble I'm having is finding the memory location of a specific element. I have formulas for finding the memory location of a 1-dimensional array element and a 2-dimensional array element, but I need a generic formula to find the address of an n-dimensional array element.
1-dimensional:
int base
address = base[index1];
address = base + (index * sizeof(int));
2-dimensional:
int base
address = base[index1][index2];
address = base + (index1 * x * sizeof(int)) + (index2 * sizeof(int))
n-dimensional:
int base
address = base[index1][index2][index3][index4]...;
address = ???
This problem must be discussed somewhere because all C compilers use it to convert array indexes into pointer arithmetic when dealing with arrays. Does anyone have any ideas?
Thanks,
-
This (http://www.eskimo.com/~scs/cclass/int/sx9b.html) might get you pointed in the right direction.
Blitter
-
@Blitter
Thanks for the prompt reply. The approach used in that example is different than the one I am using. I have one large block of contigious memory large enough to hold all the elements of the array. This example fragments the array by rows. Also, the example code deals only with 2 dimensional arrays.
I need a more generic example or formula for 3, 4, 5,..., n dimensional arrays in a contigious block of memory. :-(
I'm getting a headache.
-
Okay, It's been a while since I've done this in C but I'll try and explain my understanding of it.
In actuality an array is a pointer to a set pf pointers, so a multi-dimentional array is a pointer to a pointer to set of pointers, etc.
I'll use a 3 dimentional array as an example.
ary
so we have x number of planes that have y number of rows that has z number of colums.
Now in order to traverse every element in this multi-dimentional array we have to go through every colum of every row of every plane. But we dont't want to do that. We want the pointer of a specific element in our multi-dimetional array.
So we know what we want but how to get it? Well, since we have x planes that contain our y rows and z colums, then we can add them like this:
I'll use your example but with 3 dimentions.
int base
address = base[index1][index2][index3]
address = base+(index1* x * sizeof(int))+(index2 * y * sizeof(int))+(index3 * sizeof(int))
Okay, I was going to go into n-dimentional arrays but It's getting late and I'm starting to confuse myself now. :-P
Basically for an n-dimentional array you're gonna have to create a loop to traverse your array.
If this is of no help, then I appologize. It's been quite a while since I've had to do this.
This (http://www.cs.man.ac.uk/~pjj/cs2111/ho/node17.html) contains more algorithyms for finding addresses.
Blitter
-
You know, it just hit me. You stated contigious memory block. I'm not sure what I posted would work in that situation and I'd have to go back to my books to find an ABSOLUTE solution. If one of the more regular C programmers here can't help, then I'll did my books out this weekend and see what I can figure out for ya.
Also if you have time, this (http://www.technoplaza.net/programming/index.cgi?p=lesson9) is an interresting read.
It's for TI-89 and TI-92+ calculators, but also covers some of the pointer inderection stuff that I wanted to get into for ya.
Blitter
-
The number of elements in such an array is simply
m1 x m2 x m3 x ... x mN
where any dimension has elements indexed 0 to m-1
A linear array is m1 elements,
A 2D array is m1 x m2
A 3D array is m1 x m2 x m3 etc.
The total size of memory to allocate is
number of elements x sizeof(element)
At this point, since you are doing the pointer math, you are free to arrange your data any way you wish, but probably the simplest way is to build it up a layer at a time.
Think of the number 9999 as a 4D array with m1,m2,m3 and m4 = 10 (elements 0-9) Then the simplest way to traverse all the elements is thus:
0000
0001
0002
0003 etc ...
0009
0010
0011
0012 etc ...
9998
9999
So, an element at n1,n2,n3,n4 is at
n1 + (n2 * m1) + (n3 * m1 * m2) + (n4*m1*m2*m3)
You can expand this to as many dimensions as you wish (and watch all your memory magically disappear as the storage requirements rapidly approach huge :-D ).
-
I also use 3-dimensional array in my game, reading and writing it directly with pointers.
For writing and reading, I use inline functions (one lined). That way I should be able to modify used methods & possibly add 4th dimension (might need that...) later rather easily...
-
The question was "what is the general expression?"
For an n-dimensional array of elements 'type'
the declaration might be:
"type name[m1][m2][m3][ . . . ][mn];"
where "type" is int, char, etc;
"name" is the array name;
"m1", "m2" etc are the sizes of each subscript.
The address of an element (&name[M1][M2][. . . ][MN]) = (type *)name + MN * (sizeof(type) + M(N-1) * (sizeof(type) + . . . . +M1 * (sizeof(type)))))))); (N closing paren)
However, I could have it backwards, in which case, run the N -> 0 indices back the other way. Draw a sketch on a piece of paper, with the last subscript of the array changing fastest, and you should see it.
tony
-
Multidimensional arrays can be pretty expensive to lookup, as is clear from the replies already here. To summarise, you basically end getting N-1 multiplications and N-1 additions determining the pointer position for an N-dimensional array.
A compiler usually arranges statically defined multidimensional data in a contiguous block (in first index major order). When it comes to dynamically allocated data (which is usually the case), you have to handle the lookup yourself.
In any event, you may consider redesigning your data arrangement, or access to the critical areas to it, to require fewer dimensions (if possible).
-
Getting.... dizzy....
Couldn't you just make a pointer to your array element and figure out the address of where it's pointing? No maths needed. Or am I just being very silly?
I'll stick to ARexx :-)
-
Hehe I`ll stick to OPL on my PSION :-)
-
Ok, this is how I would visulise it:
for a two dimential array
to find x,y is easy:
Data = y(Addr+x)
This treats your array like a page:
***********
***********
***********
***********
where each * represents your data
Thus for a three dimentinal array, I would think of it like a book with lots of pages:
Data=z(y(Addr+x)
Thus:
*********** *********** ***********
*********** *********** ***********
*********** *********** ***********
*********** *********** ***********
I can't visulise more than 3 dimentions (lots of books? in lots libraries in lots of cities... gah.. the list goes on...), damn my human brain, so for an array where you have n dimentions, you would need a loop to keep multiplying by n-1 until you got to n!!! wow that would use a lot of memory!!!!
I suggest you find a size you are happy with an sick to it :-D
Unless you are doing some kind of qunatum mechanics, I don't see the need for more than 4 dimentions to an array :-p
-
index1, index2, index3....
Shouldn't index1 itself, be an array?
i.e. index(x), x increments from array to array, in a loop to max arrays you have?
index(1)= no of elements in first index
index(2)= no of elements in second index
That way, you could multiply it out before hand and see if it will overflow the ram you reserved.
AmigaOne! Move to the next dimension of power!
-
Hi,
The important idea here is the data being contiguous in memory. This is not guaranteed.
For example: int data[20][4] give us an array of 20 pointers addressed at &data or 'data' in C. Each of these pointers is to an array of 4 integers. These integer arrays may not be contiguous in memory where one array would lead onto another. Hence a formula for the address of an element would be unreliable. This would apply whether 'data' was declared on the heap i.e. with file scope or on the stack i.e. with function scope.
A reliable technique is to declare a single array in C such as data[big] and then using formulas to find addresses in this space.
Cheers Mike
-
One way of creating fast multidimensional lookups (ie without multiplication involved) is to create a table of pointers to pointers. This requires more memory (to hold the pointer table) but then you can get a simple lookup technique.
For example, a dynamic 2D array can be set up as follows
/* create our contiguous block memory for the objects */
size_t i;
size_t numRows = ....;
size_t numCols = ....;
Type* data = 0;
Type** rowPointer = 0;
Type* data = (Type*)malloc(sizeof(Type)*numRows*numCols);
/* create our row lookup */
Type** rowPointer = (Type**)malloc(sizeof(Type*)*numRows);
/* Fill the row lookup table */
for (i=0; i{
rowPointer = &data[i*numCols];
}
/* Now, the rowPointer table contains the offsets to the start of each 'row' in our main data array, so we can access by lookup without multiplication */
Type* p = (rowPointer[rowIndex])[columnIndex];
The principal drawback of this is that you need to allocate space for the rowPointer table. This is usually a lot smaller than the main data however (each entry is just 4 bytes typically), so you might not worry about this.
-
Personally, I wouldnt bother - you'll only confuse yourself !
stick to 1 or 2 dimensional arrays where the index maths is much easier - if you need more dimensions, have several 1 or 2 d arrays of the same size:
ie:
int x[1000], y[1000], z[1000];
for 3d objects, etc you could use this:
typedef coord struct {int x, y, z };
coord array[1000];
in effect an array of structures.
the coords can then be accessed like this :
px = array[123].x;
etc. or
int curr_ind = 123;
ptr_curr_x = array + curr_ind * sizeof(coord);
ptr_curr_y = array + curr_ind * sizeof(coord) + sizeof(int);
ptr_curr_z = array + curr_ind * sizeof(coord) + 2 * sizeof(int);
This last approach can quite neatly be expanded for any number of dimensions.
why do you need lots of dimensions ? complicated Tensor Analysis ? :-D
-
@AgaFaster
That's fine for statically sized information, but when you have a dynamically allocated multidimensional array of objects (any kind) where each dimension is initialised with a runtime variable you need to get dirty with pointers.
Also, look at your ptr_curr_z expressions etc. These still involve N-1 multiplications per access which can be a serious overhead in critical areas.
-
Off the top of my head I'd say the only simple :-? way I can think of to do this is to write a recursive routine where it calls itself to calculate the previous dimension and bases it's calculation off of that which is based on the previous dimension and so on. It will handle as many dimensions as your stack space will allow for the recursion. This is also limited by the maximum value your pointer can handle.
You'd need the index within each dimension, the size of that dimension and the sizeof the object you are storing in that nth dimensional array. They would need to be stored in an array, string, or whatever to be read by the recursive routine. So, if you want a n dimensional array with each dimension having it's own size you would need an array kinda like this:
//n is number of dimensions
object_position[n] = {27, 2000, ... 100}; // where you have a position within each dimension
dimension_size[n] = {
{size_n0},
{size_n1},
...
{size_nn}
} // where you have the size of each dimension
The dimension size is the return value and the actual pointer is static so offsets are added to it as the calculation goes along. You pass the recursive routine the the index into the dimension_size array which subtracts one and calls itself until it's zero. Then calculations start and returns commence.
But that's just off the top of my head. :-D
-
-
Oh, one more thing. If you just set up the recursive routine to calculate the offset rather than an actual pointer you just use ArrayBaseAddress + (offset * sizeof(array_element)) to get the actual memory address.
This will actually be faster than doing the calculation in the recursive routine.
The recursive routine is basicly an n to 1 dimensional array index converter.
Hmmmm.... if you typecast it to a 1 dimensional array you could use something more like this to access it:
array1D[offset]
-
Thank you for all of your help. I used the offset approach that jdiffend advised and was able to implement a loop to compute the offset and then add it to the base address. Simply using a bunch of 2D arrays or somthing was not an option because I'm designing a programming langauge and do not wish to impose silly limits on such things when a little time and thinking could offer a more flexable solution. Thanks to everyone who helped.
-
Am I the only one that feels really stupid after reading this thread?
-
Um... brain fart on my part... no recursion needed. Just use nested loops. DU-OH!
(recursion is slower than an iterative approach)
Glad I could help.
-
@samdu
No :-)
I tried to look cool by using the word "pointer" but noone commented my post so I guess I was very wrong :-?
-
@ everybody
So as not to be contrary here is the routine that I came up with. No problems yet, but only time will tell. ;-)
/* number_of_dimensions is an int that holds the number of dimensions of the array (clever eh?), i is the standard counter variable. address holds the memory location. The element_values[] array is number_of_dimensions in size and holds the desired position of the element that we wish to address : i.e. (2,4,1,5) . The max_element_size[] array is also number_of_dimensions in size but it holds the maximum values of each of the dimensions: i.e. (10,10,10,10).
i = number_of_dimensions;
place_value = 1;
address = element_values;
i, element_values, address);
i--;
while (i >= 0) /* While there are more dimensions to calculate. */
{
place_value *= max_element_size[i + 1];
address += element_values * place_value;
i--;
}
address *= type_size;
address += base;
And that's about it.
Cheers.
-
If you do this often, you may be doing too many multiplications. How about adding another array to keep track of the stride of each dimension, then calculate the values at the time of array creation.
i.e. you add
stride[0] = 1; // single element always is one wide!
for (i=1;i stride = stride[i-1] * max_element_size[i-1];
// then go through again to mult in the sizeof()
for (i=1;i stride *= type_size;
//Now you can find your address with
address = base;
for (i = 0; i address += element_values * stride;
which will save on multiplies as the dimensions grow and ... should compile to better code on G4 with an Altivec aware compiler!!! :-)
-
@ Fluffy
Great idea. I hadn't considered that. I think I'll give it a try straight away/