#include <stdio.h>

char cur_byte ;
int bit_count ;
int bit_index ;

#define add_new_bit(FP, VAL) { if (bit_index == 0) { cur_byte = getc((FP)) ; bit_index = 128 ; } (VAL) <<= 1 ; if ((cur_byte & bit_index) != 0) { (VAL) |= 1 ; } bit_index >>= 1 ; }

#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++ ; }

typedef struct _mapping_list_elem {
  int old ;
  int new ;
  struct _mapping_list_elem *next ;
} mapping_list_elem ;

typedef struct _run_length_val_list_elem {
  int run_length ;
  int val ;
  struct _run_length_val_list_elem *next ;
} run_length_val_list_elem ;

main(int argc, char **argv)
{
  char *rlefname, *mappingfname, *newrlefname ;
  FILE *fp1, *fp2, *fp3 ;
  mapping_list_elem *maplist, *new_item, *mle_temp ;
  run_length_val_list_elem *rlv_list, *new_rlv, *old_rlv ;
  char s[80] ;
  int run_length, old_region ;

  int w1, w2, cols, h1, h2, rows, region_bits, length_bits, i ;
  int count, val ;
  int num_regions ;

  rlefname = argv[1] ;
  mappingfname = argv[2] ;
  newrlefname = argv[3] ;

  fp1 = fopen(rlefname, "r") ;
  fp2 = fopen(mappingfname, "r") ;

  maplist = NULL ;

  while (!feof(fp2)) {
    fgets(s, 80, fp2) ;
    if (!feof(fp2)) {
      new_item = (mapping_list_elem *)malloc(sizeof(mapping_list_elem)) ;
      new_item->next = maplist ;
      sscanf(s, "%d %d", &(new_item->old), &(new_item->new)) ;
      maplist = new_item ;
    }
  }
  fclose(fp2) ;

  rlv_list = old_rlv = NULL ;
  w1 = getc(fp1) ; w2 = getc(fp1) ; cols = (w1 << 8) | w2 ;
  h1 = getc(fp1) ; h2 = getc(fp1) ; rows = (h1 << 8) | h2 ;
  region_bits = getc(fp1) ;
  length_bits = 0 ; i = cols-2 ;
  while (i != 0) { 
    i >>= 1 ; length_bits++ ;
  }
  cur_byte = bit_index = bit_count = 0 ;
  count = rows*cols ;
  while (count > 0) {
    run_length = 0 ; val = 0 ;
    for (i=0 ; i < region_bits ; i++) {
      add_new_bit(fp1, val) ;
    }
    for (i=0 ; i < length_bits ; i++) {
      add_new_bit(fp1, run_length) ;
    }

    val -= 1 ;
    run_length += 1 ;

    new_rlv = 
      (run_length_val_list_elem *)malloc(sizeof(run_length_val_list_elem)) ;
    new_rlv->val = val ;
    new_rlv->run_length = run_length ;
    new_rlv->next = NULL ;
    if (old_rlv == NULL) {
      old_rlv = new_rlv ;
      rlv_list = old_rlv ;
    }
    else {
      old_rlv->next = new_rlv ;
      old_rlv = new_rlv ;
    }

    count -= run_length ;
  }
  fclose(fp1) ;

  for (old_rlv = rlv_list ; old_rlv != NULL ; old_rlv = old_rlv->next) 
    for (mle_temp = maplist ; mle_temp != NULL ; mle_temp = mle_temp->next) {
      if (mle_temp->old == old_rlv->val) {
	old_rlv->val = mle_temp->new ;
	break ;
      }
    }

  num_regions = 0 ;
  for (old_rlv = rlv_list ; old_rlv != NULL ; old_rlv = old_rlv->next)
    if ((old_rlv->val)+2 > num_regions)
      num_regions = (old_rlv->val)+2 ;
  
  region_bits = 0 ;
  for (i = num_regions-1 ; i != 0 ; ) {
    i >>= 1 ;
    region_bits++ ;
  }

  fp3 = fopen(newrlefname, "w") ;

  fputc((char)(cols/256), fp3) ;
  fputc((char)(cols%256), fp3) ;
  fputc((char)(rows/256), fp3) ;
  fputc((char)(rows%256), fp3) ;
  fputc((char)region_bits, fp3) ;
  
  for (old_rlv = rlv_list ; old_rlv != NULL ; old_rlv = old_rlv->next) {
    for (i = 1 << (region_bits-1) ; i != 0 ; i >>= 1)
      put_bit(fp3, (((old_rlv->val)+1) & i) == 0 ? 0 : 1) ;

    for (i = 1 << (length_bits-1) ; i != 0 ; i >>= 1)
      put_bit(fp3, (((old_rlv->run_length)-1) & i) == 0 ? 0 : 1) ;
  }
  /* flush last byte */
  cur_byte <<= (8 - bit_count) ; fputc(cur_byte, fp3) ;
  
  fclose(fp3) ;

}