rotate.c

#include <stdio.h>
#include <inttypes.h>
#include <limits.h>
#include <string.h>
#include <assert.h>

// Rotate a monochrome bitmap in Microsoft BMP format by pi/2.
//
// Monochrome BMP format:
//   * Pixels in big-endian order: Bit 7 of byte 0 is bottom-left-most.
//   * Rest of first row bytes follow, left to right.
//   * Rest or rows follow, bottom to top.
//
// The image is guaranteed square with edge size a multiple of 64.

// For speed, rotate "bit squares" of size 2^k for k = 6 with a fast
// algorithm and blt bit squares to their correct position in the image.
//
// Fast bit square rotation:
// Use three shear transformations - left, down, left - modulo the
// row size. Shear left is simple row rotation: row i is rotated
// i places left. Shear down is column shifting: col j rotates j
// rows downward. For this, make k passes, rotating blocks of bits 
// with size halved for each pass.
//
// Caveat: BMP's big-endiean rep must be converted to little-endian for
// simple rotation to work for shear. Within a bit square row, byte[0]'s
// msb must shift right into byte[1]'s lsb. For speed, we'll reverse
// bits AND bytes within a bit square row while doing this conversion.

// Set up bit square. Rows correspond to an int type.

typedef uint64_t BSQ_ROW;
#define LOG_BSQ_ROW_BITS 6
#define BSQ_ROW_BITS (1 << LOG_BSQ_ROW_BITS)
#define BSQ_ROW_BITS_MASK (~(~0u << LOG_BSQ_ROW_BITS))

// Masks for blocks within bit square rows.
static const BSQ_ROW block_masks[] = {
  0x5555555555555555,
  0x3333333333333333,
  0x0f0f0f0f0f0f0f0f,
  0x00ff00ff00ff00ff,
  0x0000ffff0000ffff,
  0x00000000ffffffff,
};

// Row rotations, important for speed.
#ifdef __clang__
  #define rotate_left __builtin_rotateleft64
#else
  static BSQ_ROW rotate_left(BSQ_ROW row, unsigned n) {
    return (row << n) | (row >> (BSQ_ROW_BITS_MASK & (BSQ_ROW_BITS - n)));
  }
#endif

static void shear_down(BSQ_ROW *a) {
  // Make passes shifting decreasing-sized blocks within rows.
  for (int i_mask = LOG_BSQ_ROW_BITS - 1, shift = BSQ_ROW_BITS / 2, n_blocks = 2;
       i_mask >= 0;
       --i_mask, shift /= 2, n_blocks *= 2) {
    // Iterate over rows within blocks.
    for (int row = 0; row < shift; ++row) {
      // Iterate over blocks, shifting a cycle of rows.
      BSQ_ROW src = a[row];
      for (int blk = 0, i_dst = shift + row;
           blk < n_blocks;
           ++blk, i_dst = (i_dst + shift) & BSQ_ROW_BITS_MASK) {
        BSQ_ROW dst = a[i_dst];
        // Write masked bits from source while letting unmasked bits as-is.
        a[i_dst] = (a[i_dst] & ~block_masks[i_mask]) | (src & block_masks[i_mask]);
        src = dst;
      }
    }
  }
}

static void shear_left(BSQ_ROW *a) {
  for (int i = 1; i < BSQ_ROW_BITS; ++i) a[i] = rotate_left(a[i], i);
}

void rotate_clockwise(BSQ_ROW *a) {
  shear_left(a);
  shear_down(a);
  shear_left(a);
}

// Test frame.

typedef struct {
  uint8_t *pixels;
  int size;
} BMP;

#define BMP_PIXEL_BYTE(Bmp, X, Y) (Bmp->pixels[(Y) * (Bmp->size / 8) + (X) / 8])

// Copy the given bit square to the given BMP so that its lower left corner
// is at pixel (x * 2^k, y * 2^k).
void copy_bit_square_to_bmp(BSQ_ROW *rows, BMP *bmp, int x, int y) {
  for (int i = 0; i < BSQ_ROW_BITS; ++i) {
    BSQ_ROW row = __builtin_bitreverse64(bmp->pixels[i]);
    memcpy(&BMP_PIXEL_BYTE(bmp, x * BSQ_ROW_BITS, y * BSQ_ROW_BITS + i), &row, sizeof(BSQ_ROW));
  }
}

#define LOW8(X) ((uint8_t) (X))
#define UINT16_BYTES(X)  LOW8(X), LOW8(X >> 8)
#define UINT32_BYTES(X)  LOW8(X), LOW8(X >> 8), LOW8(X >> 16), LOW8(X >> 24)

void write_bmp(char *file_name, BSQ_ROW *rows, int rows_per_scanline) {
  const int total_header_size = 54;
  uint32_t rows_in_image = rows_per_scanline * BSQ_ROW_BITS * rows_per_scanline;
  uint32_t file_size = total_header_size + sizeof(BSQ_ROW) * rows_in_image;
  uint32_t pixel_data_offset = total_header_size + 8;
  uint8_t hdr[] = {
    'B', 'M', // Microsoft magic number
    UINT32_BYTES(file_size),
    UINT32_BYTES(0), // reserved
    UINT32_BYTES(pixel_data_offset),
  };
  uint32_t size = rows_per_scanline * BSQ_ROW_BITS;
  uint8_t file_hdr[] = {
    UINT32_BYTES(40),   // size of this header
    UINT32_BYTES(size), // width
    UINT32_BYTES(size), // height
    UINT16_BYTES(1),    // color planes
    UINT16_BYTES(1),    // bits per pixel
    UINT32_BYTES(0),    // compression/none
    UINT32_BYTES(0),    // compressed size
    UINT32_BYTES(10000),// horizontal resolution pixels/m
    UINT32_BYTES(10000),// vertical resolution pixels/m
    UINT32_BYTES(2),    // actually used colors
    UINT32_BYTES(0),    // important color/all
  };
  uint8_t color_tbl[] = {
    255, 255, 255, // RGB for 0
    0,             // reserved
    0, 0, 0,       // RGB for 1
    0,             // reserved
  };
  FILE *f = fopen(file_name, "wb");
  fwrite(hdr, sizeof hdr, 1, f);
  fwrite(file_hdr, sizeof file_hdr, 1, f);
  fwrite(color_tbl, sizeof color_tbl, 1, f);
  uint8_t copy[rows_in_image * sizeof(BSQ_ROW)];
  memset(copy, 0, rows_in_image * sizeof(BSQ_ROW));
  for (int i = 0; i < 32; ++i) copy[8 * i] = 0x40;
  memcpy(copy, rows, sizeof copy);
  for (int i = 0; i < sizeof copy; ++i) copy[i] = __builtin_bitreverse8(copy[i]);
  fwrite(copy, sizeof(BSQ_ROW), rows_in_image, f);
  fclose(f);
}

int main(void) {
  uint64_t b[64] = {0};
  for (int i = 0, d = 2; i < 64; i += d, d *= 2) b[i] = 0xff00f0f0aaaa0000;
  for (int i = 0; i < 64; ++i) printf("%016llx\n", b[i]); printf("\n");
  write_bmp("original.bmp", b, 1);
  rotate_clockwise(b);
  for (int i = 0; i < 64; ++i) printf("%016llx\n", b[i]);
  write_bmp("rotated.bmp", b, 1);
  return 0;
}