/****   Copyright (c) 2001-2003  Alexandros V. Gerbessiotis
 ****
 ****   Permission to use, copy, modify, and distribute this software,
 ****   and to incorporate it, in whole or in part, into other software,
 ****   is hereby granted without fee, provided that
 ****     (1) the above copyright notice and this permission notice appear in
 ****         all copies of the source code, and the above copyright notice
 ****         appear in clearly visible form on all supporting documentation
 ****         and distribution media, and
 ****     (2) any redistribution of the software, in original
 ****         or modified form, be without fee and subject to
 ****         these same conditions.
 ****   No guarantee is offered that the code works as
 ****   advertised or is absent of any, even damaging,
 ****   side-effects; use this code on your own personal risk
 ****/

#undef LOOPOPT
#define LOOPOPT
#ifdef  LOOPOPT
#define NNM  100000
#define NN   16
#endif
#include	"rdxai.h"	
#define ex2(X)  ((int)((unsigned int)(1)<<(X)))

/*** HERE **/
void rdx4 (unsigned int *src,int nn)
{
 register int pid;    /* processor id */
 register int nprocs; /* number of processors available */
 register int rounds;
 int count[256],tcount[256],ccount[256], total[256];
 register int i,j,dpf,dpl,first,last,size,offset,nbytes,r,m;
 int N,n;
 data *out;
 unsigned int mask;
 data **buffer;
 unsigned int shifts[4],shift;
#ifdef LOOPOPT
 int mpistat,mpistat1,mpistat2;
#endif

 pid = AIPID(); nprocs = AINPROCS();
 r=256;
 n=nn;
 nbytes=sizeof(unsigned int);
 shifts[0]=0;shifts[1]=8;shifts[2]=16;shifts[3]=24;
#ifdef LOOPOPT
 mpistat=mpistat1=mpistat2=-10;
#endif

 N=n;
 out = (unsigned int *) malloc(N*nbytes);
#ifdef SANITY_CHECK
  check_if_null((void *)out,"rdxsrt4","out");
#endif

 AIOREGISTER((char *)ccount,r*sizeof(int));
 AIOREGISTER((char *)total,r*sizeof(int));
 AIOCOMMIT();
for(rounds=0;rounds<4;rounds++) { /**********ROUND LOOP****/
 shift=shifts[rounds];
 memset(count,0,r*sizeof(int));
 for(i=0;i<n;++i)
    count[(src[i]>>shift) & 0x000000FF]++; /* count */
 memcpy(tcount,count,r*sizeof(int)); /* copy counters for later use */
 for(j=1;j<r;++j)
    count[j] +=count[j-1]; /* determine position of keys in out */
 for(i=n-1;i>=0;--i) {
   m=--count[(src[i]>>shift) & 0x000000FF];
   out[m]=src[i];         /* complete count sort */
 }

 memcpy(count,tcount,r*sizeof(int));  /* recover count */
 AIOINIT((char *)ccount);
 AIOINIT((char *)total);
 AIOCOMMIT();AIBARRIER();
 /* Determine global position of each key; ccount ppf, total global sums  */
 ai2scan(oper_add,r,(char *)count,(char *)ccount,(char*) total,sizeof(int));
 AIBARRIER();
 for(j=1;j<r;++j)
   total[j]=total[j]+total[j-1];
 for(j=1;j<r;++j)
   ccount[j]=ccount[j]+ total[j-1]; /* position of 0..r-1 in global array */
 for(j=1;j<r;++j)
    count[j] +=count[j-1]; /* repeat count sort steps */


/*
*/
 AIOREGISTER((char *)src,n*nbytes);/* prepare for communication */ 
 AIOINIT((char *)src);
 AIOCOMMIT(); AIBARRIER();
#ifdef LOOPOPT
 mpistat1= (r/nprocs)*pid;
 for(i=0;i<r;i++) { /*** Be careful with matching braces ***/
   j= (mpistat1+i)%r;
#else
 for(j=0;j<r;j++) {
#endif
   first=ccount[j]-tcount[j]; /* first position */
   last =ccount[j]-1;         /* last  position  to store [j]'s */
   dpf = first / N;           /* first processor */
   dpl = last  / N;           /* last  processor to store [j]'s */
   if (first <=last) {        /* do there exist [j] keys? */
   if (dpf==dpl){ /* if yes, check if they all go to same processor */
      /* DEBUG1; */
      if (tcount[j]>0) { /* no need for communication if 0 */
      AIOHPPUT(dpf,(char *)&out[(count[j]-tcount[j])],(char *)src,
              nbytes*(first-dpf*N), tcount[j]*nbytes);
      }
   }
   else { /* if they do not go to the same processor */
      size=dpl*N-first; /* first processor receives some */
      /* DEBUG2; */
      if (size >0) {
        AIOHPPUT(dpf,(char *)&out[(count[j]-tcount[j])],(char *)src,
               nbytes*(N-size),size*nbytes);
      }
      offset=count[j]-tcount[j]+size; /* second processor receives rest */
      size= tcount[j]-size;
      if (size >0) { 
        AIOHPPUT(dpl,(char *)&out[offset],(char *)src,0,(size)*nbytes);
      }
   }
 }
#ifdef LOOPOPT 
 if ((j>0) && (j % NN) == 0) {
    for(mpistat2;mpistat2<NNM;mpistat2++) {mpistat++;}
 }
#endif
 }
 AIOSYNC((char *)src); 
 AIBARRIER();
 AIODEREGISTER((char *)src); 
}
 AIODEREGISTER((char *)total );
 AIODEREGISTER((char *)ccount);
 AIBARRIER();
 free((void *)out);
}

