`timescale 1ns / 1ps
|
`timescale 1ns / 1ps
|
// ============================================================================
|
// ============================================================================
|
// __
|
// __
|
// \\__/ o\ (C) 2010-2020 Robert Finch, Waterloo
|
// \\__/ o\ (C) 2010-2020 Robert Finch, Waterloo
|
// \ __ / All rights reserved.
|
// \ __ / All rights reserved.
|
// \/_// robfinch<remove>@finitron.ca
|
// \/_// robfinch<remove>@finitron.ca
|
// ||
|
// ||
|
//
|
//
|
// isqrt.v
|
// isqrt.v
|
// - integer square root
|
// - integer square root
|
// - uses the standard long form calc.
|
// - uses the standard long form calc.
|
// - geared towards use in an floating point unit
|
// - geared towards use in an floating point unit
|
// - calculates to WID fractional precision (double width output)
|
// - calculates to WID fractional precision (double width output)
|
//
|
//
|
//
|
//
|
// This source file is free software: you can redistribute it and/or modify
|
// 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
|
// 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
|
// by the Free Software Foundation, either version 3 of the License, or
|
// (at your option) any later version.
|
// (at your option) any later version.
|
//
|
//
|
// This source file is distributed in the hope that it will be useful,
|
// This source file is distributed in the hope that it will be useful,
|
// but WITHOUT ANY WARRANTY; without even the implied warranty of
|
// but WITHOUT ANY WARRANTY; without even the implied warranty of
|
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
// GNU General Public License for more details.
|
// GNU General Public License for more details.
|
//
|
//
|
// You should have received a copy of the GNU General Public License
|
// You should have received a copy of the GNU General Public License
|
// along with this program. If not, see <http://www.gnu.org/licenses/>.
|
// along with this program. If not, see <http://www.gnu.org/licenses/>.
|
//
|
//
|
// ============================================================================
|
// ============================================================================
|
|
|
module isqrt2(rst, clk, ce, ld, a, o, done, lzcnt);
|
module isqrt2(rst, clk, ce, ld, a, o, done, lzcnt);
|
parameter WID = 32;
|
parameter WID = 32;
|
localparam MSB = WID-1;
|
localparam MSB = WID-1;
|
parameter IDLE=3'd0;
|
parameter IDLE=3'd0;
|
parameter CALC=3'd1;
|
parameter CALC=3'd1;
|
parameter DONE=3'd2;
|
parameter DONE=3'd2;
|
input rst;
|
input rst;
|
input clk;
|
input clk;
|
input ce;
|
input ce;
|
input ld;
|
input ld;
|
input [MSB:0] a;
|
input [MSB:0] a;
|
output [WID*2-1:0] o;
|
output [WID*2-1:0] o;
|
output done;
|
output done;
|
output reg [$clog2(WID*2-1):0] lzcnt;
|
output reg [$clog2(WID*2-1):0] lzcnt;
|
|
|
reg [2:0] state;
|
reg [2:0] state;
|
reg [WID*2:0] root;
|
reg [WID*2:0] root;
|
wire [WID*2-1:0] testDiv;
|
wire [WID*2-1:0] testDiv;
|
reg [WID*2-1:0] remLo;
|
reg [WID*2-1:0] remLo;
|
reg [WID*2-1:0] remHi;
|
reg [WID*2-1:0] remHi;
|
reg gotnz;
|
reg gotnz;
|
|
|
wire cnt_done;
|
wire cnt_done;
|
assign testDiv = {root[WID*2-2:0],1'b1};
|
assign testDiv = {root[WID*2-2:0],1'b1};
|
wire [WID*2-1:0] remHiShift = {remHi[WID*2-3:0],remLo[WID*2-1:WID*2-2]};
|
wire [WID*2-1:0] remHiShift = {remHi[WID*2-3:0],remLo[WID*2-1:WID*2-2]};
|
wire doesGoInto = remHiShift >= testDiv;
|
wire doesGoInto = remHiShift >= testDiv;
|
assign o = root[WID*2:1];
|
assign o = root[WID*2:1];
|
|
|
// Iteration counter
|
// Iteration counter
|
reg [7:0] cnt;
|
reg [7:0] cnt;
|
|
|
always @(posedge clk)
|
always @(posedge clk)
|
if (rst) begin
|
if (rst) begin
|
cnt <= WID*2;
|
cnt <= WID*2;
|
remLo <= {WID*2{1'b0}};
|
remLo <= {WID*2{1'b0}};
|
remHi <= {WID*2{1'b0}};
|
remHi <= {WID*2{1'b0}};
|
root <= {WID*2+1{1'b0}};
|
root <= {WID*2+1{1'b0}};
|
lzcnt <= 8'd0;
|
lzcnt <= 8'd0;
|
gotnz <= 1'b0;
|
gotnz <= 1'b0;
|
state <= IDLE;
|
state <= IDLE;
|
end
|
end
|
else
|
else
|
begin
|
begin
|
if (ce) begin
|
if (ce) begin
|
if (!cnt_done)
|
if (!cnt_done)
|
cnt <= cnt + 8'd1;
|
cnt <= cnt + 8'd1;
|
case(state)
|
case(state)
|
IDLE: ;
|
IDLE: ;
|
CALC:
|
CALC:
|
if (!cnt_done) begin
|
if (!cnt_done) begin
|
// Shift the remainder low
|
// Shift the remainder low
|
remLo <= {remLo[WID*2-3:0],2'd0};
|
remLo <= {remLo[WID*2-3:0],2'd0};
|
// Shift the remainder high
|
// Shift the remainder high
|
remHi <= doesGoInto ? remHiShift - testDiv: remHiShift;
|
remHi <= doesGoInto ? remHiShift - testDiv: remHiShift;
|
// Shift the root
|
// Shift the root
|
root <= {root+doesGoInto,1'b0}; // root * 2 + 1/0
|
root <= {root+doesGoInto,1'b0}; // root * 2 + 1/0
|
if (doesGoInto)
|
if (doesGoInto)
|
gotnz <= 1'b1;
|
gotnz <= 1'b1;
|
else if (!gotnz)
|
else if (!gotnz)
|
lzcnt <= lzcnt + 2'd1;
|
lzcnt <= lzcnt + 2'd1;
|
end
|
end
|
else begin
|
else begin
|
cnt <= 8'h00;
|
cnt <= 8'h00;
|
state <= DONE;
|
state <= DONE;
|
end
|
end
|
DONE:
|
DONE:
|
begin
|
begin
|
if (root[WID*2]) begin
|
if (root[WID*2]) begin
|
cnt <= cnt + 8'd1;
|
cnt <= cnt + 8'd1;
|
if (cnt == 8'd6)
|
if (cnt == 8'd6)
|
state <= IDLE;
|
state <= IDLE;
|
end
|
end
|
else begin
|
else begin
|
root <= {root,1'b0};
|
root <= {root,1'b0};
|
cnt <= 8'd0;
|
cnt <= 8'd0;
|
end
|
end
|
end
|
end
|
default: state <= IDLE;
|
default: state <= IDLE;
|
endcase
|
endcase
|
if (ld) begin
|
if (ld) begin
|
cnt <= 8'd0;
|
cnt <= 8'd0;
|
state <= CALC;
|
state <= CALC;
|
remLo <= {a,32'd0};
|
remLo <= {a,32'd0};
|
remHi <= {WID*2{1'b0}};
|
remHi <= {WID*2{1'b0}};
|
root <= {WID*2+1{1'b0}};
|
root <= {WID*2+1{1'b0}};
|
gotnz <= 1'b0;
|
gotnz <= 1'b0;
|
lzcnt <= 8'd0;
|
lzcnt <= 8'd0;
|
end
|
end
|
end
|
end
|
end
|
end
|
assign cnt_done = (cnt==WID);
|
assign cnt_done = (cnt==WID);
|
assign done = state==DONE && cnt > 8'd0;
|
assign done = state==DONE && cnt > 8'd0;
|
|
|
endmodule
|
endmodule
|
|
|
|
|
module isqrt_tb();
|
module isqrt2_tb();
|
|
|
reg clk;
|
reg clk;
|
reg rst;
|
reg rst;
|
reg [31:0] a;
|
reg [31:0] a;
|
wire [63:0] o;
|
wire [63:0] o;
|
reg ld;
|
reg ld;
|
wire done;
|
wire done;
|
reg [7:0] state;
|
reg [7:0] state;
|
|
|
initial begin
|
initial begin
|
clk = 1;
|
clk = 1;
|
rst = 0;
|
rst = 0;
|
#100 rst = 1;
|
#100 rst = 1;
|
#100 rst = 0;
|
#100 rst = 0;
|
end
|
end
|
|
|
always #10 clk = ~clk; // 50 MHz
|
always #10 clk = ~clk; // 50 MHz
|
|
|
always @(posedge clk)
|
always @(posedge clk)
|
if (rst) begin
|
if (rst) begin
|
state <= 8'd0;
|
state <= 8'd0;
|
a <= 32'h912345;
|
a <= 32'h912345;
|
end
|
end
|
else
|
else
|
begin
|
begin
|
ld <= 1'b0;
|
ld <= 1'b0;
|
case(state)
|
case(state)
|
8'd0:
|
8'd0:
|
begin
|
begin
|
a <= 32'h9123456;
|
a <= 32'h9123456;
|
ld <= 1'b1;
|
ld <= 1'b1;
|
state <= 8'd1;
|
state <= 8'd1;
|
end
|
end
|
8'd1:
|
8'd1:
|
if (done) begin
|
if (done) begin
|
$display("i=%h o=%h", a, o);
|
$display("i=%h o=%h", a, o);
|
end
|
end
|
endcase
|
endcase
|
end
|
end
|
|
|
isqrt #(32) u1 (.rst(rst), .clk(clk), .ce(1'b1), .ld(ld), .a(a), .o(o), .done(done));
|
isqrt2 #(32) u1 (.rst(rst), .clk(clk), .ce(1'b1), .ld(ld), .a(a), .o(o), .done(done));
|
|
|
endmodule
|
endmodule
|
|
|
|
|
|
|
