-- J. Bresenham/midpoint alg. Lineplot from x1,y1 to x2,y2
-- Idea by Lorraine Jong, Lisa Shirachi and Sherman Wang
-- Implementation by C. Meyer, cm@ctmagazin.de
-- für ISE 10.1.03 (!) oder höher, mit 10.1 keine Funktion

library ieee;
  use ieee.std_logic_1164.all;
  use ieee.std_logic_arith.all;
  use ieee.std_logic_unsigned.all;

entity mid_point is

generic (
	constant width : integer := 8  -- Busbreite +1
	);

port (
	clk : in std_logic;
	reset : in std_logic;
--	enable : in std_logic;
	X1 : in std_logic_vector(width-1 downto 0);
	Y1 : in std_logic_vector(width-1 downto 0);
	X2 : in std_logic_vector(width-1 downto 0);
	Y2 : in std_logic_vector(width-1 downto 0);
	XY_wr : in std_logic;
--	buf_ready : in std_logic;
	RAM_wr : out std_logic;
	Done : out std_logic :='1';
	X_addr : out std_logic_vector(width-1 downto 0);
	Y_addr : out std_logic_vector(width-1 downto 0)
	);
end mid_point;

architecture behavioral of mid_point is
	type stateT is (s1wait,s1,s2,s3a,s3b,s4,stop);
	signal state : stateT := s1wait;
	signal buf_write_pre: std_logic :='0';
	signal buf_write_ena: std_logic :='0';
	signal done_pre: std_logic :='1';
	signal X_swap: std_logic;
	signal Y_swap: std_logic;
	signal Xstart: std_logic_vector(width downto 0);
	signal Ystart: std_logic_vector(width downto 0);
	signal Xend: std_logic_vector(width downto 0);
	signal Yend: std_logic_vector(width downto 0);
	signal X_norm: std_logic_vector(width downto 0);	-- Pixeladresse normiert auf Startpunkt 0 links oben
	signal Y_norm: std_logic_vector(width downto 0);
	signal x_invert: std_logic_vector(width downto 0);
	signal y_invert: std_logic_vector(width downto 0);
begin

-- Midpoint-Alg. arbeitet nur mit Endpunkt > Startpunkt in einem Quadranten
X_swap	<= '1'  	when (X2<X1)  else '0';
Y_swap	<= '1'  	when (Y2<Y1)  else '0';
Xstart	<= X2  	when (X_swap='1')  else X1;
Xend		<= (X1-X2)	when (X_swap='1')  else (X2-X1);
X_invert	<= x"FF"	when (X_swap='1')  else x"00";	-- steigende Linie wenn Endpunkt kleiner
Ystart	<= Y2  	when (Y_swap='1')  else Y1;
Yend		<= (Y1-Y2) when (Y_swap='1')  else (Y2-Y1);
Y_invert	<= x"FF"	when (Y_swap='1')  else x"00";	-- steigende Linie wenn Endpunkt kleiner

--Berechnung der Absolut-Adressen
X_addr	<= (X_norm XOR X_invert)+Xend+Xstart+'1' when (X_swap='1') else X_norm+Xstart;
Y_addr	<= (Y_norm XOR Y_invert)+Yend+Ystart+'1' when (Y_swap='1') else Y_norm+Ystart;

process(clk, state, reset)
	variable d : std_logic_vector((width + 1) downto 0); -- decision variable
	variable x : std_logic_vector((width + 1) downto 0);
	variable y : std_logic_vector((width + 1) downto 0);
	variable temp : std_logic_vector((width + 1) downto 0);
	variable temp2 : std_logic_vector((width + 1) downto 0);
	variable temp3 : std_logic_vector((width + 1) downto 0);

	variable da : std_logic_vector((width + 1) downto 0);
	variable a : std_logic_vector((width + 1) downto 0);
	variable db : std_logic_vector((width + 1) downto 0);
	variable b : std_logic_vector((width + 1) downto 0);

	begin
	if reset = '1' then
		state <= stop;
		done<='1';
		done_pre<='1';
		x := (others =>'0');
		y := (others =>'0');
	else
		if rising_edge(clk) then
			RAM_wr <= buf_write_pre and buf_write_ena;
			done <= done_pre;
			buf_write_pre <= '0';
			case state is
			when s1wait =>
				state <= s1;
			when s1 =>
				RAM_wr <= '0';
				-- setting values
				x := (others =>'0');
				y := (others =>'0');

				-- always assume starting point is
				-- to the left and below the end point
				-- x1 < x2 => x_inc = 1
				-- y1 < y2 => y_inc = 1

				if Xend >= Yend then
					-- small slope (m <= 1)
					-- step along x-coordinate
					da := '0' & Xend;
					a := x;
					db := '0' & Yend;
					b := y;
				else
					-- steep slope (m >1)
					-- step along y-coordinate
					da := '0' & Yend;
					a := y;
					db := '0' & Xend;
					b := x;
				end if;

				d := db - da;

				if reset = '1' then
					state <= s1;
				else
					state <= s2;
				end if;

			when s2 =>
				-- condition for while loop
				if Xend >= Yend then
				-- refresh x & y
					x := a;
					y := b;
					temp2 := '0' & Xend;
				else
				-- refresh x & y
					y := a;
					x := b;
					temp2 := '0' & Yend;
				end if;

				if reset = '1' then
					state <= s1;
				elsif (a /= temp2) then
					state <= s3a;
				else
					state <= s4;
				end if;

			when s3a =>
				-- enable write on buffer, ready x and y values
				buf_write_pre <= '1';
				X_norm <= x(width downto 0);
				Y_norm <= y(width downto 0);

				if reset = '1' then
					state <= s1;
				-- hold values on x,y until buffer is ready
	--			elsif buf_ready = '0' then
	--				state <= s3a;
				else
					state <= s3b;
				end if;

			when s3b =>
				-- update x,y,d
				if (d(width + 1) = '1') then
				-- go horizontal(temp=x)/vertical(temp=y)
					temp := db;
				else
				-- go diagonal
					temp := db - da;
					b := b + '1';
				end if;
				a := a + '1';
				d := d + (temp(width downto 0) & '0');
				if reset = '1' then
					state <= s1;
				else
					state <= s2;
				end if;

			when s4 =>
				-- write last endpoint
				buf_write_pre <= '1';
				X_norm <= x(width downto 0);
				Y_norm <= y(width downto 0);
				state <= stop;
			when stop =>
				buf_write_ena<='0';
				buf_write_pre <= '0';
				if XY_wr = '1' then
					state <= s1;
					done <= '0';
					done_pre <= '0';
					buf_write_ena<='1';
				else
					state <= stop;
					done_pre <= '1';
				end if;
			end case;
		end if; --end clock
	end if;
end process;

end behavioral;