#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#define LINEPIX 4096
#define LINEPIY 4096
#define WH 224
#define FAC 1.1 //薄い場合は最も暗い所を黒にしてから更にこの分暗くする

/* ------------------------------------------------------------ */
/* Little endian                                                 */
/* ------------------------------------------------------------ */

static uint16_t read_u16(FILE *fp)
{
  unsigned char b[2];

  if (fread(b, 1, 2, fp) != 2) return 0;
  return (uint16_t)b[0] | ((uint16_t)b[1] << 8);
}

static uint32_t read_u32(FILE *fp)
{
  unsigned char b[4];

  if (fread(b, 1, 4, fp) != 4) return 0;
  return (uint32_t)b[0] | ((uint32_t)b[1] << 8) | ((uint32_t)b[2] << 16) | ((uint32_t)b[3] << 24);
}

static int32_t read_s32(FILE *fp)
{
  return (int32_t)read_u32(fp);
}

/* ------------------------------------------------------------ */
/* Bit field conversion                                          */
/* ------------------------------------------------------------ */

static unsigned char extract_field(uint32_t value, uint32_t mask)
{
  int shift = 0;
  int bits = 0;
  uint32_t x;

  if (mask == 0) return 0;
  while ((mask & 1) == 0) {
    mask >>= 1;
    shift++;
  }
  x = (value >> shift) & mask;
  while (mask != 0) {
    bits++;
    mask >>= 1;
  }
  /* Scale to 0--255 */
  return (unsigned char)((x * 255 + ((1U << bits) - 1) / 2) / ((1U << bits) - 1));
}

/* ------------------------------------------------------------ */
/* BMP reader                                                    */
/* ------------------------------------------------------------ */

int read_bmp(const char *filename, unsigned char image[LINEPIY][LINEPIX][3], int *width, int *height)
{
  FILE *fp;
  uint16_t type;
  uint32_t file_size;
  uint32_t pixel_offset;
  uint32_t header_size;
  int32_t w;
  int32_t h;
  uint16_t planes;
  uint16_t bit_count;
  uint32_t compression;
  uint32_t colors_used;
  uint32_t *palette = NULL;
  uint32_t red_mask   = 0;
  uint32_t green_mask = 0;
  uint32_t blue_mask  = 0;
  //uint32_t alpha_mask = 0;
  int top_down;
  int x, y, k, nwh=0, z, zm=255;

  fprintf(stderr,"Read: %s ... ",filename);
  fp = fopen(filename, "rb");
  if (fp == NULL) {
    fprintf(stderr, "Cannot open %s\n", filename);
    return -1;
  }
  /*
   * BITMAPFILEHEADER
   *
   * 0  : BM
   * 2  : file size
   * 6  : reserved
   * 8  : reserved
   * 10 : pixel offset
   */
  type = read_u16(fp);
  if (type != 0x4d42) {
    fprintf(stderr, "%s is not a BMP file\n", filename);
    fclose(fp);
    return -1;
  }
  file_size = read_u32(fp);
  (void)file_size;
  read_u16(fp);       /* reserved1 */
  read_u16(fp);       /* reserved2 */
  pixel_offset = read_u32(fp);
  /*
   * DIB header
   */
  header_size = read_u32(fp);
  if (header_size < 12) {
    fprintf(stderr, "Unsupported BMP header\n");
    fclose(fp);
    return -1;
  }
  /*
   * Windows BITMAPINFOHEADER or later
   */
  if (header_size >= 40) {
    w = read_s32(fp);
    h = read_s32(fp);
    planes = read_u16(fp);
    bit_count = read_u16(fp);
    compression = read_u32(fp);
    read_u32(fp);       /* image size */
    read_s32(fp);       /* X pixels/meter */
    read_s32(fp);       /* Y pixels/meter */
    colors_used = read_u32(fp);
    read_u32(fp);       /* important colors */
    if (planes != 1) {
      fprintf(stderr, "Invalid BMP planes\n");
      fclose(fp);
      return -1;
    }
    /*
     * Negative height means top-down BMP.
     */
    if (h < 0) {
      top_down = 1;
      h = -h;
    }
    else {
      top_down = 0;
    }
    /*
     * Compression
     */
    if (compression == 0) {
      /* BI_RGB */
    }
    else if (compression == 3) {
      /* BI_BITFIELDS */
      red_mask   = read_u32(fp);
      green_mask = read_u32(fp);
      blue_mask  = read_u32(fp);
      //if (header_size >= 56){
      //alpha_mask = read_u32(fp);
      //}
    }
    else if (compression == 1 || compression == 2) {
      fprintf(stderr,"RLE-compressed BMP is not supported\n");
      fclose(fp);
      return -1;
    }
    else {
      fprintf(stderr,"Unsupported BMP compression: %u\n",compression);
      fclose(fp);
      return -1;
    }
    /*
     * Default masks for BI_RGB
     */
    if (compression == 0) {
      if (bit_count == 16) {
	/*
	 * Windows commonly interprets BI_RGB 16-bit
	 * as 5-5-5.
	 */
	red_mask   = 0x7c00;
	green_mask = 0x03e0;
	blue_mask  = 0x001f;
      }
      else if (bit_count == 32) {
	red_mask   = 0x00ff0000;
	green_mask = 0x0000ff00;
	blue_mask  = 0x000000ff;
      }
    }
    /*
     * Palette
     *
     * 1, 4, 8 bit BMP
     */
    if (bit_count <= 8) {
      uint32_t ncolors;
      if (colors_used != 0) ncolors = colors_used;
      else ncolors = 1U << bit_count;
      palette = malloc(ncolors * sizeof(uint32_t));
      if (palette == NULL) {
	fclose(fp);
	return -1;
      }
      for (uint32_t i = 0; i < ncolors; i++) {
	unsigned char bgr[4];
	if (fread(bgr, 1, 4, fp) != 4) {
	  fprintf(stderr,"Cannot read BMP palette\n");
	  free(palette);
	  fclose(fp);
	  return -1;
	}
	/*
	 * Store as 0x00RRGGBB
	 */
	palette[i] = ((uint32_t)bgr[2] << 16) | ((uint32_t)bgr[1] << 8) | ((uint32_t)bgr[0]);
      }
    }
  }
  else if (header_size == 12) {
    /*
     * OS/2 BITMAPCOREHEADER
     */
    w = read_u16(fp);
    h = read_u16(fp);
    planes = read_u16(fp);
    bit_count = read_u16(fp);
    compression = 0;
    colors_used = 0;
    top_down = 0;
    if (bit_count <= 8) {
      uint32_t ncolors = 1U << bit_count;
      palette = malloc(ncolors * sizeof(uint32_t));
      if (palette == NULL) {
	fclose(fp);
	return -1;
      }
      /*
       * OS/2 palette entries are only 3 bytes.
       */
      for (uint32_t i = 0; i < ncolors; i++) {
	unsigned char bgr[3];
	fread(bgr, 1, 3, fp);
	palette[i] = ((uint32_t)bgr[2] << 16) | ((uint32_t)bgr[1] << 8) | ((uint32_t)bgr[0]);
      }
    }
  }
  else {
    fprintf(stderr,"Unsupported BMP header size: %u\n",header_size);
    fclose(fp);
    return -1;
  }
  if (w <= 0 || h <= 0) {
    fprintf(stderr, "Invalid BMP image size\n");
    free(palette);
    fclose(fp);
    return -1;
  }
  //fprintf(stderr," Image size (%d x %d), %d bit ",(int)w, (int)h, (int)bit_count);
  if(w>LINEPIX){
    fprintf(stderr,"width(%d) > LINEPIX(%d)\n",w,LINEPIX);
    exit(1);
  }
  if(h>LINEPIY){
    fprintf(stderr,"width(%d) > LINEPIX(%d)\n",h,LINEPIY);
    exit(1);
  }
  /*
   * Allocate RGB image
   */
  if (image == NULL) {
    fprintf(stderr, "Cannot allocate image memory\n");
    free(palette);
    fclose(fp);
    return -1;
  }
  /*
   * Go to pixel data.
   *
   * This is important:
   * We do NOT assume that the pixel data starts
   * immediately after the header.
   */
  fseek(fp, pixel_offset, SEEK_SET);
  /*
   * Bytes per BMP scan line.
   *
   * Every scan line is aligned to 4 bytes.
   */
  uint32_t rowbytes = ((uint32_t)w * bit_count + 31) / 32 * 4;
  unsigned char *row;
  row = malloc(rowbytes);
  if (row == NULL) {
    free(palette);
    fclose(fp);
    return -1;
  }
  /*
   * Read each scan line
   */
  for (y = 0; y < h; y++) {
    int yy;
    if (top_down) yy = y;
    else yy = h - 1 - y;
    if (fread(row, 1, rowbytes, fp) != rowbytes) {
      fprintf(stderr, "Unexpected end of BMP file\n");
      free(row);
      free(palette);
      fclose(fp);
      return -1;
    }
    /*
     * 1-bit
     */
    if (bit_count == 1) {
      for (x = 0; x < w; x++) {
	int byte = x / 8;
	int bit  = 7 - (x % 8);
	int index = (row[byte] >> bit) & 1;
	uint32_t c = palette[index];
	image[yy][x][2] = (c >> 16) & 255;
	image[yy][x][1] = (c >> 8)  & 255;
	image[yy][x][0] = c & 255;
      }
    }
    /*
     * 4-bit
     */
    else if (bit_count == 4) {
      for (x = 0; x < w; x++) {
	int byte = x / 2;
	int index;
	if ((x & 1) == 0) index = row[byte] >> 4;
	else index = row[byte] & 15;
	uint32_t c = palette[index];
	image[yy][x][2] = (c >> 16) & 255;
	image[yy][x][1] = (c >> 8)  & 255;
	image[yy][x][0] = c & 255;
      }
    }
    /*
     * 8-bit
     */
    else if (bit_count == 8) {
      for (x = 0; x < w; x++) {
	uint32_t c = palette[row[x]];
	image[yy][x][2] = (c >> 16) & 255;
	image[yy][x][1] = (c >> 8)  & 255;
	image[yy][x][0] = c & 255;
      }
    }
    /*
     * 16-bit
     */
    else if (bit_count == 16) {
      for (x = 0; x < w; x++) {
	uint32_t v = (uint32_t)row[x * 2] | ((uint32_t)row[x * 2 + 1] << 8);
	image[yy][x][2] = extract_field(v, red_mask);
	image[yy][x][1] = extract_field(v, green_mask);
	image[yy][x][0] = extract_field(v, blue_mask);
      }
    }
    /*
     * 24-bit
     */
    else if (bit_count == 24) {
      for (x = 0; x < w; x++) {
	image[yy][x][2] = row[x * 3 + 2];
	image[yy][x][1] = row[x * 3 + 1];
	image[yy][x][0] = row[x * 3 + 0];
      }
    }
    /*
     * 32-bit
     */
    else if (bit_count == 32) {
      for (x = 0; x < w; x++) {
	uint32_t v = (uint32_t)row[x * 4] | ((uint32_t)row[x * 4 + 1] << 8) | ((uint32_t)row[x * 4 + 2] << 16) | ((uint32_t)row[x * 4 + 3] << 24);
	image[yy][x][2] = extract_field(v, red_mask);
	image[yy][x][1] = extract_field(v, green_mask);
	image[yy][x][0] = extract_field(v, blue_mask);
      }
    }
    else {
      fprintf(stderr,"Unsupported BMP bit depth: %d\n",bit_count);
      free(row);
      free(palette);
      fclose(fp);
      return -1;
    }
    for (x = 0; x < w; x++) {
      z=(image[yy][x][0]+image[yy][x][1]+image[yy][x][2])/3;
      if(z>WH) nwh++;
      if(zm>z) zm=z;
    }
  }
  nwh/=w*h/100;
  if(nwh<98 && zm!=0){
    for (y = 0; y < h; y++) {
      for (x = 0; x < w; x++) {
	for (k = 0; k < 3; k++) {
	  z=255-(255-image[y][x][k])*255.*FAC/(255-zm);
	  if(z<0) image[y][x][k]=0;
	  else image[y][x][k]=z;
	}
      }
    }
  }
  free(row);
  free(palette);
  fclose(fp);
  //fprintf(stderr,"OK\n");
  *width = w;
  *height = h;
  return(nwh);
}

int write_bmp(const char *filename, unsigned char image[LINEPIY][LINEPIX][3], int width, int height)
{
  FILE *fp;
  unsigned char b[4];
  int x, y;
  /* Number of bytes in one BMP scan line.
     BMP scan lines are aligned to 4 bytes. */
  int rowbytes = ((width * 3 + 3) / 4) * 4;
  unsigned char *row;

  if(width <= 0 || width > LINEPIX || height <= 0 || height > LINEPIY){
    fprintf(stderr, "Invalid image size: %d x %d\n", width, height);
    return -1;
  }
  fprintf(stderr,"Write: %s ... ",filename);
  fp = fopen(filename, "wb");
  if (fp == NULL) {
    fprintf(stderr, "Cannot create %s\n", filename);
    return -1;
  }
  row = (unsigned char *)malloc(rowbytes);
  if (row == NULL) {
    fprintf(stderr, "Cannot allocate BMP buffer\n");
    fclose(fp);
    return -1;
  }
  /*
   * --------------------------------------------------------
   * BITMAPFILEHEADER (14 bytes)
   * --------------------------------------------------------
   */
  /* "BM" */
  fputc('B', fp);
  fputc('M', fp);
  /* File size */
  uint32_t file_size = 54 + rowbytes * height;
  b[0] = file_size & 0xff;
  b[1] = (file_size >> 8) & 0xff;
  b[2] = (file_size >> 16) & 0xff;
  b[3] = (file_size >> 24) & 0xff;
  fwrite(b, 1, 4, fp);
  /* Reserved1 */
  fputc(0, fp);
  fputc(0, fp);
  /* Reserved2 */
  fputc(0, fp);
  fputc(0, fp);
  /* Pixel data offset = 14 + 40 = 54 */
  uint32_t offset = 54;
  b[0] = offset & 0xff;
  b[1] = (offset >> 8) & 0xff;
  b[2] = (offset >> 16) & 0xff;
  b[3] = (offset >> 24) & 0xff;
  fwrite(b, 1, 4, fp);
  /*
   * --------------------------------------------------------
   * BITMAPINFOHEADER (40 bytes)
   * --------------------------------------------------------
   */
  /* Header size = 40 */
  b[0] = 40;
  b[1] = 0;
  b[2] = 0;
  b[3] = 0;
  fwrite(b, 1, 4, fp);
  /* Width */
  b[0] = width & 0xff;
  b[1] = (width >> 8) & 0xff;
  b[2] = (width >> 16) & 0xff;
  b[3] = (width >> 24) & 0xff;
  fwrite(b, 1, 4, fp);
  /* Height */
  b[0] = height & 0xff;
  b[1] = (height >> 8) & 0xff;
  b[2] = (height >> 16) & 0xff;
  b[3] = (height >> 24) & 0xff;
  fwrite(b, 1, 4, fp);
  /* Planes = 1 */
  fputc(1, fp);
  fputc(0, fp);
  /* Bits per pixel = 24 */
  fputc(24, fp);
  fputc(0, fp);
  /* Compression = BI_RGB = 0 */
  b[0] = b[1] = b[2] = b[3] = 0;
  fwrite(b, 1, 4, fp);
  /* Image size */
  uint32_t image_size = rowbytes * height;
  b[0] = image_size & 0xff;
  b[1] = (image_size >> 8) & 0xff;
  b[2] = (image_size >> 16) & 0xff;
  b[3] = (image_size >> 24) & 0xff;
  fwrite(b, 1, 4, fp);
  /* X pixels per meter = 0 */
  b[0] = b[1] = b[2] = b[3] = 0;
  fwrite(b, 1, 4, fp);
  /* Y pixels per meter = 0 */
  fwrite(b, 1, 4, fp);
  /* Number of colors = 0 */
  fwrite(b, 1, 4, fp);
  /* Important colors = 0 */
  fwrite(b, 1, 4, fp);
  /*
   * --------------------------------------------------------
   * Pixel data
   * --------------------------------------------------------
   *
   * BMP 24-bit uses BGR order.
   * Positive height means bottom-up.
   */
  for (y = height - 1; y >= 0; y--) {
    for (x = 0; x < width; x++) {
      row[x * 3 + 0] = image[y][x][0];  /* B */
      row[x * 3 + 1] = image[y][x][1];  /* G */
      row[x * 3 + 2] = image[y][x][2];  /* R */
    }
    /* Padding */
    for (x = width * 3; x < rowbytes; x++)
      row[x] = 0;
    fwrite(row, 1, rowbytes, fp);
  }
  free(row);
  fclose(fp);
  fprintf(stderr,"OK\n");
  return 0;
}

int write_bmp_8bit(const char *filename, unsigned char image[LINEPIY][LINEPIX][3], int width, int height)
{
    FILE *fp;
    unsigned char fh[14];
    unsigned char ih[40];
    unsigned char palette[256][4];
    unsigned char *row;
    int x, y;
    int rowbytes;

  if(width <= 0 || width > LINEPIX || height <= 0 || height > LINEPIY){
    fprintf(stderr, "Invalid image size: %d x %d\n", width, height);
    return -1;
  }
  fprintf(stderr,"Write: %s ... ",filename);
  fp = fopen(filename, "wb");
  if(fp == NULL){
    perror(filename);
    return -1;
  }
  /*
   * 8 bit BMP の1行のバイト数。
   * BMPでは各行が4 byte境界に揃えられる。
   */
  rowbytes = (width + 3) / 4 * 4;
  /*
   * BITMAPFILEHEADER (14 bytes)
   */
  memset(fh, 0, sizeof(fh));
  fh[0] = 'B';
  fh[1] = 'M';
  /*
   * ファイル全体のサイズ
   * 14 + 40 + 256*4 + pixel data
   */
  {
    uint32_t filesize = 14 + 40 + 256 * 4 + (uint32_t)rowbytes * height;
    fh[2] = filesize & 0xff;
    fh[3] = (filesize >> 8) & 0xff;
    fh[4] = (filesize >> 16) & 0xff;
    fh[5] = (filesize >> 24) & 0xff;
  }
  /*
   * Pixel data の開始位置
   * 14-byte file header
   * + 40-byte info header
   * + 256*4-byte palette
   */
  {
    uint32_t offset = 14 + 40 + 256 * 4;
    fh[10] = offset & 0xff;
    fh[11] = (offset >> 8) & 0xff;
    fh[12] = (offset >> 16) & 0xff;
    fh[13] = (offset >> 24) & 0xff;
  }
  if(fwrite(fh, 1, 14, fp) != 14){
    fclose(fp);
    return -1;
  }
  /*
   * BITMAPINFOHEADER (40 bytes)
   */
  memset(ih, 0, sizeof(ih));
  /* header size */
  ih[0] = 40;
  /* width */
  ih[4] = width & 0xff;
  ih[5] = (width >> 8) & 0xff;
  ih[6] = (width >> 16) & 0xff;
  ih[7] = (width >> 24) & 0xff;
  /* height */
  ih[8] = height & 0xff;
  ih[9] = (height >> 8) & 0xff;
  ih[10] = (height >> 16) & 0xff;
  ih[11] = (height >> 24) & 0xff;
  /* planes = 1 */
  ih[12] = 1;
  /* bits per pixel = 8 */
  ih[14] = 8;
  /* compression = BI_RGB = 0 */
  /* ih[16]〜ih[19] = 0 */
  /* image size */
  {
    uint32_t imagesize = (uint32_t)rowbytes * height;
    ih[20] = imagesize & 0xff;
    ih[21] = (imagesize >> 8) & 0xff;
    ih[22] = (imagesize >> 16) & 0xff;
    ih[23] = (imagesize >> 24) & 0xff;
  }
  /* X/Y pixels per meter は 0 のまま */
  /* colors used = 256 */
  ih[32] = 256 & 0xff;
  ih[33] = (256 >> 8) & 0xff;
  /* important colors = 0 */
  if(fwrite(ih, 1, 40, fp) != 40){
    fclose(fp);
    return -1;
  }
  /*
   * 256色グレースケール・パレット
   *
   * BMPのパレットは B,G,R,Reserved の順。
   */
  for(x = 0; x < 256; x++){
    palette[x][0] = x;   /* B */
    palette[x][1] = x;   /* G */
    palette[x][2] = x;   /* R */
    palette[x][3] = 0;
  }
  if(fwrite(palette, 1, 256 * 4, fp) != 256 * 4){
    fclose(fp);
    return -1;
  }
  row = (unsigned char *)malloc(rowbytes);
  if(row == NULL){
    fprintf(stderr, "malloc failed\n");
    fclose(fp);
    return -1;
  }
  /*
   * BMPは通常 bottom-up なので、
   * 最終行から書き出す。
   */
  for(y = height - 1; y >= 0; y--){
    /*
     * RGB → grayscale
     *
     * ここでは単純平均ではなく、
     * 一般的な輝度変換を使用。
     */
    for(x = 0; x < width; x++){
      int r = image[y][x][0];
      int g = image[y][x][1];
      int b = image[y][x][2];
      row[x] = (unsigned char)((299*r + 587*g + 114*b) / 1000);
    }
    /* padding 部分を 0 にする */
    for(x = width; x < rowbytes; x++) row[x] = 0;
    if(fwrite(row, 1, rowbytes, fp) != rowbytes){
      free(row);
      fclose(fp);
      return -1;
    }
  }
  free(row);
  fclose(fp);
  fprintf(stderr,"OK\n");
  return 0;
}

/*
int main(int argc,char *argv[])
{
  static unsigned char image[LINEPIY][LINEPIX][3];
  int jm,im;
  
  if(argc != 3){
    fprintf(stderr,"Usage : %s input output\n",argv[0]);
    exit(0);
  }
  read_bmp(argv[1], image, &jm, &im);
  write_bmp(argv[2], image, jm, im);
}
*/