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!