////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2018 Homework 3
//

 /// Live Solution to 2018 Homework 3
 //  Worked out during class on 25 and 27 September 2021. 

 /// Assignment  https://www.ece.lsu.edu/koppel/v/2018/hw03.pdf
  // Detailed solution:  https://www.ece.lsu.edu/koppel/v/2018/hw03-sol.v.html

`default_nettype none

//////////////////////////////////////////////////////////////////////////////
///  All Problems
//
 /// Modify sort2 so that it implements a 2-input sorting network ..
 /// .. using explicit and implicit structural code only.
//
//     [ ] Easy:   Modify to compare keys, not data.
//     [ ] Easy:   Modify to sort pairs of signed integer keys.
//     [ ] Medium: Modify to sort pairs of floating-point keys.
//     [ ] Medium: Modify to sort one signed int and one FP key.
//     [ ] Hard:   Keep cost and critical path low.
//
//     [ ] Use implicit and explicit structural code only.
//     [ ] Use mux2 to swap the values.
//     [ ] Add ChipWare Verilog modules to includes at the end of this file.
//
//     [ ] Module must be synthesizable. Use command: genus -files syn.tcl
//     [ ] Make sure that the testbench does not report errors.
//
//     [ ] Use SimVision for debugging.
//     [ ] Modify testbench to facilitate solution ..
//         .. but code must pass original testbench.

module sort2
  #( int w = 30,
     int k = 16,
     int exp = 5,
     int sig = k - exp - 1 )
   ( output uwire logic [w-1:0] x0, x1,
     input uwire logic [w-1:0] a0, a1 );

   /// Encoding of a0 and a1
   //
   // Bits        Contents
   // ---------   ------------------------------------------
   // w-1 : k+1   Data
   // k           Key type: 0, integer;  1, floating point.
   // k-1 : 0     Key, a signed integer; if Key type = 0.
   // k-1         Sign bit, if key type = 1.
   // k-2 : sig   Exponent, if key type = 1.
   // sig-1 : 0   Significand, if key type = 1.

   /// This is a live solution worked out during class on 25 and 27
   //  September 2021.

   uwire ci = signed'(a0[k-1:0]) <= signed'(a1[k-1:0]);

   uwire [k + exp + 1 -1:0] a0f, a1f, z0, z1;
   uwire [7:0] s0, s1, sc0, sc1;


   /// Brute-force solution: Set significand width to k. 
   //
   // This will have a higher cost than is necessary.
   //
   CW_fp_i2flt #( .isize( k ), .sig_width( k ), .exp_width( exp ) )
     itoflt0( .a(a0[k-1:0]), .rnd( 3'b0 ), .z( a0f ), .status(sc0) );
   CW_fp_i2flt #( .isize( k ), .sig_width( k ), .exp_width( exp ) )
     itoflt1( .a(a1[k-1:0]), .rnd( 3'b0 ), .z( a1f ), .status(sc1) );
   // 
   // See the "official" solution for a lower-cost approach
   // https://www.ece.lsu.edu/koppel/v/2018/hw03-sol.v.html

   uwire altb, aeqb, agtb, who_knows;
   //  uwire [sig+exp:0] z0, z1;

   uwire [k + exp + 1 -1:0] a0ff = a0[k-1:0] << ( k - sig );
   localparam logic [k-sig-1:0] pad = 0;
   uwire [k + exp + 1 -1:0] a1ff = { a1[k-1:0], pad };


   CW_fp_cmp #( .sig_width(k), .exp_width(exp) )
   cmp0( .a( a0[k] ? a0ff : a0f ),
         .b( a1[k] ? a1ff : a1f ), .altb( altb ), .aeqb( aeqb ),
         .unordered( who_knows ),
         .agtb( agtb ), .zctr( 1'b0 ), .status0(s1), .status1(s0),
         .z0(z0), .z1(z1) );

   uwire cf = altb || aeqb;

   uwire c = a0[k] || a1[k] ? cf : ci;

   mux2 #(w) m0( x0, c, a1, a0);
   mux2 #(w) m1( x1, c, a0, a1);

endmodule



module mux2
  #( int w = 4 )
   ( output uwire [w-1:0] x,
     input uwire select,
     input uwire [w-1:0] a0, a1 );
   assign x = select ? a1 : a0;
endmodule



//////////////////////////////////////////////////////////////////////////////
/// Testbench Code
//
//  The code below instantiates some of the modules above,
//  provides test inputs, and verifies the outputs.
//
//  The testbench may be modified to facilitate your solution. For
//  example, one might modify the testbench so that the first tests it
//  performs are those which make it easier to determine what the
//  problem is, for example, test inputs that are all 0's or all 1's.
//
//  Of course, the removal of tests which your module fails is not a
//  method of fixing a broken module.  The TA-bot will test your
//  code using a fresh copy of the testbench, not the one below.


// cadence translate_off

module testbench;

   var bit s[3];
   testbench_size #(32,16,6) t1(s[1],s[0]);
   testbench_size #(24,14,5) t2(s[2],s[1]);

   initial begin
      s[0] = 1;
      wait( s[2] );
      $write("\nAll done.\n");
   end

endmodule



module testbench_size
  #( int w = 30,
     int k = 16,
     int exp = 6,
     int sig_width = k - exp - 1 )
   ( output var bit done, input var bit start );

   localparam int s_pos = k - 1;
   localparam int exp_hi = s_pos - 1;
   localparam int exp_lo = s_pos - exp;
   localparam int sig_hi = exp_lo - 1;
   localparam int bias = ( 1 << exp - 1 ) - 1;
   localparam int exp_i_max = bias + k - 1;
   localparam int exp_max = ( 1 << exp ) - 2;
   localparam int exp_range_ini = exp_i_max - bias;
   localparam int exp_range_gti = exp_max - exp_i_max - 1;

   function real fp_to_val(input logic [k-1:0] a);
      fp_to_val =
        a[exp_hi:0] == 0 ? 0.0 :
          ( ( 1.0 + a[sig_hi:0] / real'( 1 << sig_width ) )
            * 2 ** ( 0.0 + a[exp_hi:exp_lo]-bias )
            * ( a[s_pos] ? -1 : 1 ) );
   endfunction

   /// Number of tests to perform.
   //
   //  Set to a low number, such as 3, when debugging one of the test
   //  cases added to tests queue below.
   //
   localparam int num_tests = 3000000;

   localparam int test_ff_start = num_tests / 3;
   localparam int test_if_start = test_ff_start * 2;

   uwire [w-1:0] x0, x1;
   logic [w-1:0] a[2];
   sort2 #(w,k,exp,sig_width) s2(x0,x1, a[0], a[1]);

   initial begin

      automatic int err_count[string] = '{"ii":0, "ff":0, "if":0 };

      automatic logic [1:0][w-1:0] tests[$];
      /// Add tests below by copying output of testbench.
      //  Note: Tests only work at a particular value of exp, k. 
      //  Put in correct place.
      case ( k )
        14: begin
           tests.push_back('h2a823); tests.push_back('h77b7e);
        end
        16: begin
           tests.push_back('hdc641209); tests.push_back('ha0935641);
        end
      endcase

      wait( start );
      $write("Starting testbench for w=%0d, k=%0d, exp=%0d  sig width=%0d...\n",
             w, k, exp, exp_lo);

      for ( int i=0; i<num_tests; i++ ) begin

         automatic logic [k-1:0] i_1_mask = 1 << {$random} % k;
         automatic string test_type =
           i < test_ff_start ? "ii" :
             i < test_if_start ? "ff" : "if";

         bit fp[2];
         real val[2];
         bit swap;
         logic [w-1:0] shadow_x0, shadow_x1;

         for ( int j=0; j<2; j++ )
           fp[j] = test_type == "ff" || test_type == "if" && ( (i+j) & 1 );

         for ( int j=0; j<2; j++ ) begin
            automatic int fp_sz = fp[j] ? {$random} % 4 : 4;
            a[j][w-1:0] = {$random};
            a[j][k] = fp[j];

            case ( fp_sz )
              0: a[j][exp_hi:0] = 0;
              1: a[j][exp_hi:exp_lo] = 1 + {$random} % bias;
              2: a[j][exp_hi:exp_lo] = bias + {$random} % exp_range_ini;
              3: a[j][exp_hi:exp_lo] = exp_i_max + {$random} % exp_range_gti;
              default:; // For int leave random value.
            endcase
         end

         // Test cases for floating-point pairs.
         if ( a[0][k] && a[1][k] && a[1][exp_hi:0] ) begin
            // Generate fp numbers with matching exponents
            if ( {$random} & 1 ) a[0][exp_hi:exp_lo] = a[1][exp_hi:exp_lo];
            // Generate fp numbers with matching significands.
            if ( {$random} & 1 ) a[0][sig_hi:0] = a[1][sig_hi:0];
         end

         // Test cases for integer pairs.
         if ( !a[0][k] && !a[1][k] ) begin
            case ( {$random} % 6 )

              // Differ by 1
              0: a[1][k-1:0] = a[0][k-1:0] - 1;
              1: a[1][k-1:0] = a[0][k-1:0] + 1;

              // Differ by 2
              2: a[1][k-1:0] = a[0][k-1:0] - 2;
              3: a[1][k-1:0] = a[0][k-1:0] + 2;

              // Sort key in only 1 bit.
              4: begin a[0][k-1:0] &= i_1_mask; a[1][k-1:0] &= i_1_mask; end

              default:;
            endcase
         end

         // Test cases for int/fp keys.
         if ( a[0][k] != a[1][k] ) begin
            automatic int opt = {$random} % 32;
            casex ( opt )
              'h0xxx: if ( a[0][k] ) a[1][k-1:0] = fp_to_val(a[0])+opt[2:0]-4;
              'h1xxx: if ( a[1][k] ) a[0][k-1:0] = fp_to_val(a[1])+opt[2:0]-4;
            endcase

         end

         // Replace the keys found above with user-defined keys, if any.
         if ( tests.size() ) begin
            a[0] = tests.pop_front();
            a[1] = tests.pop_front();
         end

         case ( {a[0][k], a[1][k] } )
           'b00: test_type = "ii";
           'b11: test_type = "ff";
           default: test_type = "if";
         endcase

         for ( int j=0; j<2; j++ )
           val[j] = a[j][k] ? fp_to_val(a[j]) : signed'(a[j][s_pos:0]);

         swap = val[0] > val[1];
         { shadow_x0, shadow_x1 } = { a[swap], a[1-swap] };

         #1;

         if ( shadow_x0 !== x0 || shadow_x1 !== x1 ) begin

            err_count[test_type]++;
            if ( err_count[test_type] > 5 ) continue;

            $write
              ("Test %s %4d, error (x0,x1): (%h,%h) != (%h,%h) correct.\n",
               test_type, i,
               x0, x1, shadow_x0, shadow_x1);
            for ( int j=0; j<2; j++ )
              $write("           a%1d: data %h, key %12.5f = %s %s\n",
                     j, a[j][w-1:k], val[j], a[j][k] ? "FP " : "INT",
                     a[j][k] ?
                     $sformatf("s %b  exp %0d-%0d=%0d  sig 'h%h",
                               a[j][s_pos],
                               a[j][exp_hi:exp_lo], bias,
                               signed'({1'b0,a[j][exp_hi:exp_lo]}) - bias,
                               a[j][sig_hi:0])
                     : $sformatf("'h%h",a[j][k-1:0]));
            $write("           To re-run paste:  tests.push_back('h%h); tests.push_back('h%h);\n",
                   a[0],a[1]);
         end

      end

      $write("Done with %0d tests for k=%0d, exp=%0d:", num_tests,k,exp);
      foreach ( err_count[et] )
        $write("   %0d %s errs,", err_count[et], et);
      $write("\n");

      done = 1;

   end

endmodule



// cadence translate_on

`default_nettype wire

// Add needed ChipWare modules below.

`include "/apps/linux/cadence/GENUS191/share/synth/lib/chipware/sim/verilog/CW/CW_fp_add.v"