use strict;
use warnings;
$|=1;
#
#   * problem: when converting nA digit base A number
#     to base B, it will have nB digits
#          where nB= ceil( nA*log(A)/log(B) )
#     when converting back, it will happen that nA+1 > ceil( nB*log(B)/log(A) ) > nA
#     thus losing the information on how long the original packet was.
#
# for smses this should not be a problem, we have a fixed message length.
# sending 94 possible ascii chars -> we can send fixed length 131 byte data packets.

=cut

9 / 1234567 \ 0137174
    0   = int(1/9)*9
   --
    12
     9  = int(12/9)*9
    --
     33
     27 = int(33/9)*9
     --
      64
      63 = int(64/9)*9
      --
       15
        9
       --
        66
        63
        --
         37
         36
         --
          1

=cut

# divides a big 'a' by a small 'b'
# 'a' is stored in base 'base', most significant digit first
sub bigdiv {
    my ($a, $b, $base)= @_;

    my @q;

    my $val= 0;
    for my $digit (@$a) {

        $val= $val * $base + $digit;

        #push @s, $val;

        push @q, int($val/$b);

        $val %= $b;
    }

#   printf("%s / %s \ %s\n", $b, join("",reverse @$a), join("",@q));
#   for (0..$#s-1) {
#       printf("%*d\n", $_+5, $b*$q[$_]);
#       printf("%*s\n", $_+5, "--");
#       printf("%*d\n", $_+6, $s[$_+1]);
#   }
#   printf("%*d\n", $#s+5, $b*$q[-1]);
#   printf("%*s\n", $#s+5, "--");
#   printf("%*d\n", $#s+5, $val);

    #printf("bigdiv([%s] / %d : %d -> %d, [%s]\n",asstring($a), $b, $base, $val, asstring(\@q));
    return ($val, \@q);
}
# multiplies big 'a' by small 'b', and adds small 'c'
# 'a' is stored in base 'base', most significant digit first
sub bigmuladd {
    my ($a, $b, $c, $base)= @_;

    my @res;

    my $carry= $c;
    for (my $i=$#$a ; $i>=0 ; $i--) {
        my $val = $a->[$i]*$b + $carry;
        #printf("calc res[%d] = %d*%d+%d = %d\n", $#$a-$i, $a->[$#$a-$i], $b, $carry, $val);
        $carry=int($val/$base);
        push @res, $val%$base;
    }
    while ($carry) {
        my $val= $carry;
        $carry=int($val/$base);
        push @res, $val%$base;
    }
    #printf("bigmuladd([%s],%d,%d,%d) -> [%s]\n", asstring($a), $b, $c, $base, asstring([ reverse @res ]));
    return [ reverse @res ];
}
sub digitcount {
    my ($from, $to, $num)= @_;
    #printf("%d base %d digits  are  %g base %d digits\n", $num, $from, $num * log($to) / log($from), $to);
    my $ndigits= $num * log($from) / log($to);
    if ($ndigits>int($ndigits)) {
        return int($ndigits)+1;
    }
    else {
        return int($ndigits);
    }
}
sub convertbase_down {
    my ($num, $from, $to)= @_;

    my ($r,$q);
    $q= [ @$num ];
    my @converted;
    for (0..digitcount($from, $to, scalar @$num)-1)
    {
        ($r,$q)= bigdiv($q, $to, $from);

        push @converted, $r;
    }
#   if (@converted && $converted[-1]==0) {
#       pop @converted;
#   }

    #printf("%d downto %d: %s -> %s\n", $from, $to, asstring($num), asstring([ reverse @converted ]));
    return [ reverse @converted ];
}
sub convertbase_up {
    my ($num, $from, $to)= @_;
    my $up= [];

    for my $digit (@$num)
    {
        $up= bigmuladd($up, $from, $digit, $to);
    }
    my $wanteddigits= digitcount($from, $to, scalar @$num)-1;
    while (@$up < $wanteddigits) {
        unshift @$up,0;
    }
    #printf("%d upto %d: %s -> %s\n", $from, $to, asstring($num), asstring($up));
    return $up;
}
sub convertbase {
    my ($num, $from, $to)= @_;
    if ($from == $to) {
        return $num;
    }
    elsif ($from > $to) {
        return convertbase_down($num, $from, $to);
    }
    else {
        return convertbase_up($num, $from, $to);
    }
}
sub string2num {
    my $str= shift;
    return [ map { $_-33 } unpack("C*", $str) ];
}
sub num2string {
    my $num= shift;
    return pack("C*", map { $_+33 } @$num);
}
sub binary2num {
    my $str= shift;
    return [ unpack("C*", $str) ];
}
sub num2binary {
    my $num= shift;
    return pack("C*", @$num);
}


sub encode {
    my $dec= shift;
    return num2string(convertbase(binary2num($dec), 256,94));
}
sub decode {
    my $dec= shift;
    return num2binary(convertbase(string2num($dec), 94,256));
}
my $conv;

#$conv= convertbase([1,2,3,4,5,6,7], 10, 9); printf("%s\n", join("", @$conv));
#$conv= convertbase([7,6,5,4,3,2,1], 10, 9); printf("%s\n", join("", @$conv));

#$conv= convertbase([2,2,8,1,4,5,1]  , 9, 10); printf("%s\n", join("", @$conv));
#$conv= convertbase([1,5,3,5,5,6,7,1], 9, 10); printf("%s\n", join("", @$conv));

sub asstring {
    my $num= shift;
    return join(",", @$num);
}
sub fromstring {
    my $str= shift;
    return [ split /,/,$str ];
}
printf("[49,50,51,52] -> [%s] -> [%s]\n", asstring(convertbase(fromstring("49,50,51,52"),256,94)), asstring(convertbase(convertbase(fromstring("49,50,51,52"),256,94),94,256)));
#printf("bin 1234 -> [%s] -> [%s]\n", asstring(binary2num("1234")), asstring(convertbase(binary2num("1234"), 256, 94)));
#printf("str RSTU -> [%s] -> [%s]\n", asstring(string2num("RSTU")), asstring(convertbase(string2num("RSTU"), 94, 256)));


my @strlist= ("", "akjsddksahdkj", "1231293981732", "999999999", "~~~~~~~~", "!!!!!!!");
my @binlist= (@strlist, "\x00" x 4, "\x00\x01\x02\x01\x00", "\x00\x00\x00\xff\xff\xff");
print "testing string <-> num conversion\n";
for my $instr (@strlist) {
    my $num= string2num($instr);
    my $outstr= num2string($num);
    if ($instr ne $outstr) {
        printf("ERROR: [%-15s] : [%-15s]\n", asstring($num), $outstr);
    }
}
print "testing binary <-> num conversion\n";
for my $inbin (@binlist) {
    my $bnum= binary2num($inbin);
    my $outbin= num2binary($bnum);
    if ($inbin ne $outbin) {
        printf("ERROR: [%-15s] : [%-15s]\n", asstring($bnum), $outbin);
    }
}

print "testing encode / decode\n";
for my $inbin (@binlist) {
    my $str= encode($inbin);
    my $outbin= decode($str);
    if ($inbin ne $outbin) {
        printf("ERROR: [%s] -> '%s' : [%s]\n", unpack("H*",$inbin), $str, unpack("H*",$outbin));
    }
    #printf("%s -> %s\n", unpack("H*", $inbin), $str);
}

print "testing repeating binary chars\n";
for my $l (0..15) {
    for my $ch (0..255) {
        my $inbin= chr($ch) x $l;
        my $str= encode($inbin);
        my $outbin= decode($str);
        if ($inbin ne $outbin) {
            printf("ERROR: %02x x %2d: -> '%s' : [%s]\n", $ch, $l, $str, unpack("H*",$outbin));
        }
    }
}

my @squarelist= (4, 9, 16, 25, 36, 49, 81, 100, 121, 144, 169, 196, 225, 256);
my %x;
for my $inb ( "\x00\x01\x02\x03", "\x01\x01\x01", "\x02\x02\x02", "\x03\x02\x01\x00", "\x01\x02\x03\x04\x05\x06", "\x03\x03\x03\x03\x03\x03\x03") {
    my $innum= binary2num($inb);
    for my $from (@squarelist) {
        for my $to (@squarelist) {
            next if ($from == $to);

#           my $up1= convertbase_up($innum, $from, $to);
#           my $up2= convertbase_up($up1, $to, $from);
#           my $upb= num2binary($up2);
#           if ($upb ne $inb) {
#               printf("ERROR: %2d -> %2d up: [%s]   [%s]\n", $from, $to, asstring($up1), asstring($up2));
#           }

            my $n_d= convertbase_down($innum, $from, $to);
            my $n_u= convertbase_up($innum, $from, $to);
            my $n_dd= convertbase_down($n_d, $to, $from);
            my $n_du= convertbase_up($n_d, $to, $from);
            my $n_ud= convertbase_down($n_u, $to, $from);
            my $n_uu= convertbase_up($n_u, $to, $from);
            my $b_dd= num2binary($n_dd);
            my $b_du= num2binary($n_du);
            my $b_ud= num2binary($n_ud);
            my $b_uu= num2binary($n_uu);

            if ($b_dd ne $inb) {
                printf("ERROR:  [%s]:%d d [%s]:%d d [%s]:%d\n", 
                    asstring($innum), $from,
                    asstring($n_d), $to,
                    asstring($n_dd), $from);
            }
            else {
                printf("%d d %d d %d - [%s]\n", $from, $to, $from, asstring($innum));
                $x{dd}{$from}{$to}++;
            }
            if ($b_du ne $inb) {
                printf("ERROR:  [%s]:%d d [%s]:%d u [%s]:%d\n", 
                    asstring($innum), $from,
                    asstring($n_d), $to,
                    asstring($n_du), $from);
            }
            else {
                printf("%d d %d u %d - [%s]\n", $from, $to, $from, asstring($innum));
                $x{du}{$from}{$to}++;
            }
            if ($b_ud ne $inb) {
                printf("ERROR:  [%s]:%d u [%s]:%d d [%s]:%d\n", 
                    asstring($innum), $from,
                    asstring($n_u), $to,
                    asstring($n_ud), $from);
            }
            else {
                printf("%d u %d d %d - [%s]\n", $from, $to, $from, asstring($innum));
                $x{ud}{$from}{$to}++;
            }
            if ($b_uu ne $inb) {
                printf("ERROR:  [%s]:%d u [%s]:%d u [%s]:%d\n", 
                    asstring($innum), $from,
                    asstring($n_u), $to,
                    asstring($n_uu), $from);
            }
            else {
                printf("%d u %d u %d - [%s]\n", $from, $to, $from, asstring($innum));
                $x{uu}{$from}{$to}++;
            }
        }
    }
}

for my $y (@squarelist) {
    for my $x (@squarelist) {
        printf("%d", $x{uu}{$x}{$y}||0);
    }
    printf("   ");
    for my $x (@squarelist) {
        printf("%d", $x{ud}{$x}{$y}||0);
    }
    printf("\n");
}
printf("\n");
for my $y (@squarelist) {
    for my $x (@squarelist) {
        printf("%d", $x{du}{$x}{$y}||0);
    }
    printf("   ");
    for my $x (@squarelist) {
        printf("%d", $x{dd}{$x}{$y}||0);
    }
    printf("\n");
}