Subversion Repositories heap_sorter

-------------------------------------------------------------------------------

-- Title      : Definitions for heap-sorter

-- Project    : heap-sorter

-------------------------------------------------------------------------------

-- File       : sorter_pkg.vhd

-- Author     : Wojciech M. Zabolotny <wzab@ise.pw.edu.pl>

-- Company    : 

-- Created    : 2010-05-14

-- Last update: 2011-07-11

-- Platform   : 

-- Standard   : VHDL'93

-------------------------------------------------------------------------------

-- Description: 

-------------------------------------------------------------------------------

-- Copyright (c) 2010 Wojciech M. Zabolotny

-- This file is published under the BSD license, so you can freely adapt

-- it for your own purposes.

-- Additionally this design has been described in my article:

--    Wojciech M. Zabolotny, "Dual port memory based Heapsort implementation

--    for FPGA", Proc. SPIE 8008, 80080E (2011); doi:10.1117/12.905281

-- I'd be glad if you cite this article when you publish something based

-- on my design.

-------------------------------------------------------------------------------

-- Revisions  :

-- Date        Version  Author  Description

-- 2010-05-14  1.0      wzab    Created

-------------------------------------------------------------------------------

library ieee;

use ieee.std_logic_1164.all;

use ieee.numeric_std.all;

use ieee.std_logic_textio.all;

use std.textio.all;

library work;

use work.sys_config.all;

package sorter_pkg is

  constant DATA_REC_WIDTH : integer := DATA_REC_SORT_KEY_WIDTH +

                                       DATA_REC_PAYLOAD_WIDTH + 2;

  subtype T_SORT_KEY is unsigned (DATA_REC_SORT_KEY_WIDTH - 1 downto 0);

  subtype T_PAYLOAD is std_logic_vector(DATA_REC_PAYLOAD_WIDTH - 1 downto 0);

  --alias T_SORT_KEY is unsigned (12 downto 0);

  type T_DATA_REC is record

    d_key     : T_SORT_KEY;

    init      : std_logic;

    valid     : std_logic;

    d_payload : T_PAYLOAD;

  end record;

  type T_DATA_REC_ARR is array (natural range <>) of T_DATA_REC;

  -- Special constant used to initially fill the sorter

  -- Must be sorted so, that is smaller, than any other data

  constant DATA_REC_INIT_DATA : T_DATA_REC := (

    d_key     => to_unsigned(0, DATA_REC_SORT_KEY_WIDTH),

    init      => '1',

    valid     => '0',

    d_payload => (others => '0')

    );

  -- Special constant used to ``flush'' the sorter at the end

  constant DATA_REC_END_DATA : T_DATA_REC := (

    d_key     => to_unsigned(0, DATA_REC_SORT_KEY_WIDTH),

    init      => '1',

    valid     => '1',

    d_payload => (others => '0')

    );

  function sort_cmp_lt (

    constant v1 : T_DATA_REC;

    constant v2 : T_DATA_REC)

    return boolean;

  function tdrec2stlv (

    constant drec : T_DATA_REC)

    return std_logic_vector;

  function stlv2tdrec (

    constant dstlv : std_logic_vector)

    return T_DATA_REC;

  --procedure wrstlv (

  --  rline         : inout line;

  --  constant vect :       std_logic_vector);

  file reports : text open write_mode is "STD_OUTPUT";

end sorter_pkg;

package body sorter_pkg is

  function stlv2tdrec (

    constant dstlv : std_logic_vector)

    return T_DATA_REC is

    variable result : T_DATA_REC;

    variable j      : integer := 0;

  begin  -- stlv2drec

    j                := 0;

    result.d_key     := unsigned(dstlv(j-1+DATA_REC_SORT_KEY_WIDTH downto j));

    j                := j+DATA_REC_SORT_KEY_WIDTH;

    result.valid     := dstlv(j);

    j                := j+1;

    result.init      := dstlv(j);

    j                := j+1;

    result.d_payload := dstlv(j-1+DATA_REC_PAYLOAD_WIDTH downto j);

    j                := j+DATA_REC_PAYLOAD_WIDTH;

    return result;

  end stlv2tdrec;

  function tdrec2stlv (

    constant drec : T_DATA_REC)

    return std_logic_vector is

    variable result : std_logic_vector(DATA_REC_WIDTH-1 downto 0);

    variable j      : integer := 0;

  begin  -- tdrec2stlv

    j                                            := 0;

    result(j-1+DATA_REC_SORT_KEY_WIDTH downto j) := std_logic_vector(drec.d_key);

    j                                            := j+DATA_REC_SORT_KEY_WIDTH;

    result(j)                                    := drec.valid;

    j                                            := j+1;

    result(j)                                    := drec.init;

    j                                            := j+1;

    result(j-1+DATA_REC_PAYLOAD_WIDTH downto j)  := std_logic_vector(drec.d_payload);

    j                                            := j+DATA_REC_PAYLOAD_WIDTH;

    return result;

  end tdrec2stlv;

  -- Function sort_cmp_lt returns TRUE when the first opperand is ``less'' than

  -- the second one

  function sort_cmp_lt (

    constant v1 : T_DATA_REC;

    constant v2 : T_DATA_REC)

    return boolean is

    variable rline : line;

    variable dcomp  : unsigned(DATA_REC_SORT_KEY_WIDTH-1 downto 0) := (others => '0');

  begin  -- sort_cmp_lt

    -- Check the special cases

    if (v1.init = '1') and (v2.init = '0') then

      -- v1 is the special record, v2 is the standard one

      if v1.valid = '0' then

        -- initialization record - ``smaller'' than all standard records

        return true;

      else

        -- end record - ``bigger'' than all standard records

        return false;

      end if;

    elsif (v1.init = '0') and (v2.init = '1') then

      -- v2 is the special record, v1 is the standard one      

      if (v2.valid = '0') then

        -- v2 is the initialization record - it is ``smaller'' than standard record v1

        return false;

      else

        -- v2 is the end record - it is ``bigger'' than standard record v1

        return true;

      end if;

    elsif (v1.init = '1') and (v2.init = '1') then

      -- both v1 and v2 are special records

      if (v1.valid = '0') and (v2.valid = '1') then

        -- v1 - initial record, v2 - end record

        return true;

      else

        -- v1 is end record, so it is ``bigger'' or ``equal'' to other records

        return false;

      end if;

    elsif (v1.init = '0') and (v2.init = '0') then

      -- We compare standard words

      -- We must consider the fact, that in longer sequences of data records

      -- the sort keys may wrap around

      -- therefore we perform subtraction modulo

      -- 2**DATA_REC_SORT_KEY_WIDTH and check the MSB

      dcomp := v1.d_key-v2.d_key;

      if dcomp(DATA_REC_SORT_KEY_WIDTH-1) = '1' then

      --if signed(v1.d_key - v2.d_key)<0 then -- old implementation

        return true;

      elsif v2.d_key = v1.d_key then

        if v2.valid = '1' then

          return true;

        else

          -- Empty data records should wait

          return false;

        end if;

      else

        return false;

      end if;

    else

      --assert false report "Wrong records in sort_cmp_lt" severity error;

      return false;

    end if;

    return false;                       -- should never happen

  end sort_cmp_lt;

  --procedure wrstlv (

  --  rline         : inout string;

  --  constant vect :       std_logic_vector) is

  --begin  -- stlv2str

  --  for i in vect'left downto vect'right loop

  --    case vect(i) is

  --      when 'U'    => write(line(rline), string'("u"));

  --      when 'Z'    => write(line(rline), string'("z"));

  --      when 'X'    => write(line(rline), string'("x"));

  --      when 'L'    => write(line(rline), string'("L"));

  --      when 'H'    => write(line(rline), string'("H"));

  --      when '1'    => write(line(rline), string'("1"));

  --      when '0'    => write(line(rline), string'("0"));

  --      when others => write(line(rline), string'("?"));

  --    end case;

  --  end loop;  -- i

  --end wrstlv;

end sorter_pkg;