Chapter 3 - Machine-Level Representation of Programs Flashcards
1
Q
What register is used to store where a computer is in its program sequence?
A
The program counter register, %rip.
2
Q
Which register is associated with the program counter?
A
%rip.
3
Q
How many locations are there in a typical modern integer register file?
A
16 registers.
4
Q
How many bits of information can each register in the register file hold?
A
64 bits.
5
Q
What program can be used on a Linux system to view the assembly code of a given object file?
A
objdump.
6
Q
What term is given to the class of programs used to inspect the contents of machine-code files?
A
Disassemblers.
7
Q
What command can be used to generate a file containing the assembly-level version of the source file prog.cc?
A
g++ -Og -S prog.cc
8
Q
Using g++, a source file is translated into both assembly code (with the -S flag) and an executable (with the -o flag). What is likely to be the most noticeable difference after dumping the contents of the generated files? (Either using ‘objdump’ or ‘cat’.)
A
The offset in the address.
9
Q
How does the Intel format differ from the ATT format?
A
- Intel code omits size designation suffixes (i.e. push not pushq).
- Intel code omits the ‘%’ character in front of register names.
- Intel code describes memory locations differently (e.g. QWORD PTR [rbx] rather than (%rbx)).
- Intel code lists operands in reverse order to ATT code.
10
Q
State the number of bytes taken to represent the following data types: char short int long char* float double
A
char -- 1 short -- 2 int -- 4 long -- 8 char* -- 8 float -- 4 double -- 8
11
Q
How many registers did the original 8086 processor have and what size data could they contain?
A
There were eight 16-bit registers.
12
Q
How many registers did the IA32 processor have and what size data could they contain?
A
There were eight 32-bit registers.
13
Q
How many registers does the x86-64 processor have and what size data can it contain?
A
There are 16 64-bit registers.
14
Q
What labels did the registers in the original 8086 processor have?
A
There were eight registers labelled %ax through to %sp.
15
Q
What labels did the registers in the IA32 processor have?
A
There were eight registers labelled %eax through to %esp.
16
Q
What labels do the registers of the x86-64 processor have?
A
There are 16 registers; the first eight registers are labelled %rax through to %rsp, and the other eight are labelled %r8 through %r15.
17
Q
When instructions have registers for destinations, what happens to the remaining bytes when the instructions generate size 1, 2 or 4-byte values?
A
When 1 and 2-byte values are generated, the remaining bytes in the register are left untouched.
When 4-byte values are generated, the high-order 4 bytes are set to zero.
18
Q
Which register is associated with the stack pointer?
A
%rsp.
19
Q
What suffixes are used in integer instructions to indicate the size of the operand?
A
1-byte = 'b' 2-byte = 'w' 4-byte = 'dw' 8-byte = 'qw'
20
Q
What is the syntax for providing an immediate value as an operand to an assembly instruction?
A
The given value is preceded by the $ character.
21
Q
What is the general syntax for providing a memory location as an operand to an assembly instruction?
A
The syntax has the form Imm(rb,ri,s).
22
Q
An assembly instruction is given “Imm(rb,ri,s)” as an operand. Describe what this operand represents.
A
Imm(rb,ri,s) corresponds to the byte at the memory location:
M[ Imm + R[rb] + R[ri] * s ]
The individual terms are: Imm = Immediate offset R[rb] = Base register R[ri] = Index register s = scaling index
23
Q
What are the three main types of operands supplied to assembly instructions?
A
Immediate, register and memory.
24
Q
Assume the following values are stored at the indicated memory addresses and registers:
Address Value 0x100 0xFF 0x104 0xAB 0x108 0x13 0x10C 0x11
Register Value
%rax 0x100
%rcx 0x1
%rdx 0x3
What are the values of the following operands?
260(%rcx,%rdx)
0xFC(,%rcx,4)
(%rax,%rdx,4)
A
260(%rcx,%rdx) = M[0x108] = 0x13.
0xFC(,%rcx,4) = M[0x104] = 0xFF.
(%rax,%rdx,4) = M[0x10C] = 0x11.
25
Name the four instructions in the MOV class.
movb, movw, movl, and movq.
26
True or false? Both operands supplied to a move instruction can be memory locations.
False.
27
How many instructions does it take to copy data from one memory location to another?
Two; one to copy the data into a register and another to copy it to the destination.
28
What is the movabsq instruction used for and what operand can it have for the destination?
To move 64-bit immediate values, and the destination must be a register.
N.B. movq can only handle 32-bit immediate values which are sign-extended to 64 bits.
29
What two classes of move instructions can be used to copy a smaller source to a larger destination?
The movz and movs class.
30
Name the five different movz instructions.
movzbw, movzbl, movzwl, movzbq, and movzwq.
31
Why is there no movzlq instruction?
A 4-byte source is automatically zero extended when copied it to a 8-byte destination, so the movl instruction automatically implements the movzlq instruction.
32
Name the six different movs instructions.
movsbw, movsbl, movswl, movsbq, movswq, and movslq.
33
What instruction requires no operands and sign extends a 4-byte source to a 8-byte location? What register does it operate on?
The cltq instruction, which operates on the %rax register.
34
For each of the following lines of assembly language, determine the appropriate instruction suffix based on the operands.
mov___ %eax, (%rsp)
mov___ (%rax), %dx
mov___ $0xFF, %bl
movl %eax, (%rsp)
movw (%rax), %dx
movb $0xFF, %bl
35
For each of the following lines of assembly language, determine the appropriate instruction suffix based on the operands.
mov___ (%rsp,%rdx,4), %dl
mov___ (%rdx), %rax
mov___ %dx, (%rax)
movb (%rsp,%rdx,4), %dl
movq (%rdx), %rax
movw %dx, (%rax)
36
Each of the following lines of code generates an error message when we invoke the assembler. Explain what is wrong with each line.
movb $0xF, (%ebx)
movl %rax, (%rsp)
movw (%rax),4(%rsp)
movb $0xF, (%ebx)
// Memory references require 8-byte registers.
movl %rax, (%rsp)
// Mismatch between instruction suffix and register ID
movw (%rax),4(%rsp)
// Only one operand can be a memory location.
37
Each of the following lines of code generates an error message when we invoke the assembler. Explain what is wrong with each line.
movb %al,%sl
movq %rax,$0x123
movb %al,%sl
// There is no register named sl.
movq %rax,$0x123
// The destination cannot be an immediate value.
38
Each of the following lines of code generates an error message when we invoke the assembler. Explain what is wrong with each line.
movl %eax,%rdx
movb %si, 8(%rbp)
movl %eax,%rdx
// The destination of the movl instruction cannot be an 8-byte register.
movb %si, 8(%rbp)
// Mismatch between instruction suffix and register ID.
39
Which register is associated with an integer return value?
%rax.
40
Assume variables sp and dp are declared with types
src_t *sp;
dest_t *dp;
where src_t and dest_t are data types declared with typedef. We wish to use the appropriate pair of data movement instructions to implement the operation
*dp = (dest_t) *sp;
Assume that the values of sp and dp are stored in registers %rdi and %rsi. For each entry below, show the two instructions that implement the specified data movement.
S = long, D = long:
movq (%rdi), %rax
movq %rax, (%rsi)
S = char, D = int:
______________
______________
S = char, D = unsigned:
______________
______________
S = char, D = int:
movsbl (%rdi), %eax
movl %eax, (%rsi)
S = char, D = unsigned:
movsbl (%rdi), %eax
movl %eax, (%rsi)
41
Assume variables sp and dp are declared with types
src_t *sp;
dest_t *dp;
where src_t and dest_t are data types declared with typedef. We wish to use the appropriate pair of data movement instructions to implement the operation
*dp = (dest_t) *sp;
Assume that the values of sp and dp are stored in registers %rdi and %rsi. For each entry below, show the two instructions that implement the specified data movement.
S = unsigned char, D = long:
______________
______________
S = int, D = char:
______________
______________
S = unsigned char, D = long:
movzbl (%rdi), %eax
movq %rax, (%rsi)
// Note the special trick with the first step; this relies on the fact that the high-order 4 bytes of the register will be cleared with this instruction.
S = int, D = char:
movl (%rdi), %eax
movb %al, (%rsi)
42
Assume variables sp and dp are declared with types
src_t *sp;
dest_t *dp;
where src_t and dest_t are data types declared with typedef. We wish to use the appropriate pair of data movement instructions to implement the operation
*dp = (dest_t) *sp;
Assume that the values of sp and dp are stored in registers %rdi and %rsi. For each entry below, show the two instructions that implement the specified data movement.
S = unsigned, D = unsigned char:
______________
______________
S = char, D = short:
______________
______________
S = unsigned, D = unsigned char:
movl (%rdi), %eax
movb %al, (%rsi)
S = char, D = short:
movsbw (%rdi), %ax
movw %ax, (%rsi)
43
What discipline does a stack adhere to?
A "last-in, first-out" (LIFO) discipline.
44
What effect does the pushq instruction have?
The stack pointer is decremented by 8 (to allocate 8 bytes) and the quad word provided as an operand is written to the value at the new top-of-stack address.
45
What effect does the popq instruction have?
The quad word is read from the top-of-stack location and stored at the operand destination, then the stack pointer is incremented by 8 (to deallocate 8 bytes).
46
What has the smallest address, the top of the stack or the bottom?
The top.
47
What has the smallest address, the top of the stack or the bottom?
The top.
48
What does the cltq instruction do? How many operands does it take?
It sign extends a 4-byte source to a 8-byte location and requires no operands; it sign extends the data in %eax and stores it at %rax.
49
Which assembly instruction is used to generate pointers?
The leaq instruction.
50
What instruction classes are used to compute x++, x--, -x, and ~x?
```
x++ = INC
x-- = DEC
-x = NEG
~x = NOT
```
51
How many operands do instructions in the INC, DEC, NEG, and NOT classes take?
The instructions in these classes apply unary operations. They take a single operand which corresponds to both the source and the destination.
52
How many operands do instructions in the ADD, SUB, MUL, DIV, XOR, OR and AND classes take?
They take two operands: a source, and a destination (in that order).
53
What are the classes of instructions used for left and right-shift operations? Are they all unique?
SAL, SAR, SHL, SHR. The SAL and SHL are not unique; they both have the same effect.
54
What is the result of the following assembly code?
```
long scale(long x, long y, long z)
x in %rdi, y in %rsi, z in %rdx
scale:
leaq (%rdi,%rsi,4), %rax
leaq (%rdx,%rdx,2), %rdx
leaq (%rax,%rdx,4), %rax
ret
```
long t = x + 4*y + 12*z;
55
What is the result of the following assembly code?
```
short scale3(short x, short y, short z)
x in %rdi, y in %rsi, z in %rdx
scale3:
leaq (%rsi,%rsi,9), %rbx
leaq (%rbx,%rdx), %rbx
leaq (%rbx,%rdi,%rsi), %rbx
ret
```
long t = 10*y + z + x*y;
56
Suppose register %rbx holds value p and %rdx holds value q. Fill in the table below with formulas indicating the value that will be stored in register %rax for each of the given assembly-code instructions:
```
leaq 9(%rdx), %rax
____________
leaq (%rdx,%rbx), %rax
____________
leaq (%rdx,%rbx,3), %rax
____________
```
```
leaq 9(%rdx), %rax = 9+q
leaq (%rdx,%rbx), %rax = p+q
leaq (%rdx,%rbx,3), %rax = q+3*p
```
57
Suppose register %rbx holds value p and %rdx holds value q. Fill in the table below with formulas indicating the value that will be stored in register %rax for each of the given assembly-code instructions:
```
leaq 2(%rbx,%rbx,7), %rax
____________
leaq 0xE(,%rdx,3), %rax
____________
leaq 6(%rbx,%rdx,7), %rax
____________
```
```
leaq 2(%rbx,%rbx,7), %rax = 2+8*p
leaq 0xE(,%rdx,3), %rax = 14+3*q
leaq 6(%rbx,%rdx,7), %rax = 6+p+7*q
```
58
What type of operands can be supplied to a bit-shift instruction?
An immediate value or a single-byte register.
59
What is the shift amount of the following instruction?
| shll $0xF3,%eax
A 32-bit value can only be shifted by 2^5 so only the first five bits of 0xF3 are used, i.e. [10011]. Thus, the shift amount is 19.
60
What does the cqto instruction do?
Convert a quad word to an oct word.
61
What is the difference between the imulq and mulq instructions?
```
imulq = signed multiplication
mulq = unsigned multiplication
```
62
If the imulq and mulq instructions are only provided one operand, what is their function?
They are special instructions that provide full 128-bit multiplication and division.
```
imulq = signed multiplication
mulq = unsigned multiplication
```
63
Name four of the most useful condition flags.
The carry flag, zero flag, sign flag, and overflow flag.
64
What is the carry flag used for?
It indicates that the most recent operation generated a carry out of the most significant bit. It's used to detect overflow of unsigned calculations.
65
What is the zero flag used for?
To indicate that the most recent operation yielded zero.
66
What is the sign flag used for?
To indicate that the most recent operation yielded a negative value.
67
What is the overflow flag used for?
To indicate that the most recent operation caused a two's complement overflow -- either positive or negative.
68
What two classes of instructions set the condition codes without altering any registers?
The CMP and TEST classes of instructions.
69
What is the syntax of an instruction in the CMP family and what is its effect?
Syntax: cmp{b,w,l,q} S_1, S_2.
Effect: Set condition flags based on S_2 - S_1.
70
What is the syntax of an instruction in the TEST family and what is it's effect?
Syntax: test{b,w,l,q} S_1, S_2.
Effect: Set condition flags based on S_2 & S_1.
71
The condition flags are CF, ZF, SF, and OF. Combine them to produce the instruction "setle".
```
(SF ^ OF) | ZF
// Note: this form ensures that the most recent operation has not overflowed.
```
72
The condition flags are CF, ZF, SF, and OF. Combine them to produce the instruction "setg".
```
~(SF ^ OF) & ~ZF
// Note: this form ensures that the most recent operation has not overflowed.
```
73
The C code:
```
int comp(data_t a, data_t b) {
return a COMP b;
}
```
shows a general comparison between arguments a and b, where data_t, the data type of the arguments, is defined (via typedef) to be an integer data types and either signed or unsigned. The comparison COMP is defined via #define.
Suppose a is in some portion of %rdx while b is in some portion of %rsi. For each of the following instruction sequences, determine which data types data_t and which comparisons COMP could cause the compiler to generate this code.
A. cmpl %esi, %edi
setl %al
B. cmpw %si, %di
setge %al
A. cmpl %esi, %edi
setl %al
// Data types: int
// Operation: a=b
74
The C code:
```
int comp(data_t a, data_t b) {
return a COMP b;
}
```
shows a general comparison between arguments a and b, where data_t, the data type of the arguments, is defined (via typedef) to be an integer data types and either signed or unsigned. The comparison COMP is defined via #define.
Suppose a is in some portion of %rdx while b is in some portion of %rsi. For each of the following instruction sequences, determine which data types data_t and which comparisons COMP could cause the compiler to generate this code.
A. cmpb %sil, %dil
setbe %al
B. cmpq %rsi, %rdi
setne %a
A. cmpb %sil, %dil
setbe %al
// Data types: unsigned char
// Operation: a<=b
B. cmpq %rsi, %rdi
setne %a
// Data types: long, unsigned long or a pointer
// Operation: a!=b
75
What three common ways are there to access condition codes?
(1) We can set a single byte to 0 or 1 depending on some combination of the condition codes;
(2) We can conditionally jump to some other part of the program, or;
(3) We can conditionally transfer data.
76
What do the suffixes of the instructions in the SET class denote?
The condition, NOT the data size.
77
The C code:
```
int test(data_t a) {
return a TEST 0;
}
```
shows a general comparison between argument a and 0, where we can set the data type of the argument by declaring data_t with a typedef, and the nature of the comparison by declaring TEST with a #define declaration. The following instruction sequences implement the comparison, where a is held in some portion of register %rdi. For each sequence, determine which data types data_t and which comparisons TEST could cause the compiler to generate this code.
A. testq %rdi, %rdi
setge %al
B. testw %di, %di
sete %al
A. testq %rdi, %rdi
setge %al
// Data types: long
// Operation: a>=0
B. testw %di, %di
sete %al
// Data types: short
// Operation: a==0
78
The C code:
```
int test(data_t a) {
return a TEST 0;
}
```
shows a general comparison between argument a and 0, where we can set the data type of the argument by declaring data_t with a typedef, and the nature of the comparison by declaring TEST with a #define declaration. The following instruction sequences implement the comparison, where a is held in some portion of register %rdi. For each sequence, determine which data types data_t and which comparisons TEST could cause the compiler to generate this code.
A. testb %dil, %dil
seta %al
B. testl %edi, %edi
setle %al
A. testb %dil, %dil
seta %al
// Data types: unsigned char
// Operation: a>0
B. testl %edi, %edi
setle %al
// Data types: int
// Operation: a<=0
79
What instruction can cause the execution to switch to a completely new position in the program?
The jmp instruction.
80
In assembly, what is used to indicate the jump destination?
A label.
81
What is the term given to the addresses of a jump instruction destination?
Jump target.
82
What two types of unconditional jump instruction are there?
A direct and indirect jump.
83
What is the syntax for an indirect jump?
jmp *operand.
The operand is either a register or memory location.
84
What two types of address encoding can be used for jump instructions?
PC relative and with an "absolute" address.
85
What is the target of the je instruction below? (You do not need to know anything about the callq instruction here.)
4003fa: 74 02 je XXXXXX
4003fc: ff d0 callq *%rax
4003fa: 74 02 je XXXXXX
4003fc: ff d0 callq *%rax
// 0x2 is the offset from the byte after the jump instruction, 0x4003fc. Thus, the jump target is 0x4003fe.
86
What is the target of the je instruction below?
40042f: 74 f4 je XXXXXX
400431: 5d pop %rbp
40042f: 74 f4 je XXXXXX
400431: 5d pop %rbp
// The jump is 0xf4=-12. Adding this to 0x400431 gives the jump target 0x400425.
87
What is the address of the ja and pop instructions?
XXXXXX: 77 02 ja 400547
XXXXXX: 5d pop %rbp
```
XXXXXX: 77 02 ja 400547
XXXXXX: 5d pop %rbp
// The jump target, 0x400547, is the address of the byte after the jump instruction plus 0x2. Subtracting 0x2 from 0x400547 gives 0x400545 so the filled in assembly code is:
400543: 77 02 ja 400547
400545: 5d pop %rbp
```
88
In the code that follows, the jump target is encoded in PC-relative form as a 4-byte two’s-complement number. The bytes are listed from least significant to most, reflecting the little-endian byte ordering of x86-64. What is the address of the jump target?
4005e8: e9 73 ff ff ff jmpq XXXXXXX
4005ed: 90 nop
4005e8: e9 73 ff ff ff jmpq XXXXXXX
4005ed: 90 nop
// The target of the jump is encoded as 0xffffff73 (note that this is on a little endian machine). Negating and adding one gives 0x8D=261, so the jump is -0x8D=-261. Therefore, the jump target is 400560.
89
Describe the two ways to implement a conditional transfer of control.
Option 1:
```
t = test-expr;
if (!t)
goto false;
then-statement
goto done;
false:
else-statement
done:
```
Option 2:
```
t = test-expr;
if (t)
goto true;
else-statement
goto done;
true:
then-statement
done:
```
90
You are told about the two types of conditional transfer of control for an if-statement (given below). Which option is better, and why?
Option 1:
```
t = test-expr;
if (!t)
goto false;
then-statement
goto done;
false:
else-statement
done:
```
Option 2:
```
t = test-expr;
if (t)
goto true;
else-statement
goto done;
true:
then-statement
done:
```
Option 1 is better because it is easier to adapt when there is no "else" statement. It is also has a similar structure to the normal form of an if statement.
91
When given the C code:
```
void cond(short a, short *p)
{
if (a && *p < a)
*p = a;
}
```
gcc generates the following assembly code:
```
void cond(short a, short *p)
a in %rdi, p in %rsi
cond:
testq %rdi, %rdi
je .L1
cmpq %rsi, (%rdi)
jle .L1
movq %rdi, (%rsi)
.L1:
rep; ret
```
Explain why the assembly code contains two conditional branches, even though the C code has only one if statement.
The first conditional branch is part of the implementation of the && expression. If the test for a being non-null fails, the code will skip the test of a >= *p.
92
What is the benefit of PC relative addressing?
It allows object code to be relocatable, i.e. it can be shifted to different portions of memory without alteration.
93
What are the two different ways to implement conditional branches?
Conditional transfer of control and conditional transfer of data.
94
When is conditional transfer of data a viable option?
When the amount of data that needs to be computed is small.
95
What does conditional transfer of data involve?
This approach computes both outcomes of a conditional operation and then selects one based on whether or not the condition holds.
96
Fill in the blank:
A conditional transfer of data involves computing both outcomes of a conditional operation and then selecting one based on whether or not the condition holds. This strategy makes sense only in restricted cases, but it can then be implemented by a simple ___________ _______ instruction.
A conditional transfer of data involves computing both outcomes of a conditional operation and then selecting one based on whether or not the condition holds. This strategy makes sense only in restricted cases, but it can then be implemented by a simple conditional move instruction.
97
What instruction class is key to a conditional transfer of data?
The CMOV instruction class.
98
Describe the typical form of a conditional transfer of data.
v = then-expr;
ve = else-expr;
t = test-expr;
if (!t) v = ve;
99
What are the two conditional move instructions for when the result of the most recent operation is equal to zero or not equal to zero?
cmove and cmovne.
100
What are the two conditional move instructions for when the result of the most recent operation is negative or not negative?
cmovs and cmovns.
101
Describe the typical form of an instruction from the CMOV class.
cmov[X] S,D, which moves the data from the source to the destination D when the condition specified by [X] holds.
102
What size registers can be used for conditional move instructions?
2, 4 or 8 byte registers.
103
Give two examples of when conditional data transfers won't be used by the compiler.
For example, when the result of one statement has a side effect or can generate an error condition.
104
In the following C function, we have left the definition of operation OP incomplete:
```
#define OP /* Unknown operator */
short arith(short x) {
return x OP 16;
}
```
When compiled, gcc generates the following assembly code:
```
short arith(short x)
x in %rdi
arith:
leaq 15(%rdi), %rbx
testq %rdi, %rdi
cmovns %rdi, %rbx
sarq $4, %rbx
ret
```
What operation is OP?
OP is the divide operator, implemented with the right shift ">>4"
105
What do processors use to guess whether or not each jump instruction will be followed that allow them to achieve high performance?
Branch prediction logic.
106
State the assembly form of a do-while loop.
```
loop:
body-statement
t = test-expr;
if (t)
goto loop;
```
107
In what two ways are while loops implemented?
As "jump in the middle" and "guarded do" while loops.
108
State the general form of a "jump in the middle" while loop.
```
goto test;
loop:
body-statement
test:
t=test-expr;
if (t)
goto loop;
```
109
State the general form of a "guarded do" while loop.
```
t=test-expr;
if (!t)
goto done;
loop:
body-statement
t=test-expr;
if (t)
goto loop;
done:
```
110
The gcc C compiler generates the following assembly code:
```
short test_one(unsigned short x)
x in %rdi
test_one:
movl $1, %eax
jmp .L5
.L6:
xorq %rdi, %rax
shrq %rdi Shift right by 1
.L5:
testq %rdi, %rdi
jne .L6
andl $0, %eax
ret
```
What loop translation method was used?
A "jump in the middle" while loop.
111
Describe the general form of a for loop based on a "guarded-do" while loop.
```
init-expr;
t=test-expr;
if (!t)
goto done;
loop:
body-statement
update-expr;
t=test-expr;
if (t)
goto loop;
done:
```
112
When might we encounter a problem if we naively applied our rule for translating our for loop into a while loop?
When the body statement contains continue or break statement.
(The update-expr expression would not be evaluated when the continue statement is satisfied resulting in infinite recursion.)
113
Fill in the blank:
A switch statement provides a multiway branching capability based on the value of an integer index. They are particularly useful when dealing with tests where there can be a large number of possible outcomes. Not only do they make the C code more readable, but they also allow an efficient implementation using a data structure called a _____ _____.
A switch statement provides a multiway branching capability based on the value of an integer index. They are particularly useful when dealing with tests where there can be a large number of possible outcomes. Not only do they make the C code more readable, but they also allow an efficient implementation using a data structure called a jump table.
114
What is a jump table?
A jump table is an array where entry i is the address of a code segment implementing the action the program should take when the switch index equals i.
115
When might a jump table be used in a switch statement?
When the test cases span a small range of values and there are a number of cases.
116
What is a "computed goto"?
A goto location determined using a jump table (seen in switch statements).
117
Optional: complete Practice Problem 3.31 on page 274.
Optional: complete Practice Problem 3.31 on page 274.
118
Fill in the blank:
When an x86-64 procedure requires storage beyond what it can hold in registers, it allocates space on the stack. This region is referred to as the procedure’s ______ ______.
When an x86-64 procedure requires storage beyond what it can hold in registers, it allocates space on the stack. This region is referred to as the procedure’s stack frame.
119
What is placed at the top of a function's stack frame when it calls another function?
The return address.
120
Function P calls function Q. Which functions's stack frame does the return address of P go on?
P's stack frame.
121
How many arguments are typically passed on the stack?
If there are six or less arguments then they may all be passed through registers.
If there are more than six arguments, the remaining arguments are store on the stack.
122
What assembly instruction is used to invoke a procedure?
The call instruction.
123
What two registers are always affected by a function call?
%rsp, the stack pointer register, and %rip, the program counter register.
124
Name the six registers used to pass function arguments in the order that they are used.
%rdi, %rsi, %rdx, %rcx, %r8, and %r9.
125
List three common cases in which local variables must be stored on the stack.
1. When there are not enough registers to hold the local data.
2. When the memory address of a variable is required.
3. When some of the local variables are arrays or struct. (Access of these variables require array or structure references.)
126
What is a "callee-saved" register?
A register whose value must be preserved by the callee.
127
What is a "caller-saved" register?
A register whose value must be preserved by the caller.
128
Which registers are classified as "callee-saved"?
%rbx, %rbp, and %r12-%r15.
129
Which registers are classified as "caller-saved"?
All registers except for %rbx, %rbp, %r12-%r15 and %rsp.
130
How can a callee function preserve the value of a callee-saved register?
By not overwriting it or saving its value on the stack and popping it before returning.
131
Suppose that during the execution of a function P, one value is stored in register %rbx and one is stored in register %rdi. Function P does not save these values before calling function Q. Are these values guaranteed to be preserved?
No. Register %rbx is a callee-saved register so its value will be preserved by the function Q, but register %rdi is a caller-saved register so its value should be preserved by function P before invoking function Q.
132
Given an array A with starting address x_A and data type size L, what is the address of element i in the array?
x_A + L*i.
133
Suppose E is an array of values of type int and we wish to evaluate E[i], where the address of E is stored in register %rdx and i is stored in register %rcx. What instruction would be used to access this value and store it in register %eax?
movl (%rdx,%rcx,4), %eax.
134
Suppose E is an array of values of type int and we wish to evaluate *(E+i-3). The address of E is stored in register %rdx and i is stored in register %rcx. What instruction would be used to access this value and store it in register %eax?
*(E+i-3) corresponds to the memory reference M[x_E+4*i-12], which can be evaluated using the instruction:
movl -12(%rdx,%rcx,4), %eax
135
Suppose x_P, the address of short integer array P, and long integer index i are stored in registers %rdx and %rcx, respectively. The result should be stored in register %rax if it is a pointer and register element %ax if it has data type short. Fill in the table below:
Expression: P[1]
Type: _____________
Value: _____________
Assembly code: _____________
Expression: P[1]
Type: short
Value: M[x_P + 2]
Assembly code: movw 2(%rdx), %ax
136
Suppose x_P, the address of short integer array P, and long integer index i are stored in registers %rdx and %rcx, respectively. The result should be stored in register %rax if it is a pointer and register element %ax if it has data type short. Fill in the table below:
Expression: P[2]
Type: _____________
Value: _____________
Assembly code: _____________
Expression: P[2]
Type: short
Value: M[x_P + 4]
Assembly code: movw 4(%rdx), %ax
137
Suppose x_P, the address of short integer array P, and long integer index i are stored in registers %rdx and %rcx, respectively. The result should be stored in register %rax if it is a pointer and register element %ax if it has data type short. Fill in the table below:
Expression: P + 3 + i
Type: _____________
Value: _____________
Assembly code: _____________
Expression: P + 3 + i
Type: short*
Value: x_P + 2*i + 6
Assembly code: leaq 6(%rdx,%rcx,2), %rax
138
Suppose x_P, the address of short integer array P, and long integer index i are stored in registers %rdx and %rcx, respectively. The result should be stored in register %rax if it is a pointer and register element %ax if it has data type short. Fill in the table below:
Expression: P[i * 6 - 5]
Type: _____________
Value: _____________
Assembly code: _____________
Expression: P[i * 6 - 5]
Type: short
Value: M[x_P + 12*i - 10]
Assembly code: movw -10(%rdx,%rcx,12),%ax
139
Suppose x_P, the address of short integer array P, and long integer index i are stored in registers %rdx and %rcx, respectively. The result should be stored in register %rax if it is a pointer and register element %ax if it has data type short. Fill in the table below:
Expression: &P[i + 2]
Type: _____________
Value: _____________
Assembly code: _____________
Expression: &P[i + 2]
Type: short*
Value: x_P + 2*i + 4
Assembly code: leaq 4(%rdx,%rcx,2), %rax
140
Given an array declared as
T D[R][C];
what is the general form for the memory address of array element D[i][j]?
&D[i][j]=x_D + L(C*i+j).
141
Consider the following source code, where M and N are constants declared with #define:
```
long P[M][N];
long Q[N][M];
long sum_element(long i, long j) {
return P[i][j] + Q[j][i];
}
```
In compiling this program, gcc generates the following assembly code:
```
long sum_element(long i, long j)
i in %rdi, j in %rsi
sum_element:
leaq 0(,%rdi,8), %rdx
subq %rdi, %rdx
addq %rsi, %rdx
leaq (%rsi,%rsi,4), %rax
addq %rax, %rdi
movq Q(,%rdi,8), %rax
addq P(,%rdx,8), %rax
ret
```
Determine the values of M and N based on this assembly code.
We can see that the reference to matrix P is at byte offset 8*(7i + j), while the reference to matrix Q is at byte offset 8*(5j + i). From this, we can determine that P has 7 columns, while Q has 5, giving M=5 and N=7.
142
What two mechanisms are provided by C to create data types by combining objects of different types?
Structures and unions.
143
What size does a struct have?
The sum of the sizes of each contained field, plus the padding needed to satisfy the alignment requirement of each field.
144
Consider the following structure declaration:
```
struct rec {
int i;
int j;
int a[2];
int *p;
};
```
Suppose variable r is of type "struct rec*" and is in register %rdi.
What five instructions would be used to implement the following statement?
r->p = &r->a[r->i + r->j];
Command: r->p = &r->a[r->i + r->j];
Register: r in %rdi.
Instructions:
movl 4(%rdi), %eax // Get r->j
addl (%rdi), %eax // Add r->i
cltq // Extend to 8 bytes
leaq 8(%rdi,%rax,4), %rax // Compute &r->a[r->i + r->j]
movq %rax, 16(%rdi) // Store in r->p
145
Consider the following structure declaration:
```
struct test {
short *p;
struct {
short x;
short y;
} s;
struct test *next;
};
```
What are the offsets (in bytes) of the following fields?
p: ____________
s. x: ____________
s. y: ____________
next: ____________
p: 0
s. x: 8
s. y: 10
next: 12
146
Consider the following structure declaration:
```
struct test {
short *p;
struct {
short x;
short y;
} s;
struct test *next;
};
```
The compiler generates the following assembly code for st_init:
```
void st_init(struct test *st)
st in %rdi
st_init:
movl 8(%rdi), %eax
movl %eax, 10(%rdi)
leaq 10(%rdi), %rax
movq %rax, (%rdi)
movq %rdi, 12(%rdi)
ret
```
to implement the code:
```
void st_init(struct test *st) {
st->s.y = _________;
st->p = _________;
st->next = _________;
}
```
Fill in the blanks.
```
void st_init(struct test *st) {
st->s.y = st->s.x;
st->p = st->s.y;
st->next = st;
}
```
147
The following code shows the declaration of a structure of type ACE and the prototype for a function test:
struct ACE {
short v;
struct ACE *p;
};
short test(struct ACE *ptr);
When the code for fun is compiled, gcc generates the following assembly code:
```
short test(struct ACE *ptr)
ptr in %rdi
test:
movl $1, %eax
jmp .L2
.L3:
imulq (%rdi), %rax
movq 2(%rdi), %rdi
.L2:
testq %rdi, %rdi
jne .L3
rep; ret
```
A. Use your reverse engineering skills to write C code for test.
B. Describe the data structure that this structure implements and the operation performed by test.
```
A.
short test(struct ACE *ptr)
{
short result=1;
while (ptr!=0) {result*=ptr->v; ptr=ptr->p;}
return result;
}
```
B. The data structure is a singly-linked list and the function computes the product of all the values in the list.
148
What size does a union have?
The size of the largest field, plus whatever padding is needed to satisfy its alignment requirement.
149
Name a benefit of a union.
It can be used to access the bit pattern of a data type.
150
Suppose we write a procedure that will create an 8-byte double using the bit patterns given by two 4-byte unsigned values, word0 and word1:
```
double uu2double(unsigned word0, unsigned word1)
{
union {
double d;
unsigned u[2];
} temp;
```
temp.u[0] = ________;
temp.u[1] = ________;
return temp.d;
}
Fill in the blanks using the arguments word0 and word1.
On a little endian machine, the least significant bytes (corresponding to word0) will be stored first and the most significant bytes (corresponding to word1) will be stored last. On such a machine, the code is given by:
```
double uu2double(unsigned word0, unsigned word1)
{
union {
double d;
unsigned u[2];
} temp;
```
temp.u[0] = word0;
temp.u[1] = word1;
return temp.d;
}
On a big endian machine, word0 and word1 are the other way around.
151
What are "alignment restrictions"?
The restriction (placed by many computer systems) on the allowable address for the primitive data types, requiring that the address for some objects must be a multiple of some value K (typically 2, 4, or 8).
152
What alignment restriction does a K-byte data type have?
Its address must be a multiple of K.
153
What size does the following struct have?
```
struct S1 {
int i;
char c;
int j;
};
```
12 bytes. This includes the 3 bytes needed to pad the character c so that j meets its 4-byte alignment restriction.
154
What size does the following struct have?
```
struct S2 {
int i;
int j;
char c;
};
```
12 bytes. This includes the 3 bytes needed to pad the end of that structure so that it meets a 4-byte alignment restriction necessary to allocate an array of structs of type S2.
155
For each of the following structure declarations, determine the offset of each field, the total size of the structure, and its alignment requirement for x86-64:
A. struct P1 { short i; int c; int *j; short *d; };
B. struct P2 { int i[2]; char c[8]; short s[4]; long *j; };
```
A. struct P1 { short i; int c; int *j; short *d; };
// Offset (in bytes): i=0, c=4, j=8, d=16.
// Total size: 24 bytes.
// Alignment requirement: 8.
B. struct P2 { int i[2]; char c[8]; short s[4]; long *j; };
// Offset (in bytes): i=0, c=8, s=16, j=24.
// Total size: 32 bytes.
// Alignment requirement: 8.
```
156
For each of the following structure declarations, determine the offset of each field, the total size of the structure, and its alignment requirement for x86-64:
A. struct P3 { long w[2]; int *c[2] };
B. struct P4 { char w[16]; char *c[2] };
```
A. struct P3 { long w[2]; int *c[2] };
// Offset (in bytes): w=0, c=16.
// Total size: 32 bytes.
// Alignment requirement: 8.
B. struct P4 { char w[16]; char *c[2] };
// Offset (in bytes): w=0, c=16.
// Total size: 32 bytes.
// Alignment requirement: 8.
```
157
You are given the structure declarations:
struct P1 { short i; int c; int *j; short *d; };
struct P4 { char w[16]; char *c[2] };
For the following structure declaration, determine the offset of each field, the total size of the structure, and its alignment requirement for x86-64:
A. struct P5 { struct P4 a[2]; struct P1 t };
```
A. struct P5 { struct P4 a[2]; struct P1 t };
// Offset (in bytes): a=0, t=64.
// Total size: 88 bytes.
// Alignment requirement: 3 bytes to pad short i.
```
158
What is "buffer overflow"?
A common source of state corruption resulting from an out-of-bounds access.
159
Optional: complete practice problem 3.46.
Optional: complete practice problem 3.46.
160
What is the term given to code which is used to maliciously take advantage of buffer overflow vulnerabilities?
Exploit code.
161
Name three techniques used to thwart buffer overflow attacks.
Stack randomisation (subset of ASLR; address-space layout randomisation), stack protection, and limiting the regions of memory that can hold executable code.
162
What is "stack randomisation"?
The randomisation of the position of the stack used to help thwart buffer overflow attacks.
163
What is "stack protection"?
Stack protection refers to the usage of a "canary" value on the stack to detect whether a buffer has overflowed.
164
Name a common (brute force) trick that an attacker can use to overcome stack randomisation and create a buffer overflow.
Adding a "nop sled" (consisting of a long sequence of "nop"s) before the actual exploit code.
This increases the chances of the overwritten return address jumping onto the exploit code.
165
Where is a stack protector (or a guard value) typically placed?
Between any local buffer and the rest of the stack state.
166
How does a stack protector work?
It is placed between any local buffer and the rest of the stack state once storage on the stack is allocated. Before restoring the register state and returning from the function, the program checks if the guard value has been altered. If so, the program aborts with an error.
167
How is a variable-size stack frame managed?
Using the frame (or base) pointer, %rbp.
168
What is the frame pointer and what is it's purpose?
Register %rbp serves as a frame pointer, and is used to manage variable size stack frames.
169
What instruction is used before "ret" to restore the base pointer and the stack pointer? What two instructions is it equivalent to?
The "leave" instruction.
It is equivalent to the instructions:
movq %rbp, %rsp
// Set the stack pointer to the beginning of the frame
popq %rbp
// Restore the saved value of %rbp (a callee-saved register) and set the stack pointer to the end of caller's frame.
170
With x86-64 code, when is the frame pointer used?
When the stack frame may be of variable size.
171
Optional: complete practice problem 3.49.
Optional: complete practice problem 3.49.
172
Early media instructions used to support graphics and image processing and originally focused on allowing multiple operations to be performed in parallel. What is the name of this parallel mode?
Single-instruction, multiple-data (SIMD) mode.
173
In 1997, both Intel and AMD introduced a SIMD mode with the MMX extension to the x86 architecture. Name two further revisions of the MMX extension. What do the initials of each stand for?
SSE (streaming SIMD extensions) and AVX (advanced vector extensions).
174
How many bits/bytes can an XMM register hold?
128 bits/16 bytes.
175
How many bits/bytes can a YMM register hold?
256 bits/32 bytes.
176
Which media registers are dedicated to storing procedure arguments?
Registers %ymm0-%ymm7.
177
Which media registers are caller-saved?
Registers %ymm8-%ymm15.
178
State the instructions used to unconditionally move data between XMM registers and memory (not register to register).
vmovss (single-precision) and vmovsd (double-precision)
179
State the instructions used to unconditionally move data between XMM registers (not to or from memory).
vmovaps and vmovapd.
180
State the four instructions used to convert a floating-point (float/double) number to an integer (int/long) and the possible source/destinations.
vcvttss2si, vcvttsd2si, vcvttss2siq, and vcvttsd2siq.
The source can either be a memory location or XMM register and the destination must be an integer register.
181
State the four instructions used to convert an integer (int/long) to a floating-point (float/double) number and the possible source/destinations.
vcvtsi2ss, vcvtsi2sd, vcvtsi2ssq, and vcvtsi2sdq.
The first source can be an integer register or a memory location but the second source must be an XMM register. The destination must be an XMM register.
182
What two instructions are used to convert a float to a double?
vunpcklps %xmm0, %xmm0, %xmm0
// Interleave values in sources and store in destination.
vcvtps2pd %xmm0, %xmm0
// Convert two vector elements to a double.
183
What two instructions are used to convert a double to a float?
vmovddup %xmm0, %xmm0
// Replicate first vector element.
vcvtpd2psx %xmm0, %xmm0
// Convert two vector elements to single.
184
The vunpcklps instruction is supplied two distinct source registers. The first contains the words [s3, s2, s1, s0] and the other contains words [d3, d2, d1, d0]. What will be the result of this instruction?
[s1, d1, s0, d0].
185
For the following C code, the expressions val1-val4 all map to the program values i, f, d, and l:
```
double fcvt2(int *ip, float *fp, double *dp, long l)
{
int i = *ip; float f = *fp; double d = *dp;
*ip = (int) val1;
*fp = (float) val2;
*dp = (double) val3;
return (double) val4;
}
```
Determine the mapping, based on the following x86-64 code for the function:
```
// double fcvt2(int *ip, float *fp, double *dp, long l)
// ip in %rdi, fp in %rsi, dp in %rdx, l in %rcx
// Result returned in %xmm0
fcvt2:
movl (%rdi), %eax
vmovss (%rsi), %xmm0
vcvttsd2si (%rdx), %r8d
movl %r8d, (%rdi)
vcvtsi2ss %eax, %xmm1, %xmm1
vmovss %xmm1, (%rsi)
vcvtsi2sdq %rcx, %xmm1, %xmm1
vmovsd %xmm1, (%rdx)
vunpcklps %xmm0, %xmm0, %xmm0
vcvtps2pd %xmm0, %xmm0
ret
```
```
val1 = d.
val2 = i.
val3 = l.
val4 = f.
```
186
The following C function converts an argument of type src_t to a return value of type dst_t, where these two types are defined using typedef:
```
dest_t cvt(src_t x)
{
dest_t y = (dest_t) x;
return y;
}
```
For execution on x86-64, assume that argument x is either in %xmm0 or in the appropriately named portion of register %rdi (i.e., %rdi or %edi). One or two instructions are to be used to perform the type conversion and to copy the value to the appropriately named portion of register %rax (integer result) or %xmm0 (floating-point result). Show the instruction(s), including the source and
destination registers.
src_t: long
dest_t: double
Instruction(s): vcvtsi2sdq %rdi, %xmm0
src_t: double
dest_t: int
Instruction(s): ________________
src_t: double
dest_t: float
Instruction(s): ________________
src_t: double
dest_t: int
Instruction(s): vcvttsd2sdi %xmm0, %eax
```
src_t: double
dest_t: float
Instruction(s):
vmovddup %xmm0, %xmm0
vcvtpd2psx %xmm0, %xmm0
```
187
The following C function converts an argument of type src_t to a return value of type dst_t, where these two types are defined using typedef:
```
dest_t cvt(src_t x)
{
dest_t y = (dest_t) x;
return y;
}
```
For execution on x86-64, assume that argument x is either in %xmm0 or in the appropriately named portion of register %rdi (i.e., %rdi or %edi). One or two instructions are to be used to perform the type conversion and to copy the value to the appropriately named portion of register %rax (integer result) or %xmm0 (floating-point result). Show the instruction(s), including the source and
destination registers.
src_t: long
dest_t: float
Instruction(s): ________________
src_t: float
dest_t: long
Instruction(s): ________________
src_t: long
dest_t: float
Instruction(s): vcvtsi2ssq %rdi, %xmm0, %xmm0
src_t: float
dest_t: long
Instruction(s): vcvttss2siq %xmm0, %rax
188
State the seven floating-point arithmetic operations (for float or double).
```
Add: vaddss or vaddsd
Subtract: vsubss or vsubsd
Multiply: vmulss or vmulsd
Divide: vdivss or vdivsd
Max: vmaxss or vmaxsd
Min: vminss or vminsd
Square root: sqrtss or sqrtsd
```
189
For the following C function, the types of the four arguments are defined by typedef:
```
double funct1(arg1_t p, arg2_t q, arg3_t r, arg4_t s)
{
return p/(q+r) - s;
}
```
When compiled, gcc generates the following code:
```
// double funct1(arg1_t p, arg2_t q, arg3_t r, arg4_t s)
funct1:
vcvtsi2ssq %rsi, %xmm2, %xmm2
vaddss %xmm0, %xmm2, %xmm0
vcvtsi2ss %edi, %xmm2, %xmm2
vdivss %xmm0, %xmm2, %xmm0
vunpcklps %xmm0, %xmm0, %xmm0
vcvtps2pd %xmm0, %xmm0
vsubsd %xmm1, %xmm0, %xmm0
ret
```
Determine the possible combinations of types of the four arguments (there may be more than one).
```
double funct1a(int p, float q, long r, double s);
or
double funct1b(int p, long q, float r, double s);
```
190
Function funct2 has the following prototype:
double funct2(double w, int x, float y, long z);
Gcc generates the following code for the function:
```
// double funct2(double w, int x, float y, long z)
// w in %xmm0, x in %edi, y in %xmm1, z in %rsi
funct2:
vcvtsi2ss %edi, %xmm2, %xmm2
vmulss %xmm1, %xmm2, %xmm1
vunpcklps %xmm1, %xmm1, %xmm1
vcvtps2pd %xmm1, %xmm2
vcvtsi2sdq %rsi, %xmm1, %xmm1
vdivsd %xmm1, %xmm0, %xmm0
vsubsd %xmm0, %xmm2, %xmm0
ret
```
Write a C version of funct2.
```
double funct2(double w, int x, float y, long z)
{
return x*y - w/z;
}
```
191
State two instructions that apply Boolean operations on an XMM register.
vxorps, vxorpd, vandps and vandpd.
192
What two instructions does AVX2 provide for comparing floating-point values?
vcomiss and vcomisd.
193
When is the parity flag set for integer operations?
When the least significant byte of the most recent operation contains an even number of bytes.
194
When is the parity flag set for floating-point operations?
When the most recent operation yielded NaN.
195
What are the values of the condition codes (with floating-point operations) when the "unordered case" arises?
The carry flag, zero flag and parity flag are all set to true.
196
What does the "jp" instruction stand for and when is it used?
"Jump on parity". It is used to jump when the result of the most recent floating-point operation yielded NaN.
