* An implementation of a pipelined algorithm to calculate the Mandelbrot set
* in real time on an FPGA.
*/
+
+/* verilator lint_off WIDTH */
`define XRES 640
`define YRES 480
-`define WHIRRRRR 27
+`define WHIRRRRR 47
+
+`define TOPBIT 13
module SyncGen(
input pixclk,
module NaiveMultiplier(
input clk,
- input [12:0] x, y,
+ input [`TOPBIT:0] x, y,
input xsign, ysign,
- output reg [12:0] out,
+ output reg [`TOPBIT:0] out,
output reg sign,
- output reg [1:0] ovf);
+ output reg ovf);
always @(posedge clk)
begin
{ovf,out} <=
- (((y[12] ? (x ) : 0) +
- (y[11] ? (x >> 1) : 0) +
- (y[10] ? (x >> 2) : 0) +
- (y[9] ? (x >> 3) : 0)) +
- ((y[8] ? (x >> 4) : 0) +
- (y[7] ? (x >> 5) : 0) +
- (y[6] ? (x >> 6) : 0)))+
- (((y[5] ? (x >> 7) : 0) +
- (y[4] ? (x >> 8) : 0) +
- (y[3] ? (x >> 9) : 0)) +
- ((y[2] ? (x >> 10): 0) +
- (y[1] ? (x >> 11): 0) +
- (y[0] ? (x >> 12): 0)));
+ ((((0) + // 15
+ (0)) + // 14
+ ((y[13] ? (x ) : 0) +
+ (y[12] ? (x[`TOPBIT:1]) : 0))) +
+ (((y[11] ? (x[`TOPBIT:2]) : 0) +
+ (y[10] ? (x[`TOPBIT:3]) : 0)) +
+ ((y[9] ? (x[`TOPBIT:4]) : 0) +
+ (y[8] ? (x[`TOPBIT:5]) : 0))))+
+ ((((y[7] ? (x[`TOPBIT:6]) : 0) +
+ (y[6] ? (x[`TOPBIT:7]) : 0)) +
+ ((y[5] ? (x[`TOPBIT:8]) : 0) +
+ (y[4] ? (x[`TOPBIT:9]) : 0))) +
+ (((y[3] ? (x[`TOPBIT:10]): 0) +
+ (y[2] ? (x[`TOPBIT:11]): 0)) +
+ ((y[1] ? (x[`TOPBIT:12]): 0) +
+ (y[0] ? (x[`TOPBIT]) : 0))));
sign <= xsign ^ ysign;
end
module Multiplier(
input clk,
- input [12:0] x, y,
+ input [`TOPBIT:0] x, y,
input xsign, ysign,
- output wire [12:0] out,
+ output wire [`TOPBIT:0] out,
output wire sign,
- output wire [1:0] overflow);
+ output wire overflow);
NaiveMultiplier nm(clk, x, y, xsign, ysign, out, sign, overflow);
endmodule
+// Yuq.
module MandelUnit(
input clk,
- input [12:0] x, y,
+ input [`TOPBIT:0] x, y,
input xsign, ysign,
- input [14:0] r, i,
+ input [`TOPBIT+2:0] r, i,
input rsign, isign,
input [7:0] ibail, icuriter,
- output reg [12:0] xout, yout,
+ output reg [`TOPBIT:0] xout, yout,
output reg xsout, ysout,
- output reg [14:0] rout, iout,
+ output reg [`TOPBIT+2:0] rout, iout,
output reg rsout, isout,
output reg [7:0] obail, ocuriter);
- wire [14:0] r2, i2, ri, diff;
- wire [15:0] twocdiff;
+ wire [`TOPBIT+1:0] r2, i2;
+ wire [`TOPBIT+2:0] ri, diff;
+ wire [`TOPBIT+3:0] twocdiff;
wire r2sign, i2sign, risign, dsign;
- wire [16:0] bigsum;
- wire bigsum_ovf, rin_ovf, iin_ovf, throwaway;
+ wire [`TOPBIT+2:0] bigsum;
+ wire bigsum_ovf;
- reg [12:0] xd, yd;
- reg rd, id;
+ reg [`TOPBIT:0] xd, yd;
+ reg ineedbaild;
reg xsd, ysd;
reg [7:0] ibaild, curiterd;
assign ri[0] = 0;
- Multiplier r2m(clk, r[12:0], r[12:0], rsign, rsign, r2[12:0], r2sign, r2[14:13]);
- Multiplier i2m(clk, i[12:0], i[12:0], isign, isign, i2[12:0], i2sign, i2[14:13]);
- Multiplier rim(clk, r[12:0], i[12:0], rsign, isign, ri[13:1], risign, {throwaway,ri[14]});
+ Multiplier r2m(clk, r[`TOPBIT:0], r[`TOPBIT:0], rsign, rsign, r2[`TOPBIT:0], r2sign, r2[`TOPBIT+1]);
+ Multiplier i2m(clk, i[`TOPBIT:0], i[`TOPBIT:0], isign, isign, i2[`TOPBIT:0], i2sign, i2[`TOPBIT+1]);
+ Multiplier rim(clk, r[`TOPBIT:0], i[`TOPBIT:0], rsign, isign, ri[`TOPBIT+1:1], risign, ri[`TOPBIT+2]);
- assign bigsum = r2 + i2;
- assign bigsum_ovf = bigsum[16] | bigsum[15] | bigsum[14];
- assign rin_ovf = rd;
- assign iin_ovf = id;
+ assign bigsum = r2[`TOPBIT+1:0] + i2[`TOPBIT+1:0];
+ assign bigsum_ovf = bigsum[`TOPBIT+2];
+
assign twocdiff = r2 - i2;
- assign diff = twocdiff[15] ? -twocdiff : twocdiff;
- assign dsign = twocdiff[15];
+ assign diff = twocdiff[`TOPBIT+3] ? -twocdiff : twocdiff;
+ assign dsign = twocdiff[`TOPBIT+3];
+
+ wire [`TOPBIT+3:0] twocrout = xd - diff;
+ wire [`TOPBIT+3:0] twociout = yd - ri;
always @ (posedge clk)
begin
ysout <= ysd;
ibaild <= ibail;
curiterd <= icuriter;
- rd <= r[13] | r[14];
- id <= i[13] | i[14];
+ ineedbaild <= r[`TOPBIT+1] | r[`TOPBIT+2] | i[`TOPBIT+1] | i[`TOPBIT+2];
+ // r^2 - i^2 + x
if (xsd ^ dsign) begin
- if (diff > xd) begin
- rout <= diff - xd;
+ if (twocrout[`TOPBIT+3]) begin // diff > xd
+ rout <= -twocrout;
rsout <= dsign;
end else begin
- rout <= xd - diff;
+ rout <= twocrout;
rsout <= xsd;
end
end else begin
rout <= diff + xd;
- rsout <= xsd;
+ rsout <= xsd; // xsd == dsign
end
+ // 2 * r * i + y
if (ysd ^ risign) begin
- if (ri > yd) begin
- iout <= ri - yd;
+ if (twociout[`TOPBIT+3]) begin // ri > yd
+ iout <= -twociout;
isout <= risign;
end else begin
- iout <= yd - ri;
+ iout <= twociout;
isout <= ysd;
end
end else begin
// If we haven't bailed out, and we meet any of the bailout conditions,
// bail out now. Otherwise, leave the bailout at whatever it was before.
- if ((ibaild == 255) && (bigsum_ovf | rin_ovf | iin_ovf))
+ if ((ibaild == 255) && (bigsum_ovf | ineedbaild))
obail <= curiterd;
else
obail <= ibaild;
input mclk,
input pixclk,
input [11:0] x, y,
- input [13:0] xofs, yofs,
+ input [`TOPBIT+1:0] xofs, yofs,
input [7:0] colorofs,
input [2:0] scale,
output reg [2:0] red, green, output reg [1:0] blue);
-`define MAXOUTN 11
+`define MAXOUTN 21
- wire [12:0] rx, ry;
- wire [13:0] nx, ny;
+ wire [`TOPBIT:0] rx, ry;
+ wire [`TOPBIT+1:0] nx, ny;
wire rxsign, rysign;
- assign nx = x + xofs;
- assign ny = y + yofs;
- assign rx = (nx[13] ? -nx[12:0] : nx[12:0]) << scale;
- assign rxsign = nx[13];
- assign ry = (ny[13] ? -ny[12:0] : ny[12:0]) << scale;
- assign rysign = ny[13];
-
+ assign nx = {2'b0,x} + {2'b0,xofs};
+ assign ny = {2'b0,y} + {2'b0,yofs};
+ assign rx = (nx[`TOPBIT+1] ? -nx[`TOPBIT:0] : nx[`TOPBIT:0]) << scale;
+ assign rxsign = nx[`TOPBIT+1];
+ assign ry = (ny[`TOPBIT+1] ? -ny[`TOPBIT:0] : ny[`TOPBIT:0]) << scale;
+ assign rysign = ny[`TOPBIT+1];
- wire [14:0] mr[`MAXOUTN:0], mi[`MAXOUTN:0];
+ wire [`TOPBIT+2:0] mr[`MAXOUTN:0], mi[`MAXOUTN:0];
wire mrs[`MAXOUTN:0], mis[`MAXOUTN:0];
wire [7:0] mb[`MAXOUTN:0];
- wire [12:0] xprop[`MAXOUTN:0], yprop[`MAXOUTN:0];
+ wire [`TOPBIT:0] xprop[`MAXOUTN:0], yprop[`MAXOUTN:0];
wire xsprop[`MAXOUTN:0], ysprop[`MAXOUTN:0];
wire [7:0] curiter[`MAXOUTN:0];
- wire [14:0] initx, inity, initr, initi;
- wire [7:0] initci, initb;
- wire initxs, initys, initrs, initis;
+ reg [`TOPBIT:0] initx, inity;
+ reg [`TOPBIT+2:0] initr, initi;
+ reg [7:0] initci, initb;
+ reg initxs, initys, initrs, initis;
// Values after the number of iterations denoted by the subscript.
- reg [14:0] stagex [2:1], stagey [2:1], stager [2:1], stagei [2:1];
+ reg [`TOPBIT:0] stagex [2:1], stagey [2:1];
+ reg [`TOPBIT+2:0] stager [2:1], stagei [2:1];
reg [7:0] stageci [2:1], stageb [2:1];
reg stagexs [2:1], stageys [2:1], stagers [2:1], stageis [2:1];
reg [2:0] state = 3'b001; // One-hot encoded state.
- assign initx = state[0] ? rx :
- state[1] ? stagex[1] :
- stagex[2];
- assign inity = state[0] ? ry :
- state[1] ? stagey[1] :
- stagey[2];
- assign initr = state[0] ? rx :
- state[1] ? stager[1] :
- stager[2];
- assign initi = state[0] ? ry :
- state[1] ? stagei[1] :
- stagei[2];
- assign initxs = state[0] ? rxsign :
- state[1] ? stagexs[1] :
- stagexs[2];
- assign initys = state[0] ? rysign :
- state[1] ? stageys[1] :
- stageys[2];
- assign initrs = state[0] ? rxsign :
- state[1] ? stagers[1] :
- stagers[2];
- assign initis = state[0] ? rysign :
- state[1] ? stageis[1] :
- stageis[2];
- assign initb = state[0] ? 8'b11111111 :
- state[1] ? stageb[1] :
- stageb[2];
- assign initci = state[0] ? 8'b00000000 :
- state[1] ? stageci[1] :
- stageci[2];
+ // States are advanced one from what they should be, so that they'll
+ // get there on the _next_ mclk.
+ always @(posedge mclk)
+ begin
+ initx <= (state[2]) ? rx :
+ (state[0]) ? stagex[1] :
+ (state[1]) ? stagex[2] : 0;
+ inity <= (state[2]) ? ry :
+ (state[0]) ? stagey[1] :
+ (state[1]) ? stagey[2] : 0;
+ initr <= (state[2]) ? {2'b0,rx} :
+ (state[0]) ? stager[1] :
+ (state[1]) ? stager[2] : 0;
+ initi <= (state[2]) ? {2'b0,ry} :
+ (state[0]) ? stagei[1] :
+ (state[1]) ? stagei[2] : 0;
+ initxs <= (state[2]) ? rxsign :
+ (state[0]) ? stagexs[1] :
+ (state[1]) ? stagexs[2] : 0;
+ initys <= (state[2]) ? rysign :
+ (state[0]) ? stageys[1] :
+ (state[1]) ? stageys[2] : 0;
+ initrs <= (state[2]) ? rxsign :
+ (state[0]) ? stagers[1] :
+ (state[1]) ? stagers[2] : 0;
+ initis <= (state[2]) ? rysign :
+ (state[0]) ? stageis[1] :
+ (state[1]) ? stageis[2] : 0;
+ initb <= (state[2]) ? 8'b11111111 :
+ (state[0]) ? stageb[1] :
+ (state[1]) ? stageb[2] : 0;
+ initci <= (state[2]) ? 8'b00000000 :
+ (state[0]) ? stageci[1] :
+ (state[1]) ? stageci[2] : 0;
+ end
reg [7:0] out;
// We detect when the state should be poked by a high negedge followed
- // by a high posedge -- if tha thappens, then we're guaranteed that the
- // state following the current state will be 100.
+ // by a high posedge -- if that happens, then we're guaranteed that the
+ // state following the current state will be 3'b100.
reg lastneg;
always @(negedge mclk)
lastneg <= pixclk;
if (lastneg && pixclk) // If a pixclk has happened, the state should be reset.
state <= 3'b100;
else // Otherwise, just poke it forward.
- state <= {state[1], state[0], state[2]};
+ case(state)
+ 3'b001: state <= 3'b010;
+ 3'b010: state <= 3'b100;
+ 3'b100: state <= 3'b001;
+ `ifdef isim
+ default: begin $display("invalid state"); $finish; end
+ `endif
+ endcase
// Data output handling
if (state[0]) begin
xprop[0], yprop[0], xsprop[0], ysprop[0],
mr[0], mi[0], mrs[0], mis[0],
mb[0], curiter[0]);
+
+`define MAKE_UNIT(name, num) \
+ MandelUnit name(mclk, \
+ xprop[(num)], yprop[(num)], xsprop[(num)], ysprop[(num)], mr[(num)], mi[(num)], mrs[(num)], mis[(num)], mb[(num)], curiter[(num)], \
+ xprop[(num)+1], yprop[(num)+1], xsprop[(num)+1], ysprop[(num)+1], mr[(num)+1], mi[(num)+1], mrs[(num)+1], mis[(num)+1], mb[(num)+1], curiter[(num)+1])
- MandelUnit mu1(mclk,
- xprop[0], yprop[0], xsprop[0], ysprop[0], mr[0], mi[0], mrs[0], mis[0], mb[0], curiter[0],
- xprop[1], yprop[1], xsprop[1], ysprop[1], mr[1], mi[1], mrs[1], mis[1], mb[1], curiter[1]);
- MandelUnit mu2(mclk,
- xprop[1], yprop[1], xsprop[1], ysprop[1], mr[1], mi[1], mrs[1], mis[1], mb[1], curiter[1],
- xprop[2], yprop[2], xsprop[2], ysprop[2], mr[2], mi[2], mrs[2], mis[2], mb[2], curiter[2]);
- MandelUnit mu3(mclk,
- xprop[2], yprop[2], xsprop[2], ysprop[2], mr[2], mi[2], mrs[2], mis[2], mb[2], curiter[2],
- xprop[3], yprop[3], xsprop[3], ysprop[3], mr[3], mi[3], mrs[3], mis[3], mb[3], curiter[3]);
- MandelUnit mu4(mclk,
- xprop[3], yprop[3], xsprop[3], ysprop[3], mr[3], mi[3], mrs[3], mis[3], mb[3], curiter[3],
- xprop[4], yprop[4], xsprop[4], ysprop[4], mr[4], mi[4], mrs[4], mis[4], mb[4], curiter[4]);
- MandelUnit mu5(mclk,
- xprop[4], yprop[4], xsprop[4], ysprop[4], mr[4], mi[4], mrs[4], mis[4], mb[4], curiter[4],
- xprop[5], yprop[5], xsprop[5], ysprop[5], mr[5], mi[5], mrs[5], mis[5], mb[5], curiter[5]);
- MandelUnit mu6(mclk,
- xprop[5], yprop[5], xsprop[5], ysprop[5], mr[5], mi[5], mrs[5], mis[5], mb[5], curiter[5],
- xprop[6], yprop[6], xsprop[6], ysprop[6], mr[6], mi[6], mrs[6], mis[6], mb[6], curiter[6]);
- MandelUnit mu7(mclk,
- xprop[6], yprop[6], xsprop[6], ysprop[6], mr[6], mi[6], mrs[6], mis[6], mb[6], curiter[6],
- xprop[7], yprop[7], xsprop[7], ysprop[7], mr[7], mi[7], mrs[7], mis[7], mb[7], curiter[7]);
- MandelUnit mu8(mclk,
- xprop[7], yprop[7], xsprop[7], ysprop[7], mr[7], mi[7], mrs[7], mis[7], mb[7], curiter[7],
- xprop[8], yprop[8], xsprop[8], ysprop[8], mr[8], mi[8], mrs[8], mis[8], mb[8], curiter[8]);
- MandelUnit mu9(mclk,
- xprop[8], yprop[8], xsprop[8], ysprop[8], mr[8], mi[8], mrs[8], mis[8], mb[8], curiter[8],
- xprop[9], yprop[9], xsprop[9], ysprop[9], mr[9], mi[9], mrs[9], mis[9], mb[9], curiter[9]);
- MandelUnit mua(mclk,
- xprop[9], yprop[9], xsprop[9], ysprop[9], mr[9], mi[9], mrs[9], mis[9], mb[9], curiter[9],
- xprop[10], yprop[10], xsprop[10], ysprop[10], mr[10], mi[10], mrs[10], mis[10], mb[10], curiter[10]);
- MandelUnit mub(mclk,
- xprop[10], yprop[10], xsprop[10], ysprop[10], mr[10], mi[10], mrs[10], mis[10], mb[10], curiter[10],
- xprop[11], yprop[11], xsprop[11], ysprop[11], mr[11], mi[11], mrs[11], mis[11], mb[11], curiter[11]);
-
+ `MAKE_UNIT(mu1, 0);
+ `MAKE_UNIT(mu2, 1);
+ `MAKE_UNIT(mu3, 2);
+ `MAKE_UNIT(mu4, 3);
+ `MAKE_UNIT(mu5, 4);
+ `MAKE_UNIT(mu6, 5);
+ `MAKE_UNIT(mu7, 6);
+ `MAKE_UNIT(mu8, 7);
+ `MAKE_UNIT(mu9, 8);
+ `MAKE_UNIT(mua, 9);
+ `MAKE_UNIT(mub, 10);
+ `MAKE_UNIT(muc, 11);
+ `MAKE_UNIT(mud, 12);
+ `MAKE_UNIT(mue, 13);
+ `MAKE_UNIT(muf, 14);
+ `MAKE_UNIT(mug, 15);
+ `MAKE_UNIT(muh, 16);
+ `MAKE_UNIT(mui, 17);
+ `MAKE_UNIT(muj, 18);
+ `MAKE_UNIT(muk, 19);
+ `MAKE_UNIT(mul, 20);
endmodule
module Logo(
endmodule
module MandelTop(
+`ifdef verilator
+ input pixclk, mclk,
+`else
input gclk, output wire dcmok,
+`endif
output wire vs, hs,
output wire [2:0] red, green, output [1:0] blue,
input left, right, up, down, rst, cycle, logooff,
input [2:0] scale);
-
-
- wire pixclk, mclk, gclk2, clk;
- wire dcm1ok, dcm2ok;
- //assign dcmok = dcm1ok && dcm2ok;
-
- //IBUFG typeA(.O(clk), .I(gclk));
- //pixDCM dcm( // CLKIN is 50MHz xtal, CLKFX_OUT is 25MHz
- // .CLKIN_IN(clk),
- // .CLKFX_OUT(pixclk),
- // .LOCKED_OUT(dcm1ok)
- // );
+`ifdef verilator
+`else
+ wire pixclk, mclk, clk;
+ wire dcm1ok, dcm2ok;
+ assign dcmok = dcm1ok && dcm2ok;
- //mandelDCM dcm2(
- // .CLKIN_IN(clk),
- // .CLKFX_OUT(mclk),
- // .LOCKED_OUT(dcm2ok)
- // );
+ IBUFG iclkbuf(.O(clk), .I(gclk));
- mainDCM dcm (
- .U1_CLKIN_IN(gclk),
- .U1_CLKDV_OUT(pixclk),
- .U2_CLKFX_OUT(mclk),
- .U2_LOCKED_OUT(dcmok)
- );
+ pixDCM dcm( // CLKIN is 50MHz xtal, CLKFX_OUT is 25MHz
+ .CLKIN_IN(clk),
+ .CLKFX_OUT(pixclk),
+ .LOCKED_OUT(dcm1ok)
+ );
+ mandelDCM dcm2(
+ .CLKIN_IN(clk),
+ .CLKFX_OUT(mclk),
+ .LOCKED_OUT(dcm2ok)
+ );
+`endif
+
wire border;
wire [11:0] x, y;
- reg [13:0] xofs = -`XRES/2, yofs = -`YRES/2;
+ reg [`TOPBIT+1:0] xofs = -`XRES/2, yofs = -`YRES/2;
reg [5:0] slowctr = 0;
reg [7:0] colorcycle = 0;
wire [11:0] realx, realy;
wire [2:0] mandelr, mandelg, logor, logog;
wire [1:0] mandelb, logob;
-
-
SyncGen sync(pixclk, vs, hs, x, y, realx, realy, border);
- Mandelbrot mandel(mclk, pixclk, x, y, xofs, yofs, cycle ? colorcycle : 0, scale, mandelr, mandelg, mandelb);
+ Mandelbrot mandel(mclk, pixclk, x, y, xofs, yofs, cycle ? colorcycle : 8'b0, scale, mandelr, mandelg, mandelb);
Logo logo(pixclk, realx, realy, logoenb, logor, logog, logob);
assign {red,green,blue} =
git.joshuawise.com / mandelfpga.git / blobdiff