\r
#include "FFT.h"\r
\r
- word in_a_re, in_a_im, in_b_re, in_b_im, in_W_re, in_W_im;\r
- //out_a_re, out_a_im, out_b_re, out_b_im;\r
- //mem input_a_re, input_a_im, input_b_re, input_b_im, output_a_re, output_a_im, output_b_re, output_b_im, twiddle_re, twiddle_im; \r
-\r
-void init()\r
-{\r
-\r
-}\r
-\r
-\r
-\r
-/*void update_gpi() {\r
- set_gpi(0, 1);\r
-}*/\r
-\r
+/**\r
+ * Executes a single butterfly on ALU 0-3. The inputs are the words taken from\r
+ * in, which will be read on various inputs of ALU 0-3. Outputs will be\r
+ * returned and will we be available on the output ports of ALU 0 and 2.\r
+ */\r
INLINE struct bf_out butterfly(struct bf_in in) {\r
struct bf_out out;\r
/* ALU 0 & 1 */\r
return out;\r
}\r
\r
+/**\r
+ * Writes the output of a butterfly given in res to the correct memory\r
+ * locations.\r
+ * @param second_half Are we in the second half of the stage?\r
+ */\r
INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_half) {\r
add_offset(m.output_a_re, 2);\r
add_offset(m.output_a_im, 2);\r
*/\r
INLINE struct bf_in read_input_regular(struct mems m, bool cycle_odd, bool stage_odd) {\r
struct bf_in in;\r
- /* TODO: Select left or right memories */\r
+ /* Swap memory a and b during the odd cycles */\r
if (cycle_odd) {\r
in.a_re = read_mem(m.input_a_re);\r
in.a_im = read_mem(m.input_a_im);\r
in.W_re = read_mem(m.twiddle_re);\r
in.W_im = read_mem(m.twiddle_im);\r
\r
-\r
+ \r
+ /* Read inputs sequentially */\r
add_offset(m.input_a_re, 1);\r
add_offset(m.input_a_im, 1);\r
add_offset(m.input_b_re, 1);\r
}\r
\r
/**\r
- * Initializes the addresses for the various memories.\r
+ * Initializes the addresses for writing the outputs.\r
* @param stage_odd True if this is an odd stage.\r
- *@param second_half True if we are initing halfway a stage.\r
+ * @param second_half True if we are initing halfway a stage.\r
*/ \r
INLINE void init_input_addresses_regular(struct mems m, bool stage_odd) {\r
- /* TODO: Select left or right memories */\r
+ /* We simply start reading at address 0 incrementally */\r
set_base(m.input_a_im, 0);\r
set_base(m.input_b_re, 0);\r
set_base(m.input_b_im, 0);\r
set_offset(m.twiddle_re, 0);\r
set_offset(m.twiddle_im, 0);\r
}\r
- \r
- \r
+\r
+/**\r
+ * Initializes the addresses for reading the inputs. This function must be\r
+ * called twice per stage, since halfway the stage the addressing changes.\r
+ */\r
INLINE void init_output_addresses_regular(struct mems m, bool stage_odd, bool second_half) {\r
/* \r
* For the second half of the stage, the starting addresses are \r
}\r
\r
INLINE void do_half_regular_stage(struct mems m, bool stage_odd, bool second_half){\r
+ /*\r
+ * We are doing two cycles in each iteration, so we can alternate the\r
+ * cycle_odd argument (which only works with constants, I don't expect\r
+ * the optimizer to do this loop unrolling for us). Since we need to\r
+ * write outputs before reading, but don't have any outputs to write\r
+ * in the first cycle, we must put the first cycle outside of the\r
+ * loop. Since the loop does two cycles at a time, this means there\r
+ * must be two cycles outside of the loop, so we put one at the end as\r
+ * well. Additionally, we also need to write the outputs of the last\r
+ * cycle in an extra cycle at the end. We probably can't combine this\r
+ * last cycle with the first cycle of the next stage, because they\r
+ * need the same memories (input becomes output and v.v.).\r
+ */\r
+\r
+ /* Initialize output addresses, this must be done twice per stage */\r
+ init_output_addresses_regular(m, stage_odd, second_half);\r
+\r
+ /* First cycle (no previous output to write) */\r
struct bf_in in = read_input_regular(m, EVEN_CYCLE, stage_odd);\r
struct bf_out out = butterfly(in);\r
- \r
+\r
/* Now, do a single stage. That means N_t / 2 cycles. Since we do 2\r
* cycles on every iteration, plus one before and after the loop,\r
* we will loop N_t / 4 - 1 times. */\r
init_loop(LC2, (N_t / 4) - 1);\r
do {\r
- init_output_addresses_regular(m, stage_odd, second_half);\r
+ /* Write outputs of previous cycle */\r
write_output_regular(m, out, second_half);\r
\r
+ /* Odd cycle */\r
in = read_input_regular(m, ODD_CYCLE, second_half);\r
out = butterfly(in);\r
next_cycle();\r
+\r
+ /* Write outputs of previous cycle */\r
write_output_regular(m, out, second_half);\r
\r
+ /* Even cycle */\r
in = read_input_regular(m, EVEN_CYCLE, second_half);\r
out = butterfly(in);\r
} while (loop_next(LC2));\r
\r
+ /* Write outputs of previous cycle */\r
write_output_regular(m, out, second_half);\r
+\r
+ /* Last cycle */\r
in = read_input_regular(m, ODD_CYCLE, second_half);\r
out = butterfly(in);\r
- \r
next_cycle();\r
+\r
+ /* Write outputs of last cycle */\r
write_output_regular(m, out, second_half);\r
+ \r
+ /* Force the next cycle, because the next stage must read from\r
+ * the memory we just wrote to */\r
+ next_cycle();\r
}\r
\r
INLINE struct mems init_mem_mapping(bool stage_odd){\r
return res;\r
}\r
void run() {\r
-#ifdef __MONTIUMCC__\r
- /* main.cpp will call init before pre_run(), so only need to call init for MontiumCC */\r
- init();\r
-#endif\r
do { freeze(); } while (gpi(0) == 0);\r
struct mems m;\r
\r
projects / matthijs / projects / montium-fft.git / blobdiff