/* MulSim sample program; NOT INTENDED TO BE EFFICIENT as a prime
   finder, either in algorithm or implementation 

   finds and reports the number of primes less than or equal to N

   each node works on a range of Chunk numbers at a time, testing
   them for primeness by straight division; if a potential divisor
   has already been found to be composite (i.e. nonprime), then we
   skip it

*/

#include <mulsim_lib.h>

#define MAX_N 10000

int N, /* check primes from 2 to N */
    Chunk, /* how many numbers to check at one time */
    NNodes, /* number of nodes in computation*/
    Composite[MAX_N], /* array of composites found so far, code 1 for 
                         composite, 0 otherwise */
    L;

struct BarrStruct {
   int Lock;
   int Count[2];
   int EvenOdd;
} ;

Barrier(PB)
   struct BarrStruct *PB;

{  int Par;

   LOCK(PB->Lock);
   Par = PB->EvenOdd;
   PB->Count[Par]++;
   if (PB->Count[Par] == SYS_SIZE)  {
      PB->Count[Par] = 0;
      PB->EvenOdd = 1 - Par;
      UNLOCK(PB->Lock);
   }
   else  {
      UNLOCK(PB->Lock);
      while (PB->Count[Par] > 0) ;
   }
}

struct BarrStruct Bar;

int IsComposite(K)  /* returns 1 if K is found to be composite */
   int K;

{  int J;

   for (J = 2; J*J <= K; J++)  {
      /* if J is known to be composite, don't bother dividing by it */
      if (!Composite[J])  
         if (K % J == 0) return 1;
   }
   return 0;
}

Worker(Me)
   int Me;

{  int First,Last,Iter,NIters,I,Block,MyComposites = 0;

   Block = NNodes * Chunk;

   First = 1 + Me * Chunk;
   Last = First + Chunk - 1;
   NIters = N / Block;
   for (Iter = 0; Iter < NIters; Iter++)  {
      for (I = First; I <= Last; I++)  
         if (IsComposite(I))  {
	    Composite[I] = 1;
	    MyComposites++;
	 }
      First += Block;  Last += Block;
   }

   /* need atomic access to Composite[0] */
   LOCK(L);
   Composite[0] += MyComposites;
   UNLOCK(L);
}

main()

{  int Me;  

   NNodes = SYS_SIZE;  /* built-in MulSim value for the number of CPUs */
   Me = CPU_NUM; /* built-in MulSim value for the number of this CPU */
   N = UserArgv[0];
   Chunk = UserArgv[1];

   if (N % (NNodes*Chunk) > 0)  {
      print_str("N must be an even multiple of NNodes*Chunk\n");
      print_str("results will be erratic\n");
   }

   Worker(Me);

   /* need to make sure everyone is done before printing 
      out the results */
   Barrier(&Bar);
   if (Me == 0)  {
      print_str("number of primes = ");
      print_int(N-Composite[0]-1);
      print_str("\n");
   }
}