Divider

Design

The divider implements a radix-2 non-restoring division algorithm that computes one quotient bit per cycle.

flowchart LR
    IDLE([IDLE])
    CALC([CALC])
    DONE([DONE])

    IDLE -->|valid_in & rs2 != 0| CALC
    IDLE -->|valid_in & rs2 == 0<br/>div-by-zero| DONE
    CALC -->|count == 1| DONE
    CALC -->|count > 1<br/>next AQ| CALC
    DONE -->|implicit next valid_in| IDLE

While a higher-radix algorithm (like SRT Radix-4) could halve the latency, a classic 1-bit-per-cycle state machine was chosen. DOOM performs divisions relatively infrequently, mostly during setup, scaling, and initialization, not in inner-loop rendering, making the reduced implementation complexity favorable over the modest performance gain of a higher-radix design.

Core Algorithm

The non-restoring division operates on a 65-bit register pair AQ (33-bit accumulator + 32-bit quotient) and a 33-bit divisor register M:

assign shifted_AQ = AQ << 1;
assign next_A = AQ[64] ? (shifted_AQ[64:32] + M) : (shifted_AQ[64:32] - M);
assign next_Q0 = ~next_A[32];

At each iteration:

AQ is shifted left by one
If AQ[64] is set (remainder negative), the divisor is added; otherwise it is subtracted
The new quotient bit is the inverse of the sign of the adjusted remainder
The updated values are written back to AQ

After 32 iterations, the final remainder may need correction if it is negative (non-restoring property).

Signed & Special-Case Handling

Signed operations: For DIV and REM, operands are converted to absolute values at the start. The sign of the quotient and remainder is computed and applied at the output:

quotient_neg <= is_signed & (rs1_in[31] ^ rs2_in[31]) & (rs2_in != 0);
rem_neg <= is_signed & rs1_in[31];

Divide-by-zero: The RISC-V specification requires graceful handling rather than exceptions. When a divide-by-zero is detected, the hardware returns:

Quotient (DIV): 0xFFFFFFFF (all ones)
Remainder (REM): the original dividend value

This is implemented by bypassing the iterative computation and going directly to the DONE state with AQ loaded with the dividend.

Output Selection

The module returns either the quotient or remainder depending on the opcode:

assign result = is_rem_op ? final_remainder : final_quotient;

The is_rem_op signal is registered when the instruction is issued, so the output mux is set correctly by the time the result is ready.

Latency

Setup: 1 cycle (IDLE → CALC)
Iteration: 32 cycles (one per bit)
Pipeline stall overhead: variable, depending on when results are consumed
Total: approximately 33 clock cycles per operation

Verification

The divider testbench (rtl/tb_divider.sv) uses the same scoreboard architecture as the multiplier to handle the multi-cycle latency. Tests include:

Both signed (DIV, REM) and unsigned (DIVU, REMU) operations with random operands
Edge cases: division by zero, division with large/small dividends and divisors
Negative dividend and divisor combinations
Remainder overflow conditions
Hazard chains interleaving MUL and DIV operations

Keyboard shortcuts