Subversion Repositories bluespec_md6

/* gwt.c
** Ronald L. Rivest
** 5/14/08
** Routines to work with differential properties of g
*/
 
#include <stdio.h>
 
#include <stdint.h>
typedef uint64_t md6_word;
#define w 64
 
/* Useful macros: min and max */
#define min(a,b) ((a)<(b)? (a) : (b))
#define max(a,b) ((a)>(b)? (a) : (b))
 
md6_word g(md6_word x,int r,int ell)
{
  x = x ^ (x >> r);
  x = x ^ (x << ell);
  return x;
}
 
md6_word ginv(md6_word x, int r,int ell)
{
  int i;
  md6_word y,z,xx,yy;
  y = 0;
  xx = x;
  for (i=0;xx!=0;i++)
    { y = y ^ xx;
      xx = xx << ell;
    }
  z = 0;
  yy = y;
  for (i=0;yy!=0;i++)
    { z = z ^ yy;
      yy = yy >> r;
    }
  return z;
}
 
int wt(md6_word x)
{
  int i,c=0;
  for (i=0;i<w;i++)
    c += ( 1 & (x>>i) ) ;
  return c;
}
 
// standard shift table, for MD6 as of 6/1/08
int Ar[16] =   { 28,18,1,15,12, 5,6,22,23,10,3,13,32,10,11,4 };
int Aell[16] = { 14,15,3,13,29,20,3, 7,15,24,9, 8, 4,19, 6,5};
 
int test1()
// print out difference tables for possibly useful r,ell pairs
{ int i,r,ell;
  md6_word x;
  int wt_table_g[w+1];
  int wt_table_ginv[w+1];
  if (w>16){ printf("w=%d too large!",w); return 1; }
  for (r=1;r<w;r++)
    for (ell=1;ell<=w;ell++)
      {
	if (r==ell) continue;
	if (r+ell>=w) continue;
 
	// compute difference table for g
	for (i=0;i<=w;i++) wt_table_g[i] = 2*w;
	for (x=0;;x++)
	  {
	    int in_wt = wt(x);
	    int out_wt = wt(g(x,r,ell));
	    wt_table_g[in_wt] = min(wt_table_g[in_wt],out_wt);
	    if (x==(md6_word)(-1)) break;
	  }
 
	// compute difference table for ginv
	for (i=0;i<=w;i++) wt_table_ginv[i] = 2*w;
	for (x=0;;x++)
	  {
	    int in_wt = wt(x);
	    int out_wt = wt(ginv(x,r,ell));
	    wt_table_ginv[in_wt] = min(wt_table_ginv[in_wt],out_wt);
	    if (x==(md6_word)(-1)) break;
	  }
 
	// print results
	if (wt_table_ginv[1]>2)
	  { printf("r=%2d,ell=%2d ",r,ell);
	    for (i=0;i<=w;i++) printf("%2d ",wt_table_g[i]);
	    printf("\n");
	    printf("r=%2d,ell=%2d ",r,ell);
	    for (i=0;i<=w;i++) printf("%2d ",wt_table_ginv[i]);
	    printf("\n\n");
	  }
      }
  return 0;
}
 
int test2()
{
  int r,ell;
  md6_word x;
  int gamma[w][w];  // gamma[r][ell] is min weight of ginv(x,r,ell) for 
                    // weight-one inputs x
 
  printf("Table of weights of min-weight ginv outputs for ginv inputs of weight 1 (i.e. of gamma(r,ell))\n");
  printf("  ell=");
  for (ell=1;ell<w;ell++) printf("%2d ",ell);
  printf("\n");
  for (r=1;r<w;r++)
    {
      printf("r=%2d: ",r);
      for (ell=1;ell<w;ell++)
	{
	  gamma[r][ell] = 2*w;
	  for (x=1;x>0;x=x<<1)
	    gamma[r][ell] = min(gamma[r][ell],wt(ginv(x,r,ell)));
	  printf("%2d ",gamma[r][ell]);
	  if (gamma[r][ell]==2 &&
              ( (r != 2*ell) &&
		(r != ell) &&
		(ell != 2*r) &&
		(2*r+ell<=w) ) )
	      printf("\nConjecture wrong! r=%d ell=%d",r,ell);
	}
      printf("\n");
      }
  return 0;
 
}
 
int main()
{
  // return test1();
  return test2();
}