-------------------------------------------------------------------------------
-- Title      : Calcul du modulo de nombres non signés
-- Project    : 
-------------------------------------------------------------------------------
-- File       : unsigned_mod.vhd
-- Author     :   <patrice@SOLEIL>
-- Company    : http://vhdl33.free.fr
-- Created    : 2011-03-30
-- Last update: 2011-04-08
-- Platform   : 
-- Standard   : VHDL'87
-------------------------------------------------------------------------------
-- Description: Circuit synthétisable basé sur la multiplication
-- pour implanter x mod y = x - y * partie_entiere( x / y)
-- N1 est > N2 doit être ajusté pour diminuer le nombre de cycles de calcul
-------------------------------------------------------------------------------
-- Copyright (c) 2011 
-------------------------------------------------------------------------------
-- Revisions  :
-- Date        Version  Author  Description
-- 2011-03-30  1.0      patrice	Created
-------------------------------------------------------------------------------

LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.numeric_std.ALL;

-- ATTENTION ! OPTIMISATION
-- N1 et N2 doivent être calcules au plus juste
-- car le nombre de cycles sera N1 - N2 + 1
-- diviseur < 2**N2 -1 et > 2**(N2-1) donc un '1' en tete

ENTITY unsigned_modulo IS
  GENERIC (
    N1  : natural := 24;           -- Nombres de bits  dividende
    divisor  : unsigned(7 DOWNTO 0) :=x"C8" );    -- 200 et MSB = '1'
  PORT (
    clk        : IN  std_ulogic;
    reset      : IN  std_ulogic;
    start      : IN  std_ulogic;          -- demarrage calcul
    dividend   : IN  std_logic_vector(N1-1 DOWNTO 0);  -- >0
    modulo     : OUT std_logic_vector(divisor'left DOWNTO 0);  -- modulo < diviseur
    data_valid : OUT std_ulogic);       --synchronise la sortie
END unsigned_modulo;

ARCHITECTURE un_multiplieur OF unsigned_modulo IS

 
  -- on propose des quotient par dichotomie
  -- Si dividende - quotient * diviseur est > diviseur,
  -- on augmente le quotient sinon, on le diminue
  -- on a la solution en fin de dichotomie.
  -- les nombres sont non signes mais on utilise des signes pour tester
  -- les differences, le critere etant :
  -- difference entre entree et produit positive et inferieure à quotient
  -- marque la fin (stop)
  -- le nombre de cycles est egal à la différence entre
  -- le nombre de bits dividende et le nombre de bits diviseur

  CONSTANT N2 : natural := divisor'length;  -- plus simple, 8 par defaut
  
  SIGNAL quotient : signed(N1-N2+1 DOWNTO 0);  
  SIGNAL entree : signed(N1 DOWNTO 0);  -- un bit de plus '0' pour +
  SIGNAL produit : signed(N1 +2 DOWNTO 0);  -- 
  SIGNAL plus, stop : std_ulogic;             -- sens de la dichotomie
  SIGNAL modulo_tmp : signed(N1+2 DOWNTO 0); 
  SIGNAL difference : signed(N1 +2 DOWNTO 0); 
  SIGNAL front_start : std_ulogic;
  SIGNAL diviseur : signed(N2 DOWNTO 0);
  SIGNAL zero : boolean;             -- resultat immediat

  
BEGIN

  entree <= signed( '0' & dividend);  -- donc toujours >0

  diviseur <= signed('0' & divisor);

  zero <= entree < diviseur;       -- alors quotient = 0 ; modulo = divisor
 
  -- detection front montant du signal start
  df1 : PROCESS
    VARIABLE q1, q2 : std_ulogic;
  BEGIN  -- PROCESS p1
    WAIT UNTIL rising_edge(clk);
    IF reset = '1' THEN
      q1 := '0'; q2 := '0';
    ELSE
      q2 := q1;
      q1 := start;
    END IF;
    front_start <= NOT q2 AND q1;
  END PROCESS df1;


-- calcul du quotient par dichotomie
  quo1: PROCESS
    VARIABLE dicho : signed(N1-N2+1 DOWNTO 0);
  BEGIN  -- PROCESS quo1
    WAIT UNTIL rising_edge(clk);
    IF reset = '1' OR front_start = '1' THEN
      quotient <= (OTHERS => '0');              
      dicho  := (OTHERS => '0');
      IF NOT zero THEN
          quotient(N1-N2) <= '1';    -- valeur mediane
          dicho(N1-N2-1) := '1';          -- valeur moitie
      END IF;
    ELSIF stop = '0' THEN
     IF plus = '1'  THEN
        quotient <= quotient + dicho;
      ELSE
        quotient <= quotient - dicho;
      END IF;
      dicho := dicho / 2;
     END IF;  
  END PROCESS quo1;

  -- multiplication
  produit <= quotient * diviseur;

  -- différence qui doit etre positive et inferieure à 200
  difference <= entree - produit ;

  -- comparaisons
  plus <= '1' WHEN produit < entree ELSE '0';
  stop <= '1' WHEN (difference >= 0 AND difference < diviseur) OR zero ELSE '0';

  -- calcul du modulo et verification
  cal: PROCESS
  BEGIN  -- PROCESS cal
    WAIT UNTIL rising_edge(clk);
    IF reset = '1' OR start = '1' THEN
      modulo_tmp <= (OTHERS => '0');
      data_valid <= '0';
    ELSIF stop = '1' THEN
      modulo_tmp <= entree - produit;
      data_valid <= '1';
    END if ;
  END PROCESS cal;

  modulo <= std_logic_vector(modulo_tmp(N2-1 DOWNTO 0));

END un_multiplieur;