#! perl -wl

# Parse Cunningham Project base 2 tables

# Copyright 2017 Ken Takusagawa

# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.



#input file = pmain410

&process();

#or, the word of . as revealed to mankind in the language of pure mathematics


sub process {
die unless defined ($_=<>);chomp;
die unless &readheader();
die unless /^    Table 2-              Factorizations of 2\^n-1, n odd, n<\d+$/;
print "#$_";
undef$data;  #gratuitous
$suffix="-";
for(;;){
    die unless defined($_=<>);chomp;
    last if /\x0c    Table 2\+\(odd\)         Factorizations of 2\^n\+1, n odd, n<\d+$/;
    if (/^     /){
        #continuation
        die unless /^\s+([0-9*PC\. ]+\\?)$/;
        $data.=$1;

    } elsif (/^....\d/){
        if(defined$data){
            &output($n,$alg,$data);undef$data;
        }
        die "die $_" unless /^\s+(\d+)  (\([0-9,]+\))? *([0-9*PC. ]+\\?)$/;
        $n=$1;
        $alg=$2;
        $alg="" unless $alg;
        $data.=$3;
    } else {
        die "BAD1:'$_'";
    }
}
&output($n,$alg,$data);
s/^\x0c//;
print "#$_";
$suffix="+";
die unless &readheader();
undef$data;
for(;;){
    die unless defined($_=<>);chomp;
    last if /^\x0c    Table 2LM             Factorizations of 2\^n\+1, n=4k-2, n<\d+$/;
    if (/^     /){
        #continuation
        die unless /^\s+([0-9*PC\. ]+\\?)$/;
        $data.=$1;

    } elsif (/^....\d/){
        if(defined$data){
            &output($n,$alg,$data);undef$data;
        }
        die "die $_" unless /^\s+(\d+)  (\([0-9,]+\))? *([0-9*PC. ]+\\?)$/;
        $n=$1;
        $alg=$2;
        $alg="" unless $alg;
        $data.=$3;
    } else {
        die "BAD2:'$_'";
    }
}
&output($n,$alg,$data);
s/^\x0c//;
print "#$_";
die unless &readheader();
die unless defined($_=<>);chomp;
die unless $_ eq "    2   5";
print qq(2 $suffix [] 5);
die unless defined($_=<>);chomp;

die unless $_ eq "    6  (2) 13";
print qq(6 $suffix ["2"] 13);
undef$data;
for(;;){
    die unless defined($_=<>);chomp;
    if(/^.....L /){
        if (defined$data){
            &output($n,$alg,$data);undef$data;
        }
        die $_ unless /^\s+(\d+L) (\([0-9,LM]+\))?\s*(.*)/;
        $n=$1;
        $alg=$2;
        $alg="" unless $alg;
        $data=$3;
    } elsif(/^     M/){
        if (defined$data){
            &output($n,$alg,$data);undef$data;
        }
        die $_ unless ($alg,$data)=/^\s+M (\([0-9,LM]+\))?\s*(.*)/;
        $alg="" unless $alg;
        die unless $n =~ /(\d+)L/;
        $n="$1M";
    }
    elsif(/^     /){
        die unless /\s+(.*)/;
        $data.=$1;
    } else {
        last;
    }
}
&output($n,$alg,$data);
die unless $_ eq "";
die unless defined($_=<>);chomp;
die unless $_ eq "                 2^2h+1=L.M, L=2^h-2^k+1, M=2^h+2^k+1, h=2k-1.";
print "#$_";
die unless defined($_=<>);chomp;
die "BAD3:'$_'" unless /^\x0c    Table 2\+\(4k\)          Factorizations of 2\^n\+1, n=4k, n<=\d+$/;
s/^\x0c//;
print "#$_";
die unless &readheader();
undef$data;
for(;;){
    die unless defined($_=<>);chomp;
    last if /^\x0c    Table 3-              Factorizations of 3\^n-1, n odd, n</;
    if (/^     /){
        #continuation
        die unless /^\s+([0-9*PC\. ]+\\?)$/;
        $data.=$1;

    } elsif (/^....\d/){
        if(defined$data){
            &output($n,$alg,$data);undef$data;
        }
        die "die $_" unless /^\s+(\d+)  (\([0-9,]+\))? *([0-9*PC. ]+\\?)$/;
        $n=$1;
        $alg=$2;
        $alg="" unless $alg;
        $data.=$3;
    } else {
        die;
    }

}
&output($n,$alg,$data);
#print;
die unless &readheader();  #gratuitous
}


sub readheader(){
    my $line;
    return 0 unless defined($line=<>); chomp$line;
    return 0 unless $line eq "";
    return 0 unless defined($line=<>); chomp$line;
    return 0 unless $line eq "    n                                Prime Factors";
    return 1;
}



sub output1(){
    my $target=Math::BigInt->new(2);
    $target->bpow($n);
    $target->bsub(1);
    my($n,$alg,$data)=@_;
    for($data){
        s/\\//g;
        s/ //g;
        s/\.\././g;
        #s/\./ . /g;
        die unless /^[0-9PC\.*]+$/;
    }
    my @Factors=split /\./,$data;
    #my$popped="";
    #unless(@Factors==1){
    #    unless ($Factors[$#Factors] =~ /^[PC]\d+$/){
    #        pop@Factors;
    #        $popped=".";
    #    }
    #}
    my $fout;
    for(@Factors){
        $fout.=".";
        if (/^[PC]\d+$/){
            $fout.="~$_";
            next;
        }
        my$intrinsic="";
        if(/(.*)\*$/){
            $intrinsic="*";
            $_=$1;
        }
        my $f=Math::BigInt->new($_);
        die if($target % $f);
        $fout.=&tobase64($f); #destroys $f;
        #$fout.=$f;
        #$fout.=$intrinsic;  omit intrinsic
    }
    #$fout.=$popped;
    print "$n $alg $fout";
}
sub tobase64{
    my($x)=shift;
    my$out="";
    my@base64=('A'..'Z','a'..'z','0'..'9','+','/');
    while($x>0){
        @qr=$x->bdiv(64);
        #push @out,$qr[1];
        $out=$base64[$qr[1]].$out;
    }
    return $out;
}


sub output {
    my($n,$alg,$data)=@_;
    for($data){
        s/\\//g;
        s/ //g;
        s/\.\././g;
        #s/\./  /g;
        die unless /^[0-9PC\.*]+$/;
    }
    my @Factors=split /\./,$data;
    my $fout="";
    for(@Factors){
        $fout.=" ";
        if (/^[PC]\d+$/){
            $fout.="$_";
            next;
        }
        if(/(.*)\*$/){
            #$fout.="*"; #intrinsic
            $_=$1;
        }
        $fout.=$_;
    }
    if($alg){
        die unless $alg=~/^\(([0-9LM,]+)\)$/;
        my@G=split /,/,$1;
        $alg="";
        for(0..$#G){
            $alg.="," unless $_==0;
            $alg.=qq("$G[$_]");
        }
        $alg="[$alg]";
    }else{
        $alg="[]";
    }
    print "$n $suffix $alg $fout";
}