//# 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 Adder_Subtractor_Binary #( .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; Adder_Subtractor_Binary #( .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