/// LSU EE 4755 -- Fall 2014 -- DD Using HDLs
//
/// Maxrun Sample Code

// Time-stamp: <15 September 2014, 19:02:05 CDT, koppel@sky.ece.lsu.edu>

// This file contains Verilog code describing hardware to find the
// maximum number of consecutive 1's (the maximum run) in a binary
// vector. The hardware is combinational.

 /// Versions
//
 /// maxrun16_top / maxrun16 / maxrun4 / maxrun1
//
//   The simplest (arguably) synthesizable versions of the module. The
//   vector size is 16.
//
//   The maximum run is found via a linear chain of 16 maxrun1
//   modules. This approach, though simple to understand, results in
//   hardware that more costly and slower than necessary.
//
//
 /// maxrunn
//
//   This describes the same hardware as maxrun16_top, however
//   any size vector can be used.
//
//   This module shows how to use generate statements with a loop.
//
//   Also slow and costly.
//
//
 /// maxrunrec_top / maxrunrec / maxrunrec_a
//
//   Compute the maximum run use a tree-arrangement of modules. The
//   maxrunrec module is recursive: each module with in input vector
//   of 2 or more bits instantiates two smaller ones.
//
//   This module (actually maxrunrec_a) demonstrates how to use
//   generate statements to control recursion.
//
//   Performance is much better because of an O(lg N) critical path
//   and cost is O( N ), where N is the vector length.
//
//
 /// max_run_behav
//
//   A non-synthesizable behavioral maximum run module.
//
//   The purpose is to compute the maximum run in a simple way
//   and use that to check the other modules.
//
//   Synthesizablity will be covered in future lectures.



//////////////////////////////////////////////////////////////////////////////
/// Linear Maxrun Code,  Fixed Sizes
///


 /// One-Bit
//
module maxrun1(maxrun,outrun,v,maxrunin,inrun);
   input wire v;
   input wire [4:0]  inrun;           // Abbreviation: IR
   input wire [4:0]  maxrunin;        // Abbreviation: MIR
   output wire [4:0] maxrun, outrun;  // Abbreviation: MR, OR

   assign       outrun = v ? inrun + 1 : 0;

   assign       maxrun = outrun > maxrunin ? outrun : maxrunin;

endmodule

 /// Four Bits
//
module maxrun4(maxrun,outrun,vector,maxrunin,inrun);
   input wire [3:0] vector;
   input wire [4:0]  inrun;
   input wire [4:0]  maxrunin;
   output wire [4:0] maxrun, outrun;

   wire logic [4:0] mr1, mr2, mr3, mr4, or1, or2, or3, or4;

   maxrun1 mrm1( mr1, or1, vector[3], maxrunin, inrun);
   maxrun1 mrm2( mr2, or2, vector[2], mr1, or1);
   maxrun1 mrm3( mr3, or3, vector[1], mr2, or2);
   maxrun1 mrm4( maxrun, outrun, vector[0], mr3, or3);

endmodule

 /// Sixteen Bits
///
module maxrun16(maxrun,outrun,vector,maxrunin,inrun);
   input [15:0] vector;
   input [4:0]  inrun;
   input [4:0]  maxrunin;
   output [4:0] maxrun, outrun;

   wire         logic [4:0] mxrun[3:1], iorun[3:1];

   maxrun4 m1( mxrun[1], iorun[1], vector[15:12], maxrunin, inrun    );
   maxrun4 m2( mxrun[2], iorun[2], vector[11:8],  mxrun[1], iorun[1] );
   maxrun4 m3( mxrun[3], iorun[3], vector[7:4],   mxrun[2], iorun[2] );
   maxrun4 m4( maxrun,   outrun,   vector[3:0],   mxrun[3], iorun[3] );

endmodule


 /// Sixteen Bits, Without Extra Ports
//
module maxrun16_top(maxrun,vector);
   input [15:0] vector;
   output [4:0] maxrun;

   logic [4:0] outrun;

   maxrun16 m1(maxrun, outrun, vector, 5'b0, 5'b0);

endmodule


//////////////////////////////////////////////////////////////////////////////
/// Linear Maxrun,  Parameter Determines Size


module maxrunn
  #( int width = 16, bits = 5 )
   ( output logic [bits-1:0] mr_len,
     input logic [width-1:0] vector );

   logic [bits:1] iorun [width:-1];
   logic [bits:1] mxrun [width:-1];

   assign  iorun[-1] = 0;
   assign  mxrun[-1] = 0;

   generate

     for ( genvar i=0; i<width; i++ )
       maxrun1 mrm1( mxrun[i], iorun[i], vector[i], mxrun[i-1], iorun[i-1] );

   endgenerate

   assign  mr_len = mxrun[width-1];

endmodule


//////////////////////////////////////////////////////////////////////////////
/// Recursive Maxrun - Live

`define max(a,b) ((a)>=(b)?a:b)
`define max3(a,b,c) `max(`max(a,b),c)

module maxrunrec_live
  #( int width = 16, bits = 5 )
   ( output logic [bits-1:0] left, center, right,
     output logic full,
     input logic [width-1:0] vector );

   localparam int nwidth = width/2;
   localparam int nbits = bits-1;

   generate

     if ( width == 1 ) begin

        assign left = vector[0];
        assign center = vector[0];
        assign right = vector[0];

     end else begin

        maxrunrec_live #( nwidth, nbits ) mr_left
          (lleft, lcenter, lright, lfull, vector[width-1:nwidth] );

        assign  left = lleft;

        maxrunrec_live #( nwidth, nbits ) mr_right
          (rleft, rcenter, rright, rfull, vector[nwidth-1:0] );

        assign  right = rright;

        wire [bits-1:0] mid = lright + rleft;

        assign          center = `max3( lcenter, mid, rcenter );

     end

   endgenerate

endmodule


//////////////////////////////////////////////////////////////////////////////
/// Recursive Maxrun


// `define max(a,b) ((a)>=(b)?a:b)
// `define max3(a,b,c) `max(`max(a,b),c)

module maxrunrec
  #( int width = 16, bits = 5 )
   ( output logic [bits-1:0] left, center, right,
     output logic full,
     input logic [width-1:0] vector );

   localparam int nwidth = width >> 1;
   localparam int nbits = bits - 1;

   wire    logic [nbits-1:0] lleft, lcenter, lright;
   wire    logic [nbits-1:0] rleft, rcenter, rright;
   wire    logic lf, rf;

   maxrunrec_a #( nwidth, nbits ) mleft
     ( lleft, lcenter, lright, lf, vector[width-1:nwidth] );

   maxrunrec_a #( nwidth, nbits ) mright
     ( rleft, rcenter, rright, rf, vector[nwidth-1:0] );

   always @* begin
      logic [bits-1:0] mid;
      mid = lright + rleft;
      center = `max3( lcenter, mid, rcenter );
      full = lf && rf;
      left = lf ? mid : lleft;
      right = rf ? mid : rright;
   end

endmodule

module maxrunrec_a
  #( int width = 16, bits = 5 )
   ( output logic [bits-1:0] left, center, right,
     output logic full,
     input logic [width-1:0] vector );

   generate

     if ( width == 1 )

       always @* begin

           left = vector[0];
           center = vector[0];
           right = vector[0];
           full = vector[0];

       end

     else

       maxrunrec #( width, bits ) ml( left, center, right, full, vector );

   endgenerate

endmodule






module maxrunrectop
  #( int vlen = 16, bits = 5 )
   ( output logic [bits-1:0] mr_len,
     input logic [vlen-1:0] vector );

   wire    logic [bits-1:0] left, center, right;
   wire    logic f;

   maxrunrec #(vlen,bits) mr(left,center,right,f,vector);

   assign  mr_len = `max3( left, center, right );

endmodule


//////////////////////////////////////////////////////////////////////////////
/// Behavioral Maxrun

// cadence translate_off

module max_run_behav
  #( int vlen = 16, bits = 5 )
   ( output logic [bits-1:0] mr_len,
     input logic [vlen-1:0] vector );

   always @* begin

      automatic int mr_len_so_far = 0;

      for ( int pos = 0; pos < vlen; ) begin

         automatic int pos_start = pos;
         int run_size;

         // Advance until a 0 is found.
         //
         while ( vector[pos] == 1 && pos < vlen ) pos++;

         // Note how many 1's were skipped (the run size).
         //
         run_size = pos - pos_start;

         if ( run_size > mr_len_so_far ) mr_len_so_far = run_size;

         // Advance until a 1 is found.
         //
         while ( vector[pos] == 0 && pos < vlen ) pos++;

      end

      mr_len = mr_len_so_far;

   end

endmodule

//////////////////////////////////////////////////////////////////////////////
/// Testbench

module testmr();

   localparam int bits = 5;
   localparam int vect_len = 1 << bits - 1;

   logic [vect_len-1:0] vector;
   wire logic [bits-1:0] maxrun[3];

   max_run_behav #(vect_len,bits) mr_b(maxrun[0],vector);
   //  maxrun16_top mr(maxrun[1],vector);
   maxrunn #(vect_len,bits) mrl(maxrun[2],vector);
   maxrunrectop #(vect_len,bits) mrt(maxrun[1],vector);

   initial begin

      automatic int numtests = 5000;
      automatic int errcount = 0;
      automatic int done_that[int];
      vector = 0;

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

         // Foolish use of an associative array.
         do vector = $random; while ( !done_that[vector]++ );

         #1;

         if ( maxrun[0] !== maxrun[1] )
           begin
              errcount++;
              if ( errcount < 10 )
                $display
                  ("Test %d, wrong value for input %b  %d != %d (correct)\n",
                   i, vector, maxrun[1],maxrun[0]);
           end
      end

      $display("Testbench finished %d tests, %d errors found.\n",
               numtests, errcount);

   end

endmodule

// cadence translate_on


 /// module maxrunn
//
//         Instance       Cells  Cell Area  Net Area  Total Area  Wireload
// -------------------------------------------------------------------------
// maxrunn               499      50740         0       50740    <none> (D)

//   mr_len[0]   out port                       +0   17314 F



 /// module maxrunrectop
//
//         Instance       Cells  Cell Area  Net Area  Total Area  Wireload
// -------------------------------------------------------------------------
// maxrunrectop          370      42136         0       42136    <none> (D)

//   mr_len[0]       out port                       +0    9106 F