fdct.c

fast discrete cosin transform

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

void forwardDCT(int I[8][8],int Trow[8][8],int Tcol[8][8],int O[8][8]);
void dct(int *a, int *S);

int main()
{
	int u,v;
	int I[8][8] = 
{48, 123, 89, 175, 234, 56, 78, 190,
1, 5, 67, 2, 98, 3, 125, 7,
67, 89, 155, 43, 27, 89, 0, 129,
57, 23, 51, 93, 187, 67, 189, 1,
178, 45, 39, 52, 12, 78, 49, 90,
48, 56, 120, 87, 65, 34, 167, 203,
23, 32, 44, 45, 47, 23, 90, 89,
54, 67, 90, 128, 235, 50, 190, 210};
/*
{
98, 92, 95, 80, 75, 82 ,68, 50,
97, 91, 94, 79, 74, 81, 67, 49,
95, 89, 92, 77, 72, 79, 65, 47,
93, 87, 90, 75, 70, 77, 63, 45,
91, 85, 88, 73, 68, 75, 61, 43,
89, 83, 86, 71, 66, 73, 59, 41,
87, 81, 84, 69, 64, 71, 57, 39,
85, 79, 82, 67, 62, 69, 55, 37 }; */
/*
{
154, 123, 123, 123, 123, 123, 123, 136,
192, 180, 136, 154, 154, 154, 136, 110,
254, 198, 154, 154, 180, 154, 123, 123,
239, 180, 136, 180, 180, 166, 123, 123,
180, 154, 136, 167, 166, 149, 136, 136, 
128, 136, 123, 136, 154, 180, 198, 154, 
123, 105, 110, 149, 136, 136, 180, 166,
110, 136, 123, 123, 123, 136, 154, 136}; */
/*
{
12, 10,  2,  8,  4, 13, 3,  3,
 1,  3,  5,  6, 11,  2, 0,  5,
 2,  7,  6,  5,  4,  3, 1,  9,
14,  0,  8,  3, 14,  9, 0,  0,
 0,  4, 12,  8,  5,  0, 3,  1,
 6,  7,  1,  2,  3,  4, 5,  6,
 8,  7,  6,  5,  4,  3, 2,  1,
 1,  9,  2,  1,  9,  7, 4, 13
}; */

	int Trow[8][8];
	int Tcol[8][8];
	int    O[8][8];

	printf("\n Input Matrix \n");
	for (u=0; u<8; u++)
	{
		for (v=0; v<8; v++)
			printf("%d\t",I[u][v]);
		printf("\n");
	}
	
	forwardDCT(I,Trow,Tcol,O);

	printf("\n Transpose matrix (before transposing) \n");
	for (u=0; u<8; u++)
	{
		for (v=0; v<8; v++)
			printf("%d\t",Trow[u][v]);
		printf("\n");
	}
	
	printf("\n Transpose matrix (after transposing) \n");
	for (u=0; u<8; u++)
	{
		for (v=0; v<8; v++)
			printf("%d\t",Tcol[u][v]);
		printf("\n");
	}
	
	printf("\n FDCT \n");
	for (u=0; u<8; u++)
	{
		for (v=0; v<8; v++)
			printf("%d\t",O[u][v]);
		printf("\n");
	}
	
	return 0;
}

/* FDCT */
/*--------------------------------------------------------------*/
void forwardDCT(int I[8][8],int Trow[8][8],int Tcol[8][8],int O[8][8])
{
	int u,v;
	
	/* first : do DCT on row */
	for (v=0; v<8; v++)
		dct(I[v],Trow[v]);

	/* Transpose the matrix */
	for (v=0; v<8; v++)
		for (u=0; u<8; u++)
			Tcol[v][u] = Trow[u][v];
	
	/* second : do DCT on column */
	for (v=0; v<8; v++)
		dct(Tcol[v],O[v]);
}

/* 1D-DCT */
/*--------------------------------------------------------------*/
/* the function "dct" generates the DCT coeffcients
for the 8x8 pixel block provied in "a" */

void dct(int *a, int *S)
{
	int b[8];
	int c[8];
	int d[9];
	int e[9];
	int f[8];
	
	float m1,m2,m3,m4,m5;
	
	m1 = 0.7109375;
	m3 = 0.5390625;
	m4 = 1.3046875;
	m2 = 0.3828125;	
	
/* Step 1 */
b[0] = a[0] + a[7];
b[1] = a[1] + a[6];
b[2] = a[2] - a[4];
b[3] = a[1] - a[6];
b[4] = a[2] + a[5];
b[5] = a[3] + a[4];
b[6] = a[2] - a[5];
b[7] = a[0] - a[7];

/* Step 2 */
c[0] = b[0] + b[5];
c[1] = b[1] - b[4];
c[2] = b[2] + b[6];
c[3] = b[1] + b[4];
c[4] = b[0] - b[5];
c[5] = b[3] + b[7];
c[6] = b[3] + b[6];
c[7] = b[7];

/* Step 3 */
d[0] = c[0] + c[3];
d[1] = c[0] - c[3];
d[2] = c[2]; 
d[3] = c[1] + c[4];
d[4] = c[2] - c[5];
d[5] = c[4];
d[6] = c[5];
d[7] = c[6];
d[8] = c[7];

/* Step 4 */
e[0] = d[0];
e[1] = d[1];
e[2] = (int)(float)d[2]*m3;
e[3] = (int)(float)d[7]*m1;
e[4] = (int)(float)d[6]*m4;
e[5] = d[5];
e[6] = (int)(float)d[3]*m1;
e[7] = (int)(float)d[4]*m2; 
e[8] = d[8];

/* Step 5 */
f[0] = e[0];
f[1] = e[1];
f[2] = e[5] + e[6];
f[3] = e[5] - e[6];
f[4] = e[3] + e[8];
f[5] = e[8] - e[3];
f[6] = e[2] + e[7];
f[7] = e[4] + e[7];

/* Step 6 */
S[0] = f[0];
S[1] = f[4] + f[7];
S[2] = f[2];
S[3] = f[5] - f[6];
S[4] = f[1];
S[5] = f[5] + f[6];
S[6] = f[3];
S[7] = f[4] - f[7];

}