use work.Basic.all;

package GCDpack is

constant GCD_delay: Time       := 100 Ns;
constant EqualZero_delay: Time := 10 Ns;
constant MinMax_delay: Time    := 10 Ns;
constant expand_delay: Time    := 5 Ns;
constant GCDctrl_delay: Time   := 10 Ns;
constant MODvec_delay: Time    := 40 Ns;

------------------------------------------------------------
-- Specification of the GCD Algorithm ----------------------
------------------------------------------------------------

component GCD 
  generic(Time_flag: Delay_flag);
  port(A,B: in Integer;GCD: out Integer);
end component;

------------------------------------------------------------
-- Structural Description of the GCD Algorithm -------------
------------------------------------------------------------

component GCDstruc
  generic(M: Positive;Time_flag: Delay_flag);
  port(A,B: in Logic_vector(M-1 downto 0);Start,CLK: in Logic;
       GCD: inout Logic_vector(M-1 downto 0); End1: out Logic);
end component;

-------------------------------------------------------------
-- The following Components are needed for the Structural ---
-- Description ----------------------------------------------
-------------------------------------------------------------

component EqualZero
  generic(M: Positive;Time_flag: Delay_flag);
  port(X: in Logic_vector(M-1 downto 0);Y: out Logic);
end component;

component MinMax
  generic(M: Positive;Time_flag: Delay_flag);
  port(A,B: in Logic_vector(M-1 downto 0);AgtB: out Logic);
end component;

component GCDctrl
  generic(Time_flag: Delay_flag);
  port(Start,EqualZero,CLK: in Logic;
       StoreVergl,StoreLoop,SelectLoopInit,End1: out Logic);
end component;

component MODvec
  generic(M: Positive;Time_flag: Delay_flag);
  port (N,D: in Logic_vector(M-1 downto 0);
        O: out Logic_vector(M-1 downto 0));
end component;
        
end GCDpack;

--------------------------------------------------------------
-- VHDL Description ------------------------------------------
--------------------------------------------------------------

use work.Basic.all;
use work.GCDpack.all;

entity GCD is
  generic(Time_flag: Delay_flag);
  port(A : in Integer;B : in Integer;GCD : out Integer);
end GCD;

architecture Behavioral_description of GCD is
begin

  P0:Process
      variable delay: Time :=0 Ns;
      variable X1: Integer :=0;
      variable X2: Integer :=0;
    begin
      if Time_flag=Const_delay then delay:=GCD_delay;
      end if;
      X1:=A;
      X2:=B;
      Loop0:    
      while (X1/=X2) loop
        if X1>X2 then X1:=X1-X2;
                 else X2:=X2-X1; 
        end if;
      end loop Loop0;
      GCD<=transport X1 after delay;
      wait on A,B;
    end process;
end Behavioral_description;
        
use work.Basic.all;
use work.Elementary.all;
use work.GCDpack.all;

entity GCDstruc is
  generic(M: Positive;Time_flag: Delay_flag);
  port (A,B: in Logic_vector(M-1 downto 0);Start,CLK: in Logic; 
        GCD: inout Logic_vector(M-1 downto 0);End1: out Logic);
end GCDstruc;

architecture Structure of GCDstruc is

  signal AgtB,StoreVergl,StoreLoop,SelectLoopInit,EZero: Logic := '0';
  signal in0,in1,in2,Div,Min,Max,LoopIn0,LoopIn1: Logic_vector(M-1 downto 0);

begin                 

    compare: MinMax
      generic map(M,Time_flag)
      port map(A,B,AgtB);
    MuxHigh: nMUX
      generic map(M,Time_flag)
      port map(B,A,AgtB,Max);
    MuxLow: nMUX
      generic map(M,Time_flag)
      port map(A,B,AgtB,Min);
    Max1: nREG
      generic map(M,Time_flag)
      port map(clk,StoreVergl,Max,LoopIn0);
    Min1: nREG
      generic map(M,Time_flag)
      port map(clk,StoreVergl,Min,LoopIn1);
    LoopHigh: nMux
      generic map(M,Time_flag)
      port map(GCD,LoopIn0,SelectLoopInit,in0);
    LoopLow: nMUX
      generic map(M,Time_flag)
      port map(in2,LoopIn1,SelectLoopInit,in1);
    RegX1: nREG
      generic map(M,Time_flag)
      port map(clk,StoreLoop,in0,Div);
    RegX2: nREG
      generic map(M,Time_flag)
      port map(clk,StoreLoop,in1,GCD);
    compute: MODvec
      generic map(M,Time_flag)
      port map(Div,GCD,in2);
    test: EqualZero
      generic map(M,Time_flag)
      port map(in2,EZero);   
    control: GCDctrl
      generic map(Time_flag)
      port map(Start,EZero,clk,
               StoreVergl,StoreLoop,SelectLoopInit,End1);

end Structure;

use work.Basic.all;
use work.GCDpack.all;

entity MinMax is
  generic(M: Positive;Time_flag: Delay_flag);
  port(A,B: in Logic_vector(M-1 downto 0); 
       AgtB: out Logic);
end MinMax;

architecture Behavior of MinMax is
begin

  p0: process
  variable delay: Time := 0 Ns;
  variable i: Integer := M-1;
  begin
    if Time_flag=Const_delay then delay := MinMax_delay;
    end if;
    i := M-1;
    Loop0:
    while (i>-1 and A(i)=B(i)) loop
      i := i-1;
    end loop Loop0;
    if i <= -1 then AgtB <= transport '0' after delay;
    elsif A(i)='1' and B(i)='0' then AgtB <= transport '1' after delay;
    else AgtB <= transport '0' after delay;
    end if;
    wait on A,B;
  end process;

end Behavior;
       
use work.Basic.all;
use work.GCDpack.all;

entity EqualZero is
  generic(M: Positive;Time_flag: Delay_flag);
  port(X: in Logic_vector(M-1 downto 0);Y: out Logic);
end EqualZero;

architecture Behavior of EqualZero is
begin

  P0: process
  variable delay: Time := 0 Ns;
  variable result: Logic := '1';
  begin
    if Time_flag=Const_delay then delay := EqualZero_delay;
    end if;
    result := '1';
    Loop0:
    for I in 0 to M-1 loop
      if X(I)='1' then result:='0';
      end if;
    end loop Loop0;
    Y<=transport result after delay;
    wait on X;
  end process;

end Behavior;

use work.Basic.all;
use work.GCDpack.all;

entity GCDctrl is
  generic(Time_flag: Delay_flag);
  port(Start,EqualZero,CLK: in Logic; 
       StoreVergl,StoreLoop,SelectLoopInit,End1: out Logic);
end GCDctrl;

architecture Behavior of GCDctrl is
begin

  p0: process
    variable delay: Time := 0Ns;
    variable q0,q1,nextq0,nextq1: Logic := '0';
  begin
    if Time_flag=Const_delay then delay:= GCDctrl_delay;
    end if;
    if CLK='1' then
      if Start='1' then 
        q1:='0';q0:='0';
        StoreVergl <= '1';
        SelectLoopInit <= '1';
        End1 <= '0';
      else
        if q1='0' and q0='0' then
          q1:='0';q0:='1';
          StoreVergl <= '0';
          SelectLoopInit <= '0';
          StoreLoop <= '1';
          End1 <= '0';
        elsif q1='0' and q0='1' then
          if EqualZero='0' then
            q1:='0';q0:='1';
            SelectLoopInit <= '0';
            StoreLoop <= '1';
            End1 <= '0';
          else
            q1:='1';q0:='0';
            SelectLoopInit <= '0';
            StoreLoop <= '0';
            End1 <= '1';
          end if;
        elsif q1='1' and q0='0' then
          q1:='1';q0:='0';
          SelectLoopInit <= '0';
          StoreLoop <= '0';
          End1 <= '1';
        else
          --CASE : q1='1' and q0='1' 
          q1:='1';q0:='0';
          SelectLoopInit <= '0';
          StoreLoop <= '0';
          End1 <= '1';
        end if;
      end if;
    end if;
    wait on CLK;
  end process;

end Behavior;

use work.Basic.all;
use work.GCDpack.all;

entity MODvec is
  generic(M: Positive;Time_flag: Delay_flag);
  port(N,D: in Logic_vector(M-1 downto 0);
       O: out Logic_vector(M-1 downto 0));
end MODvec;

architecture Behavior of MODvec is
begin

  P0: process
  variable delay: Time := 0 Ns;
  variable Ni,Di: Integer := 0;
  begin
    if Time_flag=Const_delay then delay := MODvec_delay;
    end if;
    Ni := 0;
    Di := 0;
    if M>1 then
      Loop0:
      for I in M-1 downto 1 loop
        if N(I)='1' then Ni := Ni + 1;
        end if;
        Ni := Ni * 2;
        if D(I)='1' then Di := Di + 1;
        end if;
        Di := Di * 2;
      end loop Loop0;
    end if;
    if N(0)='1' then Ni := Ni + 1; end if;
    if D(0)='1' then Di := Di + 1; end if;
    Loop1:
    while (Ni > 0 and Ni >= Di) loop
      Ni := Ni - Di;
    end loop Loop1;
    Loop2:
    for J in 0 to M-1 loop
      if (Ni mod 2) = 1 then O(J) <= transport '1' after delay;
                        else O(J) <= transport '0' after delay;
      end if;
      Ni := Ni / 2;
    end loop Loop2;
    wait on N,D;
  end process;
end Behavior;

------------------------------------------------------------
-- Testbench for GCD Algorithm -----------------------------
------------------------------------------------------------

entity Test_GCD is end Test_GCD;

use work.Basic.all;
use work.GCDpack.all;

architecture Test of Test_GCDbehave is

constant M: Positive := 4;

signal Start,End1,CLK: Logic := '0';
signal A,B,C: Logic_vector(M-1 downto 0);
signal A1,B1,C1: Integer := 0;

begin

  -- Behavior -----------------------------------
  U0: GCD
    generic map(Const_delay)
    port map(A1,B1,C1);

  -- Structure ----------------------------------

  U1: GCDstruc 
    generic map(M,Const_delay)
    port map(A,B,Start,CLK,C,End1);

  A  <= "0000" after 0   Ns,"1111" after 120 Ns,
        "0000" after 240 Ns,"0011" after 840 Ns,
        "0000" after 960 Ns;

  B  <= "0000" after 0   Ns,"1001" after 120 Ns,
        "0000" after 240 Ns,"1110" after 840 Ns,
        "0000" after 960 Ns;

  A1 <= 0 after 0   Ns,15 after 120 Ns,
        0 after 240 Ns, 3 after 840 Ns,
        0 after 960 Ns;

  B1 <= 0 after 0   Ns,  9 after 120 Ns,
        0 after 240 Ns, 14 after 840 Ns,
        0 after 960 Ns;  

  Start <= '0' after 0   Ns,'1' after 120 Ns,
           '0' after 240 Ns,'1' after 840 Ns,
           '0' after 960 Ns;

  CLK <= '0' after   0 Ns, '1' after  60 Ns,
         '0' after 120 Ns, '1' after 180 Ns,
         '0' after 240 Ns, '1' after 300 Ns,
         '0' after 360 Ns, '1' after 420 Ns,
         '0' after 480 Ns, '1' after 540 Ns,
         '0' after 600 Ns, '1' after 660 Ns,
         '0' after 720 Ns, '1' after 780 Ns,
         '0' after 840 Ns, '1' after 900 Ns,
         '0' after 960 Ns, '1' after 1020Ns,
         '0' after 1080Ns, '1' after 1140Ns,
         '0' after 1200Ns, '1' after 1260Ns,
         '0' after 1320Ns, '1' after 1380Ns,
         '0' after 1440Ns, '1' after 1500Ns;
                              
end Test;