CS计算机代考程序代写 compiler assembly assembler Microsoft PowerPoint – 27_X86-64_Assembly_Language_Part_7

Microsoft PowerPoint – 27_X86-64_Assembly_Language_Part_7

O
SU

C
SE

2
42

1

J.E.Jones

Required Reading: Computer Systems: A Programmer’s Perspective, 3rd Edition Chapter 3,
Section 3.8 through 3.8.4 (inclusive)

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

 Most General Form of the address expression
Imm(Rb,Ri,S) Mem[Imm+ Reg[Rb]+S*Reg[Ri]]

or Address = Imm+Rb+Ri*S
◦ Imm: Constant “displacement”
 It’s often a “displacement” of 1, 2, 4 or 8 bytes, but can be any constant value

◦ Rb: Base register: Any of the16 integer registers
◦ Ri: Index register: Any register except %rsp
◦ S: Scale: Only 1, 2, 4, or 8 (why these numbers?)
◦ This form is seen often when referencing elements of arrays
◦ DON’T CONFUSE Imm and S!!
 Imm can be *any* constant
 S can only be 1, 2, 4, or 8

O
SU

C
SE

2
42

1

J. E. Jones

 Review
◦ If p is a pointer to data type T
◦ And the value of p (i.e., an address) is x_p
◦ Then, then p+i has value x_p + L*i
 where, L is the size of data type T

◦ Thus, for an array A of elements, A[i] == *(A+i)
◦ In C the compiler takes care of multiplying i by L for us

 Example
◦ int E[10]; /*Assume int is 4 bytes long */

C expression Type Comment
E int * Address to start of array

E[i] int Value of array element i
&(E[i]) int * Address of array element i
E+i-1 int * Address of array element i-1

*(E+i-3) int Value of array element i-3

O
SU

C
SE

2
42

1

J. E. Jones

 X86-64 is consistent with what we saw in C to a point
◦ If p is a pointer to data type T
◦ And the value of p (i.e., an address) is x_p
◦ Then, then p+i has value x_p + L*i
 where, L is the size of data type T

◦ Thus, for an array A of elements, A[i] == *(A+L*i)
◦ In x86-64 we must take care of multiplying i by L ourselves
 Usually, the easiest way to do this is with Imm(Base, Index, Scale)

constructs
 Example
◦ int E[10]; /*Assume int is 4 bytes long */
◦ Suppose rdx holds starting address of array E
◦ Suppose rcx holds integer index i

C expression Type Assembly code result in rax/eax Comment
E int * movq %rdx, %rax Address copy

E[i] int
movl (%rdx,%rcx,4),%eax, or
movl E(,%rcx,4), %eax if E is a label Reference memory

&(E[i]) int * leaq (%rdx,%rcx,4),%rax Generate address

E+i-1 int * leaq -4(%rdx,%rcx,4),%rax Generate address

*(E+i-3) int movl -12(%rdx,%rcx,4),%eax Reference memory

Note memory
reference is 4-bytes

Note memory
address is 8-bytes

O
SU

C
SE

2
42

1

J. E. Jones

 C declaration: type array[length]
 Arrays store multiple data objects of the same type
 Stored sequentially, often accessed as an offset from a pointer which points

to the beginning of the array.
◦ size = length*sizeof(type)

 If x is the address of the first byte of the first element in the array, then
array element i will be stored at address x+sizeof(type)*i

 THIS DOESN’T CHANGE BETWEEN C AND x86!
◦ Nor should it since all C code gets compiled to assembler within gcc
◦ If it wasn’t consistent nothing would work!

O
SU

C
SE

2
42

1

J. E. Jones

 Basic Principle
T A[L];
◦ Array of data type T and length L
◦ Contiguously allocated region of L * sizeof(T) bytes in memory
char string[12];

if char *x==string
x x + 12

int val[5];
if int *x==val

val[0] val[1] val[2] val[3] val[4]

x x + 4 x + 8 x + 12 x + 16 x + 20

double a[3];
if x==a

p[0] p[1] p[2]

x + 24x x + 8 x + 16

char *p[3];
if x==p

a[0] a[1] a[2]

x + 24x x + 8 x + 16

O
SU

C
SE

2
42

1

J. E. Jones

 Basic Principle
T A[L];
◦ Array of data type T and length L
◦ Identifier A can be used as a pointer to array element 0: Type T*

 Reference Type Value
val[4] int 3
val int * x
val+1 int * x + 4
&val[2] int * x + 8
val[5] int ??
*(val+1) int 5
val + i int * x + 4 i

int val[5]; 1 5 2 1 3

x x + 4 x + 8 x + 12 x + 16 x + 20

O
SU

C
SE

2
42

1

J. E. Jones

 Declaration zip_dig cmu equivalent to int cmu[5]
 Example arrays were allocated in successive 20-byte blocks
◦ Not guaranteed to happen in general

#define ZLEN 5
typedef int zip_dig[ZLEN];

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

zip_dig cmu; 1 5 2 1 3

16 20 24 28 32 36

zip_dig mit; 0 2 1 3 9

36 40 44 48 52 56

zip_dig ucb; 9 4 7 2 0

56 60 64 68 72 76

O
SU

C
SE

2
42

1

J. E. Jones

 Register %rdi contains
starting address of
array

 Register %rsi contains
array index

 Desired digit at
%rdi + 4*%rsi

 Use memory reference
(%rdi,%rsi,4)

 use movl instruction
to move 4 bytes

 Use 4-byte register
%eax as destination

int get_digit(zip_dig z, int digit)
{
return z[digit];

}

# %rdi = z
# %esi = digit

movl (%rdi,%rsi,4), %eax # z[digit]

x86‐64

zip_dig cmu; 1 5 2 1 3

16 20 24 28 32 36

O
SU

C
SE

2
42

1

J. E. Jones

# %rdi = z
movq $0, %rax # i = 0

Loop: # loop:
incl (%rdi,%rax,4) # z[i]++
incq %rax # i++

Test: # middle
cmpq $4, %rax # i:4 (ZLEN-1)
jle Loop # if <=, goto Loop ret # ret void zincr(zip_dig z) { size_t i; for (i = 0; i < ZLEN; i++) z[i]++; } O SU C SE 2 42 1 J. E. Jones  Consider the following C code: static int array[30]; static int x = array[25];  Which is equivalent to assembly code: REMINDER: $ in assembly language with a label gives an address. array and x must have been defined in the data segment (.data section) of the program. pushq %rbx movq $array, %rbx # %rbx is base register movq $25, %rcx # %rcx is index register movl (%rbx,%rcx,4),%eax # %eax = array[25] movl %eax, $x # x = %eax popq %rbx Why can’t we combine the last 2 instructions? movl (%rbx, %rcx,4), $x O SU C SE 2 42 1 J. E. Jones  Consider the following C code: static int array[30]; static int x = array[25];  Which is equivalent to assembly code: REMINDER: $ in assembly language with a label gives an address. array and x must have been defined in the data segment (.data section) of the program. movq $array, %rbx # %rbx is base register movq $25, %rcx # %rcx is index register movl (%rbx,%rcx,4),%eax # %eax = array[25] movl %eax, $x # x = array[25] Why can’t we combine the last 2 instructions? movl (%rbx, %rcx,4), $x Because memory to memory moves are not legal in x86-64 O SU C SE 2 42 1 J. E. Jones  static int array[30];  static int x;  .section .rodata  .data  .align 4  array:  .skip 120, 0  x:  .long 0 C code X86-64 equivalent O SU C SE 2 42 1 J. E. Jones C code: int MyFunction1() { int data[20]; ... } What are the class/scope/linkage of the array? O SU C SE 2 42 1 J. E. Jones C code: int MyFunction1() { int data[20]; ... } What are the class/scope/linkage of the array? Automatic/Block/None Where is the array located? Stack or Heap? O SU C SE 2 42 1 J. E. Jones C code: int MyFunction1() { int data[20]; ... } What are the class/scope/linkage of the array? Automatic/Block/None Where is the array located? Stack or Heap? Stack. So how do we do that in x86-64?? O SU C SE 2 42 1 J. E. Jones C code: int MyFunction1() { int data[20]; ... } x86-64 code: MyFunction1: pushq %rbp # must do stack housekeeping first movq %rsp, %rbp subq $80,%rsp #Allocate space for array #on the stack: 20 elements, 4 bytes each=80 bytes leaq (%rsp), %rax #using %rax as base register for int data[20] array #OR movq %rsp, %rax movl (%rax,%rsi,4), %edx ... O SU C SE 2 42 1 J. E. Jones C code: void MyFunction2() { char buffer[6]; ... } x86-64 code: MyFunction2: pushq %rbp movq %rsp, %rbp subq $6,%rsp # allocate 6 bytes for array leaq (%rsp), %rax # %rax is base register for char buffer[6] # OR movq %rsp, %rax ... O SU C SE 2 42 1 J. E. Jones MyFunction2: pushq %rbp movq %rsp, %rbp subq $6, %rsp leaq (%rsp), %rax #OR movq %rsp, %rax ... Caller Ret Address 8-byte value When we enter MyFunction2: %rsp Lower Addresses Higher Addresses O SU C SE 2 42 1 J. E. Jones MyFunction2: pushq %rbp movq %rsp, %rbp subq $6, %rsp leaq (%rsp), %rax #OR movq %rsp, %rax ... Caller’s %rbp 8-byte value Caller Ret Address 8-byte value After pushq %rbp : %rsp Lower Addresses 1 byte chunks 8 byte chunks Higher Addresses O SU C SE 2 42 1 J. E. Jones MyFunction2: pushq %rbp movq %rsp, %rbp subq $6, %rsp leaq (%rsp), %rax #OR movq %rsp, %rax ... Caller’s %rbp 8-byte value Caller Ret Address 8-byte value After movq %rsp, %rbp: %rsp %rbp Lower Addresses 1 byte chunks 8 byte chunks Higher Addresses O SU C SE 2 42 1 J. E. Jones MyFunction2: pushq %rbp movq %rsp, %rbp subq $6, %rsp leaq (%rsp), %rax #OR movq %rsp, %rax ... buffer[0] 1-byte value buffer[1] 1-byte value buffer[2] 1-byte value buffer[3] 1-byte value buffer[4] 1-byte value buffer[5] 1-byte value Caller’s %rbp 8-byte value Caller Ret Address 8-byte value Lower Addresses 1 byte chunks 8 byte chunks Higher Addresses %rax %rsp After subq $6, %rsp %rax+6 %rbp %rax+12 2nd byte of 8 byte %rbp O SU C SE 2 42 1 J. E. Jones MyFunction2: pushq %rbp movq %rsp, %rbp subq $6, %rsp leaq (%rsp), %rax #OR movq %rsp, %rax ... buffer[0] 1-byte value buffer[1] 1-byte value buffer[2] 1-byte value buffer[3] 1-byte value buffer[4] 1-byte value buffer[5] 1-byte value Caller’s %rbp 8-byte value Caller Ret Address 8-byte value Lower Addresses 1 byte chunks 8 byte chunks Higher Addresses %rax %rsp After leaq (%rsp), %rax %rax+6 %rbp %rax+12 2nd byte of 8 byte %rbp O SU C SE 2 42 1 J. E. Jones MyFunction2: pushq %rbp movq %rsp, %rbp subq $6, %rsp leaq (%rsp), %rax #OR movq %rsp, %rax pushq %rbx ... %rbx 8-byte value buffer[0] 1-byte value buffer[1] 1-byte value buffer[2] 1-byte value buffer[3] 1-byte value buffer[4] 1-byte value buffer[5] 1-byte value Caller’s %rbp 8-byte value Caller Ret Address 8-byte value %rax %rsp %rax+6 %rbp %rax+12 2nd byte of 8 byte %rbp Lower Addresses 1 byte chunks 8 byte chunks Higher Addresses O SU C SE 2 42 1 J. E. Jones MyFunction2: pushq %rbp movq %rsp, %rbp subq $6, %rsp leaq (%rsp), %rax #OR movq %rsp, %rax pushq %rbx ... Note %rsp continues to change, but we still have %rax that contains the starting address of the array %rbx 8-byte value buffer[0] 1-byte value buffer[1] 1-byte value buffer[2] 1-byte value buffer[3] 1-byte value buffer[4] 1-byte value buffer[5] 1-byte value Caller’s %rbp 8-byte value Caller Ret Address 8-byte value %rax %rsp %rax+6 %rbp %rax+12 2nd byte of 8 byte %rbp Lower Addresses 1 byte chunks 8 byte chunks Higher Addresses O SU C SE 2 42 1 J. E. Jones MyFunction2: pushq %rbp movq %rsp, %rbp subq $6, %rsp leaq (%rsp), %rax #OR movq %rsp, %rax pushq %rbx ... What happens if %rcx equals 12, and the code tries to access (%rax,%rcx,1)? For example, suppose %dl equals 5, and this instruction is executed: movb %dl, (%rax,%rcx,1) %rbx 8-byte value buffer[0] 1-byte value buffer[1] 1-byte value buffer[2] 1-byte value buffer[3] 1-byte value buffer[4] 1-byte value buffer[5] 1-byte value Caller’s %rbp 8-byte value Caller Ret Address 8-byte value Lower Addresses 1 byte chunks 8 byte chunks Higher Addresses %rax %rsp %rax+6 %rbp %rax+12 2nd byte of 8 byte %rbp O SU C SE 2 42 1 J. E. Jones MyFunction2: pushq %rbp movq %rsp, %rbp subq $6, %rsp leaq (%rsp), %rax #OR movq %rsp, %rax pushq %rbx ... What happens if %rcx equals 12, and the code tries to access (%rax,%rcx,1)? For example, suppose %dl equals 5, and this instruction is executed: movb %dl, (%rax,%rcx,1) Buffer Overflow! What was on the stack where we wrote 5?? We may have written over something important! %rbx 8-byte value buffer[0] 1-byte value buffer[1] 1-byte value buffer[2] 1-byte value buffer[3] 1-byte value buffer[4] 1-byte value buffer[5] 1-byte value Caller’s %rbp 8-byte value Caller Ret Address 8-byte value Lower Addresses 1 byte chunks 8 byte chunks Higher Addresses %rax %rsp %rax+6 %rbp %rax+12 2nd byte of 8 byte %rbp 5 O SU C SE 2 42 1 J. E. Jones  Look for large allocation on the stack  Look for data references using a register other than %rsp or %rbp as the base StackArrayEx: pushq %rbp movq %rsp, %rbp pushq %rbx subq $520, %rsp leaq (%rsp), %rbx #OR movq %rsp, %rbx movl $0x0,(%rbx) #set first element to 0 What options can you think of for how the array was declared? O SU C SE 2 42 1 J. E. Jones  Look for large allocation on the stack  Look for data references using a register other than %rsp or %rbp as the base StackArrayEx: pushq %rbp movq %rsp, %rbp subq $520, %rsp leaq (%rsp), %rbx #OR movq %rsp, %rbx movl $0x0,(%rbx) #set first element to 0 What options can you think of for how the array was declared? char buffer[520]; O SU C SE 2 42 1 J. E. Jones  Look for large allocation on the stack  Look for data references using a register other than %rsp or %rbp as the base StackArrayEx: pushq %rbp movq %rsp, %rbp subq $520, %rsp leaq (%rsp), %rbx #OR movq %rsp, %rbx movl $0x0,(%rbx) #set first element to 0 What options can you think of for how the array was declared? char buffer[520]; short buffer[260]; Any of these would be options, right? int buffer[130]; long buffer[65]; O SU C SE 2 42 1 J. E. Jones  Look for large allocation on the stack  Look for data references using a register other than %rsp or %rbp as the base StackArrayEx: pushq %rbp movq %rsp, %rbp subq $520, %rsp leaq (%rsp), %rbx #OR movq %rsp, %rbx movl $0x0,(%rbx) #set first element to 0 What options can you think of for how the array was declared? char buffer[520]; short buffer[260]; Any of these would be options, right? int buffer[130]; This one is likely the correct one, since code above uses ‘l’ suffix to set first element to 0. long buffer[65]; O SU C SE 2 42 1 J. E. Jones  For the array on the preceding slide, how could the compiler generate code for a loop to initialize all the array elements to 0? StackArrayEx: pushq %rbp movq %rsp, %rbp subq $520, %rsp pushq %rbx leaq (%rsp), %rbx #base register #OR movq %rsp, %rbx movq $130, %rcx # number of array elements initialize: decq %rcx # decrement index jl next # if less than 0 done Why not jle?? movl $0x0, (%rbx,%rcx,4) # set 4 bytes of memory to zero jmp initialize # go again next: … O SU C SE 2 42 1 J. E. Jones  For the array on the preceding slides, what needs to happen with respect to cleanup before return? StackArrayEx: #CREATION pushq %rbp movq %rsp, %rbp subq $520, %rsp leaq (%rsp), %rcx #base register #OR movq %rsp, %rcx buffer[0] 4-byte value buffer[1] 4-byte value buffer[2] 4-byte value buffer[3] 4-byte value buffer[4] 4-byte value buffer[129] 4-byte value Caller’s %rbp 8-byte value Caller Ret Address 8-byte value %rsp %rcx %rbp O SU C SE 2 42 1 J. E. Jones  For the array on the preceding slides, what needs to happen with respect to cleanup before return? StackArrayEx: #CREATION pushq %rbp movq %rsp, %rbp subq $520, %rsp leaq (%rsp), %rcx #base register #OR movq %rsp, %rcx Return: #CLEANUP movq %rbp, %rsp #leave instruction popq %rbp ret buffer[0] 1-byte value buffer[1] 1-byte value buffer[2] 1-byte value buffer[3] 1-byte value buffer[4] 1-byte value buffer[519] 1-byte value Caller’s %rbp 8-byte value Caller Ret Address 8-byte value %rsp %rcx %rbp %rsp %rbp O SU C SE 2 42 1 J. E. Jones  “Global” Arrays (i.e., Static Class/Can be either File or Block Scope)  Arrays of elements with initial values of 0 by default ◦ If stored in the .data section of application (i.e., static arrays)  Accessed through a memory address .section .data staticArray1: .skip 48,0 # staticArray1 is 48 bytes long # initialized to zero # equivalent to static char staticArray1[48]; .align 4 staticArray2: .long 1 # staticArray2 is 20 bytes long .long 2 # equivalent to .long 3 # static int staticArray2[5]={1,2,3,4,5} .long 4 .long 5 O SU C SE 2 42 1 J. E. Jones  “Global” Arrays (i.e. Static Class/Can be either File or Block Scope)  Arrays of elements with initial values of 0 by default ◦ If stored in the data section of application (i.e., static arrays)  Accessed through a memory address MemArrayEx: pushq %rbp movq %rsp, %rbp pushq %rbx movq $staticArray1, %rsi #base register movq $0x0, %rbx #index register movb $0x0,(%rsi,%rbx,1) #set 1st element to 0 O SU C SE 2 42 1 J. E. Jones  If an array holds elements larger than 1 byte, the index will need to be multiplied by the size of the element ◦ The Scale element of the address computation takes care of that for us #access to array of elements of size 4, #with scaling, where rax holds the index i, #and rbx is base register: #e.g., arr[i] = 0x11223344 movl $0x11223344, (%rbx,%rax,4) ... O SU C SE 2 42 1 J. E. Jones  What if the array holds elements larger than 8 bytes? For example, what if it is an array of structures?  Recall that, in x86-64, scaling factors can only be: 1, 2, 4, or 8 so (%rbx, %rcx, 20) won’t compile!!  Therefore, for arrays with elements larger than 8 bytes, manual scaling must be used  What if we had an array of structures where each structure is 20 bytes??? #Here, two index registers are used, one #for the conventional index (here, %rcx), 0 <= %rcx =< n -1 #and one for a scaled index register, #here, %rax. This is “manual scaling.” 0<= %rax <= 20*(n-1) movq $5, %rcx # if we want to access element at index 5… # signed multiply #%rax = 20*%rcx # imulq aux, src, Dest imulq $20,%rcx,%rax # manually scale index, NOTE! 3 operand mult #Suppose we want: ptr = &arr[5] leaq (%rbx,%rax), %rdx # what is in %rdx??? O SU C SE 2 42 1 J. E. Jones  What if the array holds elements larger than 8 bytes? For example, what if it is an array of structures?  Recall that, in x86-64, scaling factors can only be: 1, 2, 4, or 8 so (%rbx, %rcx, 20) won’t compile!!  Therefore, for arrays with elements larger than 8 bytes, manual scaling must be used  What if we had an array of structures where each structure is 20 bytes??? #Here, two index registers are used, one #for the conventional index (here, %rcx), 0 <= %rcx =< n -1 #and one for a scaled index register, #here, %rax. This is “manual scaling.” 0<= %rax <= 20*(n-1) movq $5, %rcx # if we want to access element at index 5… # signed multiply #%rax = 20*%rcx # imulq aux, src, Dest imulq $20,%rcx,%rax # manually scale index, NOTE! 3 operand mult #Suppose we want: ptr = &arr[5] leaq (%rbx,%rax), %rdx # what is in %rdx??? Address to beginning of structure in an array! O SU C SE 2 42 1 J. E. Jones  What if the array holds elements larger than 8 bytes? For example, what if it is an array of structures?  Recall that, in x86-64, scaling factors can only be: 1, 2, 4, or 8 so (%rbx, %rcx, 20) won’t compile!!  Therefore, for arrays with elements larger than 8 bytes, manual scaling must be used  What if we had an array of structures where each structure is 20 bytes??? #Here, two index registers are used, one #for the conventional index (here, %rcx), #and one for a scaled index register, #here, %rax. This is “manual scaling.” movq $0, %rcx # signed multiply # imulq aux, src, Dest imulq $20,%rcx,%rax # manually scale index, NOTE! 3 operand mult #Suppose we want: ptr = &arr[i] leaq (%rbx,%rax), %rdx # what is in %rdx??? Address to beginning of structure in an array!