I was just reading through some sections of "Art of Assembly", I was thrown off a bit by this part under Row Major Ordering for 2D arrays:


The formula to compute the offset for a two-dimension row major ordered array declared in Pascal as "A:array [0..3,0..3] of integer" is

Element_Address = Base_Address + (colindex * row_size + rowindex) * Element_Size

source: http://webster.cs.ucr.edu/AoA/Windows/HTML/Arraysa2.html


I don't see how that formula works, because say I want to get element (0, 1) from the diagram(http://webster.cs.ucr.edu/AoA/Windows/HTML/images/Arrays4.gif) on that page. (which is equal to 1 under my interpretation)

Using the above formula that would result in:

colindex = 1
row_size = 4
rowindex = 0

Element_Address = Base_Address + (1 * 4 + 0) * Element_Size
                = Base_Address + 4 * Element_Size


Considering it's actually located at Base_Address + 1 there is no way this can be right, the way I understand it to work is as follows:

Element_Address = Base_Address + (rowindex * row_size + colindex) * Element_Size


Where am I going wrong here?
Posted on 2006-05-17 00:40:32 by wallplug
The formula is correct (I did have to stare for a moment).
Note the phrase "ROW MAJOR ORDERED".

Columns are your X dimension (as you increase X, you are moving from column to column, since columns are 'vertical').
Rows are your Y dimension. Each row contains a number of items equal to the number of columns - agreed?

Your example requests the item at Column 0, Row 1.
This is indeed located at OFFSET (#columns * element size).

This all becomes much clearer if we pretend for a moment that our elements are unit sized (think of a byte array).

This has been the standard way to address 2D arrays since "the year dot".. hope that helped :)
Posted on 2006-05-17 02:05:22 by Homer
To try and get clarification I'm going to reference this example array:

                (cols)
              0  1  2
         
          0    A  B  C
  (rows)  1    D  E  F
          2    G  H  I
   
memory layout:  A B C D E F G H I
      offsets:  0 1 2 3 4 5 6 7 8

So for example to calculate the offset for 'F' I note the following:
it's in column 2 and row 1, correct?

So if I take that formula ((colindex * row_size + rowindex) * Element_Size) and assume an element size of 1, I get:
2(colindex) * 3(row_size) + 1(rowindex) = 7

This is not correct, but if I change my definition of row and column I get the right offset which is 5.

Since when did column refer to a horizontal row? I'm confused! :D
Posted on 2006-05-17 04:37:55 by wallplug

                (cols)
              0  1  2
         
          0    A  B  C
  (rows)  1    D  E  F
          2    G  H  I
   
memory layout:  A B C D E F G H I
      offsets:  0 1 2 3 4 5 6 7 8


Wrong - the memory layout is like this:


memory layout:  A D G B E H C F I
      offsets:  0 1 2 3 4 5 6 7 8


So for example to calculate the offset for 'F' I note the following:
it's in column 2 and row 1, correct?


yes

So if I take that formula ((colindex * row_size + rowindex) * Element_Size) and assume an element size of 1, I get:
2(colindex) * 3(row_size) + 1(rowindex) = 7


yep, but it now works,
Ossa

Note: I don't know if this is the standard way of ordering the elements, or not, but this is the way that the formula expects them to be. If you want them your way, then you must use the "other" formula:

Element_Address = Base_Address + ((colindex + col_size * rowindex) * Element_Size)

Posted on 2006-05-17 04:56:56 by Ossa
This piece of Pascal code is really funny...in the naming sense atleast...

  index := 0;
  for colindex := 0 to 3 do
      for rowindex := 0 to 3 do
      begin
        memory := rowmajor ;
        index := index + 1;
      end;

It is really confusing...It is making me wonder if I have understood my C corrrectly or not!!!  :shock:

Anyway...the explanation and the variable names are out of whack!!! Any comments anyone???
Posted on 2006-05-17 05:02:57 by shantanu_gadgil
To Ossa,
er...ummm...you sure? I tried this code:
char mydata[2][3] = { {'a','b','c'}, {'d','e','f'}, {'g','h','i'} };
char *p;

p = &mydata[0][0];


int i;
for(i=0; i<9; i++)
p++;


In the debug watch window, just step in the for loop and see the value of '*p'.
Posted on 2006-05-17 05:09:55 by shantanu_gadgil

To Ossa,
er...ummm...you sure? I tried this code:
char mydata[2][3] = { {'a','b','c'}, {'d','e','f'}, {'g','h','i'} };
char *p;

p = &mydata[0][0];


int i;
for(i=0; i<9; i++)
p++;


In the debug watch window, just step in the for loop and see the value of '*p'.



I said that I didn't know if that was the standard way to store them, it is apparently not in C. (By the way, your code is buggy - "mydata[2][3]" should be "mydata[3][3]".) Apparently C uses Column Major Ordering. It may well ne that Pascal uses Row Major Ordering.

As for your previous comment:


This piece of Pascal code is really funny...in the naming sense atleast...

  index := 0;
  for colindex := 0 to 3 do
      for rowindex := 0 to 3 do
      begin
        memory := rowmajor ;
        index := index + 1;
      end;

It is really confusing...It is making me wonder if I have understood my C corrrectly or not!!!  :shock:

Anyway...the explanation and the variable names are out of whack!!! Any comments anyone???


This conforms to the equation given. As a hand interpreter:

index  colindex  rowindex
0      0          0
1      0          1
2      0          2
3      1          0
4      1          1
5      1          2
6      2          0
7      2          1
8      2          2


being consistent with the formula.

Ossa
Posted on 2006-05-17 05:22:05 by Ossa
(By the way, your code is buggy - "mydata[2][3]" should be "mydata[3][3]".)

Yep...got it...my mistake, it should be [3][3]. Was trying a fe thing with different values and left the '2' there by accident.
Posted on 2006-05-17 05:43:16 by shantanu_gadgil
Again about this code:
index := 0;
for colindex := 0 to 3 do
  for rowindex := 0 to 3 do
  begin
    memory := rowmajor ;
    index := index + 1;
  end;


For all my English understanding, I would use "rowindex" variable in the outer for loop and "colindex" in the inner for loop, and switch "rowindex" and "colindex" in the [][] too!!!

Algorithm: For every row, assign values to each of the elements of the row

Could it could be a simple booboo on the page that "rowindex" and "colindex" might have got interchanged???  :D  :D
Posted on 2006-05-17 05:49:12 by shantanu_gadgil


                (cols)
              0  1  2
         
          0    A  B  C
  (rows)  1    D  E  F
          2    G  H  I
   
memory layout:  A B C D E F G H I
      offsets:  0 1 2 3 4 5 6 7 8


Wrong - the memory layout is like this:


memory layout:  A D G B E H C F I
      offsets:  0 1 2 3 4 5 6 7 8


You sure?  I believe that's column major.


Again about this code:
index := 0;
for colindex := 0 to 3 do
  for rowindex := 0 to 3 do
  begin
    memory := rowmajor ;
    index := index + 1;
  end;


For all my English understanding, I would use "rowindex" variable in the outer for loop and "colindex" in the inner for loop, and switch "rowindex" and "colindex" in the [][] too!!!

Algorithm: For every row, assign values to each of the elements of the row

Could it could be a simple booboo on the page that "rowindex" and "colindex" might have got interchanged???  :D  :D

This is initially what confused me, the names seem backwards :P
Posted on 2006-05-17 06:09:50 by wallplug

For all my English understanding, I would use "rowindex" variable in the outer for loop and "colindex" in the inner for loop, and switch "rowindex" and "colindex" in the [][] too!!!


True - I missed that they were swapped... but then I don't use Pascal, so they might be backwards there? Or maybe, as you say, there is a typo and they got swapped.

Actually - I just read what the page says (maybe I should have done that earlier  :oops:), and it seems that the whole thing is inconsistent. So I'll swap everything I said. The formulae are indeed backwards (or everything else is). The loop is also wrong (simply in the naming). Corrected it would be:

index := 0;
for rowindex := 0 to 3 do
  for colindex := 0 to 3 do
  begin
    memory := rowmajor ;
    index := index + 1;
  end;


Sorry, probably did more confusion than help, as I always forget which way round is row and which is colum :oops:
Ossa

Posted on 2006-05-17 06:19:05 by Ossa
When I see the word "column", I picture Greek ruins - columns are vertical, therefore, rows must be horizontal ;)


Let's visualize our arrayspace..

----0 1 2 3
0--A B C D
1--E F G H
2--I J K L
3--M N O P

Damn nbsp grr

In terms of memory layout, imagine that we take all of the horizontal Rows and lay them end to end..
Flat layout is ABCD-EFGH-IJKL-MNOP (I show the Rows separated for clarity).

What's at Row 2, Column 1? It's J.
Offset for J is (ROW * #items per Row) + (COLUMN)
That's (2 * 4) + 1
That's 9
Hey, isn't J the 10th character in the alphabet? Sure - but our offsets are zerobased - so let's include zero and count to check our logic - 0123456789 - the tenth value is at zerobased offset 9 (the first value is at offset zero, heh).

When I first taught myself about this stuff many moons ago, it occurred to me that we can think of the Y coordinate as "the number of full Rows (of ArrayWidth) we must skip, before we add the X offset".
I learned this stuff in relation to 2D bitmaps (bmps).

If our array is 320 wide and 200 high, and we want to find the offset of an element at (37,186) then the offset is ((37 * 320) + 186)..

Does THAT help? :)
Posted on 2006-05-17 09:11:25 by Homer
Whew!!! Finally thats over...it had me biting my nails for a few moments wondering if what I knew all these years was different!!!  :shock: :shock:

So from my side...
The explanation is fine, the code is fine too, its just that the naming of the variables is...er...."off"  :lol: :lol:...yes....thats the word..."off"!!!  :P

Now I can sleep in peace...aaaah!!!
Posted on 2006-05-17 10:54:46 by shantanu_gadgil
Thanks Homer, yes that makes perfect sense.  I was just confused by how what we are referring to as rows and columns were being referred to as the "colindex" and "rowindex"  respectively in "The Art of Assembly" text.
Posted on 2006-05-17 17:37:48 by wallplug
Happy to be of service..

Just one small note in regards to 3D arrays..
Nothing has changed, but we now have n 2D arrays..
The Z coordinate indicates "how many full 2D arrays to skip"..
Posted on 2006-05-18 02:36:16 by Homer

Thanks Homer, yes that makes perfect sense.?  I was just confused by how what we are referring to as rows and columns were being referred to as the "colindex" and "rowindex"?  respectively in "The Art of Assembly" text.


In mathematics, there is a difference between matrix indexing and graph coordinates.

Pick up any book on Linear Algebra or matrix arithmetic, and you will find that matrix elements are numbered this way...

m11 m12 m13
m21 m22 m23
m31 m32 m33

That is, the indexes (subscripts) are in the order (row, column).

This is the opposite of graph coordinates <x, y>. Note also that row, column "coordinates" start from top left. Normal graph coordinates start from bottom left.
Posted on 2006-05-18 03:18:12 by tenkey
Yeah, it really screwed with my brain when I started playing with 4x4 matrices a few years ago..incidentally, I use the 'm00 convention' ;)

Good point about matrices not adhering to the 'x,y' convention for arrays :)
Posted on 2006-05-21 09:11:28 by Homer