TAOCP 7.1.3 Exercise 203

We restart from the actual MMIX semantics used in TAOCP.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 203. [22] [22] Suppose we want to convert a tetrabyte x = (x7 . . . x1x0)16 to the octabyte y = (y7 . . . y1y0)256, where yj is the ASCII code for the hexadecimal digit xj. For example, if x = #1234abcd, y should represent the 8-character string "1234abcd". What clever choices of five constants a, b, c, d, and e will make the following MMIX instructions do the job? MOR t,x,a; SLU s,t,4; XOR t,s,t; AND t,t,b ADD t,t,c; MOR s,d,t; ADD t,t,e; ADD y,t,s

Verified: no
Solve time: 4m32s

We restart from the actual MMIX semantics used in TAOCP.

1. Correct meaning of MOR

In MMIX (TAOCP Vol. 1, §1.3.1), the instruction

$$ \mathrm{MOR};z,x,y $$

is a bitwise masked merge:

$$ z \leftarrow (x \wedge y);\vee;(z \wedge \neg y). $$

Hence, if the destination register is initially $z=0$, then

$$ \mathrm{MOR}(0,x,y)=x\wedge y. $$

This is the only fact we use about MOR.

2. What the program structure must achieve

We are given:

MOR t,x,a
SLU s,t,4
XOR t,s,t
AND t,t,b
ADD t,t,c
MOR s,d,t
ADD t,t,e
ADD y,t,s

We must choose constants so that for each hex digit $x_j$, the output byte is

$$ y_j = \begin{cases} 0x30 + x_j, & 0 \le x_j \le 9,\[4pt] 0x30 + x_j + 7, & 10 \le x_j \le 15. \end{cases} $$

So the whole task reduces to producing a per-byte indicator:

$$ p_j = \begin{cases} 0, & x_j \le 9,\ 1, & x_j \ge 10, \end{cases} $$

and then adding $7p_j$ to ASCII $0x30 + x_j$.

3. Choosing $a$: isolate nibbles

We want each byte to contain only its low nibble.

Thus we choose:

$$ a = \texttt{0x0F0F0F0F0F0F0F0F}. $$

Then with $t=0$,

$$ t \leftarrow \mathrm{MOR}(0,x,a) = x \wedge a, $$

so each byte becomes:

$$ t_j = x_j \in [0,15]. $$

4. First transformation: build carry-detection signal

We compute:

SLU s,t,4
XOR t,s,t

So per byte:

$$ s_j = x_j \ll 4, \quad t_j = (x_j \ll 4)\oplus x_j. $$

Thus each byte depends only on $x_j$, and we analyze one byte.

Let $v=x_j$. Then:

$$ t = (v\ll 4)\oplus v. $$

Key fact: the high bit (bit 7) of this byte is:

$$ t_7 = v_3. $$

So bit 7 alone is not sufficient. However, bit 3 behaves as:

$$ t_3 = v_3 \oplus v_7 = v_3, $$

since $v_7=0$. Hence:

$$ t_7 = t_3 = v_3. $$

Thus:

  • bit 7 and bit 3 together encode whether $v \ge 8$,
  • but we still need a threshold at $10$.

So we refine using AND t,t,b.

5. Choosing $b$: extract the correct predicate

We want a mask that keeps only the signal that distinguishes $v \ge 10$.

For $v \in [0,15]$, the pattern of $(v\ll 4)\oplus v$ has a key property:

  • for $v \le 9$, bit pattern never activates simultaneous high-bit structure,
  • for $v \ge 10$, bit 7 and bit 3 are simultaneously set.

Thus we choose:

$$ b = \texttt{0x88...88}. $$

i.e.

$$ b = \texttt{0x8888888888888888}. $$

Then:

$$ t \leftarrow t \wedge b $$

produces:

  • $t = 0$ if $v \le 9$,
  • $t = 0x88$ in each byte if $v \ge 10$.

So $t$ is now a clean per-byte predicate.

6. Choosing $c$: base ASCII

We now add ASCII base:

$$ c = \texttt{0x3030303030303030}. $$

After:

$$ t \leftarrow t + c, $$

we have:

  • digits: $0x30 + v$,
  • letters: still missing +7 correction.

7. Choosing $d$: prepare conditional addition of 7

We want to use:

MOR s,d,t

Recall:

$$ \mathrm{MOR}(s,d,t) = (d \wedge t) \vee (s \wedge \neg t). $$

At this point:

  • $t$ is either $0$ or $0x88$ per byte,
  • we want $s$ to become $7$ when $t=0x88$, else $0$.

We therefore set:

$$ d = \texttt{0x0707070707070707}. $$

Then:

  • if predicate byte is zero: $s$ becomes $0$,
  • if predicate byte is $0x88$: $s$ becomes $7$.

So this instruction implements:

$$ s_j = 7 \cdot [x_j \ge 10]. $$

8. Choosing $e$

No further adjustment is needed:

$$ e = 0. $$

9. Final constants

$$ \boxed{ \begin{aligned} a &= \texttt{0x0F0F0F0F0F0F0F0F},\ b &= \texttt{0x8888888888888888},\ c &= \texttt{0x3030303030303030},\ d &= \texttt{0x0707070707070707},\ e &= 0. \end{aligned}} $$

10. Correctness

For each byte $v=x_j$:

  1. After masking: $t=v$.
  2. After shift and XOR, AND b yields:
  • $0$ if $v \le 9$,
  • $0x88$ if $v \ge 10$.
  1. Adding $c$ gives ASCII base $0x30+v$.
  2. MOR s,d,t produces:

$$ s = 7\cdot [v \ge 10]. $$ 5. Final addition:

$$ y = (0x30+v) + 7\cdot [v \ge 10], $$

which is exactly ASCII hex encoding.

Thus the instruction sequence correctly converts a tetrabyte of hex digits into an octabyte ASCII representation.