X-Git-Url: https://git.stderr.nl/gitweb?a=blobdiff_plain;f=FFT.mc;h=6688275a9f32d7a7341ead36d3859efe18578e57;hb=81823b7486c210898290292ed87142a89c496946;hp=e58d2fa771e0c644297c99d1935d66dd8b1055ba;hpb=e09e88b193ec1b84311b345abb2b9d7943060602;p=matthijs%2Fprojects%2Fmontium-fft.git

diff --git a/FFT.mc b/FFT.mc
index e58d2fa..6688275 100644
--- a/FFT.mc
+++ b/FFT.mc
@@ -6,28 +6,21 @@
 
 #include "FFT.h"
 
-	word in_a_re, in_a_im, in_b_re, in_b_im, in_W_re, in_W_im;
-	//out_a_re, out_a_im, out_b_re, out_b_im;
-	//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; 
-
-void init()
-{
-
-}
-
-
-
-/*void update_gpi() {
-  set_gpi(0, 1);
-}*/
-
+int stage = 1;
+/**
+ * Executes a single butterfly on ALU 0-3. The inputs are the words taken from
+ * in, which will be read on various inputs of ALU 0-3. Outputs will be
+ * returned and will we be available on the output ports of ALU 0 and 2.
+ */
 INLINE struct bf_out butterfly(struct bf_in in) {
 	struct bf_out out;
 	/* ALU 0 & 1 */
 		/* im(W) * im(b) */
 		aluexp Wixbi = west(fmul(rd1(in.W_im), rb1(in.b_im)));
+	
 		/* re(W * b) = re(W) * re(b) - im(W) * im(b) */
 		aluexp Wxbr  = ssub_acc(fmul(rc1(in.W_re), ra1(in.b_re)), Wixbi);
+
 		
 		/* re(out_a) = re(a) + re(W * b) */
 		out.a_re =   p0o0(sadd_bf(rb1(in.a_re), Wxbr));
@@ -48,13 +41,18 @@ INLINE struct bf_out butterfly(struct bf_in in) {
 		return out;
 }
 
+/**
+ * Writes the output of a butterfly given in res to the correct memory
+ * locations.
+ * @param  second_half   Are we in the second half of the stage?
+ */
 INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_half) {
 	add_offset(m.output_a_re, 2);
 	add_offset(m.output_a_im, 2);
 	add_offset(m.output_b_re, 2);
 	add_offset(m.output_b_im, 2);
 	
-	if (second_half) {
+	if (!second_half) {
 		write_mem(m.output_a_re, res.a_re);
 		write_mem(m.output_a_im, res.a_im);
 		write_mem(m.output_b_re, res.b_re);
@@ -80,7 +78,7 @@ INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_h
  */
 INLINE struct bf_in read_input_regular(struct mems m, bool cycle_odd, bool stage_odd) {
 	struct bf_in in;
-	/* TODO: Select left or right memories */
+	 /* Swap memory a and b during the odd cycles */
 	if (cycle_odd) {
 		in.a_re = read_mem(m.input_a_re);
 		in.a_im = read_mem(m.input_a_im);
@@ -95,22 +93,29 @@ INLINE struct bf_in read_input_regular(struct mems m, bool cycle_odd, bool stage
 	in.W_re = read_mem(m.twiddle_re);
 	in.W_im = read_mem(m.twiddle_im);
 	
-
+	
+	/* Read inputs sequentially */
 	add_offset(m.input_a_re, 1);
 	add_offset(m.input_a_im, 1);
 	add_offset(m.input_b_re, 1);
 	add_offset(m.input_b_im, 1);
-	/* TODO: Update twiddle offsets */
+	
+	/* TODO: Is this true? */
+	add_offset(m.twiddle_re, (PARAM_N_t>>stage));
+	add_offset(m.twiddle_im, (PARAM_N_t>>stage));
+	use_mask(m.twiddle_re, (PARAM_N_t/2)-1);
+	use_mask(m.twiddle_im, (PARAM_N_t/2)-1);
+
 	return in;
 }
 
 /**
- *  Initializes the addresses for the various memories.
+ * Initializes the addresses for writing the outputs.
  * @param stage_odd   True if this is an odd stage.
- *@param second_half True if we are initing halfway a stage.
+ * @param second_half True if we are initing halfway a stage.
  */ 
 INLINE void init_input_addresses_regular(struct mems m, bool stage_odd) {
-	/* TODO: Select left or right memories */
+	/* We simply start reading at address 0 incrementally */
 	set_base(m.input_a_im, 0);
 	set_base(m.input_b_re, 0);
 	set_base(m.input_b_im, 0);
@@ -124,8 +129,11 @@ INLINE void init_input_addresses_regular(struct mems m, bool stage_odd) {
 	set_offset(m.twiddle_re, 0);
 	set_offset(m.twiddle_im, 0);
 }
-	
-	
+
+/**
+ * Initializes the addresses for reading the inputs. This function must be
+ * called twice per stage, since halfway the stage the addressing changes.
+ */
 INLINE void init_output_addresses_regular(struct mems m, bool stage_odd, bool second_half) {
 	/* 
 	 * For the second half of the stage, the starting addresses are 
@@ -148,40 +156,70 @@ INLINE void init_output_addresses_regular(struct mems m, bool stage_odd, bool se
 		set_offset(m.output_b_re, 0-2);
 		set_offset(m.output_b_im, 0-2);
 	} else {
-		set_offset(m.output_a_re, 1-2);
-		set_offset(m.output_a_im, 1-2);
-		set_offset(m.output_b_re, 0-2);
-		set_offset(m.output_b_im, 0-2);
+		set_offset(m.output_a_re, 0-2);
+		set_offset(m.output_a_im, 0-2);
+		set_offset(m.output_b_re, 1-2);
+		set_offset(m.output_b_im, 1-2);
 	}
 }
 
 INLINE void do_half_regular_stage(struct mems m, bool stage_odd, bool second_half){
+	 /*
+	 * We are doing two cycles in each iteration, so we can alternate the
+	 * cycle_odd argument (which only works with constants, I don't expect
+	 * the optimizer to do this loop unrolling for us). Since we need to
+	 * write outputs before reading, but don't have any outputs to write
+	 * in the first cycle, we must put the first cycle outside of the
+	 * loop. Since the loop does two cycles at a time, this means there
+	 * must be two cycles outside of the loop, so we put one at the end as
+	 * well. Additionally, we also need to write the outputs of the last
+	 * cycle in an extra cycle at the end. We probably can't combine this
+	 * last cycle with the first cycle of the next stage, because they
+	 * need the same memories (input becomes output and v.v.).
+	 */
+
+	/* Initialize output addresses, this must be done twice per stage */
+	init_output_addresses_regular(m, stage_odd, second_half);
+
+	/* First cycle (no previous output to write) */
 	struct bf_in in = read_input_regular(m, EVEN_CYCLE, stage_odd);
 	struct bf_out out = butterfly(in);
-	
-	/* Now, do a single stage. That means N_t / 2 cycles. Since we do 2
+
+	/* Now, do half a single stage. That means N_t / 4 cycles. Since we do 2
 	 * cycles on every iteration, plus one before and after the loop,
-	 * we will loop N_t / 4 - 1 times. */
-	init_loop(LC2, (N_t / 4) - 1);
-	do {
-		init_output_addresses_regular(m, stage_odd, second_half);
+	 * we will loop N_t / 8 - 1 times. We add an extra - 1 because this is a do while loop... */
+	init_loop(LC2, (PARAM_N_t / 8) - 1);
+	while (loop_next(LC2)) {
+		/* Write outputs of previous cycle */
 		write_output_regular(m, out, second_half);
 
+		/* Odd cycle */
 		in = read_input_regular(m, ODD_CYCLE, second_half);
 		out = butterfly(in);
 		next_cycle();
+
+		/* Write outputs of previous cycle */
 		write_output_regular(m, out, second_half);
 
+		/* Even cycle */
 		in = read_input_regular(m, EVEN_CYCLE, second_half);
 		out = butterfly(in);
-	} while (loop_next(LC2));
+	}
 	
+	/* Write outputs of previous cycle */
 	write_output_regular(m, out, second_half);
+
+	/* Last cycle */
 	in = read_input_regular(m, ODD_CYCLE, second_half);
 	out = butterfly(in);
-	
 	next_cycle();
+
+	/* Write outputs of last cycle */
 	write_output_regular(m, out, second_half);
+	
+	/* Force the next cycle, because the next stage must read from
+	 * the memory we just wrote to */
+	next_cycle();
 }
 
 INLINE struct mems init_mem_mapping(bool stage_odd){
@@ -212,23 +250,26 @@ INLINE struct mems init_mem_mapping(bool stage_odd){
 	return res;
 }
 void run() {
-#ifdef __MONTIUMCC__
-	/* main.cpp will call init before pre_run(), so only need to call init for MontiumCC */
-	init();
-#endif
 	do { freeze(); } while (gpi(0) == 0);
 	struct mems m;
-	
-	m = init_mem_mapping(EVEN_STAGE);
-	init_input_addresses_regular(m, EVEN_STAGE);
-	/* do_half_regular_stage will init output addresses */
-	next_cycle();
-	do_half_regular_stage(m, EVEN_STAGE, FIRST_HALF);
-	do_half_regular_stage(m, EVEN_STAGE, SECOND_HALF);
-	next_cycle();
-	init_input_addresses_regular(m, ODD_STAGE);
-	m = init_mem_mapping(ODD_STAGE);
-	next_cycle();
-	do_half_regular_stage(m, ODD_STAGE, FIRST_HALF);
-	do_half_regular_stage(m, ODD_STAGE, SECOND_HALF);
+
+	/* We need to do n_t regular stages. Since we do two stages each
+	 * iteration, we'll do n_t / 2 iterations. */
+	init_loop(LC1, (PARAM_n_t / 2));
+	while (loop_next(LC1)) {
+		m = init_mem_mapping(EVEN_STAGE);
+		init_input_addresses_regular(m, EVEN_STAGE);
+		/* do_half_regular_stage will init output addresses */
+		next_cycle();
+		do_half_regular_stage(m, EVEN_STAGE, FIRST_HALF);
+		do_half_regular_stage(m, EVEN_STAGE, SECOND_HALF);
+		stage++;
+		next_cycle();
+		init_input_addresses_regular(m, ODD_STAGE);
+		m = init_mem_mapping(ODD_STAGE);
+		next_cycle();
+		do_half_regular_stage(m, ODD_STAGE, FIRST_HALF);
+		do_half_regular_stage(m, ODD_STAGE, SECOND_HALF);
+		stage++;
+	}
 }