/* Non-restoring dvision algorithm according to
   http://www.arpnjournals.org/jeas/research_papers/rp_2017/jeas_0517_6036.pdf */

module divi_pipe #(parameter NBITS_DEND=8, // number of bits of dividend
                             NBITS_SOR=8,  // number of bits of divisor
                             NBITS_Q=8)    // number of bits of quotient
            (input logic clk, rst,
             input logic  [NBITS_DEND-1:0] dend, // dividend
             input logic  [NBITS_SOR -1:0] sor,  // divisor
             output logic [NBITS_Q   -1:0] q,    // quotient
             output logic valid);                // quotient valid

  // remainders, one for each quotient bit plus one for initialization
  logic [NBITS_SOR-1:0] rem [NBITS_Q:0];
  logic [NBITS_SOR :0] rems [NBITS_Q-1:0]; // shifted remainder

  // input operando pipeline registers
  logic [NBITS_DEND-1:0] dend_ [NBITS_Q:0];  // dividend
  logic [NBITS_SOR -1:0] sor_  [NBITS_Q-1:0];  // divisor

  // output operand pipeline registers
  logic [NBITS_Q-1:0] q_ [NBITS_Q:1];   // quotient

  // get dividend and divisor from input and push them through the pipeline
  always_ff @(posedge clk)
    if(rst)
      for(int i=0; i<NBITS_Q; i++) begin
        dend_[i] = 0;
        sor_[i] = 0;
      end
    else begin
      for(int i=NBITS_Q; i>0; i--) begin
        dend_[i] = dend_[i-1]; // pass dividend to next pipeline stage
        sor_ [i] = sor_ [i-1]; // pass divisor to next pipeline stage
      end
      dend_[0] = dend; // get new dividend from input
      sor_ [0] = sor;  // get new divisor from input
   end

  // calculate remainders and quotient bits
  always_ff @(posedge clk)
    if(rst)
      for(int i=0; i<=NBITS_Q; i++) rem[i] = 0;
    else begin
      rem[0] = -sor; // calculate first remainder from input divisor
      for(int i=NBITS_Q-1; i>=0; i--) // calculate all other remainders
        // if remainder is negative, add, else subtract divisor from shifted remainder
        // (for shifted remainder see next always_comb)
        if(rem[i][NBITS_SOR-1]) rem[i+1] = rems[i] + sor_[i];
        else                    rem[i+1] = rems[i] - sor_[i];
    end

  // calculate remainders and quotient bits
  always_ff @(posedge clk)
    if(rst)
      for(int i=0; i<=NBITS_Q; i++) q_[i+1] = 0;
    else 
      for(int i=NBITS_Q-1; i>=0; i--) // calculate all other remainders
	// the inverted most significant bit of remainders are the quotient
        q_[i+1] = {i?q_[i]>>(NBITS_Q-i)     // get valid bits from pipeline stage before
                     :1'b0,                 // (zero if first pipeline stage)
                    rem[i+1][NBITS_SOR-1]}  // append MSB of remainder of next stage (invert later)
                   <<(NBITS_Q-1-i);         // shift it all in the correct position

  always_comb  // calculate all shifted remainders, those are not registers, just busses
    for(int i=0; i<NBITS_Q; i++)
      // shift in the next didivend bit
      rems[i] <= { rem[i], i<NBITS_DEND ? dend_[i][NBITS_DEND-1-i] : 1'b0 };

  always_comb q <= ~q_[NBITS_Q]; // final result is inverted from the last pipeline stage

  logic [$clog2(NBITS_Q+3)-1:0] valid_count; // count clock cycles after reset
  always_ff @(posedge clk)
    if(rst) valid_count <= 0;
    else if(valid_count < NBITS_Q+2) valid_count <= valid_count+1;
  always_comb valid <= (valid_count==NBITS_Q+2);	    
 
endmodule