[ Pobierz całość w formacie PDF ]

104 CHAPTER 5. ARRAYS
1 mov eax, [ebp - 44] ; ebp - 44 is i s location
2 sal eax, 1 ; multiple i by 2
3 add eax, [ebp - 48] ; add j
4 mov eax, [ebp + 4*eax - 40] ; ebp - 40 is the address of a[0][0]
5 mov [ebp - 52], eax ; store result into x (at ebp - 52)
Figure 5.6: Assembly for x = a[i ][ j ]
This analysis also shows how the formula is generalized to an array withN
columns: N ×i+j. Notice that the formula does not depend on the number
of rows.
As an example, let us see how gcc compiles the following code (using the
arrayadefined above):
x = a[i ][ j ];
Figure 5.6 shows the assembly this is translated into. Thus, the compiler
essentially converts the code to:
x = "(&a[0][0] + 2"i + j );
and in fact, the programmer could write this way with the same result.
There is nothing magical about the choice of the rowwise representation
of the array. A columnwise representation would work just as well:
Index 0 1 2 3 4 5
Element a[0][0] a[1][0] a[2][0] a[0][1] a[1][1] a[2][1]
In the columnwise representation, each column is stored contiguously. El-
ement[i][j]is stored at position i + 3j. Other languages (FORTRAN,
for example) use the columnwise representation. This is important when
interfacing code with multiple languages.
Dimensions Above Two
For dimensions above two, the same basic idea is applied. Consider a
three dimensional array:
int b [4][3][2];
This array would be stored like it was four two dimensional arrays each of
size[3][2]consecutively in memory. The table below shows how it starts
out:
5.1. INTRODUCTION 105
Index 0 1 2 3 4 5
Element b[0][0][0] b[0][0][1] b[0][1][0] b[0][1][1] b[0][2][0] b[0][2][1]
Index 6 7 8 9 10 11
Element b[1][0][0] b[1][0][1] b[1][1][0] b[1][1][1] b[1][2][0] b[1][2][1]
The formula for computing the position ofb[i][j][k]is 6i + 2j + k. The
6 is determined by the size of the[3][2]arrays. In general, for an ar-
ray dimensioned asa[L][M][N]the position of elementa[i][j][k]will be
M × N × i + N × j + k. Notice again that the first dimension (L) does not
appear in the formula.
For higher dimensions, the same process is generalized. For an n dimen-
sional array of dimensions D1 to Dn, the position of element denoted by the
indices i1 to in is given by the formula:
D2 × D3 · · · × Dn × i1 + D3 × D4 · · · × Dn × i2 + · · · + Dn × in-1 + in
or for the über math geek, it can be written more succinctly as:
ëø öø
n n
íø
Dkøø ij
j=1 k=j+1
The first dimension, D1, does not appear in the formula. This is where you can tell
the author was a physics
For the columnwise representation, the general formula would be:
major. (Or was the refer-
i1 + D1 × i2 + · · · + D1 × D2 × · · · × Dn-2 × in-1 + D1 × D2 × · · · × Dn-1 × in ence to FORTRAN a give-
away?)
or in über math geek notation:
ëø öø
j-1
n
íø
Dkøø ij
j=1 k=1
In this case, it is the last dimension, Dn, that does not appear in the formula.
Passing Multidimensional Arrays as Parameters in C
The rowwise representation of multidimensional arrays has a direct effect
in C programming. For one dimensional arrays, the size of the array is not
required to compute where any specific element is located in memory. This is
not true for multidimensional arrays. To access the elements of these arrays,
the compiler must know all but the first dimension. This becomes apparent
when considering the prototype of a function that takes a multidimensional
array as a parameter. The following will not compile:
void f ( int a [ ][ ] ); /" no dimension information "/
106 CHAPTER 5. ARRAYS
However, the following does compile:
void f ( int a [ ][2] );
Any two dimensional array with two columns can be passed to this function.
The first dimension is not required2.
Do not be confused by a function with this prototype:
void f ( int " a [ ] );
This defines a single dimensional array of integer pointers (which incidently
can be used to create an array of arrays that acts much like a two dimensional
array).
For higher dimensional arrays, all but the first dimension of the array
must be specified for parameters. For example, a four dimensional array
parameter might be passed like:
void f ( int a [ ][4][3][2] );
5.2 Array/String Instructions
The 80x86 family of processors provide several instructions that are de-
signed to work with arrays. These instructions are called string instructions.
They use the index registers (ESI and EDI) to perform an operation and
then to automatically increment or decrement one or both of the index reg- [ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • angela90.opx.pl

    • Archiwum