stanford.c

mips架构的bootloader,99左右的版本 但源代码现在没人更新了

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

        CreateNode (t,n) struct node **t; int n;
        {
                *t = (struct node *)malloc(sizeof(struct node)); 
                (*t)->left = nil; (*t)->right = nil;
                (*t)->val = n;
        }

    Insert(n, t) int n; struct node *t;
        /* insert n into tree */
    {
           if ( n > t->val ) 
                if ( t->left == nil ) CreateNode(&t->left,n);
                else Insert(n,t->left);
           else if ( n < t->val )
                if ( t->right == nil ) CreateNode(&t->right,n);
                else Insert(n,t->right);
    }

    int Checktree(p) struct node *p;
    /* check by inorder traversal */
    {
    int result;
        result = true;
                if ( p->left != nil ) 
                   if ( p->left->val <= p->val ) result=false;
                   else result = Checktree(p->left) && result;
                if ( p->right != nil )
                   if ( p->right->val >= p->val ) result = false;
                   else result = Checktree(p->right) && result;
        return( result);
    } /* checktree */

Trees()
    {
    int i;
    tInitarr();
    tree = (struct node *)malloc(sizeof(struct node)); 
    tree->left = nil; tree->right=nil; tree->val=sortlist[1];
    for ( i = 2; i <= sortelements; i++ ) Insert(sortlist[i],tree);
    if ( ! Checktree(tree) ) printf ( " Error in Tree.\n");
    }


    /* 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);
    }

Printcomplex(  arg1, arg2, zarray, start, finish, increment)
        int arg1, arg2, start, finish, increment;
        struct complex zarray[];
    {
    int i;
    printf("\n") ;

    i = start;
    do {
        printf("  %15.3e%15.3e",zarray[i].rp,zarray[i].ip) ;
        i = i + increment;
        printf("  %15.3e%15.3e",zarray[i].rp,zarray[i].ip) ;
        printf("\n");
        i = i + increment ;
    } while ( i <= finish );

    }

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) ;
   /* Printcomplex( 6, 99, z, 1, 256, 17 ); */
   }
} /* oscar */

main()
{
int i;

fixed = 0.0;    floated = 0.0;
/* rewrite (output); */
printf("    Perm"); timer = Getclock(); Perm();   xtimes[1] = Getclock()-timer;
fixed = fixed + permbase*xtimes[1];
floated = floated + permbase*xtimes[1];
printf("  Towers"); timer = Getclock(); Towers(); xtimes[2] = Getclock()-timer;
fixed = fixed + towersbase*xtimes[2];
floated = floated + towersbase*xtimes[2];
printf("  Queens"); timer = Getclock(); Queens(); xtimes[3] = Getclock()-timer;
fixed = fixed + queensbase*xtimes[3];
floated = floated + queensbase*xtimes[3];
printf("   Intmm"); timer = Getclock(); Intmm();  xtimes[4] = Getclock()-timer;
fixed = fixed + intmmbase*xtimes[4];
floated = floated + intmmbase*xtimes[4];
printf("      Mm"); timer = Getclock(); Mm();     xtimes[5] = Getclock()-timer;
fixed = fixed + mmbase*xtimes[5];
floated = floated + fpmmbase*xtimes[5];
printf("  Puzzle"); timer = Getclock(); Puzzle(); xtimes[6] = Getclock()-timer;
fixed = fixed + puzzlebase*xtimes[6];
floated = floated + puzzlebase*xtimes[6];
printf("   Quick"); timer = Getclock(); Quick();  xtimes[7] = Getclock()-timer;
fixed = fixed + quickbase*xtimes[7];
floated = floated + quickbase*xtimes[7];
printf("  Bubble"); timer = Getclock(); Bubble(); xtimes[8] = Getclock()-timer;
fixed = fixed + bubblebase*xtimes[8];
floated = floated + bubblebase*xtimes[8];
printf("    Tree"); timer = Getclock(); Trees(); xtimes[9] = Getclock()-timer;
fixed = fixed + treebase*xtimes[9];
floated = floated + treebase*xtimes[9];
#ifndef NOFFT
printf("     FFT"); timer = Getclock(); Oscar(); xtimes[10] = Getclock()-timer;
fixed = fixed + fftbase*xtimes[10];
floated = floated + fpfftbase*xtimes[10];
#endif
printf("\n");
for ( i = 1; i <= 10; i++ ) printf("%8d", xtimes[i]);
printf("\n");
    /* compute composites */
    printf("\n");
    printf("Nonfloating point composite is %10.0f\n",fixed/10.0);
    printf("\n");
    printf("Floating point composite is %10.0f\n",floated/10.0);
return 0;
}