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


typedef struct{
    double a, b;
} complex;

complex criandowr(int N ,int i);
void ordenandoxn(int N, int nbits,complex *xn);
int obtendoN();
float *lendoarquivo(int N);
void fft(int nbits,int N,complex *xn,complex *wn);
complex soma(complex z1, complex z2);
complex subtr(complex z1, complex z2);
complex mult(complex z1, complex z2);
complex div(complex z1, complex z2);
double modulo(complex z);
double angle(complex z);
void mostra(complex z);
complex le(void);




double pi = M_PI;



void main (){
    time_t inicio, fim,result;
    int i,j;
    int n,N;
    double nbits;
    N =  obtendoN();

    complex*  wr = (complex*)malloc(N * sizeof(complex));
    complex*  Xn = (complex*)malloc(N * sizeof(complex));
    complex *xn = lendoarquivo(N);

    printf("Numero de Amostras %i",N);

    //resolvendo a DFT

    for(i=0;i<N;i++){
        Xn[i].a = 0;
        Xn[i].b = 0;
    }

 /*
    inicio= time(NULL);
    for(i=0;i<=(N-1);i++){
        for (j=0;j<=(N-1);j++){
           wr[i].a =  cos((2*pi*i*j)/N);
           wr[i].b =  -sin((2*pi*i*j)/N);
           Xn[i].a =  Xn[i].a + (xn[j].a * wr[i].a);
           Xn[i].b =  Xn[i].b + (xn[j].a * wr[i].b );
        }
    }


    fim= time(NULL);
    printf("\n O tempo de Execucao(DFT) foi : %.2f",difftime(fim,inicio));

*/


    //Calculando o numerod de bits para a FFT
    nbits = (log10(N)/log10(2));
    nbits = (int) nbits;


    //Criando os valores Wn e colocando no vetor para FFT
    for(i =0 ; i<=(N-1); i++){
        wr[i] = criandowr(N,i);
        //printf("\n Valor Wn[%i]= %lf + j %lf",i,wr[i].a,wr[i].b);
    }



    //Chamada da funcao que ordena os Xn
    ordenandoxn(nbits,N,xn);



    fft(nbits,N,xn,wr);




}

/* Nao precisava criar um vetor da estrutura complex, voce so precisa retornar uma dela... */
complex criandowr(int N ,int i){

    complex wr;
    wr.a =  cos((2*pi*i)/N);
    wr.b =  -sin((2*pi*i)/N);

    return wr ;

}
void ordenandoxn(int nbits,int N,complex *xn){
    int i,j;


   // int array[N][nbits];

    //N= 13;
    int **array ;
    array=(int**) malloc(N*nbits*sizeof(int));
    for(i=0;i < N;i++){
        array[i]=(int*)malloc(nbits*sizeof(int));
    }



    for(j=0;j<(N);j++){

        for(i=0;i<(nbits);i++){
            printf("\n DEBUG %i %i",j,i);
            array[j][i]=0;
        }
    }



    // conveterndo de decimal para binario(ja esta invertendo)
        for(i=0;i<=(N-1);i++){
            int a=0;
            int  aux = i;
            while(aux>=2 || aux==1){
                array[i][a] = aux % 2;
                a++;
                if(aux==2){
                    array[i][a] = aux/2;
                    }
                aux = aux/2;
            }
        }

        for(i=0;i<N;i++){
            for(j=0;j<(nbits);j++){
             //printf("%i", array[i][j]);
            }
        }

        //conveterndo de binairo pra decimal
        int a ;
        int  arrayaux[N];

         for (i=0; i<N ; i++){
            arrayaux[i]=0;

         }

        for(i=0;i<N;i++){
            int expoente = nbits  ;
            for(j=0;j<nbits;j++){
                expoente = expoente - 1 ;
                a = (array[i][j] * pow((2),(expoente)));
                arrayaux[i]= a + arrayaux[i];

            }

         //   printf("\n Valor de Arrayaux[%i] = %i",i,arrayaux[i]);
        }


        int Aux[N];
        for(i=0;i<N;i++){
            Aux[i]= arrayaux[i];

           // printf("\n Valor de AUX %i",Aux[i]);

        }


        float arrayvd[N];

        for(i=0;i<N;i++){
            arrayvd[i] = xn[i].a;
        }

        for(i=0;i<N;i++){
           xn[Aux[i]].a= arrayvd[i];
        }


        for(i=0;i<N;i++){
           // printf("\n Valor de X[%i]= %lf",i,xn[i].a);
        }

}
void fft(int nbits,int N,complex *xn,complex *wr){

    time_t inicio , fim;
    //int caixas, pares,fatores;

     //para tamanho do passo dos fatores
    complex *oldxn = (complex*)malloc(N * sizeof(complex));
    int caixas = malloc(N * sizeof(int));
    int pares = malloc(N * sizeof(int));
    int fatores = malloc(N * sizeof(int));
    int i = malloc(N * sizeof(int));
    int j = malloc(N * sizeof(int));
    int k = malloc(N * sizeof(int));
    int incr = malloc(N * sizeof(int));
    int incrxn = malloc(N * sizeof(int));
    int p = malloc(N * sizeof(int));

    caixas = ((N)/2);
    pares = ((N)/(N));
    fatores = ((N)/2);
    incr=0;
    incrxn=0;
    p;

    printf("caixas %i pares %i fatores %i",caixas,pares,fatores);

    inicio= time(NULL);
    for(i = 0; i < nbits; i++) {
      //  printf("\nEstágio Número: %i", i);
        for (j = 0; j < caixas; j++){
            //printf("\nCaixa Número: %i", j);
            incr = 0;
            for (k = 0; k < pares; k++){
              //  printf("\nPares: %i", k);
                if (i == 0)
                {
                    incr = 0;
                }
                if (k != 0)
                {
                    incr = incr + caixas;
                }

                    oldxn[incrxn] = soma(xn[incrxn],(mult(wr[incr],xn[incrxn+pares])));
                    xn[incrxn+pares] = soma(xn[incrxn],(mult(wr[incr+fatores],xn[incrxn+pares])));
                    xn[incrxn] = oldxn[incrxn];
                incrxn = incrxn + 1;
                p = incrxn + pares;
            }
            incrxn = p;
            //printf("\n");
        }
        caixas = caixas/2;
        pares = pares*2;
        incrxn =0;
       // printf("\n\n");
    }

    fim= time(NULL);
    printf("\n O tempo de Execucao(FFT) foi : %.2f",difftime(fim,inicio));


        for(i=0;i<20;i++){
             printf("\n X[%i] = %lf   j %lf",i, xn[i].a, xn[i].b);

        }
}
complex soma(complex z1, complex z2){

    complex resultado ;
    resultado.a = (z1.a + z2.a);
    resultado.b = (z1.b + z2.b);
    return resultado;
}
complex subtr(complex z1, complex z2){

    complex resultado ;

    resultado.a = (z1.a - z2.a);
    resultado.b = (z1.b - z2.b);

    return resultado;
}
complex mult(complex z1, complex z2){

    complex resultado ;

    resultado.a = ((z1.a * z2.a)-(z1.b * z2.b));
    resultado.b = ((z1.a * z2.b)+(z1.b * z2.a));

    return resultado;
}
complex div(complex z1, complex z2){

    complex resultado ;

    resultado.a = ((z1.a * z2.a)+(z1.b * z2.b))/((z2.a * z2.a)+(z2.b * z2.b));
    resultado.b = ((z2.a * z1.b)-(z1.a * z2.b))/((z2.a * z2.a)+(z2.b * z2.b));

    return resultado;
}
int obtendoN(){

    int N;
    char url[] = "voz.txt";
    FILE *arq;
    arq = fopen(url, "r");

    if (arq == NULL)
        printf("Erro! Não foi possivel abrir o arquivo!\n");
    else {
        char info[7], aux[50];
        fgets(info, sizeof (info), arq);
        N = (int) atoi(info);
    }
    fclose(arq);

    return N;

}
float *lendoarquivo(int N){


    FILE *fp = fopen("voz.txt", "r");
    double current_val;
    int n;

    //Le quantos valores existem
    fscanf(fp, "%i", &n);

    //Aloca o espaco necessario para guardar n floats
    complex* xn = (complex*)malloc(n * sizeof(complex));

    int i;
    for(i = 0; i < n; i++) {
        fscanf(fp, "%lf", &current_val);
        xn[i].a = current_val;
        //printf("\n x[%i]=%lf",i,xn[i]);
    }

    return xn;

}