Time limit: 80 minutes
## Problems
### Q1
Suppose that we represent real numbers with the following fixed-point format:
– Sign: 1 bit.
– Integer component: 3 bits.
– Fractional component: 1 bit.
Which of the following values ***can*** be represented by the above format? For each value that can be, give the representation in the below text box, using the above format.
[ ] $$8$$
[ ] $$9.25$$
[ ] $$-6.5$$
[ ] $$3$$
[ ] $$-8.4$$
[ ] None of the above.
|____|
### Q2
Suppose that the designers of the C programming language introduced an unsigned integer type called `kaloti` that supported values in the range $$0_{10}$$ to $$500_{10}$$. What would be the *minimum* number of bits that this type needs in order to support its range of values? (Assume that the number of bits need not be a multiple of 8.) Justify your answer.
|____|
### Q3
Suppose that we have a statically allocated two-dimensional array of integers that happens to be stored in exactly the same way regardless of whether row-major ordering or column-major ordering is used. Which of the below *could* be the dimensions of the two-dimensional array? Select all that apply.
[ ] 2 rows, 3 columns.
[ ] 5 rows, 2 columns.
[ ] 1 row, 8 columns.
[ ] 2 rows, 1 column.
[ ] None of the above.
### Q4
During lecture, we established that when cleaning up the stack after a function, it is better to use one `add` instruction instead of multiple `pop` instructions. As an example, consider the below code that calls a function named `foo`.
“` gas
push $37
push $82
push $59
call foo
pop %rbx
pop %rbx
pop %rbx
“`
We know that replacing the three `pop %rbx` instructions with a single instruction `add $24, %rsp` would speed up the program. What if we instead replace the three `pop` instructions with three `add` instructions? See below.
“` gas
push $37
push $82
push $59
call foo
add $8, %rsp
add $8, %rsp
add $8, %rsp
“`
Would this version (that uses three `add` instructions) still be faster than the version that uses three `pop` instructions? Justify your answer.
|____|
### Q5
Suppose that we have the following values in memory (don’t worry about sizes of things):
– Address 5: 32.
– Address 10: 6.
– Address 15: 1000.
– Address 100: 5.
– Address 200: 10.
– Address 300: 68.
Suppose that we run the below snippet of assembly code.
“` gas
movl $100, %eax
movl $200, %ebx
lea (%rax, %rbx), %rcx
“`
What value will be placed in the RCX register? Give the value in base 10. Do not justify your answer. Do not put a leading dollar sign.
[____]()
### Q6
For this problem, you will write an x86-64 assembly language program using AT&T syntax that has the five variables $$a$$, $$b$$, $$c$$, $$x$$, and `result`. It is assumed that $$a < b < c$$. (Whenever I refer to a variable like $$a$$, I'm talking about the value in the variable, ***not*** its address.) Your program must set `result` according to the following rules: - Set `result` to 1 if $$x < a$$. - Set `result` to 2 if $$a \le x < b$$. - Set `result` to 3 if $$b \le x \le c$$. (*Note that it's $$x \le c$$ instead of $$x < c$$.*) - Set `result` to 4 otherwise. Below is a skeleton version to help get you started. In the below example, `result` would be set to $$3$$. You may not assume that `result` is always initialized to -1. The program should end at the `nop` instruction at the end. *Hint*: If you place a value (e.g. 3) directly in a variable, you will have to use an instruction suffix. For example, `mov $1, result` does not work, but `movl $1, result` does. ``` gas .data a: .long 18 b: .long 37 c: .long 50 x: .long 43 result: .long -1 .text .globl _start _start: # TODO: Implement. done: nop ``` If you use the text box, note that pressing Tab will not create spaces, unfortunately. Please do not submit to both the text box and the file upload; pick one or the other. If you end up submitting a file multiple times, make it clear with a comment at the top of the file which one is the most recent submission, because it isn't clear on our end. |____| |files| ### Q7 In the below C code, the function `bar()` expects a multidimensional array in the form of a pointer array (like in the lower half of slide \#29 of slide deck \#1). **Explain how the function could be rewritten in order to take better advantage of spatial locality** of references to data, i.e. variables. (Don't worry about the interaction between spatial locality and instructions.) **Explain *why* your suggestions would improve how the code takes advantage of spatial locality.** ``` C int bar(int** arr, int numRows, int numCols) { if (numCols <= 2) return 0; int x = 0; for (int i = 0; i < numRows; ++i) x += arr[i][0]; for (int i = 0; i < numRows; ++i) x += arr[i][1]; return x; } ``` |____| ### Q8 The x86-64 AT&T syntax assembly code function `blah()` takes the below three arguments and expects them to be pushed onto the stack in order. 1. The starting address of a (one-dimensional) array of integers, each 32 bits. Note that the address needs 64 bits. 2. The length of this array, a 32 bit quantity. 3. A 32 bit integer. Note that each of the above arguments will take up 64 bits on the stack. Below is a *correct* example of how `blah()` is called. ``` gas .data vals: .long 37 .long 55 .long 29 .long 43 .long 18 .text .globl _start _start: push $vals push $5 push $83 call blah done: nop # end of program ``` Below is a *not fully correct* implementation of `blah()`. This function is supposed to replace all integers in the input array (whose starting address is given as the first argument) with the target value (the third argument). Using the values in the above snippet, that would mean that `blah()` would replace all five of the array's values with the value 83. ``` gas blah: mov $1, %ecx mov 8(%rsp), %edx mov 24(%rsp), %r8 abcde: cmp 16(%rsp), %ecx jle ghijk mov (%edx), (%r8, %rcx, 3) inc %ecx jmp abcde ghijk: pop %rbp ret ``` There are some issues with the above implementation that cause it to not work correctly. **Describe all ways in which the function must be changed in order to behave correctly.** We are only concerned with correctness here, not efficiency or good form. Do not worry about register neutrality, i.e. do not worry about the fact that the old values of RCX, RDX, and R8 are not preserved. You may be penalized for stating unnecessary changes. |____| ### Q9 Consider the below assembly program. ``` gas .data x: .quad 20 # .quad is 64 bits (in contrast to .long, which is 32 bits) y: .quad 15 z: .quad 95 .text .globl _start _start: mov x, %rax # RAX = 20 mov $y, %rbx # RBX = address of the y variable mov (%rbx), %r8 push %rcx pop %rdx push z done: nop ``` Assuming the below program magically stops immediately after executing the `nop` instruction, **how many memory accesses (reads/writes) are done while this program is being run? Justify your answer, i.e. state specifically what causes each memory access.** Assume that the computer has no cache. Ignore memory accesses that have nothing to do with the execution of this program, e.g. don't worry about background programs or other programs that may be running while the above program is being run. |____| ### Q10 *This question has been removed.* ### Q11 Suppose that we are converting a C function to assembly code. The C function has a local array created in the following way: ``` C short arr[5]; ``` As a reminder, `short` takes up 16 bits (in contrast to `int`, which takes up 32 bits). Which of the following `enter` commands will create enough space for the above array? We do not want to use more space than is necessary for the local array. ( ) `enter $10, $0` ( ) `enter $20, $0` ( ) `enter $40, $0` ( ) `enter $80, $0` ( ) `enter $120, $0` ( ) `enter $160, $0` Justify your answer. |____| ### Q12 Is the following statement true or false? *Statement*: Assuming that no overflow occurs, left shifting an unsigned integer three times is the same as multiplying the integer by 6. ( ) True. ( ) False. If you picked False, provide a counterexample below and explain why it is a counterexample. (If you picked True, then leave the box blank.) |____| ## Copyright Statement This content is protected and may not be shared, uploaded, or distributed.