601.229 (S23): Exam 1 Practice Solutions

Exam 1 Practice Solutions

These questions are designed to aid your review of the material covered by the first exam. They are not representative of the difficulty, type, or length of the questions on the exam.

In all questions, assume signed integers use two’s complement representation.

Q1. Number Representation

Write the representation of the number 43 in base 16, base 10, base 8, base 6, and base 2.

From grouping 4 binary bits into one hexadecimal digit:
43₁₀ = 2B₁₆

We normally use base 10:
43₁₀ = 43₁₀

From grouping 3 binary bits into one octal digit:
43₁₀ = 53₈

From 1 * 6^2 + 1 * 6^1 + 1 * 6^0:
43₁₀ = 111₆

From 1 * 2^5 + 1 * 2^3 + 1 * 2^1 + 1 * 2^0:
43₁₀ = 101011₂
On an 8-bit computer, what is the sum of unsigned 208 + 53?, and what is the difference of signed 103 - 24?

208 + 53 = 5: Due to the 8th bit overflowing, 00000101 remains
103 + (-24) = 79: From 01100111 + 11101000
Write what -5 would be on a 4-bit and an 8-bit system.

4-bit system: -5₁₀ = 1011₂
-5₁₀ = -8₁₀ + 3₁₀ = 1000₂ + 0011₂
8-bit system: -5₁₀ = 11111011₂
-5₁₀ = -128₁₀ + 123₁₀ = 10000000₂ + 01111011₂
Show how to calculate 1.250 + 3.375 and 1.250 * 3.375 using floating point.

Assume 32-bit single precision IEEE 754 floating point values

1.250₁₀ = 1.01₂ = 1.01₂ × 2⁰

3.375₁₀ = 11.011₂ = 11.011₂ × 2⁰ = 1.1011₂ × 2¹

Addition:

Convert the smaller operand to the exponent of the larger operand

1.250₁₀ = 1.01₂ = 1.01₂ × 2⁰ = 0.101₂ × 2¹

Add:

0.101₂ × 2¹ + 1.1011₂ × 2¹ = 10.0101₂ × 2¹

Normalize:

10.0101₂ × 2¹ = 1.00101₂ × 2²

Encoded as IEEE 754 single precision (recall bias is 127, so exponent of 2 is encoded as 2 + 127 = 129):

Sign Exponent Fraction

0 10000001 00101000000000000000000

Multiplication:

Product is:

(1.01₂ × 2⁰) × (1.1011₂ × 2¹)

Rewritten:

(1.01₂ × 1.1011₂) × (2⁰ × 2¹)

Multiply mantissas:

1.01₂ × 1.1011₂ = 10.000111₂

Multiply bases/exponents:

2⁰ × 2¹ = 2¹

Product is:

10.000111₂ × 2¹

Normalize:

10.000111₂ × 2¹ = 1.0000111₂ × 2²

Encoded as IEEE 754 single precision (bias is 127, so exponent of 2 is encoded as 2 + 127 = 129):

Sign Exponent Fraction

0 10000001 00001110000000000000000
How are 32 bits broken down in IEEE-754?

Sign Bit Exponent Fraction/Mantissa

1 8 23

Sign	Exponent	Fraction
0	10000001	00101000000000000000000

Sign	Exponent	Fraction
0	10000001	00001110000000000000000

Sign Bit	Exponent	Fraction/Mantissa
1	8	23

Q2. Bitwise Operators

Write the results of arithmetic and logical executions of -113 >> 1, where -113 is an 8 bit value.

-113 in 8 bits is 10001111.
An arithmetic shift results in 11000111₂ = -57₁₀, preserving the sign bit.
A logical shift results in 01000111, treating the sign bit as any other bit.
What is the fastest way to compute 16 * 13? (Hint: don't use multiplication.)

16 * 13 can be found by 13 << 4
Determine 43 | 13, 43 & 13, 43 ^ 13, and ~43 (assume operands are unsigned 8 bit.)

43₁₀ = 00101011₂
13₁₀ = 00001101₂
43₁₀ | 13₁₀ = 00101111₂
43₁₀ & 13₁₀ = 00001001₂
43₁₀ ^ 13₁₀ = 00100110₂
~43₁₀ = 11010100₂

Q3. Basic Assembly Questions

What are the steps that happen after you run gcc on a .c program? What does the output after each step look like, and what are their file extensions?

Compilation, Assembly, Linking
The compile step converts .c source to .s assembly language code (movl $0, %eax)
The assembler step converts .s assembly to .o machine code (machine instructions, binary numbers representing the instruction the CPU should execute)
The linking step combines all .o files into an executable
How, why, and when do you align the stack pointer?

How: To align the stack pointer, N bytes must be subtracted from %rsp, using some combination of the subq and pushq instructions.

Why: %rsp must contain an address that is a multiple of 16 at the site of any call instruction. Some functions, such as printf, use special instructions to transfer data from the stack which require alignment on a multiple of 16.

When: On entry to a subroutine (a.k.a. function). Because the call instruction pushes an 8 byte return address before transferring control to the called subroutine, %rsp will contain an address which is a multiple of 8 but not a multiple of 16.
What are caller and callee saved registers?
Caller-saved: These are registers which may be freely modified by any function. However, this means that when calling a function, the caller must assume that the contents of any caller-saved register could have been modified. If any caller-saved register needs to have its contents preserved across a function call, it will need to be saved by the caller (perhaps by using pushq/popq.) Hence, "caller-saved".

Callee-saved: These are registers which may be assumed not to change as a result of calling a function. This feature makes them especially useful as loop counters, accumulators, etc. This also means that any function which will modify a callee-saved register will need to save its original value, and restore that value before returning. This is usually done using a pushq instruction on entry to the procedure, and popq just before returning from the procedure.

Write a local loop, and the line which calls it in main, that sums all the values from 0-9, given #define N 9

Answer:

#define N 9

        .section .rodata
sResultMsg: .string "Sum is %ld\n"

        .section .text

        .globl main
main:
        subq $8, %rsp       /* align stack */

        movq $0, %r10       /* counter */
        movq $0, %r11       /* sum */
.Ltop:
        addq %r10, %r11     /* add current counter value to sum */
        incq %r10           /* increment counter */
        cmpq $N, %r10       /* is %r10 <= N? */
        jle .Ltop           /* if so, continue */

        movq $sResultMsg, %rdi /* printf format arg */
        movq %r11, %rsi     /* value to be printed */
        call printf         /* print result message */

        movl $0, %eax       /* return 0 from main */
        addq $8, %rsp       /* restore stack pointer */
        ret                 /* return from main */

In AT&T syntax, what is the order of arguments for these instructions, and where are the results stored?
- addq %r9, %r10
  The sum of %r9 and %r10 is stored in %r10
- movl $0xFFFF0000, %esi
  The value 00000000FFFF0000 (hexadecimal) is stored in %rdi (%esi is the 32 bit sub register of %rdi, and a 32-bit move into a 64-bit register clears the upper 32 bits)
- cmpl %eax, %eax
  %eax (the low 32 bits of %rax) is compared to itself, but is not modified. Condition codes will be set based on the result of the comparison.

Q4. x86-64 Assembly Programming

Write an x86-64 assembly language function called swapInts which swaps the values of two int variables. The C function declaration for this function would be void swapInts(int *a, int *b);

Hints:

Think about which registers the parameters will be passed in
Think about what register(s) would be appropriate to use for temporary value(s)
Consider that int variables are 4 bytes (32 bits), and use an appropriate operand size suffix.

Important: Your function should follow proper x86-64 Linux register use conventions. Be sure to include the label defining the name of the function.

Answer:

        .globl swapInts
swapInts:
        subq $8, %rsp       /* not strictly necessary, but good style nonetheless */

        movl (%rdi), %r10d  /* get original value of *a */
        movl (%rsi), %r11d  /* get original value of *b */
        movl %r10d, (%rsi)  /* put original value of *a in *b */
        movl %r11d, (%rdi)  /* put original value of *b in *a */

        addq $8, %rsp       /* restore stack pointer */
        ret

Q5. x86-64 Assembly Programming

Consider the following C function prototype:

void str_tolower(char *s);

The str_tolower function modifies a C character string so that each upper case letter is converted to lower case.

Show an x86-64 assembly language implementation of this function. Note that the ASCII codes for upper case letters are in the range 65–90, and the ASCII codes for lower case letters are the range 97–122. Characters that aren’t letters should not be modified.

Possible answer:

	.globl str_tolower
str_tolower:
	subq $8, %rsp

.Lstr_tolower_loop:
	movb (%rdi), %al
	cmpb $0, %al
	je .Lstr_tolower_done

	cmpb $65, %al
	jb .Lstr_tolower_loop_continue
	cmpb $90, %al
	ja .Lstr_tolower_loop_continue

	addb $(97 - 65), %al
	movb %al, (%rdi)

.Lstr_tolower_loop_continue:
	incq %rdi
	jmp .Lstr_tolower_loop

.Lstr_tolower_done:
	addq $8, %rsp
	ret