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

// compressor (Golomb) for a sparse file, with many 0s and few 1s.
// Has one parameter m, which defines via M=2^m the typical number of consecutive 0s expected;

// The Golomb code can be viewed as an approximate arithmetic code

// usage: GolombEncode < filep.01.10000 > file.GZ

// (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/

#include "Gdefns.h"

void dec_to_bin(int,int);

int main( int argc , char *argv[] ){
  FILE *fp;
  int r;                 // counts the number of zeroes in the current block

  int c , tot0 = 0 , tot1 = 0  ;

  fp=stdin;
  r = 0 ; 
  while( (c=getc(fp)) != EOF ) {
    if( c == '0' ) {
      tot0 ++ ;
      r++ ;
      if( r>= MGolomb ) {
	printf("1");  // sending "1" encodes "0"xM
	r = 0 ;
      }
    } else if ( c=='1' ) {
      tot1 ++ ;
      printf("0");  // sending "0" encodes the fact that, next, there are fewer than Mx"0" on the way, followed by a "1"
      // print out current value of r using m bits
      dec_to_bin( r , mGolomb ) ; // sending "r" in binary encodes  "0"xr followed by 1.
      r = 0 ;
    } else {
      // we ignore carriage returns, etc
    } 
  }
  // To make a self-delimiting file, we need to send the final value of r, and have the receiver
  // know to remove the final "1".  As encoder, we act as if an extra '1' were received.
  printf("0");  
  dec_to_bin( r , mGolomb ) ; 

  fprintf(stderr,"\nShannon information content of the file is %d log(f) + %d log(1-f) = %8.3f\n",tot0,tot1, (tot0*log(0.99)+tot1*log(0.01))/log(0.5) ) ; 
  //  fprintf(stderr,"Decompress with GolombDecode %d < filename\n",tot0+tot1 ) ; 

  return(0);
}


/* 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);
   }
   //   printf("\n");
}