Andrew login ID: Full Name:
Recitation Section:
CS 15-213, Spring 2008 Exam 1
Tue. February 26, 2008
Copyright By PowCoder代写 加微信 powcoder
Instructions:
• Make sure that your exam is not missing any sheets, then write your full name, Andrew login ID, and recitation section (A–H) on the front.
• Write your answers in the space provided below the problem. If you make a mess, clearly indicate your final answer.
• The exam has a maximum score of 70 points.
• The problems are of varying difficulty. The point value of each problem is indicated. Pile up the easy
points quickly and then come back to the harder problems.
• This exam is OPEN BOOK. You may use any books or notes you like. No calculators or other electronic devices are allowed.
• Good luck!
TOTAL (70):
Page 1 of 10
Problem 1. (8 points):
For this problem, assume the following:
• We are running code on a 6-bit machine using two’s complement arithmetic for signed integers. • short integers are encoded using 3 bits.
• Sign extension is performed whenever a short is casted to an int
• Right shifts of ints are arithmetic.
Fill in the empty boxes in the table below. The following definitions are used in the table:
int a = -29;
short b = (short)a; unsigned ua = a; int x = -21;
short y = (short)x; unsigned ux = x;
Note: You need not fill in entries marked with “—”.
Expression
Decimal Representation
Binary Representation
−T 2 of 10
Problem 2. (8 points):
Fill in the blanks in the table below with the number described in the first column of each row. You can give your answers as unexpanded simple arithmetic expressions (such as 15213 + 42); you should not have trouble fitting your answers into the space provided.
Description
int x=1; float *f = (float *)&x; What is the value of *f?
int x=-1; float *f = (float *)&x; What is the value of *f?
Smallest positive integer that cannot be represented as a 32-bit float
Assume we are running code on an IA32 machine, which has a 32-bit word size and uses two’s complement arithmetic for signed integers. Consider the following definition:
int x = foo();
Fill in the empty boxes in the table below. For each of the C expressions in the first column, either:
• State that it is true of all argument values, or • Give an example where it is not true.
True / Counterexample
x<0 ⇒ -x>0
x ˆ ̃x < 0
(x ˆ (x >> 31)) + 1 > 0
(((!!x) << 31) >> 31) & x == x
Page 3 of 10
Problem 3. (10 points):
Consider an 8-bit IEEE floating-point representation with:
• 1 sign bit
• 3 exponent bits (therefore the bias B = 23−1 − 1 = 3)
• 4 mantissa bits
A. Fill in the blanks in the following table. Express numerical values as fractions (e.g., 277/512).
Bit representation
0 010 0101
1 000 1000
0 111 0010
B. Give the bit representation and numerical value of the largest number representable in this format as a denormalized floating-point number.
C. Give the bit representation and numerical value of the largest number representable in this format as a normalized floating-point number.
Page 4 of 10
Problem 4. (9 points):
Consider the following x86-64 assembly code:
# on entry: %rdi = n, %rsi = A 000000000040056e
# Instruction 40059c: 48 40059e: 49 4005a1: ff 4005a3: 39 4005a5: 7c 4005a7: 41 4005aa: 41 4005ad: 7c 4005af: 4c 4005b2: c3
98 cltq 01 c0 add c2 inc fa cmp e8 jl ff c1 inc 39 f9 cmp d0 jl 89 c0 mov
“cltq” is equivalent to
mov $0x0,%r8d
mov $0x0,%r9d
cmp %edi,%r9d
jge 4005af
cmp %edi,%edx
jge 4005a7
mov (%rsi,%rax,8),%rcx movslq %edx,%rax
mov (%rcx,%rax,4),%eax imul %r9d,%eax
imul %edx,%eax
“movslq %eax, %rax”
Fill in BOTH of the blanks below for the corresponding C code.
long bar(int n, ________________ A) { long sum = 0;
40058f
40057f
// Fill in type of A
// Fill in expression
for (i = 0;
i < n; i++) {
0; j < n; j++)
+= _____________________;
return sum;
00 00 00 00
Page 5 of 10
Problem 5. (8 points):
Consider the C code below, where H and J are constants declared with #define. int array1[H][J];
int array2[J][H];
int copy_array(int x, int y) { array2[y][x] = array1[x][y];
return 1; }
Suppose the above C code generates the following x86-64 assembly code:
# On entry: # %edi=x # %esi=y # copy_array:
movslq %edi,%rdi
movslq %esi,%rsi
movq %rdi, %rax
leaq (%rsi,%rsi,8), %rdx salq $5, %rax
subq %rdi, %rax
addq %rdi, %rdx
leaq (%rsi,%rax,2), %rax movl array1(,%rax,4), %eax movl %eax, array2(,%rdx,4) movl $1, %eax
What are the values of H and J? H=
Page 6 of 10
Problem 6. (8 points):
Consider the following data structure declaration:
struct node{
int array[2];
struct node *next;
Below are given four C functions and four x86-64 code blocks.
char *mon(struct node *ptr){ return &ptr->x;
int tue(struct node *ptr){ return ptr->array[ptr->idx];
void wed(struct node *ptr){ ptr->idx = ptr->array[1]; return;
char thu(struct node *ptr){ ptr = ptr->next;
return ptr->x;
In the following table, next to the name of each x86-64 code block, write the name of the C function that it implements.
movl 8(%rdi), %eax movl %eax, 12(%rdi)
movq %rdi, %rax
movq 16(%rdi), %rax movsbl (%rax),%eax
movslq 12(%rdi),%rax movl 4(%rdi,%rax,4),%eax
Code Block
Function Name
Page 7 of 10
Problem 7. (11 points):
The next problem concerns code generated by GCC for a function involving a switch statement. The code uses a jump to index into the jump table:
400518: ff 24 d5 40 06 40 00 jmpq
Using GDB, we extract the 8-entry jump table as:
0x400640: 0x0000000000400527 0x400648: 0x0000000000400525 0x400650: 0x0000000000400531 0x400658: 0x000000000040051f 0x400660: 0x0000000000400525 0x400668: 0x0000000000400525 0x400670: 0x000000000040052a 0x400678: 0x0000000000400531
*0x400640(,%rdx,8)
The following block of disassembled code implements the branches of the switch statement:
# on entry: %rdi = 400510: 31 c0 400512: 48 83 fa 400516: 77 0d 400518: ff 24 d5 40051f: 48 89 f0 400522: 48 29 f8 400525: f3 c3 400527: 48 01 f7 40052a: 48 89 f8 40052d: 48 31 f0 400530: c3 400531: 48 8d 46 400535: c3
a, %rsi = b, %rdx = xor
40 06 40 00 jmpq mov
400525 <_Z4testlll+0x15> *0x400640(,%rdx,8) %rsi,%rax
is a no-op here
2a lea 0x2a(%rsi),%rax retq
repz retq # repz
add %rsi,%rdi
mov %rdi,%rax
xor %rsi,%rax
Page 8 of 10
Fill in the blank portions of C code below to reproduce the function corresponding to this object code. You can assume that the first entry in the jump table is for the case when c equals 0.
long test(long a, long b, long c) {
long answer = _____; switch(c)
answer = _____;
answer = _____;
a = _____;
/* Fall through */ case ___:
answer = _____;
answer = _____;
return answer;
Page 9 of 10
Problem 8. (8 points):
struct BOOKLIST { char a;
double EU;
} booklist;
A. Show how the struct above would appear on a 32 bit Windows machine (primitives of size k are k byte aligned). Label the bytes that belong to the various fields with their names and clearly mark the end of the struct. Use hatch marks to indicate bytes that are allocated in the struct but are not used.
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
B. Rearrange the above fields in booklist to conserve the most space in the memory below. Label the bytes that belong to the various fields with their names and clearly mark the end of the struct. Use hatch marks to indicate bytes that are allocated in the struct but are not used.
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
C. How many bytes of the struct are wasted in part A?
D. How many bytes of the struct are wasted in part B? Page 10 of 10
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com