transpose8.c.txt

// Programs for computing the transpose of an 8x8 bit matrix.
// Max line length is 57 (sometimes), to fit in hacker.book.
// This has been tested on both AIX/xlc and Windows/gcc, and
// so is believed to be independent of endian mode and whether
// char is by default signed or unsigned.
#include <stdio.h>
#include <string.h>

/* All the functions herein are for transposing an 8x8 bit matrix, that
is presumed to be a block of a larger matrix of size m x n bytes. Brief
description of the functions:

transpose8vn:    Very naive method, directly places one bit at a time.
transpose8b64:   Basic shifting method that directly places a few bits at a time.
transpose8b64c:  Compact version of 8b64; uses a for-loop.
transpose8bS64:  Like 8b64, but uses GLS's bit swapping device.
transpose8r64:   Basic recursive method (the main point of this comparison study).
transpose8rS64:  Like 8r64, but uses GLS's bit swapping device.
transpose8b32, ..., 8rS32: Above four coded for a 32-bit machine.
transpose8rSr32: Like 8rS32 but done in reverse (coarse to fine granularity). */


/* -------------------------- transpose8vn -------------------------- */

/* This is the very naive method, that directly places one bit at a
time. This may be too naive to include in the book (i.e., maybe we
should take this out if there should be another edition).
   This is equally suitable (or unsuitable, if you wish) for a 32- or a
64-bit machine.
   Instruction counts for the calculation part:
   62 ANDs
   56 shifts
   56 ORs (or ADDs or XORs)
   --
  174 total (very naive method, placing one bit at a time) */

void transpose8vn(unsigned char A[8], int m, int n, unsigned char B[8]) {
   unsigned char a0, a1, a2, a3, a4, a5, a6, a7,
                 b0, b1, b2, b3, b4, b5, b6, b7;

   // Load the array into eight one-byte variables.

   a0 = A[0];  a1 = A[m];  a2 = A[2*m];  a3 = A[3*m];
   a4 = A[4*m];  a5 = A[5*m];  a6 = A[6*m];  a7 = A[7*m];

   b0 = (a0 & 128)    | (a1 & 128)/2  | (a2 & 128)/4  | (a3 & 128)/8 |
        (a4 & 128)/16 | (a5 & 128)/32 | (a6 & 128)/64 | (a7      )/128;
   b1 = (a0 &  64)*2  | (a1 &  64)    | (a2 &  64)/2  | (a3 &  64)/4 |
        (a4 &  64)/8  | (a5 &  64)/16 | (a6 &  64)/32 | (a7 &  64)/64;
   b2 = (a0 &  32)*4  | (a1 &  32)*2  | (a2 &  32)    | (a3 &  32)/2 |
        (a4 &  32)/4  | (a5 &  32)/8  | (a6 &  32)/16 | (a7 &  32)/32;
   b3 = (a0 &  16)*8  | (a1 &  16)*4  | (a2 &  16)*2  | (a3 &  16)   |
        (a4 &  16)/2  | (a5 &  16)/4  | (a6 &  16)/8  | (a7 &  16)/16;
   b4 = (a0 &   8)*16 | (a1 &   8)*8  | (a2 &   8)*4  | (a3 &   8)*2 |
        (a4 &   8)    | (a5 &   8)/2  | (a6 &   8)/4  | (a7 &   8)/8;
   b5 = (a0 &   4)*32 | (a1 &   4)*16 | (a2 &   4)*8  | (a3 &   4)*4 |
        (a4 &   4)*2  | (a5 &   4)    | (a6 &   4)/2  | (a7 &   4)/4;
   b6 = (a0 &   2)*64 | (a1 &   2)*32 | (a2 &   2)*16 | (a3 &   2)*8 |
        (a4 &   2)*4  | (a5 &   2)*2  | (a6 &   2)    | (a7 &   2)/2;
   b7 = (a0      )*128| (a1 &   1)*64 | (a2 &   1)*32 | (a3 &   1)*16|
        (a4 &   1)*8  | (a5 &   1)*4  | (a6 &   1)*2  | (a7 &   1);

   B[0] = b0;    B[n] = b1;    B[2*n] = b2;  B[3*n] = b3;
   B[4*n] = b4;  B[5*n] = b5;  B[6*n] = b6;  B[7*n] = b7;
}

/* The above executes in 174 instructions (just the calculation part).
62 ANDs, 56 shifts, and 56 ORs. */


/* ------------------------- transpose8b64 -------------------------- */

/* transpose8b64 directly places the bits in the target array. It uses
64-bit quantities, which makes it easy to understand. It can be easily
translated for execution on a 32-bit machine, either by hand or by
letting the compiler do it, if your compiler supports 64-bit integers on
a 32-bit machine.
   It is based on the observation that the bits in the 64-bit doubleword
all move either 0, 7, 14, 21, 28, 35, 42, or 49 positions to the left or
right. This is illustrated by the diagram below. Each digit, letter, $,
or period represents a single bit in a 64-bit word. A dash represents a
0, resulting from the shift instructions.
   Looking at the Input and Output lines, the bit denoted by the
character '0' does not move, '1' moves 7 positions to the right, '2'
moves 14 positions to the right, etc.
   Note: Rotate shifts do not help. That is, they do not move any
additional bits to their output positions.

Input x: 01234567 89abcdef ghijklmn opqrstuv wxyzABCD EFGHIJKL MNOPQRST UVWXYZ$.
Output:  08gowEMU 19hpxFNV 2aiqyGOW 3bjrzHPX 4cksAIQY 5dltBJRZ 6emuCKS$ 7fnvDLT.

x:       01234567 89abcdef ghijklmn opqrstuv wxyzABCD EFGHIJKL MNOPQRST UVWXYZ$.
x <<  7: 789abcde fghijklm nopqrstu vwxyzABC DEFGHIJK LMNOPQRS TUVWXYZ$ .-------
x << 14: efghijkl mnopqrst uvwxyzAB CDEFGHIJ KLMNOPQR STUVWXYZ $.------ --------
x << 21: lmnopqrs tuvwxyzA BCDEFGHI JKLMNOPQ RSTUVWXY Z$.----- -------- --------
x << 28: stuvwxyz ABCDEFGH IJKLMNOP QRSTUVWX YZ$.---- -------- -------- --------
x << 35: zABCDEFG HIJKLMNO PQRSTUVW XYZ$.--- -------- -------- -------- --------
x << 42: GHIJKLMN OPQRSTUV WXYZ$.-- -------- -------- -------- -------- --------
x << 49: NOPQRSTU VWXYZ$.- --------- ------- -------- -------- -------- --------
x >>  7: -------0 12345678 9abcdefg hijklmno pqrstuvw xyzABCDE FGHIJKLM NOPQRSTU
x >> 14: -------- ------01 23456789 abcdefgh ijklmnop qrstuvwx yzABCDEF GHIJKLMN
x >> 21: -------- -------- -----012 3456789a bcdefghi jklmnopq rstuvwxy zABCDEFG
x >> 28: -------- -------- -------- ----0123 456789ab cdefghij klmnopqr stuvwxyz
x >> 35: -------- -------- -------- -------- ---01234 56789abc defghijk lmnopqrs
x >> 42: -------- -------- -------- ----------------- -0123456 789abcde fghijklm
x >> 49: -------- -------- -------- ----------------- -------- 01234567 89abcdef

The function below positions some of the bits with an expression of the
form (x & mask) << s, and some with an expression of the form (x >> s) &
mask. This is reduces the number of distinct masks that are required.
   Instruction counts for the calculation part, for a 64-bit machine:
   14 shifts
   15 ANDs
   14 ORs (or ADDs or XORs)
    9 Mask generation (4 for the first and 1 for each subsequent
      one, except the two smallest masks can be immediate fields).
   --
   52 total (64-bit machine, direct placement) */

void transpose8b64(unsigned char A[8], int m, int n,
                   unsigned char B[8]) {
   unsigned long long x, y;
   int i;

   for (i = 0; i <= 7; i++)     // Load 8 bytes from the
      x = x << 8 | A[m*i];      // input array and pack
                                // them into x.

   y =  x & 0x8040201008040201LL        |
       (x & 0x0080402010080402LL) <<  7 |
       (x & 0x0000804020100804LL) << 14 |
       (x & 0x0000008040201008LL) << 21 |
       (x & 0x0000000080402010LL) << 28 |
       (x & 0x0000000000804020LL) << 35 |
       (x & 0x0000000000008040LL) << 42 |
       (x & 0x0000000000000080LL) << 49 |
       (x >>  7) & 0x0080402010080402LL |
       (x >> 14) & 0x0000804020100804LL |
       (x >> 21) & 0x0000008040201008LL |
       (x >> 28) & 0x0000000080402010LL |
       (x >> 35) & 0x0000000000804020LL |
       (x >> 42) & 0x0000000000008040LL |
       (x >> 49) & 0x0000000000000080LL;

   for (i = 7; i >= 0; i--) {   // Store result into
      B[n*i] = y; y = y >> 8;}  // output array B.
}


/* ------------------------- transpose8b64c ------------------------- */

/* This is a compact version of transpose8b64, ca. 75 instructions for
the calculation part. */

void transpose8b64c(unsigned char A[8], int m, int n,
                    unsigned char B[8]) {
   unsigned long long x, y, mask;
   int i, s;

   for (i = 0; i <= 7; i++)     // Load 8 bytes from the
      x = x << 8 | A[m*i];      // input array and pack
                                // them into x.
   mask = 0x8040201008040201LL;
   y = x & mask;

   for (s = 7; s <= 49; s = s + 7) {
      mask = mask >> 8;
      y = y | ((x & mask) << s) | ((x >> s) & mask);
   }

   for (i = 7; i >= 0; i--) {   // Store result into
      B[n*i] = y; y = y >> 8;}  // output array B.
}

/* ------------------------- transpose8bS64 ------------------------- */

/* This is transpose8b64 but using the GLS method of bit field swapping.
   Instruction counts for the calculation part:
    7 ANDs
   21 XORs
   14 shifts
    8 Mask generation (many can be generated from earlier masks)
   --
   50 total (direct placement method for a 64-bit machine, using GLS's bit swapping) */

void transpose8bS64(unsigned char A[8], int m, int n,
                    unsigned char B[8]) {
   unsigned long long x, t;
   int i;

   for (i = 0; i <= 7; i++)     // Load 8 bytes from the
      x = x << 8 | A[m*i];      // input array and pack
                                // them into x.

   t = (x ^ (x >>  7)) & 0x0080402010080402LL;
   x = x ^ t ^ (t <<  7);
   t = (x ^ (x >> 14)) & 0x0000804020100804LL;
   x = x ^ t ^ (t << 14);
   t = (x ^ (x >> 21)) & 0x0000008040201008LL;
   x = x ^ t ^ (t << 21);
   t = (x ^ (x >> 28)) & 0x0000000080402010LL;
   x = x ^ t ^ (t << 28);
   t = (x ^ (x >> 35)) & 0x0000000000804020LL;
   x = x ^ t ^ (t << 35);
   t = (x ^ (x >> 42)) & 0x0000000000008040LL;
   x = x ^ t ^ (t << 42);
   t = (x ^ (x >> 49)) & 0x0000000000000080LL;
   x = x ^ t ^ (t << 49);

   for (i = 7; i >= 0; i--) {   // Store result into
      B[n*i] = x; x = x >> 8;}  // output array B.
}


/* ------------------------- transpose8r64 -------------------------- */

/* transpose8r64 is the basic recursive method for a 64-bit machine.
This function positions some of the bits with an expression of the
form (x & mask) << s, and some with an expression of the form (x >> s) &
mask. This is reduces the number of distinct masks that are required.
   Instruction counts for the calculation part, for a 64-bit machine:
    6 shifts
    9 ANDs
    6 ORs (or ADDs or XORs)
   17 Mask generation
   --
   38 total (64-bit machine, basic recursive method) */

void transpose8r64(unsigned char A[8], int m, int n,
                   unsigned char B[8]) {
   unsigned long long x;
   int i;

   for (i = 0; i <= 7; i++)     // Load 8 bytes from the
      x = x << 8 | A[m*i];      // input array and pack
                                // them into x.

   x =  x & 0xAA55AA55AA55AA55LL        |
       (x & 0x00AA00AA00AA00AALL) <<  7 |
       (x >> 7) & 0x00AA00AA00AA00AALL;
   x =  x & 0xCCCC3333CCCC3333LL        |
       (x & 0x0000CCCC0000CCCCLL) << 14 |
       (x >> 14) & 0x0000CCCC0000CCCCLL;
   x =  x & 0xF0F0F0F00F0F0F0FLL        |
       (x & 0x00000000F0F0F0F0LL) << 28 |
       (x >> 28) & 0x00000000F0F0F0F0LL;

   for (i = 7; i >= 0; i--) {   // Store result into
      B[n*i] = x; x = x >> 8;}  // output array B.
}


/* ------------------------- transpose8rS64 -------------------------- */

/* This is transpose8r64 but using the GLS method of bit field swapping.
   Instruction counts for the calculation part, for a 64-bit machine:
    6 shifts
    3 ANDs
    9 XORs
    8 Mask generation
   --
   26 total (64-bit machine, recursive method with GLS bit swapping) */

void transpose8rS64(unsigned char A[8], int m, int n,
                    unsigned char B[8]) {
   unsigned long long x, t;
   int i;

   for (i = 0; i <= 7; i++)     // Load 8 bytes from the
      x = x << 8 | A[m*i];      // input array and pack
                                // them into x.

   t = (x ^ (x >> 7)) & 0x00AA00AA00AA00AALL;
   x = x ^ t ^ (t << 7);
   t = (x ^ (x >> 14)) & 0x0000CCCC0000CCCCLL;
   x = x ^ t ^ (t << 14);
   t = (x ^ (x >> 28)) & 0x00000000F0F0F0F0LL;
   x = x ^ t ^ (t << 28);

   for (i = 7; i >= 0; i--) {   // Store result into
      B[n*i] = x; x = x >> 8;}  // output array B.
}


/* ------------------------- transpose8b32 -------------------------- */

/* This is transpose8b64 adapted to a 32-bit machine more-or-less
mechanically. Because of the double-length shifts, some of the terms of
the from (x & mask) << n were changed to (x << n) & mask'. Then, for
consistency, all were changed to that form.
   Instruction counts for the calculation part, for a 32-bit machine:
   26 shifts
   22 ANDs
   26 ORs (or ADDs or XORs)
   10 Mask generation (many can be generated from earlier masks)
   --
   84 total (32-bit machine, direct placement) */

void transpose8b32(unsigned char A[8], int m, int n,
                   unsigned char B[8]) {
   unsigned int xh, xl, yh, yl;         // x high, low, etc.

   // Load the array and pack it into xh and xl.

   xh = (A[0]<<24)   | (A[m]<<16)   | (A[2*m]<<8) | A[3*m];
   xl = (A[4*m]<<24) | (A[5*m]<<16) | (A[6*m]<<8) | A[7*m];

   yh = xh                   & 0x80402010 |
       (xh <<  7 | xl >> 25) & 0x40201008 |
       (xh << 14 | xl >> 18) & 0x20100804 |
       (xh << 21 | xl >> 11) & 0x10080402 |
       (xh << 28 | xl >>  4) & 0x08040201 |
       (           xl <<  3) & 0x04020100 |
       (           xl << 10) & 0x02010000 |
       (           xl << 17) & 0x01000000 |
       (xh >>  7           ) & 0x00804020 |
       (xh >> 14           ) & 0x00008040 |
       (xh >> 21           ) & 0x00000080;

   yl = xl                   & 0x08040201 |
       (xl <<  7           ) & 0x04020100 |
       (xl << 14           ) & 0x02010000 |
       (xl << 21           ) & 0x01000000 |
       (xh << 25 | xl >>  7) & 0x10080402 |
       (xh << 18 | xl >> 14) & 0x20100804 |
       (xh << 11 | xl >> 21) & 0x40201008 |
       (xh <<  4           ) & 0x80402010 |
       (xh >>  3           ) & 0x00804020 |
       (xh >> 10           ) & 0x00008040 |
       (xh >> 17           ) & 0x00000080;

   B[0]=yh>>24;    B[n]=yh>>16;    B[2*n]=yh>>8;  B[3*n]=yh;
   B[4*n]=yl>>24;  B[5*n]=yl>>16;  B[6*n]=yl>>8;  B[7*n]=yl;
}


/* ------------------------- transpose8bS32 ------------------------- */

/* This is transpose8b32 but using the GLS method of bit field swapping.
   Instruction counts for the calculation part, for a 32-bit machine:
   27 shifts
   10 ANDs
    6 ORs (or ADDs or XORs)
   31 XORs
    7 Mask generation (many can be generated from earlier masks)
   --
   81 total (32-bit machine, direct placement with GLS bit swapping) */

void transpose8bS32(unsigned char A[8], int m, int n,
                    unsigned char B[8]) {
   unsigned int xh, xl, th, tl;         // x high, low, etc.

   // Load the array and pack it into xh and xl.

   xh = (A[0]<<24)   | (A[m]<<16)   | (A[2*m]<<8) | A[3*m];
   xl = (A[4*m]<<24) | (A[5*m]<<16) | (A[6*m]<<8) | A[7*m];

   th = (xh ^ (xh >> 7)) & 0x00804020;
   tl = (xl ^ (xl >> 7 | xh << 25)) & 0x10080402;
   xh = xh ^ th ^ (th << 7 | tl >> 25);
   xl = xl ^ tl ^ (tl << 7);

   th = (xh ^ (xh >> 14)) & 0x00008040;
   tl = (xl ^ (xl >> 14 | xh << 18)) & 0x20100804;
   xh = xh ^ th ^ (th << 14 | tl >> 18);
   xl = xl ^ tl ^ (tl << 14);

   th = (xh ^ (xh >> 21)) & 0x00000080;
   tl = (xl ^ (xl >> 21 | xh << 11)) & 0x40201008;
   xh = xh ^ th ^ (th << 21 | tl >> 11);
   xl = xl ^ tl ^ (tl << 21);

   tl = (xl ^ (xh << 4)) & 0x80402010;
   xh = xh ^ (tl >> 4);
   xl = xl ^ tl ^ (tl << 28);

   tl = (xl ^ (xh >> 3)) & 0x00804020;
   xh = xh ^ (tl << 3);
   xl = xl ^ tl;

   tl = (xl ^ (xh >> 10)) & 0x00008040;
   xh = xh ^ (tl << 10);
   xl = xl ^ tl;

   tl = (xl ^ (xh >> 17)) & 0x00000080;
   xh = xh ^ (tl << 17);
   xl = xl ^ tl;

   B[0]=xh>>24;    B[n]=xh>>16;    B[2*n]=xh>>8;  B[3*n]=xh;
   B[4*n]=xl>>24;  B[5*n]=xl>>16;  B[6*n]=xl>>8;  B[7*n]=xl;
}


/* ------------------------- transpose8r32 -------------------------- */

/* Next is the basic "recursive" method. Decided not to include this in
HD. It's too similar to transpose8rS32, which is a little better (probably).
   Instruction counts for the calculation part:
   16 ANDs
   10 shifts
   10 ORs
    9 mask generation
   --
   45 total (recursive method, direct placement at each step) */

void transpose8r32(unsigned char A[8], int m, int n,
                   unsigned char B[8]) {
   unsigned x, y, t;

   // Load the array and pack it into x and y.

   x = (A[0]<<24)   | (A[m]<<16)   | (A[2*m]<<8) | A[3*m];
   y = (A[4*m]<<24) | (A[5*m]<<16) | (A[6*m]<<8) | A[7*m];

   x = (x & 0xAA55AA55) | ((x & 0x00AA00AA) << 7) |
       ((x >> 7) & 0x00AA00AA);
   y = (y & 0xAA55AA55) | ((y & 0x00AA00AA) << 7) |
       ((y >> 7) & 0x00AA00AA);

   x = (x & 0xCCCC3333) | ((x & 0x0000CCCC) << 14) |
       ((x >> 14) & 0x0000CCCC);
   y = (y & 0xCCCC3333) | ((y & 0x0000CCCC) << 14) |
       ((y >> 14) & 0x0000CCCC);

   t = (x & 0xF0F0F0F0) | ((y >> 4) & 0x0F0F0F0F);
   y = ((x << 4) & 0xF0F0F0F0) | (y & 0x0F0F0F0F);
   x = t;

   B[0]=x>>24;    B[n]=x>>16;    B[2*n]=x>>8;  B[3*n]=x;
   B[4*n]=y>>24;  B[5*n]=y>>16;  B[6*n]=y>>8;  B[7*n]=y;
}


/* ------------------------- transpose8rS32 ------------------------- */

/* This is transpose8r32 but using the GLS method of bit field swapping.
   Instruction counts for the calculation part:
    8 ANDs
   12 XORs
   10 shifts
    2 ORs
    5 mask generation
   --
   37 total (recursive method using GLS's bit swapping) */

void transpose8rS32(unsigned char A[8], int m, int n,
                 unsigned char B[8]) {
   unsigned x, y, t;

   // Load the array and pack it into x and y.

   x = (A[0]<<24)   | (A[m]<<16)   | (A[2*m]<<8) | A[3*m];
   y = (A[4*m]<<24) | (A[5*m]<<16) | (A[6*m]<<8) | A[7*m];

   t = (x ^ (x >> 7)) & 0x00AA00AA;  x = x ^ t ^ (t << 7);
   t = (y ^ (y >> 7)) & 0x00AA00AA;  y = y ^ t ^ (t << 7);

   t = (x ^ (x >>14)) & 0x0000CCCC;  x = x ^ t ^ (t <<14);
   t = (y ^ (y >>14)) & 0x0000CCCC;  y = y ^ t ^ (t <<14);

   t = (x & 0xF0F0F0F0) | ((y >> 4) & 0x0F0F0F0F);
   y = ((x << 4) & 0xF0F0F0F0) | (y & 0x0F0F0F0F);
   x = t;

   B[0]=x>>24;    B[n]=x>>16;    B[2*n]=x>>8;  B[3*n]=x;
   B[4*n]=y>>24;  B[5*n]=y>>16;  B[6*n]=y>>8;  B[7*n]=y;
}


/* ------------------------ transpose8rSr32 ------------------------- */

/* This is transpose8rS32 done "backwards" (coarse to fine granularity).
Why? Just to show that this works.
   Instruction counts for the calculation part:
    8 ANDs
   12 XORs
   10 shifts
    2 ORs
    5 mask generation
   --
   37 total (recursive method in reverse, using GLS's bit swapping) */

void transpose8rSr32(unsigned char A[8], int m, int n,
                 unsigned char B[8]) {
   unsigned x, y, t;

   // Load the array and pack it into x and y.

   x = (A[0]<<24)   | (A[m]<<16)   | (A[2*m]<<8) | A[3*m];
   y = (A[4*m]<<24) | (A[5*m]<<16) | (A[6*m]<<8) | A[7*m];

   t = (x & 0xF0F0F0F0) | ((y >> 4) & 0x0F0F0F0F);
   y = ((x << 4) & 0xF0F0F0F0) | (y & 0x0F0F0F0F);
   x = t;

   t = (x ^ (x >>14)) & 0x0000CCCC;  x = x ^ t ^ (t <<14);
   t = (y ^ (y >>14)) & 0x0000CCCC;  y = y ^ t ^ (t <<14);

   t = (x ^ (x >> 7)) & 0x00AA00AA;  x = x ^ t ^ (t << 7);
   t = (y ^ (y >> 7)) & 0x00AA00AA;  y = y ^ t ^ (t << 7);

   B[0]=x>>24;    B[n]=x>>16;    B[2*n]=x>>8;  B[3*n]=x;
   B[4*n]=y>>24;  B[5*n]=y>>16;  B[6*n]=y>>8;  B[7*n]=y;
}

// ----------------------------- error ---------------------------------

int errors;
void error(unsigned char T[8], unsigned char R[8]) {
   errors = errors + 1;
   printf("Error for test = %02x%02x%02x%02x %02x%02x%02x%02x, got "
      "%02x%02x%02x%02x %02x%02x%02x%02x\n",
      T[0],T[1],T[2],T[3],T[4],T[5],T[6],T[7],
      R[0],R[1],R[2],R[3],R[4],R[5],R[6],R[7]);

}

// ------------------------------ main ---------------------------------

int main() {
   int i, n;
   static unsigned char test[][8] = {
      {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}, {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00},
      {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01}, {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01},
      {0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00}, {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x10},
      {0x00,0x00,0x00,0x02,0x00,0x00,0x00,0x00}, {0x00,0x00,0x00,0x00,0x00,0x00,0x10,0x00},
      {0x00,0x00,0x00,0x04,0x00,0x00,0x00,0x00}, {0x00,0x00,0x00,0x00,0x00,0x10,0x00,0x00},
      {0x00,0x00,0x00,0x08,0x00,0x00,0x00,0x00}, {0x00,0x00,0x00,0x00,0x10,0x00,0x00,0x00},
      {0x55,0x55,0x55,0x55,0x55,0x55,0x55,0x55}, {0x00,0xFF,0x00,0xFF,0x00,0xFF,0x00,0xFF},
      {0xAA,0xAA,0xAA,0xAA,0xAA,0xAA,0xAA,0xAA}, {0xFF,0x00,0xFF,0x00,0xFF,0x00,0xFF,0x00},
      {0x7F,0x3F,0x1F,0x0F,0x07,0x03,0x01,0x00}, {0x00,0x80,0xC0,0xE0,0xF0,0xF8,0xFC,0xFE},
      {0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00}, {0xF0,0xF0,0xF0,0xF0,0xF0,0xF0,0xF0,0xF0},
      {0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF}, {0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F},
      {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF}, {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF},
   };

   unsigned char result[8];
   n = sizeof(test)/8;

   printf("transpose8vn:\n");
   for (i = 0; i < n; i += 2) {
      transpose8vn(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8vn(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8b64:\n");
   for (i = 0; i < n; i += 2) {
      transpose8b64(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8b64(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8b64c:\n");
   for (i = 0; i < n; i += 2) {
      transpose8b64c(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8b64c(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8bS64:\n");
   for (i = 0; i < n; i += 2) {
      transpose8bS64(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8bS64(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8r64:\n");
   for (i = 0; i < n; i += 2) {
      transpose8r64(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8r64(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8rS64:\n");
   for (i = 0; i < n; i += 2) {
      transpose8rS64(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8rS64(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8b32:\n");
   for (i = 0; i < n; i += 2) {
      transpose8b32(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8b32(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8bS32:\n");
   for (i = 0; i < n; i += 2) {
      transpose8bS32(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8bS32(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8r32:\n");
   for (i = 0; i < n; i += 2) {
      transpose8r32(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8r32(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8rS32:\n");
   for (i = 0; i < n; i += 2) {
      transpose8rS32(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8rS32(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   printf("transpose8rSr32:\n");
   for (i = 0; i < n; i += 2) {
      transpose8rSr32(test[i], 1, 1, result);
      if (memcmp((char *)test[i+1], (char *)result, 8) != 0)
         error(test[i], result);

      transpose8rSr32(test[i+1], 1, 1, result);
      if (memcmp((char *)test[i], (char *)result, 8) != 0)
         error(test[i+1], result);
   }

   if (errors == 0)
      printf("Passed all %d cases and their reversals.\n", n/2);
   return 0;
}

/* Summary of instruction counts and operation counts (instruction
counts less those for mask generation) for all the transpose8 functions
above except for transpose8b64c:

        Instructions          Operations
           Machine              Machine
       64-bit  32-bit       64-bit  32-bit
8vn      174     174          174     174      Very naive method
8b        54      84           43      74      Basic direct placement
8bS       50      81           42      74      Above with GLS bit swapping
8r        38      45           21      36      Basic recursive
8rS       26      37           18      32      Above with GLS bit swapping
8rSr              37                   32      8rS in reverse order
*/