Exam1

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Exam1

Reference

Powers of two

Hexadecimal

Selected x86-64 instructions and conventions

• cmp %a, %b: compute the status bits as if you had computed sub %r2, %r1

• jne: jump if not equal

• inc %a: increment the value in register a

• add %a, %b: add the values in register a and b, store the result in register bd

• imulq %a, %b: multiply the 64-bit two's complement value provided in register a with the two's complement value in register b, store the result in register b

• caller-save registers: %rax, %rdi, %rsi, %rdx, %rcx, %r8, %r9, %r10, %r11

• callee-save registers: %rsp, %rbx, %rbp, %r12, %r13, %r14, %r15

C Tvpes

In all questions concerning C:

• uint8_t is an 8-bit unsigned integer type;

• uint 16_t is a 16-bit unsigned integer type;

• uint32_t is a 32-bit unsigned integer type;

• uint64_t is a 64-bit unsigned integer type;

• int8_t is an 8-bit signed two's complement integer type;

• int16_t is a 16-bit signed two's complement integer type;

• int32_t is a 32-bit signed two's complement integer type;

• int64_t is a 64-bit signed two's complement integer type;

• float isa 32-bit IEEE 754 floating point type with 1 sign bit, 8 exponent bits (biased by 127), and 23 fraction bits; and

• double is a 64-bit IEEE 754 floating point type with I sign bit, 11 exponent bits (biased by 1023), and 52 fraction bits

Multiple Choice

Mark each of the following statements as either true or false.

1. The x86 jmp instruction conditionally jumps based on the values of bits in status registers.     (3)

2. An assembler directly converts high-level C code to machine code.       (3)

3. A 32-bit instruction set architecture can address a maximum of 4 GB of memory.      (3)

4. A compiler may choose to insert "empty space" between variables to ensure proper alignment.     (3)

5. The value Oxff00, when interpreted as a hexadecimal representation of an int 16-t, is negative.     (3)

6. In x86 assembly the instruction pointer is stored in %rsp.     (3)

7. The ALU has different circuitry to handle addition of two's complement values and addition of unsigned values.     (3)

8. The .text section contains executable program code.     (3)

9. Let I refer to bitwise or. Then 0xff00 I 0x0f0f is equal to 0xffff.     (3)

10. It is possible to perfectly represent the value 10/1 using IEEE floating point representation.     (3)

Short Answer

Respond to the following short answer questions.

11. Give the binary int8_t representation of the following values if one exists. If one does not exist, describe why.

(a) 14                 (4)

(b) 4/3                 (4)

(c) -121                 (4)

(d) 255                 (4)

12. Give the binary float representation of the following values if one exists. If one does not exist, describe why.

(a) 14                 (4)

(b) 4/3                 (4)

(c) -121                 (4)

(d) 255                 (4)

13. What is the output of the following C program?                      (6)

uint8 t a= 181 << 1:

uint8_t b = 154;

uint8 t sum=a+b;

printf("%u\n", sum);

14. In class we discussed five strategies for mitigating buffer overflows. Identify one of them. Give a short de-l scription (two to three bullet points) of how it works and its limitations.               (6)

15. In two or three sentences, describe the difference between callee-save and caller-save registers.              (6)

Free Response

Respond to the following free response programming question.

16. A common operation in cryptography is to compute c = x, where e is a constant. A typical choice for e is the value 65537=216 +1 because there exists a fast assembly routine for this value using a technique called repeated squaring.

Repeated squaring can be used to quickly calculate exponents that are a power of two. For example, x can be computed as (x2)2 using two imulq instructions. Similarly, x216 can be computed using sixteen imulq instructions.

The routine works like this:

• Save x in a temporary variable (such as a register).

• Compute y =x216 using repeated squaring and store y in another temporary variable (such as another register).

• Return z=x·y, which is x65537 because x·x216 = x216+1 by the laws of exponents.

Implement this fast exponentiation routine in x86-64 assembly. You must use a loop for the repeated squaring, properly align memory, follow x86-64 register conventions, and provide a comment for each assembly instruction.

You should use assume that e = 65537 is a constant and imulq instructions will not overflow. The only parameter will be r. You do not have to implement any test cases.

An example function prototype in C for your implementation is as follows:

// Compute x*65537

int64_t fast_exponentiate(int64_t x);

Some example calls:

• fast_exponentiate (0)

• fast_exponentiate (2)

• fast_exponentiate(17)

A skeleton template is provided on the next page.

• section .text

• globl fast_exponentiate

fast_exponentiate: