-- generic_adder.vhdl -- Generic Carry-Increment Adder
-- Copyright (C) 2000, 2001 Michael Riepe <michael@stud.uni-hannover.de>
--
-- This program is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program; if not, write to the Free Software
-- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

-- $Id: generic_adder.vhdl,v 1.5 2001/11/26 19:38:55 michael Exp $

library IEEE;
use IEEE.std_logic_1164.all;

package Generic_Adder is
	-- sequential versions
	procedure CIA_Core (Gi, Pi : in std_ulogic_vector(3 downto 0);
						Cv, Iv : out std_ulogic_vector(3 downto 0);
						Go, Po : out std_ulogic);
	procedure CIA_Row (Gi, Pi : in std_ulogic_vector;
					   Cv, Iv, Go, Po : out std_ulogic_vector);
	procedure CIA_Inc (Yi, Ci, Cv, Iv : in std_ulogic_vector;
					   Yo, Co : out std_ulogic_vector;
					   step : in natural);
	procedure CIAdd (A, B : in std_ulogic_vector;
				     Y, C : out std_ulogic_vector;
				     G, P : out std_ulogic);
	-- concurrent versions
	procedure S_CIA_Core (Gi, Pi : in std_ulogic_vector(3 downto 0);
						  signal Cv, Iv : out std_ulogic_vector(3 downto 0);
						  signal Go, Po : out std_ulogic);
	procedure S_CIA_Row (Gi, Pi : in std_ulogic_vector;
						 signal Cv, Iv, Go, Po : out std_ulogic_vector);
	procedure S_CIA_Inc (Yi, Ci, Cv, Iv : in std_ulogic_vector;
						 signal Yo, Co : out std_ulogic_vector;
						 step : in natural);
	procedure S_CIAdd (A, B : in std_ulogic_vector;
					   signal Y, C : out std_ulogic_vector;
					   signal G, P : out std_ulogic);
end Generic_Adder;

package body Generic_Adder is
	procedure CIA_Core (Gi, Pi : in std_ulogic_vector(3 downto 0);
						Cv, Iv : out std_ulogic_vector(3 downto 0);
						Go, Po : out std_ulogic) is
	begin
		Cv(0) := '0';
		Cv(1) := Gi(0);
		Cv(2) := Gi(1)
			 or (Pi(1) and Gi(0));
		Cv(3) := Gi(2)
			 or (Pi(2) and Gi(1))
			 or (Pi(2) and Pi(1) and Gi(0));
		Iv(0) := '1';
		Iv(1) := Pi(0);
		Iv(2) := Pi(1) and Pi(0);
		Iv(3) := Pi(2) and Pi(1) and Pi(0);
		Go    := Gi(3)
			 or (Pi(3) and Gi(2))
			 or (Pi(3) and Pi(2) and Gi(1))
			 or (Pi(3) and Pi(2) and Pi(1) and Gi(0));
		Po    := Pi(3) and Pi(2) and Pi(1) and Pi(0);
	end CIA_Core;

	procedure CIA_Row (Gi, Pi : in std_ulogic_vector;
					   Cv, Iv, Go, Po : out std_ulogic_vector) is
		constant WIDTH : natural := Gi'length;
		constant SMALL : natural := (WIDTH+3)/4;
		constant L : natural := 4*SMALL;
		constant n : natural := WIDTH/4;
		variable g_i, p_i, c_v, i_v : std_ulogic_vector(L-1 downto 0);
		variable g_o, p_o : std_ulogic_vector(SMALL-1 downto 0);
	begin
--pragma synthesis_off
		assert WIDTH > 1;
		assert Gi'length = WIDTH;
		assert Pi'length = WIDTH;
		assert Cv'length = WIDTH;
		assert Iv'length = WIDTH;
		assert Go'length = SMALL;
		assert Po'length = SMALL;
--pragma synthesis_on

		-- normalize inputs
		g_i := (others => '0'); g_i(WIDTH-1 downto 0) := Gi;
		p_i := (others => '1'); p_i(WIDTH-1 downto 0) := Pi;

		-- logic
		for i in SMALL-1 downto 0 loop
			CIA_Core(
				g_i(4*i+3 downto 4*i),
				p_i(4*i+3 downto 4*i),
				c_v(4*i+3 downto 4*i),
				i_v(4*i+3 downto 4*i),
				g_o(i), p_o(i)
			);
		end loop;

		-- outputs
		Cv := c_v(WIDTH-1 downto 0);
		Iv := i_v(WIDTH-1 downto 0);
		Go := g_o;
		Po := p_o;
	end CIA_Row;

	procedure CIA_Inc (Yi, Ci, Cv, Iv : in std_ulogic_vector;
					   Yo, Co : out std_ulogic_vector;
					   step : in natural) is
		constant WIDTH : natural := Yi'length;
		constant SMALL : natural := (WIDTH-1)/step + 1;
		variable yy, cc : std_ulogic_vector(WIDTH-1 downto 0);
		variable c_v, i_v : std_ulogic_vector(SMALL-1 downto 0);
	begin
--pragma synthesis_off
		assert Yi'length = WIDTH;
		assert Ci'length = WIDTH;
		assert Cv'length = SMALL;
		assert Iv'length = SMALL;
--pragma synthesis_on

		-- normalize inputs
		yy := Yi;
		cc := Ci;
		c_v := Cv;
		i_v := Iv;

		for i in yy'range loop
			yy(i) := yy(i) xor (cc(i) and c_v(i/step));
			cc(i) := cc(i) and i_v(i/step);
		end loop;

		-- outputs
		Yo := yy;
		Co := cc;
	end CIA_Inc;

	-- delay:
	--   1 ..   4 bit: d=4
	--   5 ..   8 bit: d=5
	--   9 ..  32 bit: d=7
	--  33 .. 128 bit: d=9
	-- 129 .. 512 bit: d=11
	procedure CIAdd (A, B : in std_ulogic_vector;
				     Y, C : out std_ulogic_vector;
				     G, P : out std_ulogic) is
		constant WIDTH : natural := A'length;
		variable aa, bb : std_ulogic_vector(WIDTH-1 downto 0);
		variable ym, cm : std_ulogic_vector(WIDTH-1 downto 0);
		variable gm, pm : std_ulogic_vector(WIDTH-1 downto 0);
		variable cv, iv : std_ulogic_vector(WIDTH-1 downto 0);
		variable step, left : integer;
	begin
--pragma synthesis_off
		assert A'length = WIDTH;
		assert B'length = WIDTH;
		assert Y'length = WIDTH;
		assert C'length = WIDTH;
--pragma synthesis_on

		-- normalize inputs
		aa := A;
		bb := B;

		-- a row of 4-bit adders
		gm := aa and bb;				-- d=1
		pm := aa xor bb;				-- d=1
		ym := pm;
		CIA_Row(
			gm, pm, cv, iv,
			gm((WIDTH-1)/4 downto 0),	-- d=3
			pm((WIDTH-1)/4 downto 0)	-- d=2
		);
		cm := iv;						-- d=2
		ym := ym xor cv;				-- d=4

		-- carry-increment tree
		for level in 1 to 15 loop	-- should be enough...
			step := 4 ** level;
			exit when step >= WIDTH;
			left := (WIDTH - 1) / step;

			-- single level of carry-increment tree
			CIA_Row(					-- b <= 8  16  32  64 128 256 512
				gm(left downto 0),		-- d =  3   3   5   5   7   7   9
				pm(left downto 0),		-- d =  2   2   3   3   4   4   5
			--
				cv(left downto 0),		-- d =  3   5   5   7   7   9   9
				iv(left downto 0),		-- d =  2   3   3   4   4   5   5
				gm(left/4 downto 0),	-- d =  5   5   7   7   9   9  11
				pm(left/4 downto 0)		-- d =  3   3   4   4   5   5   6
			);

			-- intermediate result
			CIA_Inc(					-- b <= 8  16  32  64 128 256 512
				ym(WIDTH-1 downto 0),	-- d =  4   4   7   7   9   9  11
				cm(WIDTH-1 downto 0),	-- d =  2   2   4   4   5   5   6
				cv(left downto 0),		-- d =  3   5   5   7   7   9   9
				iv(left downto 0),		-- d =  2   3   3   4   4   5   5
			--
				ym(WIDTH-1 downto 0),	-- d =  5   7   8   9  10  11  12
				cm(WIDTH-1 downto 0),	-- d =  3   4   5   5   6   6   7
				step
			);
		end loop;

		-- outputs
		Y := ym;
		C := cm;
		G := gm(0);
		P := pm(0);
	end CIAdd;

	procedure S_CIA_Core (Gi, Pi : in std_ulogic_vector(3 downto 0);
						  signal Cv, Iv : out std_ulogic_vector(3 downto 0);
						  signal Go, Po : out std_ulogic) is
		variable c_v, i_v : std_ulogic_vector(3 downto 0);
		variable g_o, p_o : std_ulogic;
	begin
		CIA_Core(Gi, Pi, c_v, i_v, g_o, p_o);
		Cv <= c_v;
		Iv <= i_v;
		Go <= g_o;
		Po <= p_o;
	end S_CIA_Core;

	procedure S_CIA_Row (Gi, Pi : in std_ulogic_vector;
						 signal Cv, Iv, Go, Po : out std_ulogic_vector) is
		variable c_v : std_ulogic_vector(Cv'length-1 downto 0);
		variable i_v : std_ulogic_vector(Iv'length-1 downto 0);
		variable g_o : std_ulogic_vector(Go'length-1 downto 0);
		variable p_o : std_ulogic_vector(Po'length-1 downto 0);
	begin
		CIA_Row(Gi, Pi, c_v, i_v, g_o, p_o);
		Cv <= c_v;
		Iv <= i_v;
		Go <= g_o;
		Po <= p_o;
	end S_CIA_Row;

	procedure S_CIA_Inc (Yi, Ci, Cv, Iv : in std_ulogic_vector;
						 signal Yo, Co : out std_ulogic_vector;
						 step : in natural) is
		variable y_o : std_ulogic_vector(Yo'length-1 downto 0);
		variable c_o : std_ulogic_vector(Co'length-1 downto 0);
	begin
		CIA_Inc(Yi, Ci, Cv, Iv, y_o, c_o, step);
		Yo <= y_o;
		Co <= c_o;
	end S_CIA_Inc;

	procedure S_CIAdd (A, B : in std_ulogic_vector;
					   signal Y, C : out std_ulogic_vector;
					   signal G, P : out std_ulogic) is
		variable y_o : std_ulogic_vector(Y'length-1 downto 0);
		variable c_o : std_ulogic_vector(C'length-1 downto 0);
		variable g_o, p_o : std_ulogic;
	begin
		CIAdd(A, B, y_o, c_o, g_o, p_o);
		Y <= y_o;
		C <= c_o;
		G <= g_o;
		P <= p_o;
	end S_CIAdd;
end Generic_Adder;

--pragma synthesis_off

-- testbench

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_textio.all;
use IEEE.numeric_std.all;
use std.textio.all;
use work.Generic_Adder.all;

entity Generic_Adder_test is
	generic (WIDTH : natural := 39);
end Generic_Adder_test;

architecture Arch_1 of Generic_Adder_test is
	signal A, B : std_ulogic_vector(WIDTH-1 downto 0) := (others => '1');
	signal Y, C : std_ulogic_vector(WIDTH-1 downto 0);
	signal G, P : std_ulogic_vector(0 downto 0);

	procedure writestr (s : string) is
		variable lout : line;
	begin
		write(lout, s);
		writeline(output, lout);
	end writestr;

	procedure do_report (lbl : string;
						 x, y : std_ulogic_vector) is
		variable lout : line;
	begin
		write(lout, string'("WHOA THERE!!!")); writeline(output, lout);
		write(lout, string'("A := ")); write(lout, A); writeline(output, lout);
		write(lout, string'("B := ")); write(lout, B); writeline(output, lout);
		write(lout, string'("Y := ")); write(lout, Y); writeline(output, lout);
		write(lout, string'("C := ")); write(lout, C); writeline(output, lout);
		write(lout, string'("G := ")); write(lout, G); writeline(output, lout);
		write(lout, string'("P := ")); write(lout, P); writeline(output, lout);
		write(lout, lbl);
		write(lout, string'(" := "));
		write(lout, x);
		writeline(output, lout);
		write(lout, lbl);
		write(lout, string'(" /= "));
		write(lout, y);
		writeline(output, lout);
	end do_report;

	procedure check_numeric (lbl : string;
							 x : std_ulogic_vector;
							 y : natural) is
		variable tmp : std_ulogic_vector(x'range);
		variable lout : line;
	begin
		tmp := std_ulogic_vector(to_unsigned(y mod 2**x'length, x'length));
		if x /= tmp then
			do_report(lbl, x, tmp);
		end if;
	end check_numeric;

	procedure check_logic (lbl : string;
						   a, b : std_ulogic_vector) is
		alias x : std_ulogic_vector(a'length downto 1) is a;
		alias y : std_ulogic_vector(b'length downto 1) is b;
		variable lout : line;
	begin
		assert a'length = b'length;
		for i in x'range loop
			next when y(i) = '-';
			next when x(i) = y(i);
			do_report(lbl, x, y);
			return;
		end loop;
	end check_logic;
begin
	-- module under test
	mut : S_CIAdd(A, B, Y, C, G(0), P(0));

	-- driver process
	run : process
		variable av, bv, tmp : std_ulogic_vector(WIDTH-1 downto 0);
		variable left, right, bits, res : natural;
		variable lout : line;
	begin
		write(lout, string'("*** testing Generic_Adder entity ("));
		write(lout, WIDTH);
		write(lout, string'(" bits wide) ***"));
		writeline(output, lout);

		av := (others => 'X');
		bv := (others => 'X');
		for slice in 0 to (WIDTH-1)/4 loop
			write(lout, string'("*** testing slice "));
			write(lout, slice);
			write(lout, string'(" ***"));
			writeline(output, lout);

			-- calculate slice range and width
			right := 4 * slice; left := right + 4;
			if left >= WIDTH then
				-- leftmost 4-bit slice, strip MSBits
				left := WIDTH - 1;
			end if;
			bits := left - right + 1;
			-- carry-in on/off loop
			for k in 0 to 1 loop
				-- turn carry-in on/off
				if right /= 0 then
					if k = 0 then
						av(right-1) := '0';
						bv(right-1) := '0';
					else
						av(right-1) := '1';
						bv(right-1) := '1';
					end if;
				end if;
				-- input values loops
				for i in 0 to 2**bits-1 loop
					av(left downto right) := std_ulogic_vector(to_unsigned(i, bits));
					A <= av;
					for j in 0 to 2**bits-1 loop
						bv(left downto right) := std_ulogic_vector(to_unsigned(j, bits));
						B <= bv;
						wait for 1 ns;
						-- test normal output
						res := i + j;
						if right /= 0 then
							res := res + k;
						end if;
						check_numeric("Y", Y(left downto right), res);
					end loop;
				end loop;
			end loop;
			-- clear slice
			av(left downto right) := (others => 'X');
			bv(left downto right) := (others => 'X');
			if right /= 0 then
				av(right-1) := 'X';
				bv(right-1) := 'X';
			end if;
		end loop;

		writestr("*** testing G/P outputs ***");
		av := (others => 'X');
		bv := (others => 'X');
		for i in WIDTH-1 downto 0 loop
			av(i) := '1';
			bv(i) := '1';
			A <= av;
			B <= bv;
			wait for 1 ns;
			check_logic("G", G, std_ulogic_vector'("1"));
			check_logic("P", P, std_ulogic_vector'("0"));
			av(i) := '0';
			bv(i) := '0';
			A <= av;
			B <= bv;
			wait for 1 ns;
			check_logic("G", G, std_ulogic_vector'("0"));
			check_logic("P", P, std_ulogic_vector'("0"));
			av(i) := '1';
		end loop;
		A <= av;
		wait for 1 ns;
		tmp := (others => '1');
		check_logic("G", G, std_ulogic_vector'("0"));
		check_logic("P", P, std_ulogic_vector'("1"));
		check_logic("C", C, tmp);
		for i in WIDTH-1 downto 0 loop
			av(i) := not av(i);
			bv(i) := not bv(i);
			A <= av;
			B <= bv;
			wait for 1 ns;
			check_logic("G", G, std_ulogic_vector'("0"));
			check_logic("P", P, std_ulogic_vector'("1"));
			check_logic("C", C, tmp);
		end loop;

		writestr("*** testing C output ***");
		av := (others => 'X');
		bv := (others => 'X');
		tmp := (others => '-');
		tmp(0) := '1';
		check_logic("C", C, tmp);
		for i in 1 to WIDTH-1 loop
			tmp(i) := '0';
			av(i-1) := '1';
			bv(i-1) := '1';
			A <= av;
			B <= bv;
			wait for 1 ns;
			check_logic("C", C, tmp);
			av(i-1) := '0';
			bv(i-1) := '0';
			A <= av;
			B <= bv;
			wait for 1 ns;
			check_logic("C", C, tmp);
			tmp(i) := '1';
			av(i-1) := '1';
			A <= av;
			wait for 1 ns;
			check_logic("C", C, tmp);
			av(i-1) := '0';
			bv(i-1) := '1';
			A <= av;
			B <= bv;
			wait for 1 ns;
			check_logic("C", C, tmp);
		end loop;

		-- stop simulation
		writestr("*** simulation complete ***");
		wait;
	end process;
end Arch_1;

--pragma synthesis_on

-- vi: set ts=4 sw=4 equalprg="fmt -72 -p--": please