Source

Index

# Signed Integer Divider by Powers of Two (Truncating Division)

While a left shift by N is always equivalent to a multiplication by 2N for both signed and unsigned binary integers, an arithmetic shift right by N is only a truncating division by 2N for positive binary integers. For negative integers, the result is a so-called modulus division, and the quotient ends up off by one in magnitude, and must be corrected by adding +1, but only if an odd number results as part of the intermediate division steps.

The implementation is based on the PowerPC method, as described in Hacker's Delight, Section 10-1, "Signed Division by a Known Power of Two": We perform the right shift and take note if any 1-bits are shifted out. If so, add one to the shifted value.

Since we divide only by powers of two, a division by zero cannot happen. (i.e.: there exists no N where 2N = 0) Also, we only allow positive exponents. A negative exponent would imply a multiplication, and that can be done directly with a left shift and not all this complication.

Note that shifting by more than the WORD_WIDTH, with an exponent of value greater than WORD_WIDTH, will give a nonsense result for negative numbers as we only have WORD_WIDTH sign bits to shift in at most.

````default_nettype none

module Divider_Integer_Signed_by_Powers_of_Two
#(
parameter WORD_WIDTH = 0
)
(
input  wire signed [WORD_WIDTH-1:0] numerator,
input  wire        [WORD_WIDTH-1:0] exponent_of_two,

output wire signed [WORD_WIDTH-1:0] quotient,
output wire signed [WORD_WIDTH-1:0] remainder
);

localparam WORD_ZERO = {WORD_WIDTH{1'b0}};
localparam WORD_ONES = {WORD_WIDTH{1'b1}};
localparam ONE       = {{WORD_WIDTH-1{1'b0}},1'b1};
```

We depend on automatic width extension of the WORD_WIDTH integer here, as doing it using a loop in an initial block is worse for linting and CAD warnings. I normally don't allow automatic width extension, but in this case it will always work, as the register will always store up to 2N-1 for a WORD_WIDTH of N, and N is always unsigned. This width extension is necessary to match port widths later on. We do have to silence the linter, though.

```    // verilator lint_off WIDTH
reg [WORD_WIDTH-1:0] WORD_WIDTH_LONG = WORD_WIDTH;
// verilator lint_on  WIDTH

localparam POSITIVE  = 1'b0;
localparam NEGATIVE  = 1'b1;
```

Prepare for a positive or negative numerator. The remainder will also make use of the sign extension.

```    reg                  numerator_sign = 1'b0;
reg [WORD_WIDTH-1:0] sign_extension = WORD_ZERO;

always @(*) begin
numerator_sign = numerator[WORD_WIDTH-1];
sign_extension = {WORD_WIDTH{numerator_sign}};
end
```

Do the initial, uncorrected division. The remainder is "short" because all its significant bits are at the left. We will shift them, with sign extension, back to the right later.

```    wire [WORD_WIDTH-1:0] uncorrected_quotient;
wire [WORD_WIDTH-1:0] short_remainder;

Bit_Shifter
#(
.WORD_WIDTH         (WORD_WIDTH)
)
uncorrected_division
(
.word_in_left       (sign_extension),
.word_in            (numerator),
.word_in_right      (WORD_ZERO),

.shift_amount       (exponent_of_two),
.shift_direction    (1'b1),             // 0/1 -> left/right

// verilator lint_off PINCONNECTEMPTY
.word_out_left      (),
// verilator lint_on  PINCONNECTEMPTY
.word_out           (uncorrected_quotient),
.word_out_right     (short_remainder)
);
```

We need to know if at any point during the shift, a 1-bit was shifted into the remainder, indicating an odd-valued intermediate result, and thus an off-by-one error in the quotient. A simple OR-reduction works because we primed that part of the shift with zeros.

```    reg odd_intermediate_result = 1'b0;

always @(*) begin
odd_intermediate_result = (short_remainder != WORD_ZERO);
end
```

Now, if the numerator was negative, and there was an odd-valued intermediate result, let's add +1 to the uncorrected_quotient to bring it back to the result a truncating division would give us.

```    reg correction = 1'b0;

always @(*) begin
correction = (numerator_sign == NEGATIVE) && (odd_intermediate_result == 1'b1);
end

#(
.WORD_WIDTH     (WORD_WIDTH)
)
quotient_correction
(
.add_sub        (1'b0),    // 0/1 -> A+B/A-B
.carry_in       (correction),
.A              (uncorrected_quotient),
.B              (WORD_ZERO),
.sum            (quotient),
// verilator lint_off PINCONNECTEMPTY
.carry_out      (),
.carries        (),
.overflow       ()
// verilator lint_on  PINCONNECTEMPTY
);
```

To shift the short remainder back to the right, we need to shift by the remainder of the distance to the right, which is WORD_WIDTH - exponent_of_two.

```    wire [WORD_WIDTH-1:0] remainder_shift_amount;

#(
.WORD_WIDTH     (WORD_WIDTH)
)
remainder_alignment
(
.add_sub        (1'b1),    // 0/1 -> A+B/A-B
.carry_in       (1'b0),
.A              (WORD_WIDTH_LONG),
.B              (exponent_of_two),
.sum            (remainder_shift_amount),
// verilator lint_off PINCONNECTEMPTY
.carry_out      (),
.carries        (),
.overflow       ()
// verilator lint_on  PINCONNECTEMPTY
);
```

Finally, let's shift the remainder significant bits back to the right, with the same sign extension as the quotient if the remainder was not zero.

```    Bit_Shifter
#(
.WORD_WIDTH         (WORD_WIDTH)
)
remainder_extension
(
.word_in_left       (sign_extension),
.word_in            (short_remainder),
.word_in_right      (WORD_ZERO),

.shift_amount       (remainder_shift_amount),
.shift_direction    (1'b1),             // 0/1 -> left/right

// verilator lint_off PINCONNECTEMPTY
.word_out_left      (),
.word_out           (remainder),
.word_out_right     ()
// verilator lint_on  PINCONNECTEMPTY
);

endmodule
```

fpgacpu.ca