#define _USE_MATH_DEFINES

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

#define LENGTH 8 /* 信号長 */

typedef struct {
    double r; /* 実部 */
    double i; /* 虚部 */
} Complex; /* 複素数 */

/* プロトタイプ宣言 */
void initComplexList(Complex*, int);
Complex getComplex(double, double);
Complex addComplex(Complex, Complex);
Complex timeComplex(Complex, Complex);
Complex divComplexByReal(Complex, double);
Complex powComplex(Complex, int);
void printComplex(Complex);

void genTwiddleTable(Complex*, int);
Complex calcTwiddlePower(Complex*, int, int);
void calcDFT(Complex*, Complex*, int);
void calcIDFT(Complex*, Complex*, int);

void printTable(char*, char, Complex*, int);

int main(void) {
    /* 信号長 */
    int N = LENGTH;
    /* 信号配列 */
    Complex x[LENGTH] = {getComplex(0, 0), getComplex(1, 0), getComplex(2, 0), getComplex(3, 0), getComplex(4, 0), getComplex(5, 0), getComplex(6, 0), getComplex(7, 0)};
    /* N点DFT係数 */
    Complex c[LENGTH];
    /* 復元された信号配列 */
    Complex idft_x[LENGTH];

    initComplexList(c, N);
    initComplexList(idft_x, N);

    printTable("DATA", 'n', x, N);

    calcDFT(x, c, N);

    printTable("DFT", 'k', c, N);

    calcIDFT(c, idft_x, N);

    printTable("IDFT", 'n', idft_x, N);


    return 0;
}

/* 複素数配列を0+j0で初期化 */
void initComplexList(Complex *list, int N) {
    int i;
    for(i = 0; i < N; i++) {
        list[i] = getComplex(0.0, 0.0);
    }
}

/* 第一引数を実部，第二引数を虚部とする複素数を返す */
Complex getComplex(double real, double imaginary) {
    Complex z;
    z.r = real;
    z.i = imaginary;
    return z;
}

/* 第一引数と第二引数の和を返す */
Complex addComplex(Complex a, Complex b) {
    return getComplex(a.r + b.r, a.i + b.i);
}

/* 第一引数と第二引数の積を返す */
Complex timeComplex(Complex a, Complex b) {
    return getComplex(a.r*b.r - a.i*b.i, a.r*b.i+a.i*b.r);
}

/* 第一引数(複素数)を第二引数(実数)で割った値(複素数)を返す */
Complex divComplexByReal(Complex z, double div) {
    return getComplex(z.r / div, z.i / div);
}

/* 第一引数の第二引数乗を返す
 * 第二引数が負の場合は，第一引数の大きさが1のときのみ正しく計算される
 */
Complex powComplex(Complex z, int pow) {
    if(pow == 0) return getComplex(1.0, 0.0);

    int i;
    int p = (pow > 0) ? pow : -pow;
    Complex ret = z;
    for(i = 0; i < p-1; i++) {
        ret = timeComplex(ret, z);
    }

    /* |z|==1のとき，zの-1乗はzの共役複素数 */
    if(pow < 0)
        ret.i = -ret.i;

    return ret;
}

/* 複素数出力 */
void printComplex(Complex z) {
    if(z.i < 0) {
        printf("%f-j%f\n", z.r, -z.i);
    } else {
        printf("%f+j%f\n", z.r, z.i);
    }
}

/* 回転子W_Nの0乗からN-1乗を計算 */
void genTwiddleTable(Complex *W, int N) {
    int i;
    for (i = 0; i < N; i++) {
        W[i] = getComplex(cos(i * 2.0 * M_PI / N), -sin(i * 2.0 * M_PI / N));
    }
}

/* 回転子W_Nのn乗のk乗を計算 */
Complex calcTwiddlePower(Complex *W, int n, int k) {
    return powComplex(W[n], k);
}

/* 離散フーリエ変換 */
void calcDFT(Complex *x, Complex *c, int N) {
    int k, n;
    Complex W[LENGTH];

    genTwiddleTable(W, N);
    printTable("TWIDDLE", 'i', W, N);

    /* 信号長で反復 */
    for(k = 0; k < N; k++) {
        /* シグマループ */
        for(n = 0; n < N; n++) {
            c[k] = addComplex(
                c[k],
                timeComplex(
                    x[n],
                    calcTwiddlePower(
                        W, k, n
                    )
                )
            );
        }
    }
}

/* 離散フーリエ逆変換 */
void calcIDFT(Complex *c, Complex *x, int N) {
    int n, k;
    Complex W[LENGTH];

    genTwiddleTable(W, N);

    /* 信号長で反復 */
    for(n = 0; n < N; n++) {
        /* シグマループ */
        for(k = 0; k < N; k++) {
            x[n] = addComplex(
                x[n],
                timeComplex(
                    c[k],
                    calcTwiddlePower(
                        W, n, -k
                    )
                )
            );
        }
        /* 総和をNで割る */
        x[n] = divComplexByReal(x[n], (double)N);
    }
}

/* 複素数テーブル出力 */
void printTable(char *name, char index, Complex *z, int N) {
    int i;
    printf("----- BEGIN %s TABLE -----\n", name);
    for(i = 0; i < N; i++) {
        printf("%c = %d : ", index, i);
        printComplex(z[i]);
    }
    printf("----- END %s TABLE -----\n", name);
}