/* sbox.c - Don Yang (uguu.org)

   Find substitution boxes.

   05/21/12
                                                                           */

#include<stdio.h>

#undef FIND_SBOX
#define SHOW_SBOX

typedef unsigned char Byte;
typedef unsigned int Word;

/* Convert a byte value to number of 1 bits set */
#define BITCOUNT(value)  \
   value = (value & 0x55) + ((value & 0xaa) >> 1);  \
   value = (value & 0x33) + ((value & 0xcc) >> 2);  \
   value = (value & 0x0f) + ((value & 0xf0) >> 4)

/* Rotate left */
#define ROTL32(value, r) \
   (((value) << r) | ((value) >> (32 - r)))

/* Swap sbox entries to minimize single bit dependencies.  For every
   output that single bit flip in input that resulted in single bit
   flip in output, swap with another entry by flipping another input
   bit.

   Empirically, it seems flipping the (N+1)%8 bit (as opposed to any
   bit higher than +1) seems to produced the best results.  Also,
   applying this function twice seems to make any sbox fulfill the
   single bit check.                                                 */
static void AdjustSingleBitDependencies(Byte *sbox)
{
   int bit, i, j, x;
   Byte current, neighbor, tmp;

   for(bit = 0; bit < 8; bit++)
   {
      for(i = 0; i < 256; i++)
      {
         current = sbox[i];
         neighbor = sbox[i ^ (1 << bit)];
         x = current ^ neighbor;

         /* Check if current differs from neighbor by 1 bit only.
            The following expression wouldn't work if x==0, but that
            is impossible due to how the sbox is constructed.        */
         if( (x & (x - 1)) == 0 )
         {
            j = i ^ (1 << ((bit + 1) % 8));
            tmp = sbox[i];
            sbox[i] = sbox[j];
            sbox[j] = tmp;
         }
      }
   }
}

/* Check if sbox is reversible, returns 0 if not */
static int IsReversible(const Byte *sbox)
{
   int i, output[256];
   for(i = 0; i < 256; i++)
      output[i] = 0;
   for(i = 0; i < 256; i++)
      output[sbox[i]]++;
   for(i = 0; i < 256; i++)
   {
      if( output[i] != 1 )
         return 0;
   }
   return 1;
}

/* Check if sbox contains no identity transformations, returns 0 if at
   least one entry translates to itself.  A good sbox should always
   translate all inputs to something different, anything left
   untranslated could be used as weak keys.                            */
static int HasNoIdentityEntries(const Byte *sbox)
{
   int i;
   for(i = 0; i < 256; i++)
   {
      if( sbox[i] == i )
         return 0;
   }
   return 1;
}

/* Assign equivalence groups to sbox entries */
static void GetSboxGroups(const Byte *sbox, int *equal)
{
   int i, j, k;

   for(i = 0; i < 256; i++)
      equal[i] = i;
   for(i = 0; i < 256; i++)
   {
      for(j = i; j != equal[j]; j = equal[j]);
      for(k = (int)sbox[i]; k != equal[k]; k = equal[k]);
      if( j < k )
         equal[k] = j;
      else
         equal[j] = k;
   }
   for(i = 0; i < 256; i++)
   {
      for(j = i; j != equal[j]; j = equal[j]);
      equal[i] = j;
   }
}

/* Count the number of different groups in a sbox.  A good sbox should
   only have a single equivalence group.                               */
static int GetSboxGroupCount(int *groups)
{
   int unique[256], count, i, j;

   for(i = 0; i < 256; i++)
      unique[i] = 0;
   count = 0;
   for(i = 0; i < 256; i++)
   {
      j = groups[i];
      if( unique[j] == 0 )
      {
         count++;
         unique[j] = 1;
      }
   }
   return count;
}

/* For any single bit flip in input byte, count the number of single
   output bit flips in single_bit_flips.  This number should be low
   (preferably 0) so that the cipher is less prone to differential
   cryptanalysis.  Returns 0 to reject the sbox if number is too high. */
static int HasFewSingleBitDependencies(const Byte *sbox)
{
   int i, j, x;
   Byte current, neighbor;

   for(i = 0; i < 256; i++)
   {
      current = sbox[i];
      for(j = 0; j < 8; j++)
      {
         neighbor = sbox[i ^ (1 << j)];
         x = current ^ neighbor;
         if( (x & (x - 1)) == 0 )
            return 0;
      }
   }
   return 1;
}

/* Same as HasFewSingleBitDependencies, but get the actual count
   instead of failing early, for debugging.                      */
static int GetSingleBitDependencies(const Byte *sbox)
{
   int single_bit_flip = 0;
   int i, j, x;
   Byte current, neighbor;

   for(i = 0; i < 256; i++)
   {
      current = sbox[i];
      for(j = 0; j < 8; j++)
      {
         neighbor = sbox[i ^ (1 << j)];
         x = current ^ neighbor;
         if( (x & (x - 1)) == 0 )
            ++single_bit_flip;
      }
   }
   return single_bit_flip;
}

/* Check for transition bias */
static int IsUnbiased(const Byte *sbox)
{
   int zero_to_zero, zero_to_one, one_to_zero, one_to_one;
   int bit, i, output;

   for(bit = 1; bit < 0x100; bit <<= 1)
   {
      zero_to_zero = zero_to_one = one_to_zero = one_to_one = 0;
      for(i = 0; i < 256; i++)
      {
         output = sbox[i];
         if( (i & bit) == 0 )
         {
            if( (output & bit) == 0 )
            {
               if( ++zero_to_zero > 64 )
                  return 0;
            }
            else
            {
               if( ++zero_to_one > 64 )
                  return 0;
            }
         }
         else
         {
            if( (output & bit) == 0 )
            {
               if( ++one_to_zero > 64 )
                  return 0;
            }
            else
            {
               if( ++one_to_one > 64 )
                  return 0;
            }
         }
      }
   }
   return 1;
}

/* Compute hash for sbox.  This is needed because after
   AdjustSingleBitDependencies, we tend to get several sboxes that are
   identical despite different input parameters.  This function
   computes a hash of the sbox so that we can easily filter out
   identical sboxes.

   Murmur3 is used to compute the hash here.
   http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp  */
static Word GetHash(const Byte *sbox)
{
   const Word c1 = 0xcc9e2d51;
   const Word c2 = 0x1b873593;
   Word h = 42;  /* seed */
   Word *data = (Word*)sbox;
   Word k;
   int i;

   for(i = 0; i < 64; i++)
   {
      k = *data++;
      k *= c1;
      k = ROTL32(k, 15);
      k *= c2;
      h ^= k;
      h = ROTL32(h, 13);
      h = h * 5 + 0xe6546b64;
   }
   h ^= h >> 16;
   h *= 0x85ebca6b;
   h ^= h >> 13;
   h *= 0xc2b2ae35;
   h ^= h >> 16;
   return h;
}

/* Check fitness and strength of this sbox and diagnoses to stdout */
static void TestSbox(const Byte *sbox)
{
   int equal_groups[256];

   if( IsReversible(sbox) == 0 )
   {
      puts("not reversible");
      return;
   }

   if( HasNoIdentityEntries(sbox) == 0 )
   {
      puts("identity");
      return;
   }

   if( HasFewSingleBitDependencies(sbox) == 0 )
   {
      printf("bit_dependencies=%d\n", GetSingleBitDependencies(sbox));
      return;
   }

   GetSboxGroups(sbox, equal_groups);
   if( GetSboxGroupCount(equal_groups) > 1 )
   {
      printf("group_count=%d\n", GetSboxGroupCount(equal_groups));
      return;
   }

   if( IsUnbiased(sbox) == 0 )
   {
      puts("biased");
      return;
   }

   printf("OK, hash=%08x\n", GetHash(sbox));
}

#ifdef FIND_SBOX
/* Find sbox seed parameters */
static void FindSbox(void)
{
   int offset1, offset2, offset3;
   int i, t;
   Byte sbox[256];

   for(offset1 = 0; offset1 < 0x80; offset1++)
   {
      for(offset2 = 0; offset2 < 0x80; offset2++)
      {
         for(offset3 = 0; offset3 < 0x80; offset3++)
         {
            for(i = 0; i < 256; i++)
            {
               t = ((i + offset1) & 0x7f) | (i & 0x80);
               t = (((t >> 1) + offset2) & 0x7f) | ((t << 7) & 0x80);
               t = (((t >> 1) + offset3) & 0x7f) | ((t << 7) & 0x80);
               sbox[i] = (Byte)(t & 0xff);
            }
            AdjustSingleBitDependencies(sbox);
            AdjustSingleBitDependencies(sbox);

            printf("0x%02x, 0x%02x, 0x%02x: ", offset1, offset2, offset3);
            TestSbox(sbox);
         }
      }
   }
}
#endif

#ifdef SHOW_SBOX
/* Get sum of all bit differences from all single bit flips */
static int GetSingleBitDistance(const Byte *sbox)
{
   int i, bit, diff, sum;
   Byte current, neighbor;

   sum = 0;
   for(i = 0; i < 256; i++)
   {
      for(bit = 1; bit < 0x100; bit <<= 1)
      {
         current = sbox[i];
         neighbor = sbox[i ^ bit];
         diff = current ^ neighbor;
         BITCOUNT(diff);
         sum += diff;
      }
   }
   return sum;
}

/* Output sboxes to stdout */
static const int params[][3] =
{
   {0x3f, 0x56, 0x3d},  /* hash=e2230364, distance=4936 */
   {0x21, 0x09, 0x7b},  /* hash=5984eef0, distance=5108 */
   {0x37, 0x5a, 0x3d},  /* hash=0519b512, distance=5192 */
   {0x01, 0x6d, 0x67},  /* hash=de12c6cb, distance=5204 */
   {0x0d, 0x5d, 0x1e},  /* hash=13fa7e9a, distance=5304 */
   {0x11, 0x5b, 0x1e},  /* hash=2cbbd2da, distance=5312 */
   {0x25, 0x61, 0x3e},  /* hash=1ea1a69f, distance=5344 */
   {0x21, 0x4b, 0x4a},  /* hash=4cffa1a4, distance=5360 */
   {0x31, 0x5f, 0x3c},  /* hash=ef6ceb78, distance=5360 */
   {0x19, 0x59, 0x1d},  /* hash=7a05cc44, distance=5368 */
   {0x37, 0x64, 0x38},  /* hash=5fb98c60, distance=5376 */
   {0x25, 0x69, 0x3a},  /* hash=e6126ba3, distance=5408 */
   {0x3b, 0x3c, 0x5f},  /* hash=d44e46ad, distance=5408 */
   {0x31, 0x63, 0x3a},  /* hash=54a47e90, distance=5412 */
   {0x19, 0x5b, 0x1c},  /* hash=12a0c91f, distance=5424 */
   {0x17, 0x5c, 0x1c},  /* hash=2e1ff8c9, distance=5432 */
   {0x15, 0x5d, 0x1c},  /* hash=f92a85f4, distance=5440 */
   {0x33, 0x62, 0x3a},  /* hash=af25660c, distance=5440 */
   {0x13, 0x60, 0x1b},  /* hash=fb895646, distance=5460 */
   {0x2b, 0x66, 0x3a},  /* hash=3d814d8e, distance=5464 */
   {0x29, 0x6b, 0x28},  /* hash=220e3c3d, distance=5480 */
   {0x11, 0x05, 0x31},  /* hash=b2d31b24, distance=5484 */
   {0x05, 0x6f, 0x7e},  /* hash=7009be74, distance=5524 */
   {0x39, 0x5b, 0x23},  /* hash=671b337c, distance=5528 */
   {0x05, 0x71, 0x7d},  /* hash=97e1bd32, distance=5548 */
   {0x01, 0x01, 0x76},  /* hash=a5b193f6, distance=5560 */
   {0x79, 0x69, 0x5c},  /* hash=e050f3fa, distance=5632 */
   {0x19, 0x35, 0x25},  /* hash=f37aeba7, distance=5664 */
   {0x6c, 0x3c, 0x73},  /* hash=7dbcaa76, distance=5672 */
   {0x05, 0x55, 0x53},  /* hash=fead0bfe, distance=5688 */
   {0x2c, 0x46, 0x66},  /* hash=22052b78, distance=5736 */
   {0x01, 0x4b, 0x69},  /* hash=d1307d86, distance=5744 */
   {0x22, 0x45, 0x33},  /* hash=fc032a73, distance=5760 */
   {0x26, 0x43, 0x33},  /* hash=3528a9b4, distance=5760 */
   {0x27, 0x5e, 0x2f},  /* hash=39062da8, distance=5760 */
   {0x2b, 0x60, 0x2d},  /* hash=8b7b0a9b, distance=5760 */
   {0x01, 0x49, 0x6a},  /* hash=6ca671b9, distance=5768 */
   {0x2f, 0x60, 0x2c},  /* hash=a6fea0a1, distance=5800 */
   {0x15, 0x6f, 0x0a},  /* hash=5a07c9af, distance=5812 */
   {0x59, 0x33, 0x62},  /* hash=0624a104, distance=5816 */
   {0x1c, 0x3c, 0x1f},  /* hash=d9b0238f, distance=5848 */
   {0x69, 0x3d, 0x33},  /* hash=4f52519c, distance=5848 */
   {0x01, 0x6c, 0x49},  /* hash=d4156e03, distance=5852 */
   {0x7f, 0x12, 0x3e},  /* hash=7ece8932, distance=5860 */
   {0x51, 0x2b, 0x74},  /* hash=c0ca9efc, distance=5872 */
   {0x3f, 0x5e, 0x77},  /* hash=897e0603, distance=5876 */
   {0x2f, 0x60, 0x38},  /* hash=5b273c24, distance=5884 */
   {0x2f, 0x00, 0x6a},  /* hash=126d69c5, distance=5904 */
   {0x41, 0x4b, 0x29},  /* hash=0157c466, distance=5916 */
   {0x11, 0x13, 0x56},  /* hash=fc1b5f22, distance=5936 */
   {0x3f, 0x23, 0x0e},  /* hash=283783a8, distance=5940 */
   {0x41, 0x49, 0x2a},  /* hash=6e561c6e, distance=5940 */
   {0x09, 0x61, 0x5c},  /* hash=11e90378, distance=5944 */
   {0x1d, 0x5d, 0x59},  /* hash=21bb4708, distance=5952 */
   {0x59, 0x67, 0x15},  /* hash=c6d15447, distance=5952 */
   {0x65, 0x47, 0x1d},  /* hash=847795d2, distance=5964 */
   {0x09, 0x63, 0x5b},  /* hash=641d61a4, distance=5968 */
   {0x5b, 0x32, 0x62},  /* hash=e40bd72b, distance=5976 */
   {0x35, 0x13, 0x36},  /* hash=dcbf0df1, distance=6000 */
   {0x09, 0x39, 0x03},  /* hash=23e04359, distance=6008 */
   {0x39, 0x5f, 0x36},  /* hash=1b109494, distance=6024 */
   {0x0b, 0x00, 0x73},  /* hash=8db0c7c9, distance=6036 */
   {0x65, 0x49, 0x1c},  /* hash=9c5e3879, distance=6040 */
   {0x2d, 0x67, 0x35},  /* hash=ddabd975, distance=6052 */
   {0x35, 0x5f, 0x37},  /* hash=86abd2d6, distance=6068 */
   {0x13, 0x7a, 0x74},  /* hash=069ffcfd, distance=6084 */
   {0x19, 0x2f, 0x59},  /* hash=dd62ab4e, distance=6088 */
   {0x0f, 0x1c, 0x34},  /* hash=ba18a50e, distance=6092 */
   {0x63, 0x48, 0x1d},  /* hash=21ae71be, distance=6092 */
   {0x21, 0x6d, 0x35},  /* hash=229d9012, distance=6096 */
   {0x37, 0x5e, 0x37},  /* hash=2ee86bdd, distance=6096 */
   {0x65, 0x4b, 0x1b},  /* hash=ea129957, distance=6124 */
   {0x35, 0x1e, 0x7b},  /* hash=baa23b73, distance=6128 */
   {0x2d, 0x41, 0x5a},  /* hash=b761045b, distance=6132 */
   {0x45, 0x17, 0x6a},  /* hash=e5213e4b, distance=6132 */
   {0x0d, 0x37, 0x03},  /* hash=3983da52, distance=6136 */
   {0x17, 0x30, 0x59},  /* hash=9cd32b0f, distance=6140 */
   {0x1f, 0x4e, 0x4e},  /* hash=535204c3, distance=6148 */
   {0x7d, 0x1d, 0x59},  /* hash=7453a06d, distance=6148 */
   {0x01, 0x71, 0x6e},  /* hash=11199551, distance=6152 */
   {0x23, 0x1f, 0x7f},  /* hash=61a9a0e8, distance=6152 */
   {0x05, 0x77, 0x6a},  /* hash=b93a66f2, distance=6172 */
   {0x1f, 0x32, 0x16},  /* hash=1aeea3fe, distance=6180 */
   {0x01, 0x73, 0x6d},  /* hash=49594366, distance=6184 */
   {0x51, 0x05, 0x36},  /* hash=cc0e36c0, distance=6184 */
   {0x07, 0x70, 0x6d},  /* hash=f37039ab, distance=6188 */
   {0x11, 0x6b, 0x0d},  /* hash=c85c61a0, distance=6188 */
   {0x15, 0x31, 0x59},  /* hash=4a19d302, distance=6204 */
   {0x05, 0x4b, 0x5a},  /* hash=b61561fb, distance=6208 */
   {0x11, 0x7d, 0x73},  /* hash=06927a84, distance=6216 */
   {0x31, 0x3f, 0x5a},  /* hash=d2508a69, distance=6216 */
   {0x7d, 0x1b, 0x5a},  /* hash=74b20184, distance=6220 */
   {0x3d, 0x11, 0x19},  /* hash=a9102f13, distance=6224 */
   {0x01, 0x1b, 0x19},  /* hash=c038e35f, distance=6228 */
   {0x01, 0x39, 0x25},  /* hash=3851842f, distance=6232 */
   {0x1f, 0x46, 0x06},  /* hash=e9136a38, distance=6232 */
   {0x23, 0x21, 0x7e},  /* hash=52a9d9ca, distance=6232 */
   {0x11, 0x61, 0x12},  /* hash=c67be79a, distance=6252 */
   {0x3f, 0x5c, 0x1c},  /* hash=1b989671, distance=6252 */
   {0x69, 0x6b, 0x2d},  /* hash=91056140, distance=6252 */
   {0x0b, 0x06, 0x7d},  /* hash=3e5e53a9, distance=6260 */
   {0x07, 0x1a, 0x5e},  /* hash=079a0aa6, distance=6268 */
   {0x3f, 0x6e, 0x6b},  /* hash=a1a0a77b, distance=6268 */
   {0x31, 0x3d, 0x5b},  /* hash=8f5c0d77, distance=6284 */
   {0x01, 0x6c, 0x38},  /* hash=89096da9, distance=6288 */
   {0x3f, 0x4c, 0x3d},  /* hash=113827fe, distance=6300 */
   {0x05, 0x1b, 0x2b},  /* hash=2e4a87dc, distance=6304 */
   {0x19, 0x0f, 0x56},  /* hash=0450727b, distance=6304 */
   {0x3f, 0x70, 0x6a},  /* hash=0de3428a, distance=6308 */
   {0x09, 0x1b, 0x2a},  /* hash=fc28e66d, distance=6312 */
   {0x2b, 0x5e, 0x51},  /* hash=0fcdb944, distance=6316 */
   {0x01, 0x6e, 0x37},  /* hash=6e1efc44, distance=6320 */
   {0x3b, 0x12, 0x19},  /* hash=18b35c3b, distance=6320 */
   {0x03, 0x7a, 0x73},  /* hash=fd0aa060, distance=6336 */
   {0x2d, 0x7d, 0x0c},  /* hash=17e154b1, distance=6336 */
   {0x29, 0x0f, 0x64},  /* hash=01c1796e, distance=6340 */
   {0x31, 0x4d, 0x02},  /* hash=4142fcbb, distance=6340 */
   {0x03, 0x78, 0x74},  /* hash=0e1bcbdc, distance=6344 */
   {0x2b, 0x0a, 0x5a},  /* hash=5bac570b, distance=6344 */
   {0x33, 0x3c, 0x5b},  /* hash=a7464ca5, distance=6344 */
   {0x35, 0x3b, 0x5b},  /* hash=ff50aff4, distance=6344 */
   {0x39, 0x11, 0x1e},  /* hash=549f57d1, distance=6352 */
   {0x3b, 0x7e, 0x33},  /* hash=439950ca, distance=6360 */
   {0x05, 0x73, 0x76},  /* hash=0a92ffe9, distance=6368 */
   {0x35, 0x29, 0x65},  /* hash=5f78cb74, distance=6368 */
   {0x05, 0x19, 0x2c},  /* hash=0de99915, distance=6392 */
   {0x1d, 0x13, 0x65},  /* hash=f9bdbf62, distance=6392 */
   {0x17, 0x54, 0x5d},  /* hash=984d87e9, distance=6396 */
   {0x35, 0x39, 0x5c},  /* hash=cf644db4, distance=6396 */
   {0x17, 0x1a, 0x63},  /* hash=e75f146b, distance=6412 */
   {0x09, 0x19, 0x2b},  /* hash=48fc07ef, distance=6416 */
   {0x33, 0x2a, 0x65},  /* hash=4a4f53c4, distance=6420 */
   {0x33, 0x25, 0x78},  /* hash=3e289ef0, distance=6424 */
   {0x17, 0x28, 0x1c},  /* hash=263f9704, distance=6428 */
   {0x1f, 0x64, 0x51},  /* hash=1831be5c, distance=6432 */
   {0x25, 0x11, 0x64},  /* hash=f0d52048, distance=6436 */
   {0x37, 0x64, 0x4b},  /* hash=90ad42f3, distance=6444 */
   {0x4d, 0x71, 0x35},  /* hash=b0a70d95, distance=6444 */
   {0x63, 0x6e, 0x2d},  /* hash=b9245105, distance=6448 */
   {0x1d, 0x15, 0x64},  /* hash=f26d421f, distance=6456 */
   {0x63, 0x6c, 0x2e},  /* hash=82840f2e, distance=6456 */
   {0x7b, 0x50, 0x5a},  /* hash=e11bc694, distance=6456 */
   {0x33, 0x28, 0x25},  /* hash=f2a77991, distance=6464 */
   {0x3f, 0x7c, 0x2c},  /* hash=e95081bd, distance=6464 */
   {0x17, 0x0e, 0x27},  /* hash=5a78885d, distance=6472 */
   {0x03, 0x03, 0x01},  /* hash=e7709dee, distance=6480 */
   {0x31, 0x26, 0x78},  /* hash=80c6ff25, distance=6480 */
   {0x3d, 0x13, 0x62},  /* hash=026e0bfb, distance=6480 */
   {0x23, 0x60, 0x2d},  /* hash=aea06549, distance=6484 */
   {0x09, 0x6d, 0x0d},  /* hash=7cfc6195, distance=6488 */
   {0x3d, 0x15, 0x61},  /* hash=c66185db, distance=6488 */
   {0x03, 0x10, 0x12},  /* hash=22981514, distance=6496 */
   {0x03, 0x00, 0x02},  /* hash=9f06e9cd, distance=6500 */
   {0x1b, 0x2e, 0x6c},  /* hash=00bad9ae, distance=6504 */
   {0x3d, 0x7d, 0x2c},  /* hash=ace0f30a, distance=6504 */
   {0x2f, 0x27, 0x78},  /* hash=8adfdb54, distance=6512 */
   {0x1d, 0x6d, 0x6b},  /* hash=bb03f1b2, distance=6524 */
   {0x27, 0x27, 0x7a},  /* hash=049444ff, distance=6524 */
   {0x1d, 0x65, 0x51},  /* hash=76e27ee2, distance=6528 */
   {0x2d, 0x65, 0x6c},  /* hash=3734923c, distance=6532 */
   {0x2d, 0x28, 0x78},  /* hash=8b7be84b, distance=6536 */
   {0x0f, 0x56, 0x53},  /* hash=e5dd4cb3, distance=6540 */
   {0x61, 0x6d, 0x2b},  /* hash=59c587a8, distance=6540 */
   {0x25, 0x65, 0x2a},  /* hash=63eed4aa, distance=6544 */
   {0x0f, 0x18, 0x5d},  /* hash=053559d5, distance=6548 */
   {0x0b, 0x64, 0x28},  /* hash=adb059e0, distance=6564 */
   {0x25, 0x63, 0x2b},  /* hash=dfd35473, distance=6568 */
   {0x17, 0x32, 0x1e},  /* hash=b39c35b9, distance=6572 */
   {0x19, 0x71, 0x46},  /* hash=b80744a2, distance=6580 */
   {0x65, 0x67, 0x34},  /* hash=1e9191dd, distance=6580 */
   {0x7d, 0x25, 0x34},  /* hash=7becdd4b, distance=6580 */
   {0x39, 0x03, 0x2a},  /* hash=6a0b0992, distance=6596 */
   {0x51, 0x67, 0x6a},  /* hash=6a5f17e4, distance=6600 */
   {0x2b, 0x29, 0x78},  /* hash=d29ab3e5, distance=6608 */
   {0x37, 0x02, 0x2b},  /* hash=20877095, distance=6608 */
   {0x0f, 0x52, 0x55},  /* hash=24bcc7ce, distance=6612 */
   {0x3f, 0x5a, 0x36},  /* hash=a5bb61ad, distance=6632 */
   {0x1f, 0x62, 0x14},  /* hash=45b53bc5, distance=6640 */
   {0x2b, 0x4e, 0x74},  /* hash=8722bedc, distance=6640 */
   {0x17, 0x34, 0x1d},  /* hash=70544fe6, distance=6652 */
   {0x7b, 0x26, 0x34},  /* hash=fe699e3f, distance=6664 */
   {0x31, 0x57, 0x7d},  /* hash=26075aa7, distance=6668 */
   {0x21, 0x20, 0x7e},  /* hash=7a697b92, distance=6672 */
   {0x29, 0x2a, 0x78},  /* hash=280d4419, distance=6680 */
   {0x2b, 0x50, 0x73},  /* hash=098591dc, distance=6684 */
   {0x33, 0x20, 0x4d},  /* hash=d3720c35, distance=6684 */
   {0x19, 0x33, 0x1a},  /* hash=8bbbf057, distance=6692 */
   {0x19, 0x33, 0x5a},  /* hash=257a5645, distance=6692 */
   {0x1b, 0x64, 0x62},  /* hash=ea032e22, distance=6700 */
   {0x19, 0x31, 0x1b},  /* hash=01d2acde, distance=6704 */
   {0x19, 0x31, 0x5b},  /* hash=645fc37b, distance=6704 */
   {0x3b, 0x56, 0x7b},  /* hash=546b3c6b, distance=6704 */
   {0x39, 0x57, 0x7b},  /* hash=8346edcc, distance=6720 */
   {0x3b, 0x1c, 0x5e},  /* hash=cc9ea3a6, distance=6760 */
   {0x05, 0x6b, 0x2c},  /* hash=38b335fe, distance=6800 */
   {0x39, 0x1d, 0x5e},  /* hash=69c8f1b9, distance=6800 */
   {0x3b, 0x1e, 0x5d},  /* hash=353f69a3, distance=6800 */
   {0x0f, 0x64, 0x27},  /* hash=a965128d, distance=6820 */
   {0x11, 0x19, 0x72},  /* hash=548aa655, distance=6848 */
   {0x65, 0x43, 0x66},  /* hash=c45b253f, distance=6848 */
   {0x01, 0x1f, 0x1a},  /* hash=d5c483fb, distance=6856 */
   {0x11, 0x1b, 0x71},  /* hash=3379eaaa, distance=6872 */
   {0x01, 0x27, 0x16},  /* hash=dc8a6e3b, distance=6876 */
   {0x17, 0x20, 0x54},  /* hash=018675ee, distance=6876 */
   {0x33, 0x22, 0x1c},  /* hash=c56b1df2, distance=6880 */
   {0x33, 0x20, 0x1d},  /* hash=d044f2a8, distance=6884 */
   {0x3f, 0x3e, 0x5b},  /* hash=1106b3f0, distance=6896 */
   {0x05, 0x0e, 0x0f},  /* hash=2ac77068, distance=6900 */
   {0x65, 0x2b, 0x5b},  /* hash=e4f78abd, distance=6900 */
   {0x63, 0x2e, 0x1a},  /* hash=b45e012f, distance=6904 */
   {0x63, 0x2e, 0x5a},  /* hash=6891e21e, distance=6904 */
   {0x1d, 0x6d, 0x24},  /* hash=c5eda54f, distance=6912 */
   {0x0b, 0x76, 0x6c},  /* hash=8ceeb704, distance=6920 */
   {0x15, 0x57, 0x52},  /* hash=76e27807, distance=6924 */
   {0x61, 0x2d, 0x5b},  /* hash=b050c6b0, distance=6932 */
   {0x01, 0x21, 0x19},  /* hash=2c8552e4, distance=6936 */
   {0x03, 0x2e, 0x12},  /* hash=43814063, distance=6940 */
   {0x05, 0x7b, 0x6b},  /* hash=12aafdfc, distance=6944 */
   {0x63, 0x2c, 0x1b},  /* hash=99342772, distance=6948 */
   {0x63, 0x2c, 0x5b},  /* hash=67747759, distance=6948 */
   {0x15, 0x71, 0x54},  /* hash=d58c4f54, distance=6968 */
   {0x17, 0x70, 0x54},  /* hash=95728891, distance=6968 */
   {0x6b, 0x46, 0x24},  /* hash=33f7fcb2, distance=6972 */
   {0x37, 0x42, 0x7a},  /* hash=47c5cf56, distance=7016 */
   {0x77, 0x28, 0x51},  /* hash=ca576dd6, distance=7052 */
   {0x03, 0x28, 0x15},  /* hash=344a9f81, distance=7064 */
   {0x31, 0x17, 0x1d},  /* hash=fec020c4, distance=7080 */
   {0x77, 0x26, 0x52},  /* hash=5c56e519, distance=7100 */
   {0x3b, 0x40, 0x7a},  /* hash=f03dfbda, distance=7120 */
   {0x15, 0x67, 0x52},  /* hash=58ac8290, distance=7128 */
   {0x37, 0x42, 0x2b},  /* hash=bc591a5b, distance=7128 */
   {0x3b, 0x42, 0x79},  /* hash=f784cde4, distance=7128 */
   {0x7d, 0x1f, 0x54},  /* hash=d716568f, distance=7132 */
   {0x39, 0x19, 0x2e},  /* hash=92af8e65, distance=7140 */
   {0x29, 0x4d, 0x52},  /* hash=ebcbd078, distance=7152 */
   {0x2b, 0x38, 0x3e},  /* hash=74a03367, distance=7156 */
   {0x07, 0x78, 0x54},  /* hash=edfd5b8f, distance=7164 */
   {0x75, 0x27, 0x52},  /* hash=c1f4cc40, distance=7172 */
   {0x39, 0x1b, 0x2d},  /* hash=d68a250a, distance=7204 */
   {0x25, 0x0b, 0x13},  /* hash=816497ba, distance=7248 */
   {0x79, 0x41, 0x76},  /* hash=fd65a4e5, distance=7280 */
   {0x2f, 0x36, 0x3e},  /* hash=731fd2f1, distance=7284 */
   {0x03, 0x4c, 0x1e},  /* hash=005bdc60, distance=7304 */
   {0x79, 0x43, 0x75},  /* hash=5f210841, distance=7304 */
   {0x01, 0x4f, 0x1d},  /* hash=44043def, distance=7320 */
   {0x09, 0x49, 0x2b},  /* hash=c5cfd3d1, distance=7324 */
   {0x7f, 0x4e, 0x1e},  /* hash=58b5736c, distance=7344 */
   {0x3b, 0x7e, 0x14},  /* hash=a3d60663, distance=7356 */
   {0x01, 0x41, 0x32},  /* hash=f91756ff, distance=7376 */
   {0x01, 0x43, 0x31},  /* hash=e323108b, distance=7400 */
   {0x01, 0x63, 0x57},  /* hash=172e0b6a, distance=7408 */
   {0x7b, 0x50, 0x6e},  /* hash=f4de5be0, distance=7428 */
   {0x7f, 0x3c, 0x77},  /* hash=7568fe1e, distance=7444 */
   {0x27, 0x54, 0x11},  /* hash=2895d8fe, distance=7448 */
   {0x1f, 0x60, 0x5d},  /* hash=e10fb9f1, distance=7456 */
   {0x27, 0x52, 0x12},  /* hash=de68322c, distance=7464 */
   {0x29, 0x45, 0x2c},  /* hash=5e65b49a, distance=7496 */
   {0x3b, 0x14, 0x6a},  /* hash=8babb33c, distance=7508 */
   {0x01, 0x3d, 0x76},  /* hash=27708e5b, distance=7564 */
   {0x15, 0x03, 0x4c},  /* hash=923c6e6f, distance=7580 */
   {0x13, 0x06, 0x4b},  /* hash=7d870504, distance=7596 */
   {0x21, 0x47, 0x69},  /* hash=9e0f944c, distance=7608 */
   {0x11, 0x07, 0x4b},  /* hash=b83bf0eb, distance=7612 */
   {0x0b, 0x0a, 0x4b},  /* hash=3a3c870f, distance=7644 */
   {0x0f, 0x08, 0x4b},  /* hash=63425794, distance=7644 */
   {0x01, 0x53, 0x6b},  /* hash=212f09ba, distance=7648 */
   {0x7d, 0x2e, 0x1b},  /* hash=a036b5d1, distance=7648 */
   {0x3f, 0x10, 0x0b},  /* hash=414eb2d2, distance=7668 */
   {0x03, 0x36, 0x29},  /* hash=c0b0c4da, distance=7692 */
   {0x71, 0x76, 0x5a},  /* hash=ce12da49, distance=7696 */
   {0x77, 0x4c, 0x21},  /* hash=780a801e, distance=7792 */
   {0x2d, 0x6d, 0x23},  /* hash=3b719c89, distance=7860 */
   {0x75, 0x53, 0x1e},  /* hash=b76a6525, distance=7872 */
   {0x09, 0x3b, 0x75},  /* hash=0218e910, distance=7884 */
   {0x2b, 0x7b, 0x7d},  /* hash=a8d43d04, distance=7888 */
   {0x5b, 0x62, 0x1d},  /* hash=f9f1b928, distance=7920 */
   {0x79, 0x41, 0x26},  /* hash=0bc0b652, distance=7920 */
   {0x23, 0x03, 0x7b},  /* hash=42909f79, distance=7924 */
   {0x59, 0x63, 0x1d},  /* hash=bd3b8f88, distance=7924 */
   {0x77, 0x42, 0x26},  /* hash=d5129faf, distance=7976 */
   {0x2f, 0x6c, 0x23},  /* hash=b4a00f10, distance=7988 */
   {0x15, 0x35, 0x75},  /* hash=c0829a07, distance=8004 */
   {0x11, 0x37, 0x75},  /* hash=560e6bc7, distance=8060 */
   {0x77, 0x3c, 0x29},  /* hash=39d39a27, distance=8112 */
   {0, 0, 0}
};
static void ShowSbox(void)
{
   int p, i, j;
   Byte sbox[256];

   for(p = 0; params[p][0] != 0; p++)
   {
      for(i = 0; i < 256; i++)
      {
         j = ((i + params[p][0]) & 0x7f) | (i & 0x80);
         j = (((j >> 1) + params[p][1]) & 0x7f) | ((j << 7) & 0x80);
         j = (((j >> 1) + params[p][2]) & 0x7f) | ((j << 7) & 0x80);
         sbox[i] = (Byte)(j & 0xff);
      }
      AdjustSingleBitDependencies(sbox);
      AdjustSingleBitDependencies(sbox);
      printf("{{{ o1=0x%02x, o2=0x%02x, o3=0x%02x, hash=%08x, distance=%d\n",
             params[p][0], params[p][1], params[p][2],
             GetHash(sbox), GetSingleBitDistance(sbox));
      for(i = 0; i < 256; i += 16)
      {
         for(j = 0; j < 16; j++)
            printf(" %02x", sbox[i + j]);
         putchar('\n');
      }
      puts("}}}");
   }
}
#endif

int main(void)
{
   #ifdef FIND_SBOX
      FindSbox();
   #endif
   #ifdef SHOW_SBOX
      ShowSbox();
   #endif
   return 0;
}