3.72

Solution

Assembly code:

    long aframe(long n, long idx, long *q)
    n in %rdi, idx in %rsi, q in %rdx
1   aframe:
2   pushq   %rbp
3   movq    %rsp, %rbp
4   subq    $16, %rsp           Allocate space for i (%rsp = s1)
5   leaq    30(,%rdi,8), %rax
6   andq    $-16, %rax
7   subq    %rax, %rsp          Allocate space for array p (%rsp = s2)
8   leaq    15(%rsp), %r8
9   andq    $-16, %r8           Set %r8 to &p[0]
    ⋮

A.

\[ s2 = s1 - (30 + 8 \cdot n)\ \text{AND}\ (-16) \]

The $k\ \text{AND}\ (-16)$ is equivalent to $k - k \bmod 16$ (from the bitwise representation of -16)

We have,

$(30 + 8 \cdot n)\ \text{AND}\ (-16) = 30 + 8 \cdot n - (30 + 8 \cdot n) \bmod 16$

$= 30 + 8 \cdot n - (16 + 8 \cdot n + 8 + 6) \bmod 16$

$= 30 + 8 \cdot n - (16 + 8 \cdot (n+1) + 6) \bmod 16$

We have two cases, when n is even and when is odd

When n is even,

$n = 2k$

$\implies (16 + 8 \cdot (n + 1) + 6) \bmod 16 = (16 + 8 \cdot (2k + 1) + 6) \bmod 16$

$= (16 \cdot (k + 1) + 14) \bmod 16$

$= 14$

$(30 + 8 \cdot n)\ \text{AND}\ (-16) = 30 + 8 \cdot n - 14 = 16 + 8 \cdot n$

When n is odd,

n + 1 is even. $\implies n + 1 = 2k$

$(16 + 8 \cdot (n + 1) + 6) \bmod 16 = (16 + 8 \cdot (2k) + 6) \bmod 16$

$= 6$

We get, $(30 + 8 \cdot n)\ \text{AND}\ (-16) = 30 + 8 \cdot n - 6 = 24 + 8 \cdot n$

\[ \begin{align} s_2 = \begin{cases} s_1 - 8 \cdot n - 16 & \text{if n is even} \\ s_1 - 8 \cdot n - 24 & \text{if n is odd} \end{cases} \end{align} \]

B.

From lines 8 and 9, $p = 15 + s_2\ \text{AND}\ (-16)$.

$= 15 + s_2 - (15 + s_2) \bmod 16$

$(15 + s_2) \bmod 16 = (15 \bmod 16 + s_2 \bmod 16) \bmod 16$

$= (15 + s_2 \bmod 16) \bmod 16$

$s_2 \bmod 16$ can have 16 values, from 0 to 15.

We have these two cases:

Case 1: $s_2 \bmod 16 = 0$

$(15 + s_2 \bmod 16) \bmod 16 = 15$, and we get $p = 15 + s_2 - 15 = s_2$

Case 2: $1 <= (s_2 \bmod 16) <= 15$

Let $k = s_2 \bmod 16$

$(15 + k) \bmod 16 = (16 - 1 + k) \bmod 16 = (k - 1) \bmod 16$

$0 <= k - 1 <= 14 \implies p = 15 + s_2 - (s_2 \bmod 16 - 1) = 16 + s_2 - s_2 \bmod 16$

\[ \begin{align} p = \begin{cases} s_2 & \text{if $s_2$ is a multiple of 16} \\ s_2 + 16 - s_2 \bmod 16 & \text{otherwise} \end{cases} \end{align} \]

C.

$e_1 + e_2 = s_1 - s_2$

From A,

$e_1 + e_2$ is either 16 (when $n$ is even) or 24 (when $n$ is odd).

From B,

$e2$ is either 0 (when $s_2$, and consequently $s_1$, as the offset between $s_1$ and $s_2$ is also a multiple of 16), or $16 - s_2 mod 16$ (same as $16 - s_1 mod 16$).

We end up with four cases

\[ \begin{align} e_1 = \begin{cases} 24 - 0 & \text{if $s_1$ is a multiple of 16 and n is odd} \\ 24 - (16 - s_1 \bmod 16) & \text{if $s_1$ is not a multiple of 16 and n is odd} \\ 16 - 0 & \text{if $s_1$ is a multiple of 16 and n is even} \\ 16 - (16 - s_1 \bmod 16) & \text{if $s_1$ is not a mulitiple of 16 and n is even} \end{cases} \end{align} \]

By comparing these cases, the case for maximum is case 1 where $e_1$ is 24, and the case for minimum is the last one, where $e_1$ is 1 when $s_1 \bmod 16$ is 1.

D.

Always a multiple of 16 relative to $s_1$.