#!/usr/bin/perl -w
# sort_sbox_params.pl - Don Yang (uguu.org)
#
# Assign sbox parameters to each moon phase:
#  - assign the strongest sboxes first.
#  - assign to each moon phase in round robin.
#
# Initially, we would assign all the sboxes for a single moon phase
# first, with full moon getting 16 strongest sboxes, waning gibbous
# getting the next 16 and so on.  Because strong sboxes tend to have
# similar configuations, this resulted in many similar sboxes for a
# single moon phase, which is bad.  By assigning to each moon phase in
# round robin, we eliminate the weakness caused by similar sboxes.
#
# 06/20/12

use strict;

# Convert sbox parameters to actual sbox data
sub GenerateSbox($$$)
{
   my ($o1, $o2, $o3) = @_;
   my @sbox;

   $#sbox = 255;
   for(my $i = 0; $i < 256; $i++)
   {
      my $j = (($i + $o1) & 0x7f) | ($i & 0x80);
      $j = ((($j >> 1) + $o2) & 0x7f) | (($j << 7) & 0x80);
      $j = ((($j >> 1) + $o3) & 0x7f) | (($j << 7) & 0x80);
      $sbox[$i] = $j;
   }

   for(my $iteration = 0; $iteration < 2; $iteration++)
   {
      for(my $bit = 0; $bit < 8; $bit++)
      {
         for(my $i = 0; $i < 256; $i++)
         {
            my $diff = $sbox[$i] ^ $sbox[$i ^ (1 << $bit)];
            if( ($diff & ($diff - 1)) == 0 )
            {
               my $j = $i ^ (1 << (($bit + 1) % 8));
               my $tmp = $sbox[$i];
               $sbox[$i] = $sbox[$j];
               $sbox[$j] = $tmp;
            }
         }
      }
   }

   return join '', map { chr($_) } @sbox;
}

# Compare two sbox strings and return number of characters that matched
sub SharedCharacterCount($$)
{
   my ($a, $b) = @_;

   die unless (length($a) == length($b));
   my $count = 0;
   for(my $i = 0; $i < length($a); $i++)
   {
      $count++ if( substr($a, $i, 1) eq substr($b, $i, 1) );
   }
   return $count;
}

# Load sbox parameters
my %params;
foreach my $line (<DATA>)
{
   next unless $line =~ /distance=(\d+)/;
   $params{$line} = $1;
}
die if( (scalar keys %params) != 144 );

# Convert parameters to actual sboxes
my %sbox;
foreach my $line (keys %params)
{
   $line =~ /0x([[:xdigit:]]{2}), 0x([[:xdigit:]]{2}), 0x([[:xdigit:]]{2})/
      or die;
   $sbox{$line} = GenerateSbox(hex($1), hex($2), hex($3));
}

# Generate reverse mapping from sbox to parameters.  This is so that
# we can operate on the sboxes directly instead of the parameters.
my %sbox_to_params;
foreach (keys %params)
{
   $sbox_to_params{$sbox{$_}} = $_;
}

# Sort sbox parameters by bit distance
my @sorted_sboxes;
#foreach my $i (sort {CompareParams(\%params, $a, $b)} keys %params)
foreach my $i (sort {$params{$b} <=> $params{$a} || $a cmp $b} keys %params)
{
   push @sorted_sboxes, $sbox{$i}
}

# Group sboxes by moon phases
my @schedule = (4, 5, 3, 6, 2, 7, 1, 0, 8);
my @phases = ([], [], [], [], [], [], [], [], []);
for(my $i = 0; $i <= $#sorted_sboxes; $i++)
{
   push @{$phases[$schedule[$i % 9]]}, $sorted_sboxes[$i];
}

# At this point, we will have some adjacent sboxes that are similar.
# Swap with the sbox few steps away if we see those.
for(my $delta = 10; $delta > 3; $delta--)
{
   for(my $i = 0; $i < 9; $i++)
   {
      for(my $j = 0; $j < 16; $j++)
      {
         my $c1 = SharedCharacterCount($phases[$i][$j],
                                       $phases[$i][($j + 1) % 16]);
         my $c2 = SharedCharacterCount($phases[$i][$j],
                                       $phases[$i][($j + 2) % 16]);
         if( $c1 > 0 || $c2 > 0 )
         {
            my $tmp = $phases[$i][($j + 1) % 16];
            $phases[$i][($j + 1) % 16] = $phases[$i][($j + $delta) % 16];
            $phases[$i][($j + $delta) % 16] = $tmp;
         }
      }
   }
}

# Output sorted parameters
my @phase_name =
(
   "new moon",
   "waxing crescent",
   "first quarter",
   "waxing gibbous",
   "full moon",
   "waning gibbous",
   "last quarter",
   "waning crescent",
   "init key"
);
for(my $i = 0; $i < 9; $i++)
{
   print "   /* {{{ $phase_name[$i] */\n";
   for(my $j = 0; $j < 16; $j++)
   {
      printf '   /* %3d ',
             SharedCharacterCount($phases[$i][$j], $phases[$i][($j + 1) % 16]);
      foreach my $k (unpack 'C*', $phases[$i][$j])
      {
         printf '%02x', $k;
      }
      print " */\n";
   }

   foreach my $j (@{$phases[$i]})
   {
      print $sbox_to_params{$j};
   }
   print "   /* }}} */\n";
}


__DATA__
   /* {{{ new moon */
   {0x39, 0x03, 0x2a},  /* hash=6a0b0992, distance=6596 */
   {0x7d, 0x25, 0x34},  /* hash=7becdd4b, distance=6580 */
   {0x65, 0x67, 0x34},  /* hash=1e9191dd, distance=6580 */
   {0x19, 0x71, 0x46},  /* hash=b80744a2, distance=6580 */
   {0x17, 0x32, 0x1e},  /* hash=b39c35b9, distance=6572 */
   {0x25, 0x63, 0x2b},  /* hash=dfd35473, distance=6568 */
   {0x0b, 0x64, 0x28},  /* hash=adb059e0, distance=6564 */
   {0x0f, 0x18, 0x5d},  /* hash=053559d5, distance=6548 */
   {0x25, 0x65, 0x2a},  /* hash=63eed4aa, distance=6544 */
   {0x61, 0x6d, 0x2b},  /* hash=59c587a8, distance=6540 */
   {0x0f, 0x56, 0x53},  /* hash=e5dd4cb3, distance=6540 */
   {0x2d, 0x28, 0x78},  /* hash=8b7be84b, distance=6536 */
   {0x2d, 0x65, 0x6c},  /* hash=3734923c, distance=6532 */
   {0x1d, 0x65, 0x51},  /* hash=76e27ee2, distance=6528 */
   {0x27, 0x27, 0x7a},  /* hash=049444ff, distance=6524 */
   {0x1d, 0x6d, 0x6b},  /* hash=bb03f1b2, distance=6524 */
   /* }}} */
   /* {{{ waxing crescent */
   {0x19, 0x33, 0x5a},  /* hash=257a5645, distance=6692 */
   {0x19, 0x33, 0x1a},  /* hash=8bbbf057, distance=6692 */
   {0x33, 0x20, 0x4d},  /* hash=d3720c35, distance=6684 */
   {0x2b, 0x50, 0x73},  /* hash=098591dc, distance=6684 */
   {0x29, 0x2a, 0x78},  /* hash=280d4419, distance=6680 */
   {0x21, 0x20, 0x7e},  /* hash=7a697b92, distance=6672 */
   {0x31, 0x57, 0x7d},  /* hash=26075aa7, distance=6668 */
   {0x7b, 0x26, 0x34},  /* hash=fe699e3f, distance=6664 */
   {0x17, 0x34, 0x1d},  /* hash=70544fe6, distance=6652 */
   {0x2b, 0x4e, 0x74},  /* hash=8722bedc, distance=6640 */
   {0x1f, 0x62, 0x14},  /* hash=45b53bc5, distance=6640 */
   {0x3f, 0x5a, 0x36},  /* hash=a5bb61ad, distance=6632 */
   {0x0f, 0x52, 0x55},  /* hash=24bcc7ce, distance=6612 */
   {0x37, 0x02, 0x2b},  /* hash=20877095, distance=6608 */
   {0x2b, 0x29, 0x78},  /* hash=d29ab3e5, distance=6608 */
   {0x51, 0x67, 0x6a},  /* hash=6a5f17e4, distance=6600 */
   /* }}} */
   /* {{{ first quarter */
   {0x63, 0x2c, 0x5b},  /* hash=67747759, distance=6948 */
   {0x63, 0x2c, 0x1b},  /* hash=99342772, distance=6948 */
   {0x05, 0x7b, 0x6b},  /* hash=12aafdfc, distance=6944 */
   {0x03, 0x2e, 0x12},  /* hash=43814063, distance=6940 */
   {0x01, 0x21, 0x19},  /* hash=2c8552e4, distance=6936 */
   {0x61, 0x2d, 0x5b},  /* hash=b050c6b0, distance=6932 */
   {0x15, 0x57, 0x52},  /* hash=76e27807, distance=6924 */
   {0x0b, 0x76, 0x6c},  /* hash=8ceeb704, distance=6920 */
   {0x1d, 0x6d, 0x24},  /* hash=c5eda54f, distance=6912 */
   {0x63, 0x2e, 0x5a},  /* hash=6891e21e, distance=6904 */
   {0x63, 0x2e, 0x1a},  /* hash=b45e012f, distance=6904 */
   {0x65, 0x2b, 0x5b},  /* hash=e4f78abd, distance=6900 */
   {0x05, 0x0e, 0x0f},  /* hash=2ac77068, distance=6900 */
   {0x3f, 0x3e, 0x5b},  /* hash=1106b3f0, distance=6896 */
   {0x33, 0x20, 0x1d},  /* hash=d044f2a8, distance=6884 */
   {0x33, 0x22, 0x1c},  /* hash=c56b1df2, distance=6880 */
   /* }}} */
   /* {{{ waxing gibbous */
   {0x7b, 0x50, 0x6e},  /* hash=f4de5be0, distance=7428 */
   {0x01, 0x63, 0x57},  /* hash=172e0b6a, distance=7408 */
   {0x01, 0x43, 0x31},  /* hash=e323108b, distance=7400 */
   {0x01, 0x41, 0x32},  /* hash=f91756ff, distance=7376 */
   {0x3b, 0x7e, 0x14},  /* hash=a3d60663, distance=7356 */
   {0x7f, 0x4e, 0x1e},  /* hash=58b5736c, distance=7344 */
   {0x09, 0x49, 0x2b},  /* hash=c5cfd3d1, distance=7324 */
   {0x01, 0x4f, 0x1d},  /* hash=44043def, distance=7320 */
   {0x79, 0x43, 0x75},  /* hash=5f210841, distance=7304 */
   {0x03, 0x4c, 0x1e},  /* hash=005bdc60, distance=7304 */
   {0x2f, 0x36, 0x3e},  /* hash=731fd2f1, distance=7284 */
   {0x79, 0x41, 0x76},  /* hash=fd65a4e5, distance=7280 */
   {0x25, 0x0b, 0x13},  /* hash=816497ba, distance=7248 */
   {0x39, 0x1b, 0x2d},  /* hash=d68a250a, distance=7204 */
   {0x75, 0x27, 0x52},  /* hash=c1f4cc40, distance=7172 */
   {0x07, 0x78, 0x54},  /* hash=edfd5b8f, distance=7164 */
   /* }}} */
   /* {{{ full moon */
   {0x77, 0x3c, 0x29},  /* hash=39d39a27, distance=8112 */
   {0x11, 0x37, 0x75},  /* hash=560e6bc7, distance=8060 */
   {0x15, 0x35, 0x75},  /* hash=c0829a07, distance=8004 */
   {0x2f, 0x6c, 0x23},  /* hash=b4a00f10, distance=7988 */
   {0x77, 0x42, 0x26},  /* hash=d5129faf, distance=7976 */
   {0x59, 0x63, 0x1d},  /* hash=bd3b8f88, distance=7924 */
   {0x23, 0x03, 0x7b},  /* hash=42909f79, distance=7924 */
   {0x79, 0x41, 0x26},  /* hash=0bc0b652, distance=7920 */
   {0x5b, 0x62, 0x1d},  /* hash=f9f1b928, distance=7920 */
   {0x2b, 0x7b, 0x7d},  /* hash=a8d43d04, distance=7888 */
   {0x09, 0x3b, 0x75},  /* hash=0218e910, distance=7884 */
   {0x75, 0x53, 0x1e},  /* hash=b76a6525, distance=7872 */
   {0x2d, 0x6d, 0x23},  /* hash=3b719c89, distance=7860 */
   {0x77, 0x4c, 0x21},  /* hash=780a801e, distance=7792 */
   {0x71, 0x76, 0x5a},  /* hash=ce12da49, distance=7696 */
   {0x03, 0x36, 0x29},  /* hash=c0b0c4da, distance=7692 */
   /* }}} */
   /* {{{ waning gibbous */
   {0x3f, 0x10, 0x0b},  /* hash=414eb2d2, distance=7668 */
   {0x7d, 0x2e, 0x1b},  /* hash=a036b5d1, distance=7648 */
   {0x01, 0x53, 0x6b},  /* hash=212f09ba, distance=7648 */
   {0x0f, 0x08, 0x4b},  /* hash=63425794, distance=7644 */
   {0x0b, 0x0a, 0x4b},  /* hash=3a3c870f, distance=7644 */
   {0x11, 0x07, 0x4b},  /* hash=b83bf0eb, distance=7612 */
   {0x21, 0x47, 0x69},  /* hash=9e0f944c, distance=7608 */
   {0x13, 0x06, 0x4b},  /* hash=7d870504, distance=7596 */
   {0x15, 0x03, 0x4c},  /* hash=923c6e6f, distance=7580 */
   {0x01, 0x3d, 0x76},  /* hash=27708e5b, distance=7564 */
   {0x3b, 0x14, 0x6a},  /* hash=8babb33c, distance=7508 */
   {0x29, 0x45, 0x2c},  /* hash=5e65b49a, distance=7496 */
   {0x27, 0x52, 0x12},  /* hash=de68322c, distance=7464 */
   {0x1f, 0x60, 0x5d},  /* hash=e10fb9f1, distance=7456 */
   {0x27, 0x54, 0x11},  /* hash=2895d8fe, distance=7448 */
   {0x7f, 0x3c, 0x77},  /* hash=7568fe1e, distance=7444 */
   /* }}} */
   /* {{{ last quarter */
   {0x2b, 0x38, 0x3e},  /* hash=74a03367, distance=7156 */
   {0x29, 0x4d, 0x52},  /* hash=ebcbd078, distance=7152 */
   {0x39, 0x19, 0x2e},  /* hash=92af8e65, distance=7140 */
   {0x7d, 0x1f, 0x54},  /* hash=d716568f, distance=7132 */
   {0x3b, 0x42, 0x79},  /* hash=f784cde4, distance=7128 */
   {0x37, 0x42, 0x2b},  /* hash=bc591a5b, distance=7128 */
   {0x15, 0x67, 0x52},  /* hash=58ac8290, distance=7128 */
   {0x3b, 0x40, 0x7a},  /* hash=f03dfbda, distance=7120 */
   {0x77, 0x26, 0x52},  /* hash=5c56e519, distance=7100 */
   {0x31, 0x17, 0x1d},  /* hash=fec020c4, distance=7080 */
   {0x03, 0x28, 0x15},  /* hash=344a9f81, distance=7064 */
   {0x77, 0x28, 0x51},  /* hash=ca576dd6, distance=7052 */
   {0x37, 0x42, 0x7a},  /* hash=47c5cf56, distance=7016 */
   {0x6b, 0x46, 0x24},  /* hash=33f7fcb2, distance=6972 */
   {0x17, 0x70, 0x54},  /* hash=95728891, distance=6968 */
   {0x15, 0x71, 0x54},  /* hash=d58c4f54, distance=6968 */
   /* }}} */
   /* {{{ waning crescent */
   {0x17, 0x20, 0x54},  /* hash=018675ee, distance=6876 */
   {0x01, 0x27, 0x16},  /* hash=dc8a6e3b, distance=6876 */
   {0x11, 0x1b, 0x71},  /* hash=3379eaaa, distance=6872 */
   {0x01, 0x1f, 0x1a},  /* hash=d5c483fb, distance=6856 */
   {0x65, 0x43, 0x66},  /* hash=c45b253f, distance=6848 */
   {0x11, 0x19, 0x72},  /* hash=548aa655, distance=6848 */
   {0x0f, 0x64, 0x27},  /* hash=a965128d, distance=6820 */
   {0x3b, 0x1e, 0x5d},  /* hash=353f69a3, distance=6800 */
   {0x39, 0x1d, 0x5e},  /* hash=69c8f1b9, distance=6800 */
   {0x05, 0x6b, 0x2c},  /* hash=38b335fe, distance=6800 */
   {0x3b, 0x1c, 0x5e},  /* hash=cc9ea3a6, distance=6760 */
   {0x39, 0x57, 0x7b},  /* hash=8346edcc, distance=6720 */
   {0x3b, 0x56, 0x7b},  /* hash=546b3c6b, distance=6704 */
   {0x19, 0x31, 0x5b},  /* hash=645fc37b, distance=6704 */
   {0x19, 0x31, 0x1b},  /* hash=01d2acde, distance=6704 */
   {0x1b, 0x64, 0x62},  /* hash=ea032e22, distance=6700 */
   /* }}} */
   /* {{{ init key */
   {0x2f, 0x27, 0x78},  /* hash=8adfdb54, distance=6512 */
   {0x3d, 0x7d, 0x2c},  /* hash=ace0f30a, distance=6504 */
   {0x1b, 0x2e, 0x6c},  /* hash=00bad9ae, distance=6504 */
   {0x03, 0x00, 0x02},  /* hash=9f06e9cd, distance=6500 */
   {0x03, 0x10, 0x12},  /* hash=22981514, distance=6496 */
   {0x3d, 0x15, 0x61},  /* hash=c66185db, distance=6488 */
   {0x09, 0x6d, 0x0d},  /* hash=7cfc6195, distance=6488 */
   {0x23, 0x60, 0x2d},  /* hash=aea06549, distance=6484 */
   {0x3d, 0x13, 0x62},  /* hash=026e0bfb, distance=6480 */
   {0x31, 0x26, 0x78},  /* hash=80c6ff25, distance=6480 */
   {0x03, 0x03, 0x01},  /* hash=e7709dee, distance=6480 */
   {0x17, 0x0e, 0x27},  /* hash=5a78885d, distance=6472 */
   {0x3f, 0x7c, 0x2c},  /* hash=e95081bd, distance=6464 */
   {0x33, 0x28, 0x25},  /* hash=f2a77991, distance=6464 */
   {0x7b, 0x50, 0x5a},  /* hash=e11bc694, distance=6456 */
   {0x63, 0x6c, 0x2e},  /* hash=82840f2e, distance=6456 */
   /* }}} */