//# Multiprecision Binary Integer Adder/Subtractor

// A signed binary integer adder/subtractor, which does arithmetic over
// `WORD_WIDTH` words as a sequence of smaller `STEP_WORD_WIDTH` operations to
// save area and increase operating speed at the price of extra latency.

// The main use of this circuit is to avoid CAD problems which can emerge at
// large integer bit widths (e.g.: 128 bits): the area of added pipeline
// registers would become quite large, and the CAD tools can fail to retime
// them completely into the extra-wide adder logic, thus failing to reach
// a high operating frequency and slowing down the rest of the system.  *There
// are notes in the code which point out the critical paths you can expect to
// see (or not).*

// Also, if we don't need a result every cycle, regular pipelining is
// wasteful: it unnecessarily duplicates the input/output data storage, and
// makes poor use of the adder/subtractor logic (e.g.: the least-significant
// bits are used once, then sit idle for multiple cycles while the higher bits
// are computed).

// Since the result latency depends on the ratio of `WORD_WIDTH` to
// `STEP_WORD_WIDTH` and whether that ratio is a whole integer, the inputs are
// set with a ready/valid handshake, and can be updated after the output
// handshake completes.

// Addition/subtraction is selected with `add_sub`: 0 for an add (`A+B`), and
// 1 for a subtract (`A-B`). This assignment conveniently matches the
// convention of sign bits. *Note that the `overflow` bit is only meaningful
// for signed numbers. For unsigned numbers, use `carry_out` instead.*

//## Ports and Constants

`default_nettype none

module Adder_Subtractor_Binary_Multiprecision
#(
    parameter WORD_WIDTH        = 0,
    parameter STEP_WORD_WIDTH   = 0
)
(
    input   wire                        clock,
    input   wire                        clock_enable,
    input   wire                        clear,

    input   wire                        input_valid,
    output  reg                         input_ready,

    input   wire                        add_sub,    // 0/1 -> A+B/A-B
    input   wire    [WORD_WIDTH-1:0]    A,
    input   wire    [WORD_WIDTH-1:0]    B,

    output  reg                         output_valid,
    input   wire                        output_ready,

    output  wire    [WORD_WIDTH-1:0]    sum,
    output  reg                         carry_out,
    output  wire    [WORD_WIDTH-1:0]    carries,
    output  reg                         overflow
);

    initial begin
        input_ready     = 1'b1; // Ready after reset.
        output_valid    = 1'b0;
        carry_out       = 1'b0;
        overflow        = 1'b0;
    end

    `include "word_count_function.vh"
    `include "word_pad_function.vh"
    `include "clog2_function.vh"

    localparam WORD_ZERO = {WORD_WIDTH{1'b0}};

// Compute how many `STEP_WORD_WIDTH` words we will need to hold
// a `WORD_WIDTH` input. The total width may end up larger, but we will
// discard the extra bits at the end.

    localparam STEP_WORD_COUNT = word_count(WORD_WIDTH, STEP_WORD_WIDTH);
    localparam STEP_WORD_WIDTH_TOTAL = STEP_WORD_WIDTH * STEP_WORD_COUNT;

    localparam STEP_WORD_ZERO  = {STEP_WORD_WIDTH{1'b0}};
    localparam STEP_TOTAL_ZERO = {STEP_WORD_WIDTH_TOTAL{1'b0}};

// How many pad bits at the end of the last step word?  Re-adjust to zero (see
// [Word Pad](./word_pad_function.html) for why) since we don't construct
// a pad here, only index to its position in the last step word.    

    localparam PAD_WIDTH_RAW   = word_pad(WORD_WIDTH, STEP_WORD_WIDTH);
    localparam PAD_WIDTH       = (PAD_WIDTH_RAW == STEP_WORD_WIDTH) ? 0 : PAD_WIDTH_RAW;

// We must add a bit of width to the step counter to deal with the special
// case where `STEP_WORD_WIDTH` equals `WORD_WIDTH`, so the `STEP_WORD_COUNT`
// is 1, and thus the counter would be of width zero, which is impossible.
// The overhead is insignificant and grows logarithmically at worst.

    localparam STEP_COUNT_WIDTH   = clog2(STEP_WORD_COUNT) + 1;
    localparam STEP_COUNT_INITIAL = STEP_WORD_COUNT - 1;
    localparam STEP_ONE           = {{STEP_COUNT_WIDTH-1{1'b0}},1'b1};
    localparam STEP_ZERO          = {STEP_COUNT_WIDTH{1'b0}};

//## Datapath

//### Carry Bit Storage

// Set the initial `step_carry_in` into the step adder/subtractor to 1 (which
// matches the `add_sub` convention) if subtracting to complete the negation
// of the inverted `B` operand, and update it at each calculation step with the
// `step_carry_out`.  The final `carry_out` is calculated later, and depends on
// the `PAD_WIDTH`.

    reg  load_carry_initial     = 1'b0;
    reg  load_carry_step        = 1'b0;
    reg  step_carry_selected    = 1'b0;
    wire step_carry_out;
    wire step_carry_in;

    always @(*) begin
        step_carry_selected = (load_carry_initial == 1'b1) ? add_sub : step_carry_out;
    end 

    Register
    #(
        .WORD_WIDTH     (1),
        .RESET_VALUE    (1'b0)
    )
    carry_storage
    (
        .clock          (clock),
        .clock_enable   (load_carry_step),
        .clear          (1'b0),
        .data_in        (step_carry_selected),
        .data_out       (step_carry_in)
    );

//### Input Pipeline for A

// Extend A to the total width of the pipeline as a signed integer.

    wire [STEP_WORD_WIDTH_TOTAL-1:0] A_extended;

    Width_Adjuster
    #(
        .WORD_WIDTH_IN  (WORD_WIDTH),
        .SIGNED         (1),
        .WORD_WIDTH_OUT (STEP_WORD_WIDTH_TOTAL)
    )
    A_extender
    (
        .original_input     (A),
        .adjusted_output    (A_extended)
    );

// Word-reverse `A_extended` so the pipeline outputs the least significant
// step word first.

    wire [STEP_WORD_WIDTH_TOTAL-1:0] A_reversed;

    Word_Reverser
    #(
        .WORD_WIDTH (STEP_WORD_WIDTH),
        .WORD_COUNT (STEP_WORD_COUNT)
    )
    A_reverser
    (
        .words_in   (A_extended),
        .words_out  (A_reversed)
    );

// Read `A_extended` into the pipeline, and feed it out one step word at
// a time, from least to most-significant.

    reg                        load_A = 1'b0;
    wire [STEP_WORD_WIDTH-1:0] step_A;

    Register_Pipeline
    #(
        .WORD_WIDTH     (STEP_WORD_WIDTH),
        .PIPE_DEPTH     (STEP_WORD_COUNT),
        .RESET_VALUES   (STEP_TOTAL_ZERO)
    )
    A_storage
    (
        .clock          (clock),
        .clock_enable   (clock_enable),
        .clear          (1'b0),
        .parallel_load  (load_A),
        .parallel_in    (A_reversed),
        // verilator lint_off PINCONNECTEMPTY
        .parallel_out   (),
        // verilator lint_on  PINCONNECTEMPTY
        .pipe_in        (STEP_WORD_ZERO),
        .pipe_out       (step_A)
    );

//### Input Pipeline for B

// Invert `B` if subtracting. The `step_carry_in` is already correctly
// initialized to 1 to make it into a negation.

// We do the negation of `B` in this module instead of using the built-in
// negation logic in the `Adder_Subtractor_Binary` sub-module because I could
// not predict what logic would synthesize when subtracting, which is
// internally be implemented as `A+((~B)+1)-carry_in`. So to be sure the logic
// synthesizes predictably, I decided to remove `carry_in` as an input to this
// module and use the internal `carry_storage` as part of the negation of `B`
// when subtracting, which then implements as `A+((~B)+step_carry_in)`.

    reg [WORD_WIDTH-1:0] B_selected = WORD_ZERO;

    always @(*) begin
        B_selected = (add_sub == 1'b1) ? ~B : B;
    end

// Extend B to the total width of the pipeline as a signed integer.

    wire [STEP_WORD_WIDTH_TOTAL-1:0] B_extended;

    Width_Adjuster
    #(
        .WORD_WIDTH_IN  (WORD_WIDTH),
        .SIGNED         (1),
        .WORD_WIDTH_OUT (STEP_WORD_WIDTH_TOTAL)
    )
    B_extender
    (
        .original_input     (B_selected),
        .adjusted_output    (B_extended)
    );

// Word-reverse `B_extended` so the pipeline outputs the least significant step
// word first.

    wire [STEP_WORD_WIDTH_TOTAL-1:0] B_reversed;

    Word_Reverser
    #(
        .WORD_WIDTH (STEP_WORD_WIDTH),
        .WORD_COUNT (STEP_WORD_COUNT)
    )
    B_reverser
    (
        .words_in   (B_extended),
        .words_out  (B_reversed)
    );

// Read `B_extended` into the pipeline , and feed it out one step word at
// a time, from least to most-significant.

    reg                        load_B = 1'b0;
    wire [STEP_WORD_WIDTH-1:0] step_B;

    Register_Pipeline
    #(
        .WORD_WIDTH     (STEP_WORD_WIDTH),
        .PIPE_DEPTH     (STEP_WORD_COUNT),
        .RESET_VALUES   (STEP_TOTAL_ZERO)
    )
    B_storage
    (
        .clock          (clock),
        .clock_enable   (clock_enable),
        .clear          (1'b0),
        .parallel_load  (load_B),
        .parallel_in    (B_reversed),
        // verilator lint_off PINCONNECTEMPTY
        .parallel_out   (),
        // verilator lint_on  PINCONNECTEMPTY
        .pipe_in        (STEP_WORD_ZERO),
        .pipe_out       (step_B)
    );

//### Step Adder Logic 

// *NOTE: the `step_carry_in` and `step_carry_out` storage and wiring was
// defined earlier.*

// We cannot use the built-in `overflow` as if there are pad bits at the MSB
// positions in the last step word, they will falsely disable the overflow and
// carry-out bits. So we calculate the `overflow` and `carry_out` later in
// this module, and the unused logic in `Adder_Subtractor_Binary` will
// optimize away.

// The adder carry-chain should *never* be the critical path. If so, reduce
// `STEP_WORD_WIDTH` as needed.

    wire [STEP_WORD_WIDTH-1:0] step_sum;
    wire [STEP_WORD_WIDTH-1:0] step_carries;

    Adder_Subtractor_Binary
    #(
        .WORD_WIDTH (STEP_WORD_WIDTH)
    )
    step_adder
    (
        .add_sub    (1'b0), // 0/1 -> A+B/A-B
        .carry_in   (step_carry_in),
        .A          (step_A),
        .B          (step_B),
        .sum        (step_sum),
        .carry_out  (step_carry_out),
        .carries    (step_carries),
        // verilator lint_off PINCONNECTEMPTY
        .overflow   ()
        // verilator lint_on  PINCONNECTEMPTY
    );

//### Output Pipeline for Sum

// Store the `step_sum` word-by-word, then word-reverse it back to the
// expected order so we can extract the least-significant `WORD_WIDTH` subset
// which contains the result we want.

    reg                              load_step_sum = 1'b0;
    wire [STEP_WORD_WIDTH_TOTAL-1:0] sum_reversed;
    wire [STEP_WORD_WIDTH_TOTAL-1:0] sum_restored;

    Register_Pipeline
    #(
        .WORD_WIDTH     (STEP_WORD_WIDTH),
        .PIPE_DEPTH     (STEP_WORD_COUNT),
        .RESET_VALUES   (STEP_TOTAL_ZERO)
    )
    output_sum
    (
        .clock          (clock),
        .clock_enable   (load_step_sum),
        .clear          (1'b0),
        .parallel_load  (1'b0),
        .parallel_in    (STEP_TOTAL_ZERO),
        .parallel_out   (sum_reversed),
        .pipe_in        (step_sum),
        // verilator lint_off PINCONNECTEMPTY
        .pipe_out       ()
        // verilator lint_on  PINCONNECTEMPTY
    );

    Word_Reverser
    #(
        .WORD_WIDTH (STEP_WORD_WIDTH),
        .WORD_COUNT (STEP_WORD_COUNT)
    )
    sum_reverser
    (
        .words_in   (sum_reversed),
        .words_out  (sum_restored)
    );

    Width_Adjuster
    #(
        .WORD_WIDTH_IN  (STEP_WORD_WIDTH_TOTAL),
        .SIGNED         (1),
        .WORD_WIDTH_OUT (WORD_WIDTH)
    )
    sum_truncator
    (
        .original_input     (sum_restored),
        .adjusted_output    (sum)
    );

//### Output Pipeline for Carries

// Store the carries word-by-word, then word-reverse them back to the expected
// order so we can extract the least-significant `WORD_WIDTH` subset which
// contains the result we want.

    reg                              load_step_carries = 1'b0;
    wire [STEP_WORD_WIDTH_TOTAL-1:0] carries_reversed;
    wire [STEP_WORD_WIDTH_TOTAL-1:0] carries_restored;

    Register_Pipeline
    #(
        .WORD_WIDTH     (STEP_WORD_WIDTH),
        .PIPE_DEPTH     (STEP_WORD_COUNT),
        .RESET_VALUES   (STEP_TOTAL_ZERO)
    )
    output_carries
    (
        .clock          (clock),
        .clock_enable   (load_step_carries),
        .clear          (1'b0),
        .parallel_load  (1'b0),
        .parallel_in    (STEP_TOTAL_ZERO),
        .parallel_out   (carries_reversed),
        .pipe_in        (step_carries),
        // verilator lint_off PINCONNECTEMPTY
        .pipe_out       ()
        // verilator lint_on  PINCONNECTEMPTY
    );

    Word_Reverser
    #(
        .WORD_WIDTH (STEP_WORD_WIDTH),
        .WORD_COUNT (STEP_WORD_COUNT)
    )
    carries_reverser
    (
        .words_in   (carries_reversed),
        .words_out  (carries_restored)
    );

    Width_Adjuster
    #(
        .WORD_WIDTH_IN  (STEP_WORD_WIDTH_TOTAL),
        .SIGNED         (0),
        .WORD_WIDTH_OUT (WORD_WIDTH)
    )
    carries_truncator
    (
        .original_input     (carries_restored),
        .adjusted_output    (carries)
    );

//### Overflow and Carry-Out Flags

// We gather together the carries from the final `step_sum` (the most
// significant word of the result) and the final `step_carry_in` (which now
// holds the last `step_carry_out`), and select the correct carries, based on
// the amount of padding in the last step word, to compute the `carry_out` and
// the `overflow`. We have to handle all cases, including when there is no
// padding when `STEP_WORD_WIDTH` exactly divides `WORD_WIDTH`.

// The wiring here is constant and only uses 2 bits, so it will never be
// a critical path, regardless of the width of `all_carries`.

    localparam ALL_CARRIES_WIDTH = 1 + STEP_WORD_WIDTH;
    localparam ALL_CARRIES_ZERO  = {ALL_CARRIES_WIDTH{1'b0}};

    reg [ALL_CARRIES_WIDTH-1:0] all_carries   = ALL_CARRIES_ZERO;
    reg                         last_carry_in = 1'b0;

    always @(*) begin
        all_carries     = {step_carry_in, carries_restored [STEP_WORD_WIDTH_TOTAL-1 -: STEP_WORD_WIDTH]};
        last_carry_in   = all_carries [STEP_WORD_WIDTH - PAD_WIDTH - 1];
        carry_out       = all_carries [STEP_WORD_WIDTH - PAD_WIDTH];
        overflow        = (carry_out != last_carry_in);
    end

//## Control Logic

//### States and Storage 

// We accept inputs in `STATE_LOAD`, compute in
// `STATE_CALC`, and present the output in `STATE_DONE`. Once the results are
// read out, we return to `STATE_LOAD`.

// *NOTE: The state encoding is arbitrary. Also, control from `state_storage`
// to the input/output pipelines will tend to be the critical path as
// `WORD_WIDTH` gets larger due to physical distance and routing congestion,
// depending on the target device and CAD tool.*

    localparam STATE_WIDTH                   = 2;
    localparam [STATE_WIDTH-1:0] STATE_LOAD  = 2'b00;
    localparam [STATE_WIDTH-1:0] STATE_CALC  = 2'b01;
    localparam [STATE_WIDTH-1:0] STATE_DONE  = 2'b11;
    localparam [STATE_WIDTH-1:0] STATE_ERROR = 2'b10; // Never reached.

    wire [STATE_WIDTH-1:0] state;
    reg  [STATE_WIDTH-1:0] state_next = STATE_LOAD;

    Register
    #(
        .WORD_WIDTH     (STATE_WIDTH),
        .RESET_VALUE    (STATE_LOAD)
    )
    state_storage
    (
        .clock          (clock),
        .clock_enable   (clock_enable),
        .clear          (clear),
        .data_in        (state_next),
        .data_out       (state)
    );

//### Calculation Steps

// Count down the calculation steps until zero, which is how long we stay in
// `STATE_CALC`.

    reg                         step_do     = 1'b0;
    reg                         step_load   = 1'b0;
    wire [STEP_COUNT_WIDTH-1:0] step;

    Counter_Binary
    #(
        .WORD_WIDTH     (STEP_COUNT_WIDTH),
        .INCREMENT      (STEP_ONE),
        .INITIAL_COUNT  (STEP_COUNT_INITIAL [STEP_COUNT_WIDTH-1:0])
    )
    calc_steps
    (
        .clock          (clock),
        .clear          (clear),

        .up_down        (1'b1), // 0/1 --> up/down
        .run            (step_do),

        .load           (step_load),
        .load_count     (STEP_COUNT_INITIAL [STEP_COUNT_WIDTH-1:0]),

        .carry_in       (1'b0),
        // verilator lint_off PINCONNECTEMPTY
        .carry_out      (),
        .carries        (),
        .overflow       (),
        // verilator lint_on  PINCONNECTEMPTY

        .count          (step)
    );

    reg step_done = 1'b0;

    always @(*) begin
        step_done = (step == STEP_ZERO);
    end

//### Input/Output Handshaking

    reg input_handshake_done  = 1'b0;
    reg output_handshake_done = 1'b0;

    always @(*) begin
        input_ready  = (state == STATE_LOAD);
        output_valid = (state == STATE_DONE);
        input_handshake_done  = (input_ready  == 1'b1) && (input_valid  == 1'b1);
        output_handshake_done = (output_ready == 1'b1) && (output_valid == 1'b1);
    end

//### Control Events

    reg input_load  = 1'b0; // Load of input operation and operands.
    reg calculating = 1'b0; // High while doing the calculation steps.
    reg last_calc   = 1'b0; // High during the last calculation step.
    reg output_read = 1'b0; // When the result is read out.

    always @(*) begin
        input_load  = (state == STATE_LOAD) && (input_handshake_done  == 1'b1);
        calculating = (state == STATE_CALC);
        last_calc   = (state == STATE_CALC) && (step_done             == 1'b1);
        output_read = (state == STATE_DONE) && (output_handshake_done == 1'b1);
    end

// After this point, there should be no reference to inputs, outputs, or
// states. All control logic must be expressed in terms of control events.

//### State Transitions

    always @(*) begin
        state_next = (input_load  == 1'b1) ? STATE_CALC : state;
        state_next = (last_calc   == 1'b1) ? STATE_DONE : state_next;
        state_next = (output_read == 1'b1) ? STATE_LOAD : state_next;
    end

//### Datapath Control Signals 

    always @(*) begin
        load_carry_initial  = (input_load  == 1'b1);
        load_carry_step     = (input_load  == 1'b1) || (calculating == 1'b1);
        load_A              = (input_load  == 1'b1);
        load_B              = (input_load  == 1'b1);
        load_step_sum       = (calculating == 1'b1);
        load_step_carries   = (calculating == 1'b1);
        step_do             = (calculating == 1'b1);
        step_load           = (input_load  == 1'b1);
    end

endmodule