[Tutorial] Memory layout of an multidimensional array
#1

Actually all I'm doing is just attempt at translating pawn implemeneter guide from really technically advanced to normal language, but I hope someone will find this useful one day. Everything in here can be found in appendix F of the implementers guide. Also keep in mind that I'm neither english native user or pawn expert, so feel free to tell me if I'm wrong somewhere.

So - how twodimensional arrays are stored in memory? We'll assume that memory is one long chain of bytes. In pawn we mostly access them by 'cells' - 4 bytes in one pack. Twodimensional array resembles rectangle (at least to me), so there has to be some magic method of storing it. Well, actually there isn't.



Basically: starting from array address (red pipe), there is stored array data. For X long array: first X cells are storing pointers to start of subarray (looking at picture: second *sa has address for third el (first element of this subarray)). *sa is equal array address plus element offset times size of second dimension (in bytes).

Assuming array address is 0, and the second dimension is 3 cells big then *sa = 0 + 3 (size) * index * 4 (cellsize) *sa for first element is 0, *sa for second element is 12, *sa for X'th element is 0 + 3*x*4.

Let's run simple test:

pawn Код:
#include <a_samp>

new Target[4][3];
main() {
    new tmp;
    #emit LOAD.S.pri    Target
    #emit STOR.S.pri    tmp
    for(new i = sizeof Target; i != sizeof Target * ( 1 + sizeof Target[]); ++i) {
        #emit LOAD.S.alt    tmp
        #emit LOAD.S.pri    i
        #emit IDXADDR
        #emit MOVE.alt
        #emit CONST.pri     666
        #emit STOR.I
    }


    Target[0][0] = 3;
    Target[1][0] = 2;
    Target[2][0] = 1;

    Foo(Target);
}

stock Foo(array[][], size_1 = sizeof array, size_2 = sizeof array[]) {
    new tmp;
    for(new i = 0; i != size_1 * (1 + size_2); ++i) {
        #emit LOAD.S.alt    array
        #emit LOAD.S.pri    i
        #emit LIDX
        #emit STOR.S.pri    tmp
        printf("At: %d", tmp);
    }
}
The emit soup in main just fills the array with 666's. What matters now is the Foo function. After running the script we'll see something like:

Quote:

[14:36:01] At: 16
[14:36:01] At: 24
[14:36:01] At: 32
[14:36:01] At: 40
[14:36:01] At: 3
[14:36:01] At: 666
[14:36:01] At: 666
[14:36:01] At: 2
[14:36:01] At: 666
[14:36:01] At: 666
[14:36:01] At: 1
[14:36:01] At: 666
[14:36:01] At: 666
[14:36:01] At: 666
[14:36:01] At: 666
[14:36:01] At: 666

Our array is X elements (subarrays) long.
Quote:

[14:36:01] At: 16
[14:36:01] At: 24
[14:36:01] At: 32
[14:36:01] At: 40

These are our pointers to first element of each subarray. If you'll load cell at each of this values, you'll get first element of each subarray. Cool, eh? That's all for now, I hope that this will help you (I don't know why but when I write those tuts I understand stuff better myself)

Update 1:

What is IDXADDR?
Look at these three thingies:

pawn Код:
#emit LOAD.S.alt    tmp
#emit LOAD.S.pri    i
#emit IDXADDR
pawn Код:
#emit LOAD.S.alt tmp
#emit LOAD.S.pri    i
#emit SMUL.C 4
#emit ADD
pawn Код:
#emit LOAD.S.pri tmp
#emit LOAD.S.alt i
#emit SHL.C.alt 2
#emit ADD
(Slice method)

Value from tmp is loaded, and multiplicated by 4, so it is represented in cellsize. IDXADDR does PRI = ALT + PRI * cellsize, so we don't have to multiply stuff manually. LIDX is IDXADDR, then LOAD.I

I'll write about enumerators and 3 dim array later if you want
Reply
#2

I hope one day my english will improve to the level when I'll be able to teach others using simple language. If anyone has any further questions, this topic is open
Reply


Forum Jump:


Users browsing this thread: 2 Guest(s)