stanford.c

来自「基于4个mips核的noc设计」· C语言 代码 · 共 864 行 · 第 1/2 页

/* A compute-bound program from Forest Baskett. */

int Fit (i, j) int i, j;
{
  int k;
  for ( k = 0; k <= piecemax[i]; k++ )
    if ( p[i][k] ) if ( puzzl[j+k] ) return (false);
  return (true);
};

int Place (i, j) int i,j;
{
  int k;
  for ( k = 0; k <= piecemax[i]; k++ )
    if ( p[i][k] ) puzzl[j+k] = true;
  piececount[class[i]] = piececount[class[i]] - 1;
  for ( k = j; k <= size; k++ )
    if ( ! puzzl[k] ) {
      return (k);
    };
  return (0);
};

Remove (i, j) int i, j;
{
  int k;
  for ( k = 0; k <= piecemax[i]; k++ )
    if ( p[i][k] ) puzzl[j+k] = false;
  piececount[class[i]] = piececount[class[i]] + 1;
};

int Trial (j) int j;
{
  int i, k;
  kount = kount + 1;
  for ( i = 0; i <= typemax; i++ )
    if ( piececount[class[i]] != 0 )
      if ( Fit (i, j) ) {
	k = Place (i, j);
	if ( Trial(k) || (k == 0) ) {
	  return (true);
	}
	else Remove (i, j);
      };
  return (false);
};

Puzzle ()
{
  int i, j, k, m;
  for ( m = 0; m <= size; m++ ) puzzl[m] = true;
  for( i = 1; i <= 5; i++ )for( j = 1; j <= 5; j++ )for( k = 1; k <= 5; k++ )
    puzzl[i+d*(j+d*k)] = false;
  for( i = 0; i <= typemax; i++ )for( m = 0; m<= size; m++ ) p[i][m] = false;
  
  for( i = 0; i <= 3; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 0; k++ )
    p[0][i+d*(j+d*k)] = true;
  class[0] = 0;
  piecemax[0] = 3+d*1+d*d*0;
  
  for( i = 0; i <= 1; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 3; k++ )
    p[1][i+d*(j+d*k)] = true;
  class[1] = 0;
  piecemax[1] = 1+d*0+d*d*3;
  
  for( i = 0; i <= 0; i++ )for( j = 0; j <= 3; j++ )for( k = 0; k <= 1; k++ )
    p[2][i+d*(j+d*k)] = true;
  class[2] = 0;
  piecemax[2] = 0+d*3+d*d*1;
  
  for( i = 0; i <= 1; i++ )for( j = 0; j <= 3; j++ )for( k = 0; k <= 0; k++ )
    p[3][i+d*(j+d*k)] = true;
  class[3] = 0;
  piecemax[3] = 1+d*3+d*d*0;
  
  for( i = 0; i <= 3; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 1; k++ )
    p[4][i+d*(j+d*k)] = true;
  class[4] = 0;
  piecemax[4] = 3+d*0+d*d*1;
  
  for( i = 0; i <= 0; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 3; k++ )
    p[5][i+d*(j+d*k)] = true;
  class[5] = 0;
  piecemax[5] = 0+d*1+d*d*3;
  
  for( i = 0; i <= 2; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 0; k++ )
    p[6][i+d*(j+d*k)] = true;
  class[6] = 1;
  piecemax[6] = 2+d*0+d*d*0;
  
  for( i = 0; i <= 0; i++ )for( j = 0; j <= 2; j++ )for( k = 0; k <= 0; k++ )
    p[7][i+d*(j+d*k)] = true;
  class[7] = 1;
  piecemax[7] = 0+d*2+d*d*0;
  
  for( i = 0; i <= 0; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 2; k++ )
    p[8][i+d*(j+d*k)] = true;
  class[8] = 1;
  piecemax[8] = 0+d*0+d*d*2;
  
  for( i = 0; i <= 1; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 0; k++ )
    p[9][i+d*(j+d*k)] = true;
  class[9] = 2;
  piecemax[9] = 1+d*1+d*d*0;
  
  for( i = 0; i <= 1; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 1; k++ )
    p[10][i+d*(j+d*k)] = true;
  class[10] = 2;
  piecemax[10] = 1+d*0+d*d*1;
  
  for( i = 0; i <= 0; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 1; k++ )
    p[11][i+d*(j+d*k)] = true;
  class[11] = 2;
  piecemax[11] = 0+d*1+d*d*1;
  
  for( i = 0; i <= 1; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 1; k++ )
    p[12][i+d*(j+d*k)] = true;
  class[12] = 3;
  piecemax[12] = 1+d*1+d*d*1;
  
  piececount[0] = 13;
  piececount[1] = 3;
  piececount[2] = 1;
  piececount[3] = 1;
  m = 1+d*(1+d*1);
  kount = 0;
  if ( Fit(0, m) ) n = Place(0, m);
  else printf("Error1 in Puzzle\n");
  if ( ! Trial(n) ) printf ("Error2 in Puzzle.\n");
  else if ( kount != 2005 ) printf ( "Error3 in Puzzle.\n");
};



/* Sorts an array using quicksort */

Initarr()
{
  int i, temp;
  Initrand();
  biggest = 0; littlest = 0;
  for ( i = 1; i <= sortelements; i++ )
    {
      temp = Rand();
      sortlist[i] = temp - (temp/100000)*100000 - 50000;
      if ( sortlist[i] > biggest ) biggest = sortlist[i];
      else if ( sortlist[i] < littlest ) littlest = sortlist[i];
    };
};

Quicksort( a,l,r) int a[], l, r;
     /* quicksort the array A from start to finish */
{
  int i,j,x,w;
  
  i=l; j=r;
  x=a[(l+r) / 2];
  do {
    while ( a[i]<x ) i = i+1;
    while ( x<a[j] ) j = j-1;
    if ( i<=j ) {
      w = a[i];
      a[i] = a[j];
      a[j] = w;
      i = i+1;    j= j-1;
    }
  } while ( i<=j );
  if ( l <j ) Quicksort(a,l,j);
  if ( i<r ) Quicksort(a,i,r);
};


Quick ()
{
  Initarr();
  Quicksort(sortlist,1,sortelements);
  if ( (sortlist[1] != littlest) || (sortlist[sortelements] != biggest) )
    printf ( " Error in Quick.\n");
};


/* Sorts an array using treesort */

tInitarr()
{
  int i, temp;
  Initrand();
  biggest = 0; littlest = 0;
  for ( i = 1; i <= sortelements; i++ )
    {
      temp = Rand();
      sortlist[i] = temp - (temp/100000)*100000 - 50000;
      if ( sortlist[i] > biggest ) biggest = sortlist[i];
      else if ( sortlist[i] < littlest ) littlest = sortlist[i];
    };
};


/* Sorts an array using bubblesort */

bInitarr()
{
  int i, temp;
  Initrand();
  biggest = 0; littlest = 0;
  for ( i = 1; i <= srtelements; i++ )
    {
      temp = Rand();
      sortlist[i] = temp - (temp/100000)*100000 - 50000;
      if ( sortlist[i] > biggest ) biggest = sortlist[i];
      else if ( sortlist[i] < littlest ) littlest = sortlist[i];
    };
};

Bubble()
{
  int i, j;
  bInitarr();
  top=srtelements;
  
  while ( top>1 ) {
    
    i=1;
    while ( i<top ) {
      
      if ( sortlist[i] > sortlist[i+1] ) {
	j = sortlist[i];
	sortlist[i] = sortlist[i+1];
	sortlist[i+1] = j;
      };
      i=i+1;
    };
    
    top=top-1;
  };
  if ( (sortlist[1] != littlest) || (sortlist[srtelements] != biggest) )
    printf ( "Error3 in Bubble.\n");
};


float Cos (x) float x;
     /* computes cos of x (x in radians) by an expansion */
{
  int i, factor;
  float    result,power;
  
  result = 1.0; factor = 1;  power = x;
  for ( i = 2; i <= 10; i++ ) {
    factor = factor * i;  power = power*x;
    if ( (i & 1) == 0 )  {
      if ( (i & 3) == 0 ) result = result + power/factor;
      else result = result - power/factor;
    };
  };
  return (result);
};

int Min0( arg1, arg2) int arg1, arg2;
{
  if ( arg1 < arg2 )
    return (arg1);
  else
    return (arg2);
};

Uniform11(iy, yfl) int iy; float yfl;
{
  iy = (4855*iy + 1731) & 8191;
  yfl = iy/8192.0;
} /* uniform */ ;

Exptab(n, e) int n; struct complex e[];
     
{ /* exptab */
  float theta, divisor, h[26];
  int i, j, k, l, m;
  
  theta = 3.1415926536;
  divisor = 4.0;
  for ( i=1; i <= 25; i++ )
    {
      h[i] = 1/(2*Cos( theta/divisor ));
      divisor = divisor + divisor;
    };
  
  m = n / 2 ;
  l = m / 2 ;
  j = 1 ;
  e[1].rp = 1.0 ;
  e[1].ip = 0.0;
  e[l+1].rp = 0.0;
  e[l+1].ip = 1.0 ;
  e[m+1].rp = -1.0 ;
  e[m+1].ip = 0.0 ;
  
  do {
    i = l / 2 ;
    k = i ;
    
    do {
      e[k+1].rp = h[j]*(e[k+i+1].rp+e[k-i+1].rp) ;
      e[k+1].ip = h[j]*(e[k+i+1].ip+e[k-i+1].ip) ;
      k = k+l ;
    } while ( k <= m );
    
    j = Min0( j+1, 25);
    l = i ;
  } while ( l > 1 );
  
} /* exptab */ ;

Fft( n, z, w, e, sqrinv)
     int n; struct complex z[], w[]; struct complex e[]; float sqrinv;
{
  int i, j, k, l, m, index;
  m = n / 2 ;
  l = 1 ;
  
  do {
    k = 0 ;
    j = l ;
    i = 1 ;
    
    do {
      
      do {
	w[i+k].rp = z[i].rp+z[m+i].rp ;
	w[i+k].ip = z[i].ip+z[m+i].ip ;
	w[i+j].rp = e[k+1].rp*(z[i].rp-z[i+m].rp)
	  -e[k+1].ip*(z[i].ip-z[i+m].ip) ;
	w[i+j].ip = e[k+1].rp*(z[i].ip-z[i+m].ip)
	  +e[k+1].ip*(z[i].rp-z[i+m].rp) ;
	i = i+1 ;
      } while ( i <= j );
      
      k = j ;
      j = k+l ;
    } while ( j <= m );
    
    /*z = w ;*/ index = 1;
    do {
      z[index] = w[index];
      index = index+1;
    } while ( index <= n );
    l = l+l ;
  } while ( l <= m );
  
  for ( i = 1; i <= n; i++ )
    {
      z[i].rp = sqrinv*z[i].rp ;
      z[i].ip = -sqrinv*z[i].ip;
    } ;
  
} ;

Oscar()
{ /* oscar */
  int i;
  Exptab(fftsize,e) ;
  seed = 5767 ;
  for ( i = 1; i <= fftsize; i++ )
    {
      Uniform11( seed, zr );
      Uniform11( seed, zi );
      z[i].rp = 20.0*zr - 10.0;
      z[i].ip = 20.0*zi - 10.0;
    } ;
  
  
  for ( i = 1; i <= 20; i++ ) {
    Fft(fftsize,z,w,e,0.0625) ;
  };
} /* oscar */ ;

#define ITER           1
#define REPEAT(what)   for(iter = 0; iter < ITER; iter++) what
#define AVGTIME(t)     ((int)((t) / (float)ITER))

main()
{
  int i, iter;
  float f;

  for(f = 0; f < 3.14; f += 0.1)
	printf("%f %f %f %f\n",f, sin(f), cos(f), sin(f)*sin(f)+cos(f)*cos(f));

  fixed = 0.0;	floated = 0.0;
  /* rewrite (output); */
  printf("    Perm"); 
  timer = Getclock(); REPEAT(Perm());   xtimes[1] = AVGTIME(Getclock()-timer);
  fixed = fixed + permbase*xtimes[1];
  floated = floated + permbase*xtimes[1];
  printf("  Towers"); timer = Getclock(); 
  REPEAT(Towers()); xtimes[2] = AVGTIME(Getclock()-timer);
  fixed = fixed + towersbase*xtimes[2];
  floated = floated + towersbase*xtimes[2];
  printf("  Queens"); timer = Getclock(); 
  REPEAT(Queens()); xtimes[3] = AVGTIME(Getclock()-timer);
  fixed = fixed + queensbase*xtimes[3];
  floated = floated + queensbase*xtimes[3];
  printf("   Intmm"); timer = Getclock(); 
  REPEAT(Intmm());  xtimes[4] = AVGTIME(Getclock()-timer);
  fixed = fixed + intmmbase*xtimes[4];
  floated = floated + intmmbase*xtimes[4];
  printf("      Mm"); timer = Getclock(); 
  REPEAT(Mm());     xtimes[5] = AVGTIME(Getclock()-timer);
  fixed = fixed + mmbase*xtimes[5];
  floated = floated + fpmmbase*xtimes[5];
  printf("  Puzzle"); timer = Getclock(); 
  REPEAT(Puzzle()); xtimes[6] = AVGTIME(Getclock()-timer);
  fixed = fixed + puzzlebase*xtimes[6];
  floated = floated + puzzlebase*xtimes[6];
  printf("   Quick"); timer = Getclock(); 
  REPEAT(Quick());  xtimes[7] = AVGTIME(Getclock()-timer);
  fixed = fixed + quickbase*xtimes[7];
  floated = floated + quickbase*xtimes[7];
  printf("  Bubble"); timer = Getclock(); 
  REPEAT(Bubble()); xtimes[8] = AVGTIME(Getclock()-timer);
  fixed = fixed + bubblebase*xtimes[8];
  floated = floated + bubblebase*xtimes[8];
  floated = floated + treebase*xtimes[9];
  printf("     FFT"); timer = Getclock(); 
  REPEAT(Oscar()); xtimes[10] = AVGTIME(Getclock()-timer);
  fixed = fixed + fftbase*xtimes[10];
  floated = floated + fpfftbase*xtimes[10];
  printf("\n");
}