/* * 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 [14:0] r2, i2, ri, diff; wire [15:0] twocdiff; wire r2sign, i2sign, risign, dsign; wire [15:0] bigsum; wire bigsum_ovf, rin_ovf, iin_ovf, throwaway; reg [12:0] xd, yd; reg rd, id; 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 + i2; assign bigsum_ovf = bigsum[15] | bigsum[14]; assign rin_ovf = rd; assign iin_ovf = id; assign twocdiff = r2 - i2; assign diff = twocdiff[15] ? -twocdiff : twocdiff; assign dsign = twocdiff[15]; always @ (posedge clk) begin xd <= x; yd <= y; xsd <= xsign; ysd <= ysign; xout <= xd; yout <= yd; xsout <= xsd; ysout <= ysd; ibaild <= ibail; curiterd <= icuriter; rd <= r[13] | r[14]; id <= i[13] | i[14]; if (xsd ^ dsign) begin if (diff > xd) begin rout <= diff - xd; rsout <= dsign; end else begin rout <= xd - diff; rsout <= xsd; end end else begin rout <= diff + xd; rsout <= xsd; end if (ysd ^ risign) begin if (ri > yd) begin iout <= ri - yd; isout <= risign; end else begin iout <= yd - ri; 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 | rin_ovf | iin_ovf)) 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]); 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]); 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 typeA(.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