-- Kyle McGhee
-- kmcghee@purdue.edu
-- divide.vhd

-- This module performs unsigned 32-bit fixed point division.
-- It is purely dataflow and will finish in a single clock cycle.

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;

entity divide is
  port (
    X: in STD_LOGIC_VECTOR(31 downto 0);
    Y: in STD_LOGIC_VECTOR(31 downto 0);

    Z: out STD_LOGIC_VECTOR(31 downto 0);
    V: out STD_LOGIC);
end divide;

-- X:       16.16
-- Y:       16.16
-- Z = X/Y: 16.16
-- V = OVERFLOW

-- Division is a fairly complicated purely dataflow module.
-- It performs a series of checks and possible shifts and subtracts in stages.

architecture divide_arch of divide is
  constant ZERO: STD_LOGIC_VECTOR(31 downto 0) := "00000000000000000000000000000000";

  signal T: STD_LOGIC_VECTOR(47 downto 0);

  signal STAGE_1: UNSIGNED(31 downto 0);
  signal STAGE_2: UNSIGNED(31 downto 0);
  signal STAGE_3: UNSIGNED(31 downto 0);
  signal STAGE_4: UNSIGNED(31 downto 0);
  signal STAGE_5: UNSIGNED(31 downto 0);
  signal STAGE_6: UNSIGNED(31 downto 0);
  signal STAGE_7: UNSIGNED(31 downto 0);
  signal STAGE_8: UNSIGNED(31 downto 0);
  signal STAGE_9: UNSIGNED(31 downto 0);
  signal STAGE_10: UNSIGNED(31 downto 0);
  signal STAGE_11: UNSIGNED(31 downto 0);
  signal STAGE_12: UNSIGNED(31 downto 0);
  signal STAGE_13: UNSIGNED(31 downto 0);
  signal STAGE_14: UNSIGNED(31 downto 0);
  signal STAGE_15: UNSIGNED(31 downto 0);
  signal STAGE_16: UNSIGNED(31 downto 0);
  signal STAGE_17: UNSIGNED(31 downto 0);
  signal STAGE_18: UNSIGNED(31 downto 0);
  signal STAGE_19: UNSIGNED(31 downto 0);
  signal STAGE_20: UNSIGNED(31 downto 0);
  signal STAGE_21: UNSIGNED(31 downto 0);
  signal STAGE_22: UNSIGNED(31 downto 0);
  signal STAGE_23: UNSIGNED(31 downto 0);
  signal STAGE_24: UNSIGNED(31 downto 0);
  signal STAGE_25: UNSIGNED(31 downto 0);
  signal STAGE_26: UNSIGNED(31 downto 0);
  signal STAGE_27: UNSIGNED(31 downto 0);
  signal STAGE_28: UNSIGNED(31 downto 0);
  signal STAGE_29: UNSIGNED(31 downto 0);
  signal STAGE_30: UNSIGNED(31 downto 0);
  signal STAGE_31: UNSIGNED(31 downto 0);
  signal STAGE_32: UNSIGNED(31 downto 0);
  signal STAGE_33: UNSIGNED(31 downto 0);
  signal STAGE_34: UNSIGNED(31 downto 0);
  signal STAGE_35: UNSIGNED(31 downto 0);
  signal STAGE_36: UNSIGNED(31 downto 0);
  signal STAGE_37: UNSIGNED(31 downto 0);
  signal STAGE_38: UNSIGNED(31 downto 0);
  signal STAGE_39: UNSIGNED(31 downto 0);
  signal STAGE_40: UNSIGNED(31 downto 0);
  signal STAGE_41: UNSIGNED(31 downto 0);
  signal STAGE_42: UNSIGNED(31 downto 0);
  signal STAGE_43: UNSIGNED(31 downto 0);
  signal STAGE_44: UNSIGNED(31 downto 0);
  signal STAGE_45: UNSIGNED(31 downto 0);
  signal STAGE_46: UNSIGNED(31 downto 0);
  signal STAGE_47: UNSIGNED(31 downto 0);
begin
  -- Determine if a shift and subtract is appropriate - this is the result of the division
  T(47) <= '1' when (UNSIGNED(X) >= UNSIGNED(Y(0) & ZERO(31 downto  1))) and (Y(31 downto  1) = ZERO(31 downto  1)) else '0';

  T(46) <= '1' when (STAGE_1  >= UNSIGNED(Y( 1 downto 0) & ZERO(31 downto  2))) and (Y(31 downto  2) = ZERO(31 downto  2)) else '0';
  T(45) <= '1' when (STAGE_2  >= UNSIGNED(Y( 2 downto 0) & ZERO(31 downto  3))) and (Y(31 downto  3) = ZERO(31 downto  3)) else '0';
  T(44) <= '1' when (STAGE_3  >= UNSIGNED(Y( 3 downto 0) & ZERO(31 downto  4))) and (Y(31 downto  4) = ZERO(31 downto  4)) else '0';
  T(43) <= '1' when (STAGE_4  >= UNSIGNED(Y( 4 downto 0) & ZERO(31 downto  5))) and (Y(31 downto  5) = ZERO(31 downto  5)) else '0';
  T(42) <= '1' when (STAGE_5  >= UNSIGNED(Y( 5 downto 0) & ZERO(31 downto  6))) and (Y(31 downto  6) = ZERO(31 downto  6)) else '0';
  T(41) <= '1' when (STAGE_6  >= UNSIGNED(Y( 6 downto 0) & ZERO(31 downto  7))) and (Y(31 downto  7) = ZERO(31 downto  7)) else '0';
  T(40) <= '1' when (STAGE_7  >= UNSIGNED(Y( 7 downto 0) & ZERO(31 downto  8))) and (Y(31 downto  8) = ZERO(31 downto  8)) else '0';
  T(39) <= '1' when (STAGE_8  >= UNSIGNED(Y( 8 downto 0) & ZERO(31 downto  9))) and (Y(31 downto  9) = ZERO(31 downto  9)) else '0';
  T(38) <= '1' when (STAGE_9  >= UNSIGNED(Y( 9 downto 0) & ZERO(31 downto 10))) and (Y(31 downto 10) = ZERO(31 downto 10)) else '0';
  T(37) <= '1' when (STAGE_10 >= UNSIGNED(Y(10 downto 0) & ZERO(31 downto 11))) and (Y(31 downto 11) = ZERO(31 downto 11)) else '0';
  T(36) <= '1' when (STAGE_11 >= UNSIGNED(Y(11 downto 0) & ZERO(31 downto 12))) and (Y(31 downto 12) = ZERO(31 downto 12)) else '0';
  T(35) <= '1' when (STAGE_12 >= UNSIGNED(Y(12 downto 0) & ZERO(31 downto 13))) and (Y(31 downto 13) = ZERO(31 downto 13)) else '0';
  T(34) <= '1' when (STAGE_13 >= UNSIGNED(Y(13 downto 0) & ZERO(31 downto 14))) and (Y(31 downto 14) = ZERO(31 downto 14)) else '0';
  T(33) <= '1' when (STAGE_14 >= UNSIGNED(Y(14 downto 0) & ZERO(31 downto 15))) and (Y(31 downto 15) = ZERO(31 downto 15)) else '0';
  T(32) <= '1' when (STAGE_15 >= UNSIGNED(Y(15 downto 0) & ZERO(31 downto 16))) and (Y(31 downto 16) = ZERO(31 downto 16)) else '0';
  T(31) <= '1' when (STAGE_16 >= UNSIGNED(Y(16 downto 0) & ZERO(31 downto 17))) and (Y(31 downto 17) = ZERO(31 downto 17)) else '0';
  T(30) <= '1' when (STAGE_17 >= UNSIGNED(Y(17 downto 0) & ZERO(31 downto 18))) and (Y(31 downto 18) = ZERO(31 downto 18)) else '0';
  T(29) <= '1' when (STAGE_18 >= UNSIGNED(Y(18 downto 0) & ZERO(31 downto 19))) and (Y(31 downto 19) = ZERO(31 downto 19)) else '0';
  T(28) <= '1' when (STAGE_19 >= UNSIGNED(Y(19 downto 0) & ZERO(31 downto 20))) and (Y(31 downto 20) = ZERO(31 downto 20)) else '0';
  T(27) <= '1' when (STAGE_20 >= UNSIGNED(Y(20 downto 0) & ZERO(31 downto 21))) and (Y(31 downto 21) = ZERO(31 downto 21)) else '0';
  T(26) <= '1' when (STAGE_21 >= UNSIGNED(Y(21 downto 0) & ZERO(31 downto 22))) and (Y(31 downto 22) = ZERO(31 downto 22)) else '0';
  T(25) <= '1' when (STAGE_22 >= UNSIGNED(Y(22 downto 0) & ZERO(31 downto 23))) and (Y(31 downto 23) = ZERO(31 downto 23)) else '0';
  T(24) <= '1' when (STAGE_23 >= UNSIGNED(Y(23 downto 0) & ZERO(31 downto 24))) and (Y(31 downto 24) = ZERO(31 downto 24)) else '0';
  T(23) <= '1' when (STAGE_24 >= UNSIGNED(Y(24 downto 0) & ZERO(31 downto 25))) and (Y(31 downto 25) = ZERO(31 downto 25)) else '0';
  T(22) <= '1' when (STAGE_25 >= UNSIGNED(Y(25 downto 0) & ZERO(31 downto 26))) and (Y(31 downto 26) = ZERO(31 downto 26)) else '0';
  T(21) <= '1' when (STAGE_26 >= UNSIGNED(Y(26 downto 0) & ZERO(31 downto 27))) and (Y(31 downto 27) = ZERO(31 downto 27)) else '0';
  T(20) <= '1' when (STAGE_27 >= UNSIGNED(Y(27 downto 0) & ZERO(31 downto 28))) and (Y(31 downto 28) = ZERO(31 downto 28)) else '0';
  T(19) <= '1' when (STAGE_28 >= UNSIGNED(Y(28 downto 0) & ZERO(31 downto 29))) and (Y(31 downto 29) = ZERO(31 downto 29)) else '0';
  T(18) <= '1' when (STAGE_29 >= UNSIGNED(Y(29 downto 0) & ZERO(31 downto 30))) and (Y(31 downto 30) = ZERO(31 downto 30)) else '0';

  T(17) <= '1' when (STAGE_30 >= UNSIGNED(Y(30 downto 0) & ZERO(31))) and (Y(31) = ZERO(31)) else '0';
  T(16) <= '1' when (STAGE_31 >= UNSIGNED(Y)) else '0';
  T(15) <= '1' when (STAGE_32 >= UNSIGNED(ZERO(0) & Y(31 downto 1))) and (Y(31 downto 1) /= ZERO(31 downto 1)) else '0';

  T(14) <= '1' when (STAGE_33 >= UNSIGNED(ZERO( 1 downto 0) & Y(31 downto  2))) and (Y(31 downto  2) /= ZERO(31 downto  2)) else '0';
  T(13) <= '1' when (STAGE_34 >= UNSIGNED(ZERO( 2 downto 0) & Y(31 downto  3))) and (Y(31 downto  3) /= ZERO(31 downto  3)) else '0';
  T(12) <= '1' when (STAGE_35 >= UNSIGNED(ZERO( 3 downto 0) & Y(31 downto  4))) and (Y(31 downto  4) /= ZERO(31 downto  4)) else '0';
  T(11) <= '1' when (STAGE_36 >= UNSIGNED(ZERO( 4 downto 0) & Y(31 downto  5))) and (Y(31 downto  5) /= ZERO(31 downto  5)) else '0';
  T(10) <= '1' when (STAGE_37 >= UNSIGNED(ZERO( 5 downto 0) & Y(31 downto  6))) and (Y(31 downto  6) /= ZERO(31 downto  6)) else '0';
  T( 9) <= '1' when (STAGE_38 >= UNSIGNED(ZERO( 6 downto 0) & Y(31 downto  7))) and (Y(31 downto  7) /= ZERO(31 downto  7)) else '0';
  T( 8) <= '1' when (STAGE_39 >= UNSIGNED(ZERO( 7 downto 0) & Y(31 downto  8))) and (Y(31 downto  8) /= ZERO(31 downto  8)) else '0';
  T( 7) <= '1' when (STAGE_40 >= UNSIGNED(ZERO( 8 downto 0) & Y(31 downto  9))) and (Y(31 downto  9) /= ZERO(31 downto  9)) else '0';
  T( 6) <= '1' when (STAGE_41 >= UNSIGNED(ZERO( 9 downto 0) & Y(31 downto 10))) and (Y(31 downto 10) /= ZERO(31 downto 10)) else '0';
  T( 5) <= '1' when (STAGE_42 >= UNSIGNED(ZERO(10 downto 0) & Y(31 downto 11))) and (Y(31 downto 11) /= ZERO(31 downto 11)) else '0';
  T( 4) <= '1' when (STAGE_43 >= UNSIGNED(ZERO(11 downto 0) & Y(31 downto 12))) and (Y(31 downto 12) /= ZERO(31 downto 12)) else '0';
  T( 3) <= '1' when (STAGE_44 >= UNSIGNED(ZERO(12 downto 0) & Y(31 downto 13))) and (Y(31 downto 13) /= ZERO(31 downto 13)) else '0';
  T( 2) <= '1' when (STAGE_45 >= UNSIGNED(ZERO(13 downto 0) & Y(31 downto 14))) and (Y(31 downto 14) /= ZERO(31 downto 14)) else '0';
  T( 1) <= '1' when (STAGE_46 >= UNSIGNED(ZERO(14 downto 0) & Y(31 downto 15))) and (Y(31 downto 15) /= ZERO(31 downto 15)) else '0';
  T( 0) <= '1' when (STAGE_47 >= UNSIGNED(ZERO(15 downto 0) & Y(31 downto 16))) and (Y(31 downto 16) /= ZERO(31 downto 16)) else '0';

  -- Set the results of the shift and subtracts if they are appropriate
  STAGE_1  <= (UNSIGNED(X) - UNSIGNED(Y(0) & ZERO(30 downto 0))) when (T(47) = '1') else UNSIGNED(X);

  STAGE_2  <= (STAGE_1  - UNSIGNED(Y( 1 downto 0) & ZERO(29 downto 0))) when (T(46) = '1') else STAGE_1;
  STAGE_3  <= (STAGE_2  - UNSIGNED(Y( 2 downto 0) & ZERO(28 downto 0))) when (T(45) = '1') else STAGE_2;
  STAGE_4  <= (STAGE_3  - UNSIGNED(Y( 3 downto 0) & ZERO(27 downto 0))) when (T(44) = '1') else STAGE_3;
  STAGE_5  <= (STAGE_4  - UNSIGNED(Y( 4 downto 0) & ZERO(26 downto 0))) when (T(43) = '1') else STAGE_4;
  STAGE_6  <= (STAGE_5  - UNSIGNED(Y( 5 downto 0) & ZERO(25 downto 0))) when (T(42) = '1') else STAGE_5;
  STAGE_7  <= (STAGE_6  - UNSIGNED(Y( 6 downto 0) & ZERO(24 downto 0))) when (T(41) = '1') else STAGE_6;
  STAGE_8  <= (STAGE_7  - UNSIGNED(Y( 7 downto 0) & ZERO(23 downto 0))) when (T(40) = '1') else STAGE_7;
  STAGE_9  <= (STAGE_8  - UNSIGNED(Y( 8 downto 0) & ZERO(22 downto 0))) when (T(39) = '1') else STAGE_8;
  STAGE_10 <= (STAGE_9  - UNSIGNED(Y( 9 downto 0) & ZERO(21 downto 0))) when (T(38) = '1') else STAGE_9;
  STAGE_11 <= (STAGE_10 - UNSIGNED(Y(10 downto 0) & ZERO(20 downto 0))) when (T(37) = '1') else STAGE_10;
  STAGE_12 <= (STAGE_11 - UNSIGNED(Y(11 downto 0) & ZERO(19 downto 0))) when (T(36) = '1') else STAGE_11;
  STAGE_13 <= (STAGE_12 - UNSIGNED(Y(12 downto 0) & ZERO(18 downto 0))) when (T(35) = '1') else STAGE_12;
  STAGE_14 <= (STAGE_13 - UNSIGNED(Y(13 downto 0) & ZERO(17 downto 0))) when (T(34) = '1') else STAGE_13;
  STAGE_15 <= (STAGE_14 - UNSIGNED(Y(14 downto 0) & ZERO(16 downto 0))) when (T(33) = '1') else STAGE_14;
  STAGE_16 <= (STAGE_15 - UNSIGNED(Y(15 downto 0) & ZERO(15 downto 0))) when (T(32) = '1') else STAGE_15;
  STAGE_17 <= (STAGE_16 - UNSIGNED(Y(16 downto 0) & ZERO(14 downto 0))) when (T(31) = '1') else STAGE_16;
  STAGE_18 <= (STAGE_17 - UNSIGNED(Y(17 downto 0) & ZERO(13 downto 0))) when (T(30) = '1') else STAGE_17;
  STAGE_19 <= (STAGE_18 - UNSIGNED(Y(18 downto 0) & ZERO(12 downto 0))) when (T(29) = '1') else STAGE_18;
  STAGE_20 <= (STAGE_19 - UNSIGNED(Y(19 downto 0) & ZERO(11 downto 0))) when (T(28) = '1') else STAGE_19;
  STAGE_21 <= (STAGE_20 - UNSIGNED(Y(20 downto 0) & ZERO(10 downto 0))) when (T(27) = '1') else STAGE_20;
  STAGE_22 <= (STAGE_21 - UNSIGNED(Y(21 downto 0) & ZERO( 9 downto 0))) when (T(26) = '1') else STAGE_21;
  STAGE_23 <= (STAGE_22 - UNSIGNED(Y(22 downto 0) & ZERO( 8 downto 0))) when (T(25) = '1') else STAGE_22;
  STAGE_24 <= (STAGE_23 - UNSIGNED(Y(23 downto 0) & ZERO( 7 downto 0))) when (T(24) = '1') else STAGE_23;
  STAGE_25 <= (STAGE_24 - UNSIGNED(Y(24 downto 0) & ZERO( 6 downto 0))) when (T(23) = '1') else STAGE_24;
  STAGE_26 <= (STAGE_25 - UNSIGNED(Y(25 downto 0) & ZERO( 5 downto 0))) when (T(22) = '1') else STAGE_25;
  STAGE_27 <= (STAGE_26 - UNSIGNED(Y(26 downto 0) & ZERO( 4 downto 0))) when (T(21) = '1') else STAGE_26;
  STAGE_28 <= (STAGE_27 - UNSIGNED(Y(27 downto 0) & ZERO( 3 downto 0))) when (T(20) = '1') else STAGE_27;
  STAGE_29 <= (STAGE_28 - UNSIGNED(Y(28 downto 0) & ZERO( 2 downto 0))) when (T(19) = '1') else STAGE_28;
  STAGE_30 <= (STAGE_29 - UNSIGNED(Y(29 downto 0) & ZERO( 1 downto 0))) when (T(18) = '1') else STAGE_29;

  STAGE_31 <= (STAGE_30 - UNSIGNED(Y(30 downto 0) & ZERO(0))) when (T(17) = '1') else STAGE_30;
  STAGE_32 <= (STAGE_31 - UNSIGNED(Y(31 downto 0))) when (T(16) = '1') else STAGE_31;
  STAGE_33 <= (STAGE_32 - UNSIGNED(ZERO(0) & Y(31 downto 1))) when (T(15) = '1') else STAGE_32;

  STAGE_34 <= (STAGE_33 - UNSIGNED(ZERO( 1 downto 0) & Y(31 downto  2))) when (T(14) = '1') else STAGE_33;
  STAGE_35 <= (STAGE_34 - UNSIGNED(ZERO( 2 downto 0) & Y(31 downto  3))) when (T(13) = '1') else STAGE_34;
  STAGE_36 <= (STAGE_35 - UNSIGNED(ZERO( 3 downto 0) & Y(31 downto  4))) when (T(12) = '1') else STAGE_35;
  STAGE_37 <= (STAGE_36 - UNSIGNED(ZERO( 4 downto 0) & Y(31 downto  5))) when (T(11) = '1') else STAGE_36;
  STAGE_38 <= (STAGE_37 - UNSIGNED(ZERO( 5 downto 0) & Y(31 downto  6))) when (T(10) = '1') else STAGE_37;
  STAGE_39 <= (STAGE_38 - UNSIGNED(ZERO( 6 downto 0) & Y(31 downto  7))) when (T( 9) = '1') else STAGE_38;
  STAGE_40 <= (STAGE_39 - UNSIGNED(ZERO( 7 downto 0) & Y(31 downto  8))) when (T( 8) = '1') else STAGE_39;
  STAGE_41 <= (STAGE_40 - UNSIGNED(ZERO( 8 downto 0) & Y(31 downto  9))) when (T( 7) = '1') else STAGE_40;
  STAGE_42 <= (STAGE_41 - UNSIGNED(ZERO( 9 downto 0) & Y(31 downto 10))) when (T( 6) = '1') else STAGE_41;
  STAGE_43 <= (STAGE_42 - UNSIGNED(ZERO(10 downto 0) & Y(31 downto 11))) when (T( 5) = '1') else STAGE_42;
  STAGE_44 <= (STAGE_43 - UNSIGNED(ZERO(11 downto 0) & Y(31 downto 12))) when (T( 4) = '1') else STAGE_43;
  STAGE_45 <= (STAGE_44 - UNSIGNED(ZERO(12 downto 0) & Y(31 downto 13))) when (T( 3) = '1') else STAGE_44;
  STAGE_46 <= (STAGE_45 - UNSIGNED(ZERO(13 downto 0) & Y(31 downto 14))) when (T( 2) = '1') else STAGE_45;
  STAGE_47 <= (STAGE_46 - UNSIGNED(ZERO(14 downto 0) & Y(31 downto 15))) when (T( 1) = '1') else STAGE_46;

  -- The result is the last (middle) 32 bits
  Z <= T(31 downto 0);

  -- If any of the dropped bits are set, there was an overflow
  V <= '1' when ((T(47) = '1') or
                 (T(46) = '1') or
                 (T(45) = '1') or
                 (T(44) = '1') or
                 (T(43) = '1') or
                 (T(42) = '1') or
                 (T(41) = '1') or
                 (T(40) = '1') or
                 (T(39) = '1') or
                 (T(38) = '1') or
                 (T(37) = '1') or
                 (T(36) = '1') or
                 (T(35) = '1') or
                 (T(34) = '1') or
                 (T(33) = '1') or
                 (T(32) = '1')) else '0';
end divide_arch;
