/*  IK2PIH ALOHA Simulator  V1.0 
    a pure/slotted aloha time-driven simulation
    written by IK2PIH, Marco on 20 jan 2021

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.  */


#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>

#define DURATION 524287  /* number of time slots */
#define PACLEN 32        /* lenght of a packet in time slots */
#define BITS 32          /* number of stations + digipeater */
#define MAXRATE 255      /* max tx rate */

/* function prototypes */
void simulate(int p, int typ, int dig, int *gn, int *sn);
int tx(int p, int typ, int t);
void exportcsv(int *gn, int *sn);
void drawcross(char *img, int x, int y, int l);
void drawtheor(char *img, int typ, int dig);
void drawaloha(int *gn, int *sn, int typ, int d);
void clear(char *img);
void plot(char *img, int x, int y, char c);
void iswap(int *a, int *b);
void line(char *img, int x1, int y1, int x2, int y2, char c);
void byte2hex(char c, char *hc, char *lc);
void save(char *img, char *filename);
void axis(char *img, char a, char g);
void put14seg(char *img, int x, int y, char n);
void write14seg(char *img, int x, int y, char *s);




int main()
{
 int p;      /* transmission rate */
 int typ=0;  /* type of simulation ('p'=pure, 's'=slotted) */
 int dig=0;  /* digipeater ('y'=yes, 'n'=no) */
 int gra=0;  /* outputs a graphic file ('y'=yes, 'n'=no) */
 int csv=0;  /* outputs a csv file (separator=semicolon) ('y'=yes, 'n'=no) */
 time_t begin,end;

 /* allocate arrays for normalized traffic (gn) and throughput (sn) */
 int gn[MAXRATE];
 int sn[MAXRATE];

 /* screen header */ 
 printf("---------------------------------------\n");
 printf("         IK2PIH ALOHA simulator\n");
 printf("---------------------------------------\n");
 putchar('\n');
 
 /* get inputs from stdin */ 
 printf("Pure or slotted aloha? (p/s) ");
 while(typ!='p' && typ!='s')
                 typ=getchar();

 printf("Digipeater? (y/n) ");
 while(dig!='y' && dig!='n')
                 dig=getchar();

 printf("Draw a graphic output file? (y/n) ");
 while(gra!='y' && gra!='n')
                 gra=getchar();

 printf("Create a CSV output file? (y/n) ");
 while(csv!='y' && csv!='n')
                 csv=getchar();
 
 putchar('\n');
 printf("Starting simulation.\n"); 

 /* initialize random numbers generator and set start time */
 srand(time(&begin)); 
 
 /* clear normalized traffic and throughput arrays */
 for(p=0;p<MAXRATE;p++)
                   {gn[p]=0;
                    sn[p]=0;}

 /* repeat simulation for all tx rates, but only if gn<200 */
 for(p=1;(p<MAXRATE)&&(gn[p-1]<200);p++)
                   {/* simulate and print results to stdout */
                    simulate(p,typ,dig,gn,sn);        
                    printf("gn%% = %4d     -     sn%% x 10 = %4d\n",gn[p],sn[p]);}

 time(&end); /* Set end time */

 putchar('\n');
 printf("Simulation completed in %.0f seconds.\n",difftime(end,begin)); 


 /* draw graphic if requested */
 if(gra=='y')
     {drawaloha(gn,sn,typ,dig);
      printf("Graphic saved in file 'alohasim.xbm'\n");}

 /* output csv file if requested */
 if(csv=='y')
      {exportcsv(gn,sn);
       printf("Data exported in file 'alohasim.csv'\n");}
 
 return(0);
}





/* simulate an aloha session; p=tx rate, typ=type(pure/slotted) dig=digi(y/n) */
/* return normalized traffic gn and normalized throughput sn */
void simulate(int p, int typ, int dig, int *gn, int *sn)
{
 int a,t,x,y,s,g,k;
 int *f;

 /* a=tx output */
 /* t=time counter */
 /* x,y=counters */
 /* s=throughput (packets) */
 /* g=traffic (packets) */
 /* k=bit counter for collision check */

 /* reset traffic and throughput counter */
 g=0;
 s=0;

 /* allocate the empty array f for simulation */
 if(!(f=(int*)calloc(DURATION,sizeof(int))))
      {fprintf(stderr,"Can't allocate memory\n");
       exit(EXIT_FAILURE);}
      
 for(t=PACLEN;t<DURATION-PACLEN;t++)
            {
             /* isolate valid packets and increment throughput counter s */  
             for(x=0;x<(BITS-1);x++)  /* repeat for all stations */
                       {
                       k=0;
                       for(y=1;y<=PACLEN;y++)          /* control if there was a collision */
                                 if(f[t-y]==(1<<x)) k++;
                       if(k==PACLEN)                   /* if no collisions */ 
                            {for(y=1;y<=PACLEN;y++)    /* delete the packet from stream */
                                             f[t-y]=0;
                             s++;                      /* increment throughput counter */
                       
                             if(dig=='y')           /* digipeat valid packet if required */
                                   {for(y=0;y<PACLEN;y++)
                                          f[t+y]|=(1<<(BITS-1));
                                    t+=PACLEN;}
                             }                         
                       } 


               /* send packets randomly and increment traffic counter g */
               for(x=0;x<BITS-1;x++)    /* repeat for all stations */
                      {/* send a packet randomly but only if channel is idle */  
                       a=tx(p,typ,t);      
                       if((a==1) && ((f[t]&(1<<x))==0) && ((f[t]&(1<<(BITS-1)))==0))
                                        {g++;
                                         for(y=0;y<PACLEN;y++)
                                                     f[t+y]|=(1<<x);
                                         }
                       }
 
             
             }

  /* calculates normalized traffic (%) and normalized throughput x 10 (%) for current tx rate p */
  gn[p]=g*100*PACLEN/(DURATION-2*PACLEN);    /* normalized traffic */
  sn[p]=s*1000*PACLEN/(DURATION-2*PACLEN);   /* normalized throughput x 10 */
  
  /* deallocate array f */
  free(f);
  return;
}





/* transmit randomly unslotted (typ='p') or slotted (typ!='p')  packets */
int tx(int p, int typ, int t)                           
{ 
 int n,r,k;
 
 if(typ=='p') k=32768;
 else k=2048;

 r=0;

 if((typ=='p')||(t%PACLEN==0))
  {
   n=(rand() % k);
   if(n<p)
        r=1;
  }
 return(r);
} 







/* export output in csv format (actual separator is a semicolon ';') */
void exportcsv(int *gn, int *sn)
{
 int p;
 FILE *fp;
 char filename[13]="alohasim.csv";
 
 /* open the file alohasim.csv for writing */
 if(!(fp=fopen(filename,"w")))
   {fprintf(stderr,"Can't open the file\n");
    exit(EXIT_FAILURE);}
 
 /* print the first row of the csv file with the headers*/
 fprintf(fp,"gn;sn\n");

 /* print the rest of the csv file */
 for(p=0;(p<=MAXRATE)&&(gn[p]<200);p++)
    fprintf(fp,"%d;%d\n",gn[p],sn[p]);
 
 /* close the file */
 fclose(fp);

 return;
}







/* Draw the graph to file "alohasim.xbm" in current directory */
void drawaloha(int *gn, int *sn, int typ, int dig)
{
 int p;
 char img[32767];
 char imagename[13]="alohasim.xbm";

 /* clear the image and draw axes */
 clear(img);
 axis(img,0,2);
 axis(img,1,2);

 /* plot simulation results on the graphic */
 for(p=0;(p<=MAXRATE)&&(gn[p]<200);p++)
     drawcross(img,2*gn[p]+50,sn[p]+50,2);
 
 /* draw the theoretical curve */
 drawtheor(img,typ,dig);

 /* write the title of the graph */
 if(typ=='p'&&dig=='n') write14seg(img,180,470,"PURE ALOHA\0");
 else if(typ=='p'&&dig=='y') write14seg(img,100,470,"PURE ALOHA WITH DIGIPEATER\0");
 else if(typ=='s'&&dig=='n') write14seg(img,160,470,"SLOTTED ALOHA\0");
 else write14seg(img,85,470,"SLOTTED ALOHA WITH DIGIPEATER\0");

 /* save the graphic in xbm format in the file "alohasim.xbm", current directory */
 save(img,imagename);
 
 return;
}
 
 


 

/* draw a cross at (x,y) */
void drawcross(char *img, int x, int y, int l)
{
 int i,k;

 k=2*l;

 for(i=0;i<=k;i++)
    {plot(img,x-l+i,y,1);
     plot(img,x,y-l+i,1);}
 
 return;
}






/* draw the theoretical curves for comparison */
void drawtheor(char *img, int typ, int dig)
{
 int x,g,s,go,so;
 double gd,sd,k;
 /* x=loop counter */
 /* g,s=current traffic and throughput (integer) */
 /* go,so=previous traffic and throughput (integer) */
 /* gd,sd=current traffic and throughput (double) */
 /* k=coefficient of the exponent in the aloha formula */

 /* if pure, coeffficient k=2, else k=1 */
 if(typ=='p') k=2.0;
 else k=1.0;

 /* set previous values of integer traffic and throughput to 0 */
 go=0;
 so=0;

 x=0; /* initialize loop counter */

 while((g<=400)&&(x<=32767))
    {/* calculates throughput with theoretical formula s=Gexp(-kG) */
     gd=((double)x)/200.0;
     sd=gd*exp(-k*gd);

     /* renormalize if digipeater=yes */
     if(dig=='y')
       {gd=gd/(1.0+sd);
        sd=sd/(1.0+sd);
        g=(int)floor(200.0*gd); /* we need an integer traffic in order to draw it, with digi... */
       }
     else
        g=x;  /* ...and without a digi */

     /* we need also an integer throughput in order to draw it */  
     s=(int)floor(sd*1000.0);
 
     /* draw the graph by joining the points with lines */ 
     line(img,go+50,so+50,g+50,s+50,1);
     
     /* current integer traffic and throughput become the previous ones */
     go=g;
     so=s;
     
     /* increment loop counter */
     x++;}

 return;
}






/* Draw x or y axis (a=0->x a=1->y), g=grid(0,1,2) */
void axis(char *img, char a, char g)
{
 int x,y;
 /* draw the axis: a=0 -> x, a!=0 -> y */
 for(x=50;x<480;x++)
      {if(a==0) plot(img,x,50,1);
      else plot(img,50,x,1);}

 /* draw the arrow */
 for(x=0;x<10;x++)
     {if(a==0) plot(img,480-x,50+x,1);
      else plot(img,50+x,480-x,1);
      if(a==0) plot(img,480-x,50-x,1);
      else plot(img,50-x,480-x,1);}

 /* draw tics every 10 units */
 for(x=50;x<=450;x+=10)
   for(y=47;y<50;y++)
         {if(a==0) plot(img,x,y,1);
          else plot(img,y,x,1);}

 /* extend tics every 100 units */
  for(x=50;x<=450;x+=100)
    for(y=41;y<47;y++)
         {if(a==0) plot(img,x,y,1);
          else plot(img,y,x,1);}

 /* draw the grid if g=1 */
  if(g==1||g==2)
     for(y=150;y<=450;y+=100) 
             for(x=50;x<450;x++)
                      {if(a==0) plot(img,x,y,1);
                       else plot(img,y,x,1);}

 /* draw the secondary grid if g=2*/
  if(g==2)
     for(y=100;y<=400;y+=100) 
             for(x=50;x<450;x+=2)
                      {if(a==0) plot(img,x,y,1);
                       else plot(img,y,x,1);}
 
 /* write the numbers */
  if(a==0)
       {write14seg(img,46,20,"0\0");
        write14seg(img,146,20,"50\0");
        write14seg(img,234,20,"100\0");
        write14seg(img,334,20,"150\0");
        write14seg(img,434,20,"200\0");}
  else
       {write14seg(img,28,42,"0\0");
        write14seg(img,16,142,"10\0");
        write14seg(img,16,242,"20\0");
        write14seg(img,16,342,"30\0");
        write14seg(img,16,442,"40\0");}
 return;
}







/* write chars (0123456789/-+*=><ABCDEFGHIJKLMNOPQRSTUVWXYZ) in 14 seg format at (x,y) */
/* used by the "write14seg" function */
void put14seg(char *img, int x, int y, char n)
{
 /* characters belonging to each segment */
 char a[25]="02356789ABCDEFGIOPQRSTZ$$";
 char b[25]="0123489ABDHJMNOPQRUW$$$$$";
 char c[25]="01345689ABDGHJMNOQSUW$$$$";
 char d[25]="0235689BCDEGIJLOQSUZ=$$$$";
 char e[25]="0268ACEFGHJKLMNOPQRUVW$$$";
 char f[25]="045689ACEFGHKLMNOPQRSUVW$";
 char g1[25]="2456789AEFHKPRS-+*=$$$$$$";
 char g2[25]="23456789ABEGHPRS-+*=$$$$$";
 char h[25]="MNXY*>$$$$$$$$$$$$$$$$$$$";
 char i[25]="BDIT+*$$$$$$$$$$$$$$$$$$$";
 char j[25]="17KMVXYZ*/<$$$$$$$$$$$$$$";
 char k[25]="VWXZ*/>$$$$$$$$$$$$$$$$$$";
 char l[25]="7BDITY+*$$$$$$$$$$$$$$$$$";
 char m[25]="KNQRWX*<$$$$$$$$$$$$$$$$$";

 int z; /* counter */

 /* for each of the 14 segments draw the corresponding line if required */
 for(z=0;z<=24;z++)
         {if(n==a[z]) line(img,x,y+16,x+8,y+16,1);
          if(n==b[z]) line(img,x+8,y+8,x+8,y+16,1);
          if(n==c[z]) line(img,x+8,y,x+8,y+8,1);
          if(n==d[z]) line(img,x,y,x+8,y,1);
          if(n==e[z]) line(img,x,y,x,y+8,1);
          if(n==f[z]) line(img,x,y+8,x,y+16,1);
          if(n==g1[z]) line(img,x,y+8,x+4,y+8,1);
          if(n==g2[z]) line(img,x+4,y+8,x+8,y+8,1);
          if(n==h[z]) line(img,x+4,y+8,x,y+16,1);
          if(n==i[z]) line(img,x+4,y+8,x+4,y+16,1);
          if(n==j[z]) line(img,x+4,y+8,x+8,y+16,1);
          if(n==k[z]) line(img,x+4,y+8,x,y,1);
          if(n==l[z]) line(img,x+4,y+8,x+4,y,1);
          if(n==m[z]) line(img,x+4,y+8,x+8,y,1);}
return;
}







/* write strings in 14 segment format */
void write14seg(char *img, int x, int y, char *s)
{
 int i;

 i=0;
 while(s[i]!='\0')
      {put14seg(img,x+i*12,y,s[i]);
       i++;}
 return;
}







/* clear the image */
void clear(char *img)
{
 int i;
 for(i=0;i<=32767;i++)
                   img[i]=0;
 return;
}






/* set/reset the point (x,y) */
void plot(char *img, int x, int y, char c)
{
 if((x>=0)&&(y>=0)&&(x<=511)&&(y<=511)&&((c==0)||(c==1)))
  {if(c==0) img[x/8+(64*(511-y))]&=~(1<<(x%8));
   else     img[x/8+(64*(511-y))]|=(1<<(x%8));}
 return;
}






/* swap the two integers a and b (used by "line" function) */
void iswap(int *a, int *b)
{
 int t;
 t=*a;
 *a=*b;
 *b=t;
 return;
}






/* draw a black/white line from x1,y1 to x2,y2 with Bresenham */
void line(char *img, int x1, int y1, int x2, int y2, char c)
{
 int x,y,adx,ady,m,e,s;

 adx=abs(x2-x1);
 ady=abs(y2-y1); 
 s=0;

 if(adx<ady)
     {iswap(&x1,&y1);
      iswap(&x2,&y2);
      iswap(&adx,&ady);
      s=1;}
 
 if(x1>x2)
     {iswap(&x1,&x2);
      iswap(&y1,&y2);}

 m=2*ady;
 e=m-adx;
 for(x=x1,y=y1;x<=x2;x++)
                   {if(s==0) plot(img,x,y,c);
                    else     plot(img,y,x,c);
                    e+=m;
                    if(e>0)
                          {if(y2>=y1) y++;
			   else       y--;
	                   e-=2*adx;}
                    } 
 return;
}







/* convert a byte to it's hexadecimal equivalent (used by "save" function) */
void byte2hex(char c, char *hc, char *lc)
{
 char l,h; 

 l=(c & 0x0f);
 if(l<=9) *lc='0'+l;
 else *lc='a'+l-10;

 h=((c>>4) & 0x0f);
 if(h<=9) *hc='0'+h;
 else *hc='a'+h-10;

 return;
}






/* save the image to disk in xbm format */
void save(char *img, char *filename)
{
FILE *fp;
int i,j;
char hc,lc;

if(!(fp=fopen(filename,"w")))
   {fprintf(stderr,"Can't open the file\n");
    exit(EXIT_FAILURE);}

fprintf(fp,"#define image_width 512\n");
fprintf(fp,"#define image_height 512\n");
fprintf(fp,"static unsigned char image_bits[] = {\n");

for(j=0;j<=511;j++)
   {for(i=0;i<=63;i++)
        {byte2hex(img[i+64*j],&hc,&lc);
         if(!((j==0) && (i==0)) && (i%16==0)) fprintf(fp,"\n");
         fprintf(fp,"0x%c%c",hc,lc);
         if(!((j==511) && (i==63))) fprintf(fp,",");}
   }
 
fprintf(fp,"};\n");
fclose(fp);
return;
}