Add 2d functions

2 files changed, 72 insertions, 1 deletions

diff --git a/fft.c b/fft.c
index 1897d7e..9a9682f 100644
--- a/fft.c
+++ b/fft.c
@@ -82,10 +82,74 @@ shift (complex_t *buffer, int n)
 {
     int i;
 
-    for (i = 0; i < n / 2; ++i)
+    for (i = 0; i < n/2; ++i)
     {
 	complex_t tmp = buffer[i];
 	buffer[i] = buffer[i + n/2];
 	buffer[i + n/2] = tmp;
     }
 }
+
+
+void
+fft_2d (complex_t *buffer, int n)
+{
+    int i;
+
+    /* Transform all the rows */
+    for (i = 0; i < n; ++i)
+    {
+	complex_t *b = buffer + i * n;
+
+	fft (b, n);
+    }
+
+    /* Then the columns */
+    for (i = 0; i < n; ++i)
+    {
+	int j;
+	complex_t *tmp = malloc (n * sizeof (complex_t));
+
+	for (j = 0; j < n; ++j)
+	    tmp[j] = buffer[j * n + i];
+
+	fft (tmp, n);
+
+	for (j = 0; j < n; ++j)
+	    buffer[j * n + i] = tmp[j];
+
+	free (tmp);
+    }
+}
+
+void
+shift_2d (complex_t *buffer, int n)
+{
+    int i, j;
+    
+    /* Swap quadrant 0 with quadrant 3 */
+    for (i = 0; i < n/2; ++i)
+    {
+	for (j = 0; j < n/2; ++j)
+	{
+	    complex_t tmp;
+	    
+	    tmp = buffer[i * n + j];
+	    buffer[i * n + j] = buffer[((n/2) + i) * n + (j + n/2)];
+	    buffer[((n/2) + i) * n + (j + n/2)] = tmp;
+	}
+    }
+
+    /* Swap quadrant 1 with quadrant 2 */
+    for (i = 0; i < n/2; ++i)
+    {
+	for (j = 0; j < n/2; ++j)
+	{
+	    complex_t tmp;
+
+	    tmp = buffer[i * n + j + n/2];
+	    buffer[i * n + j + n/2] = buffer[(i + n/2) * n + j];
+	    buffer[(i + n/2) * n + j] = tmp;
+	}
+    }
+}
diff --git a/fft.h b/fft.h
index 35a756d..f98e059 100644
--- a/fft.h
+++ b/fft.h
@@ -68,6 +68,13 @@ fft (complex_t *buffer, int n);
 void
 ifft (complex_t *buffer, int n);
 
+/* Fourier transform an n x n array */
+void
+fft_2d (complex_t *buffer, int n);
+
 /* Shifts the zero component to the center of the array */
 void
 shift (complex_t *buffer, int n);
+
+void
+shift_2d (complex_t *buffer, int n);