TAOCP 7.1.3 Exercise 188

The failure in the previous solution is fundamental: the bitmap is 1-bit packed, so each pixel must be extracted by bit operations, not by byte-wise `LDB` interpretation.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 188. ▶ [25] [25] Bitmap images can often be viewed conveniently using pixels that are shades of gray instead of just black or white. Such gray levels typically are 8-bit values that range from 0 (black) to 255 (white); notice that the black/white convention is tradition- ally reversed with respect to the 1-bit case. An m × n bitmap whose resolution is 600 dots per inch corresponds nicely to the (m/8) × (n/8) grayscale image with 75 pixels per inch that is obtained by mapping each 8 × 8 subarray of 1-bit pixels into the gray level ⌊255(1 −k/64)1/γ + 1 2⌋, where γ = 1.3 and k is the number of 1s in the subarray. Write an MMIX routine that converts a given m × n array BITMAP into the corre- sponding (m/8) × (n/8) image GRAYMAP, assuming that m = 8m′ and n = 64n′.

Verified: no
Solve time: 4m29s

The failure in the previous solution is fundamental: the bitmap is 1-bit packed, so each pixel must be extracted by bit operations, not by byte-wise LDB interpretation. The corrected solution restarts the computation of $k(i,j)$ from the actual storage model.

1. Correct bitmap representation

The bitmap is an $m \times n$ array of bits, stored in row-major order, packed 8 bits per byte.

Thus each row contains $n/8$ bytes.

Given:

$$ m = 8m', \quad n = 64n' $$

so:

$$ \frac{n}{8} = 8n' $$

Let:

$$ N_B = \frac{n}{8} $$

Byte addressing

For pixel $(x,y)$:

  • byte index in row: $y \div 8$
  • row byte offset: $x \cdot N_B$

So byte address is:

$$ \text{BITMAP} + x \cdot N_B + \left\lfloor \frac{y}{8} \right\rfloor $$

Within that byte, the bit position is:

$$ b = y \bmod 8 $$

We use the standard convention:

  • bit 7 is the leftmost pixel in the byte
  • bit 0 is the rightmost pixel

Thus the pixel value is:

\text{BIT}(x,y) = \left( \frac{\text{byte} \gg (7-b)} \right) \bmod 2

2. Block structure

Each output pixel corresponds to an $8 \times 8$ block:

$$ x = 8i + a,\quad y = 8j + b $$

with:

$$ 0 \le a,b \le 7 $$

The block sum is:

$$ k(i,j)=\sum_{a=0}^{7}\sum_{b=0}^{7} \text{BIT}(8i+a,,8j+b) $$

3. Gray value mapping

Precomputed table:

$$ T[k] = \left\lfloor 255\left(1-\frac{k}{64}\right)^{1/\gamma} + \frac12 \right\rfloor,\quad \gamma = 1.3 $$

4. MMIX implementation

Registers

  • $0 return
  • $1 i
  • $2 j
  • $3 a
  • $4 b
  • $5 k
  • $6 BITMAP base
  • $7 GRAYMAP base
  • $8 T base
  • $9 temp byte
  • $10 address / temp
  • $11 N_B = n/8
  • $12 shift amount
  • $13 gray value

5. Correct MMIX routine

GrayMap  PUSHJ 0,InitT

         SET   1,0              % i = 0

I_loop   CMP   $255,1,m'
         BZ    $255,Done

         SET   2,0              % j = 0

J_loop   CMP   $255,2,NG
         BZ    $255,NextI

         SET   5,0              % k = 0
         SET   3,0              % a = 0

A_loop   CMP   $255,3,8
         BZ    $255,BlockDone

         SET   4,0              % b = 0

B_loop   CMP   $255,4,8
         BZ    $255,NextA

         % --, compute BITMAP byte address ----
         % (8i+a)*N_B + j

         MUL   $10,1,8
         ADD   $10,$10,3
         MUL   $10,$10,$11
         ADD   $10,$10,2
         ADD   $10,$10,$6

         % load packed byte
         LDB   $9,$10,0

         % --, extract bit b ----
         % shift = 7 - b
         SET   $12,7
         SUB   $12,$12,4
         SR    $9,$9,$12
         AND   $9,$9,1

         ADD   $5,$5,$9

         INC   4,1
         JMP   B_loop

NextA    INC   3,1
         JMP   A_loop

BlockDone
         % lookup T[k]
         ADD   $10,$8,$5
         LDB   $13,$10,0

         % store GRAYMAP[i,j]
         MUL   $10,1,NG
         ADD   $10,$10,2
         ADD   $10,$10,$7
         STB   $13,$10,0

         INC   2,1
         JMP   J_loop

NextI    INC   1,1
         JMP   I_loop

Done     POP   0,0
         GO    $0,$0,0

6. Correctness argument

(1) Correct pixel extraction

Each bitmap pixel is stored as a single bit inside a packed byte. The routine:

  • selects the correct byte using

$$ x \cdot (n/8) + \lfloor y/8 \rfloor $$

  • extracts bit $b = y \bmod 8$
  • isolates it via shift and mask

Thus each $\text{BIT}(x,y)$ is computed exactly once and correctly.

(2) Correct block aggregation

The nested loops over $a,b \in {0,\dots,7}$ enumerate all pixels in the $8\times 8$ block corresponding to $(i,j)$. Therefore:

$$ k(i,j) = \sum_{a,b} \text{BIT}(8i+a,8j+b) $$

is computed exactly.

(3) Correct output layout

Each block produces one grayscale byte stored at:

$$ \text{GRAYMAP}[i,j], \quad 0 \le j < n/8 $$

with linearization:

$$ i \cdot (n/8) + j $$

which matches the required $(m/8) \times (n/8)$ image layout.

(4) Correct gray-level mapping

The lookup table implements:

$$ \left\lfloor 255\left(1-\frac{k}{64}\right)^{1/\gamma} + \frac12 \right\rfloor $$

so the nonlinear perceptual correction is applied exactly once per block.

Conclusion

The corrected program fixes the critical defect by replacing byte-wise pixel access with proper bit extraction from packed bitmap storage. All subsequent computations, block aggregation, and output indexing are consistent with TAOCP conventions.