Subversion Repositories cr_div

`timescale 1ns / 1ps

// ============================================================================

//        __

//   \\__/ o\    (C) 2012-2013  Robert Finch, Stratford

//    \  __ /    All rights reserved.

//     \/_//     robfinch<remove>@opencores.org

//       ||

//

// Cached Reciprocal Divider

// - Allows divides to be performed in three clock cycles by storing the

//   reciprocal of the divisor in a cache, then using a multiply for

//   subsequent divides.

//

// This source file is free software: you can redistribute it and/or modify 

// it under the terms of the GNU Lesser General Public License as published 

// by the Free Software Foundation, either version 3 of the License, or     

// (at your option) any later version.                                      

//                                                                          

// This source file 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, see <http://www.gnu.org/licenses/>.    

//

// ============================================================================

//

module cr_div(rst, clk, addr, start, a, b, q, r, done);

parameter IDLE = 3'd1;

parameter RECIP = 3'd2;

parameter RECIP1 = 3'd3;

parameter DONE = 3'd4;

input rst;

input clk;

input [31:0] addr;

input start;

input [31:0] a;

input [31:0] b;

output [31:0] q;

output [31:0] r;

output done;

reg [2:0] state;

reg [31:0] bcache [0:63];         // 'b' is the cache tag

reg [31:0] recip_cache [0:63];    // cache of reciprocals

wire [63:0] prod = recip_cache[addr[7:2]] * a;

reg [31:0] q,r;

reg [7:0] cnt;

wire cnt_done = cnt==8'd0;

assign done = state==DONE;

wire b0 = b <= r;

wire [31:0] r1 = b0 ? r - b : r;

always @(posedge clk)

if (rst) begin

        state <= IDLE;

end

else begin

if (!cnt_done)

        cnt <= cnt - 8'd1;

case(state)

IDLE:

        if (start) begin

                // Note: we are calculating the inverse as a fraction less than one, so

                // we start by placing the dividend directly into the remainder field

                // rather than the quotient field as for a normal divide. We can save

                // 32 clock cycles this way. We know there would just be 32 leading

                // zeros because the fraction is less than one.

                q <= 32'd0;

                r <= 32'd1;

                if (b==1) begin

                        q <= a;

                        r <= 0;

                        state <= DONE;

                end

                // Here is what speeds things up, if we find the reciprocal cached, the

                // quotient is returned right away after a multiply.

                else if (b==bcache[addr[7:2]]) begin

                        q <= prod[63:32];

                        state <= DONE;

                end

                else

                        state <= RECIP;

                cnt <= 8'd33;

        end

// This state computes the reciprocal and caches it if the reciprocal isn't in

// the cache already.

RECIP:

        if (!cnt_done) begin

                q <= {q[30:0],b0};

                r <= {r1,q[31]};

        end

        else begin

                bcache[addr[7:2]] <= b;

                recip_cache[addr[7:2]] <= q;

                state <= RECIP1;

        end

// State to compute the quotient using the newly cached reciprocal.

RECIP1:

        begin

                q <= prod[63:32];

                state <= DONE;

        end

// Compute the remainder. You may not want to since it's a resource hog - it

// takes an additional multiply and subtract. The remainder is often easily

// calculated by program code rather than hardware.

DONE:

        begin

        $display("==========================");

        $display("a=%d,b=%d",a,b);

        $display("q=%d,r=%d",q,a - b * q);

        $display("rc[%h]=%d",addr[7:2],recip_cache[addr[7:2]]);

        $display("==========================");

        r <= a - b * q;

        state <= IDLE;

        end

endcase

end

endmodule

module cr_div_tb();

reg rst;

reg clk;

reg start;

wire done;

wire [31:0] q,r;

reg [31:0] a,b;

reg [7:0] cnt;

reg [7:0] cycles;

reg [31:0] addr,oaddr;

initial begin

        clk = 1;

        rst = 0;

        #100 rst = 1;

        #100 rst = 0;

        #100 start = 1;

        #150 start = 0;

end

always #10 clk = ~clk;  //  50 MHz

cr_div u1

(

        .rst(rst),

        .clk(clk),

        .start(start),

        .addr(addr),

        .a(a),

        .b(b),

        .q(q),

        .r(r),

        .done(done)

);

always @(posedge clk)

if (rst) begin

addr <= 32'd0;

cycles <= 8'h0;

end

else begin

start <= 1'b0;

cycles <= cycles + 8'd1;

oaddr <= addr;

if (done)

        addr <= addr + 32'd4;

if (addr != oaddr) begin

        start <= 1'b1;

        cycles <= 8'h00;

end

case(addr)

10'h00:  begin a = 32'd10005; b = 32'd27; end

10'h04:  begin a = 32'd9999; b = 32'd21; end

10'h08:  begin a = 32'd9999; b = 32'd0; end

10'h0C:  begin a = 32'hFFFFFFFF; b = 32'd1; end

10'h10: begin a = 32'h36969; b = 27; end

10'h14:  begin a = 32'd0; b = 32'hFFFFFFFF; end

10'h18:  begin a = 32'd1; b = 32'hFFFFFFFF; end

10'h1C:  begin a = 32'hFFFFFFFF; b = 32'd2; end

10'h100:begin a = 32'd3721; b = 32'd27; end                      // <- this one simulates a loop (hits the same cache address as h00

default:        begin a = 32'd999; b = 32'd99;  end

endcase

$display("addr=%h,a=%d,b=%d,q=%d,r=%d,done=%d,cycles=%d",addr,a,b,q,r,done,cycles);

end

endmodule