#include <stdio.h>
#include <stdlib.h>

/* bitmap exploration program */

int pbm_getc(FILE *fp)
{
  int retval ;
  retval = getc(fp) ;
  while (!feof(fp) && retval == '#') {
    do {
      retval = getc(fp) ;
    } while (!feof(fp) && retval != '\n') ;
    if (retval == '\n') retval = getc(fp) ;
  }
  return retval ;
}

#define skip_spaces() do { c = pbm_getc(fp) ; } while (isspace(c)) ;

void read_bitmap(char *fname, int invert, int ***p_bitmap, 
		 int *p_width, int *p_height)
{
  FILE *fp ;
  char c ;
  int i, j, mask ;

  fp = fopen(fname, "r") ;
  pbm_getc(fp) ; pbm_getc(fp) ; /* the "magic number" */

  skip_spaces() ;

  *p_width = 0 ;
  do {
    *p_width *= 10 ;
    *p_width += (c - '0') ;
    c = pbm_getc(fp) ;
  } while (!isspace(c)) ;

  skip_spaces() ;

  *p_height = 0 ;
  do {
    *p_height *= 10 ;
    *p_height += (c - '0') ;
    c = pbm_getc(fp) ;
  } while (!isspace(c)) ;

  do { c = getc(fp) ; } while (isspace(c)) ;

  (*p_bitmap) = (int **)malloc(sizeof(int *) * *p_height) ;
  for (i=0 ; i < *p_height ; i++)
    (*p_bitmap)[i] = (int *)malloc(sizeof(int) * *p_width) ;

  mask = 128 ;
  for (i=0 ; i < *p_height ; i++) 
    for (j=0 ; j < *p_width ; j++) {
      (*p_bitmap)[i][j] = ((c & mask) != 0) ? !invert : invert ;
      mask >>= 1 ;
      if (!mask) {
	mask = 128 ;
	c = getc(fp) ;
      }
    }
  fclose(fp) ;
}   

char cur_byte ;
int bit_count ;

#define put_bit(FP, VAL) { if (bit_count == 8) { fputc(cur_byte, (FP)) ; cur_byte=(char)0 ; bit_count=0 ; } cur_byte <<=1 ; cur_byte |= (VAL) ; bit_count++ ; }

void save_map_rle2(char *fname, int **map, int width, int height, 
		   int region_count)
{
  FILE *fp ;
  int curval, run_length, i, j, k, count ;
  int num_regions, region_bits, length_bits ;

  num_regions = region_count+1 ; /* include the "-1" border region */

  region_bits = 0 ; i = num_regions-1 ;
  while (i != 0) {
    i >>= 1 ;
    region_bits++ ;
  }
       
  length_bits = 0 ; i = width-2 ;
  while (i != 0) {
    i >>= 1 ;
    length_bits++ ;
  }
  if (length_bits == 0) length_bits = 1 ;

  fp = fopen(fname, "w") ;

  fputc((char)(width/256), fp) ;
  fputc((char)(width%256), fp) ;
  fputc((char)(height/256), fp) ;
  fputc((char)(height%256), fp) ;
  fputc((char)region_bits, fp) ;

  cur_byte = (char)0 ;
  bit_count = 0 ;

  for (i=0 ; i < height ; i++) {
    curval = map[i][0] ;
    run_length = 0 ;
    for (j=0 ; j < width ; j++) {
      if (map[i][j] == curval) run_length++ ;
      else {
	for (k = 1 << (region_bits-1) ; k != 0 ; k >>= 1)
	  if (((curval+1) & k) == 0) {
	    put_bit(fp, 0) ;
	  }
	  else {
	    put_bit(fp, 1) ;
	  }

	for (k = 1 << (length_bits-1) ; k != 0 ; k >>= 1)
	  if (((run_length-1) & k) == 0) {
	    put_bit(fp, 0) ;
	  }
	  else {
	    put_bit(fp, 1) ;
	  }
	curval = map[i][j] ;
	run_length = 1 ;
      }
    }
    for (k = 1 << (region_bits-1) ; k != 0 ; k >>= 1)
      if (((curval+1) & k) == 0) {
	put_bit(fp, 0) ;
      }
      else {
	put_bit(fp, 1) ;
      }
    
    for (k = 1 << (length_bits-1) ; k != 0 ; k >>= 1)
      if (((run_length-1) & k) == 0) {
	put_bit(fp, 0) ;
      }
      else {
	put_bit(fp, 1) ;
      }
  }

  /* flush the last byte */
  cur_byte <<= (8-bit_count) ; fputc(cur_byte, fp) ;

  fclose(fp) ;
}

typedef struct _point_stack {
  int x ; 
  int y ;
  struct _point_stack *next ;
} point_stack ;

void pixel_push(int x, int y, point_stack **stack)
{
  point_stack *newp ;
  newp = (point_stack *)malloc(sizeof(point_stack)) ;
  newp->x= x ;
  newp->y = y ;
  newp->next = *stack ;
  *stack = newp ;
}

void mark_region(int x, int y, int **bitmap, int width, int height, 
		 int **region, int *minx, int *maxx, int *miny, int *maxy)
{
  point_stack *stack=NULL, *tempp ;

  pixel_push(x, y, &stack) ;
  *minx = *maxx = x ;
  *miny = *maxy = y ;

  while (stack != NULL) {
    x = stack->x ; y = stack->y ;
    tempp = stack ;
    stack = stack->next ;
    free(tempp) ;

    region[y][x] = 1 ;
    
    if (x < *minx) *minx = x ;
    if (x > *maxx) *maxx = x ;
    if (y < *miny) *miny = y ;
    if (y > *maxy) *maxy = y ;

    if (y - 1 > 0 && bitmap[y-1][x] && !region[y-1][x])
      pixel_push(x, y-1, &stack) ;
    if (y + 1 < height && bitmap[y+1][x] && !region[y+1][x])
      pixel_push(x, y+1, &stack) ;
    if (x - 1 > 0 && bitmap[y][x-1] && !region[y][x-1]) 
      pixel_push(x-1, y, &stack) ;
    if (x + 1 < width && bitmap[y][x+1] && !region[y][x+1])
      pixel_push(x+1, y, &stack) ;
  }
}

main(int argc, char *argv[])
{
  char *region_fname=NULL, *border_fname=NULL, *output_fname=NULL ;
  int region_count=0 ;
  int opt, i, j, x, y, minx, miny, maxx, maxy ;
  int marked_pixel_found, no_more_regions ;
  int **bitmap, **region, **newmap ;
  int width, height, width2, height2 ;

  while ((opt = getopt(argc, argv, "b:r:o:")) != EOF)
    switch(opt) {
    case 'b': border_fname = optarg ; break ;
    case 'r': region_fname = optarg ; break ;
    case 'o': output_fname = optarg ; break ;
    case '?':
      fprintf(stderr, "usage: rle2_builder -r regionfile [-b borderfile] -o outpufile\n") ;
      exit(1) ;
      break ;
    }
      
  if (region_fname == NULL || output_fname == NULL) {
    fprintf(stderr, "usage: rle2_builder -r regionfile [-b borderfile] -o outpufile\n") ;
    exit(1) ;
  }

  if (border_fname == NULL) border_fname = region_fname ;

  /* read in bitmap delimiting regions only */
  read_bitmap(region_fname, 1, &bitmap, &width, &height) ;

  region = (int **)malloc(sizeof(int *) * height) ;
  newmap = (int **)malloc(sizeof(int *) * height) ;
  for (i=0 ; i < height ; i++) {
    region[i] = (int *)malloc(sizeof(int) * width) ;
    newmap[i] = (int *)malloc(sizeof(int) * width) ;
    for (j=0 ; j < width ; j++) region[i][j] = newmap[i][j] = 0 ;
  }

  do {
    marked_pixel_found = 0 ;
    y = 0 ;
    while (!marked_pixel_found && y < height) {
      x = 0 ;
      while (!marked_pixel_found && x < width) {
	marked_pixel_found = bitmap[y][x] ;
	if (!marked_pixel_found) x++ ;
      }
      if (!marked_pixel_found) y++ ;
    }

    if (marked_pixel_found) {
      mark_region(x, y, bitmap, width, height, 
		  region, &minx, &maxx, &miny, &maxy) ;
      for (i=miny ; i <= maxy ; i++)
	for (j=minx ; j <= maxx ; j++) 
	  if (region[i][j]) {
	    newmap[i][j] = region_count ;
	    bitmap[i][j] = region[i][j] = 0 ;
	  }

      region_count++ ;
    }
  } while (marked_pixel_found) ;

  printf("%d regions found.\n", region_count) ;
  
  /* read bitmap denoting borders and annotations */
  read_bitmap(border_fname, 0, &bitmap, &width2, &height2) ;

  if (width2 != width || height2 != height) {
    fprintf(stderr, "error - region bitmap must have same dimensions as border bitmap\n") ;
    exit(1) ;
  }

  for (i=0 ; i < height2 ; i++)
    for (j=0 ; j < width2 ; j++)
      if (bitmap[i][j]) newmap[i][j] = -1 ;

  save_map_rle2(output_fname, newmap, width, height, region_count) ;
}