Involution Calculator

Introduction

Involution is a common transformation in mathematical contests. However, it can be difficult to visualize. Unlike the transformations typically taught in high school, an involution can produce an image that looks completely different from the original—without any apparent similarity.

To some extent, you can imagine involution as follows: First, place a ball at the center of the transformation. Then, project the original image onto the north pole of the ball. Next, position a new plane parallel to the original image at the north pole and project the image back through the south pole of the ball.

In the following program, I use the spng library to decode a PNG image, scale it up, apply the involution transformation, and then encode it back into a PNG file.

Implementation

#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <inttypes.h>
#include <stdlib.h>
#include <stdbool.h>

#include <spng.h>

#define ERR_EXIT(s) do{ perror(s); exit(-1); } while(0);

#define get_pixel(image, row, col) (image + (row * ihdr.width + col) * bytes_per_pixel)
#define get_new_pixel(image, row, col, scale) (image + (row * ihdr.width * scale + col) * bytes_per_pixel)
#define get_used(used, row, col, scale) (used + (row * ihdr.width * scale + col))

int main(int argc, char *argv[]) {
  FILE *picture_file;
  spng_ctx *ctx = NULL;
  unsigned char *image = NULL;
  if (argc < 2) {
    printf("no input file\n");
    printf("Usage: involution [picture name] [inv certer row] [inv center col] [inv prod]\n");
    exit(-1);
  }
  if (argc < 4) {
    printf("miss involution center\n");
    printf("Usage: involution [picture name] [inv certer row] [inv center col] [inv prod]\n");
    exit(-1);
  }
  if (argc < 5) {
    printf("miss involution product\n");
    printf("Usage: involution [picture name] [inv certer row] [inv center col] [inv prod]\n");
    exit(-1);
  }

  int inv_center_row = atoi(argv[2]);
  int inv_center_col = atoi(argv[3]);
  double inv_prod = atof(argv[4]);
  printf("Involution center: (%d, %d)\n", inv_center_row, inv_center_col);

  picture_file = fopen(argv[1], "rb");
  if (picture_file == NULL) {
    ERR_EXIT("cannot open the file");
  }
  ctx = spng_ctx_new(0);
  if (ctx == NULL) {
    ERR_EXIT("ctx new failed");
  }
  spng_set_crc_action(ctx, SPNG_CRC_USE, SPNG_CRC_USE);
  const size_t limit = 1024 * 1024 * 1024;
  spng_set_chunk_limits(ctx, limit, limit);
  spng_set_png_file(ctx, picture_file);
  struct spng_ihdr ihdr;
  int ret = spng_get_ihdr(ctx, &ihdr);
  if (ret != 0) {
    ERR_EXIT("get ihdr failed");
  }
  printf("width: %u\n"
    "height: %u\n"
    "bit depth: %u\n"
    "color type: %u\n",
    ihdr.width, ihdr.height, ihdr.bit_depth, ihdr.color_type);

  struct spng_plte plte = {0};
  ret = spng_get_plte(ctx, &plte);
  if (ret != 0 && ret != SPNG_ECHUNKAVAIL) {
    fprintf(stderr, "%s\n", spng_strerror(ret));
    ERR_EXIT("get plte error");
  }
  if (ret == 0) {
    printf("plaette entries: %u\n", plte.n_entries);
  }

  size_t image_size, image_width;
  int fmt = SPNG_FMT_PNG;
  if (ihdr.color_type == SPNG_COLOR_TYPE_INDEXED) fmt = SPNG_FMT_RGB8;
  ret = spng_decoded_image_size(ctx, fmt, &image_size);
  if (ret != 0) {
    ERR_EXIT("image size decode error");
  }
  image = malloc(image_size);
  if (image == NULL) {
    ERR_EXIT("memory allocation failed");
  }
  image_size = 4 * ihdr.width * ihdr.height;
  ret = spng_decode_image(ctx, image, image_size, SPNG_FMT_RGBA8, 0);
  if (ret != 0) {
    fprintf(stderr, "%s\n", spng_strerror(ret));
    ERR_EXIT("image decode error");
  }

  int scale = 20;
  if (inv_center_row < 0 || inv_center_col < 0 ||
      inv_center_col >= ihdr.width * scale || inv_center_row >= ihdr.height * scale) {
    ERR_EXIT("invalid inv center");
  }
  int bytes_per_pixel = 4;  // RGBA
  unsigned char *new_image = malloc(image_size * scale * scale);
  struct spng_ihdr new_ihdr = ihdr;
  new_ihdr.width *= scale;
  new_ihdr.height *= scale;
  for (int i = 0; i < ihdr.height; ++i) {
    for (int j = 0; j < ihdr.width; ++j) {
      for (int k = 0; k < scale; ++k) {
        for (int l = 0; l < scale; ++l) {
          unsigned char *new_pixel = (new_image +
            ((i * scale + k) * (ihdr.width * scale) + j * scale + l) *
              bytes_per_pixel);
          for (int m = 0; m < bytes_per_pixel; ++m) {
            new_pixel[m] = get_pixel(image, i, j)[m];
          }
        }
      }
    }
  }

  bool *used = calloc(image_size * scale * scale, sizeof(unsigned char));
  for (int i = 0; i < ihdr.height * scale; ++i) {
    for (int j = 0; j < ihdr.width * scale; ++j) {
      if (i == inv_center_row && j == inv_center_col) {
        continue;
      }
      unsigned char *pixel = get_new_pixel(new_image, i, j, scale);
      int dr = inv_center_row - i, dc = inv_center_col - j;
      double delta_len = sqrt(dr * dr + dc * dc);
      double new_len = inv_prod / delta_len;
      dr *= new_len / delta_len;
      dc *= new_len / delta_len;
      int newr = inv_center_row + dr, newc = inv_center_col + dc;
      if (newr < 0 || newr >= ihdr.height * scale || newc < 0 || newc >= ihdr.width * scale) {
        continue;
      }
      if (!*get_used(used, i, j, scale) && !*get_used(used, newr, newc, scale)) {
        *get_used(used, i, j, scale) = true;
        *get_used(used, newr, newc, scale) = true;
        unsigned char *new_pixel = get_new_pixel(new_image, newr, newc, scale);
        unsigned char tp[4];
        for (int k = 0; k < bytes_per_pixel; ++k) {
          tp[k] = pixel[k];
        }
        for (int k = 0; k < bytes_per_pixel; ++k) {
          pixel[k] = new_pixel[k];
        }
        for (int k = 0; k < bytes_per_pixel; ++k) {
          new_pixel[k] = tp[k];
        }
      } else if (!*get_used(used, i, j, scale)) {
        pixel[0] = pixel[1] = pixel[2] = pixel[3] = 255;
      }
    }
  }

  FILE *out_file = fopen("output.png", "wb");
  if (out_file == NULL) {
    ERR_EXIT("Failed to create output file\n");
  }

  // Initialize encoder context
  spng_ctx *out_ctx = spng_ctx_new(SPNG_CTX_ENCODER);
  if (out_ctx == NULL) {
    fprintf(stderr, "Failed to create encoder context\n");
    fclose(out_file);
    return 1;
  }

  spng_set_png_file(out_ctx, out_file);
  new_ihdr.bit_depth = 8;
  new_ihdr.color_type = SPNG_COLOR_TYPE_TRUECOLOR_ALPHA;
  new_ihdr.compression_method = 0;
  new_ihdr.filter_method = 0;
  new_ihdr.interlace_method = 0;
  ret = spng_set_ihdr(out_ctx, &new_ihdr);
  if (ret != 0) {
    ERR_EXIT("ihdr set failed")
  }
  ret = spng_encode_image(out_ctx, new_image, image_size * scale * scale,
    SPNG_FMT_PNG, 0);
  if (ret != 0) {
    fprintf(stderr, "spng_encode_image error: %s\n", spng_strerror(ret));
    ERR_EXIT("encode error");
  }

  spng_ctx_free(ctx);
  spng_ctx_free(out_ctx);
  fclose(out_file);
  free(image);
  free(new_image);
  free(used);
}