X-Git-Url: https://git.stderr.nl/gitweb?a=blobdiff_plain;f=FFT.mc;h=4a80cfa8cc6241cc3f28a5c7d6b1e6a79c823215;hb=23a9ac963f8123a6fecf5105492f8be5e2da8190;hp=6df71adcf9574508b3254204185c092ce8e12746;hpb=6599667fbc3945f5a32569832a79c543aa233d44;p=matthijs%2Fprojects%2Fmontium-fft.git diff --git a/FFT.mc b/FFT.mc index 6df71ad..4a80cfa 100644 --- a/FFT.mc +++ b/FFT.mc @@ -16,8 +16,10 @@ INLINE struct bf_out butterfly(struct bf_in in) { /* 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)); @@ -49,7 +51,7 @@ INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_h 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); @@ -73,7 +75,7 @@ INLINE void write_output_regular(struct mems m, struct bf_out res, bool second_h * read input a from memory b and v.v. If not, * simply read a from memory a and b from memory b. */ -INLINE struct bf_in read_input_regular(struct mems m, bool cycle_odd, bool stage_odd) { +INLINE struct bf_in read_input_regular(struct mems m, bool cycle_odd, int stage) { struct bf_in in; /* Swap memory a and b during the odd cycles */ if (cycle_odd) { @@ -96,16 +98,21 @@ INLINE struct bf_in read_input_regular(struct mems m, bool cycle_odd, bool stage 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 writing the outputs. - * @param stage_odd True if this is an odd stage. - * @param second_half True if we are initing halfway a stage. + * Initializes the addresses for reading the inputs and twiddel factors. + * Should be called once at the start of each stage. */ -INLINE void init_input_addresses_regular(struct mems m, bool stage_odd) { +INLINE void init_input_addresses_regular(struct mems m) { /* We simply start reading at address 0 incrementally */ set_base(m.input_a_im, 0); set_base(m.input_b_re, 0); @@ -125,7 +132,7 @@ INLINE void init_input_addresses_regular(struct mems m, bool stage_odd) { * 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) { +INLINE void init_output_addresses_regular(struct mems m, bool second_half) { /* * For the second half of the stage, the starting addresses are * reversed. write_output_regular above will also swap the output @@ -147,14 +154,14 @@ 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){ +INLINE void do_half_regular_stage(struct mems m, int stage, 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 @@ -170,22 +177,22 @@ INLINE void do_half_regular_stage(struct mems m, bool stage_odd, bool second_hal */ /* Initialize output addresses, this must be done twice per stage */ - init_output_addresses_regular(m, stage_odd, second_half); + init_output_addresses_regular(m, second_half); /* First cycle (no previous output to write) */ - struct bf_in in = read_input_regular(m, EVEN_CYCLE, stage_odd); + struct bf_in in = read_input_regular(m, EVEN_CYCLE, stage); 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); + * 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 - 1); do { /* Write outputs of previous cycle */ write_output_regular(m, out, second_half); /* Odd cycle */ - in = read_input_regular(m, ODD_CYCLE, second_half); + in = read_input_regular(m, ODD_CYCLE, stage); out = butterfly(in); next_cycle(); @@ -193,7 +200,7 @@ INLINE void do_half_regular_stage(struct mems m, bool stage_odd, bool second_hal write_output_regular(m, out, second_half); /* Even cycle */ - in = read_input_regular(m, EVEN_CYCLE, second_half); + in = read_input_regular(m, EVEN_CYCLE, stage); out = butterfly(in); } while (loop_next(LC2)); @@ -201,7 +208,7 @@ INLINE void do_half_regular_stage(struct mems m, bool stage_odd, bool second_hal write_output_regular(m, out, second_half); /* Last cycle */ - in = read_input_regular(m, ODD_CYCLE, second_half); + in = read_input_regular(m, ODD_CYCLE, stage); out = butterfly(in); next_cycle(); @@ -213,9 +220,15 @@ INLINE void do_half_regular_stage(struct mems m, bool stage_odd, bool second_hal next_cycle(); } -INLINE struct mems init_mem_mapping(bool stage_odd){ +/** + * Assign the input and output memories, based on the current stage. Also + * assigns the twiddle memories, but those are fixed. + */ +INLINE struct mems init_mem_mapping(int stage){ struct mems res; - if (stage_odd) { + /* Use left memories for input on odd (ie, first) + * stages and right memories on even stages. */ + if ((stage % 2) == 0) { res.input_a_re = alloc_mem(P0M1); res.input_a_im = alloc_mem(P1M1); res.input_b_re = alloc_mem(P2M1); @@ -240,20 +253,21 @@ INLINE struct mems init_mem_mapping(bool stage_odd){ return res; } -void run() { - do { freeze(); } while (gpi(0) == 0); - struct mems m; - - m = init_mem_mapping(EVEN_STAGE); - init_input_addresses_regular(m, EVEN_STAGE); + +INLINE void do_regular_stage(int stage) +{ + struct mems m = init_mem_mapping(stage); + init_input_addresses_regular(m); /* 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); + do_half_regular_stage(m, stage, FIRST_HALF); + do_half_regular_stage(m, stage, SECOND_HALF); +} +void run() { + do { freeze(); } while (gpi(0) == 0); + + do_regular_stage(1); + do_regular_stage(2); + do_regular_stage(3); + do_regular_stage(4); }