CS计算机代考程序代写 compiler assembly CPSC 213, Winter 2019, Term 2 ¡ª Midterm Exam Solution Date: February 27, 2020; Instructors: Mike Feeley, Robert Xiao
CPSC 213, Winter 2019, Term 2 ¡ª Midterm Exam Solution Date: February 27, 2020; Instructors: Mike Feeley, Robert Xiao
Unless otherwise specified, comments are not mandatory, but showing your work is always encouraged.
1 (8 marks) Memory and Numbers. Consider the execution of the following code. Assume that the compiler has statically allocated p to start at address 0x2020, and consecutively allocates the subsequent variables, inserting padding (wasting memory) only where needed to ensure that each variable is aligned.
Assume too that char¡¯s are signed, and int¡¯s and pointers are 4 bytes long. Prior to the execution of foo(), assume that the memory contents are indeterminate (i.e. anything could hold any value).
int *p;
int i;
char c;
short s;
void foo() {
p = &i;
Assuming that the code above executes on a little-endian machine, give the value in hex stored at each memory address below, or write UNKNOWN if the value cannot be determined completely.
0x2020: 0x24 ____________
0x2021: 0x20 ____________
0x2022: 0x00 ____________
0x2023: 0x00 ____________
0x2024: 0xfe ____________
0x2025: 0xca ____________
0x2026: 0xff ____________
0x2027: 0xff ____________
0x2028: 0x24 ____________
0x2029: UNKNOWN ____________
0x202a: 0xfe ____________
0x202b: 0xca ____________
2 (8 marks) Global Variables and Arrays. Answer the following questions about these global variables. Assume that int¡¯s and pointers are 4 bytes long. Treat each subquestion separately: do not use values computed in other subquestions. No comments needed.
int i;
int a[4];
int *b;
2a TranslatethisCstatementintoassembly:i = a[0] + a[3].
i = 0x0badcafe;
c = (char)p;
s = (short)i;
*p = *p | s;
}
Do not share
ld $a, r0
ld (r0), r1
ld $3, r2
ld (r0, r2, 4), r2
add r2, r1
ld $i, r0
st r1, (r0)
# r0 = &a
# r1 = a[0]
# r2 = 3
# r2 = a[3] (can also do ld 12(r0), r2)
# r1 = a[0] + a[3]
# r0 = &i
# i = a[0] + a[3]
2b TranslatethisCstatementintoassembly:b[a[i]] = a[i-1].
ld $i, r0
ld (r0), r0
ld $a, r1
ld (r1, r0, 4), r2
dec r0
ld (r1, r0, 4), r1
ld $b, r0
ld (r0), r0
st r1, (r0, r2, 4)
# r0 = &i
# r0 = i
# r1 = &a
# r2 = a[i]
# r0 = i – 1
# r1 = a[i-1]
# r2 = &b
# r2 = b
# b[a[i]] = a[i-1]
2c Whatistheminimumnumberofmemoryreadsrequiredtoexecutethisstatement?Assumeyouhaveenough registers so that no value needs to be read twice. Fill in a single multiple choice option below.
a[b[i]+1] = a[b[i]] + a[b[i]-1];
5: b, i, b[i], a[b[i]], a[b[i]-1]
012345678
3 (8 marks) Structs and Instance Variables. Answer the following questions about these structures and variables.
struct A {
int c[2];
char d[2];
};
3a Assuming that pointers are 4 bytes in size, give the values of the following expressions under the ¡°32-bit¡± column. Repeat for 8-byte pointers under the ¡°64-bit¡± column. Recall that sizeof obtains the size (in bytes) of the given structure, and offsetof obtains the offset (in bytes) of the given field from the start of the structure.
sizeof(struct A)
sizeof(struct B)
offsetof(struct A, d[1])
offsetof(struct B, f)
12 12 32-bit ____________
24 32 32-bit ____________
9 9 32-bit ____________
4 8 32-bit ____________
64-bit ____________
64-bit ____________
64-bit ____________
64-bit ____________
64-bit ____________
offsetof(struct B, g.c[1]) 12 20 32-bit ____________
struct B {
int e;
struct B *f;
struct A g;
char h[2];
};
struct A *a;
struct B b;
3b ConvertthefollowingCstatementtoSM213assembly:b.f->e = a[2].c[1] + 4;.NotethatSM213 pointers are 4 bytes in size.
2
Do not share
ld $a, r0
ld (r0), r0
ld 28(r0), r0
inca r0
ld $b, r1
ld 4(r1), r1
st r0, 0(r1)
# r0 = &a
# r0 = a
# r0 = a[2].c[1]
# r0 = a[2].c[1] + 4
# r1 = &b
# r1 = b.f
# b.f->e = a[2].c[1] + 4
4 (8 marks) Static Control Flow. Answer the following question on static control flow. Assume the following global declarations:
int x, y, a[4];
void foo();
Give assembly code for the following. Assume that the function foo does not modify any registers. Insert a halt at the end of your program.
for(x = 0; x < y; x += 2) {
if(a[x] > 0)
foo();
/* halt */
}
ld $0, r0
ld $y, r1
ld (r1), r1
ld $a, r3
mov r1, r2
not r2
inc r2
add r0, r2
bgt r2, done
beq r2, done
ld(r3,r0,4),r2 bgt r2, callfoo
j next
callfoo:
j foo
# x = 0
# set r1 = &y
# set r1 = y
# r2 = y # r2 = -y
# r2 = x – y
# if x – y >= 0, done.
#r2=a[x]
# if r2 > 0, call foo
# otherwise, go to next
# call foo (+6 for size of j instruction)
# x += 2
# next loop
# store x¡¯ back to x
# all done
loop:
next: done:
inc r0
inc r0
br loop
ld $x, r1
st r0, (r1)
halt
gpc $6, r6
5 (8 marks) C Pointers. Consider the following global variable declarations.
int a[5] = {3, 1, 4, 1, 5};
int *b[3] = {&a[0], &a[2], &a[4]};
int **c = &b[1];
int d = 0;
Assume that the address of a is 0x1000, the address of b is 0x2000, the address of c is 0x3000 and the address of d is 0x4000. Assume that pointers are 4 bytes in size.
For each of the following questions, execute the snippet starting from the declarations above – that is, each question is independent and not cumulative. Report all changed values in memory (in either decimal or hex), along with their addresses (in hex); for example, if d changes to 12345, you would write 0x4000, 12345. You do not have to use all lines.
3
Do not share
5a
5b
5c
5d
**c=3;
d = c – b; a[d]++;
0x1008 3 address ____________
0x4000 1 address ____________
0x1004 2 address ____________
*b = c[0];
*(&a[2]) = b[0][2];
0x2000 0x1008 address ____________
0x1008 5 address ____________
address ____________
c=(b+3); c[-2][0] = 6;
0x3000 0x200c address ____________
0x1008 6 address ____________
address ____________
d=(c+a[3]-&b[0]); **(b + 1) = d;
0x4000 2 address ____________
0x1008 2 address ____________
address ____________
value ____________
value ____________
value ____________
value ____________
value ____________
value ____________
value ____________
value ____________
value ____________
value ____________
value ____________
value ____________
6 (8 marks)
Dynamic Allocation. Consider each of the following pieces of C code. Identify which memory-related error(s) the snippet might exhibit when receive is called. If there cannot be any errors, select no error. Assume that array indices are always within bounds, and that any function called magic is defined elsewhere and has unknown behaviour.
For each identified error, explain how the error might occur in a single sentence. If an error might only occur under certain conditions (e.g. certain behaviour of external functions), briefly describe such a condition. Don¡¯t fix any bugs.
6a int receive(int *m, int c) { int *r = malloc(sizeof(int)); *r = 0;
for(int i=0; i
r = transform(m[i], r);
int s = *r;
free(r);
return s;
}
int y = magic(x, r);
*r = y;
return r;
no error
}
memory leak
Cause of possible error(s):
dangling pointer
dangling pointer: magic might make a copy of the pointer which would become dangling after the free in transform.
6d int receive(int *m, int c) { int *r = malloc(sizeof(int)); *r = 0;
for(int i=0; i
6
Do not share
/* Set structure. Don¡¯t modify. */
struct set {
int **data; // all elements in the set
int capacity; // maximum number of elements
int size; // current number of elements
};
/* Create a new reference-counted element (an integer). Don¡¯t modify. */
int *element_new(int value) {
int *e = rc_malloc(sizeof(int));
*e = value;
return e;
}
/* Create a set capable of holding a fixed number of distinct items.
Don¡¯t modify. */
struct set *set_new(int capacity) {
struct set *s = malloc(sizeof(struct set));
s->data = malloc(sizeof(int *) * capacity);
s->capacity = capacity;
s->size = 0;
return s;
}
/* Find an element in the set. The set keeps its reference. */
int *set_lookup(struct set *s, int v) {
for(int i=0; i
if(*(s->data[i]) == v) {
rc_keep_ref(s->data[i]);
return s->data[i];
}
}
return NULL;
}
/* Add an element to the set. The set adds a reference if it is new. */
void set_add(struct set *s, int *v) {
if(s->size == s->capacity) return;
int *x = set_lookup(s, *v);
if(x != NULL) {
rc_free_ref(x);
return;
}
rc_keep_ref(v);
s->data[s->size] = v;
s->size++; }
7
Do not share
/* Print the set and delete it */
void set_print_delete(struct set *s) {
for(int i=0; i
printf(“%d “, *(s->data[i]));
rc_free_ref(s->data[i]);
}
free(s->data);
free(s);
printf(“
”);
}
int main() {
struct set *s1 = set_new(3);
struct set *s2 = set_new(3);
int *e1 = element_new(16);
int *e2 = element_new(23);
int *e3 = element_new(23);
set_add(s1, e1);
set_add(s2, e2);
set_add(s2, e3);
int *e4 = set_lookup(s1, 16);
int *e5 = set_lookup(s2, 23);
set_add(s2, e4);
rc_free_ref(e1); rc_free_ref(e2); rc_free_ref(e3); rc_free_ref(e4); rc_free_ref(e5);
set_print_delete(s1);
set_print_delete(s2);
}
8 (10 marks) (+2 bonus) Reverse-Engineering Assembly. Comment the following assembly code and then reverse- engineer it into C. Use the back of the preceding page for extra space if you need it.
8
Do not share
ld $0, r0
ld $0, r1
ld $s, r2
ld $t, r3
ld (r3), r3
L0: ld (r2), r4
not r4
inc r4
add r1, r4
beq r4, L3 ld(r3,r1,4),r4
L1: beq r4, L2
ld $1, r7
and r4, r7
add r7, r0
shr $1, r4
br L1
L2: inc r1
br L0
L3: ld $r,
st r0, (r1)
halt
# r¡¯=0 # i=0
# r2=&s # r3=&t # r3=t # r4=s # r4=-s #
# r4=i-s
# ifi==s,gotoL3 #r4=j=t[i] #ifj==0,gotoL2 #r7=1 #r7=j&1 #r¡¯+=j&1 #j=j>>1
# goto L1
# i++
# goto L0
#r1=&r
# r = r¡¯
r1
8a TranslateintoC.Includedefinitionsofallglobalvariables.
int r, s;
int *t;
r = 0;
for(int i = 0; i != s; i++) {
int j = t[i];
while(j) {
r += j & 1;
j >>= 1; }
}
8b BONUS(+2):Explaininonesentencewhatthecodecomputesintotheglobalvariabler. r counts the number of ¡°1¡± bits in the first s integers in the array t.
9
Do not share
