//
// Copyright (c) 1999 Thomas Coonan (tcoonan@mindspring.com)
//
//    This source code is free software; you can redistribute it
//    and/or modify it in source code form under the terms of the GNU
//    General Public License as published by the Free Software
//    Foundation; either version 2 of the License, or (at your option)
//    any later version.
//
//    This program is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU General Public License for more details.
//
//    You should have received a copy of the GNU General Public License
//    along with this program; if not, write to the Free Software
//    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
//
//
// Integer Multicycle Divide circuit (divide a 16-bit number by a 16-bit number in 16 cycles).
//
// a / b = q with remainder r
//
// Where a is 16-bits,
// Where b is 16 bits
//
// Module is actually parameterized if you want other widths.
//
// *** Test the ranges of values for which you'll use this.  For example, you
//     can't divide FFFF by FF without underflow (overflow?).  Mess with
//     the testbench.  You may need to widen some thing.  ***
//
// The answer is 16-bits and the remainder is also 16-bits.
// After the start pulse, the module requires 16 cycles to complete.
// The q/r outputs stay the same until next start pulse.
// Start pulse should be a single cycle.
// Division by zero results in a quotient equal to FFFF and remainder equal to 'a'.
//
// 
// Written by tom coonan.
//
// Notes:
//    - This ain't fancy.  I wanted something straight-forward quickly.  Go study
//      more elaborate algorithms if you want to optimize area or speed.  If you
//      have an isolated divide and can spare N cycles for N bits; this may meet your needs.
//    - You might want to think more about the sizes of things.  I wanted a basic estimate
//      of gates plus I specifically needed to divide 16-bits (not even full range)
//      by 8-bits.
//    - Handle divide by zero at higher level..
//    - I needed a remainder so I could easily to truncate and rounding stuff,
//      but remove this to save gates if you don't need a remainder.
//    - This is about 800 asic gates (0.25um, Standard Cell, 27Mhz).  27Mhz
//      is my system clock and NOT the maximum it can go..
//    - I tried to keep everything parameterized by N, but I only worked through
//      the N=16 case because that's what I needed...
//
module div16 (clk, resetb, start, a, b, q, r, done);

parameter N = 16;	// a/b = q remainder r, where all operands are N wide.

input		clk;
input		resetb;	// Asynchronous, active low reset.
input		start;	// Pulse this to start the division.
input [N-1:0]	a;	// This is the number we are dividing (the dividend)
input [N-1:0]	b;	// This is the 'divisor'
output [N-1:0]	q;	// This is the 'quotient'
output [N-1:0]	r;	// Here is the remainder.
output		done;	// Will be asserted when q and r are available.

// Registered q
reg [N-1:0]	q;
reg		done;

// Power is the current 2^n bit we are considering.  Power is a shifting
// '1' that starts at the highest power of 2 and goes all the way down
// to ...00001  Shift this until it is zero at which point we stop.
//
reg [N-1:0]	power;

// This is the accumulator.  We are start with the accumulator set to 'a' (the dividend).
// For each (divisor*2^N) term, we see if we can subtract (divisor*2^N) from the accumulator.
// We subtract these terms as long as adding in the term doesn't cause the accumulator
// to exceed a.  When we are done, whatever is left in the accumulator is the remainder.
//
reg [N-1:0]	accum;

// This is the divisor*2^N term.  Essentually, we are taking the divisor ('b'), initially
// shifting it all the way to the left, and shifting it 1 bit at a time to the right.
//
reg [(2*N-1):0]	bpower;

// Remainder will be whatever is left in the accumulator.
assign r = accum;

// Do this addition here for resource sharing.  
// ** Note that 'accum' is N bits wide, but bpower is 2*N-1 bits wide **
//
wire [2*N-1:0] accum_minus_bpower = accum - bpower;

always @(posedge clk or negedge resetb) begin
   if (~resetb) begin
      q <= 0;
      accum <= 0;
      power <= 0;
      bpower <= 0;
      done <= 0;
   end
   else begin
      if (start) begin
         // Reinitialize the divide circuit.
         q      <= 0;
         accum  <= a; // Accumulator initially gets the dividend.  
         power[N-1] <= 1'b1; // We start with highest power of 2 (which is a '1' in MSB)
         bpower <= b << N-1; // Start with highest bpower, which is (divisor * 2^(N-1))
         done <= 0;
      end
      else begin
         // Go until power is zero.
         //
         if (power != 0) begin
            //
            // Can we add this divisor*2^(power) to the accumulator without going negative?
            // Just test the MSB of the subtraction.  If it is '1', then it must be negative.
            //
            if ( ~accum_minus_bpower[2*N-1]) begin
               // Yes!  Set this power of 2 in the quotieny and
               // then actually comitt to the subtraction from our accumulator.
               //
               q     <= q | power;
               accum <= accum_minus_bpower;
            end
            // Regardless, always go to next lower power of 2.
            //
            power  <= power >> 1;
            bpower <= bpower >> 1;
         end
         else begin
            // We're done.  Set done flag.
            done <= 1;
         end
      end
   end
end
endmodule

// synopsys translate_off
module test_div16;
reg		clk;
reg		resetb;
reg		start;
reg [15:0]	a;
reg [15:0]	b;
wire [15:0]	q;
wire [15:0]	r;
wire		done;

integer		num_errors;

div16 div16 (
   .clk(clk),
   .resetb(resetb),
   .start(start),
   .a(a),
   .b(b),
   .q(q),
   .r(r),
   .done(done)
);

initial begin
   num_errors = 0;
   
   start = 0;
   
   // Wait till reset is completely over.
   #200;
   
   // Do some divisions where divisor is constrained to 8-bits and dividend is 16-bits
   $display ("16-bit Dividend, 8-bit divisor");
   repeat (25) begin
      do_divide ($random, $random & 255);
   end
   
   // Do some divisions where divisor is constrained to 12-bits and dividend is 16-bits
   $display ("\n16-bit Dividend, 12-bit divisor");
   repeat (25) begin
      do_divide ($random, $random & 4095);
   end
   
   // Do some divisions where both divisor and dividend is 16-bits
   $display ("\n16-bit Dividend, 16-bit divisor");
   repeat (25) begin
      do_divide ($random, $random);
   end
   
   // Special cases
   $display ("\nSpecial Cases:");
   do_divide (16'hFFFF,  16'hFFFF); // largest possible quotient
   do_divide (312,  1); // divide by 1
   do_divide (  0, 42); // divide 0 by something else
   do_divide (312,  0); // divide by zero

   // That's all.  Summarize the test.
   if (num_errors === 0) begin
      $display ("\n\nPASSED. -  There were %0d Errors.", num_errors);
   end
   else begin
      $display ("\n\nFAILED - There were %0d Errors.", num_errors);
   end
   
   $finish;
end

task do_divide;
   input [15:0] arga;
   input [15:0] argb;
   
   begin
      a = arga;
      b = argb;
      @(posedge clk);
      #1 start = 1;
      @(posedge clk);
      #1 start = 0;
      while (~done) @(posedge clk);
      #1;
      
      $display ("Circuit: %0d / %0d = %0d, rem = %0d \t\t......... Reality: %0d, rem = %0d", arga, argb, q, r, a/b, a%b);
      if (b !== 0) begin
         if (q !== a/b) begin
            $display ("   Error!  Unexpected Quotient\n\n");
            num_errors = num_errors + 1;
         end
         if (r !== a % b) begin
            $display ("   Error!  Unexpected Remainder\n\n");
            num_errors = num_errors + 1;
         end
      end
   end
endtask

initial begin
   clk = 0;
   forever begin
      #10 clk = 1;
      #10 clk = 0;
   end
end

initial begin
   resetb = 0;
   #133 resetb = 1;
end

initial begin
   $dumpfile ("test_div16.vcd");
   $dumpvars (0,test_div16);   
end

endmodule