///  LSU EE 4755 -- Fall 2024 -- Digital Design / HDL
///
///  Elaboration, Parameters, and Generate Constructs

 // Under construction.  Still

/// References

// :SV23: IEEE 1800-2023 -- The SystemVerilog Standard
//        https://ieeexplore.ieee.org/document/10458102
//        This is for those already familiar with Verilog.
//
// :BV3:  Brown & Vranesic, Fundamentals of Digital Logic with Verilog, 3rd Ed.
//        The text used in LSU EE 2740.


//////////////////////////////////////////////////////////////////////////////
/// Elaboration

 // :Def: Elaboration [of a module]
 // The process of locating instantiated modules, applying parameter
 // values, and running generate expressions. It is roughly analogous
 // to preprocessig in C.
 //
 // Elaboration happens BEFORE simulation, and so it happens before
 // initial blocks are executed.

 // :Def: Design Hierarchy
 // Details about the design elaborated from some top-level modules
 // constructed and used by a Verilog tool, such as simulator, synthesis
 // program, etc.
 //
 // Cadence Xcelium uses program xmelab for elaboration. (It is
 // automatically called by other tools.)
 //
 // Using Genus, the design hierarchy can be explored in the
 // command-line interface using filesystem-like commands vls and vcd,
 // which, after the initial 'v' is removed, work like their Unix
 // counterparts. Using the Genus GUI the design hierarchy is visible
 // in the Design Browser pane.

 // :Example:
 //
 // Module sat_add (saturating adder) is instantiated three times by
 // elab_demo, at two different sizes.
 //
 // After elaborating elab_demo, the design hierarchy will have four
 // modules: elab_demo, two sat_add's at 5 bits, and one at 9 bits.

module sat_add
  #( int width = 8 )
   ( output uwire [width:1] sum,
     input uwire [width:1] a, b );

   localparam logic [width:1] val_max = -1; // Or ( 1 << width ) - 1

   uwire [width:1] raw_sum;
   uwire           carry_out;
   assign         { carry_out, raw_sum } = a + b;
   assign         sum = carry_out ? val_max : raw_sum;

endmodule

module elab_demo
  ( output uwire [4:0] s1, s3,
    output uwire [8:0] s2, d,
    input uwire [4:0] a, b,
    input uwire [8:0] c );

   sat_add #(5) a1( s1, a,  b);
   sat_add #(5) a2( s3, a, -b);
   sat_add #(9) a3( s2, {9'b1110} , c);

   assign d = s2 - s1;

endmodule

//////////////////////////////////////////////////////////////////////////////
/// Elaboration-Time Constants

 // :SV23: Section 6.20 Constants

 // :Def: Elaboration-Time Constant
 //  - An object declared with the qualifiers:
 //    :Keywords: localparam,genvar,parameter,specparam
 //  - A parameter declared in a module header (using #).
 //  - An expression consisting only of elaboration-time constants and
 //    a subset of functions.

 // :Example:
 //
 // Consider the saturating adder from above.

module sat_add_from_above
  #( int width = 8 )
  // width is an elaboration-time constant because it is a parameter.

   ( output uwire [width:1] sum,

     // Input a IS NOT an elaboration-time constant, even for elab_demo.a2.
     input uwire [width:1] a,

     input uwire [width:1] b );

   // Var val_max is an elaboration-time constant because it is
   // declared localparam.
   //
   localparam logic [width:1] val_max = -1;

   // The right-hand-side, width - 1, is an elaboration-time constant
   // because it is an expression consisting only of elaboration-time
   // constants (just width in this case), operators (just - in this
   // case), and constant functions (no functions here).
   //
   localparam int wm1 = width - 1;

   // NOT an elaboration-time constant ...
   uwire [7:0] not_constant_enough = 5;
   // ... because object kind is not one of localparam, genvar, etc.

   uwire [7:0] not_constant_enough_either;
   assign not_constant_enough_either = 5;

   uwire [wm1:0] raw_sum;
   uwire           carry_out;
   assign         { carry_out, raw_sum } = a + b;
   assign         sum = carry_out ? val_max : raw_sum;

endmodule



//////////////////////////////////////////////////////////////////////////////
/// Generate Constructs

// :SV23: Chapter 27

 /// :Def: Generate Construct
 //  Verilog statements that are executed during elaboration and
 //  which essentially write new Verilog code.
 //
 /// Important Concepts
 //
 //  Generate statements execute before simulation or synthesis.
 //
 //  Expressions in generate statements can only refer to elaboration-time
 //    constants (expressions that can be computed in terms of parameters,
 //    literals, and genvars.)
 //
 //  Unlike procedural code, generate statements can be placed
 //    in module scope.

 ///  The Generate Constructs
 //
 ///   - Integer object kind for use in generate loops.
 //       :Keyword: genvar
 //        Declares an integer-valued object that can be used as
 //         an iterator in generate loops.
 //        See the "for" construct.
 //
 ///   - Loop Generate Constructs
 //       :Keyword: for
 //       :Syntax:  for ( genvar IDENT = INIT; TEST; INCR ) STATEMENT;
 //
 //       Iterator must be of kind genvar.
 //       INIT, TEST, and INCR must be expressions that consist
 //        of genvar's and elaboration-time constants.
 //
 //       STATEMENT can contain assign's and instantiations.
 //       :Sample: for ( genvar i=0; i<9; i++ ) begin assign a[i] = b[w-i]; end
 //
 ///   - Conditional Generate Constructs
 //       :Keywords: if,else,case,endcase
 //       if / else
 //       case / endcase

 /// :Practice Problems:
 //
//   2017 Midterm Exam Problem 5b -- Easy
//    -- Correct the use of generate statements.
//    https://www.ece.lsu.edu/v/2017/mt.pdf
//    https://www.ece.lsu.edu/v/2017/mt_sol.pdf
//
//   2022 Midterm Exam Problem 2 -- Moderate Difficulty
//    -- Convert radix-r ASCII within a string to integer.
//    https://www.ece.lsu.edu/v/2022/mt.pdf
//    https://www.ece.lsu.edu/v/2022/mt_sol.pdf


// :Example:
//
// Use a generate "if" for a shift module that can shift either left or right.
//
module shift_operator
  #( int w = 5, bit shift_left = 1 )
  ( output uwire [w-1:0] shifted,
    input uwire [w-1:0] un,
    input uwire [$clog2(w)-1:0] amt );

   // This module uses a generate if.

   // An instance can shift either left or right.
   // The hardware (and its cost) will be for a left shifter or a right shifter.

   if ( shift_left )  // This is a generate "if", okay in module scope.
     assign shifted = un << amt;
   else
     assign shifted = un >> amt;

endmodule
//
module shift_operator_2
  #( int w = 5 )
  ( output uwire [w-1:0] shifted,
    input uwire shift_left,
    input uwire [w-1:0] un,
    input uwire [$clog2(w)-1:0] amt );

   // This module does not use generate statements.

   // An instance can shift both shift left and right.
   // The hardware (and its cost) will be both a left and right shifter.

   assign shifted = shift_left ? un << amt : un >> amt;

endmodule


// :Example:
//
// Use of generate for loop to construct a ripple adder.
//
// First, define a BFA (binary full adder) in the usual way.
//
module bfa( output uwire sum, cout, input uwire a, b, cin );
   assign  sum = a ^ b ^ cin;
   assign  cout = a & b | a & cin | b & cin;
endmodule
//
// Next, connect four BFAs to form a 4-bit ripple adder:
//
// 
//
// Here is how the ripple adder is described in Verilog without
// generate statements:
//

module ripple_4
   ( output uwire [3:0] sum,  output uwire cout,
     input uwire [3:0] a, b,  input uwire cin);

   uwire         c0, c1, c2;

   bfa bfa0( sum[0], c0,   a[0], b[0], cin );
   bfa bfa1( sum[1], c1,   a[1], b[1], c0  );
   bfa bfa2( sum[2], c2,   a[2], b[2], c1  );
   bfa bfa3( sum[3], cout, a[3], b[3], c2  );
   //
   // How tedious!  What if we need a 16-bit ripple adder? Or 64? 128?

endmodule
//
// Use of generate statements to instantiate BFA's ..
// .. to construct 4-bit ripple adder.
//
module ripple_4_elab
  ( output uwire [3:0] sum,  output uwire cout,
    input uwire [3:0] a, b,  input uwire cin);

   uwire         carry[3:-1];
   assign        carry[-1] = cin;
   assign        cout = carry[3];

   for ( genvar i=0; i<4; i++ )
      bfa bfai( sum[i], carry[i], a[i], b[i], carry[i-1] );
   //
   /// Please make sure that you understand what the loop above is doing:
   ///   It is instantiating (creating) four BFA's ..
   ///   .. IT IS NOT using the same BFA four times.

endmodule
//
// Use of generate statements to instantiate BFA's ..
// .. to construct a ripple adder of any size (using parameter w).
//
module ripple_w
  #( int w = 4 )
   ( output uwire [w-1:0] sum,   output uwire cout,
     input uwire [w-1:0] a, b,   input uwire cin);

   uwire         c[w-1:-1];
   assign        c[-1] = cin;
   assign        cout = c[w-1];

   for ( genvar i = 0; i<w; i++ )
     bfa bfai( sum[i], c[i], a[i], b[i], c[i-1] );

endmodule
//
// :


// :Example:
//
// Miscellaneous correct and incorrect usage of generate statements.
//
module gen_examples1
  #( int option = 0 )
   ( output uwire logic [7:0] ab, abc,
     output var logic [7:0] vab, vabc,
     input uwire logic [7:0] a, b, c );

   for ( genvar i=0; i<8; i += 2 )
     // This *IS NOT PROCEDURAL* code ... that's why assign is okay.
     begin
        assign ab[i] = a[i];
        assign ab[i+1] = b[i+1];
     end

   `ifdef IF_THIS_IS_DEFINED_CODE_SHOULDNT_COMPILE
   always_comb
     // This is procedural code (because of the always_comb) ...
     /// ... that's why assign is *NOT OKAY*.
     for ( int i=0; i<8; i+=2 ) begin
        assign ab[i] = a[i];
        assign ab[i+1] = b[i+1];
     end
   `endif

   always_comb
     // This is correct procedural code.
     for ( int i=0; i<8; i+=2 ) begin
        vab[i] = a[i];
        vab[i+1] = b[i+1];
     end

   for ( genvar i=0; i<8; i++ )
     begin:myblock
        uwire aab;
        and a1(aab,a[i],b[i]);
        if ( option == 0 )
          or  o1(abc[i],aab,c[i]); // Instantiation okay because in genblock.
        else
          xor o1(abc[i],aab,c[i]);
     end

endmodule
//
module gen_examples2
   ( output uwire [7:0] ab,abc,
     input uwire option,
     input uwire [7:0] a, b, c );

   // This code IS good.
   for ( genvar i=0; i<8; i += 2 )
     begin
        assign ab[i] = a[i];
        assign ab[i+1] = b[i+1];
     end

   `ifdef SHOW_BAD_CODE
   for ( genvar i=0; i<8; i++ )
     begin:myblock
        uwire aab;
        and a1(aab,a[i],b[i]);
        /// The generate IF below is BAD, because option not constant.
        if ( option == 0 )
          or  o1(abc[i],aab,c[i]);
        else
          xor x1(abc[i],aab,c[i]);
     end
    `endif

   // This code IS good.
   for ( genvar i=0; i<8; i++ )
     begin:myotherblock
        uwire aab, ior, eor;
        and a1(aab,a[i],b[i]);
        or  o1(ior,aab,c[i]);
        xor x1(eor,aab,c[i]);
        assign abc[i] = option == 0 ? ior : eor;
     end

endmodule


//////////////////////////////////////////////////////////////////////////////
/// Recursion Using Generate Constructs 

 /// Recursive Definition of a Module
//
//   Sometimes it's easier to describe something recursively.
//     E.g., Multiplexors, minimum, sorting modules.
//   Sometimes it's not.
//     E.g., Ripple adder.
//
 /// General Idea
//
//   A module instantiates one or more smaller modules ..
//   .. splits work between these smaller modules ..
//   .. and (if necessary) combines their outputs.

 /// :Practice Problems:
//
//   2019 Homework 2 -- Count Low Zeros
//    https://www.ece.lsu.edu/v/2019/hw02.pdf
//    https://www.ece.lsu.edu/v/2019/hw02_sol.pdf
//
//   2016 Homework 4 -- A Table Lookup
//    https://www.ece.lsu.edu/v/2016/hw04.pdf
//    https://www.ece.lsu.edu/v/2016/hw04.v.html
//    https://www.ece.lsu.edu/v/2016/hw04_sol.pdf
//    https://www.ece.lsu.edu/v/2016/hw04-sol.v.html
//
//   2017 Midterm Exam Problem 2 -- Recursively Described Multiplexor
//    https://www.ece.lsu.edu/v/2017/mt.pdf
//    https://www.ece.lsu.edu/v/2017/mt_sol.pdf
//
//   2022 Midterm Exam Problem 1c -- Recursively Described 2-Input [sic] Mux
//    https://www.ece.lsu.edu/v/2022/mt.pdf
//    https://www.ece.lsu.edu/v/2022/mt_sol.pdf
//
//   2014 Homework 2 -- Integer Multiplier
//    https://www.ece.lsu.edu/v/2014/hw02.pdf
//    https://www.ece.lsu.edu/v/2014/hw02.v.html
//    https://www.ece.lsu.edu/v/2014/hw02-sol.v.html
//
//   2020 Midterm Exam Problem 4 -- Recursively Defined Multiplier (BFA,BHA)
//    https://www.ece.lsu.edu/v/2020/mt.pdf
//    https://www.ece.lsu.edu/v/2020/mt_sol.pdf
//
//   2018 Homework 5 -- Batcher Odd/Even Sorting Network
//    https://www.ece.lsu.edu/v/2018/hw05.pdf
//    https://www.ece.lsu.edu/v/2018/hw05.v.html
//    https://www.ece.lsu.edu/v/2018/hw05-sol.v.html


// :Example:
//
// Note: I don't like this example because it shows where recursion
// should *not* be used. Recursion shouldn't be used for the ripple
// adder because it makes the description more complicated and does
// not have any compensating benefit. I feel the same way about using
// recursion to compute a factorial.
//
// Recursive description of a ripple adder.
// Here, recursion may not be worth the trouble ..
// .. see ripple_w above which avoids recursion.
//
module ripple_w_r
  #( int w = 16 )
   ( output uwire [w-1:0] sum,   output uwire cout,
     input uwire [w-1:0] a, b,   input uwire cin);

   uwire c;

   // Instantiate a BFA to handle least-significant bit.
   //
   bfa bfa( sum[0], c, a[0], b[0], cin );

   if ( w == 1 )
     // If just one bit, we're done.
     //
     assign cout = c;
   else
     // Recursively instantiate this module to handle remaining bits.
     //
     ripple_w_r #(w-1) r(sum[w-1:1], cout, a[w-1:1], b[w-1:1], c);

   // Note: Don't use recursion for hardware like this. Recursion is
   // correct but is less intuitive. Instead use iteration as in
   // ripple_w.

endmodule

 // 
 // 



//////////////////////////////////////////////////////////////////////////////
/// Recursive Description of Tree Structures
//
//
 /// Typical Steps: (See simple_tree, below)
//
//  - Start with a module that has some kind of size parameter.
//  - Split work (usually inputs) into two parts, call the parts lo and hi.
//  - Recursively instantiate two copies of the module ..
//    .. connecting lo to one module and hi to the other module ..
//    .. making sure that at least one size parameter 
//    .. is smaller that its value in the enclosing module.
//  - Combine the outputs of the two modules.
//  - Provide a non-recursive case for when size is minimum ..
//    .. this might be called the termination condition.
//
module simple_tree
  #( int n = 16, int w = 32 )
   ( output uwire [w-1:0] sum, input uwire [w-1:0] a[n] );

   // Note: n is the size parameter.

   if ( n > 1 ) begin

      // Recursive case.

      uwire [w-1:0] xlo, xhi;

      // Work, a, is split into a[n/2-1:0] and a[n-1:n/2}.

      // Recursive instantiations.
      //
      simple_tree #(n/2,w)   st_lo( xlo, a[0:n/2-1] );
      simple_tree #(n-n/2,w) st_hi( xhi, a[n/2:n-1] );
      //
      // n/2 is smaller than n (since n > 1)
      // n-n/2 is also smaller than n (since n > 1)

      // Combine outputs.
      assign sum = xlo + xhi;
      //
      // The combination here is simple.

   end else begin

      // Non-recursive case for minimum size, n == 1
      //
      assign sum = a[0];

   end

endmodule

module sans_arbe
  #( int n = 16, int w = 32 )
   ( output logic [w-1:0] sum, input uwire [w-1:0] a[n] );

   always_comb begin
      sum = a[0];
      for ( int i=1; i<n; i++ ) sum += a[i];
   end

   // First of all, if your goal is to compute an integer sum the code
   // above is best because we expect the synthesis program to do a
   // good job with such a common operation. The synthesis program
   // knows that integer addition is associative and commutative and
   // will transform the computation as needed, possibly into a tree
   // form, to realize a low-cost design meeting the provided timing
   // constraint.
   //
   // For other operations, the synthesis program might not produce as
   // good a result and so for those a recursive tree structure would
   // be better.

endmodule



// :Example:
//
// Find the minimum of n numbers. Use generate constructs to
// describe linear- and tree-structured modules.

module min_2
  #( int w = 4 )
   ( output uwire [w-1:0] e_min,
     input  uwire [w-1:0] e_0, e_1 );

   assign e_min = e_0 < e_1 ? e_0 : e_1;

endmodule

 // 

module min_n_tree_live
  #( int w = 4,  n = 8 )
   ( output uwire [w-1:0] e_min,
     input  uwire [w-1:0] e[n] );


   if ( n == 1 ) begin

      assign e_min = e[0];

   end else begin

      localparam int nlo = n/2;
      localparam int nhi = n - nlo;

      uwire [w-1:0] e_lo, e_hi;

      min_n_tree_live #( .n(nlo), .w(w) ) mt_lo( e_lo, e[0:nlo-1] );
      min_n_tree_live #( .n(nhi), .w(w) ) mt_hi( e_hi, e[nlo:n-1] );

      min_2 #(w) min( e_min, e_lo, e_hi );

   end

endmodule


module min_n
  #( int w = 4,  n = 8 )
   ( output uwire [w-1:0] e_min,
     input  uwire [w-1:0] e[n] );

   uwire [w-1:0] im[n];
   assign im[0] = e[0];

   for ( genvar i = 1; i < n; i++ )
     min_2 #(w) m( im[i], e[i], im[i-1] );

   assign e_min = im[n-1];

endmodule

 // 


module min_t
  #( int w = 4,  n = 8 )
   ( output uwire [w-1:0] e_min,
     input uwire [w-1:0] e [ n-1:0 ] );

   if ( n == 1 ) begin

      assign e_min = e[0];

   end else begin

      localparam int n_lo = n / 2;
      localparam int n_hi = n - n_lo;

      uwire [w-1:0] m_lo, m_hi;

      min_t #(w,n_lo) mlo( m_lo, e[n_lo-1:0] );
      min_t #(w,n_hi) mhi( m_hi, e[n-1:n_lo] );

      min_2 #(w) m2( e_min, m_lo, m_hi);

   end

endmodule

 // 

 // 

 // 

 // 


module pop
  #( int w = 16, int wl = $clog2(w+1) )
   ( output logic [wl-1:0] p,
     input uwire [w-1:0] a );

   always_comb begin
      p=0;
      for ( int i=0; i<w; i++ ) p += a[i];
   end

endmodule

module pop_t
  #( int w = 16,
     int wl = $clog2(w+1) )
   ( output uwire [wl-1:0] p,
     input uwire [w-1:0] a );

   if ( w == 1 ) begin

      assign p = a[0];

   end else begin
      localparam int wlo = w/2, whi = w-wlo;
      uwire [$clog2(wlo+1)-1:0] p_lo, p_hi;
      pop_t #(wlo) plo(p_lo,a[wlo-1:0]);
      pop_t #(whi) phi(p_hi,a[w-1:wlo]);
      assign p = p_lo + p_hi;
      
   end
   

endmodule










   


// :Example:
//
// Implement a population count module using recursion.
//
// Note: The population of a bit vector (which might hold an integer)
// is the number of bits equal to 1. For example, the population of
// 8'b00010100 is 2 and the population of 8'b10010011 is 4.

// Live module, not yet finished. (20 September 2018, 12:33:26 CDT)
module pop
  #( int w = 5,
     int pw = $clog2(w) )
   (output var logic [pw-1:0] p,
    input uwire [w-1:0] a );

   if ( w == 1 ) begin

      assign p = a[0];

   end else begin
     
   uwire [pw-1:0] p_lo, p_hi;
   localparam int wlo = w / 2;
   localparam int whi = w - wlo;
   pop #(wlo,pw) plo(p_lo, a[wlo-1:0]);
   pop #(whi,pw) phi(p_hi, a[w-1:wlo]);
   assign p = p_lo + p_hi;
      end
   `ifdef justincaseineeditlater
   always_comb begin

      p = 0;
      for ( int i=0; i<w; i++ ) p += a[i];

   end
   `endif

endmodule








// A population count module using procedural code.
//
module pop_1
  (output logic [4:0] p,
   input uwire [15:0] v );

   always_comb begin
      p = 0;
      for ( int i=0; i<16; i++ ) p += v[i];
   end

endmodule

// A population count module using recursion to describe a tree
// structure.
//
module pop_n
  #( int bits = 16 )
   ( output uwire [4:0] p,
     input uwire [bits-1:0] v );

   if ( bits == 1 ) begin

      assign p = v[0];

   end else begin

      uwire [4:0]         p1, p2;

      // Split work in half between two modules.
      //
      pop_n #(bits/2)      pi1( p1, v[bits/2-1:0] );
      pop_n #(bits-bits/2) pi2( p2, v[bits-1:bits/2] );

      // And then combine the results of each.
      //
      assign p = p1 + p2;

   end

endmodule