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

#define VERBOSE 0
#define NEWLINES 1

// run length compressor, "without explicit probabilistic model", for a sparse file.
// usage: IRL < ~mackay/compress/filep.01.10000 > file.IRLZ

// decoding usage: IRL -1 <  file.IRLZ > decoded

// compresses lengths of runs of 1s or 0s into a uniquely decodeable representation, C_alpha,
// as described in David MacKay's textbook,
//         Information Theory, Inference, and Learning Algorithms. (Ch 7: Codes for Integers)
//                                       http://www.inference.phy.cam.ac.uk/mackay/itila/

// (c) David J.C. MacKay
// License: GPL                                  http://www.gnu.org/copyleft/gpl.html

// Originates from:  http://www.inference.phy.cam.ac.uk/mackay/itprnn/code/c/compress/

void   print_encoded_alpha( int ) ;
void   alpha_decoder ( int ,   FILE * ) ;
void   dec_to_bin(int,int);

int main( int argc , char *argv[] ){
  FILE *fp;
  int r , N = 0 , encoding=1 ;
  int c , oc ; 
  fp=stdin;
  r = 1; 

  // Read encoding variable from command line
  if(argc>1) {
    sscanf(argv[argc-1], "%d", &encoding ) ;
  }

  if ( encoding >= 1 ) {
    fprintf(stderr,"ENCODING\n" ) ;
    
    while( (c=getc(fp)) != EOF ) {
      if ( N==0 ) {
	// print the very first character
	if( c == '1' ) {
	  printf("1");
	  N ++ ;
	} else if (c=='0') {
	  printf("0");
	  N ++ ;
	} else {
	  fprintf(stderr,"Error, first character is not 1 or 0\n");
	}
	if(VERBOSE) printf("[<-First digit]");
	oc = c ; 
      } else if( (c == '1' ) ||  (c=='0') ) {
	if ( c != oc ) {
	  print_encoded_alpha (r) ;
	  r = 1 ; 
	} else { r++   ; }
	oc = c ; 
	N ++ ;
      } else {
	// ignore carriage returns
      }
    }
    // print the final run length
    print_encoded_alpha (r) ;
  } else {
    fprintf(stderr,"DECODING\n" ) ;
    if ( (c=getc(fp)) != EOF ) {
      if( c == '1' ) {
	c=1;
      } else if (c=='0') {
	c=0;
      } else {
	fprintf(stderr,"Error, first character is not 1 or 0\n");
      }
      //      printf("%1d",c);
      alpha_decoder(c , fp );
    }
  }
  return(0);
}

/* examples:  prints 17 ( 10001 ) as 000010001
   and 63 ( 111111 ) as 00000111111 */
void   print_encoded_alpha ( int r ) {
  int c=0 , rc = r ;
  if(VERBOSE) printf("(%d)",r);
  while ( (r = (r >> 1)) >= 1) {
    printf("0");
    c ++ ;
  }
  dec_to_bin( rc , c+1 ) ;  // prints the standard binary representation of the number r
}

void   alpha_decoder ( int digit ,   FILE *fp ) {
  int h;
  int c=0 , tot  ;
  do {
    c=0 ;
    while( ( (h=getc(fp)) != EOF ) && h=='0' ) {
      c ++ ;
    } 
    if(VERBOSE) 
      printf("(%d bits to read)",c);
    // ok, we have just read a 1, that was the start of the integer
    if ( (h!=EOF) ) {
      tot = 1 ; 
      while(  (c > 0)  &&  ( (h=getc(fp)) != EOF )  ) {
	// bin2dec
	tot = tot * 2 + (( h=='1' ) ? 1: 0 ) ;
	c-- ;
      }
      if(VERBOSE) 
	printf("(printing %d copies of %d)",tot,digit);
      while ( tot > 0 ) {
	printf("%1d",digit);
	if(NEWLINES) 
	  printf("\n") ;
	tot -- ;
      }
      if(VERBOSE) 
	printf("\n");
      digit = 1-digit ;
    }
  } while    ( (h!=EOF) ) ;
}

/* n is the number to convert to binary */
/* digits is the number of bits you want */
void dec_to_bin(int n , int digits){
   int i=0 , b ;
   if(n<0) { fprintf(stderr,"warning, negative n not expected\n"); }
   for(i=digits-1;i>=0;i--) {
     b = (((1<<i)&n)>0) ? 1 : 0 ;
     printf("%d",b);
   }
   if(VERBOSE) 
     printf("\n") ;
}