Subversion Repositories or2k

/*
  Instruction opcode frequency analysis application
 
  Author:
  Julius Baxter - julius.baxter@orsoc.se
 
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// Opcode space in OR1K is 32-bits, so maximum 64 opcodes
#define MAX_OR1K_32_OPCODES 64
// Array of opcode string pointers (we malloc space for actual strings)
char *opcode_strings[MAX_OR1K_32_OPCODES];
// Count for occurance of each opcode
int opcode_count[MAX_OR1K_32_OPCODES];
 
// Maximum number of pairs to keep track of
#define MAX_OR1K_32_PAIRS (MAX_OR1K_32_OPCODES*MAX_OR1K_32_OPCODES)
// 2-dimensional array, long enough to hold all possible pairs, and the 2
// indexes corresponding to their opcode in the *opcode_strings[] array
// Ie. Each will be: [previous_opcode][current_opcode][count]
int opcode_pairs[MAX_OR1K_32_PAIRS][3];
 
// Maximum number of triplets to kep track of
#define MAX_OR1K_32_TRIPLETS (MAX_OR1K_32_OPCODES*MAX_OR1K_32_OPCODES*MAX_OR1K_32_OPCODES)
// 2-dimensional array, long enough to hold all possible pairs, and the 2
// indexes corresponding to their opcode in the *opcode_strings[] array
// Ie. Each will be: 
//      [second_prev][first_prev][current_opcode][count]
int opcode_triplets[MAX_OR1K_32_TRIPLETS][4];
 
// Maximum number of quadruples to keep track of
#define MAX_OR1K_32_QUADS (MAX_OR1K_32_OPCODES*MAX_OR1K_32_OPCODES*MAX_OR1K_32_OPCODES*MAX_OR1K_32_OPCODES)
// 2-dimensional array, long enough to hold all possible pairs, and the 2
// indexes corresponding to their opcode in the *opcode_strings[] array
// Ie. Each will be: 
//  [third_prev][second_prev][first_prev][current_opcode][count]
int opcode_quads[MAX_OR1K_32_QUADS][5];
 
// Strings shouldn't be more than 32 bytes long
#define OPCODE_STRING_SIZE 32
 
// Indicator for an opcode we haven't seen before
#define IS_UNIQUE -1
 
// Result defines
#define SORTED_DESCENDING_DISPLAY
 
// Style of output  - String or CSV
// Uncomment only 1!
#define DISPLAY_STRING
//#define DISPLAY_CSV
 
// Report only the 10 most common pairs/triples/quadruples, etc
#define MAX_SETS_TO_REPORT 10
 
// Little function to strip newlines
inline void strip_newline(char* str)
{
  int len = strlen(str);
  if (str[len-1] == '\n')
    str[len-1] = '\0';
 
}
 
// Return the position in the index this instruction is at
// else -1 if it isn't
int check_opcode(char *opcode_to_check, int num_opcodes_so_far)
{
  // Get stringlength of current instruction
  int opcode_strlen = strlen(opcode_to_check);
 
  int i = 0;
  // Loop for all opcodes we have so far
  while (i < num_opcodes_so_far)
    {
      // Do we have a match?
      // Debugging output
      //printf("Comparing: %s (%d) == %s (%d) ?\n", 
      //	     opcode_to_check, opcode_strlen,
      //             opcode_strings[i], strlen(opcode_strings[i]));
      if ((strncmp(opcode_to_check, opcode_strings[i], opcode_strlen) == 0)
	  && (strlen(opcode_strings[i]) == opcode_strlen))
	// Found a match - return its index
	return i;
      // No match yet, go to next opcode
      i++;
    }
  // No opcodes found, indicate it's one we haven't seen before
  return IS_UNIQUE;
}
 
// Record an opcode in our list of known opcodes
void add_opcode(char *opcode_to_add, int num_opcodes_so_far)
{
  int opcode_strlen = strlen(opcode_to_add);
 
  // Malloc space to hold the new opcode string
  char *new_opcode;
  new_opcode = (char*) calloc(OPCODE_STRING_SIZE, 1);
 
  // Copy in opcode string
  strncpy(new_opcode, opcode_to_add, opcode_strlen);
 
  // Now store the pointer to this new opcode string
  opcode_strings[num_opcodes_so_far] = new_opcode;
 
  // Initialise count
  opcode_count[num_opcodes_so_far] = 1;
 
  return;  
}
 
// Increment the count for this opcode
void count_opcode(int opcode_index)
{
  opcode_count[opcode_index]++;
 
  return;
}
 
 
 
void display_opcodes(int total_unique_opcodes, int total_opcodes_counted)
{
 
#ifdef DISPLAY_STRING  
  // Totals
  printf("Number of total opcodes: %d\n",total_opcodes_counted);
  printf("Number unique opcodes: %d\n", total_unique_opcodes);
#endif
#ifdef DISPLAY_CSV
  printf("\"Opcode\",\"Occurances\",\"%%'age of total\",\"Total opcodes counted:\",%d\n",total_opcodes_counted);
#endif
 
#ifdef SIMPLE_DISPLAY  
  while (total_unique_opcodes)
    {
      --total_unique_opcodes;
      printf("Opcode:\t%s\tCount:\t%d\n",
	     opcode_strings[total_unique_opcodes],
	     opcode_count[total_unique_opcodes]);
    }
#endif
#ifdef SORTED_DESCENDING_DISPLAY
  int i, largest, largest_index;
  int initial_total = total_unique_opcodes;
  while (total_unique_opcodes)
    {
      --total_unique_opcodes;
      largest=0;
      // Go through the list, find the largest, print it, eliminate it
      for(i=0;i<initial_total;i++)
	if(opcode_count[i] > largest)
	  {
	    largest = opcode_count[i];
	    largest_index = i;
	  }
 
      printf(
#ifdef DISPLAY_STRING      
	     "Opcode:\t%s\tCount:\t%d\t(%f%%)\n",
#endif
#ifdef DISPLAY_CSV
	     // CSV format - "opcode string",frequency,percentage
	     "\"%s\",%d,%f\n",
#endif
	     opcode_strings[largest_index],
	     opcode_count[largest_index],
	     (float)(((float)opcode_count[largest_index])/
		     ((float)total_opcodes_counted))*100.f);
 
 
      opcode_count[largest_index] = -1; // Eliminate this one
 
    }
#endif
 
 
}
 
// Deal with opcode pair checking
int opcode_pair_check( int previous_opcode_index, int current_opcode_index,
		       int total_pairs )
{
  int i;
  // Check through for this pair's occurance before
  for (i=0;i<total_pairs;i++)
    {
      if ((opcode_pairs[i][0] == previous_opcode_index) &&
	  (opcode_pairs[i][1] == current_opcode_index))
	// Found a match
	{
	  opcode_pairs[i][2]++;
	  return 0;
	}
    }
  // No match, let's create a new entry
  // Index for previous opcode
  opcode_pairs[total_pairs][0] = previous_opcode_index;
  // Index for current opcode
  opcode_pairs[total_pairs][1] = current_opcode_index;
  // Count for this pair
  opcode_pairs[total_pairs][2] = 1;
 
  return 1;
 
}
 
 
void opcode_pair_report(int total_opcode_sets)
{
 
  int i, largest, largest_index;
  int initial_total = total_opcode_sets;
 
#ifdef DISPLAY_STRING 
  printf("Number of unique opcode pairs: %d\n", total_opcode_sets);
#endif
#ifdef DISPLAY_CSV
  printf("\"Opcode pair\",\"Occurances\",\"Total unique pairs:\",%d\n", 
	 total_opcode_sets);
#endif
 
  while (total_opcode_sets)
    {
      --total_opcode_sets;
      largest=0;
      // Go through the list, find the largest, print it, eliminate it
      for(i=0;i<initial_total;i++)
	if(opcode_pairs[i][2] > largest)
	  {
	    largest = opcode_pairs[i][2];
	    largest_index = i;
	  }
      printf(
#ifdef DISPLAY_STRING            
	     "Opcode pair:\t%s\t%s\tCount:\t%d\n",
#endif
#ifdef DISPLAY_CSV
	     "\"%s %s\",%d\n",
#endif
 
	     opcode_strings[opcode_pairs[largest_index][0]],
	     opcode_strings[opcode_pairs[largest_index][1]],
	     opcode_pairs[largest_index][2]);
 
 
      opcode_pairs[largest_index][2] = -1; // Eliminate this one
 
      // If we've printed out the maximum we wanted then return
      if ((initial_total - total_opcode_sets) == MAX_SETS_TO_REPORT)
	return;
 
 
    }
 
 
}
 
// Deal with opcode triplet checking
int opcode_triplet_check(int second_previous_opcode_index,  
			 int previous_opcode_index, 
			 int current_opcode_index,
			 int sets_so_far )
{
  int i;
  // Check through for this pair's occurance before
  for (i=0;i<sets_so_far;i++)
    {
      if ((opcode_triplets[i][0] == second_previous_opcode_index) &&
	  (opcode_triplets[i][1] == previous_opcode_index) &&
	  (opcode_triplets[i][2] == current_opcode_index))
 
	// Found a match
	{
	  opcode_triplets[i][3]++;
	  return 0;
	}
    }
  // No match, let's create a new entry
  opcode_triplets[sets_so_far][0] = second_previous_opcode_index;
  // Index for previous opcode
  opcode_triplets[sets_so_far][1] = previous_opcode_index;
  // Index for current opcode
  opcode_triplets[sets_so_far][2] = current_opcode_index;
  // Count for this pair
  opcode_triplets[sets_so_far][3] = 1;
 
  return 1;
 
}
 
void opcode_triplet_report(int total_opcode_sets)
{
 
  int i, largest, largest_index;
  int initial_total = total_opcode_sets;
 
#ifdef DISPLAY_STRING 
  printf("Number of unique opcode triplets: %d\n", total_opcode_sets);
#endif
#ifdef DISPLAY_CSV
  printf("\"Opcode triplet\",\"Occurances\",\"Total unique triplets:\",%d\n", 
	 total_opcode_sets);
#endif
 
  while (total_opcode_sets)
    {
      --total_opcode_sets;
      largest=0;
      // Go through the list, find the largest, print it, eliminate it
      for(i=0;i<initial_total;i++)
	if(opcode_triplets[i][3] > largest)
	  {
	    largest = opcode_triplets[i][3];
	    largest_index = i;
	  }
 
      printf(
#ifdef DISPLAY_STRING
	     "Opcode triplet:\t%s\t%s\t%s\tCount:\t%d\n",
#endif
#ifdef DISPLAY_CSV
	     "\"%s %s %s\",%d\n",
#endif	     
	     opcode_strings[opcode_triplets[largest_index][0]],
	     opcode_strings[opcode_triplets[largest_index][1]],
	     opcode_strings[opcode_triplets[largest_index][2]],
	     opcode_triplets[largest_index][3]);
 
      opcode_triplets[largest_index][3] = -1; // Eliminate this one
 
      // If we've printed out the maximum we wanted then return
      if ((initial_total - total_opcode_sets) == MAX_SETS_TO_REPORT)
	return;
 
    }
}
 
// Deal with opcode triplet checking
int opcode_quad_check(int third_previous_opcode_index,  
		      int second_previous_opcode_index,  
		      int previous_opcode_index, 
		      int current_opcode_index,
		      int sets_so_far )
{
  int i;
  // Check through for this pair's occurance before
  for (i=0;i<sets_so_far;i++)
    {
      if ((opcode_quads[i][0] == third_previous_opcode_index) &&
	  (opcode_quads[i][1] == second_previous_opcode_index) &&
	  (opcode_quads[i][2] == previous_opcode_index) &&
	  (opcode_quads[i][3] == current_opcode_index))
 
	// Found a match
	{
	  opcode_quads[i][4]++;
	  return 0;
	}
    }
  // No match, let's create a new entry
  opcode_quads[sets_so_far][0] = third_previous_opcode_index;
  opcode_quads[sets_so_far][1] = second_previous_opcode_index;
  // Index for previous opcode
  opcode_quads[sets_so_far][2] = previous_opcode_index;
  // Index for current opcode
  opcode_quads[sets_so_far][3] = current_opcode_index;
  // Count for this pair
  opcode_quads[sets_so_far][4] = 1;
 
  return 1;
 
}
 
void opcode_quad_report(int total_opcode_sets)
{
 
  int i, largest, largest_index;
  int initial_total = total_opcode_sets;
 
#ifdef DISPLAY_STRING 
  printf("Number of unique opcode quads: %d\n", total_opcode_sets);
#endif
#ifdef DISPLAY_CSV
  printf("\"Opcode quad\",\"Occurances\",\"Total unique quadruples:\",%d\n", 
	 total_opcode_sets);
#endif
 
  while (total_opcode_sets)
    {
      --total_opcode_sets;
      largest=0;
      // Go through the list, find the largest, print it, eliminate it
      for(i=0;i<initial_total;i++)
	if(opcode_quads[i][4] > largest)
	  {
	    largest = opcode_quads[i][4];
	    largest_index = i;
	  }
 
      printf(
#ifdef DISPLAY_STRING
	     "Opcode triplet:\t%s\t%s\t%s\t%s\tCount:\t%d\n",
#endif
#ifdef DISPLAY_CSV
	     "\"%s %s %s %s\",%d\n",
#endif	     
	     opcode_strings[opcode_quads[largest_index][0]],
	     opcode_strings[opcode_quads[largest_index][1]],
	     opcode_strings[opcode_quads[largest_index][2]],
	     opcode_strings[opcode_quads[largest_index][3]],
	     opcode_quads[largest_index][4]);
 
      opcode_quads[largest_index][4] = -1; // Eliminate this one
 
      // If we've printed out the maximum we wanted then return
      if ((initial_total - total_opcode_sets) == MAX_SETS_TO_REPORT)
	return;      
 
    }
}
 
 
int main(int argc, char *argv[])
{
  FILE *fp;
 
  char current_opcode[OPCODE_STRING_SIZE];  
 
  int num_unique_opcodes = 0;
 
  int opcode_index;
 
  int total_seen_opcodes = 0;
 
  int previous_opcode_indexes[16]; // keep last 16 opcode indexes
 
  int i;
 
  int num_opcode_pairs = 0;
 
  int num_opcode_triplets = 0;
  int num_opcode_quads = 0;
 
 
 
  if((fp = fopen(argv[ 1 ], "r"))==NULL) {
    printf("Cannot open file.\n");
    exit(1);
  }
 
  // Do initial instruction set analysis
  while(!feof(fp)) {
    if(fgets(current_opcode, OPCODE_STRING_SIZE, fp)) 
      {
 
	strip_newline(current_opcode);
	//printf("Checking for: %s \n", current_opcode);
 
	// Find if we have this opcode already, if so we'll get its index in
	// the list, else we'll get an indication that it's unique
	opcode_index = check_opcode(current_opcode, num_unique_opcodes);
 
	if (opcode_index == IS_UNIQUE)
	  {
	    // Add this opcode to our list so we know it now
	    add_opcode(current_opcode, num_unique_opcodes);
	    // Increment the number of known opcodes
	    num_unique_opcodes++;
	  }
	else
	  // Is not unique, just increment the incidences of this opcode
	  count_opcode(opcode_index);
 
	// Track the total number of opcodes we've looked at
	total_seen_opcodes++;
 
	// Error check - bail out early if we're doing something wrong and
	// there's too many unique opcodes (ISA is only so big...)
	if (num_unique_opcodes == MAX_OR1K_32_OPCODES)
	  {
	    printf("Error: Reached maximum opcodes\n");
	    break;
	  }
 
	//printf("So far: unique: %d total: %d\n", 
	//num_unique_opcodes, total_seen_opcodes);
 
      }
  }
 
  // Print some more detailed information
  display_opcodes(num_unique_opcodes, total_seen_opcodes);
 
#ifdef DISPLAY_STRING
  fprintf(stdout,"Beginning groups analysis\n");
#endif
 
  // Now do groups analysis
  rewind(fp);
 
  // Reset total_seen_opcodes, we'll count through the list again
 
  total_seen_opcodes = 0;
 
  while(!feof(fp)) {
    if(fgets(current_opcode, OPCODE_STRING_SIZE, fp)) 
      {
 
	total_seen_opcodes++;
 
	strip_newline(current_opcode);
 
	// Find if we have this opcode already, if so we'll get its index in
	// the list, else we'll get an indication that it's unique
	opcode_index = check_opcode(current_opcode, num_unique_opcodes);
 
	if (opcode_index == IS_UNIQUE)
	  {
	    // Error! Should not have unique opcodes here...
	    printf("Unique opcode detected during pair analysis.\n");
	    break;
	  }
 
	// Now pass this current pair to the function to check if we've seen
	// it before - if not we record it (and return 1) else we just increment
	// count of it (and return 0)
	if (total_seen_opcodes > 1)
	  {
	    if (opcode_pair_check(previous_opcode_indexes[0], opcode_index, 
				  num_opcode_pairs))
	      num_opcode_pairs++;
	  }
 
	if (total_seen_opcodes > 2)
	  {
	    if (opcode_triplet_check(previous_opcode_indexes[1],
				     previous_opcode_indexes[0],
				     opcode_index, 
				     num_opcode_triplets))
	      num_opcode_triplets++;
	  }
	if (total_seen_opcodes > 3)
	  {
	    if (opcode_quad_check(previous_opcode_indexes[2],
				  previous_opcode_indexes[1],
				  previous_opcode_indexes[0],
				  opcode_index, 
				  num_opcode_quads))
	      num_opcode_quads++;
	  }
	// Shift along our list of previously seen opcodes
	for (i=16-1;i > 0; i--)
	  previous_opcode_indexes[i] = previous_opcode_indexes[i-1];
 
	previous_opcode_indexes[0] = opcode_index;
 
      }
  }
 
  opcode_pair_report(num_opcode_pairs);
 
  opcode_triplet_report(num_opcode_pairs);
 
  opcode_quad_report(num_opcode_quads);
 
  // Close file pointer, we're done with it
  fclose(fp); 
 
  // Free all the strings we declared
  while(num_unique_opcodes)
    {
      --num_unique_opcodes;
      free(opcode_strings[num_unique_opcodes]);
    }
 
  //printf("freeing complete: %d\n", num_unique_opcodes);
 
  return 0;
}