TAOCP 7.1.3 Exercise 189

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 189. [25] [25] Given a 64 × 64 bitmap, what’s a good way (a) to transpose it, or (b) to rotate it counterclockwise by 90◦, using operations on 64-bit numbers?

Verified: no
Solve time: 1m14s

Solution

Let the bitmap be stored as $8$ consecutive rows of bytes per block column. Since $n = 64n'$, each row consists of $8n'$ bytes, and each $8 \times 8$ subarray is contained in exactly $8$ consecutive rows and one group of $8$ consecutive bits inside a byte.

For each $8 \times 8$ block, let $k$ be the number of 1-bits in the block. The required gray level is

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

with $\gamma = 1.3$, so $g(k)$ depends only on $k \in {0,\dots,64}$.

A direct computation of $k$ is reduced to byte operations by splitting each $8 \times 8$ block into $8$ bytes $b_0,\dots,b_7$, where each byte represents one row of the block. Then

$k = \sum_{i=0}^{7} \mathrm{pop}(b_i),$

where $\mathrm{pop}(b)$ is the number of 1-bits in a byte.

Precompute two tables:

$\mathrm{POP}[b] = \mathrm{pop}(b), \quad 0 \le b < 256,$

and

$\mathrm{GRAY}[k] = \left\lfloor 255\left(1 - \frac{k}{64}\right)^{1/\gamma} + \frac{1}{2} \right\rfloor, \quad 0 \le k \le 64.$

Then each block is converted by table lookups only.

Let BITMAP be addressed as byte array $B$, and GRAYMAP as byte array $G$. Each row of GRAYMAP has $n/8 = 8n'$ entries.

MMIX routine:

        LOC     Data_Segment

POP     IS      @           % 256-byte table
GRAY    IS      @           % 65-byte table

BITMAP  GREG
GRAYMAP GREG

m       GREG
nblocks GREG

k       GREG
i       GREG
j       GREG
p       GREG

        LOC     #100

Convert SET     i,0

RowLp   CMP     i,m
        BZ      Done

        SET     j,0

ColLp   CMP     j,nblocks
        BZ      NextRow

        SET     k,0

        % address of 8x8 block in BITMAP
        SET     p,BITMAP
        MUL     t,i,8*nblocks
        ADD     p,p,t
        ADD     p,p,j

        % load 8 bytes and accumulate popcount
        LDB     t,p,0
        LDB     t2,p,1
        LDB     t3,p,2
        LDB     t4,p,3
        LDB     t5,p,4
        LDB     t6,p,5
        LDB     t7,p,6
        LDB     t8,p,7

        LDB     t,POP,t
        ADD     k,k,t
        LDB     t,POP,t2
        ADD     k,k,t
        LDB     t,POP,t3
        ADD     k,k,t
        LDB     t,POP,t4
        ADD     k,k,t
        LDB     t,POP,t5
        ADD     k,k,t
        LDB     t,POP,t6
        ADD     k,k,t
        LDB     t,POP,t7
        ADD     k,k,t
        LDB     t,POP,t8
        ADD     k,k,t

        LDB     t,GRAY,k

        % store result pixel
        SET     p,GRAYMAP
        MUL     t2,i,nblocks
        ADD     p,p,t2
        ADD     p,p,j
        STB     t,p,0

        INCL    j,1
        JMP     ColLp

NextRow INCL    i,1
        JMP     RowLp

Done    TRAP    0,Halt,0

Each output pixel is written exactly once because the loops partition the image into disjoint $8 \times 8$ blocks indexed by $(i,j)$. Each $k$ is computed solely from the corresponding block bytes, and each byte contributes exactly one lookup into $\mathrm{POP}$, so the total popcount is correct by definition of $\mathrm{POP}$. The gray level follows from a single lookup into $\mathrm{GRAY}$, which encodes the required function of $k$. ∎