//
// 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\nSUCCESS.  There were %0d Errors.", num_errors);
   end
   else begin
      $display ("\n\nFAILURE!!  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


[ [ [ 'module',
      'div16',
      '(',
      [['clk'], ['resetb'], ['start'], ['a'], ['b'], ['q'], ['r'], ['done']],
      ')',
      ';'],
    [ ['parameter', ['N', '=', '16'], ';'],
      ['input', 'clk', ';'],
      ['input', 'resetb', ';'],
      ['input', 'start', ';'],
      ['input', '[', ['N'], '-', '1', ':', '0', ']', 'a', ';'],
      ['input', '[', ['N'], '-', '1', ':', '0', ']', 'b', ';'],
      ['output', '[', ['N'], '-', '1', ':', '0', ']', 'q', ';'],
      ['output', '[', ['N'], '-', '1', ':', '0', ']', 'r', ';'],
      ['output', 'done', ';'],
      ['reg', '[', ['N'], '-', '1', ':', '0', ']', ['q'], ';'],
      ['reg', ['done'], ';'],
      ['reg', '[', ['N'], '-', '1', ':', '0', ']', ['power'], ';'],
      ['reg', '[', ['N'], '-', '1', ':', '0', ']', ['accum'], ';'],
      [ 'reg',
        '[',
        '(',
        ['2', '*', ['N'], '-', '1'],
        ')',
        ':',
        '0',
        ']',
        ['bpower'],
        ';'],
      ['assign', [['r'], '=', ['accum']], ';'],
      [ 'wire',
        '[',
        '2',
        '*',
        ['N'],
        '-',
        '1',
        ':',
        '0',
        ']',
        [[['accum_minus_bpower'], '=', ['accum'], '-', ['bpower']]],
        ';'],
      [ 'always',
        ['@', '(', ['posedge', ['clk'], 'negedge', ['resetb']], ')'],
        [ 'begin',
          [ [ 'if',
              ['(', '~', ['resetb'], ')'],
              [ 'begin',
                [ [[['q'], '<=', '0'], ';'],
                  [[['accum'], '<=', '0'], ';'],
                  [[['power'], '<=', '0'], ';'],
                  [[['bpower'], '<=', '0'], ';'],
                  [[['done'], '<=', '0'], ';']],
                'end'],
              'else',
              [ 'begin',
                [ [ 'if',
                    ['(', ['start'], ')'],
                    [ 'begin',
                      [ [[['q'], '<=', '0'], ';'],
                        [[['accum'], '<=', ['a']], ';'],
                        [ [ ['power', ['[', ['N'], '-', '1', ']']],
                            '<=',
                            "1 'b 1"],
                          ';'],
                        [[['bpower'], '<=', ['b'], '<<', ['N'], '-', '1'], ';'],
                        [[['done'], '<=', '0'], ';']],
                      'end'],
                    'else',
                    [ 'begin',
                      [ [ 'if',
                          ['(', ['power'], '!=', '0', ')'],
                          [ 'begin',
                            [ [ 'if',
                                [ '(',
                                  '~',
                                  [ 'accum_minus_bpower',
                                    ['[', '2', '*', ['N'], '-', '1', ']']],
                                  ')'],
                                [ 'begin',
                                  [ [[['q'], '<=', ['q'], '|', ['power']], ';'],
                                    [ [['accum'], '<=', ['accum_minus_bpower']],
                                      ';']],
                                  'end']],
                              [[['power'], '<=', ['power'], '>>', '1'], ';'],
                              [[['bpower'], '<=', ['bpower'], '>>', '1'], ';']],
                            'end'],
                          'else',
                          ['begin', [[[['done'], '<=', '1'], ';']], 'end']]],
                      'end']]],
                'end']]],
          'end']]],
    'endmodule'],
  [ ['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'], ';'],
            [['#', '200'], ';'],
            ['$display', '(', '"16-bit Dividend, 8-bit divisor"', ')', ';'],
            [ 'repeat',
              '(',
              '25',
              ')',
              [ 'begin',
                [ [ 'do_divide',
                    '(',
                    ['$random'],
                    ['$random'],
                    '&',
                    '255',
                    ')',
                    ';']],
                'end']],
            ['$display', '(', '"\\n16-bit Dividend, 12-bit divisor"', ')', ';'],
            [ 'repeat',
              '(',
              '25',
              ')',
              [ 'begin',
                [ [ 'do_divide',
                    '(',
                    ['$random'],
                    ['$random'],
                    '&',
                    '4095',
                    ')',
                    ';']],
                'end']],
            ['$display', '(', '"\\n16-bit Dividend, 16-bit divisor"', ')', ';'],
            [ 'repeat',
              '(',
              '25',
              ')',
              [ 'begin',
                [['do_divide', '(', ['$random'], ['$random'], ')', ';']],
                'end']],
            ['$display', '(', '"\\nSpecial Cases:"', ')', ';'],
            ['do_divide', '(', "16 'h FFFF", "16 'h FFFF", ')', ';'],
            ['do_divide', '(', '312', '1', ')', ';'],
            ['do_divide', '(', '0', '42', ')', ';'],
            ['do_divide', '(', '312', '0', ')', ';'],
            [ 'if',
              ['(', ['num_errors'], '===', '0', ')'],
              [ 'begin',
                [ [ '$display',
                    '(',
                    '"\\n\\nSUCCESS.  There were %0d Errors."',
                    ['num_errors'],
                    ')',
                    ';']],
                'end'],
              'else',
              [ 'begin',
                [ [ '$display',
                    '(',
                    '"\\n\\nFAILURE!!  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']]