CS计算机代考程序代写 assembly Microsoft PowerPoint – 28_X86-64_Assembly_Language_Part_8

Microsoft PowerPoint – 28_X86-64_Assembly_Language_Part_8

O
SU

C
SE

2
42

1

J.E.Jones

Multi-dimensional and multi-level arrays

O
SU

C
SE

2
42

1

J. E. Jones

 Arrays
One-dimensional
◦ Multi-dimensional (nested)
◦ Multi-level

 Structures
◦ Allocation
◦ Access
◦ Alignment

O
SU

C
SE

2
42

1

J. E. Jones

 Declaration
T A[R][C];
◦ 2D array of data type T
 3D, 4D, etc. beyond scope of this

class
◦ R rows, C columns
◦ Type T element requires K bytes

 Array Size
◦ R * C * K bytes

 Arrangement
◦ Row-Major Ordering

A[0][0] A[0][C-1]

A[R-1][0]

• • •

• • • A[R-1][C-1]





int A[R][C];

• • •
A
[0]
[0]

A
[0]

[C-1]
• • •

A
[1]
[0]

A
[1]

[C-1]
• • •

A
[R-1]

[0]

A
[R-1]
[C-1]

• • •

4*R*C Bytes

O
SU

C
SE

2
42

1

J. E. Jones

 zip_dig pgh[4] equivalent to int pgh[4][5]
◦ Variable pgh: array of 4 elements, allocated contiguously
◦ Each element is an array of 5 int’s, allocated contiguously

 “Row-Major” ordering of all elements in memory

#define PCOUNT 4
zip_dig pgh[PCOUNT] =
{{1, 5, 2, 0, 6},
{1, 5, 2, 1, 3 },
{1, 5, 2, 1, 7 },
{1, 5, 2, 2, 1 }};

zip_dig pgh[4];

76 96 116 136 156

1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1
int pgh[4][5];

O
SU

C
SE

2
42

1

J. E. Jones

 To get access to a specific nested array
element
◦ Consider it a two-step process:

1. Compute the address to the desired row
2. Compute the offset within the row to the desired

element
3. Add #1 and #2; result is address of designed

element

O
SU

C
SE

2
42

1

J. E. Jones

• • •

 Row Vectors
◦ A[i] is array of C elements
◦ Each element of type T requires K bytes
◦ Starting address A + i * (C * K)

• • •
A
[i]
[0]

A
[i]

[C-1]

A[i]

• • •
A

[R-1]
[0]

A
[R-1]
[C-1]

A[R-1]

• • •

A

• • •
A
[0]
[0]

A
[0]

[C-1]

A[0]

A+(i*C*4) A+((R-1)*C*4)

int A[R][C];

O
SU

C
SE

2
42

1

J. E. Jones

 Row Vector
◦ pgh[index] is array of 5 int’s
◦ Starting address pgh+20*index

 Machine Code
◦ Computes and returns address
◦ Compute as pgh + 4*(index+5*index)

int *get_pgh_zip(int index)
{
return pgh[index];

}

# %rdi = index
leaq (%rdi,%rdi,4),%rax # 5 * index
leaq pgh(,%rax,4),%rax # pgh + (20 * index)

pgh

1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1

pgh+20 pgh+40

O
SU

C
SE

2
42

1

J. E. Jones

• • •

 Array Elements
◦ A[i][j] is element of type T, which requires K bytes
◦ Address A + (i * (C * K)) + j * K = A + ((i * C )+ j)* K

• • • • • •
A
[i]
[j]

A[i]

• • •
A

[R-1]
[0]

A
[R-1]
[C-1]

A[R-1]

• • •

A

• • •
A
[0]
[0]

A
[0]

[C-1]

A[0]

A+(i*C*4) A+((R-1)*C*4)

int A[R][C];

A+(i*C*4)+(j*4)1. Address of
row start 2. Offset within

row

O
SU

C
SE

2
42

1

J. E. Jones

 Array Elements
◦ pgh[index][dig] is int
◦ Address: pgh + 20*index + 4*dig

= pgh + 4*(5*index + dig)

int get_pgh_digit(int index, int dig)
{
return (pgh[index][dig]);

}

leaq (%rdi,%rdi,4), %rax # 5*index
# %rsi => 2nd parameter

addq %rax, %rsi # 5*index+dig
movl pgh(,%rsi,4), %eax # M[pgh + 4*(5*index+dig)]

pgh

1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1

pgh+20 pgh+40

pgh[2][3]

O
SU

C
SE

2
42

1

J. E. Jones

 Variable univ denotes
array of 3 elements

 Each element is a
pointer
◦ 8 bytes

 Each pointer points to
array of integers

zip_dig cmu = { 1, 5, 2, 1, 3 };
zip_dig mit = { 0, 2, 1, 3, 9 };
zip_dig ucb = { 9, 4, 7, 2, 0 };

#define UCOUNT 3
int *univ[UCOUNT] = {mit, cmu, ucb};

136160
16

256
168
176

univ

cmu

mit

ucb

1 5 2 1 3

16 20 24 28 32 36
0 2 1 3 9

136 140 144 148 152 156

9 4 7 2 0

256 260 264 268 272 276

Note int *

O
SU

C
SE

2
42

1

J. E. Jones

 Computation
◦ Element access Mem[Mem[univ+8*index]+4*digit]
◦ Must do two memory reads
 First read gets pointer to row array
 Second read accesses element within array

salq $2, %rsi # 4*digit (2nd parameter)
addq univ(,%rdi,8), %rsi # p = univ[index] + 4*digit
movl (%rsi), %eax # return *p
ret

int get_univ_digit(size_t index, size_t digit)
{

return univ[index][digit];
}

O
SU

C
SE

2
42

1

J. E. Jones

int get_pgh_digit(size_t index, size_t digit)
{
return pgh[index][digit];

}

int get_univ_digit(size_t index, size_t digit)
{
return univ[index][digit];

}

Nested array Multi-level array

Accesses looks similar in C, but address computations very different:

Mem[pgh+20*index+4*digit] Mem[Mem[univ+8*index]+4*digit]

O
SU

C
SE

2
42

1

J. E. Jones

 Fixed dimensions
◦ Know value of N at

compile time
 Variable dimensions,

explicit indexing
◦ Traditional way to

implement dynamic
arrays

 Variable dimensions,
implicit indexing
◦ Now supported by gcc

(non-ANSI C)

#define N 16
typedef int fix_matrix[N][N];
/* Get element a[i][j] */
int fix_ele(fix_matrix a, size_t i, size_t j)
{
return a[i][j];

}

#define IDX(n, i, j) ((i)*(n)+(j))
/* Get element a[i][j] */
int vec_ele(size_t n, int *a,

size_t i, size_t j)
{
return a[IDX(n,i,j)];

}

/* Get element a[i][j] */
int var_ele(size_t n, int a[n][n],

size_t i, size_t j) {
return a[i][j];

}

O
SU

C
SE

2
42

1

J. E. Jones

/* Get element a[i][j] */
int fix_ele(fix_matrix a, size_t i, size_t j) {
return a[i][j];

}

# a in %rdi, i in %rsi, j in %rdx
salq $6, %rsi # 64*i

#calculate address of needed row
addq %rsi, %rdi # a + 64*i

#now get to specific row element
movl (%rdi,%rdx,4), %eax # M[a + 64*i + 4*j]
ret

 Array Elements (int a[16][16])
 Address a + i * (C * K) + j * K
 C = 16, K = 4, therefore, each row = 16*4 = 64 bytes
 Total Size of Array: 16*16*4 = 1024 bytes

O
SU

C
SE

2
42

1

J. E. Jones

/* Get element a[i][j] */
int var_ele(size_t n, int a[n][n], size_t i, size_t j) {

return a[i][j];
}

# n in %rdi, a in %rsi, i in %rdx, j in %rcx
imulq %rdx, %rdi # n*i
leaq (%rsi,%rdi,4), %rax # a + 4*n*i
movl (%rax,%rcx,4), %eax # a + 4*n*i + 4*j
ret

 Array Elements
 Address A + i * (C * K) + j * K
 C = n, K = 4
 Must perform integer multiplication