CPSC 220, Fall 2022
About the Second Test


The second test in CS 220 will be given in class on Wednesday, November 9. Topics include: the memory hierarchy and caching; the design of Larc-in-Logisim and relevant material on logic circuits; the x86-64 architecture; x86-64 assembly language programming; the Linux C calling convention; and basic functions from the Linux standard library. This includes material from labs 7 through 11. For textbook readings, you can consult the weekly entries on the course web page for the sixth through eleventh weeks. A detailed list of topics is given below.

For the memory hierarchy, there will be only general questions; you do not need to understand how caching is implemented. For Larc-in-Logisim, you should be familiar with the overall design, and you should remember enough about logic circuits to do the sorts of things that were used in the implementation. You will not need to memorize the commands for assembling and linking assembly language programs, and you will not need to memorize the details of register use or the Linux C calling convention beyond knowing which registers to use for the first four function arguments; if more information is needed, it will be provided to you. There will be no questions about: debugging or ddd; C programming or pointers in C; specific syscalls; or assembly language instructions that are not listed below.

The format of the test will be as usual. There will be four pages. The types of questions might include: definitions, short-answer and longer essay-type questions, basic coding questions using x86-64 assembly language, reading and explaining assembly language instructions, implementing control structures in assembly language, writing and using functions in assembly langauge, and designing basic circuits similar to ones used in Larc-in-Logisim.


Here are some terms and ideas that you should be familiar with:

Larc-in-Logisim
   how a complicated logic circuit can store and execute computer programs
   the overall structure (like how the register file connects to the ALU)
   the role of the clock
   the role of the PC
   the structure of the register file
   how different sources of input can be selected for the PC and register
   how the opcode is used to control the computation
   how to build a logic circuit to test the opcode

the memory hierarchy
   registers, cache memory, RAM, hard disks and SSDs
   how levels of the memory hierarchy compare in terms of speed, cost, and size
   caches and why they are used

the x86-64 architecture (for integers only)
   16 general purpose registers
   how registers are used for 8-bit, 16-bit, 32-bit, and 64-bit values
   flag register, including the carry flag, C, and other flags
   a memory location holds one byte; an address is 64 bits
   little-endian representation of integers
   
x86-64 assembly language
   assembling an assembly language (.asm) file with yasm to get an object (.o) file
   linking object files with ld to get an executable program
   sections of a program:  .data, .text
   data sizes: byte, word, dword, qword
   declaring initialized variables in the .data section: db, dw, dd, and dq
   declaring strings and arrays in the .data section
   using registers in assembly langauge
   64-bit registers rax, rbx, rcx, rdx, r8 through 15
   32-bit registers eax, epx, ecx, edx, r8d through r15d
   accessing memory, with brackets []
   using a data size in an assembly instruction, such as  inc dword [A]
   labels
   global and extern
   the _start label for marking the entry point of a program
   basic assembly language commands (see list below)
   comparing values and jumping
   the stack and the rsp register; push and pop
   calling and returning from functions
   syscall and why it exists (but nothing about any specific syscall)

the difference between pointers (addresses) and values (in memory)
translating Java-style control structures into assembly language
accessing array elements with notations like [A + r12*8]
writing and using functions in assembly language
how the stack is used for functions

calling convention
the Linux C calling convention
in the C calling convention, arguments are passed in rdi, rsi, rdx, rcx
callee-saved and caller-saved registers in the C calling convention
writing functions that can be called from C
using functions from the C standard library
using printf for output of integers and strings
understanding C function prototypes well enough to call a function

x86-64 assembly instructions that you should know for the test:
   add <dest>, <src>      and <dest>, <src>     jmp <label>
   sub <dest>, <src>      or <dest>, <src>      je <label>
   inc <dest>             not <dest>, <src>     jne <label>
   dec <dest>                                   jg <label>
   imul <dest>, <src>     call <label>          jge <label>
   div <dest>, <src>      ret                   jl <label>
   mov <dest>, <src>      push <src>            jle <label>   
                          pop <dest>            cmp <op1> <op2>


Here are a few sample questions. This is not meant to be a comprehensive survey of all the types of questions or all of the topics that you might see on the test.

1. What memory is allocated by the following .data section in an x86-64 assembly language program?

section .data
   A: dq 100
   B: dd 10, 2, 5, 3
   C: db "fizzbuzz", 0

2. Using the declarations from the .data section in the previous problem, what value is placed into the eax register by the following assembly language instructions? Explain!

mov eax, [B]
imul eax, [B+4]
imul eax, [B+8]
imul eax, [B+12]

3. Suppose that list is defined in a .data section to refer to an array of 64-bit integers. Write assembly instructions to use the standard printf function to output the first three items in the array. Use the following format string:

listfmt: db "The first three items are %ld, %ld, and %ld.", 10, 0

4. What value is placed into the rax register by the following code? Explain!

mov rax, 24
mov r12, 10
mov rdx, 0
div r12
imul rdx, 10
add rax, rdx

5. Assume that X, Y, and Z are defined in a .data section as labels that refer to 64-bit values. Translate the following if statement into x86-64 assembly language instructions:

if ( X > Y ) {
   Z = 1;
}
else if (X == Y) {
   Z = 2;
}
else {
   Z = 3;
}

6. What is accomplished by the following assembly language instructions? What would A and B have to be? (Your answer might include a translation of the assembly code into pseudocode.)

   mov r12, 0
   mov r13, 0
startloop:
   cmp r12, 12
   je done
   add r13, [A + r12*8]
   mov [B + r12*8], r13
   inc r12
   jmp startloop
done:

7. Suppose that when building the Larc computer, there is a wire that you want to be on for opcodes 1001, 1100, and 1011. Draw a logic circuit whose input is the four-bit opcode and whose output is that wire.

8. When the Larc computer is executing a program, the next value of the PC can come from three different sources. What are two of those sources and under what circumstances is each source used for input to the PC?

9. Discuss some of the ways that an assembly language such as x86-64 assembly differs from a high-level language such as Java.

10. Explain how using a memory cache can allow a program to run faster than it would run without the cache.