/* * MandelFPGA * by Joshua Wise and Chris Lu * * An implementation of a pipelined algorithm to calculate the Mandelbrot set * in real time on an FPGA. */ `define XRES 640 `define YRES 480 `define WHIRRRRR 27 module SyncGen( input pixclk, output reg vs, hs, output reg [11:0] xout = `WHIRRRRR, yout = 0, output wire [11:0] xoutreal, youtreal, output reg border); reg [11:0] x = 0, y = 0; // Used for generating border and timing. assign xoutreal = x; assign youtreal = y; parameter XFPORCH = 16; parameter XSYNC = 96; parameter XBPORCH = 48; parameter YFPORCH = 10; parameter YSYNC = 2; parameter YBPORCH = 29; always @(posedge pixclk) begin if (x >= (`XRES + XFPORCH + XSYNC + XBPORCH)) begin if (y >= (`YRES + YFPORCH + YSYNC + YBPORCH)) y <= 0; else y <= y + 1; x <= 0; end else x <= x + 1; if (xout >= (`XRES + XFPORCH + XSYNC + XBPORCH)) begin if (yout >= (`YRES + YFPORCH + YSYNC + YBPORCH)) yout <= 0; else yout <= yout + 1; xout <= 0; end else xout <= xout + 1; hs <= (x >= (`XRES + XFPORCH)) && (x < (`XRES + XFPORCH + XSYNC)); vs <= (y >= (`YRES + YFPORCH)) && (y < (`YRES + YFPORCH + YSYNC)); border <= (x > `XRES) || (y > `YRES); end endmodule // bits: 1.12 module NaiveMultiplier( input clk, input [12:0] x, y, input xsign, ysign, output reg [12:0] out, output reg sign, 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))); sign <= xsign ^ ysign; end endmodule module Multiplier( input clk, input [12:0] x, y, input xsign, ysign, output wire [12:0] out, output wire sign, 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 xsign, ysign, input [14:0] r, i, input rsign, isign, input [7:0] ibail, icuriter, output reg [12:0] xout, yout, output reg xsout, ysout, output reg [14:0] rout, iout, output reg rsout, isout, output reg [7:0] obail, ocuriter); wire [13:0] r2, i2; wire [14:0] ri, diff; wire [15:0] twocdiff; wire r2sign, i2sign, risign, dsign; wire [13:0] bigsum; wire bigsum_ovf; reg [12: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[13]); Multiplier i2m(clk, i[12:0], i[12:0], isign, isign, i2[12:0], i2sign, i2[13]); Multiplier rim(clk, r[12:0], i[12:0], rsign, isign, ri[13:1], risign, ri[14]); assign bigsum = r2[12:0] + i2[12:0]; assign bigsum_ovf = bigsum[13] | r2[13] | i2[13]; assign twocdiff = r2 - i2; assign diff = twocdiff[15] ? -twocdiff : twocdiff; assign dsign = twocdiff[15]; wire [15:0] twocrout = xd - diff; wire [15:0] twociout = yd - ri; always @ (posedge clk) begin xd <= x; yd <= y; xsd <= xsign; ysd <= ysign; xout <= xd; yout <= yd; xsout <= xsd; ysout <= ysd; ibaild <= ibail; curiterd <= icuriter; ineedbaild <= r[13] | r[14] | i[13] | i[14]; // r^2 - i^2 + x if (xsd ^ dsign) begin if (twocrout[15]) begin // diff > xd rout <= -twocrout; rsout <= dsign; end else begin rout <= twocrout; rsout <= xsd; end end else begin rout <= diff + xd; rsout <= xsd; // xsd == dsign end // 2 * r * i + y if (ysd ^ risign) begin if (twociout[15]) begin // ri > yd iout <= -twociout; isout <= risign; end else begin iout <= twociout; isout <= ysd; end end else begin iout <= ri + yd; isout <= ysd; end // 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 | ineedbaild)) obail <= curiterd; else obail <= ibaild; ocuriter <= curiterd + 8'b1; end endmodule module Mandelbrot( input mclk, input pixclk, input [11:0] x, y, input [13: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 wire [12:0] rx, ry; wire [13: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]; wire [14: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 xsprop[`MAXOUTN:0], ysprop[`MAXOUTN:0]; wire [7:0] curiter[`MAXOUTN:0]; reg [14:0] initx, inity, 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 [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. // 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]) ? rx : (state[0]) ? stager[1] : (state[1]) ? stager[2] : 0; initi <= (state[2]) ? 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 that happens, then we're guaranteed that the // state following the current state will be 3'b100. reg lastneg; always @(negedge mclk) lastneg <= pixclk; always @(posedge mclk) begin if (lastneg && pixclk) // If a pixclk has happened, the state should be reset. state <= 3'b100; else // Otherwise, just poke it forward. case(state) 3'b001: state <= 3'b010; 3'b010: state <= 3'b100; 3'b100: state <= 3'b001; endcase // Data output handling if (state[0]) begin {red, green, blue} <= {out[0],out[3],out[6],out[1],out[4],out[7],out[2],out[5]}; end if (state[1]) begin out <= ~mb[`MAXOUTN] + colorofs; end if (state[0]) begin // PnR0 in, PnR2 out stagex[2] <= xprop[`MAXOUTN]; stagey[2] <= yprop[`MAXOUTN]; stager[2] <= mr[`MAXOUTN]; stagei[2] <= mi[`MAXOUTN]; stagexs[2] <= xsprop[`MAXOUTN]; stageys[2] <= ysprop[`MAXOUTN]; stagers[2] <= mrs[`MAXOUTN]; stageis[2] <= mis[`MAXOUTN]; stageb[2] <= mb[`MAXOUTN]; stageci[2] <= curiter[`MAXOUTN]; end if (state[2]) begin // PnR2 in, PnR1 out stagex[1] <= xprop[`MAXOUTN]; stagey[1] <= yprop[`MAXOUTN]; stager[1] <= mr[`MAXOUTN]; stagei[1] <= mi[`MAXOUTN]; stagexs[1] <= xsprop[`MAXOUTN]; stageys[1] <= ysprop[`MAXOUTN]; stagers[1] <= mrs[`MAXOUTN]; stageis[1] <= mis[`MAXOUTN]; stageb[1] <= mb[`MAXOUTN]; stageci[1] <= curiter[`MAXOUTN]; end end MandelUnit mu0( mclk, initx, inity, initxs, initys, initr, initi, initrs, initis, initb, initci, 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]) `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); endmodule module Logo( input pixclk, input [11:0] x, y, output wire enb, output wire [2:0] red, green, output wire [1:0] blue); reg [1:0] logo[8191:0]; initial $readmemb("logo.readmemb", logo); assign enb = (x < 96) && (y < 64); wire [12:0] addr = {y[5:0], x[6:0]}; wire [1:0] data = logo[addr]; assign {red, green, blue} = (data == 2'b00) ? 8'b00000000 : ((data == 2'b01) ? 8'b00011100 : ((data == 2'b10) ? 8'b11100000 : 8'b11111111)); endmodule module MandelTop( input gclk, output wire dcmok, 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 iclkbuf(.O(clk), .I(gclk)); 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) ); wire border; wire [11:0] x, y; reg [13:0] xofs = -`XRES/2, yofs = -`YRES/2; reg [5:0] slowctr = 0; reg [7:0] colorcycle = 0; wire [11:0] realx, realy; wire logoenb; 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); Logo logo(pixclk, realx, realy, logoenb, logor, logog, logob); assign {red,green,blue} = border ? 8'b00000000 : (!logooff && logoenb) ? {logor, logog, logob} : {mandelr, mandelg, mandelb}; always @(posedge vs) begin if (rst) begin xofs <= -`XRES/2; yofs <= -`YRES/2; colorcycle <= 0; end else begin if (up) yofs <= yofs + 1; else if (down) yofs <= yofs - 1; if (left) xofs <= xofs + 1; else if (right) xofs <= xofs - 1; if (slowctr == 0) colorcycle <= colorcycle + 1; end if (slowctr == 12) slowctr <= 0; else slowctr <= slowctr + 1; end endmodule