Midterm I: Required Topics

Binary Systems for Integer Numbers

Typical tasks:

Examples:

Convert $(12.50)_{10}$ to binary (answer: 1100.1)
Convert $-65$ to signed 8-bit (answer: 10111111)
Convert 11011010 to hex (answer: 0xDA)
Convert the signed char 11011010 to decimal (answer: $-38$)
Convert the unsigned char 11011010 to decimal (answer: $218$)
What is the range of signed/unsigned integers with $n$ bits?
What is the hex encoding of MAX_INT, MIN_INT, 1, 0, -1, MAX_UINT, MIN_UINT?
What is the size and range of the C types char, short, int, long?
What are the conditions to detect signed overflow?
What are the conditions to detect unsigned overflow?

Typical tasks:

Explaining the use and size of fields in the IEEE 754 encoding (32 bits, 64 bits, or “classroom 12-bit”)
Convert a number encoded as IEEE 754 to decimal
Convert a decimal number to IEEE 754

Examples:

Assuming a 12-bit floating-point representation (1 sign bit, 5 exponent bits using excess-15, and 6 fraction bits), convert 1 01111 100000 to decimal.
- 1 ⟹ the sign is -
- 01111 ⟹ the exponent after conversion from excess-15 is $(15 - 15) = 0$
- 100000 ⟹ the fraction (without 1.) is .100000
- So, the number is $-(1.100000)_2 \times 2^{0} = (-1.1)_2$
- Base 10, the number is $-1.5$
Using the same 12-bit representation, encode $-20.5$ (use “round to nearest, half to even” to round the fraction).
- - ⟹ the sign bit is 1
- $(20.5)_{10}$ is 10100.1 in binary
- 10100.1 is $1.01001 \times 2^4$ in normal form
- Converted to excess-15, the exponent $4$ is $4 + 15 = 19$
- Encoded as unsigned integer, the excess-15 exponent is 10011
- The fraction without 1. is 010010 (a 0 added to the end, no rounding needed)
- The final encoding is 1 10011 010010
What is the 32-bit IEEE 754 encoding of $+\infty, -\infty, +0.0, -0.0$, NaN?
What exponent value is used by denormalized 32-bit floating-point numbers? (answer: $-126$)
What is the range of float/double?
What is the number of significant digits of float/double?

Typical topics include:

Movement instructions (mov/movz/movs/cmov).
Arithmetic and comparison instructions (lea, add, sub, imul, mul, idiv, div, inc, dec, neg, not, and, or, xor, sar, sal, shr, shl, cmp, test).
Computing the resulting register values.
Computing the resulting flags ZF, SF, OF, CF.

For example, after the instructions:

movw $0x1122,%bx
cmpw $0x1100,%bx

Another example:

movb $0x80,%al
movsbl %al,%eax
xorw $0x8020, %ax

(More examples are on the slides and textbook. Make sure that you understand instructions on this slide plus lea, imul, mul, idiv, div.)

Typical tasks include:

Mastering all of the indirect addressing modes such as (%rax), 10(%rax), (%rax,%rbx), (%rax,%rbx,2), 3(,%rbx,2).
Given the contents of the registers and memory, figure out the effect of data movement instructions (mov) with indirect addressing modes.
Direct memory addressing (0x1020) and immediate values ($0x1020).
Remember that 4-byte operations set the most-significant 4-bytes of the destination register to 0.
Conditional moves (e.g., cmovge %rcx,%rdx following cmpq %rax,%rbx moves the data of %rcx to %rdx only when %rbx >= %rax).

(Examples are on the slides and in Chapter 3 of the textbook. Study all addressing modes on this slide.)

By looking at C code and x86-64 assembly code side-by-side (as in these slides), you should be able to complete missing parts of either.

Features of C covered in class include:

if statements, for/while loops (translated using cmp, test, and jumps)
Pointers (translated using indirect addressing).
Access to array elements (remember to multiply by the element size, as in (%rdx,%rcx,4) when %rcx is the index and %rdx is the base address of an int array).
Multiplication without * (e.g., 3*x == (x + (x << 1))).
Division by powers of 2 (e.g., x/4 == (x + bias) >> 2).
lea-style operations (e.g., 7 + a + 4*b == 7(%rax,%rbx,4)).
Bitwise operations (|, &, ~, ^, >>, <<).

The textbook has excellent practice problems such as 3.7, 3.9, 3.10, 3.18, 3.24. Study all instructions on described in Unit 4 and 6.

Assembly procedures: callq to push a return address and jump, ret to pop a return address and jump back.
Why jumps are not sufficient to call/return from a procedure.
Registers used to pass arguments (rdi, rsi, rdx, rcx, r8, r9, others pushed on the stack in reverse order) and return values (rax).
Local variables on the stack: situations in which we are forced to use variables on the stack (i.e., in memory) instead of registers; allocation/deallocation of variables by decreasing/increasing rsp; scope of local variables.
Callee-saved and caller-saved registers.
The use of the rbp register.

After completing DataLab, you should be very proficient in bitwise operations in C (|, &, ~, ^, >>, <<).

For example, given the following variables:

long x = 0x1122334455667788;
int m = 0xC3;

What is the value of x & ((m << 8) | (m << 16) | m)?

We expect you to be able to solve minor variants of the programming puzzles that were part of DataLab.