#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/* Definicoes de "combine" para calcular soma de inteiros */

#define IDENT 0
#define OPER  +
#define OPER_NAME "Sum"

#define DATA_NAME "Integer"
typedef int data_t;


/* $begin adt */
/* Criar um "abstract data type" para vector */
typedef struct {
    int len;
    data_t *data;
} vec_rec, *vec_ptr;
/* $end adt */

/* Declaracoes das funcoes necessarias */


/* Criar vector de comprimento "len" */
vec_ptr new_vec(int len)
{
    /* allocate header structure */
    vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec));
    if (!result)
        return NULL;  /* Couldn't allocate storage */
    result->len = len;
    /* Allocate array */
    if (len > 0) {
        data_t *data = (data_t *)calloc(len, sizeof(data_t));
		if (!data) {
		    free((void *) result);
 		    return NULL; /* Couldn't allocate storage */
		}
		result->data = data;
    }
    else
		result->data = NULL;
    return result;
}

/* $begin get_vec_start */
data_t *get_vec_start(vec_ptr v)
{
    return v->data;
}
/* $end get_vec_start */

/*
 * Copiar um elemento do vector para "dest" e
 * devolver 0 (indice fora de limites) ou 1 (sucesso)
 */
int get_vec_element(vec_ptr v, int index, data_t *dest)
{
    if (index < 0 || index >= v->len)
		return 0;
    *dest = v->data[index];
    return 1;
}

/* Calcular o comprimento do vector */
int vec_length(vec_ptr v)
{
    return v->len;
}

/*
 * Atribuir um valor a um elemento e
 * devolver 0 (indice fora de limites) ou 1 (sucesso)
 */
int set_vec_element(vec_ptr v, int index, data_t val)
{
    if (index < 0 || index >= v->len)
	return 0;
    v->data[index] = val;
	return 1;
}


/* Código para inicializar o array
 * garantindo que não é eliminado pela optimização */
volatile data_t sink; 
vec_ptr vector;

void setup(int len)
{
    int i;
    vector = new_vec(len);
    /* Inicializa array  */
    for (i = 0; i < len; i++) 
	set_vec_element(vector, i, 32);
    sink = (data_t) 0;
}


/* $begin clear_cache */
/* Number of bytes in the largest cache to be cleared */ 
#define CBYTES (1<<22)   
#define CINTS (CBYTES/sizeof(int)) 

/* A large array to bring into cache */ 
static int dummy[CINTS]; 
volatile int sink2; 
 
/* Evict the existing blocks from the data caches */
void clear_cache() 
{
    int i; 
    int sum = 0; 

    for (i = 0; i < CINTS; i++) 
	dummy[i] = 3; 
    for (i = 0; i < CINTS; i++) 
	sum += dummy[i]; 
    sink2 = sum; 
}
/* $end clear_cache */


/* 
 * Rotinas para usar o cycle counter 
 */


/* Registar o valor actual do cycle counter. */
/* Colocar em *hi e *lo os bits mais e menos significativos do cycle counter.  
 * Requer codigo assembly para usar a instrucao "rdtsc". */
void access_counter(unsigned *hi, unsigned *lo)
{
    asm("rdtsc; movl %%edx,%0; movl %%eax,%1"   /* Ler o cycle counter */
	: "=r" (*hi), "=r" (*lo)                /* e mover resultados para */
	: /* No input */                        /* os dois outputs */
	: "%edx", "%eax");
}

/* Initializar as variaveis do cycle counter */
static unsigned cyc_hi = 0;
static unsigned cyc_lo = 0;
	
void start_counter()
{
	access_counter(&cyc_hi, &cyc_lo);
}

/* Devolver o numero de ciclos desde a ultima chamada a start_counter. */
double get_counter()
{
    unsigned ncyc_hi, ncyc_lo;
    unsigned hi, lo, borrow;
    double result;

    /* Obter o valor do cycle counter */
    access_counter(&ncyc_hi, &ncyc_lo);

    /* Efectuar subtraccao de precisao dupla */
    lo = ncyc_lo - cyc_lo;
    borrow = lo > ncyc_lo;
    hi = ncyc_hi - cyc_hi - borrow;
    result = (double) hi * (1 << 30) * 4 + lo;
    if (result < 0) {
	fprintf(stderr, "Erro: contador devolve valor negativo: %.0f\n", result);
    }
    return result;
}


/*
 * Código para o "combine1" 
 */

void combine1(vec_ptr v, data_t *dest)
{
    int i;
    *dest = IDENT;
    for (i = 0; i < vec_length(v); i++) {
		data_t val;
		get_vec_element(v, i, &val);
		*dest = *dest OPER val;
    }
}


/*
 * Código para o "combine11" (loop mais eficiente)  
 */

void combine11(vec_ptr v, data_t *dest)
{
    int i;
    int length = vec_length(v);

    *dest = IDENT;
    for (i = 0; i < length; i++) {
		data_t val;
		get_vec_element(v, i, &val);
		*dest = *dest OPER val;
    }
}


/*
 * Código para o "combine12" (redução nº de calls) 
 */

void combine12(vec_ptr v, data_t *dest)
{
    int i;
    int length = vec_length(v);
    data_t *data = get_vec_start(v);

    *dest = IDENT;
    for (i = 0; i < length; i++) {
		*dest = *dest OPER data[i];
    }
}


/*
 * Código para o "combine13" (redução acessos à mem)
 */

void combine13(vec_ptr v, data_t *dest)
{
    int i;
    int length = vec_length(v);
    data_t *data = get_vec_start(v);
    data_t x = IDENT;

    *dest = IDENT;
    for (i = 0; i < length; i++) {
		x = x OPER data[i];
    }
    *dest = x;
}


/*
 * Código para o "combine14" (acesso por apontadores)
 */

void combine14(vec_ptr v, data_t *dest)
{
    int length = vec_length(v);
    data_t *data = get_vec_start(v);
    data_t *dend = data+length;
    data_t x = IDENT;

    for (; data < dend; data++) {
		x = x OPER *data;
    }
    *dest = x;
}


/*
 * Código para o "combine15" (loop unroll 2x)
 */

void combine15(vec_ptr v, data_t *dest)
{
    int length = vec_length(v);
    int limit = length-1;
    data_t *data = get_vec_start(v);
    data_t x = IDENT;

    int i;

    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
		x = x OPER data[i] OPER data[i+1];
    }

	/* Finish any remaining elements */
    for (; i < length; i++) {
		x = x OPER data[i];
    }
    *dest = x;
}


/*
 * Código para o "combine16" (loop unroll 2x, acesso apont.)
 */

void combine16(vec_ptr v, data_t *dest)
{
    int length = vec_length(v);
    data_t *data = get_vec_start(v);
    int over = length%2;
    data_t *dend = data+length-over;
    data_t x = IDENT;

    while (data < dend) {
		x = x OPER data[0];
		x = x OPER data[1];
		data += 2;
    }
    dend += over;
    while (data < dend) {
		x = x OPER *data;
		data ++;
    }
    *dest = x;
}


/*
 * Código para o "combine17" (loop unroll 2x, com paralel 2x)
 */

void combine17(vec_ptr v, data_t *dest)
{
    int length = vec_length(v);
    int limit = length-1;
    data_t *data = get_vec_start(v);
    data_t x0 = IDENT;
    data_t x1 = IDENT;
    int i;

    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
		x0 = x0 OPER data[i]; 
		x1 = x1 OPER data[i+1];
    }

    /* Finish any remaining elements */
    for (; i < length; i++) {
		x0 = x0 OPER data[i];
    }
    *dest = x0 OPER x1;
}




/* Programa para medir o CPE (simplificado) das funções "combine"
 * e produzir apenas um resultado - soma inteiros - para ambos os casos:
 * com a cache a frio e a quente */

int main() 
{
	int i;
	int dimensao = 1024;
	// vec_ptr vector = new_vec(dimensao); ver em setup
	data_t resultado;
	
	double cpe;

	/* Preparar ficheiro para escrita de resultados */
	FILE *f;
	f= fopen("cpe_s_i", "w");
    fprintf(f, "Valores de CPE para versões de combine\n\n");

	/* Inicializa o array, colocando em cada elemento o valor 32 */
	setup(dimensao);

/* Execução de "combine1" com a cache a frio */
    fprintf(f, "Combine1\n");

	for (i = 0; i < 5; i++) {
		clear_cache();

		start_counter(); 
		combine1(vector, &resultado); 
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a frio (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

	/* Execução de "combine1" com a cache já quente */

	for (i = 0; i < 5; i++) {
		start_counter(); 
		combine1(vector, &resultado);
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a quente (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

/* Execução de "combine11" com a cache a frio */
    fprintf(f, "Combine11\n");

	for (i = 0; i < 5; i++) {
		clear_cache();

		start_counter(); 
		combine11(vector, &resultado); 
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a frio (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

	/* Execução de "combine11" com a cache já quente */

	for (i = 0; i < 5; i++) {
		start_counter(); 
		combine11(vector, &resultado);
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a quente (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

/* Execução de "combine12" com a cache a frio */
    fprintf(f, "Combine12\n");

    for (i = 0; i < 5; i++) {
		clear_cache();

		start_counter(); 
		combine11(vector, &resultado); 
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a frio (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

	/* Execução de "combine12" com a cache já quente */

	for (i = 0; i < 5; i++) {
		start_counter(); 
		combine12(vector, &resultado);
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a quente (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

/* Execução de "combine13" com a cache a frio */
    fprintf(f, "Combine13\n");

    for (i = 0; i < 5; i++) {
		clear_cache();
	
		start_counter(); 
		combine13(vector, &resultado); 
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a frio (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

	/* Execução de "combine13" com a cache já quente */

	for (i = 0; i < 5; i++) {
		start_counter(); 
		combine13(vector, &resultado);
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a quente (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

/* Execução de "combine14" com a cache a frio */
    fprintf(f, "Combine14\n");

    for (i = 0; i < 5; i++) {
		clear_cache();

		start_counter(); 
		combine14(vector, &resultado); 
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a frio (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

	/* Execução de "combine14" com a cache já quente */

	for (i = 0; i < 5; i++) {
		start_counter(); 
		combine14(vector, &resultado);
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a quente (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

/* Execução de "combine15" com a cache a frio */
    fprintf(f, "Combine15\n");

    for (i = 0; i < 5; i++) {
		clear_cache();

		start_counter(); 
		combine15(vector, &resultado); 
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a frio (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

	/* Execução de "combine15" com a cache já quente */

	for (i = 0; i < 5; i++) {
		start_counter(); 
		combine15(vector, &resultado);
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a quente (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

/* Execução de "combine16" com a cache a frio */
    fprintf(f, "Combine16\n");

    for (i = 0; i < 5; i++) {
		clear_cache();
		
		start_counter(); 
		combine16(vector, &resultado); 
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a frio (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

	/* Execução de "combine16" com a cache já quente */

	for (i = 0; i < 5; i++) {
		start_counter(); 
		combine16(vector, &resultado);
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a quente (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

/* Execução de "combine17" com a cache a frio */
    fprintf(f, "Combine17\n");

    for (i = 0; i < 5; i++) {
		clear_cache();

		start_counter(); 
		combine17(vector, &resultado); 
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a frio (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

	/* Execução de "combine17" com a cache já quente */

	for (i = 0; i < 5; i++) {
		start_counter(); 
		combine17(vector, &resultado);
		cpe = get_counter(); 
		cpe = cpe / dimensao;
		fprintf(f, "CPE a quente (%s, %s, %d elem): %.2f\n", OPER_NAME, DATA_NAME, dimensao, cpe);
	}

	printf("Ficheiro cpe_s_i actualizado");
}