TAOCP 7.1.3 Exercise 213

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 213. ▶ [HM26] [HM26] Implement the CRC procedure (183) on MMIX.

Verified: no
Solve time: 2m10s

The original solution fails because it does not implement the correct byte insertion into the polynomial register and therefore does not preserve the CRC invariant. A correct implementation must first form the concatenation $R(x)\cdot x^8 + B(x)$ and only then perform reduction modulo $P(x)$.

1. Correct polynomial model

Let the generator polynomial be

$$ P(x)=x^d+p_{d-1}x^{d-1}+\cdots+p_1x+1, \quad p_i\in{0,1}. $$

Write the current remainder as a polynomial $R(x)$ with $\deg R < d$. For an incoming byte $B$, interpreted as a polynomial $B(x)$ of degree $\le 7$, the CRC update is

$$ R(x) \leftarrow \bigl(R(x)\cdot x^8 + B(x)\bigr)\bmod P(x). $$

This identity is the core invariant and must be reflected exactly in the MMIX implementation.

2. Correct byte insertion step

The previous solution incorrectly computed $(R \oplus B)\ll 8$. The correct construction is:

$$ R \leftarrow (R \ll 8)\ \oplus\ B. $$

This places the byte into the low 8 bits of the shifted register, matching the polynomial addition $+B(x)$ after multiplication by $x^8$.

On MMIX:

shifting is SLU
byte insertion is XOR after the shift

So the correct order is:

SLU     r, r, 8
XOR     r, r, b

3. Reduction modulo $P(x)$

After shifting, the degree of the intermediate polynomial can be as large as $d+7$. Reduction must eliminate all terms of degree $\ge d$, not only test a single bit.

Let:

$$ P_{\text{full}} = 1\ll d ;; \text{OR} ;; P' $$

where $P' = P \bmod x^d$.

When a term $x^i$ with $i\ge d$ appears, we use:

$$ x^i \equiv x^{i-d} P(x). $$

Thus reduction is performed by scanning down from the highest possible bit.

The highest possible degree after byte shift is $d+7$. So we must reduce all bits from $d+7$ down to $d$.

4. Correct MMIX implementation

Registers:

r: current remainder $R$
b: input byte $B$
p: lower part $P'$
t: temporary
i: loop counter

We assume a bit mask $1\ll d$ is available in m.

Core loop per byte

        SLU     r, r, 8        % r <- r << 8
        XOR     r, r, b        % r <- r xor b

Reduction loop

We reduce all high bits from $d+7$ down to $d$:

        SET     i, d+7

Reduce  CMP     t, i, d
        PBL     t, Done        % if i < d stop

        % test bit i
        SET     t, 1
        SLU     t, t, i
        AND     t, r, t
        PBEQ    t, Skip

        % r ^= P << (i-d)
        SUB     t, i, d
        SET     tmp, p
        SLU     tmp, tmp, t
        XOR     r, r, tmp

Skip    SUB     i, i, 1
        JMP     Reduce

Done:

5. Why this is correct

5.1 Correct byte polynomial construction

After:

SLU r, r, 8
XOR r, r, b

we obtain:

$$ r = R(x)\cdot x^8 + B(x), $$

because:

shifting implements multiplication by $x^8$
XOR adds the byte polynomial in the low 8 bits

This exactly matches the CRC definition.

5.2 Correctness of reduction loop

At any step, if bit $x^i$ is present for $i \ge d$, we eliminate it using:

$$ x^i \leftarrow x^i \oplus x^{i-d}P(x), $$

which preserves equivalence modulo $P(x)$ and strictly decreases the highest-degree term.

Because we iterate from $d+7$ down to $d$, every possible overflow term introduced by the byte shift is eliminated.

5.3 Termination and invariant

After the loop:

all bits $x^i$ for $i \ge d$ are zero
hence $\deg(r) < d$
and $r \equiv R(x)x^8 + B(x) \pmod{P(x)}$

Thus the CRC invariant is preserved for every byte.

6. Correction of prior issues

XOR-before-shift bug removed by restoring correct order.
Polynomial interpretation restored to correct concatenation model.
Reduction no longer assumes a single conditional step; full high-bit elimination is performed.
Mask $M$ is unnecessary and omitted.

This completes a correct MMIX implementation of CRC procedure (183) consistent with the polynomial definition over $\mathbb{F}_2[x]$.