/***********************************************************************
statecov.c : File which outlines a deterministic algorithm to cover as many 
tri-sequence states in the minimum sequence length
***********************************************************************/

#include <stdio.h>
#define MAX_OPTIONS 16
#define MODIFY 1
#define SEARCH 0
#define ASCII_A 65
#define MAX_CLASSES 10
#define MAX_INST_IN_CLASS 20
#define MAX_INP_LENGTH 20
#define MAXLEVELS 5
#define MAX_TOTAL_CLASSES 30000

typedef struct node_type {
   struct node_type* successor[MAX_OPTIONS]; /* pointers to subsequent nodes */
   int available;			     /* whether path has been taken */
   char descrip[MAX_INP_LENGTH];
} nd;

struct node_type* top_nodes[MAX_OPTIONS];    /* top level array */
char instructions[MAX_CLASSES][MAX_INST_IN_CLASS][MAX_INP_LENGTH];
char classes[MAX_CLASSES][MAX_INP_LENGTH];
int inst_per_class[MAX_CLASSES];
char * inst_classes[MAX_TOTAL_CLASSES];

int sequence_length = 32767;
int class_no = 3;
char outname[MAX_INP_LENGTH];
char infile[20];
int successcount = 0;
int backtrackcount = 0;
int cur_successcount = 0;
int cur_backtrackcount = 0;
int classcount = 0;
int inst_class_count = 0;
FILE *fp;
int bias_file_given = 0;
char bias_filename[64];

/**********************************************************************
This function initializes the tree structure. Given the depth of the tree in
level, the function makes an n-ary tree (n: Options) with the given node as 
root
**********************************************************************/
void init (int level, struct node_type* node[])
{
   int i,j;

   for (i = 0; i < classcount; i++) {
      node[i] = (struct node_type*)malloc(sizeof(struct node_type));
      node[i]->available = 1;
      strcpy (node[i]->descrip, classes[i]);
      if (level) 
         init (level - 1, node[i]->successor);
      else {
         for (j = 0; j < classcount; j++)
	    node[i]->successor[j] = NULL;
      }
   }
   return;
}

/****************************************************************************
This prints the header for the output files
****************************************************************************/

void print_header (char c[], FILE *f, int seq) {
   int i, j;
   char s;
   FILE *bias_fp;

   fprintf (f, "c=> OutFile = %s.out\n", c);
   fprintf (f, "c=> LstFile = %s.lst\n", c);
   fprintf (f, "c=> InstMemFile = %s.imem\n", c);
   fprintf (f, "c=> DataMemFile = %s.dmem\n", c);
   fprintf (f, "c=> RegistersRefFile = %s.regsr\n", c);
   fprintf (f, "c=> DataMemRefFile = %s.dmemr\n", c);
   fprintf (f, "c=> CovFile = %s.cov\n", c);
   fprintf (f, "c=> LstOrder = sequential\n");
   fprintf (f, "c=> InstPerTest = %d\n", seq);
   for (i = 0; i < classcount; i++) {
      fprintf (f, "c=> InstLst %s = {", classes[i]);
      for (j = 0; j <= inst_per_class[i]; j++) {
         fprintf (f, "%s", instructions[i][j]);
         if (j != inst_per_class[i]) 
            fprintf (f, ", ", instructions[i][j]);
      }
      fprintf (f, "}\n");
   }
   if (bias_file_given) {
      bias_fp = fopen (bias_filename, "r");
      while ((s = fgetc (bias_fp)) != EOF) {
         fputc (s, f);
      }
      fclose (bias_fp);
   }
}

/************************************************************************
This function finds the next free successor node and returns its number.
This function can be used in two modes, MODIFY and SEARCH. MODIFY
changes "available", SEARCH will not. 
************************************************************************/

int choice (struct node_type* n, int mode, char c[])
{  
   int i;

   for (i = 0; i < classcount; i++) {
      if (n->successor[i]->available) {
         sprintf (c, "c=> Genlst %s", n->successor[i]->descrip);
         if (mode) 
            n->successor[i]->available = 0;
         return(i);
      }
   }
   n->available = 0;
   inst_class_count--; /* This is a very bad patch as inst_class_count 
			is incremented for every call of choice */
   return (-1);
}

/*************************************************************************
This function returns a successor node corresponding to the i-th successor
This is used mainly to update the position pointers
*************************************************************************/
struct node_type* search (struct node_type *n1, int choice)
{
   return n1->successor[choice];
}

/*************************************************************************
This prints the help message
*************************************************************************/
void print_help() {
   printf ("Statecov: Automatic bias generator for biased random %s\n\n",
           "instruction generation");
   printf ("Usage: \n");
   printf ("statecov [-i/p][-s <seq_length>][-c <number of pipeline stages>]\n");
   printf ("         [-h][-o <output_prefix>][-b <bias_file>] <input_file>\n");
   printf ("Options:\n");
   printf ("  -i: generate biases for all individual instructions\n");
   printf ("  -p: generate biases for all instruction pairs\n");
   printf ("      Note: -i and -p options are mutually exclusive\n");
   printf ("  -s <seq_length>: specify maximum number of instructions %s\n",
           "per file");
   printf ("     Note: -s option should not be used with -i or -p\n");
   printf ("  -c <number of pipeline stages>: specify whether instruction\n");
   printf ("     triples, quadruples, or quintuples will be generated\n");
   printf ("     Note: number must be 3 or greater\n");
   printf ("  -h: print this help message\n");
   printf ("  -o <output_prefix>: specify first part of output file name\n");
   printf ("  -b <bias_file>: specify file containing additional biases\n");
   printf ("                  to include in output files\n");
   return;
}

/************************************************************************
This reads the input file
************************************************************************/
void read_input_file (char name[]) {
   FILE *f;
   char inp[20];
   int instructioncount = -1;
   int i,j;
  
   f = fopen (name, "r");
   while (!feof (f)) {
      fscanf (f, "%s", inp);
      if (!strcmp (inp, "#end")) 
         break;
      if (!strcmp (inp, "#class")) {
         fscanf (f,"%s",inp);
         strcpy (classes[classcount], inp);
         inst_per_class[classcount] = -1;
         classcount++;
      } else {
         inst_per_class[classcount - 1]++;
         strcpy (instructions[classcount - 1][inst_per_class[classcount - 1]], inp);
      }
   }
   fclose (f);
}

/********************************************************************************
The initial sequence
********************************************************************************/
       
void initial_setting (int level, struct node_type *node_at_level[], 
    struct node_type *root_node, int node_no_at_level[])
{
   node_at_level[level] = root_node->successor[0];
   node_no_at_level[level] = 0;
   inst_classes[inst_class_count] = (char *)malloc(80 * (sizeof(char)));
   sprintf (inst_classes[inst_class_count], "c=> GenLst %s",
            node_at_level[level]->descrip);
   inst_class_count++;
   if (level != 1) 
      initial_setting (level-1 , node_at_level, root_node->successor[0], 
                       node_no_at_level);
   return;
}

/********************************************************************************
Updates the position pointers
********************************************************************************/

void update (int level, struct node_type *node_at_level[], 
	struct node_type *root_node, int node_no_at_level[]) 
{
   int newlevelvalue;

   newlevelvalue = node_no_at_level[level-1];
   node_no_at_level[level] = newlevelvalue;
   node_at_level[level] = root_node->successor[newlevelvalue];
   if (level != 2) 
      update (level-1, node_at_level, root_node->successor[newlevelvalue], 
              node_no_at_level);
   return;
}

/*********************************************************************************
Function which gives the shortest sequence length for covering the maximum number of 
instruction class triples, quadruples, quintuples
*********************************************************************************/

void shortest_sequence() 
{
   struct node_type* top_node, *top_node_plus_one, *root_node;
   int node_choice;
   int top_node_no = 0;
   int top_node_plus_one_no = 0;
   struct node_type *node_at_level[MAXLEVELS];
   struct node_type *temp_node_at_level[MAXLEVELS];
   int node_no_at_level[MAXLEVELS];
   int temp_choice, i, j;
     
   init (class_no-1, top_nodes);        /* Initialize the top nodes*/
  
   root_node = (struct node_type *)malloc(sizeof(struct node_type));
  
   for (i = 0; i < classcount; i++) { 
			    /* Set root node as the parent of top->nodes */
      root_node->successor[i] = top_nodes[i];
   }
  
   node_at_level[class_no] = root_node;
   initial_setting (class_no-1, node_at_level, root_node, node_no_at_level);

   while (1) {
      inst_classes[inst_class_count] = (char *)malloc(80 * (sizeof(char)));
      node_choice = choice (node_at_level[1], MODIFY,
                            inst_classes[inst_class_count]);
      inst_class_count++;
  
      if (node_choice == -1) {  /* No path, search in next subtree */
         backtrackcount++;
         for (j = 2; j <= class_no; j++) {
            temp_node_at_level[class_no] = root_node;
            for (i = class_no-1; i > (1+j-2); i--) {
               temp_node_at_level[i] = 
                 temp_node_at_level[i+1]->successor[node_no_at_level[i-(1+j-2)]];
            }
            inst_classes[inst_class_count] = 
              (char *)malloc(80 * (sizeof(char)));
            temp_choice = choice (temp_node_at_level[j], SEARCH,
                                  inst_classes[inst_class_count]);
            inst_class_count++;

            if (temp_choice!=-1) break;
         }
         if (temp_choice == -1) {
             printf ("Sequence Generation complete\n");
	     printf ("Combinations found: %d\n", successcount);
	     printf ("Backtracks performed: %d\n", backtrackcount);
             return;
	 }
         node_choice = temp_choice;
      } else{
         successcount++;
      }
      update (class_no - 1, node_at_level, root_node, node_no_at_level);

      node_at_level[1] = search (node_at_level[2], node_choice);
			   /*Update pointers */
      node_no_at_level[1] = node_choice;
   }
}

/*****************************************************************************
Prints all individual instructions, one to a file
*****************************************************************************/

void all_indiv()  
{
   int i, j;
   int fileno = 0;
   char filename[MAX_INP_LENGTH];
   char act_filename[MAX_INP_LENGTH];
   char fileno_char[4];
   FILE *f;
   for (i = 0; i < classcount; i++) {
      for (j = 0; j <= inst_per_class[i]; j++) {
         strcpy (filename, outname);
         sprintf (fileno_char, "%d", fileno);
         strcat (filename, fileno_char);
         strcpy (act_filename, filename);
         strcat (act_filename, ".bitg");
         f = fopen (act_filename, "w");
         print_header (filename, f, 1);
         fprintf (f, "c=> Gen %s\n", instructions[i][j]);
         fclose (f);
         fileno++;
      }
   } 
}

/******************************************************************************
Prints allpairs of instructions to separate files
******************************************************************************/
void all_pairs() 
{
   int i,j,k,l;
   int fileno = 0;
   char filename[MAX_INP_LENGTH];
   char act_filename[MAX_INP_LENGTH];
   char fileno_char[4];
   char firstline[80];
   FILE *f;

   for (i = 0; i < classcount; i++) {
      for (j = 0; j <= inst_per_class[i]; j++) {
         sprintf (firstline, "c=> Gen %s", instructions[i][j]);
         for (k = 0; k < classcount; k++) {
             for (l = 0; l <= inst_per_class[k]; l++){
                 strcpy (filename, outname);
                 sprintf (fileno_char, "%d", fileno);
                 strcat (filename, fileno_char);
                 strcpy (act_filename, filename);
                 strcat (act_filename, ".bitg");
                 f = fopen (act_filename, "w");
                 print_header (filename, f, 2);
                 fprintf (f, "%s\n", firstline);
                 fprintf (f, "c=> Gen %s\n", instructions[k][l]);
                 fclose (f);
                 fileno++;
             }
         }
      }
   } 
}

/************************************************************************
The Inst_per_test field was getting the maximum instead of actual value, 
patch for that 
************************************************************************/         
void print_file (int num_inst) 
{
   FILE * f1;
   char s[200];
   char name[MAX_INP_LENGTH];
   char name1[MAX_INP_LENGTH];
   char num_rep[4];
   int i, fileno = 0;
   int upperbound = sequence_length;
   int lowerbound = 0;
   int overlap = class_no - 1;
 
   while (num_inst > sequence_length) {
      strcpy (name, outname);
      sprintf (num_rep, "%d", fileno);
      strcat (name, num_rep);
      strcpy (name1, name);
      strcat (name, ".bitg");

      f1 = fopen (name, "w");
      print_header (name1, f1, sequence_length);
      for (i = lowerbound; i < upperbound; i++) {
	 fprintf (f1, "%s\n", inst_classes[i]);
      }
      fclose (f1);
      /* num_inst = num_inst - sequence_length + classcount; */
      num_inst = num_inst - sequence_length + overlap; 
      fileno++;
      /* lowerbound=lowerbound + sequence_length - classcount; */
      lowerbound=lowerbound + sequence_length - overlap;
      /* upperbound=upperbound + sequence_length - classcount; */
      upperbound=upperbound + sequence_length - overlap;
   }
   strcpy (name, outname);
   if (fileno > 0) {
      sprintf (num_rep, "%d", fileno);
      strcat (name, num_rep);
   }
   strcpy (name1, name);
   strcat (name, ".bitg");

   f1 = fopen (name, "w");
   print_header (name1, f1, num_inst);
   for (i = lowerbound; i < lowerbound + num_inst; i++) {
      fprintf (f1, "%s\n", inst_classes[i]);
   }
   fclose (f1);
} 


/************************************************************************/

main (int argc, char **argv)
{
   int c;
   int indpair = 2;
   char name[MAX_INP_LENGTH];
   char act_name[MAX_INP_LENGTH];
   int i;
 
   extern char *optarg;
   extern int optind, opterr;

   if ((argc == 1) || (argv[argc - 1][0] == '-')) {
      print_help();
      exit (1);
   }

   strcpy (infile, argv[argc-1]);
   if ((fopen (infile, "r"))) {
      read_input_file (infile);
   } else {
      printf ("Error reading input file: %s\n", argv[argc-1]);
      exit (2);
   }
	 
   strcpy (outname, "test");
   while ((c = getopt (argc, argv, "iphs:c:o:b:")) != EOF) {
      switch (c) {
          case 'i':
            printf ("Individual instructions\n");
            indpair = 0;
            break;
          case 'p':
            printf ("Instruction pairs\n");
            indpair = 1;
            break;
          case 'h':
            print_help();
            exit (0);
            break;
          case 's':
            sscanf (optarg, "%d", &sequence_length);
            break;
          case 'c':
            sscanf (optarg, "%d", &class_no);
            if (class_no < 3) {
                print_help();
                exit(0);
            }
            break;
          case 'o':
            sscanf (optarg, "%s", outname);
            break;
          case 'b':
            bias_file_given = 1;
            sscanf (optarg, "%s", &bias_filename);
            break;
          default:
            print_help();
            break;
      }
   }
   if (sequence_length <= class_no) {
      printf ("Error: Sequence length must be greater than %d\n", class_no);
      exit (10);
   }
   switch (indpair) {
      case 0:
         all_indiv();
         break;
      case 1:
         all_pairs();
         break;
      case 2:
         shortest_sequence();
         print_file (successcount + backtrackcount + class_no - 1);
         break;
   }
}