CS61C F20 Final
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS61C F20 Final
Section 1: Quest Clobber
1: Quest Clobber (10 pts)
Part A — 2 pts Recall that an 8-bit bias-encoded number normally has a bias of -127 so that roughly half the numbers are negative and half are positive, but there’s one more positive than negative number. Using an equivalent scheme for choosing
the bias, what base 14 number XXXXXX represents 0? (That is, your answer needs to have 6 base-14 characters.) Variants: Different bases (all even, so the above process works), and different number of digits.
Part B — 8 pts We want to write a helper function to return a memory address aligned to 220-byte boundaries. We also need to “return” the original malloced amount so we can free it later. We want to malloc the fewest extra bytes possible, and then do something to the pointer to align it. Fill in the code to complete it; don’t worry about typecast warnings/errors (we removed casting for simplicity).
void *malloc_2totheN_aligned(size_t size, void /* CODE INPUT 1 */) {
size_t offset = /* CODE INPUT 2 */;
/* CODE INPUT 3 */ = malloc(size + offset); //smallest possible
return ((/* CODE INPUT 4 */ + offset) /* CODE INPUT 5 */ /* CODE INPUT 6 */); //align
}
int main(int argc, char *argv[]) {
void *head, *aligned;
aligned = malloc_2totheN_aligned(59, /* CODE INPUT 7 */
printf("head = 0x%p\n",head); // %p is what we use to print out a pointer
printf("aligned = 0x%p\n",aligned);
free(head);
}
unix% a.out
head = 0x12345678
aligned = 0x[HEX INPUT HERE]
Variants: Different alignment requirement. This changed the exponent used, and changed how many bits turn into zeros in the hex input.
Section 2: Midterm Clobber (30 pts)
1: CALL (2 pts)
Variants: Students were given a random set of eight of the following parts, and were asked to determine which part of CALL bests matches the statements.
Choose which of Compiler, Assembler, Linker, Loader best matches each statement.
• Its input may contain pseudoinstructions.
• It copies instructions into its address space . text and data segments .
• Its job is to read the relocation table .
• Its input is executable code .
• One of its jobs is to take the text segments from .o files and concatenate them together .
• Its output is true assembly only.
• It reads directives .
• Output file suffix is .o.
• Its input is object code files (among other things) .
• It sets the PC .
• This job is typically part of the operating system .
• One of its jobs is to take the code segments from .o files and concatenate them together .
• It creates a new address space for the program large enough to hold - Input file suffix is .s.
• It deals with the syntax of C .
• Its output is an object file .
• Its output is machine language .
• Input file suffix is .c.
• This stage makes two passes over its input .
• Input file suffix is .o.
• Typical input file is a .out .
• Its output may contain pseudoinstructions .
• Its input is information tables (among other things) .
• It is often called the ‘bottleneck’ of the development process .
• Its output is a fully running program .
• Typical output file is a .out.
• It deals with the semantics (i .e . meaning) of C .
• Its job is to resolve references and fill in the absolute addresses .
• It replaces pseudoinstructions .
• Output file suffix is .s.
• Its output is two information tables .
• People sometimes do this stage by hand for optimization .
• Its output is an executable .
• It initializes machine registers.
2: Floating Point (3 pts)
Consider a NON-WORD-LENGTH-bit floating point number with the following components: 1 sign bit, 13 exponent bits, and 19 mantissa/significand bits structured otherwise in IEEE754 Floating Point standard format.
sEEEEEEEEEEEEEMMMMMMMMMMMMMMMMMMM
Recall the median of a set of numbers is the “middle number”, if you sorted them.
E.g., the median of {1, 2, 5, 100, 1000} is 5.
Part A — 3 pts What is the median of the positive non-NaN floats? (including +0, denorms, and ∞ , which is an odd number of numbers) Write your answer as a decimal number, like 7.65; something a first grader could understand.
Part B — 2 pts Of all the numbers you can represent with this floating-point format, what is the largest odd number?
Different versions had different numbers of exponent and mantissa bits.
3: SDS (6 pts)
Part A Circuit to Expression — 3 pts
Please choose the correct boolean expression for the circuit given. NOTE: see all versioned diagrams in the Appendix.
Part B FSM Blinding Lights — 3 pts You fall in love with a new pop hit, Blinding Lights. To make your own blinking lights, come up with a finite state machine that turns static input into “blinking” outputs. Based on two examples of input and output boolean sequences, fill in the state transition table for the finite state machine below.
Version 1
Input 1: 111111111111111
Output 1: 001001001001001
Input 2: 001011011101111
Output 2: 000000000100010
current state input next state output
00 |
0 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
00 |
1 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
01 |
0 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
01 |
1 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
10 |
0 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
10 |
1 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
Version 2
Input 1: 111111111111111
Output 1: 010010010010010
Input 2: 001011011101111
Output 2: 000001001000100
current state input next state output
00 |
0 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
00 |
1 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
01 |
0 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
01 |
1 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
10 |
0 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
10 |
1 |
YOUR |
ANS |
HERE |
YOUR |
ANS |
HERE |
Version 3
Input 1: 111111111111111
Output 1: 011011011011011
Input 2: 001011011101111
Output 2: 000001001100110
current state |
input |
next state |
output |
00 |
0 |
YOUR ANS HERE |
YOUR ANS HERE |
00 |
1 |
YOUR ANS HERE |
YOUR ANS HERE |
01 |
0 |
YOUR ANS HERE |
YOUR ANS HERE |
01 |
1 |
YOUR ANS HERE |
YOUR ANS HERE |
10 |
0 |
YOUR ANS HERE |
YOUR ANS HERE |
10 |
1 |
YOUR ANS HERE |
YOUR ANS HERE |
2022-07-29