Back to Notes

CS 61C Midterm Review

Logistics

Scope

Topical Review with Questions

Number Representation

Example

Quick Tricks

Two’s Complement: Negative Nums

Screen Shot 2021-10-17 at 2.31.47 PM

Converting Binary to Hex

0b10100

Bias Notation

Fall 2019 Q1

Screen Shot 2021-10-17 at 2.37.53 PM

==CHEAT SHEET STUFF==

Screen Shot 2021-10-17 at 2.39.54 PM

Bitwise Operations

C Types

Types

False Values

Pointer Arithmetic

Screen Shot 2021-10-17 at 2.43.20 PM

Bit Manipulation

Example (Fa19 Q3)

void ConvertTo2sArray(int32_t *A) {
	while (*A) {						// checks if A != 0x00000000 (terminator)
		if (*A < 0) {					// checks if value in A is negative
			ConvertTo2s(A);			// calls other function on address
		}
		A = A + 1;						// increments A's address by 1
}
}

void ConvertTo2s(int32_t *B) {
	*B = (*B & 0x7FFF_FFFF) + 1;		// converts to 2s complement
}

Structs

sizeof

Memory

Endianness

Types

Example

int a = 5;
int main(){
	int b = 0;
	char* s1 = “cs61c”;	
	char s2[] = “cs61c”;
	char *c = malloc(sizeof(char) * 100);
	return 0;
}

Practice

Screen Shot 2021-10-18 at 6.07.59 PM

Floating Point

==Practice Problems==

Conversion

Sign Exponent Mantissa/Significand/Fraction
1 8 23
Exponent Significand Meaning
0 0 0
0 any denorm
255 0 + or – \(\infin\)
255 nonzero NaN
1-254 any norm

Example Fa18 Q1

// NOTE: always round down to 0
minifloat should_be_a_billion() {
	minifloat sum = 0.0;
	for (unsigned int i = 0; i < 1000000000; i++) {
		sum = sum + 1.0;
	}
	return sum;
}

RISC-V

C to RISC-V

Screen Shot 2021-10-17 at 3.42.38 PM

Jumping

  labels registers
no linking j jr
linking jal jar

Calling Convention

Example Su19 Q5

# iterative python-ish pseudocode:
i = 0
while (i != n):
	copy_one_char_from_source_to_dest
	if source_is_null_terminator:
		return dest
	increment source pointer
return dest

# iterative RISC-V solution
# a0 = dest, a1 = source, a2 = n
strncpy:
	li t0, 0		# initialize counter
	mv t2, a0		# store a0 in t2 as a temp
loop:
	beq t0, a2, end	# check end of while loop
	lb t1, 0(a1)	# read char from source
	sb t1, 0(a0)	# copy char to dest
	beq t1, x0, end	# check null terminator
	addi t0, t0, 1	# increment counter
	addi a1, a1, 1	# increment source
	addi a0, a0, 1	# increment dest
	j loop		# go back to top of loop
end:
	mv a0, t2		# t2 contains the original dest
	ret

# recursive solution
# a0 = dest, a1 = source, a2 = n
strncpy:
  # missing! we need to save the return address and s0
  addi sp sp -8
  sw ra 0(sp)
  sw s0 4(sp)
  
	beq a2, x0, end	# n == 0
	lb s0, 0(a1)	# read *source
	sb s0, 0(a0)	# copy to *destination
	beq s0, x0, end	# check if *source == 0
	# set up recursive call
	addi a0, a0, 1
	addi a1, a1, 1
	addi a2, a2, -1
	jal strncpy
	addi a0, a0, -1			# decrements the address back to the destination
end:
  # missing!
  lw ra 0(sp)					# restores ra and s0
  lw s0 4(sp)
  addi sp sp 8
  
	ret			# return (a0 is already dest)
# Q: What’s missing?
# A: Calling convention (need to save s0 and ra)!

Instruction Formats

Screen Shot 2021-10-17 at 4.13.24 PM

Practice Problem

lw t5, 17(t6)

CALL

C = Compile

A = Assemble

L = Link

L = Load

Summary of CALL

Screen Shot 2021-10-18 at 12.13.10 AM

Lecture 13: CALL Notes

Interpretation vs Translation

Full Picture

Screen Shot 2021-10-17 at 4.30.44 PM

Compiler

Assembler

Assember Directives

gives directions to assembler, but doesn’t produce machine instructions

Pseudo-instruction Replacement

Producing Machine Code

Tables

Object File Format

Linker

General Info

Screen Shot 2021-10-17 at 11.40.50 PM

Steps

  1. take text segment from each .o file and put them together
  2. take data segment from each .o file, put them together, and concatenate onto the end of text segments
  3. resolve references (i.e., handle each entry from reloc table, fill in all absolute addresses)

4 Types of Addresses

Relocation Editing

Resolving References

Static vs Dynamically Linked Libraries

Loader

General

How it works

Screen Shot 2021-10-18 at 12.07.53 AM

SDS/Boolean Algebra/FSM

Hold Time

Screen Shot 2021-12-08 at 11.16.40 PM