// *Logical* multiplication circuit
// Assignment 6 for COMP231, ??/??/01
// by Julian Graham

// First, we create some basic gates so we can be nice and abstract when
// we build our combinational circuits...

module and_gate (in1, in2, out);
	input in1, in2;
	output out;

	assign out = in1 & in2;
endmodule

module or_gate (in1, in2, out);
        input in1, in2;
        output out;

        assign out = in1 | in2;
endmodule

module xor_gate (in1, in2, out);
	input in1, in2;
	output out;

	assign out = in1 ^ in2;
endmodule

// Perhaps the following isn't actually a "bitwise" AND gate.
// What it does is AND all of the bits of input #1 with the single bit
// in input #2 and send out the result.

module bitwise_and_gate (in1, in2, out);
	parameter N = 10;
	input [N - 1 : 0] in1;
	input in2;
	output [N - 1 : 0] out;
	
	and_gate and1 (in1 [0], in2, out [0]);
	and_gate and2 (in1 [1], in2, out [1]);
	and_gate and3 (in1 [2], in2, out [2]);
	and_gate and4 (in1 [3], in2, out [3]);
	and_gate and5 (in1 [4], in2, out [4]);
	and_gate and6 (in1 [5], in2, out [5]);
	and_gate and7 (in1 [6], in2, out [6]);
	and_gate and8 (in1 [7], in2, out [7]);
	and_gate and8 (in1 [8], in2, out [8]);
	and_gate and9 (in1 [N - 1], in2, out [N - 1]);
endmodule

// This is perhaps the part I'm most ashamed of.  All it does is take 2
// N-bit inputs and return their 2N-bit concatenation.  It saves me the
// trouble of writing a 20-bit adder so that I can add "y" only to the
// top N bits of "z."

module concatenator (in1, in2, out);
	parameter N = 10;
	input [N - 1 : 0] in1;
	input [N - 1 : 0] in2;
        output [(2 * N) - 1 : 0] out;
        
        assign out = {in1, in2};
endmodule

// The main component of our friend, the adder.  Given two inputs, it
// produces a sum and a carry bit.

module half_adder (in1, in2, sum, carry);
	input in1, in2;
	output sum, carry;

	xor_gate xor1 (in1, in2, sum);
	and_gate and1 (in1, in2, carry);
endmodule

// Here's our adder circuit.  Given an input and a carry_bit, it uses 2
// half adders to return a sum and a bit to carry out of the addition.

module adder (in1, in2, carry_in, sum, carry_out);
	input in1, in2, carry_in;
	output sum, carry_out;
        wire input_sum, input_carry, carry_carry;

	half_adder ha1 (in1, in2, input_sum, input_carry);
        half_adder ha2 (input_sum, carry_in, sum, carry_carry);
        or_gate or1 (input_carry, carry_carry, carry_out);
endmodule

// Here's where we put our adder circuit to good use: given 2 9-bit
// inputs, it returns a 10-bit sum.  The adder we use for the lowest bits
// is created with a line held low to indicate that we're not carrying
// anything in from the right.  We use this adder for our two's complement
// module.

module ninebit_adder (in1, in2, out);
	parameter N = 9;
	input [(N - 1) : 0] in1;
	input [(N - 1) : 0] in2;
	output [N : 0] out;

	wire [N - 1 : 0] carry_bits;

        adder adder_1 (in1 [0], in2 [0], 1'b0, out [0], carry_bits [0]);
        adder adder_2 (in1 [1], in2 [1], carry_bits [0], out [1], carry_bits [1]);
        adder adder_3 (in1 [2], in2 [2], carry_bits [1], out [2], carry_bits [2]);
        adder adder_4 (in1 [3], in2 [3], carry_bits [2], out [3], carry_bits [3]);
        adder adder_5 (in1 [4], in2 [4], carry_bits [3], out [4], carry_bits [4]);
        adder adder_6 (in1 [5], in2 [5], carry_bits [4], out [5], carry_bits [5]);
        adder adder_7 (in1 [6], in2 [6], carry_bits [5], out [6], carry_bits [6]);
        adder adder_8 (in1 [7], in2 [7], carry_bits [6], out [7], carry_bits [7]);
        adder adder_9 (in1 [8], in2 [8], carry_bits [7], out [8], carry_bits [8]);
        assign out [9] = carry_bits [8];
endmodule

// Just a 10-bit relative of our 9-bit adder.  This one gets used to add
// the bits of "y" to the high 10 bits of "z," should the low bit of "z"
// be "1."

module tenbit_adder (in1, in2, out);
	parameter N = 10;
	input [N - 1 : 0] in1;
	input [N - 1 : 0] in2;
	output [N : 0] out;
	
	wire [N - 1 : 0] carry_bits;

	adder adder_1 (in1 [0], in2 [0], 1'b0, out [0], carry_bits [0]);
	adder adder_2 (in1 [1], in2 [1], carry_bits [0], out [1], carry_bits [1]);
	adder adder_3 (in1 [2], in2 [2], carry_bits [1], out [2], carry_bits [2]);
	adder adder_4 (in1 [3], in2 [3], carry_bits [2], out [3], carry_bits [3]);
	adder adder_5 (in1 [4], in2 [4], carry_bits [3], out [4], carry_bits [4]);
	adder adder_6 (in1 [5], in2 [5], carry_bits [4], out [5], carry_bits [5]);
	adder adder_7 (in1 [6], in2 [6], carry_bits [5], out [6], carry_bits [6]);
	adder adder_8 (in1 [7], in2 [7], carry_bits [6], out [7], carry_bits [7]);
	adder adder_9 (in1 [8], in2 [8], carry_bits [7], out [8], carry_bits [8]);
	adder adder_10 (in1 [9], in2 [9], carry_bits [8], out [9], carry_bits [9]);
        assign out [10] = carry_bits [9];
endmodule

// A 10-bit shifter for the multiplication algorithm.  Shifts right with
// control bit set to "1," left with "0."

module shifter (in, out, control_bit);
	parameter N = 20;
	input [N - 1 : 0] in;
	input control_bit;
	output [N - 1 : 0] out;	

	assign out [0] = (control_bit & in [1]);
	assign out [1] = (control_bit & in [2]) | (~(control_bit) & in [0]);
	assign out [2] = (control_bit & in [3]) | (~(control_bit) & in [1]);
	assign out [3] = (control_bit & in [4]) | (~(control_bit) & in [2]);
	assign out [4] = (control_bit & in [5]) | (~(control_bit) & in [3]);
	assign out [5] = (control_bit & in [6]) | (~(control_bit) & in [4]);
	assign out [6] = (control_bit & in [7]) | (~(control_bit) & in [5]);
	assign out [7] = (control_bit & in [8]) | (~(control_bit) & in [6]);
	assign out [8] = (control_bit & in [9]) | (~(control_bit) & in [7]);
	assign out [9] = (control_bit & in [10]) | (~(control_bit) & in [8]);
	assign out [10] = (control_bit & in [11]) | (~(control_bit) & in [9]);
	assign out [11] = (control_bit & in [12]) | (~(control_bit) & in [10]);
	assign out [12] = (control_bit & in [13]) | (~(control_bit) & in [11]);
	assign out [13] = (control_bit & in [14]) | (~(control_bit) & in [12]);
	assign out [14] = (control_bit & in [15]) | (~(control_bit) & in [13]);
	assign out [15] = (control_bit & in [16]) | (~(control_bit) & in [14]);
	assign out [16] = (control_bit & in [17]) | (~(control_bit) & in [15]);
	assign out [17] = (control_bit & in [18]) | (~(control_bit) & in [16]);
	assign out [18] = (control_bit & in [19]) | (~(control_bit) & in [17]);
	assign out [N - 1] = (~(control_bit) & in [18]);
endmodule

// Here's where the action happens!  It may look confusing, but here's how
// it works: We want to simulate a sequential circuit using hardware,
// which operates naturally in parallel.  We do this by chaining a bunch
// modules together in a sequential fashion!  First, we create the means
// to do one step of the algorithm:  We take the low bit of "z" and AND it
// with each bit in "y" (in2, in this case), and add the result to the
// high N bits of "z."  If the low bit is "0," this addition has no
// effect, since the 0 cancels out all the bits in "y."  If it's "1," the
// result is that "y" gets added.  Then we use a concatenator module to
// join our new top 10 bits with the old low 10 bits to form our new
// "z."
//
// So, using 4 instantiated modules, we've done 1 step!  To do all 10
// steps, we use wires to feed the output of one set of modules
// into the next until we're done.  Seems to me like it works, even if
// it is a bit hard on the eyesight (and the processor cycles on condor).

module mult (in1, in2, out);
	parameter N = 10;
	input [N - 1 : 0] in1;
	input [N - 1 : 0] in2;
	output [(2 * N) - 1 : 0] out;

	wire [N - 1 : 0] addend1; wire [N - 1 : 0] addend2;
	wire [N - 1 : 0] addend3; wire [N - 1 : 0] addend4;
	wire [N - 1 : 0] addend5; wire [N - 1 : 0] addend6;
	wire [N - 1 : 0] addend7; wire [N - 1 : 0] addend8;
	wire [N - 1 : 0] addend9; wire [N - 1 : 0] addend10;
        wire [N - 1 : 0] addend11;

	wire [N : 0] sum1; wire [N : 0] sum2; wire [N : 0] sum3;
	wire [N : 0] sum4; wire [N : 0] sum5; wire [N : 0] sum6;
	wire [N : 0] sum7; wire [N : 0] sum8; wire [N : 0] sum9;
        wire [N : 0] sum10; wire [N : 0] sum11;

	wire [(2 * N) - 1 : 0] shifted1; wire [(2 * N) - 1 : 0] shifted2;
	wire [(2 * N) - 1 : 0] shifted3; wire [(2 * N) - 1 : 0] shifted4;
	wire [(2 * N) - 1 : 0] shifted5; wire [(2 * N) - 1 : 0] shifted6;
	wire [(2 * N) - 1 : 0] shifted7; wire [(2 * N) - 1 : 0] shifted8;
	wire [(2 * N) - 1 : 0] shifted9; wire [(2 * N) - 1 : 0] shifted10;
        wire [(2 * N) - 1 : 0] shifted11;

	wire [(2 * N) - 1 : 0] subtotal1; wire [(2 * N) - 1 : 0] subtotal2;
	wire [(2 * N) - 1 : 0] subtotal3; wire [(2 * N) - 1 : 0] subtotal4;
	wire [(2 * N) - 1 : 0] subtotal5; wire [(2 * N) - 1 : 0] subtotal6;
	wire [(2 * N) - 1 : 0] subtotal7; wire [(2 * N) - 1 : 0] subtotal8;
	wire [(2 * N) - 1 : 0] subtotal9; wire [(2 * N) - 1 : 0] subtotal10;
        wire [(2 * N) - 1 : 0] subtotal11;

	concatenator concat1 (10'b0000000000, in1, subtotal1);

        bitwise_and_gate and1 (in2, subtotal1 [0], addend1);
        tenbit_adder adder1 (addend1, subtotal1 [(2 * N) - 1 : N], sum1);
        concatenator concat2 (sum1 [N - 1 : 0], subtotal1 [N - 1 : 0], subtotal2);

	shifter shift2 (subtotal2, shifted2, 1'b1);
	bitwise_and_gate and2 (in2, shifted2 [0], addend2);
	tenbit_adder adder2 (addend2, shifted2 [(2 * N) - 1 : N], sum2);
	concatenator concat3 (sum2 [N - 1 : 0], shifted2 [N - 1 : 0], subtotal3);

	shifter shift3 (subtotal3, shifted3, 1'b1);
	bitwise_and_gate and3 (in2, shifted3 [0], addend3);
	tenbit_adder adder3 (addend3, shifted3 [(2 * N) - 1 : N], sum3);
	concatenator concat4 (sum3 [N - 1 : 0], shifted3 [N - 1 : 0], subtotal4);

	shifter shift4 (subtotal4, shifted4, 1'b1);
	bitwise_and_gate and4 (in2, shifted4 [0], addend4);
	tenbit_adder adder3 (addend4, shifted4 [(2 * N) - 1 : N], sum4);
	concatenator concat5 (sum4 [N - 1 : 0], shifted4 [N - 1 : 0], subtotal5);

	shifter shift5 (subtotal5, shifted5, 1'b1);
	bitwise_and_gate and5 (in2, shifted5 [0], addend5);
	tenbit_adder adder4 (addend5, shifted5 [(2 * N) - 1 : N], sum5);
	concatenator concat6 (sum5 [N - 1 : 0], shifted5 [N - 1 : 0], subtotal6);

	shifter shift6 (subtotal6, shifted6, 1'b1);
	bitwise_and_gate and6 (in2, shifted6 [0], addend6);
	tenbit_adder adder5 (addend6, shifted6 [(2 * N) - 1 : N], sum6);
	concatenator concat7 (sum6 [N - 1 : 0], shifted6 [N - 1 : 0], subtotal7);

	shifter shift7 (subtotal7, shifted7, 1'b1);
	bitwise_and_gate and7 (in2, shifted7 [0], addend7);
	tenbit_adder adder6 (addend7, shifted7 [(2 * N) - 1 : N], sum7);
	concatenator concat8 (sum7 [N - 1 : 0], shifted7 [N - 1 : 0], subtotal8);

	shifter shift8 (subtotal8, shifted8, 1'b1);
	bitwise_and_gate and8 (in2, shifted8 [0], addend8);
	tenbit_adder adder7 (addend8, shifted8 [(2 * N) - 1 : N], sum8);
	concatenator concat9 (sum8 [N - 1 : 0], shifted8 [N - 1 : 0], subtotal9);

	shifter shift9 (subtotal9, shifted9, 1'b1);
	bitwise_and_gate and9 (in2, shifted9 [0], addend9);
	tenbit_adder adder8 (addend9, shifted9 [(2 * N) - 1 : N], sum9);
        concatenator concat10 (sum9 [N - 1 : 0], shifted9 [N - 1 : 0], subtotal10);

        shifter shift10 (subtotal10, shifted10, 1'b1);
        bitwise_and_gate and10 (in2, shifted10 [0], addend10);
        tenbit_adder adder9 (addend10, shifted10 [(2 * N) - 1 : N], sum10);
        concatenator concat11 (sum10 [N - 1 : 0], shifted10 [N - 1 : 0], subtotal11);

        shifter shift11 (subtotal11, out, 1'b1);
        bitwise_and_gate and11 (in2, shifted11 [0], addend11);
        tenbit_adder adder10 (addend11, shifted11 [(2 * N) - 1 : N], sum11);
        concatenator concat12 (sum11 [N - 1 : 0], shifted11 [N - 1 : 0], out); 
endmodule

// A two's complement module for handling negative numbers.  A "1" in the
// control bit indicates a negative, and the appropriate actions are
// taken.  We use a 9-bit adder here to add the requisite bit.

module twos_comp (in, control_bit, out);
	parameter N = 9;
	input [N - 1 : 0] in;
	input control_bit;
	output [N : 0] out;
	
	wire [N - 1 : 0] subtotal;
	wire [N : 0] result;

	xor_gate xor1 (in [0], control_bit, subtotal [0]);
	xor_gate xor1 (in [1], control_bit, subtotal [1]);
	xor_gate xor1 (in [2], control_bit, subtotal [2]);
	xor_gate xor1 (in [3], control_bit, subtotal [3]);
	xor_gate xor1 (in [4], control_bit, subtotal [4]);
	xor_gate xor1 (in [5], control_bit, subtotal [5]);
	xor_gate xor1 (in [6], control_bit, subtotal [6]);
	xor_gate xor1 (in [7], control_bit, subtotal [7]);
	xor_gate xor1 (in [8], control_bit, subtotal [8]);

	ninebit_adder adder1 ({8'b00000000, control_bit}, subtotal, result); 

        assign out = {control_bit, result [N - 1 : 0]};
endmodule

// Our main program, which creates instantiations of our wonderful modules
// and sets the registers according to our "clock" ticks.

module main_program;
	parameter N = 9;
	reg [N - 1 : 0] x; reg [N - 1 : 0] y;
	reg control_bit_x; reg control_bit_y;

	wire [N : 0] mult_x; 
	wire [N : 0] mult_y;
        wire [(2 * N) + 1 : 0] result;
        wire [N : 0] product;

	twos_comp twos1 (x, control_bit_x, mult_x);
        twos_comp twos2 (y, control_bit_y, mult_y);

        mult mult1 (mult_x, mult_y, result);
        assign product = result [N : 0]; 

	initial begin
                #1 x = 5; y = 9; control_bit_x = 0; control_bit_y = 0;
                #1 x = 5; y = 7; control_bit_x = 0; control_bit_y = 1;
                #1 x = 8; y = 15; control_bit_x = 1; control_bit_y = 1;
                #1 x = 50; y = 6; control_bit_x = 0; control_bit_y = 0;
                #1 x = 40; y = 7; control_bit_x = 0; control_bit_y = 1;
	end
        initial begin
                 $monitor ("%d * %d = %b (positive decimal %d)", x, y, product, product);
        end
endmodule