primenums.c

/* -----------------------------------------------------------------------------
 *  Copyright (C) 2019-2021 daiteq s.r.o.                http://www.daiteq.com
 *
 *  This program is distributed WITHOUT ANY WARRANTY; without even
 *  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 *  PURPOSE.
 *
 * -----------------------------------------------------------------------------
 *  Filename    : primenums.c
 *  Authors     : Martin Danek
 *  Description : Sieve of Eratosthenes with SWAR operations
 *  Release     :
 *  Version     : 1.0
 *  Date        : 27.4.2021
 * -----------------------------------------------------------------------------
 */


#include <stdint.h>
#include <stdlib.h>

#include "../common_sys_header.inc"

#include "asm_swar.inc"

#include "swar.h"


void report_time(int clr) {
unsigned ticks_lo, ticks_hi, insns_lo, insns_hi;
static unsigned ticks_lo_acc, ticks_hi_acc, insns_lo_acc, insns_hi_acc;
  sysregs_stop();
  sysregs_read(&ticks_lo, &ticks_hi, &insns_lo, &insns_hi);

  if (ticks_hi) {
    printf("EXECUTED IN (%u * 2^32 + %u) TICKS AND (%u * 2^32 + %u) INSTRUCTIONS\n\n",ticks_hi, ticks_lo, insns_hi, insns_lo);
  }
  else {
    printf("EXECUTED IN %u TICKS AND %u INSTRUCTIONS\n\n",ticks_lo, insns_lo);
  }
  ticks_lo_acc+=ticks_lo; ticks_hi_acc+=ticks_hi;
  insns_lo_acc+=insns_lo; insns_hi_acc+=insns_hi;
  if (clr) {
    NL;
    if (ticks_hi_acc) {
      printf("ACCUMULATED VALUES (%u  * 2^32 + %u) TICKS AND (%u * 2^32 + %u) INSTRUCTIONS\n\n", ticks_hi_acc, ticks_lo_acc, insns_hi_acc, insns_lo_acc);
    }
    else {
      printf("ACCUMULATED VALUES %u TICKS AND %u INSTRUCTIONS\n\n",ticks_lo_acc, insns_lo_acc);
    }
    ticks_lo_acc=0; ticks_hi_acc=0;
    insns_lo_acc=0; insns_hi_acc=0;
  }
  sysregs_start();
}

// -----------------------------------------------------------------------------
// SWAR - macros
//#define SWAR_SET_ELM(tp,svar,index,value)
      //svar = (svar ) |
      //((value & ((1<<sizeofswar(tp))-1))<<(index*sizeofswar(tp)))

void SWAR_SET_ELM(void *swar, int idx, int val, int bitsz)
{
  *((unsigned int *)swar) = ( (*((unsigned int *)swar)) & ~(((1<<bitsz)-1)<<(bitsz*idx))) | ((val & ((1<<bitsz)-1))<<(bitsz*idx));
}

//#define SWAR_GET_ELM(tp,svar,index)
int SWAR_GET_ELM(void *swar, int idx, int bitsz)
{
  return ((*((unsigned int *)swar) >> (bitsz*idx)) & ((1<<bitsz)-1));
}


//#define SWAR_SET_ARR_ELM(tp,arry,index,value)
void SWAR_SET_ARR_ELM(void *arry, int idx, int val, int bitsz)
{
  int pack = 32/bitsz;
  int ofs = idx / pack;
  int elidx = idx - ofs*pack;
  unsigned int *pw = ((unsigned int *)arry) + ofs;
  if (pack==1)
    *pw=val;
  else
    SWAR_SET_ELM(pw, elidx, val, bitsz);
}

//#define SWAR_GET_ARR_ELM(tp,arry,index)
int SWAR_GET_ARR_ELM(void *arry, int idx, int bitsz)
{
  int pack = 32/bitsz;
  int ofs = idx / pack;
  int elidx = idx - ofs*pack;
  unsigned int *pw = ((unsigned int *)arry) + ofs;
  if (pack==1)
    return *pw;
  else
    return SWAR_GET_ELM(pw, elidx, bitsz);
}

// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// BIT - macros


#define BIT_SET_ELM(word, pos, val) \
  ((val)?(word | (1<<pos)):(word & (~(1<<pos))))

#define BIT_GET_ELM(word, pos) \
  (word & (1<<pos))



#define VERBOSE /* */

//#define RAWRAM

#define VERSION_NAIVE
#define VERSION_BITVEC
// #define VERSION_SWAR_INLINEASM
// #define VERSION_SWAR
// #define VERSION_SWAR_CHAR
// #define VERSION_CHAR_SWAR
// #define PRINT_ITEMS

#ifdef VERSION_SWAR_INLINEASM
#define SLICESZ 1
#ifdef VERSION_SWAR
#error "INVALID CONFIGURATION - SWAR WHEN SWAR_INLINEASM"
#endif
#endif

#ifdef VERSION_SWAR
#define VERSION_SWAR_CHAR
#define VERSION_CHAR_SWAR
#define SLICESZ 8
#ifdef VERSION_SWAR_INLINEASM
#error "INVALID CONFIGURATION - SWAR_INLINEASM WHEN SWAR"
#endif
#endif


typedef unsigned int u8b __attribute__((subword(SLICESZ)));
typedef unsigned int u8b1 __attribute__((subword(SLICESZ,1)));
#define PACKING (32/SLICESZ)

//#define MAXNUM 1300000
//#define SQRTMAXNUM 1141 // ceil(sqrt(1300000))
#define MAXNUM 256 // 1300000
#define SQRTMAXNUM 16 // 1141 // ceil(sqrt(1300000))
// #define MAXNUM 2048 // 1300000
// #define SQRTMAXNUM 46 // 1141 // ceil(sqrt(1300000))

//#define MAXSLOTS ((MAXNUM-1)/PACKING+1)
#define MAXSLOTS ((MAXNUM+PACKING-1)/PACKING)
#define MAXMASKS (MAXSLOTS<<1) // (((SQRTMAXNUM-1)/PACKING+1)<<1)

//#define RAMSTART  0x50000000 // VC707 w/ mig
//#define RAMSTART2 0x6000000 // VC707 w/ mig

extern unsigned long __heap_min;  /* start address after .bss section. defined in linker script */
#define RAMSTART (&__heap_min)
//unsigned char dataarray[MAXNUM];
//#define RAMSTART  (&dataarray)

int main(void) {
volatile unsigned acc;
volatile u8b redmask[2];
// #ifdef RAWRAM
// volatile u8b *swnumbers=RAMSTART;
// volatile u8b *swmasks=RAMSTART+(MAXSLOTS*4);
// #else
volatile u8b swnumbers[MAXSLOTS];
volatile u8b swmasks[MAXSLOTS];
// #endif

int i,j,k,l,m;
unsigned sz;
unsigned top;
unsigned slot,slotreg;
unsigned slotstart;
unsigned prime, first, last;
unsigned fin, cont;

unsigned sqr, val, res;

#ifdef VERSION_SWAR_INLINEASM
#ifdef RAWRAM
unsigned *a=(unsigned *)RAMSTART;
#else
unsigned a[MAXNUM];
#endif
#else
#ifdef RAWRAM
unsigned char *a=(unsigned char *)RAMSTART;
#else
unsigned char a[MAXNUM];
#endif
#endif


// unsigned roots[MAXNUM];

#ifdef RAWRAM
unsigned *numbers=(unsigned *)RAMSTART;
unsigned *masks=(unsigned *)(RAMSTART+(MAXSLOTS*4));
#else
unsigned numbers[MAXSLOTS];
unsigned masks[MAXMASKS];
#endif

system_init();


top = MAXNUM;
sz = sizeof(*a);

#ifdef VERBOSE
printf("\n\nConfiguration:\n");
#ifdef VERSION_NAIVE
printf("   VERSION_NAIVE\n");
printf("   sizeof(*a) = %dB\n",sz);
#endif
#ifdef VERSION_BITVEC
printf("   VERSION_BITVEC\n");
#endif
#ifdef VERSION_SWAR_INLINEASM
printf("   VERSION_SWAR_INLINEASM\n");
#endif
#ifdef VERSION_SWAR
printf("   VERSION_SWAR\n");
#endif
#ifdef VERSION_SWAR_CHAR
printf("   VERSION_SWAR_CHAR\n");
#endif
#ifdef VERSION_CHAR_SWAR
printf("   VERSION_CHAR_SWAR\n");
#endif
printf("\n");
printf("   MAXNUM = %d\n",top);
printf("   SQRTMAXNUM = %d\n",SQRTMAXNUM);
printf("   SLICESZ = %d\n",SLICESZ);
printf("   PACKING = %d\n",PACKING);
printf("   MAXSLOTS = %d\n",MAXSLOTS);
printf("   MAXMASKS = %d\n",MAXMASKS);
printf("\n\n\n");
#endif

#ifdef PRECOMP_SQRT
k=0;
roots[0]=1;
for (i=1;i<top;i++) {
  roots[i]=i*i;
}

k=0;
while (roots[k]<top)  {
  k++;
}

#else

k=SQRTMAXNUM;

#endif


printf("primenums: sqrt(%d)=%d\n",top,k);

// -------------------------------------------------------------

#ifdef VERSION_NAIVE

printf("\n\n*** VERSION_NAIVE BEGIN ***\n\n");

printf("primenums: initializing array (%d)\n", top);
sysregs_init();

for (i=0;i<top;i++) {
  *(a+i)=1;
}

report_time(0);
printf("primenums: eliminating composites\n");
sysregs_init();

j=2;
while(j<=SQRTMAXNUM) {
  while (*(a+j)==0)
    j++;
  for (i=j;i<top;i=i+j)
    if (i>j) {
      *(a+i)=0;
    }
  j++;
}

report_time(0);
printf("primenums: counting primes...\n");
sysregs_init();
acc=0;
for (i=1;i<top;i++) {
  if (*(a+i)==1) {
    acc++;
  }
}
report_time(1);
printf("primenums: primes found: %d\n\n",acc);
sysregs_init();

#ifdef PRINT_ITEMS
#ifdef VERBOSE
printf("primenums: printing primes\n");
#endif
for (i=1;i<top;i++)
#ifdef VERBOSE
  if (*(a+i)==1) {
    printf("%d\n",i);
  }
#else
  if (*(a+i)==1) {
    printf("1");
  }
  else
    printf("0");
#endif
printf("\n");
#endif

printf("\nprimenums: VERSION_NAIVE done\n\n\n");

#endif

// -------------------------------------------------------------

#ifdef VERSION_BITVEC

printf("\n\n*** VERSION_BITVEC BEGIN ***\n\n");

printf("primenums: initializing array\n");
sysregs_init();

numbers[0]=0xfffffffe;
for (i=1;i<(MAXSLOTS)+1;i++) {
  numbers[i]=0xffffffff;
}


report_time(0);
printf("primenums: eliminating composites\n");
sysregs_init();

j=0;
l=0;
prime=0;
cont=1;
while(cont) {
// Get the next prime
  while(numbers[j]==0) {
    j++;
  }
  val=numbers[j];
  while (!((val>>l)&1))
    l++;
  prime=PACKING*j+l+1; // the actual prime

// Compute masks, set the number of active masks
  last=0;
  first=1;
  m=prime;
  val=0;
  slot=0;
  fin=0;
  slotreg=0;
  slotstart=slot;
  while ((slot<MAXSLOTS)&&(fin<2)) {
    if (prime<=PACKING) {
      if (!first)
        val|=(1<<(m-1));
      else
        first=0;
//       printf("m %d val %08X\n",m,val);
      if (val&(1<<(PACKING-1))) {
        fin++;
        if (!slotreg) {
          slotreg=slot+1;
//           printf("slotreg is %d\n",slotreg);
        }
      }
      m+=prime;
      if (m>PACKING) {
//         printf("masks[%d]=%08X\n",slot,val);
        masks[slot++]=val;
        m=m%PACKING;
        val=0;
      }
    }
    else {
      if ((m-1-last)<(PACKING)) {
        // the only non-zero word
        val=(1<<(m-last-1));
        last=PACKING-m+last;
        if ((!slotstart)&&(!first))
          slotstart=slot;
      }
      else {
        val=0;
        last+=PACKING;
      }
      if (val&(1<<(PACKING-1))) {
        fin++;
        if (!slotreg) {
          slotreg=slot+1;
//           printf("slotreg is %d\n",slotreg);
        }
      }
//       printf("last %d m %d m-last %d\n",last,m,m-last);
//       printf("masks[%d]=%08X\n",slot,val);
      if (first)
        masks[slot++]=0;
      else
        masks[slot++]=val;
      if ((first)&&(val))
        first=0;

    }
  }

  if (slot>=MAXMASKS) {
    printf("\nMAXIMUM NUMBER OF MASKS EXCEEDED - SLOT %d PRIME %d\n",slot,prime);
    exit(1);
  }

//   printf("slot %d\n",slot);
//   printf("prime %d\n",prime);
//   for (i=0;i<slot;i++) {
//     printf("masks[%d]=%08X\n",i,masks[i]);
//   }
  if (!slotreg) slotreg=MAXSLOTS;

  for (i=0;i<slotreg;i++) {
    numbers[i]&=(~masks[i%slot]);
  }
  for (i=slotreg;i<MAXSLOTS;i++) {
    numbers[i]&=(~masks[i%slotreg+slotreg]);
  }

  l++;
  if (l>=PACKING) {
    l=0;
    j++;
  }
  if (prime>k) {
    cont=0;
  }
}
numbers[0]|=1;

report_time(0);
printf("primenums: counting primes...\n");
sysregs_init();
acc=0;
m=0;
for (i=0;i<MAXSLOTS;i++) {
  for (j=0;j<PACKING;j++) {
    m++;
//     if ((numbers[i]&(1<<j))&&(m<top)) {
    if (numbers[i]&(1<<j)) {
      acc++;
    }
  }
//   printf("numbers[%d] %08X acc %d\n",i,numbers[i],acc);
}
report_time(1);
printf("primenums: primes found: %d\n\n",acc);
sysregs_init();

#ifdef PRINT_ITEMS
m=0;
for (i=0;i<MAXSLOTS;i++) {
  for (j=0;j<PACKING;j++) {
    m++;
    if ((numbers[i]&(1<<j))&&(m<top)) {
      printf("%d\n",m);
    }
  }
}
printf("\n");
#endif

printf("\nprimenums: VERSION_BITVEC done\n\n\n");

#endif


// -------------------------------------------------------------


#ifdef VERSION_SWAR_INLINEASM

printf("\n\n*** VERSION_SWAR_INLINEASM BEGIN ***\n\n");

printf("primenums: initializing array\n");
sysregs_init();

numbers[0]=0xfffffffe;
for (i=1;i<(MAXSLOTS)+1;i++) {
  numbers[i]=0xffffffff;
}


report_time(0);
printf("primenums: eliminating composites\n");
sysregs_init();


j=0;
l=0;
prime=0;
cont=1;
while(cont) {
// Get the next prime
  while(numbers[j]==0) {
    printf("Skipping j=%d\n",j);
    j++;
  }
  val=numbers[j];
  while (!((val>>l)&1))
    l++;
  prime=PACKING*j+l+1; // the actual prime

// Compute masks, set the number of active masks
  last=0;
  first=1;
  m=prime;
  val=0;
  slot=0;
  fin=0;
  slotreg=0;
  slotstart=slot;
  while ((slot<MAXSLOTS)&&(fin<2)) {
    if (prime<=PACKING) {
      if (!first)
        val|=(1<<(m-1));
      else
        first=0;
      if (val&(1<<(PACKING-1))) {
        fin++;
        if (!slotreg) {
          slotreg=slot+1;
        }
      }
      m+=prime;
      if (m>PACKING) {
        masks[slot++]=val;
        m=m%PACKING;
        val=0;
      }
    }
    else {
      if ((m-1-last)<(PACKING)) {
        // the only non-zero word
        val=(1<<(m-last-1));
        last=PACKING-m+last;
        if ((!slotstart)&&(!first))
          slotstart=slot;
      }
      else {
        val=0;
        last+=PACKING;
      }
      if (val&(1<<(PACKING-1))) {
        fin++;
        if (!slotreg) {
          slotreg=slot+1;
        }
      }
      if (first)
        masks[slot++]=0;
      else
        masks[slot++]=val;
      if ((first)&&(val))
        first=0;

    }
  }

  if (slot>=MAXMASKS) {
    printf("\nMAXIMUM NUMBER OF MASKS EXCEEDED - SLOT %d PRIME %d\n",slot,prime);
    exit(1);
  }

//   printf("slot %d\n",slot);
//   printf("prime %d\n",prime);
//   for (i=0;i<slot;i++) {
//     printf("masks[%d]=%08X\n",i,masks[i]);
//   }
  if (!slotreg) slotreg=MAXSLOTS;

  for (i=0;i<slotreg;i++) {
    numbers[i]&=(~masks[i%slot]);
  }
  for (i=slotreg;i<MAXSLOTS;i++) {
    numbers[i]&=(~masks[i%slotreg+slotreg]);
  }

  l++;
  if (l>=PACKING) {
    l=0;
    j++;
  }
  if (prime>k) {
    cont=0;
  }
}
numbers[0]|=1;

report_time(0);
printf("primenums: counting primes...\n");
sysregs_init();

acc=0;
op_set_ctrl(SW_OP_COR1b|SW_CTRL_REDUCE);
for (i=0;i<MAXSLOTS;i++) {
  op_swar(0xffffffff, numbers[i], acc);
//   printf("numbers[%d] %08X acc %d\n",i,numbers[i],acc);
}
report_time(1);
printf("primenums: primes found: %d\n\n",acc);
sysregs_init();

#ifdef PRINT_ITEMS
m=0;
for (i=0;i<MAXSLOTS;i++) {
  for (j=0;j<PACKING;j++) {
    m++;
    if ((numbers[i]&(1<<j))&&(m<top)) {
      printf("%d\n",m);
    }
  }
}
printf("\n");
#endif

printf("\nprimenums: VERSION_SWAR_INLINEASM done\n\n\n");

#endif


// -------------------------------------------------------------


#ifdef VERSION_SWAR

printf("\n\n*** VERSION_SWAR BEGIN ***\n\n");

printf("primenums: initializing array\n");
sysregs_init();

// swnumbers[0][0]=0;
SWAR_SET_ARR_ELM(swnumbers, 0, 0, SLICESZ);
for (j=1;j<PACKING;j++)
//   swnumbers[0][j]=((1<<SLICESZ)-1);
  SWAR_SET_ARR_ELM(swnumbers, j, ((1<<SLICESZ)-1), SLICESZ);
for (i=1;i<(MAXSLOTS)+1;i++) {
  for (j=0;j<PACKING;j++)
//     swnumbers[i][j]=((1<<SLICESZ)-1);
    SWAR_SET_ARR_ELM(swnumbers, i*PACKING+j, ((1<<SLICESZ)-1), SLICESZ);
}

for (i=0;i<(MAXSLOTS)+1;i++) {
   printf("swnumbers[%d]=%08X\n",i,*((unsigned*)&swnumbers[i]));
}


report_time(0);
printf("primenums: eliminating composites\n");
sysregs_init();

redmask[0]=0xffffffff;

j=0;
l=0;
prime=0;
cont=1;
while(cont) {
// Get the next prime
  val=(*((int*)&swnumbers[j]));
  //printf("j %d val %08X\n",j,val);
  while(val==0) {
    printf("Skipping j=%d val %08X\n",j,val);
    j++;
    l=0;
    val=(*((int*)&swnumbers[j]));
  }
//   while (!((val>>l)&1)) {
  while (!(SWAR_GET_ARR_ELM(swnumbers, PACKING*j+l, SLICESZ))) {
    //printf("Skipping (SWAR_GET_ARR_ELM(swnumbers, %d*%d+%d, %d) %08X\n",PACKING,j,l,SLICESZ,SWAR_GET_ARR_ELM(swnumbers, PACKING*j+l, SLICESZ));
    l++;
    if (l==PACKING) {
      l=0;
      j++;
    }
  }
  prime=PACKING*j+l+1; // the actual prime
  //printf("current prime is %d\n",prime);

// Compute swmasks, set the number of active swmasks
  last=0;
  first=1;
  m=prime;
  val=0;
  slot=0;
  fin=0;
  slotreg=0;
  slotstart=slot;
  while ((slot<MAXSLOTS)&&(fin<2)) {
//printf("#%d : (fin=%d) prime=%u /%u\n", slot, fin, prime, PACKING);
    if (prime<=PACKING) {
      if (!first)
        val|=(((1<<SLICESZ)-1)<<(SLICESZ*(m-1)));
      else
        first=0;
      //printf("m %d val %08X\n",m,val);
      if (val&(((1<<SLICESZ)-1)<<((PACKING-1)*SLICESZ))) {
        fin++;
        if (!slotreg) {
          slotreg=slot+1;
          //printf("slotreg is %d\n",slotreg);
        }
      }
      m+=prime;
      if (m>PACKING) {
        //printf("swmasks[%d]=%08X\n",slot,~val);
//printf("->swmasks[%d]=%08X\n",slot,*(unsigned *)&swmasks[slot]);
        *(unsigned int *)&swmasks[slot]=~val;
//printf("<-swmasks[%d]=%08X\n",slot,*(unsigned *)&swmasks[slot]);
        slot++;
        m=m%PACKING;
        val=0;
      }
    }
    else {
      if ((m-1-last)<(PACKING)) {
        // the only non-zero word
        val=(((1<<SLICESZ)-1)<<(SLICESZ*(m-last-1)));
        last=PACKING-m+last;
        if ((!slotstart)&&(!first))
          slotstart=slot;
      }
      else {
        val=0;
        last+=PACKING;
      }
      if (val&(((1<<SLICESZ)-1)<<((PACKING-1)*SLICESZ))) {
        fin++;
        if (!slotreg) {
          slotreg=slot+1;
          //printf("slotreg is %d\n",slotreg);
        }
      }
      //printf("last %d m %d m-last %d\n",last,m,m-last);
      //printf("swmasks[%d]=%08X (%d)\n",slot,~val, first);
//printf("->swmasks[%d]=%08X\n",slot,*(unsigned *)&swmasks[slot]);
      if (first)
        *(unsigned int *)&swmasks[slot]=~0;
      else
        *(unsigned int *)&swmasks[slot]=~val;
//printf("<-swmasks[%d]=%08X\n",slot,*(unsigned *)&swmasks[slot]);
      slot++;
      if ((first)&&(val))
        first=0;
    }
  }

  if (slot>=MAXMASKS) {
    printf("\nMAXIMUM NUMBER OF MASKS EXCEEDED - SLOT %d PRIME %d\n",slot,prime);
    exit(1);
  }

  //printf("slotreg %d\n",slotreg);
  if (!slotreg) {
    slotreg=MAXSLOTS;
    //printf("adjusted slotreg %d\n",slotreg);
  }
  //printf("slot %d\n",slot);
  //printf("prime %d\n",prime);
  //for (i=0;i<slot;i++) {
  //  printf("swmasks[%d]=%08X\n",i,*((int*)&swmasks[i]));
  //}

  res=0;
  for (i=0;i<slotreg;i++) {
//     printf("slot %d swnumbers[%d]=%08X swmasks[%d]=%08X\n",slot, i, *((int*)&swnumbers[i]),i%slot, (*((int*)&swmasks[i%slot])));
//     res=*((int*)&swnumbers[i]);
//     res&=((*((int*)&swmasks[i%slot])));
//     swnumbers[i]=res;
    swnumbers[i] = swnumbers[i] * swmasks[i%slot];
//     printf("#1 swnumbers[%d]=%08X\n",i,*((int*)&swnumbers[i]));
  }
  for (i=slotreg;i<MAXSLOTS;i++) {
//     printf("slot %d swnumbers[%d]=%08X swmasks[%d]=%08X\n",slot, i, *((int*)&swnumbers[i]),i%slotreg+slotreg, (*((int*)&swmasks[i%slotreg+slotreg])));
//     res=*((int*)&swnumbers[i]);
//     res&=((*((int*)&swmasks[i%slotreg+slotreg])));
//     swnumbers[i]=res;
    swnumbers[i] = swnumbers[i] * swmasks[i%slotreg+slotreg];
//     printf("#2 swnumbers[%d]=%08X\n",i,*((int*)&swnumbers[i]));
  }

  // correct values back to all '1's
  for (i=0;i<(MAXSLOTS);i++) {
    //printf("#3.1 swnumbers[%d]=%08X * redmask[0]=%08X\n",i,*((int*)&swnumbers[i]),*((int*)&redmask[0]));
    swnumbers[i] = swnumbers[i] * redmask[0];
    //printf("#3.2 swnumbers[%d]=%08X\n",i,*((int*)&swnumbers[i]));
  }

  //for (i=0;i<(MAXSLOTS);i++) {
  //  printf("corr swnumbers[%d]=%08X\n",i,*((int*)&swnumbers[i]));
  //}

  l++;
  if (l>=PACKING) {
    l=0;
    j++;
  }
  if (prime>k) {
//     printf("setting cont=0 for prime=%d and k=%d\n",prime,k);
    cont=0;
  }
}
val=*((int*)&swnumbers[0]);
val|=((1<<SLICESZ)-1);
swnumbers[0]=val;


report_time(0);
printf("primenums: translating flags...\n");
sysregs_init();

// redmask[0]=0xffffffff; // moved at the beginning
// convert values to single 1's
for (i=0;i<MAXSLOTS;i++) {
  swnumbers[i] = redmask[0] * swnumbers[i];
//   printf("#4 swnumbers[%d]=%08X\n",i,*((int*)&swnumbers[i]));
}

report_time(0);
printf("primenums: counting primes...\n");
sysregs_init();

acc=0;
redmask[0]=redmask[0]*redmask[0];
// printf("#5 init redmask[0]=%08X\n",*((int*)&redmask[0]));
#pragma swar reduce
for (i=0;i<MAXSLOTS;i++) {
  redmask[1] = redmask[0] * swnumbers[i];
  acc+=*((int *)&redmask[1]);
//   printf("#6 swnumbers[%d]=%08X redmask[1]=%08X acc=%d\n",i,*((int*)&swnumbers[i]),*((int*)&redmask[1]),acc);
}

report_time(1);
printf("primenums: primes found: %d\n\n",acc);
sysregs_init();

#ifdef PRINT_ITEMS
m=0;
for (i=0;i<MAXSLOTS;i++) {
  for (j=0;j<PACKING;j++) {
    m++;
    if (((*((int*)&swnumbers[i]))&(1<<(SLICESZ*j)))&&(m<top)) {
      printf("%d\n",m);
    }
  }
}
printf("\n");
#endif

printf("\nprimenums: VERSION_SWAR done\n\n\n");

#endif


// -------------------------------------------------------------


#ifdef VERSION_SWAR_CHAR

printf("\n\n*** VERSION_SWAR_CHAR BEGIN ***\n\n");

printf("primenums: initializing array\n");
sysregs_init();

*((char*)&swnumbers)=0;
for (j=1;j<PACKING*MAXSLOTS;j++) {
  *(((char*)&swnumbers)+j)=1;
//   printf("((char*)&swnumbers)+%d=%08X *(((char*)&swnumbers)+%d)=%08X\n",j,((char*)&swnumbers)+j,j,*(((char*)&swnumbers)+j));
}

// for (i=0;i<MAXSLOTS;i++) {
//   printf("(((int*)&swnumbers)+%d)=%08X swnumbers[%d]=%08X\n",i,(((int*)&swnumbers)+i),i,*(((int*)&swnumbers)+i));
// }


report_time(0);
printf("primenums: eliminating composites\n");
sysregs_init();

j=1;
while(j<MAXSLOTS*PACKING) {
  val=*(((char*)&swnumbers)+j);
  while (val==0) {
//     printf("Skipping ((char*)&swnumbers)+%d=%08X *(((char*)&swnumbers)+%d)=%08X val=%08X\n",j,((char*)&swnumbers)+j,j,*(((char*)&swnumbers)+j),val);
    j++;
    val=*(((char*)&swnumbers)+j);
  }
//   printf("prime %d\n",j+1);
  for (i=j;i<top;i=i+j+1) {
    if (i>j) {
      *(((char*)&swnumbers)+i)=0;
//       printf("Zeroed ((char*)&swnumbers)+%d=%08X *(((char*)&swnumbers)+%d)=%08X\n",i,((char*)&swnumbers)+i,i,*(((char*)&swnumbers)+i));
    }
  }
  j++;
}

*((char*)&swnumbers)=1;

report_time(0);
// printf("primenums: counting primes - naive...\n");
// sysregs_init();
//
// acc=0;
// for (i=0;i<top;i++) {
//   if (*(((char*)&swnumbers)+i)==1) {
//     acc++;
//   }
// }
// report_time(0);
// printf("primenums: primes found: %d\n\n",acc);
//
// printf("\n\n");
//
printf("primenums: counting primes - SWAR reduction...\n");
sysregs_init();

redmask[0]=0xffffffff;
// redmask[0]=0x01010101;
acc=0;
// printf("#5.0 acc=%d\n",acc); // when commented, the previous assignment acc=0 is not executed
// printf("#5.1 init redmask[0]=%08X\n",*((int*)&redmask[0]));
redmask[0]=redmask[0]*redmask[0];
// printf("#5.2 init redmask[0]=%08X\n",*((int*)&redmask[0]));
#pragma swar reduce
for (i=0;i<MAXSLOTS;i++) {
  redmask[1] = redmask[0] * swnumbers[i];
  acc+=*((int *)&redmask[1]);
//   printf("#6 swnumbers[%d]=%08X redmask[1]=%08X acc=%d\n",i,*((int*)&swnumbers[i]),*((int*)&redmask[1]),acc);
}

report_time(1);
printf("primenums: primes found: %d\n\n",acc);
sysregs_init();


// #ifdef PRINT_ITEMS
// #ifdef VERBOSE
// printf("primenums: printing primes - naive\n");
// #endif
// for (i=1;i<top;i++)
// #ifdef VERBOSE
//   if (*(a+i)==1) {
//     printf("%d\n",i);
//   }
// #else
//   if (*(a+i)==1) {
//     printf("1");
//   }
//   else
//     printf("0");
// #endif
// printf("\n");
// #endif


#ifdef PRINT_ITEMS
#ifdef VERBOSE
printf("primenums: printing primes - SWAR reduction\n");
#endif
m=0;
for (i=0;i<MAXSLOTS;i++) {
  for (j=0;j<PACKING;j++) {
    m++;
    if (((*((int*)&swnumbers[i]))&(1<<(SLICESZ*j)))&&(m<top)) {
      printf("%d\n",m);
    }
  }
}
printf("\n");
#endif

printf("\nprimenums: VERSION_SWAR_CHAR done\n\n\n");

#endif


// -------------------------------------------------------------


#ifdef VERSION_CHAR_SWAR

printf("\n\n*** VERSION_CHAR_SWAR BEGIN ***\n\n");

printf("primenums: initializing array\n");
sysregs_init();

*(a)=0;
for (i=1;i<top;i++) {
  *(a+i)=1;
}

report_time(0);
printf("primenums: eliminating composites\n");
sysregs_init();

j=1;
while(j<=SQRTMAXNUM) {
  while (*(a+j)==0)
    j++;
  for (i=j;i<top;i=i+j+1)
    if (i>j) {
      *(a+i)=0;
  }
  j++;
}


*(a)=1;

report_time(0);
printf("primenums: counting primes - SWAR reduction...\n");
// sysregs_init();

redmask[0]=0xffffffff;
// redmask[0]=0x01010101;
acc=0;
// printf("#5.0 acc=%d\n",acc); // when commented, the previous assignment acc=0 is not executed
sysregs_init();
// printf("#5.1 init redmask[0]=%08X\n",*((int*)&redmask[0]));
redmask[0]=redmask[0]*redmask[0];
// printf("#5.2 init redmask[0]=%08X\n",*((int*)&redmask[0]));
#pragma swar reduce
for (i=0;i<MAXSLOTS;i++) {
  redmask[1] = redmask[0] * (*(u8b*)(((void*)a)+i*PACKING));
  acc+=*((int *)&redmask[1]);
//   printf("#6 *(a+%d*PACKING)=%08X redmask[1]=%08X acc=%d\n",i,*(int*)(((void*)a)+i*PACKING),*((int*)&redmask[1]),acc);
}

report_time(1);
printf("primenums: primes found: %d\n\n",acc);
sysregs_init();

#ifdef PRINT_ITEMS
#ifdef VERBOSE
printf("primenums: printing primes\n");
#endif
for (i=1;i<top;i++)
#ifdef VERBOSE
  if (*(a+i)==1) {
    printf("%d\n",i);
  }
#else
  if (*(a+i)==1) {
    printf("1");
  }
  else
    printf("0");
#endif
printf("\n");
#endif

printf("\nprimenums: VERSION_CHAR_SWAR done\n\n\n");

#endif


// -------------------------------------------------------------



// sysregs_stop();
// sysregs_read(&ticks_lo, &ticks_hi, &insns_lo, &insns_hi);
//
// if (ticks_hi) {
//   m_print("TEST EXECUTED IN ("); i_print(ticks_hi); m_print(" * 2^32 + "); i_print(ticks_lo); m_print(") TICKS AND ("); i_print(insns_hi); m_print(" * 2^32 + "); i_print(insns_lo); m_print(" INSTRUCTIONS");NL;NL;
// }
// else {
//   m_print("TEST EXECUTED IN "); i_print(ticks_lo); m_print(" TICKS AND "); i_print(insns_lo); m_print(" INSTRUCTIONS");NL;NL;
//  }



  printf("\n*** END OF TEST ***\n");

  system_done();

  return 0;
}