#!/usr/bin/perl -w
## position code for compression
##
## How well it works: 
##
## bits=14, multipleblocks=0: 1442
##
## bits=5: Achieves 931 bits on Neil's file.
## bits=6: Achieves 878 bits on Neil's file.
## bits=7: Achieves 903 bits on Neil's file.
## bits=8: Achieves 967 bits on Neil's file.
## bits=14: 1546  (ie all in one block, with a waste of 100 bits
##        used to convey the fact that there are 100 1 bits in the file)
##
## Method: 
##
## Divide data into blocks of size B
$bits=7;
## Encode the 1s positions into bytes
## If there are multiple blocks, 
##   precede every 1 by a "1" and every end of block by a "0".
##
## File length must be known somehow to receiver
$N=10000;
##
## usage:
##  position.p bits=6 ../filep.01.10000 > encoded.pos
##  position.p bits=6 decode=1 encoded.pos  > recovered
##  position.p bits=8 ../filep.01.10000 > encoded.pos
##  position.p bits=8 decode=1 encoded.pos  > recovered
##  position.p bits=14 ../filep.01.10000 > encoded.pos
##  position.p bits=14 decode=1 encoded.pos  > recovered
##  position.p multipleblocks=0 bits=14 ../filep.01.10000 > encoded.pos
##  position.p multipleblocks=0 bits=14 decode=1 encoded.pos  > recovered

$decode=0; ## are we decoding?
$v=1; ## verbose output?
$multipleblocks=1;

## read command-line options
eval "\$$1=\$2" while @ARGV && $ARGV[0]=~ /^(\w+)=(.*)/ && shift;

$B=1<<$bits;
print STDERR "B=$B\n" if($v);

$encode=1-$decode;
if($encode) {
    $i = 0 ; ## counts where we are in the block
    ## read a single character
    while(<>) {
	s/\s+//g; ## strip white space characters
	if( $_ eq "1" ) {
	    print "1\n" if ($multipleblocks) ; ## to say 'there is another 1 in this block'
	    &binary($i,$bits) ; ## send the details of the bit
	}
	$i ++ ; 
	if (($multipleblocks) && ($i>=$B)) {
	    print "0\n" ; ## to say 'a block has ended'
	    $i=0;
	}
    }
    ## finish the file.
    print "0\n"  if ($multipleblocks) ;
} else { # decode
    $offset=0;
    @output=(0)x$N ; # an array of B zeros
    if ($multipleblocks){ 
	while(<>) {
	    s/\s+//g;
	    if( $_ eq "1" ) {
		if ( ($i = &frombinary($bits)) > 0 ) {
		    $output[$i + $offset] = 1 ; 
		}
	    } else {
		$offset += $B ; 
	    }
	}
    } else {
	while ( ($i = &frombinary($bits)) > 0 ) {
	    $output[$i] = 1 ; 
	}
    }
    print join ( "\n" , @output )."\n" ;
}

## converts from binary (with length bits) back to an integer
sub frombinary {
    local($bits) = @_ ;
    $m=1; $ans=0;
    while(($bits>0) && ($_ = <>) ) {
	s/\s+//g;
	if( $_ eq "1" ) {
	    $ans += $m ;
	}
	$m *= 2 ; $bits--;
    }
    if($bits>0) {
	printf STDERR "end of file\n" if ($v) ;
	$ans = -1 ;
    }
    return $ans;
}
    
## converts a number i to binary with length bits
sub binary {
    local($i,$bits) = @_ ;
    while($bits>0) {
	$bits--;
	printf "%d" ,  $i%2;
	$i = $i / 2 ;
	print "\n" ;
    }
}