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

   Check that string encoded by sbox_params2.c is usable.

   06/08/12
                                                                           */

#include<stdio.h>

typedef unsigned char Byte;
typedef unsigned int Word;

const char *params =
#if 1
                                                                      "\nt\5DAJDqJn\6\23(Wn"
   ":P<b4\4,3,P+nh\13F"                                       "zXlH%BPU)|stX{\25""2z60;CPuO"
  "R 1D\25TT}44q,,\tLb6\5"                                  "fTbnj4Nt\14\10u\5R\6\n|>`H%\2~ "
  "&R8\nRZ\6j@c^@KR>\r4U~4=Cp"                            "Qqh\25""2&Z9*0,.*ox[Jlk4&T>F\30?H"
   "'\3P\t\2^\36SNvEX_3~1`&0J2:C"         "p6f28B$E\6f\24""3^\16EVnL`0`D#mb6UL{<xS4zmeL{sF6L"
   "&*1j\nFh\r5,8\3^DMjh\14tu3jTaF" "fLrv5jVb$1J28\2R\25\31@!mx<`.X\6@\riZr0vD\nX-mZ\34Sz?`2"
   ":\3v1bhActs2@\21S\0qrvB\tTms~z;`\1\5T\30\27@\17j|{;l\5zH'Cz.&`AeJ8tPY\5^r?\40`Bh\17""6*F"
   "v0{3B\20SJrzr\25cR\26\32F\"\5P7\1&>IHg^(Umn(Cb>=(W>P1\16j\2rPW*t\35\13fT3DgLZ`tPEsj\10EzF"
   "knL.F$\6LsIl\3y*FB";
#else
"\nt\5DAJDqJn\6\23(Wn:P<b4\4,3,P+nh\13FzXlH%BPU)|stX{\25""2z60;CPuOR 1D\25TT}44q,,\tLb6\5fTbnj4Nt\14\10u\5R\6\n|>`H%\2~ &R8\nRZ\6j@c^@KR>\r4U~4=CpQqh\25""2&Z9*0,.*ox[Jlk4&T>F\30?H'\3P\t\2^\36SNvEX_3~1`&0J2:Cp6f28B$E\6f\24""3^\16EVnL`0`D#mb6UL{<xS4zmeL{sF6L&*1j\nFh\r5,8\3^DMjh\14tu3jTaFfLrv5jVb$1J28\2R\25\31@!mx<`.X\6@\riZr0vD\nX-mZ\34Sz?`2:\3v1bhActs2@\21S\0qrvB\tTms~z;`\1\5T\30\27@\17j|{;l\5zH'Cz.&`AeJ8tPY\5^r? `Bh\17""6*Fv0{3B\20SJrzr\25cR\26\32F\"\5P7\1&>IHg^(Umn(Cb>=(W>P1\16j\2rPW*t\35\13fT3DgLZ`tPEsj\10EzFknL.F$\6LsIl\3y*FB";
#endif

/* Reduce bit dependencies */
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;

         if( (x & (x - 1)) == 0 )
         {
            j = i ^ (1 << ((bit + 1) % 8));
            tmp = sbox[i];
            sbox[i] = sbox[j];
            sbox[j] = tmp;
         }
      }
   }
}

/* Initialize sbox from 3 offset parameters */
static void InitSbox(int offset1, int offset2, int offset3, Byte *sbox)
{
   int i, j;

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

/* Get number of equivalence groups in sbox */
static int GetSboxGroups(const Byte *sbox)
{
   int equal[256], unique[256];
   int i, j, k, count;

   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;
   }

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

/* Return number of single bit dependencies in sbox */
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;
}

int main(/*@unused@*/int argc, /*@unused@*/char **argv)
{
   Byte sbox[256];
   int i, j;

   for(i = 0; i < 9 * 16 * 3; i += 3)
   {
      InitSbox(params[i] ^ 81, params[i + 1] ^ 22, params[i + 2] ^ 24, sbox);
      printf("%d %d ",
             GetSboxGroups(sbox),
             GetSingleBitDependencies(sbox));
      for(j = 0; j < 256; j++)
         printf("%02x", sbox[j]);
      putchar('\n');
   }
   return 0;
}