Unit 6.12 Two Dimensional Array Dealing with Columns -- Another Example
PROG
will sum column 1 of A into B(1)
will sum column 2 of A into B(2)
...
will sum column NOCOLS of A into B(NOCOLS)
PED
to learn how to handle two-dimensional logic that proceeds
by column
CONCEPTS
Same as UNIT 6.11
SF
none
34.html
Unit 6.11/6.12 -- Two Dimensional Array Dealing With Columns
We learned how to deal with two-dimensional arrays going row
by row. We also need to learn how to deal with them when we
process them column by column.
It doesn't make any difference in the logic, whether we
process the entire column or we are processing the array or
the upper left hand corner of the array only.
Looking at our template,
AX:array[k..m,x..n] of integer;
for i = x to r
for j = k to p
process AX(j,i)
Note that i starts at x, the starting value of the range of
the second subscript--the column. Thus, i now tells us
which column we are processing. The inner loop has j
starting from k, the starting value of the range of the
first subscript--the row.
Note that in our "process A(j,i)" we have i, the column
subscript in the second position of A. j, which is a row
number, appears in the first subscript of A(j,i).
We again use the concept of a "big arrow" and a "small
arrow." The "big arrow" moves through the top row, taking
ont the positions AX[k,x], AX[k,x+1]... AX[k,n-1], A[k,n].
(If k and x were both one, then, it would point to A[1,1],
A[1,2] ... A[1,n-1],A[1,n].)
It moves one position in the top row for each time through
the outer loop. This is easy to do--we simply add four.
Note that regA, our big arrow, is initialized to point at
A[1,1] by LA regA,AX. Note at the very end of the outer FOR
LOOP, we have an add 4 to regA. This bumps the big arrow to
the next location in the top row, which is four bytes, one
integer, away.
Prior to entering the inner loop, we let the small arrow
equal the big arrow. In other words, we initialize the
small arrow to point to the top of the apppropriate column.
The "small arrow" starts off at the position of the "big
arrow." That is at the beginning of the "for j" inner loop,
it is at the top of the column. Each time through the inner
loop, the small arrow goes down to the element below it.
For example, assume that we have a 2-D arrow whose first
subscript starts at 1, i.e., k is 1. If the column we are
processing was #3, the small arrow would point at A[1,3],
then A[2,3], then A[3,3] and so forth until A[m,3].
In order to do this, we have to compute the number of bytes
between A[I,J] and A[I+1,J]. This is the number of bytes in
a row or 4*(n-x+1). In the event, that m and n are not
constants, this would have to be computed by appropriate A
and S instructions. The multiplication by four can be done
by two successive doublings with AR regC,regC.
In our template "regA" is the big arrow. "regB" is the big
arrow.
The setting of the "small arrow" to the "big arrow" occurs
in the LR regB,regA. In the inner loop, we process the
element at the small arrow, just as we did last time. Note
the use of "regC" as the increment for regB. Now "regA,"
our small arrow, will point to the next element in the
column.
Just at the end of the outer loop, we add 4 to regA. This
bumps our big arrow by four to point to the top of the next
column.
Two examples are provided here. The first sets the upper
left hand 3 by 3 subsquare of an array to the values I+J. I
and J are the first and second subscript, respectively.
However, it goes by columns rather than by rows as in Unit
25. You will note in the Pascal code converted that I and J
were reversed in the subscript list for B. The program
looks very similar to that for Unit 25. The only changes to
the Assembly Code are in lines 32 and 36. Note also that R3
will be pointing at the top of the column instead of the
beginning of the row. R5 now points to a row within that
column.
Let's go through the program systematically, however. Line
19 initializes register 3 to point to the top of the first
column. This will serve as the big arrow. Line 20
initializes the counter I in 1. Lines 21 through 23, check
that I is not greater thatn 3 for the outer for loop. Line
24 initializes the counter for J for the iner loop. Line 25
copies the "big arrow" to the "small arrow." This sets the
pointer to the row within the column to the top of the
current column. Line 26 to 28 compare J to 3 for the inner
loop. Lines 29 to 30 compute I+J. Remembering that the
inner arrow is register five, line 31 stores I+J at A[J,I].
This serves the purpose of "process A[J,I]" in our template.
Line 33 increments the register containing J.
Lines 34 to 35 end the inner loop. Line 36 increments the
big arrow to the next column. That is, the big arrow is
advanced to the next column. Line 37 increments I in the
outer loop and we branch back to Line 38.
Our second example will sum the first column and put it's
value into B[1]. The sum of the second column will go into
B[2]. Lastly, the sum of B[NOCOLS] will contain the sum of
the last column of A, corresponding to NOCOLS.
Our supplementary program in Unit 26 Supplementary, will be
the equivalent to the PASCAL:
FOR J:=0 to NOCOLS-1 DO
SUM:=0
FOR I:=0 to NOROWS-1 DO
SUM:=SUM+A[I,J]
END
B[I]:=SUM
END
Since we didn't specify the exact dimensions of the array,
we will assume it is dimensioned [0..NOCOL-1,0..NOROWS-1].
Our big arrow, "regA," is stored in register one. Our small
arrow is stored in stored in register 4. "regC" is in
register 2. Note that we simply double the number of
columns to compute this.
We also have one more address register, or "arrow," a
pointer to the current position in B to contain the next
sum. That is initialized at B and is incremented by four in
the outer loop. That is kept in register 5. This is is
"RegB."
We keep "I" in register 7 and "J" in register 8. The
current value of the SUM is kept in register 6, which is
deposited into the appropriate element of B at the end of
the inner loop.
We load the contents of the address of the array in line 27.
"regC" which is register 2 is set to the number of bytes in
a row in lines 28 to 30. Note that since the array goes
from 0 to NOCOL-1, all we have to do is to double NOCOL.
Register 7 is initialized to 1 as part of the FOR loop in
line 5. The FOR-LOOP1 beginning stuff, lines to 33 to 35.
Line 36 zeros out the SUM for the column to be summed in the
inner loop, implementing line 6. Line 37 copies the big
arrow to the little arrow. Line 38 initializes J to 1.
Lines 39 to 41 do the beginning of the FOR-loop stuff for
the inner loop. Line 42 process ARRAY[I,J], by adding it to
the column sum being kept in register 6. Line 43 pushes the
pointer to the next element in the current column. Line 44
increments J. Lines 45 to 46 ends the inner loop.
Line 47 copies the value of the SUM to the appropriate
element of J. Line 48 advances the pointer into the B array
to the location where the next column's sum is to be put.
Line 49 moves the big arrow to the next column. Line 50 to
52 end the outer FOR-LOOP with line 53 returning to the
operating system.