///  LSU EE 4755 -- Fall 2020 -- Digital Design / HDL
//
/// Verilog Notes -- Synthesis of Combinational Logic: Structural

/// Under Construction

/// Contents
//
// Inference of Expressions
// Inference of Non-Arithmetic Operators
// Synthesis of The Conditional Operator, Index Op
// Inference of Comparison Operators

/// References

// :SV12: IEEE 1800-2012 -- The SystemVerilog Standard
// :SV17: IEEE 1800-2017 -- The SystemVerilog Standard
//        https://ieeexplore.ieee.org/document/8299595/
//        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.

//  Step-by-Step Genus Instructions (For this Course)
//        https://www.ece.lsu.edu/v/proc.html#synthesis
//
//  Genus HDL Modeling Guide -- Access from Within lsu.edu Only.
//        https://www.ece.lsu.edu/v/s/genus_hdlmod.pdf
//
//  Links to More Documentation and References
//        https://www.ece.lsu.edu/v/ref.html

////////////////////////////////////////////////////////////////////////////////
/// Inference of Expressions
//
// :Def: Expression
// An arrangement of operators and operands which returns a result, as
// defined by some language, such as C++11 or SystemVerilog 2012.
//
// :Sample: x = a + b * ( c - d );
//
// We should be familiar with expressions in many computer languages.
//

// :Def: Operator Syntax
// The rules for using the operator in code written in the language.

// :Def: Operator Semantics
// A description of how an operator transforms its operands into a result.
//
// :Sample: int a,b; ... a + b;
// Semantics of +: Result is signed integer sum, overflow ignored.

/// SystemVerilog Operator Treatment -- Simulation
//
//  SystemVerilog 2012 defines operators and expressions in Chapter 12.
//  Syntax and semantics must (shall!) follow the standard.
//  Semantics exactly described.

/// SystemVerilog Operator Treatment -- Synthesis
//
//  Each synthesis program defines a synthesizable subset.
//
//
//    Synthesizable Subset Described In
//      Genus HDL Modeling Guide
//        See Chapter 4.

// :Def: Synthesizable Operator
// An operator that's synthesizable by a particular synthesis program.

/// Arithmetic Operators v. Other Operators
//
//  For logical operators it is easy to infer hardware,
//   for example  assign x = a && b; would be inferred as an AND gate.
//
//  Arithmetic operators inference is not so simple because of:
//   Operand width (number of bits).
//   Operand type (signed v. unsigned).
//   Need to provide optimization flexibility.
//
//  Inference of arithmetic and non-arithmetic operators covered in
//  this set.

////////////////////////////////////////////////////////////////////////////////
/// Inference of Arbitrary Expressions

/// Steps
//
//  - Use precedence and association to determine order.
//  - Draw diagram.

// :Example:
//
// Show inferred hardware for the expression in the module below.

module arb_exp
( output uwire [7:0] x,
input uwire [8:0] a,
input uwire [6:0] b, c,
input uwire [2:0] e, f );

assign x = a + b * c << ( e + f );

/// Based on precedence and association:
//
// i1 = b*c;
// i2 = a + i1;
// i3 = e + f;
// x = i2 << i3;
//
// Note: i1, i2, and i3 are not actually declared anywhere ..
// .. they are used to make clear the order in which the operations
//    are performed ..
// .. and as labels in the diagram below.

endmodule

//

////////////////////////////////////////////////////////////////////////////////
/// Inference of Logical Operators
///

/// Boolean Two-Operand Logical Operators
//
//  &&,  ||  (AND, OR)
//  <->, ->  (XNOR (equivalence), implication)  Note: not implemented.
//
//  - Both arguments are Boolean types.
//  - Result is a 1-bit unsigned integer.
//  - Arguments are converted into Boolean types if necessary.
//
//  All these can be inferred in a straightforward manner.
//  Synthesizes into the gate that you would expect.

module example_bool_and_or
(output uwire x, y,
input uwire a, b);

assign x = a && b;
assign y = a || b;

endmodule

//

/// Conversion from Integer Types to Boolean Type
//
//  Integer Types
//   Set l020 will cover types in detail.
//   An example of an integer type is: uwire [7:0] a;
//
//  Conversion value a to Boolean:
//    If a == 0, Boolean value is False.
//    If a != 0, Boolean value is True.
//    If a contains x's (undefined), Boolean value is x.
//
//  Synthesis of Integer-to-Boolean Conversion
//
//    For course assignments, assume that an n-bit integer
//     is converted to a Boolean with an n-input OR gate.

// :Example:
//
// Convert 4-bit inputs a and b into Booleans, then perform AND operation.

module example_conversion
(output uwire x,
input uwire [3:0] a, b);

assign x = a && b;
//
// Note that a and b are 4 bits each and that x is 1 bit.

endmodule

//

/// Bitwise Logical Operators
//
//  &, |, ^,  (AND, OR, XOR)
//
//  - Both arguments are bit vectors.
//  - Result is a bit vector at least as large as larger operand.
//
//  All these can be inferred in a straightforward manner.
//  Synthesizes into a collection of gates, one gate for each bit.

module example_bitw_and
(output uwire [3:0] x,
input uwire [3:0] a, b);

assign x = a & b;

endmodule

//

module example_bitw_and_or_xor
(output uwire [3:0] x, y, z,
input uwire [3:0] a, b);

assign x = a & b;
assign y = a | b;
assign z = a ^ b;

endmodule

/// Reduction Operators
//
//  Reduction operators convert multiple bits into one bit.
//
//  &, ~&, |, ~|, ^, ~^
//
//  - There is one argument, a bit vector.
//  - In effect the operator is placed between adjacent bits ..
//    .. for example, &x is equivalent to
//    .. x[0] && x[1] && x[2] ..
//    .. for x declared: logic x[0:2].
//  - The result is one bit.
//
//  All these can be inferred in a straightforward manner.
//  Synthesizes into a w-input gate, where w is the width of the operand.

module example_redlop
(input uwire [3:0] a,
output uwire x, y, z );

assign x = & a;   // Equivalent to x = a[3] && a[2] && a[1] && a[0];
assign y = | a;   // Reduction OR, same as conversion to Boolean.
assign z = ^ a;   // Reduction XOR, true if odd number of bits 1.

endmodule

/// Shift
//
//  <<,  >>   // Logical Shift Operators
//  <<<, >>>  // Arithmetic Shift Operators
//
//  All these can be inferred in a straightforward manner.

/// Concatenation
//
//  {}
//
//  Nothing to synthesize.

////////////////////////////////////////////////////////////////////////////////
/// Synthesis of The Conditional Operator
///

/// The Conditional Operator (Review)
//
// Similar to the conditional operator in C, C++, C++11, ...
//
// :Sample:  x = s ? a : b;
// Equivalent to:  if ( s ) x = a; else x = b;

/// The conditional operator (s?a:b) is synthesized as a multiplexor.
//
// :Sample: assign x = s ? a : b;
// Two-input mux, x is control, a and b are data inputs.

module conditional_review
( output int x, input logic s, input uwire [7:0] c, d );

int a, b;

initial begin

a = 2;
b = 3;

// The two lines below do the same thing:
//
x = s ? a : b;
if ( s ) x = a; else x = b;

// The two lines below do the same thing:
//
x = c < d ? a : b + 1;
if ( c < d ) x = a; else x = b+1;

// The first line and the following lines do the same thing.
//
x = c < d ? a : c < 2 * d ? b : b + 2;
if ( c < d )
begin
x = a;
end
else
begin
if ( c < 2 * d ) x = b; else x = b + 2;
end
//
// Did you take the time to figure this out?

end

endmodule

// :Example:
//
// Use of conditional operator to describe a two-input multiplexor.

module mux2
( output uwire [7:0] x,
input uwire s,
input uwire [7:0] a, b );

assign x = s == 0 ? a : b;

endmodule

//

// Note that a two-input multiplexor can be implemented using
// three gates per bit:

//

// The following code containing chained conditional operators. This
// can be synthesized as three 2-input multiplxors or, because s is
// being tested for the sequence 0, 1, 3, a single multiple-input
// multiplexor.
//
// :Example:
//
// Use of conditional operator to describe a four-input multiplexor.

module mux4
( output uwire [7:0] x,
input uwire [1:0] s,
input uwire [7:0] a0, a1, a2, a3 );

assign x =  s==0 ? a0 :
s==1 ? a1 :
s==2 ? a2 : a3;

endmodule

// Inferred as three 2-input multiplexors.
//

// Inferred as one 4-input multiplexor.
//

////////////////////////////////////////////////////////////////////////////////
/// Synthesis of The Index Operator
///

/// Index Operator, []
//
//  :Sample:  a[5] // Access element 5 of a.
//
//  Used to access elements of a vector or array.
//  Some people are surprised to learn that "[]" is an operator.

/// The index operator [] is inferred as a mux.
//
//   Consider a[s] where
//     s is n-bit vector
//     a is a 2^n-element array of vectors.

module mux16
( output uwire [7:0] x,
input uwire [4:1] s,
input uwire [15:0][7:0] a );

assign      x = a[s];

endmodule

module muxn
#( int w = 16,
int n = 4,
int lgn = \$clog2(n) )
( output uwire [w:1] x,
input uwire [lgn:1] s,
input uwire [w:1] a[n] );

assign      x = a[s];

endmodule

////////////////////////////////////////////////////////////////////////////////
/// Inference of Widths of Arithmetic Expressions
///

/// Expression Width
//
//  The number of bits used for an intermediate value.
//  Beware: Verilog can use fewer bits than you assume.

/// Widths (Size)
//
//  :Def: Self-Determined Expression Context
//  Size determined by expression itself, not the surrounding context.
//
//  :Example:
//
//  x = a << E;   // E is in a self-determined context (by def of << operator).
//                // Therefore size of E does not depend on a or x.
//
//
//  :Def: Context-Determined Expression Context
//  Size determined by expression itself, and by how or where it is used.
//
//  :Example:
//
//  x = E + b;   // E is a context-determined operand (and so is b).
//               // Size of E is maximum of sizes of x, E, and b.

//  :Example:
//
//  x = E << b;  // E is a context-determined operand.
//               // Size of E depends on size of x.

/// Motivating Example
//
// :Example:
//
// The less than module below seems to be returning the wrong result.
// Why?

module less_than( output uwire lt, input uwire [6:0] a, b, amt );

assign lt = a + b < amt;

endmodule

module less_than_tryout;
logic [6:0] a, b, amt;
uwire lt;

less_than lt1(lt, a, b, amt);

initial begin
b = 35;
amt = 100;

for ( int av = 80; av < 120; av += 10 )
begin
a = av;
#1;
\$write("Expression %d + %d < %d is: %s\n",
a, b, amt, lt ? "true" : "false");
end
end

// Expression  80 +  35 < 100 is: false
// Expression  90 +  35 < 100 is: false
// Expression 100 +  35 < 100 is:  true
// Expression 110 +  35 < 100 is:  true

endmodule

module example
( output uwire [4:0] x1, x2,
input uwire [3:0] a, b,
input uwire [6:0] c );

assign x1 = ( a + b ) + c;
//
// Operands of + are context-determined,
//  therefore width of adder inputs and outputs will be max(4,5,7) = 7;
// x1 gets 5 LSB of result, the rest is discarded.

assign x2 = a + b << c;
//
// c is self-determined, so its size stays at 7 (which is overkill).
// Size of others is max(4,5) = 5.
// Shifter's data input and outputs are 5 bits, shift amt is 7 bits.

endmodule

// :Example:
//
// Determine the bit widths of the intermediate values of expressions
// in the module below. See 2017 Midterm Exam Problem 4.
//
module wqf
#( int w = 16 )
( output uwire signed [2*w-1:0] rad,
input uwire [w-1:0] a, b, c );

always_comb begin

rad = b*b - 4 * a * c;

end

endmodule

//

module sqrt #(int w=16)(output uwire [w:1] x, input uwire [w:1] a);
// Warning: not usually synthesizable.
assign x = a**0.5;
endmodule

////////////////////////////////////////////////////////////////////////////////
/// Inference of Comparison Operators
///

/// Comparison
//
//  Ordinary comparison:  ==, !=,  >,   >=, <, <=
//  Four-state compare:  ===, !==, ==?, !=?
//
//  - Result of all comparisons is one bit.
//  - Several argument types possible: bit vectors, reals.
//
//
//  Synthesis programs will only work with ordinary comparisons of int types.
//  Typically inferred into a library module.
//  Magnitude comparison, such as >, <, can be implemented using subtraction.

module example_comparison
(output uwire x,
input uwire [7:0] a, b);

assign x = a > b;

endmodule

/// Arithmetic Operators
//
//  +, -, /, *, **, %
//
//  - Multiple argument types, eg, signed bit vector, integer, real.
//  - Result type and width depends on operands.
//
//  Synthesis programs (so far) limit operator and operand combinations ..
//  .. for example the exponent of ** must be a constant.
//  Typically inferred into a library module.
//
/// Be Careful
//
//  - Pay attention to rules on bit widths.
//  - Pay attention to rules on signed/unsigned integers.
//  - Don't impede optimization by limiting widths or by touching bits.

module example_arithmetic
(output uwire [8:0] x,
input uwire [7:0] a, b);

assign x = a + b;
//
// Note: because of x's size, a+b performed at width of 9 bits.

endmodule

// :Example: Example of how helping hurts.
//
// Goal is to compute (a+b)/2  ...
// ... but using formula a + (b-a)/2.
//
// We would like efficient hardware with a + (b-a)/2.
//
// If arithmetic expression written cleanly ..
// .. synthesis program will transform a+(b-a)/2 to (a+b)/2.
//
// If arithmetic expression mixed with logic ..
// .. synthesis program may not be able to transform expression.

module example_avg_helping_hurt
( output uwire [7:0] avg,
input uwire [7:0] a, b );

uwire [7:0]   a_inv = ~a;
uwire [7:0]   minus_a = a_inv + 1;

uwire logic [7:0] diff = b + minus_a;
assign avg = diff[7:1] + a;

endmodule

module example_avg_good
( output uwire signed [7:0] avg,
input uwire signed [7:0] a, b );

assign avg = a + ( b - a ) / 2;

endmodule

module example_avg_best
( output uwire signed [7:0] avg,
input uwire signed [7:0] a, b );

assign avg = ( 0 + a + b ) / 2;

endmodule

/// Pay Attention To
//
//  Data type and number of bits of inputs.
//  Data type and number of bits of outputs.
//
//  Changes in the number of bits.
//  Interpretation of integer as signed or unsigned.

module bool_v_1bit
( output uwire y1, output uwire y2,
input uwire [7:0] a, b );

// Consider
//
assign y1 = a && b;
//
//  The && is defined for 1-bit operands.
//

assign y2 = a & b;
//
// Note: y2's size should match a and b's.

endmodule