CS计算机代考程序代写 assembly Java data structure Introduction to Computer Systems 15-213/18-243, spring 2009 1st Lecture, Jan. 12th

Introduction to Computer Systems 15-213/18-243, spring 2009 1st Lecture, Jan. 12th

Data Structures in Assembly
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structs
Alignment
1

CMPT 295
L09 – Arrays

1

Array Example
2
Example arrays happened to be allocated in successive 20 byte blocks
Not guaranteed to happen in general
zip_dig cmu;
1
5
2
1
3
16
20

24

28

32

36

zip_dig sfu;
9
8
1
9
5
36
40

44

48

52

56

zip_dig ucb;
9
4
7
2
0
56
60

64

68

72

76

typedef int zip_dig[5];

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

CMPT 295
L09 – Arrays
20 B each
No gap in this case
Could have stuff in between

Array Accessing Example
3
int get_digit(zip_dig z, int digit){
return z[digit];
}
zip_dig sfu;
9
8
1
9
5
36
40

44

48

52

56

get_digit:
slli a1,a1,2
add a1,a0,a1
lw a0,0(a1)
ret
Register %a0 contains starting address of array
Register %a1 contains array index
Desired digit at %a0+4*%a1
typedef int zip_dig[5];

CMPT 295
L09 – Arrays
Array also explain funky memory addressing instructions

3

Nested Array Row Access
Row vectors
Given T A[R][C],
A[i] is an array of C elements (“row i”)
A is address of array
Starting address of row i =
4
•  •  •
• • •
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];
A + i*(C * sizeof(T))

CMPT 295
L09 – Arrays
Row is just an address

Nested Array Row Access Code
5
int* get_sea_zip(int index)
{
return sea[index];
}
int sea[4][5] =
{{ 9, 8, 1, 9, 5 },
{ 9, 8, 1, 0, 5 },
{ 9, 8, 1, 0, 3 },
{ 9, 8, 1, 1, 5 }};

CMPT 295
L09 – Arrays
Sea is a global variable here, so its in memory

Nested Array Row Access Code
Row Vector
sea[index] is array of 5 ints
Starting address = sea+20*index
Assembly Code
Computes and returns address
Compute as: sea+4*(index + 4*index) = sea+20*index
6
int* get_sea_zip(int index)
{
return sea[index];
}
int sea[4][5] =
{{ 9, 8, 1, 9, 5 },
{ 9, 8, 1, 0, 5 },
{ 9, 8, 1, 0, 3 },
{ 9, 8, 1, 1, 5 }};
What data type is sea[index]?
What is its value?

CMPT 295
L09 – Arrays
Returns an address, no access

•  •  •
• • • • • •
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];

Nested Array Element Access
Array Elements
A[i][j] is element of type T, which requires K bytes
Address of A[i][j] is

7
?

CMPT 295
L09 – Arrays
A + i*(C*K) + j*K

Nested Array Element Access
Array Elements
A[i][j] is element of type T, which requires K bytes
Address of A[i][j] is
A + i*(C*K) + j*K == A + (i*C + j)*K
8
A + i*C*4 + j*4
•  •  •
• • • • • •
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];

CMPT 295
L09 – Arrays

Nested Array Element Access Code
9
int get_sea_digit
(int index, int digit)
{
return sea[index][digit];
}
int sea[4][5] =
{{ 9, 8, 1, 9, 5 },
{ 9, 8, 1, 0, 5 },
{ 9, 8, 1, 0, 3 },
{ 9, 8, 1, 1, 5 }};

CMPT 295
L09 – Arrays
Asm is 3 steps
Compute row
Compute loctation in row
Access with scaling

Multi-Dimensional Referencing Examples
Reference Address Value Guaranteed?
sea[3][3]
sea[2][5]
sea[2][-1]
sea[4][-1]
sea[0][19]
sea[0][-1]
Code does not do any bounds checking
Ordering of elements within array guaranteed

10
zip_dig sea[4];

76

96

116

136

156
9
8
1
9
5
9
8
1
0
5
9
8
1
0
3
9
8
1
1
5

CMPT 295
L09 – Arrays
148 1 yes
136 9 yes
112 5 yes
152 5 yes
152 5 yes
72 ?? no

Multi-Level Array Example
11
int cmu[5] = { 1, 5, 2, 1, 3 };
int sfu[5] = { 9, 8, 1, 9, 5 };
int ucb[5] = { 9, 4, 7, 2, 0 };
int* univ[3] = {sfu, cmu, ucb};
Is a multi-level array the
same thing as a 2D array?
zip_dig univ2D[3] = {
{ 9, 8, 1, 9, 5 },
{ 1, 5, 2, 1, 3 },
{ 9, 4, 7, 2, 0 }
};
One array declaration = one contiguous block of memory
NO
2D Array Declaration:
Multi-Level Array Declaration(s):

CMPT 295
L09 – Arrays

Multi-Level Array Example
12
Variable univ denotes array of 3 elements
Each element is a pointer
4 bytes each
Each pointer points to array of ints
36

160
16
60

168
176
univ

cmu
sfu
ucb
1
5
2
1
3
16
20

24

28

32

36

9
8
1
9
5
36
40

44

48

52

56

9
4
7
2
0
60
64

68

72

76

80

Note: this is how Java represents multi-dimensional arrays
int* univ[3] = {sfu, cmu, ucb};
int cmu[5] = { 1, 5, 2, 1, 3 };
int sfu[5] = { 9, 8, 1, 9, 5 };
int ucb[5] = { 9, 4, 7, 2, 0 };

CMPT 295
L09 – Arrays

Element Access in Multi-Level Array
13
Computation
Element access Mem[Mem[univ+8*index]+4*digit]
Must do two memory reads
First get pointer to row array
Then access element within array
But allows inner arrays to be different lengths (not in this example)
slli a0, a0, 3 # All registers are assumed to be 64 bit. a5 = &univ[0]
add a5,a5,a0
ld a5,0(a5) # 64 bit load. This is because univ is a pointer array.
slli a1,a1,2 # 4*digit
add a5,a5,a1 # univ[index]+4*digit
lw a0,0(a5) # 32 bit load
int get_univ_digit
(int index, int digit)
{
return univ[index][digit];
}
36

160
16
60

168
176
univ

cmu
sfu
ucb
1
5
2
1
3
16
20

24

28

32

36

9
8
1
9
5
36
40

44

48

52

56

9
4
7
2
0
60
64

68

72

76

80

CMPT 295
L09 – Arrays
Just two array reads

Array Element Accesses
14
int get_sea_digit
(int index, int digit)
{
return sea[index][digit];
}
int get_univ_digit
(int index, int digit)
{
return univ[index][digit];
}
Nested array
Multi-level array
Access looks the same, but it isn’t:
Mem[sea+20*index+4*digit]
Mem[Mem[univ+8*index]+4*digit]

36

160
16
60

168
176
univ

cmu
sfu
ucb
1
5
2
1
3
16
20

24

28

32

36

9
8
1
9
5
36
40

44

48

52

56

9
4
7
2
0
60
64

68

72

76

80

CMPT 295
L09 – Arrays
Depends on how array is declared
Multi-dimensional arrays are a special construct!

Multi-Level Referencing Examples
Reference Address Value Guaranteed?
univ[2][3]
univ[1][5]
univ[2][-2]
univ[3][-1]
univ[1][12]
C code does not do any bounds checking
Location of each lower-level array in memory is not guaranteed

15
36

160
16
60

168
176
univ

cmu
sfu
ucb
1
5
2
1
3
16
20

24

28

32

36

9
8
1
9
5
36
40

44

48

52

56

9
4
7
2
0
60
64

68

72

76

80

CMPT 295
L09 – Arrays
72 2 yes
36 9 no
52 5 no
?? ?? No
64 4 no

int zd2int(zip_dig z)
{
int i;
int zi = 0;
for (i = 0; i < 5; i++) { zi = 10 * zi + z[i]; } return zi; } Array Loop Example 16 zi = 10*0 + 9 = 9 zi = 10*9 + 8 = 98 zi = 10*98 + 1 = 981 zi = 10*981 + 9 = 9819 zi = 10*9819 + 5 = 98195 9 8 1 9 5 typedef int zip_dig[5]; CMPT 295 L09 - Arrays Array Loop Example Original: Transformed: Eliminate loop variable i, use pointer zend instead Convert array code to pointer code Pointer arithmetic on z Express in do-while form (no test at entrance) 17 int zd2int(zip_dig z) { int zi = 0; int *zend = z + 5; do { zi = 10 * zi + *z; z++; } while (z < zend); return zi; } zip_dig sfu; 9 8 1 9 5 36 40 44 48 52 56 address just past 5th digit Increments by 4 (size of int) int zd2int(zip_dig z) { int i; int zi = 0; for (i = 0; i < 5; i++) { zi = 10 * zi + z[i]; } return zi; } CMPT 295 L09 - Arrays 15au: With –Og, gcc will generate different code for each of these. With –O1, the same code. int zd2int(zip_dig z) { int zi = 0; int *zend = z + 5; do { zi = 10 * zi + *z; z++; } while (z < zend); return zi; } Array Loop Implementation 18 gcc with –O1 zd2int(int*): # @zd2int(int*) a3=10,a4=20 mv a2, a0 add a4, a0, a4 # a4=zend # a0 = Base address # a2 = Loop variable .LBB0_1: Loop lw a5, 0(a2) # *z mul a1, a1, a3 # 10 * zi add a1, a1, a5 # 10 * zi + *z addi a2, a2, 4 # increment pointer z++ bne a2, a4, .LBB0_1 # z < zend add a0, zero, a1 ret CMPT 295 L09 - Arrays Arrvindh Shriraman (AS) - Arrvindh Shriraman (AS) - Strange Referencing Examples Reference Address Value Guaranteed? sea[3][3] sea[2][5] sea[2][-1] sea[4][-1] sea[0][19] sea[0][-1] Code does not do any bounds checking Ordering of elements within array guaranteed 19 76+20*3+4*3 = 148 1 Yes 76+20*2+4*5 = 136 9 Yes 76+20*2+4*-1 = 112 5 Yes 76+20*4+4*-1 = 152 5 Yes 76+20*0+4*19 = 152 5 Yes 76+20*0+4*-1 = 72 ?? No typedef int zip_dig[5]; zip_dig sea[4]; 76 96 116 136 156 9 8 1 9 5 9 8 1 0 5 9 8 1 0 3 9 8 1 1 5 CMPT 295 L09 - Arrays