### C语言代写 | CS 211: Final : 100 points

这个作业是完成一个C语言exam

CS 211: Final : 100 points

Full Name Here:

RUID:

Question Max Points Points

1 20

2 12

3 23

4 22

5 23

6 (Extra Credit) 40

1

Problem 1: C Programming (20 points)

1. (5 points) Complete the following function to multiply two matrices and returns the pointer to the

result matrix. The arguments to the function are pointers to matrix A and matrix B. The number

of rows and columns in matrix A are provided as arguments m1 and m2. The number of rows and

columns in matrix B are provided as arguments n1 and n2. You have to allocate space for the result

matrix. Your code should compile and should not experience segmentation faults.

int** matrix_multiply(int** A, int **B, int m1, int m2, int n1, int n2){

2

2. (5 points) You are implementing a hash table with open chaining where each node is of the following

type.

struct node{

int key;

int value;

struct node * next;

};

Given that the hash table is implemented as an array of pointers to hash table nodes, implement the

following hash search function to search a key in the hash table. If the key is found, the search

function returns the value associated with the key. Otherwise, returns -1. The value MAX ENTRIES

is the number of buckets in the hash table. Your code should carefully handle all corner cases, should

compile, and should not experience segmentation faults on any input. Use the modulo function as the

hash function.

struct node * hash_table[MAX_ENTRIES];

…

int hash_search(int key){

3

3. (10 points) Complete the function traverse below that prints the values at each node of the tree in

breadth-first order. In breadth-first order, all the nodes at height h are printed before the nodes at

height h+1. Nodes at the same height are printed in left-to-right order.

If necessary, you may define additional functions and data structures. The tree passed to traverse

should not be modified.

struct Tree {

int value;

struct Tree *left;

struct Tree *right;

};

void traverse(struct Tree *tree){

4

Problem 2: Data Representation (12 points)

1. (5 points) Write code for a function with the following prototype to perform rotating left shift. Your

function should follow bit-level integer coding rules. It is undefined behavior in C if the shift amount

is greater than or equal to the bitwidth of the data type. Be careful of the case n = 0.

/* Do rotating left shift. Assume 0<= n < w.

Examples when x = 0x12345678 and w =32:

n = 4 -> 0x23456781

n= 20-> 0x67812345

*/

unsigned rotate_left(unsigned x, int n)

5

2. (2 points) Can every 32-bit integer be represented as a 32-bit float? Give reasons.

3. (5 points) You are given a 5-bit floating representation based on IEEE-754 representation with one

sign bit, two exponent bits and two fraction bits. Writing the bit pattern is sufficient.

• What is the smallest positive number in this representation?

• What is the smallest normalized positive value in this representation?

• What is the largest normalized positive value in this representation?

• What is the largest denormal positive value in this representation?

• What is positive infinity in this representation?

6

Problem 3: Assembly (23 points)

1. (7 points) Write C code for the following assembly code.

.globl test

.type test, @function

test:

pushl %ebp

movl %esp, %ebp

movl 8(%ebp), %eax

movl 12(%ebp), %edx

cmpl $-3, %eax

jge .L2

cmpl %edx, %eax

jle .L3

imull %edx, %eax

jmp .L4

.L3:

leal (%edx, %eax), %eax

jmp .L4

.L2:

cmpl $2, %eax

jg .L5

xorl %edx, %eax

jmp .L4

.L5:

subl %edx, %eax

.L4:

popl %ebp

ret

7

2. (8 points) Consider the assembly for a switch statement below.

.globl switcher

.type switcher, @function

switcher:

pushl %ebp

movl %esp, %ebp

movl 8(%ebp), %edx

movl 12(%ebp), %eax

movl 16(%ebp), %ecx

cmpl $7, %edx

ja .L8

jmp *.L7(,%edx,4)

.section .rodata

.align 4

.align 4

.L7:

.long .L3

.long .L8

.long .L4

.long .L8

.long .L5

.long .L6

.long .L8

.long .L4

.text

.L5:

movl $4, %eax

jmp .L8

.L6:

movl %eax, %ecx

xorl $15, %ecx

.L3:

leal 112(%ecx), %eax

jmp .L8

.L4:

leal (%ecx,%eax), %eax

sall $2, %eax

.L8:

popl %ebp

ret

Complete the following C function for the above assembly code.

int switcher(int a, int b, int c ){

int answer;

switch(a){

8

/* Extra page for work */

9

3. (8 points) The following is the binary given for your bomblab assignment. However, we have simplified the binary so that you can solve this assignment without gdb. Your goal is to find all inputs that

defuse the bomb. Each input consists of 3 items: an integer, a character, and a character.

.LC0:

.string “%d %c %c”

.text

.globl phase1

.type phase1, @function

phase1:

pushl %ebp

movl %esp, %ebp

subl $56, %esp

leal -14(%ebp), %eax

movl %eax, 16(%esp)

leal -13(%ebp), %eax

movl %eax, 12(%esp)

leal -12(%ebp), %eax

movl %eax, 8(%esp)

movl $.LC0, 4(%esp)

movl 8(%ebp), %eax

movl %eax, (%esp)

call sscanf

movl -12(%ebp), %edx

leal 3(%edx), %eax

cmpl $9, %eax

je .L9

.L2:

leal 0xf(,%edx,4), %eax

cmpl $23, %eax

je .L9

.L5:

leal -0x2(%eax, %edx, 2), %eax

cmpl $97, %eax

je .L9

.L8:

call explode_bomb

.L9:

leave

ret

• (1 point) How many inputs solve the bomb?

10

• (7 points) List all inputs that solve the bomb. It is only necessary to list inputs that need a distinct

integer input.

11

Problem 4: Caches (22 points)

1. You are given a cache with n sets, associativity of a and a block size of b. Given an unsigned 64-bit

address (addr). Write a C function for the following tasks using bitwise operations. You should not

convert the address to a string. You are allowed to use the log2 function if necessary. The prototype

of the log2 function is given below.

double log2 (double);

/* (4 points) Compute the set index */

unsigned long compute_set_index (unsigned long addr){

}

/* (2 points) Compute the tag bits */

unsigned long compute_tag (unsigned long addr){

}

12

2. Consider a machine with a direct mapped cache that has 8 sets and has a block size of 4 bytes. Memory

addresses are 13 bits and each memory access from a processor requests a byte from the cache. The

contents of the cache are as follows, with all numbers in hexadecimal.

Cache Line

Set Index Tag Valid Byte 0 Byte 1 Byte 2 Byte 3

0 09 1 30 F4 72 AB

1 38 1 78 3F 92 D4

2 6E 0 – – – –

3 06 0 1F DA 40 C5

4 C7 1 – – – –

5 71 1 D3 9A 0B 12

6 91 1 – – – –

7 46 0 5C 80 B3 59

(a) (1 point) Calculate the size of the cache in bytes.

(b) (1 point) Indicate the number of bits used to determine

• the block offset:

• set index:

• tag:

(c) (4 points) A program running on this machine makes memory references at the addresses specified in the first column of the following table. For each memory reference indicate the block

offset, set index and tag. Furthermore, indicate whether a cache hit occurs and the byte returned.

The byte returned is – for a miss.

Address Set index Block offset Tag Cache hit? (Y/N) Byte returned

0x0E35

0x0DD5

0x1FE4

0x0705

13

(d) (3 points) If we redesign the cache by increasing the associativity to 4 while keeping the total

cache size exactly the same as above, how many bits will you use for the following:

• Tag:

• Set index:

• Block offset:

(e) (2 points) What is spatial locality and temporal locality?

3. You are given a system where accessing memory takes 500 cycles per memory access. A hit in the

cache takes 10 cycles and the latency of a cache miss (including the time to search in the cache and

getting the data from memory) is 500 cycles.

• (2 points) You run the program by completely removing the caches. How many cycles does the

program take?

• (2 points) You run the program with caches and 90% of the accesses are hits in the cache and

the rest are misses. How many cycles will the program take with caches?

• (2 points) Assume that your program takes 10 hours to run on a machine without caches. How

long would it take on a machine with caches?

14

Problem 5: Logic Design (23 points)

1. (8 points) You are supposed to design a circuit which takes four bits as input (ABCD) and the bits are

interpreted as an unsigned integer. Here, A is the most significant bit and D is the least significant

bit. Design a combinational circuit that outputs a 1 if the number is divisible by 3. Clearly show truth

table. Simplification using K-maps.

15

2. (2 points) Implement the function F = A¯.B + A.B¯ using a 2:1 multiplexer.

3. (1 point) Implement the function F = A¯.B + A.B¯ using a 2:4 decoder.

16

4. (12 points) Design a Moore finite state machine that detects 1 0 1 in consecutive digits in the input

stream of 0’s and 1’s received every clock cycle. The circuit should output a 1 when it detects 1 0 1 as

consecutive digits. Implement the FSM using a combination of sequential and combinational logic.

Clearly show your work. Draw the truth table for inputs, outputs and your states. Draw the K-map for

everything. Clearly indicate how many flip flops you are going to use. Draw the final circuit with the

flip flops.

INPUT : 0 1 0 1 0 1 1 0 1 0 0….

OUTPUT: 0 0 0 1 0 1 0 0 1 0 0….

17

/* Extra page for work */

18

Extra Credit Problems (40 points)

1. (15 points) Identify the inputs that defuse the following bomb. There are 3 different inputs that solve

this bomb. Your goal is to identify the each of the inputs to solve the bomb.

.LC0:

.string “%d %c %c”

.text

.globl phase1

.type phase1, @function

phase1:

pushl %ebp

movl %esp, %ebp

subl $56, %esp

leal -14(%ebp), %eax

movl %eax, 16(%esp)

leal -13(%ebp), %eax

movl %eax, 12(%esp)

leal -12(%ebp), %eax

movl %eax, 8(%esp)

movl $.LC0, 4(%esp)

movl 8(%ebp), %eax

movl %eax, (%esp)

call sscanf

movl -12(%ebp), %eax

cmpl $7, %eax

je .L6

cmpl $9, %eax

jne .L3

movl string, %eax

movzbl 10(%eax), %eax

cmpb -13(%ebp), %al

je .L6

call explode_bomb

.L3:

cmpl $41, -12(%ebp)

jne .L4

movl string, %eax

movzbl 9(%eax), %edx

cmpb -13(%ebp), %dl

jne .L5

movzbl 13(%eax), %eax

cmpb -14(%ebp), %al

je .L6

.L5:

call explode_bomb

.L4:

call explode_bomb

.L6:

leave

ret

19

.globl string

.section .rodata.str1.1

.LC1:

.string “CS 211 students are awesome!”

.data

.align 4

.type string, @object

.size string, 4

string:

.long .LC1

.ident “GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)”

.section .note.GNU-stack,””,@progbits

2. (7 points) You are asked to create a three dimensional matrix with each dimension having 10, 20, and

30 elements respectively. When given this questions, student P comes with the following solution

/* student P’s solution */

int ***A;

void init (){

int j, k;

A = (int ***)malloc(10* sizeof(int**));

for(j = 0; j< 20; j++){

int** temp = (int**) malloc(20 * sizeof(int*));

A[j] = temp;

for(k = 0; k < 30; k++){

int * temp2 = (int*) malloc(30 * sizeof(int));

A[j][k] = temp2;

}

}

}

Student Q comes up with the following solution:

int *A;

void init(){

A = (int*) malloc(10* 20*30 * sizeof(int));

}

• (2 points) Which solution has the best possible performance and why?

20

• (2 points) Let’s say you want to logically access the matrix element A[2][3][4]. How do you do

it in Student P’s solution?

• (3 points) How do you access the matrix element A[2][3][4] in Student Q’s solution?

3. (18 points) Consider the following example, where P, Q, R are constants declared with #define:

int A[P][Q][R];

int test_element(int i, int j, int k, int *dest){

*dest = A[i][j][k];

return sizeof(A);

}

GCC generates the following assembly code:

.globl test_element

.type test_element, @function

test_element:

pushl %ebp

movl %esp, %ebp

movl 12(%ebp), %eax

leal (%eax,%eax,4), %edx

leal (%eax,%edx,2), %edx

21

imull $88, 8(%ebp), %eax

leal (%edx,%eax), %eax

addl 16(%ebp), %eax

movl A(,%eax,4), %edx

movl 20(%ebp), %eax

movl %edx, (%eax)

movl $2464, %eax

popl %ebp

ret

Use your reverse engineering skills to determine the values of P, Q, and R based on the assembly code.

22

## 发表评论