Source

Index

# Signed Integer Quotient

Computes the signed quotient of the signed dividend and divisor, based on whether each Remainder addition/subtraction step is successful. Part of the Signed Integer Divider module. Not usable by itself.

## Ports and Constants

````default_nettype none

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

input  wire                     input_valid,
input  wire                     dividend_sign,
input  wire                     divisor_sign,

output reg                      output_valid,
output wire [WORD_WIDTH-1:0]    quotient,

input  wire                     control_valid,
input  wire                     step_ok
);

`include "clog2_function.vh"

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

initial begin
output_valid     = 1'b0;
end
```

Some basic definitions to establish our two's-complement signed representation.

```    localparam ADD = 1'b0;
localparam SUB = 1'b1;
```

We have to internally compute with one extra bit of range to match the behaviour of the Remainder calculations.

```    localparam STEP_WORD_WIDTH_LONG = STEP_WORD_WIDTH + 1;

localparam WORD_WIDTH_LONG  = WORD_WIDTH + 1;
localparam WORD_ZERO_LONG   = {WORD_WIDTH_LONG{1'b0}};
localparam WORD_ONE_LONG    = {{WORD_WIDTH_LONG-1{1'b0}},1'b1};
localparam WORD_ONES_LONG   = {WORD_WIDTH_LONG{1'b1}};
```

## Datapath

### Divisor and Dividend Signs

```    reg  divisor_sign_enable = 1'b0;

Register
#(
.WORD_WIDTH     (1),
.RESET_VALUE    (1'b0)
)
divisor_sign_storage
(
.clock          (clock),
.clock_enable   (divisor_sign_enable),
.clear          (1'b0),
.data_in        (divisor_sign),
);

reg  dividend_sign_enable = 1'b0;

Register
#(
.WORD_WIDTH     (1),
.RESET_VALUE    (1'b0)
)
dividend_sign_storage
(
.clock          (clock),
.clock_enable   (dividend_sign_enable),
.clear          (1'b0),
.data_in        (dividend_sign),
);
```

### Quotient Increment

The quotient increment is added/subtracted to/from the quotient each time we could remove the divisor from the remainder. Shift it right by 1 each calculation step, so we increment by decreasing multiples of 2 at each division step.

```    reg                         quotient_increment_enable   = 1'b0;
reg                         quotient_increment_load     = 1'b0;
wire [WORD_WIDTH_LONG-1:0]  quotient_increment_reversed;

Register_Pipeline
#(
.WORD_WIDTH     (1),
.PIPE_DEPTH     (WORD_WIDTH_LONG),
.RESET_VALUES   (WORD_ZERO_LONG)
)
quotient_increment_storage
(
.clock          (clock),
.clock_enable   (quotient_increment_enable),
.clear          (clear),
.parallel_in    (WORD_ONE_LONG),
.parallel_out   (quotient_increment_reversed),
.pipe_in        (1'b0),
// verilator lint_off PINCONNECTEMPTY
.pipe_out       ()
// verilator lint_on  PINCONNECTEMPTY
);
```

The Register_Pipeline only shifts left, so let's reverse its parallel output.

```    wire [WORD_WIDTH_LONG-1:0]  quotient_increment;

Word_Reverser
#(
.WORD_WIDTH (1),
.WORD_COUNT (WORD_WIDTH_LONG)
)
quotient_increment_shift_direction
(
.words_in   (quotient_increment_reversed),
.words_out  (quotient_increment)
);
```

### Quotient Storage

```    reg                         quotient_enable = 1'b0;
reg                         quotient_clear  = 1'b0;
wire [WORD_WIDTH_LONG-1:0]  quotient_next;

Register
#(
.WORD_WIDTH     (WORD_WIDTH_LONG),
.RESET_VALUE    (WORD_ZERO_LONG)
)
quotient_storage
(
.clock          (clock),
.clock_enable   (quotient_enable),
.clear          (quotient_clear),
.data_in        (quotient_next),
);

#(
.WORD_WIDTH_IN  (WORD_WIDTH_LONG),
.SIGNED         (1),
.WORD_WIDTH_OUT (WORD_WIDTH)
)
quotient_shorten
(
);
```

### Quotient Calculation

Add or subtract depending on the signs of the inputs. We don't need to handle backpressure at the input handshake of the `Adder_Subtractor_Binary_Multiprecision` since we don't try to start a new operation until the previous one has completed and its results stored.

```    reg quotient_add_sub = 1'b0;

always @(*) begin
end

reg  quotient_input_valid  = 1'b0;
wire quotient_output_valid;
// Veril*tor cannot quite anaylze this signals path across the hierarchy.
// This is not a synthesis bug.
// verilator lint_off UNOPTFLAT
reg  quotient_output_ready = 1'b0;
// verilator lint_on  UNOPTFLAT

#(
.WORD_WIDTH         (WORD_WIDTH_LONG),
.STEP_WORD_WIDTH    (STEP_WORD_WIDTH_LONG)
)
quotient_calc
(
.clock          (clock),
.clock_enable   (1'b1),
.clear          (clear),

.input_valid    (quotient_input_valid),
//verilator lint_off PINCONNECTEMPTY
//verilator lint_on  PINCONNECTEMPTY

.B              (quotient_increment),

.output_valid   (quotient_output_valid),

.sum            (quotient_next),
// verilator lint_off PINCONNECTEMPTY
.carry_out  (),
.carries    (),
.overflow   ()
// verilator lint_on  PINCONNECTEMPTY
);
```

## Control Path

### States and Storage

We denote state as two bits, with the following transitions: LOAD -> CALC -> DONE -> LOAD -> ... We don't handle the fourth, impossible case. The state encoding is arbitrary.

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

The state bits, from which we derive the control outputs and the internal control signals.

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

Register
#(
.WORD_WIDTH     (STATE_WIDTH),
)
state_storage
(
.clock          (clock),
.clock_enable   (1'b1),
.clear          (clear),
.data_in        (state_next),
.data_out       (state)
);
```

### Calculation Steps

Each division takes `WORD_WIDTH_LONG` steps, from `WORD_WIDTH_LONG-1` to `0`, plus one step to initially load the dividend and divisor. Thus, we need a counter of the correct width.

```    localparam STEPS_WIDTH      = clog2(WORD_WIDTH_LONG);
localparam STEPS_INITIAL    = WORD_WIDTH_LONG - 1;
localparam STEPS_ZERO       = {STEPS_WIDTH{1'b0}};
localparam STEPS_ONE        = {{STEPS_WIDTH-1{1'b0}},1'b1};
```

Count down WORD_WIDTH_LONG-1 calculation steps. Stops at zero, and reloads when leaving STATE_LOAD.

```    reg                     calculation_step_clear  = 1'b0;
reg                     calculation_step_do     = 1'b0;
wire [STEPS_WIDTH-1:0]  calculation_step;

Counter_Binary
#(
.WORD_WIDTH     (STEPS_WIDTH),
.INCREMENT      (STEPS_ONE),
.INITIAL_COUNT  (STEPS_INITIAL [STEPS_WIDTH-1:0])
)
calculation_steps
(
.clock          (clock),
.clear          (calculation_step_clear),

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

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

### Input/Output/Control Handshakes

Accept inputs when empty (after results are read out) or frehsly reset/cleared). Declare outputs valid when calculation is done. Signal a new calculation step each time the addition/subtraction is complete.

```    always @(*) begin
output_valid   = (state == STATE_DONE);
control_ready  = (state == STATE_CALC) && (quotient_output_valid == 1'b1);
end
```

### Control Events

```    reg load_inputs       = 1'b0; // When we load the dividend and divisor signs.
reg read_outputs      = 1'b0; // When we read out the quotient.
reg read_control      = 1'b0; // When we read in the calculation step status.
reg calculating       = 1'b0; // High while performing the division steps.
reg step_done         = 1'b0; // High when an add/sub completes and is ack'ed by other computations.
reg last_calculation  = 1'b0; // High during the last calculation step.

always @(*) begin
load_inputs       = (input_ready   == 1'b1) && (input_valid   == 1'b1);
read_outputs      = (output_valid  == 1'b1) && (output_ready  == 1'b1);
read_control      = (control_valid == 1'b1) && (control_ready == 1'b1);
calculating       = (state == STATE_CALC);
step_done         = (read_control == 1'b1);
last_calculation  = (read_control == 1'b1) && (calculation_step == STEPS_ZERO);
end
```

Past this point, we should not refer directly to the FSM states or inputs/outputs, but to these events which are combinations of states and signals.

### State Transitions

There is no handling of erroneous states.

```    always @(*) begin
state_next = (load_inputs       == 1'b1) ? STATE_CALC : state;
state_next = (last_calculation  == 1'b1) ? STATE_DONE : state_next;
state_next = (read_outputs      == 1'b1) ? STATE_LOAD : state_next;
end
```

### Calculation Steps Control

```    always @(*) begin
calculation_step_clear = (load_inputs == 1'b1) || (clear == 1'b1);
calculation_step_do    = (step_done   == 1'b1);
end
```

Let the Adder/Subtractor run independently, but read out its value only when the control handshake (from the Remainder module) completes. This then allows the Adder/Subtractor's input handshake to complete.

```    always @(*) begin
quotient_input_valid  = (calculating   == 1'b1);
quotient_output_ready = (control_valid == 1'b1);
end
```

### Input Storage Control

```    always @(*) begin
divisor_sign_enable  = (load_inputs == 1'b1);
dividend_sign_enable = (load_inputs == 1'b1);
end
```

### Quotient and Increment Storage Control

Store only an updated Quotient if the division step from the Remainder module was OK (could successfully remove the divisor from the dividend).

```    always @(*) begin
quotient_increment_enable = (load_inputs == 1'b1) || (step_done == 1'b1);