/*
 * Routines for bitmap manipulation
 *
  gsumi version 0.5

  Copyright 1997 Owen Taylor <owt1@cornell.edu>

  Heavily based on

  xink version 0.02

  Copyright 1997 Raph Levien <raph@acm.org>

  This code is free for commercial and non-commercial use or
  redistribution, as long as the source code release, startup screen,
  or product packaging includes this copyright notice.
*/

#include "gsumi.h"

/* The undo buffer. */
#define MAX_UNDO 16
image *undo_ring[MAX_UNDO];
/* undo_n and undo_cur are relative to undo_start, mod MAX_UNDO. */
int undo_start, undo_n, undo_cur;

/* Stuff for the hi-res bitmap being drawn upon */
/* It's stored in a runlength encoded form. Each int32 represents WHITE_X
 white pixels followed by BLACK_X black ones. All zero terminates the list. */
image *bitmap;

/* forward declarations */
void image_free (image *img);
int32 *add_band (image *img, int32 *line, int x, int width);

image *image_create (int x, int y) {
  int j;

  image *new_image;

  new_image = (image *)malloc (sizeof(image) + (y - 1) * sizeof(int32 *));
  for (j = 0; j < y; j++) {
    new_image->lines[j] = (int32 *)malloc (sizeof(int32));
    new_image->lines[j][0] = 0;
  }
  new_image->rec.x0 = 0;
  new_image->rec.y0 = 0;
  new_image->rec.x1 = x;
  new_image->rec.y1 = y;
  new_image->width = x;
  new_image->height = y;

  return new_image;
}

#define MAX_STRING 256
#define MAX_LINEBUF 2000

/* return true on sucess, false otherwise */
int load_bitmap (const char *fn, int compress) {
  FILE *f;
  char s[MAX_STRING];
  int x, y;
  int i, j, k;
  uint8 linebuf[MAX_LINEBUF];
  uint8 b;
  int32 *l;
  int xb;

 image *new_bitmap;
  
  const char *gzip_cmd = "gzip -cd < ";
  
  if (compress) {
    char *cmd = (char *)malloc(sizeof(char)*(strlen(gzip_cmd)+strlen(fn)+1));
    strcpy(cmd,gzip_cmd);
    strcat(cmd,fn);
    f = popen(cmd,"r");
    if (!f) {
      fprintf (stderr, "could execute pipe '%s' for loading image\n", cmd);
      free((void *)cmd);
      return 0;
    }
    free((void *)cmd);
  } 
  else
    {
      f = fopen (fn, "r");
      if (!f) {
	fprintf (stderr, "could not open %s for loading image\n", fn);
	return 0;
      }
    }
      
  fgets (s, MAX_STRING, f);
  if (s[0] != 'P' || s[1] != '4') {
    fprintf(stderr,"Image not in pbm raw format.\n");
    if (compress)
      pclose (f);
    else
      fclose (f);
    return 0;
  }
  do {
    fgets (s, 80, f);
  } while (s[0] == '#');
  sscanf (s, "%d %d", &x, &y);
  printf ("loading %d x %d bitmap\n", x, y);

  new_bitmap = image_create(x,y);

  xb = (x + 7) >> 3;
  /* This should be more efficient then what was here before,
     though more complicated. The number of add_band calls is
     minimized but the scanning probably could be improved. */
  for (j = 0; j < y; j++) {
    int band_length = 0;	/* sop to stop GCC from whining */
    int band_start = 0;
    int in_band;
    int bytes_read;

    bytes_read = fread (linebuf, 1, xb, f);
    if (bytes_read != xb)	/* error or short file */
      {
	fprintf(stderr,"Error reading pbm");
	if (compress)
	  pclose (f);
	else
	  fclose (f);
	image_free(new_bitmap);
	return 0;
      }
    l = new_bitmap->lines[j];
    in_band = 0;
    for (i = 0; i < xb; i++) {
      b = linebuf[i];
      if (b == 0xff) {
	if (in_band) {
	  band_length += 8;
	} else {
	  in_band = 1;
	  band_start = i * 8;
	  band_length = 8;
	}
      } else if (b) {
	for (k = 0; k < 8; k++)
	  if (b & (128 >> k)) {
	    if (in_band) {
	      band_length ++;
	    } else {
	      in_band = 1;
	      band_start = i * 8 + k;
	      band_length = 1;
	    }
	  } else if (in_band) {
	    l = add_band (new_bitmap, l, band_start, band_length);
	    in_band = 0;
	  }
      } else if (in_band) {	/* b == 0x00 */
	l = add_band (new_bitmap, l, band_start, band_length);
	in_band = 0;
      }
    }
    if (in_band)
      l = add_band (new_bitmap, l, band_start, band_length);

    new_bitmap->lines[j] = l;
  }
  if (compress)
    pclose (f);
  else
    fclose (f);

  /* success */

  bitmap_update (&bitmap->rec);
  image_free(bitmap);

  /* the proper order of the two lines is a bit uncertain - but
     it shouldn't matter currently */
  bitmap = new_bitmap;
  bitmap_update (&new_bitmap->rec);

  return 1;
}

/* modified to use stdio instead of raw files. No detectable
   loss of speed. (wanted to use popen for gzipped stuff). */
void save_bitmap (const char *fn, int compress) {
  FILE *f;
  unsigned char linebuf[MAX_LINEBUF];
  int bpl, i, y;
  int pos, pos_1, pos_2;
  int k, k1, k2;

  const char *gzip_cmd = "gzip > ";
  
  if (compress) {
    char *cmd = (char *)malloc(sizeof(char)*(strlen(gzip_cmd)+strlen(fn)+1));
    strcpy(cmd,gzip_cmd);
    strcat(cmd,fn);
    f = popen(cmd,"w");
    if (!f) {
      fprintf (stderr, "could execute pipe '%s' for saving image\n", cmd);
      free((void *)cmd);
      return;
    }
    free((void *)cmd);
  } else {
    f = fopen (fn, "w+");
    if (!f) {
      fprintf (stderr, "could not open %s for saving image\n", fn);
      return;
    }
  }

  fprintf(f,"P4\n%d %d\n", bitmap->width, bitmap->height);
  bpl = (bitmap->width + 7) >> 3;
  for (y = 0; y < bitmap->height; y++) {
    memset (linebuf, 0, bpl);
    pos = 0;
    for (i = 0; bitmap->lines[y][i]; i++) {
      pos_1 = pos + WHITE_X(bitmap->lines[y][i]);
      pos_2 = pos_1 + BLACK_X(bitmap->lines[y][i]);
      k1 = pos_1 >> 3;
      k2 = pos_2 >> 3;
      if (k1 == k2)
	linebuf[k1] |= (256 >> (pos_1 & 7)) - (256 >> (pos_2 & 7));
      else {
	linebuf[k1] |= (256 >> (pos_1 & 7)) - 1;
	for (k = k1 + 1; k < k2; k++)
	  linebuf[k] = 255;
	linebuf[k2] |= 256 - (256 >> (pos_2 & 7));
      }
      pos = pos_2;
    }
    fwrite (linebuf, 1, bpl, f);
  }
  if (compress)
    pclose (f);
  else
    fclose (f);
}

void bitmap_init (int x, int y) 
{
  bitmap = image_create(x,y);
}

/* The rest of the routines in this file are umodified from
 * xink v0.2
 ***********************************************************/

/* Routines for manipulating the bitmap. */

/* Add a band to an existing line. Free the argument. Malloc the return. */
int32 *add_band (image *img, int32 *line, int x, int width) {
  int i, j;
  int32 *new;
  int pos, pos_1, pos_2;
  int x_0, x_1, x_2;

  /* This routine is pretty gorpy. It could probably be sped up
     (at the expense of additional gorp) by blindly copying the
     bands before and after the interesting part. */

  /* It would be fun to prove this correct - it seems like the perfect
     thing for weakest preconditions. */

  /* Clip band to actual bitmap dimensions. */
  if (x < 0) { width += x; x = 0; }
  if (width <= 0 || x >= img->width) return line;
  if (x + width > img->width) width = img->width - x;

  for (i = 0; line[i]; i++);
  new = (int32 *)malloc (sizeof(int32) * (i + 2));
  pos = 0;
  /* invariant: [x_0..x_1) is a white band and [x_1..x_2) is a black
     band that have not yet been output. [x_1..x_2) includes [x..x+width)
     if x_2 >= x. */
  x_0 = 0;
  x_1 = 0;
  if (x == 0)
    x_2 = width;
  else
    x_2 = 0;
  j = 0;
  for (i = 0; line[i]; i++) {
    pos_1 = pos + WHITE_X(line[i]);
    pos_2 = pos_1 + BLACK_X(line[i]);
    /* output [x_0..x_1) and [x_1..x_2) if pos_1 > x_2 */
    if (pos_1 > x_2) {
      if (x_2 > x_1) { /* skip zero-width black bands */
	new[j++] = WHITE_BLACK (x_1 - x_0, x_2 - x_1);
	x_0 = x_2;
      }
      x_1 = pos_1;
      x_2 = pos_2;
    } else {
      if (x_2 < pos_2)
	x_2 = pos_2;
    }
    /* x_0, x_1, x_2 represent the input bands, now or in [x..x+width) */
    if (x >= x_0 && x_2 >= x) {
      if (x + width < x_1) {
	new[j++] = WHITE_BLACK (x - x_0, width);
	x_0 = x + width;
      } else {
	if (x_1 > x) x_1 = x;
	if (x_2 < x + width) x_2 = x + width;
      }
    }
    pos = pos_2;
  }
  if (x_2 > x_1) { /* skip zero-width black bands */
    new[j++] = WHITE_BLACK (x_1 - x_0, x_2 - x_1);
    x_0 = x_2;
  }
  if (x_2 < x)
    new[j++] = WHITE_BLACK (x - x_0, width);
  new[j] = 0;
  free (line);
  return new;
}

/* Remove a band from an existing line. Has type "free the argument, malloc
 the return", but in most cases won't do any allocation. */
int32 *remove_band (image *img, int32 *line, int x, int width) {
    int i, j, k;
    int x_0, x_1, x_2;
    int x_0p, x_1p, x_2p;
    int x_end;

    int32 t;
    
    /* Clip band to actual bitmap dimensions. */
    if (x < 0) { width += x; x = 0; }
    if (width <= 0 || x >= img->width) return line;
    if (x + width > img->width) width = img->width - x;

    x_end = x+width;

    /* find the beginning of the band */
    
    x_2 = 0;

    for (i=0; line[i]; i++) {
	x_0 = x_2;
	x_1 = x_0 + WHITE_X(line[i]);
	x_2 = x_1 + BLACK_X(line[i]);
	
	if (x < x_1) {		/* start in white region */
	    x_2p = x_0;
	    for (j=i; line[j]; j++) {
		x_0p = x_2p;
		x_1p = x_0p + WHITE_X(line[j]);
		x_2p = x_1p + BLACK_X(line[j]);
		
		if (x_end < x_2p) { /* end this segment */
		    if (x_end < x_1p) {	/* end in white segment */
			line[i] = WHITE_BLACK(x_1p - x_0, x_2p - x_1p);
		    } else {
			line[i] = WHITE_BLACK(x_end - x_0, x_2p - x_end);
		    }
		    if (i!=j) {	
			for (k=1;(t=line[j+k]);k++)
			    line[i+k] = t;
			line[i+k] = 0; /* terminate */
		    }
		    return line;
		}
	    }
	    line[i] = 0;	/* didn't find end, truncate line */
	    return line;

	} else if (x < x_2) {	/* start in black segment */
	    line[i] = WHITE_BLACK(x_1 - x_0, x - x_1);
	    if (x_end < x_2) {	/* need to split segment */
		for (j=i; line[j]; j++);
		line = realloc(line, (sizeof(int32))*(j+2));

		for (k=j+1; k>i+1; k--)
		    line[k] = line[k-1];

		line[i+1] = WHITE_BLACK(x_end - x, x_2 - x_end);

		return line;
	    }
	    
	    x_2p = x_2;
	    for (j=i+1; line[j]; j++) {
		x_0p = x_2p;
		x_1p = x_0p + WHITE_X(line[j]);
		x_2p = x_1p + BLACK_X(line[j]);
		
		if (x_end < x_2p) { /* end this segment */
		    if (x_end < x_1p) {	/* end in white segment */
			line[i+1] = WHITE_BLACK(x_1p - x, x_2p - x_1p);
		    } else {
			line[i+1] = WHITE_BLACK(x_end - x, x_2p - x_end);
		    }
		    if (i+1!=j) {	
			for (k=2;(t=line[j+k-1]);k++)
			    line[i+k] = t;
			line[i+k] = 0; /* terminate */
		    }
		    return line;
		}
	    }
	    line[i+1] = 0;	/* didn't find end, truncate */
	    return line;
	}
    }
    return line;		/* start not find, do  nothing  */
}

/* appropriately draw or remove a band from a line */
int32 *draw_band (image *img, int32 *line, int x, int width, int color) {
    if (color) {
	return remove_band(img, line,x,width);
    } else {
	return add_band(img, line,x,width);
    }
}

void dump_line (int32 *line) {
  int i;
  int pos;

  pos = 0;
  for (i = 0; line[i]; i++) {
    printf ("[%d..%d) ", pos + WHITE_X(line[i]), pos + WHITE_X(line[i]) + BLACK_X(line[i]));
    pos += WHITE_X(line[i]) + BLACK_X(line[i]);
  }
  printf ("\n");
}

/* Draw  disk (image coordinates). A radius of 1 is a single pixel. */
/* I want to change the interface so that the coordintates are doubles. */
void bitmap_draw_disk (int x, int y, int r, int color) {
  int j, w;

  for (j = y + 1 - r; j < y + r; j++) {
    w = sqrt (r * r - (j - y) * (j - y));
    if (j >= 0 && j < bitmap->height)
      bitmap->lines[j] = 
	draw_band (bitmap, bitmap->lines[j], x + 1 - w, w * 2 - 1, color);
  }
}

/* Draws a Blob (see blob.h) into a bitmap */
void bitmap_draw_blob (Blob *b, int color)
{
  int i;

  for (i=0;i<b->height;i++)
    if (i+b->y >= 0 && i+b->y < bitmap->height)
      bitmap->lines[i+b->y] = 
	draw_band (bitmap, bitmap->lines[i+b->y],
		   b->data[i].left, b->data[i].right-b->data[i].left+1,
		   color);
}

/* Draw a black convex polygon, with pixels in clockwise order. */
void bitmap_draw_convpoly (int x[], int y[], int n, int color) {
  int j, k;
  int k_min, k_left, k_right;
  int x0_left, y0_left, x1_left, y1_left;
  int x0_right, y0_right, x1_right, y1_right;
  int x_left, x_right;

#ifdef DEBUG
  printf ("convpoly");
  for (i = 0; i < n; i++)
    printf (" (%d, %d)", x[i], y[i]);
  printf ("\n");
#endif
  j = 0x7fff;
  for (k = 0; k < n; k++) {
    if (j > y[k]) {
      k_min = k;
      j = y[k];
    }
  }
  k_left = k_min;
  x0_left = x[k_left];
  y0_left = y[k_left];
  x1_left = x[(k_left + n - 1) % n];
  y1_left = y[(k_left + n - 1) % n];
  k_right = k_min;
  x0_right = x[k_right];
  y0_right = y[k_right];
  x1_right = x[(k_right + 1) % n];
  y1_right = y[(k_right + 1) % n];
  for (; ; j++) {
    if (j == y1_left) {
      if (j >= y[(k_left + n - 2) % n])
	break;
      else {
	k_left = (k_left + n - 1) % n;
	x0_left = x1_left;
	y0_left = y1_left;
	x1_left = x[(k_left + n - 1) % n];
	y1_left = y[(k_left + n - 1) % n];
      }
    }
    if (j == y1_right) {
      if (j >= y[(k_right + 2) % n])
	break;
      else {
	k_right = (k_right + 1) % n;
	x0_right = x1_right;
	y0_right = y1_right;
	x1_right = x[(k_right + 1) % n];
	y1_right = y[(k_right + 1) % n];
      }
    }
    /* Could use differential math here, but why bother? */
    x_left = x0_left + ((x1_left - x0_left) * ((j - y0_left) * 2 + 1))
      / ((y1_left - y0_left) * 2);
    x_right = x0_right + ((x1_right - x0_right) * ((j - y0_right) * 2 + 1))
      / ((y1_right - y0_right) * 2);
    if (x_left < x_right && j >= 0 && j < bitmap->height)
      bitmap->lines[j] = 
	draw_band (bitmap, bitmap->lines[j], x_left, x_right - x_left, color);
  }
}

/* Draw a black "connector" between the two disks. */
void bitmap_draw_connector (int x0, int y0, int r0, int x1, int y1, int r1,
			    int color) {
  int x[4], y[4];
  double d;
  double dx0, dy0, dx1, dy1;

  /* This routine needs a little more careful thought to make the coordinates
     match up more precisely with the disks drawn. */

  d = sqrt ((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0));
  /* compute deltas */
  dx0 = ((y1 - y0) / d) * (r0 - 0.5);
  dy0 = ((x0 - x1) / d) * (r0 - 0.5);
  dx1 = ((y1 - y0) / d) * (r1 - 0.5);
  dy1 = ((x0 - x1) / d) * (r1 - 0.5);

  /* draw the quadrilateral */
  x[0] = x0 + 0.5 - dx0;
  y[0] = y0 + 0.5 - dy0;
  x[1] = x0 + 0.5 + dx0;
  y[1] = y0 + 0.5 + dy0;
  x[2] = x1 + 0.5 + dx1;
  y[2] = y1 + 0.5 + dy1;
  x[3] = x1 + 0.5 - dx1;
  y[3] = y1 + 0.5 - dy1;
  bitmap_draw_convpoly (x, y, 4, color);
}

/* clear the bitmap */
void bitmap_clear ()
{
  int j;

  for (j = 0; j < bitmap->height; j++) {
    free(bitmap->lines[j]);
    bitmap->lines[j] = (int32 *)malloc (sizeof(int32));
    bitmap->lines[j][0] = 0;
  }
}


/* Functions for implementing undo. The interface is as follows:

   undo_begin ()
     Begins an undo transaction. Allocates a new place in the undo_ring
     (freeing an old one to make space, if necessary). Also kills all
     redo entries.

   undo_update ()
     Adds a rectangle to the undo region. Call this routine before
     mutating that rectangle. Copies needed parts of that rectangle
     to the current undo buffer.

   undo_reset ()
     Clears the undo buffer.

   undo ()
     Copies from the undo buffer to the image, and also copies from
     the image into the undo ring.

   redo ()
     The reverse of undo.

   One thing that is not dealt with is the possibility that the undo
   image is a different size than the image. It would be nice to be
   able to do this, for example so you could undo a load.

*/

void image_free (image *img) {
  int y;

  for (y = img->rec.y0; y < img->rec.y1; y++)
    free (img->lines[y]);
  free (img);
}

void undo_begin (void) {
  int new;

  while (undo_n > undo_cur) {
    undo_n--;
    image_free (undo_ring[(undo_start + undo_n) % MAX_UNDO]);
  }
  if (undo_n == MAX_UNDO) {
    image_free (undo_ring[undo_start]);
    undo_start = (undo_start + 1) % MAX_UNDO;
    undo_n--;
  }
  new = (undo_start + undo_n) % MAX_UNDO;
  undo_ring[new] = (image *)malloc (sizeof(image) + (bitmap->height - 1)
				    * sizeof (int32 *));
  undo_ring[new]->width = bitmap->width;
  undo_ring[new]->height = bitmap->height;
  undo_ring[new]->rec.x0 = 0;
  undo_ring[new]->rec.y0 = 0;
  undo_ring[new]->rec.x1 = 0;
  undo_ring[new]->rec.y1 = 0;
  /* Don't need to update any lines, because the region is empty. */
  undo_n++;
  undo_cur = undo_n;
}

/* Make a new copy of the line, and copy it to the dst image. */
void copy_line (image *dst, const image *src, int y) {
  int n;
  int32 *l, *new;

  l = src->lines[y];
  for (n = 0; l[n]; n++);
  new = (int32 *)malloc (sizeof(int32) * (n + 1));
  memcpy (new, l, sizeof(int32) * (n + 1));
  dst->lines[y] = new;
}

void undo_update (rect *rec) {
  int cur;
  int y;
  rect old_rec, clip_rec;

  if (undo_n < 1) {
    fprintf (stderr, "undo_update: undo_n < 1\n");
    exit (1);
  }
  rect_intersect (&clip_rec, rec, &(bitmap->rec));
  cur = (undo_start + undo_cur - 1) % MAX_UNDO;
  old_rec = undo_ring[cur]->rec;
  if (old_rec.y1 <= old_rec.y0) {
    /* Undo buffer is empty - start from scratch. */
    for (y = clip_rec.y0; y < clip_rec.y1; y++)
      copy_line (undo_ring[cur], bitmap, y);
  } else {
    /* Undo buffer is not empty - just copy new parts. */
    for (y = clip_rec.y0; y < old_rec.y0; y++)
      copy_line (undo_ring[cur], bitmap, y);
    for (y = old_rec.y1; y < clip_rec.y1; y++)
      copy_line (undo_ring[cur], bitmap, y);
  }
  rect_union (&(undo_ring[cur]->rec), &old_rec, &clip_rec);
}

void undo_reset (void) {
  while (undo_n) {
    undo_n--;
    image_free (undo_ring[(undo_start + undo_n) % MAX_UNDO]);
  }
}

/* Exchanges the numbered undo buffer with the relevant region in the image,
   and calls bitmap_update(), so that it gets displayed. */
void undo_exchange (int num) {
  int y;
  int32 *l;

  for (y = undo_ring[num]->rec.y0; y < undo_ring[num]->rec.y1; y++) {
    l = bitmap->lines[y];
    bitmap->lines[y] = undo_ring[num]->lines[y];
    undo_ring[num]->lines[y] = l;
  }
  bitmap_update (&(undo_ring[num]->rec));
}

void undo () {

  if (undo_cur == 0) return;
  undo_cur--;
  undo_exchange ((undo_start + undo_cur) % MAX_UNDO);
}

void redo () {

  if (undo_cur == undo_n) return;
  undo_exchange ((undo_start + undo_cur) % MAX_UNDO);
  undo_cur++;
}