////////////////////////////////////////////////////////////////////////////////
///
/// Solution to LSU EE 3755 Spring 2002 Homework 4
///


////////////////////////////////////////////////////////////////////////////////
/// Problem 1
///

// Complete the module below so that it performs 18 bit x 9 bit
// unsigned integer multiplication using a radix-8 multiplier using
// the same handshaking as mult_18x9_sim (and other modules presented
// in class).
//
// Hint: The solution is a straightforward extension of imult_ord_radix_4
// in l07 (http://www.ece.lsu.edu/ee3755/2002/l07.html) to radix 8.


module mult_radix_8(prod,ready,cand,multiplier,start,clk);
   input [17:0]  cand;
   input [8:0]   multiplier;
   input         start, clk;
   output        prod;
   output        ready;

   reg [29:0]    product;
   wire [26:0]   prod = product[26:0];

   reg [1:0]     bit; 
   wire          ready = !bit;
   
   initial bit = 0;

   wire [18:0]   candx2 = cand << 1;
   wire [19:0]   candx3 = candx2 + cand;
   wire [19:0]   candx4 = cand << 2;
   wire [20:0]   candx5 = candx4 + cand;
   wire [20:0]   candx6 = candx4 + candx2;
   wire [20:0]   candx7 = candx6 + cand;

   always @( posedge clk )

     if( ready && start ) begin

        bit     = 3;
        product = { 19'd0, multiplier };
        
     end else if( bit ) begin


        case ( product[2:0] )

          3'b000: product[29:9] = product[29:9];
          3'b001: product[29:9] = product[29:9] + cand;
          3'b010: product[29:9] = product[29:9] + candx2;
          3'b011: product[29:9] = product[29:9] + candx3;
          3'b100: product[29:9] = product[29:9] + candx4;
          3'b101: product[29:9] = product[29:9] + candx5;
          3'b110: product[29:9] = product[29:9] + candx6;
          3'b111: product[29:9] = product[29:9] + candx7;
          
        endcase

        product = product >> 3;
        bit     = bit - 1;

     end

endmodule


////////////////////////////////////////////////////////////////////////////////
/// Problem 2
///

// Complete the module below so that it performs a 18 x 18 bit
// unsigned integer multiplication using two mult_prob_2 18 x 9 bit
// multiplier modules.  All modules use the same handshaking.


module mult_faster(prod,ready,cand,multiplier,start,clk);
   input [17:0]  cand;
   input [17:0]  multiplier;
   input         start, clk;
   output [35:0] prod;
   output        ready;

   wire [26:0]    prod_lo, prod_hi;
   wire           rdy_1;

   mult_prob_2 m1(prod_lo,rdy_1,cand,multiplier[8:0], start,clk);
   mult_prob_2 m2(prod_hi,ready,cand,multiplier[17:9],start,clk);

   assign prod = prod_lo + ( prod_hi << 9 );

endmodule


////////////////////////////////////////////////////////////////////////////////
/// Problem 3
///

// Complete the module below so that it performs a 18 x 18 bit
// unsigned integer multiplication using one mult_prob_3 18 x 9 bit
// multiplier module.  All modules use the same handshaking.
//
// Hint: Use a state machine to control the two modules.


module mult_cheaper(prod,ready,cand,multiplier,start,clk);
   input [17:0]  cand;
   input [17:0]  multiplier;
   input         start, clk;
   output [35:0] prod;
   output        ready;

   parameter     ST_rdy    = 3'd0;
   parameter     ST_m1_rdy = 3'd1;
   parameter     ST_m1_cmp = 3'd2;
   parameter     ST_m2_rdy = 3'd4;
   parameter     ST_m2_cmp = 3'd5;

   reg [2:0]     state;

   wire [8:0]    lier = state[2] ? multiplier[17:9] : multiplier[8:0];

   reg [26:0]    first_prod;

   wire [26:0]   prod_m;
   wire          ready_m;
   reg           start_m;
   
   mult_prob_3 m(prod_m,ready_m,cand,lier,start_m,clk);

   assign        ready = state == ST_rdy;
   assign        prod  = first_prod + ( prod_m << 9 );

   always @( state or start )
     case( state )
       ST_rdy               : start_m = start;
       ST_m1_rdy, ST_m2_rdy : start_m = 1;
       default              : start_m = 0;
     endcase

   always @( posedge clk )
     case( state )
       ST_rdy    : if( start    ) state = ST_m1_rdy;
       ST_m1_rdy : if( ~ready_m ) state = ST_m1_cmp;
       ST_m1_cmp : if( ready_m  ) begin first_prod=prod_m;  state=ST_m2_rdy; end
       ST_m2_rdy : if( ~ready_m ) state = ST_m2_cmp;
       ST_m2_cmp : if( ready_m  ) state = ST_rdy; 
       default   : if( ready_m  ) state = ST_rdy; 
     endcase

endmodule


// exemplar translate_off


module mult_prob_2(prod,ready,cand,multiplier,start,clk);
   input [17:0]  cand;
   input [8:0]   multiplier;
   input         start, clk;
   output [26:0] prod;
   output        ready;

   mult_18x9_sim #(0) the_worlds_mult(prod,ready,cand,multiplier,start,clk);

endmodule

module mult_prob_3(prod,ready,cand,multiplier,start,clk);
   input [17:0]  cand;
   input [8:0]   multiplier;
   input         start, clk;
   output [26:0] prod;
   output        ready;

   mult_18x9_sim #(1) the_worlds_mult(prod,ready,cand,multiplier,start,clk);

endmodule

module mult_18x9_sim(prod,ready,cand,multiplier,start,clk);

   input [17:0]  cand;
   input [8:0]   multiplier;
   input         start, clk;
   output [26:0] prod;
   output        ready;

   parameter     random_delay = 0;

   reg [26:0]    prod;

   reg [3:0]     bit;  // Not necessarily size needed for other modules.
   wire          ready = !bit;
   
   initial bit <= 0;

   always @( posedge clk )

     if( ready && start ) begin

        bit <= random_delay ? 1 + $random : 3;
        
     end else if( bit ) begin

        bit <= bit - 1;
        if( bit == 1 ) prod <= cand * multiplier;

     end

endmodule


module test_faster();
   testmults #(0) tm();
endmodule

module test_cheaper();
   testmults #(1) tm();
endmodule

module test_8();
   testmults #(2) tm();
endmodule

module testmults();

   parameter DUT = 0;

   parameter stop_on_error = 1;

   parameter DUT_faster = 0;
   parameter DUT_cheaper = 1;
   parameter DUT_eight = 2;

   reg [35:0] product;
   wire [35:0] product_c, product_f;
   wire [26:0]  product_8;
   wire        ready_c, ready_f, ready_8;
   reg         ready;
   reg [17:0]  multiplier;
   reg [17:0]  multiplicand;
   reg         start, clk;

   reg [35:0]  shadow_product;
   integer     i;

   always @( product_c or product_f or product_8
             or ready_c or ready_f or ready_8 )
     case( DUT )
       DUT_faster:  begin  product = product_f;  ready = ready_f; end
       DUT_cheaper: begin  product = product_c;  ready = ready_c; end
       DUT_eight:   begin  product = product_8;  ready = ready_8; end
     endcase

   mult_radix_8 m8(product_8,ready_8,multiplicand,multiplier[8:0],start,clk);
   mult_cheaper mc(product_c,ready_c,multiplicand,multiplier,start,clk);
   mult_faster  mf(product_f,ready_f,multiplicand,multiplier,start,clk);

   always #10 clk = !clk;

   real cycles;
   initial begin cycles = 0; forever @( posedge clk ) cycles <= cycles + 1; end

   reg [17:0] lier_mask;
   reg [7*8-1:0] name;
   real          start_time;
   real          cpm;

   integer       err;

   initial begin

      case( DUT )
        DUT_faster:  begin  lier_mask = 18'o777777; name = "Faster"; end
        DUT_cheaper: begin  lier_mask = 18'o777777; name = "Cheaper"; end
        DUT_eight:   begin  lier_mask = 18'o000777; name = "Radix 8"; end
      endcase

      clk = 0;
      start = 0;
      err = 0;

      #25;

      start_time = cycles;

      $display("Starting test for %s",name);

      for(i=0; i<1000; i=i+1) begin

         wait( ready );

         #5;

         multiplier = $random & lier_mask;
         multiplicand = $random & 18'o777777;
         shadow_product = multiplier * multiplicand;

         #1;

         start = 1;
         wait( !ready );
         start = 0;
         wait( ready );
         #1;

         if( shadow_product !== product ) begin
            $display("FAIL: %s %o x %o = %o(correct) != %o\n",
                     name,
                     multiplier, multiplicand,
                     shadow_product, product );
            err = err + 1;
            if( stop_on_error && err >= stop_on_error ) $stop;
         end

      end

      cpm = (cycles - start_time) / ( i ? i : 1 );

      $display("Finished at speed of %f cycles per multiplication.", cpm);

      case ( DUT )
        DUT_faster:
          if( cpm > 5.1 ) begin
             $display("FAIL: Faster multiplier taking too long.");
             err = err + 1;
          end else if ( cpm < 3.0 ) begin
             $display("FAIL: Faster multiplier too fast.");
             err = err + 1;
          end
        DUT_eight:
          if( cpm > 4.1 ) begin
             $display("FAIL: Radix 8 multiplier taking too long.");
             err = err + 1;
          end else if ( cpm < 3.0 ) begin
             $display("FAIL: Radix 8 multiplier too fast.");
             err = err + 1;
          end
        DUT_cheaper:
          if( cpm > 22 ) begin
             $display("FAIL: Cheaper multiplier taking too long.");
             err = err + 1;
          end else if ( cpm < 15 ) begin
             $display("FAIL: Cheaper multiplier too fast.");
             err = err + 1;
          end
      endcase

      if( err )
        $display("FAIL: %s, encountered %d errors.",name,err);
      else
        $display("PASS: %s, no errors found.",name);

      $display("Done with tests.");
      
      $stop;

   end

endmodule

// exemplar translate_on