#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include "inc/mob.h"
#include "inc/routines.h"
#include "inc/genCode.h"


/* global variables externally defined */
extern struct globalSystem sys;


/* 
   Setup the benchmark data array.
   Currently we try to allocate as much memory as possible up to 64M in 
   quantities of 8M.
   FIXME: the size should be based on which benchmarks are going to be run.
   
   size - requested size.
   return - non-zero on error.
*/
int arrayAllocate( unsigned int size ) {
  
  void * aux;
  unsigned int i, m = M_SIZE( M_1M );
  
  /* loop from 1M to 64M */
  for( i = 0; i <= 8; i++, m = i * M_SIZE( M_8M ) ) {
    /* try to allocate, stop if fail */
    aux = malloc( m * sizeof( char ) );
    if( aux == NULL )
      break;
    free( aux );
  }

  /* check if we even got started and backup one step */
  if( i-- ) {
    /* check if more than 1M */
    if( i )
      sys.arraySize = i * M_SIZE( M_8M );
    else
      sys.arraySize = M_SIZE( M_1M );

    /* allocate correct amount and store in sys structure 
       actually grab enough extra to handle a single return block */
    sys.array = (char *)malloc( (sys.arraySize + retBlockSize()) * sizeof( char ) );
    /* Force the pages to be mapped to real memory (i.e: to avoid ZERO_PAGE
       feature under Linux )*/
    memset( sys.array, 0, sys.arraySize );
    if( sys.array ) {
      show( VERB_NORMAL, "Allocated %uMB of memory for benchmarking\n", sys.arraySize / M_SIZE( M_1M ) );
      return( 0 );
    }
  }
  
  return( -1  );
}


/*
  Prepare the array for a new test.
  This includes checking that the size is correct and writing through the working set.
  This second part seems to be necessary for linux.

  size - required size for test
  return - non-zero value indicates not enough memory for test
*/
int arrayPrepare( unsigned int size ) {

  /* ensure enough memory exists for test */
  if( sys.arraySize < size )
    return( -1 );

  /* write to working set 
     memset( sys.array, 0, size );*/
  
  return( 0 );
}


/* A wrapper function to print according to the system's verbosity. */
int show( verbLevel_t level, char * fmt, ... ){

  va_list ap;
 
  /* Avoid printing plot output if user doesn't set plot verbosity */
  if( level == VERB_PLOT && sys.args.verbosity>VERB_PLOT )
    return 0;

  if( sys.args.verbosity >= level ){
     va_start(ap,fmt);
     return( vprintf(fmt,ap) );
  }
  return 0;
}

/* Handle errors. */
void handleError( char *where, int errno ) {

  printf( "Error %d detected while %s \n", errno, where );
  exit( 1 );
}


/* 
   Return the minimum value between two data points.
*/
double min( double a, double b ) {

  return( (a < b) ? a : b );
}


/* 
   Return the maximum value between two data points.
*/
double max( double a, double b ) {

  return( (a > b) ? a : b );
}


/*
  Return the minimum value from a series of data points.
*/
double getMin( double *data , unsigned int points ) {

  int i;
  double min=data[0];

  if( points <= 0 )
    handleError( "invalid number of points in min ", EinvalParams );

  for( i=0; i < points; i++)
    if( data[i] < min )
      min = data[i];

  return( min );
}


/*
  Return the maximum value from a series of data points.
*/
double getMax( double *data, unsigned int points ) {
  int i;
  double max = data[0];

  if( points <= 0 )
    handleError( "invalid number of points in max ", EinvalParams );

  for( i = 0; i < points; i++ )
    if( data[i] > max )
      max = data[i];
  
  return( max );
}


/* Returns the mean of the array. */
double getMean( double *data , unsigned int points ) {

  int i;
  double acum=0;

  for( i=0; i < points; i++ )
    acum += data[i];

  return( acum / points );
}


/* Returns the standard deviation of the array. */
double getStdDev( double *data , unsigned int points ) {

  int i;
  double mean, acum = 0, dev = 0;
  
  /* need at least two points for a std dev */
  if( points > 1 ) {
   
    /* calculate the mean of the data points */
    mean = getMean( data, points );

    /* sum the square of the difference of each data point
       from the mean */
    for( i = 0; i < points; i++ )
      acum += pow( data[i] - mean, 2.0 );
    
    dev = sqrt( acum / (points - 1) );
  }
  
  return( dev );
}


/* 
   Reverse the data values from the source array.

   data - source of data points
   points - number of data points
   return - new array with reversed data points
*/
double *getReverse( double *data, unsigned int points ) {

  double *reverse;
  unsigned int i, j;

  /* allocate space for the reverse array */
  reverse = (double *)malloc( points * sizeof( double ) );
  if( ! reverse )
    return( NULL );
  
  /* store the data values in reverse order */
  for( i = 0, j = points - 1; i < points; i++, j-- )
    reverse[j] = data[i];

  return( reverse );
}


/*
  Get the rise of the line represented by the data points.
  Spikes will be smoothed out, but the data points are assumed to be fairly linear,
  no attempt is made to ensure linearity.

  data - data points to use as a line
  points - number of data points
  return - rise of smoothed line
*/
double getRise( double *data, unsigned int points ) {

  double *reverse, *dsmooth, *rsmooth, rise;

  /* can't work with less than two points */
  if( points < 2 )
    return( 0.0 );

  /* get the reverse data set */
  reverse = getReverse( data, points );
  if( ! reverse )
    return( 0 );
  
  /* get a smoothed version of the data and reversed data */
  dsmooth = getSmooth( data, points, 0.2 );
  rsmooth = getSmooth( reverse, points, 0.2 );
  /* make sure we got the smooth arrays */
  if( ! (dsmooth && rsmooth) )
    return( 0 );

  /* return the difference between the smoothed end-points,
     each is at the end of the smooth set */
  rise = dsmooth[points-1] - rsmooth[points-1];

  /* free allocated memory */
  free( reverse );
  free( dsmooth );
  free( rsmooth );

  return( rise );
}


/* 
   Get a vector with smoothed values given an alpha value.
   
   data - data points to smooth
   points - number of data points
   return - array of smoothed values
 */
double *getSmooth( double * data, unsigned int points, double alpha ) {

  double last ;
  double * smooth;
  unsigned int i;

  /* allocate new array for smooth values, return if fail */
  smooth = (double *)malloc( points * sizeof(double) );
  if( ! smooth )
    return( NULL );

  last = data[0];
  for( i = 0; i < points; i++ ) {
    last = last * (1 - alpha) + data[i] * alpha ;
    smooth[i] = last;
  }

  return( smooth );
}


/* 
   Find the point with the most votes.
   This function assumes that point zero is never voted on, but simply used as
   an initial dtaa point.  A return value of zero indicates that nothing was voted
   on rather than point zero was most popular.

   votes - list of votes per point
   points - number of points in list
   return - index of popular point, zero if no points were popular, -1 if many points were equally popular
 */
int getPopular( unsigned int *votes, unsigned int points ) {

  unsigned int i, dups = 0, candidate = 0;
  
  /* start with candidate as zero and compare others to find
     individual candidate with most votes */
  for( i = 1; i < points; i++)
    if( votes[i] > votes[candidate] ) {
      candidate = i;
      dups = 0;
    } else if( votes[i] == votes[candidate] )
      dups++;
 
  /* check if candidate has no votes or duplicate candidates had same vote */
  if( ! votes[candidate] )
    return( 0 );
  else if ( dups )
    return( -1 );

  return( candidate );
}


/*
  Return the size of the largest cache found in the system.

  return - size of largest cache
*/
unsigned long getMaxCache( void ) {

  unsigned long maxData, maxInst;
  
  /* get the biggest cache size for each type */
  maxData = (sys.numDataCaches) ? sys.dataCaches[sys.numDataCaches]->size : 0;
  maxInst = (sys.numInstCaches) ? sys.instCaches[sys.numInstCaches]->size : 0;

  /* return the larger of the two */
  return( maxVal( maxData, maxInst ) );
}


/* It trims the leading and trailing spaces/tabs of a string 
   It changes the passed string.
   Returns the pointer to the trimmed string */
char * trim( char * string ){

  char * pnt = string, *start;

  while( isspace( (int)*pnt ) )
    pnt++;
  
  start = pnt;
  
  pnt=&string[strlen(string)-1];
  while( pnt > string && isspace( (int)*pnt ) )
    pnt--;
  *(pnt+1) = '\x0';
  
  /* move string to start (memmove handles overlapping) */
  memmove( string, start, (pnt-start < 0 ? 1 : pnt-start) );

  return string;
}


/* 
   Attempt to detect transitions in the data points 
   using a set of control points to reason about the 
   magnitude of a reasonable transition.

   data - data points to analyze
   control - control points to use as a bound on noise
   points - number of data points
   return - a list of votes per data point
*/
unsigned int *detectTransitions( double *data, double *control, unsigned int points ) {
  
  unsigned int i, poss = 0, possible[points], *votes;
  double bound, last = 0, lookahead;
  double lookback = data[0]; /* Duplicate the first point's value */
  
  /* create votes array */
  votes = (unsigned int*)calloc( points, sizeof( int ) );
  if( ! votes )
    return( NULL );
  
  /* calculate the std. deviation in control times to determine what 
     may be considered a transition rather than a perturbation.
     we consider a change greater than twice the std dev to be noteworthy */
  bound = getStdDev( control, points ) * 2.0;
  
  /* find possible transitions in the measured values,
     using first value for comparison only */
  for( i = 1; i < points; i++ ) {
    double diff, spike;
    
    if( i == points - 1 )  /* If last point */
      lookahead = data[i]; /* (duplicate last) fake a point so it stays in a plateau */
    else
      lookahead = data[i+1];

    /* calculate difference between adjacent points and a value used to consider a spike */
    diff = data[i] - data[i-1];
    spike = data[i-1] + diff / 2;
    
    /* check whether diff is larger than bound, at least a 3rd of a jump of last found transition,
       and it is not a spike */
    if( diff > bound && diff > last / 3 && lookahead > spike && lookback < spike )  {
      /* save index of possible transition for further study, and set value as last seen */
      possible[poss++] = i;
      last = maxVal( last, diff );
    }
    /* save the lookback point for next round*/
    lookback = data[i-1]; 
  }
  
  /* for each possible transition, ensure it isn't a neighbor 
     of a better transition (just interference).
     NOTE: this does not allow us to detect two immediately 
     adjacent cache levels */
  for( i = 0; i < poss; i++ )
    if( i == poss - 1 || possible[i+1] - possible[i] > 1 )
      votes[possible[i]]++;
  
  
  /* return votes of transitions detected */
  return( votes );
}


/* 
   Searches for the biggest transition in the points array.

   returns the index of the max transition, 0 if none are bigger than control
   or -1 if any other error occurs .
*/
int getMaxTransition( double *data, double *control, unsigned int points ) {
  
  unsigned int i;
  int voted=0;
  double bound=0, last = 0, lookahead;
  double lookback = data[0]; /* duplicate the first point's value */
  
  if( control )
    /* calculate the std. deviation in control times to determine what 
       may be considered a transition rather than a perturbation.
       we consider a change greater than twice the std dev to be noteworthy */
    bound = max( getStdDev( control, points ) * 2.0, data[0] * 0.15 );
  
  /* find possible transitions in the measured values,
     using first value for comparison only */
  for( i = 1; i < points; i++ ) {
    double diff, spike;
    
    if( i == points - 1 )  /* If last point */
      lookahead = data[i]; /* (duplicate last) fake a plateau point */
    else
      lookahead = data[i+1];

    /* calculate diff between adjacent points and a value to consider spikes 
       avoid negative differences */
    diff = maxVal( 0, data[i] - data[i-1] );
    spike = data[i-1] + diff / 2;
    
    /* check whether diff is larger than bound, 
       at least a 3rd of a jump of last found transition,
       and it is not a spike */
    if( diff > bound && lookahead > spike && lookback < spike )  {
      /* save index of possible transition for further study, 
	 and set value as last seen */
      if( last < diff ){
	voted = i;
	last = maxVal( last, diff );
      }
    }
    /* save the lookback point for next round*/
    lookback = data[i-1]; 
  }
    
  /* return votes of transitions detected */
  return( voted );
}


/* 
   Searches for the first valid upward transition in the points array.

   returns the index of the biggest transition, 0 if none is bigger than control
   or -1 if any other error occurs .
*/
int getFirstTransition( double *data, double *control, unsigned int points ) {
  
  unsigned int i;
  int voted = 0;
  double bound = 0;
  double lookback = data[0]; /* Duplicate the first point's value */
  
  if( control )
    /* calculate the std. deviation in control times to determine what 
       may be considered a transition rather than a perturbation.
       we consider a change greater than twice the std dev to be noteworthy */
    bound = max( getStdDev( control, points ) * 2.0, data[0] * 0.15 );
  
  /* find possible transitions in the measured values,
     using first value for comparison only */
  for( i = 1; i < points; i++ ) {
    double diff;
    
    /* calculate difference between adjacent points 
       Avoid negative differences */
    diff = maxVal( 0, data[i] - data[i-1] );    
    /* check whether diff is larger than bound - increasing */
    if( diff > bound )  {
      /* save index of first transition */
      voted=i;
      break;
    }
    /* save the lookback point for next round*/
    lookback = data[i-1]; 
  }
    
  /* return transition detected */
  return( voted );
}


/* 
   Attempt to detect a plateau in the data points. Once we've hit the
   correct cache-line size, all subsequent sizes should force a miss 
   on every read.  This should form a plateau starting at the correct
   line size.
   To detect the plateau, we're comparing the changes ahead of us with
   the jump before us.  After us should be calm, before us should be a
   sizable jump.  We're trying different margins (some portion of the 
   total change in access times) and voting on candidate points that 
   fit the profile within that margin.

   data - data points to analyze
   points - number of data points
   return - a list of votes per data point.
*/
unsigned int *detectPlateau( double *data, unsigned int points ) {

  double min, max, lowerBound, margin;
  double * smooth;    
  int i, *votes;
  
  /* create array to hold votes for each candidate point */
  votes = (int *)calloc( points, sizeof( int ) ); 
  /* smooth the data values to remove spikes */
  smooth = getSmooth( data, points, 0.15 );
  if( ! (votes && smooth) )
    return( NULL );
  
  /* get min and max to determine the middle of the range */
  max = getMax( smooth, points );
  min = getMin( smooth, points );
  /* we'll use this as a lower bound for our search,
     the plateau should be at the "max" - definitly above 
     half-way mark */
  lowerBound = min + ( max - min ) / 2;
  
  /* free acquired memory */
  free( smooth );
  
  /* check for a plateau with a range of margins,
     voting on each candidate point that fits within that margin */
  for( margin = 0.16; margin > 0 ; margin -= 0.02 )
    for( i = 1; i < points - LOOK_AHEAD; i++ )
      /* only work with data points in the upper half,
	 this helps narrow the range of the search */
      if( data[i] > lowerBound ) {	  
	/* consider some portion of the total change to be 
	   big enough for consideration */
	double diff = 0, variance = (max - min) * margin;	  
	int j;
	
	/* look ahead for a plateau - minimal change */
	for( j = 1; j <= LOOK_AHEAD; j++)
	  diff += fabs( data[i+j] - data[i] );
	diff /= LOOK_AHEAD;
	
	/* if there's a jump on the left of the plateau (twice as big as the
	   plateau variance), and the plateau variance is small enough, we 
	   have a candidate */
	if( (data[i] - data[i-1]) > 2 * variance && diff < variance  )
	  votes[i]++;
      }
  return( votes );
}

unsigned int *detectPlateau2( double *data, unsigned int points ) {

  double min, max, lowerBound;
  int i, *votes;
  
  /* create array to hold votes for each candidate point */
  votes = (int *)calloc( points, sizeof( int ) ); 

  /* get min and max to determine the middle of the range */
  max = getMax( data, points );
  min = getMin( data, points );
  /* we'll use this as a lower bound for our search,
     the plateau should be at the "max" - definitly above 
     80% mark */
  lowerBound = max-(max-min)*0.2;
    
  /* check for a plateau with a range of margins,
     voting on each candidate point that fits within that margin */
  for( i = 1; i < points - 1; i++ ){
    /* only work with data points in the upper half,
       this helps narrow the range of the search */
    if( data[i] > lowerBound &&
	data[i] - data[i-1] > 0 &&
	(data[i+1]-data[i])*2 < data[i] - data[i-1] ){
      votes[i]++;
      return(votes);
    }
  }

  return( votes );
}


/* mask representations */
struct {
  char *string;
  unsigned long value;
} maskList[] = { { "32M",  M_32M }, 
		 { "16M",  M_16M },
		 { "8M",   M_8M },
		 { "4M",   M_4M },
		 { "2M",   M_2M },
		 { "1M",   M_1M },
		 { "512K", M_512K },
		 { "256K", M_256K},
		 { "128K", M_128K },
		 { "64K",  M_64K },
		 { "32K",  M_32K },
		 { "16K",  M_16K },
		 { "8K",   M_8K },
		 { "4K",   M_4K },
		 { "2K",   M_2K },
		 { "1K",   M_1K },
		 { "512",  M_512 },
		 { "256",  M_256 } };


/*
  Return the mask associated with the string value.

  mask - string representation of the mask
  return - mask value or zero if not found
*/
unsigned long getMask( char * mask ) {

  int m;

  /* find correct mask string and return the value */
  for( m = 0; m < NUM_MASKS; m++ )
    if( strcmp( mask, maskList[m].string ) == 0 )
      return( maskList[m].value );

  /* if we didn't find it, return zero */
  return( 0 );
}


/*
  Return the size associated with the mask string value.

  mask - string representation of the mask
  return - mask value or zero if not found
*/
unsigned long getMaskSize( char *mask ) {

  unsigned long value = getMask( mask );

  /* check if mask was found */
  if( value )
    /* convert to size */
    return( M_SIZE( value ) );
  else
    return( 0 );
}