`define VGA_W 160
`define VGA_H 120

module reuleaux(clk, rst_n, colour, centre_x, centre_y, diameter, start, done,
	vga_x, vga_y, vga_colour, vga_plot);

	input logic clk, rst_n, start;
	input logic [2:0] colour;
	input logic [6:0] centre_y;
	input logic [7:0] centre_x, diameter;

	output logic done, vga_plot;
	output logic [2:0] vga_colour;
	output logic [6:0] vga_y;
	output logic [7:0] vga_x;

	logic clear, ready, vga_plot_next;
	logic [2:0] octant;
	logic [7:0] offset_x, offset_y, offset_x_next, offset_y_next;
	/* One bit larger since these are signed. */
	logic signed [7:0] vga_y_next;
	logic signed [8:0] vga_x_next, crit, crit_next;

	logic [6:0] centre_y1, centre_y2, centre_y3;
	logic [7:0] centre_x1, centre_x2, centre_x3, radius;
	/* Auxiliary value for calculations. */
	logic [19:0] y_offset;

	assign vga_colour = clear ? 3'b000 : colour;
	/* Circle radius is the same as the Reuleaux triangle diameter. */
	assign radius = diameter;

	/* sqrt(3)/3 * 2^12 = 2364.826...
	 * Add 2^(N-1) before shifting by N to round to the nearest integer. */
	assign y_offset = diameter * 2365;
	assign centre_x1 = centre_x;
	assign centre_y1 = centre_y - ((y_offset + (1 << 11)) >> 12);
	assign centre_x2 = centre_x + (diameter >> 1);
	assign centre_y2 = centre_y + ((y_offset + (1 << 12)) >> 13);
	assign centre_x3 = centre_x - (diameter >> 1);
	assign centre_y3 = centre_y + ((y_offset + (1 << 12)) >> 13);

	/* Draw only the octants that are needed for each circle.
	 * Extra pixels will be taken care further below. */
	always_comb case (octant)
		/* Circle 1: octants 2 and 3. */
		3'd0: begin
			vga_x_next = centre_x1 + offset_y;
			vga_y_next = centre_y1 + offset_x;
		end
		3'd1: begin
			vga_x_next = centre_x1 - offset_y;
			vga_y_next = centre_y1 + offset_x;
		end
		/* Circle 2: octants 5 and 6. */
		3'd2: begin
			vga_x_next = centre_x2 - offset_x;
			vga_y_next = centre_y2 - offset_y;
		end
		3'd3: begin
			vga_x_next = centre_x2 - offset_y;
			vga_y_next = centre_y2 - offset_x;
		end
		/* Circle 3: octants 7 and 8. */
		3'd4: begin
			vga_x_next = centre_x3 + offset_y;
			vga_y_next = centre_y3 - offset_x;
		end
		3'd5: begin
			vga_x_next = centre_x3 + offset_x;
			vga_y_next = centre_y3 - offset_y;
		end
		default: begin
			vga_x_next = 9'bx;
			vga_y_next = 8'bx;
		end
	endcase

	/* Only plot the pixels of the triangle. */
	always_comb begin
		vga_plot_next = 1'b0;
		/* Pixels of circle 1 that are below the centre of 2 or 3. */
		if ((octant == 3'd0) || (octant == 3'd1))
			if (vga_y_next > centre_y2)
				vga_plot_next = 1'b1;
		/* Pixels of circle 2 that are to the left of the centre. */
		if ((octant == 3'd2) || (octant == 3'd3))
			if (vga_x_next <= centre_x)
				vga_plot_next = 1'b1;
		/* Pixels of circle 3 that are to the right of the centre. */
		if ((octant == 3'd4) || (octant == 3'd5))
			if (vga_x_next >= centre_x)
				vga_plot_next = 1'b1;
	end

	/* Main combinational logic for the Bresenham circle algorithm. */
	always_comb begin
		offset_x_next = offset_x;
		offset_y_next = offset_y + 1;

		if (crit <= 0)
			crit_next = crit + 2 * offset_y_next + 1;
		else begin
			offset_x_next = offset_x - 1;
			crit_next = crit
				+ 2 * (offset_y_next - offset_x_next) + 1;
		end
	end

	always_ff @(posedge clk) begin
		if (~rst_n) begin
			done <= 1'b0;
			ready <= 1'b0;

			/* Start clearing the screen. */
			clear <= 1'b1;
			vga_x <= 8'b0;
			vga_y <= 7'b0;
			vga_plot <= 1'b1;
		end

		/* Clear the screen. */
		if (clear) begin
			if (vga_y < 120) begin
				/* Check for one column less since it takes
				 * one clock cycle to reset and increment. */
				if (vga_x < 159)
					vga_x <= vga_x + 1;
				else begin
					vga_x <= 8'b0;
					vga_y <= vga_y + 1;
				end
			end else begin
				clear <= 1'b0;
				ready <= 1'b1;
				vga_x <= 8'b0;
				vga_y <= 7'b0;
				vga_plot <= 1'b0;
			end
		/* Initialise the registers for the circle algorithm. */
		end else if (ready && start && ~done) begin
			ready <= 1'b0;
			octant <= 3'b0;
			offset_y <= 8'b0;
			offset_x <= radius;
			crit <= 1 - radius;
		/* Draw the circle using the Bresenham circle algorithm. */
		end else if (start && ~done) begin
			if (offset_y <= offset_x) begin
				if ((vga_x_next >= 0) && (vga_x_next <= `VGA_W))
					vga_x <= vga_x_next;
				if ((vga_y_next >= 0) && (vga_y_next <= `VGA_H))
					vga_y <= vga_y_next;

				/* Plot only within the monitor's geometry. */
				vga_plot <= (vga_plot_next
					&& (vga_x_next >= 0)
					&& (vga_x_next <= `VGA_W)
					&& (vga_y_next >= 0)
					&& (vga_y_next <= `VGA_H));

				/* The last octant. */
				if (octant == 5) begin
					offset_x <= offset_x_next;
					offset_y <= offset_y_next;
					crit <= crit_next;
					octant <= 3'b0;
				end else
					octant <= octant + 1;
			/* Finished. */
			end else begin
				done <= 1'b1;
				ready <= 1'b1;
				vga_plot <= 1'b0;
			end
		/* Wait for start to be deasserted. */
		end else if (~start && done)
			done <= 1'b0;
	end

endmodule: reuleaux