1 |
2 |
wzab |
-------------------------------------------------------------------------------
|
2 |
|
|
-- Title : Definitions for heap-sorter
|
3 |
|
|
-- Project : heap-sorter
|
4 |
|
|
-------------------------------------------------------------------------------
|
5 |
|
|
-- File : sorter_pkg.vhd
|
6 |
|
|
-- Author : Wojciech M. Zabolotny <wzab@ise.pw.edu.pl>
|
7 |
|
|
-- Company :
|
8 |
|
|
-- Created : 2010-05-14
|
9 |
|
|
-- Last update: 2011-07-11
|
10 |
|
|
-- Platform :
|
11 |
|
|
-- Standard : VHDL'93
|
12 |
|
|
-------------------------------------------------------------------------------
|
13 |
|
|
-- Description:
|
14 |
|
|
-------------------------------------------------------------------------------
|
15 |
|
|
-- Copyright (c) 2010 Wojciech M. Zabolotny
|
16 |
|
|
-- This file is published under the BSD license, so you can freely adapt
|
17 |
|
|
-- it for your own purposes.
|
18 |
|
|
-- Additionally this design has been described in my article:
|
19 |
|
|
-- Wojciech M. Zabolotny, "Dual port memory based Heapsort implementation
|
20 |
|
|
-- for FPGA", Proc. SPIE 8008, 80080E (2011); doi:10.1117/12.905281
|
21 |
|
|
-- I'd be glad if you cite this article when you publish something based
|
22 |
|
|
-- on my design.
|
23 |
|
|
-------------------------------------------------------------------------------
|
24 |
|
|
-- Revisions :
|
25 |
|
|
-- Date Version Author Description
|
26 |
|
|
-- 2010-05-14 1.0 wzab Created
|
27 |
|
|
-------------------------------------------------------------------------------
|
28 |
|
|
library ieee;
|
29 |
|
|
use ieee.std_logic_1164.all;
|
30 |
|
|
use ieee.numeric_std.all;
|
31 |
|
|
use ieee.std_logic_textio.all;
|
32 |
|
|
use std.textio.all;
|
33 |
|
|
library work;
|
34 |
|
|
use work.sys_config.all;
|
35 |
|
|
|
36 |
|
|
package sorter_pkg is
|
37 |
|
|
constant DATA_REC_WIDTH : integer := DATA_REC_SORT_KEY_WIDTH +
|
38 |
|
|
DATA_REC_PAYLOAD_WIDTH + 2;
|
39 |
|
|
|
40 |
|
|
|
41 |
|
|
subtype T_SORT_KEY is unsigned (DATA_REC_SORT_KEY_WIDTH - 1 downto 0);
|
42 |
|
|
subtype T_PAYLOAD is std_logic_vector(DATA_REC_PAYLOAD_WIDTH - 1 downto 0);
|
43 |
|
|
|
44 |
|
|
--alias T_SORT_KEY is unsigned (12 downto 0);
|
45 |
|
|
type T_DATA_REC is record
|
46 |
|
|
d_key : T_SORT_KEY;
|
47 |
|
|
init : std_logic;
|
48 |
|
|
valid : std_logic;
|
49 |
|
|
d_payload : T_PAYLOAD;
|
50 |
|
|
end record;
|
51 |
|
|
|
52 |
|
|
-- Special constant used to initially fill the sorter
|
53 |
|
|
-- Must be sorted so, that is smaller, than any other data
|
54 |
|
|
constant DATA_REC_INIT_DATA : T_DATA_REC := (
|
55 |
|
|
d_key => to_unsigned(0, DATA_REC_SORT_KEY_WIDTH),
|
56 |
|
|
init => '1',
|
57 |
|
|
valid => '0',
|
58 |
|
|
d_payload => (others => '0')
|
59 |
|
|
);
|
60 |
|
|
|
61 |
|
|
-- Special constant used to ``flush'' the sorter at the end
|
62 |
|
|
constant DATA_REC_END_DATA : T_DATA_REC := (
|
63 |
|
|
d_key => to_unsigned(0, DATA_REC_SORT_KEY_WIDTH),
|
64 |
|
|
init => '1',
|
65 |
|
|
valid => '1',
|
66 |
|
|
d_payload => (others => '0')
|
67 |
|
|
);
|
68 |
|
|
|
69 |
|
|
|
70 |
|
|
function sort_cmp_lt (
|
71 |
|
|
constant v1 : T_DATA_REC;
|
72 |
|
|
constant v2 : T_DATA_REC)
|
73 |
|
|
return boolean;
|
74 |
|
|
|
75 |
|
|
function tdrec2stlv (
|
76 |
|
|
constant drec : T_DATA_REC)
|
77 |
|
|
return std_logic_vector;
|
78 |
|
|
|
79 |
|
|
function stlv2tdrec (
|
80 |
|
|
constant dstlv : std_logic_vector)
|
81 |
|
|
return T_DATA_REC;
|
82 |
|
|
|
83 |
|
|
procedure wrstlv (
|
84 |
|
|
rline : inout line;
|
85 |
|
|
constant vect : std_logic_vector);
|
86 |
|
|
|
87 |
|
|
file reports : text open write_mode is "STD_OUTPUT";
|
88 |
|
|
|
89 |
|
|
end sorter_pkg;
|
90 |
|
|
|
91 |
|
|
package body sorter_pkg is
|
92 |
|
|
|
93 |
|
|
function stlv2tdrec (
|
94 |
|
|
constant dstlv : std_logic_vector)
|
95 |
|
|
return T_DATA_REC is
|
96 |
|
|
variable result : T_DATA_REC;
|
97 |
|
|
variable j : integer := 0;
|
98 |
|
|
begin -- stlv2drec
|
99 |
|
|
j := 0;
|
100 |
|
|
result.d_key := unsigned(dstlv(j-1+DATA_REC_SORT_KEY_WIDTH downto j));
|
101 |
|
|
j := j+DATA_REC_SORT_KEY_WIDTH;
|
102 |
|
|
result.valid := dstlv(j);
|
103 |
|
|
j := j+1;
|
104 |
|
|
result.init := dstlv(j);
|
105 |
|
|
j := j+1;
|
106 |
|
|
result.d_payload := dstlv(j-1+DATA_REC_PAYLOAD_WIDTH downto j);
|
107 |
|
|
j := j+DATA_REC_PAYLOAD_WIDTH;
|
108 |
|
|
return result;
|
109 |
|
|
end stlv2tdrec;
|
110 |
|
|
|
111 |
|
|
function tdrec2stlv (
|
112 |
|
|
constant drec : T_DATA_REC)
|
113 |
|
|
return std_logic_vector is
|
114 |
|
|
variable result : std_logic_vector(DATA_REC_WIDTH-1 downto 0);
|
115 |
|
|
variable j : integer := 0;
|
116 |
|
|
begin -- tdrec2stlv
|
117 |
|
|
j := 0;
|
118 |
|
|
result(j-1+DATA_REC_SORT_KEY_WIDTH downto j) := std_logic_vector(drec.d_key);
|
119 |
|
|
j := j+DATA_REC_SORT_KEY_WIDTH;
|
120 |
|
|
result(j) := drec.valid;
|
121 |
|
|
j := j+1;
|
122 |
|
|
result(j) := drec.init;
|
123 |
|
|
j := j+1;
|
124 |
|
|
result(j-1+DATA_REC_PAYLOAD_WIDTH downto j) := std_logic_vector(drec.d_payload);
|
125 |
|
|
j := j+DATA_REC_PAYLOAD_WIDTH;
|
126 |
|
|
return result;
|
127 |
|
|
end tdrec2stlv;
|
128 |
|
|
|
129 |
|
|
|
130 |
|
|
-- Function sort_cmp_lt returns TRUE when the first opperand is ``less'' than
|
131 |
|
|
-- the second one
|
132 |
|
|
function sort_cmp_lt (
|
133 |
|
|
constant v1 : T_DATA_REC;
|
134 |
|
|
constant v2 : T_DATA_REC)
|
135 |
|
|
return boolean is
|
136 |
|
|
variable rline : line;
|
137 |
|
|
variable dcomp : unsigned(DATA_REC_SORT_KEY_WIDTH-1 downto 0) := (others => '0');
|
138 |
|
|
begin -- sort_cmp_lt
|
139 |
|
|
-- Check the special cases
|
140 |
|
|
if (v1.init = '1') and (v2.init = '0') then
|
141 |
|
|
-- v1 is the special record, v2 is the standard one
|
142 |
|
|
if v1.valid = '0' then
|
143 |
|
|
-- initialization record - ``smaller'' than all standard records
|
144 |
|
|
return true;
|
145 |
|
|
else
|
146 |
|
|
-- end record - ``bigger'' than all standard records
|
147 |
|
|
return false;
|
148 |
|
|
end if;
|
149 |
|
|
elsif (v1.init = '0') and (v2.init = '1') then
|
150 |
|
|
-- v2 is the special record, v1 is the standard one
|
151 |
|
|
if (v2.valid = '0') then
|
152 |
|
|
-- v2 is the initialization record - it is ``smaller'' than standard record v1
|
153 |
|
|
return false;
|
154 |
|
|
else
|
155 |
|
|
-- v2 is the end record - it is ``bigger'' than standard record v1
|
156 |
|
|
return true;
|
157 |
|
|
end if;
|
158 |
|
|
elsif (v1.init = '1') and (v2.init = '1') then
|
159 |
|
|
-- both v1 and v2 are special records
|
160 |
|
|
if (v1.valid = '0') and (v2.valid = '1') then
|
161 |
|
|
-- v1 - initial record, v2 - end record
|
162 |
|
|
return true;
|
163 |
|
|
else
|
164 |
|
|
-- v1 is end record, so it is ``bigger'' or ``equal'' to other records
|
165 |
|
|
return false;
|
166 |
|
|
end if;
|
167 |
|
|
elsif (v1.init = '0') and (v2.init = '0') then
|
168 |
|
|
-- We compare standard words
|
169 |
|
|
-- We must consider the fact, that in longer sequences of data records
|
170 |
|
|
-- the sort keys may wrap around
|
171 |
|
|
-- therefore we perform subtraction modulo
|
172 |
|
|
-- 2**DATA_REC_SORT_KEY_WIDTH and check the MSB
|
173 |
|
|
dcomp := v1.d_key-v2.d_key;
|
174 |
|
|
if dcomp(DATA_REC_SORT_KEY_WIDTH-1) = '1' then
|
175 |
|
|
--if signed(v1.d_key - v2.d_key)<0 then -- old implementation
|
176 |
|
|
return true;
|
177 |
|
|
elsif v2.d_key = v1.d_key then
|
178 |
|
|
if v2.valid = '1' then
|
179 |
|
|
return true;
|
180 |
|
|
else
|
181 |
|
|
-- Empty data records should wait
|
182 |
|
|
return false;
|
183 |
|
|
end if;
|
184 |
|
|
else
|
185 |
|
|
return false;
|
186 |
|
|
end if;
|
187 |
|
|
else
|
188 |
|
|
assert false report "Wrong records in sort_cmp_lt" severity error;
|
189 |
|
|
return false;
|
190 |
|
|
end if;
|
191 |
|
|
return false; -- should never happen
|
192 |
|
|
end sort_cmp_lt;
|
193 |
|
|
|
194 |
|
|
|
195 |
|
|
procedure wrstlv (
|
196 |
|
|
rline : inout line;
|
197 |
|
|
constant vect : std_logic_vector) is
|
198 |
|
|
begin -- stlv2str
|
199 |
|
|
for i in vect'left downto vect'right loop
|
200 |
|
|
case vect(i) is
|
201 |
|
|
when 'U' => write(rline, string'("u"));
|
202 |
|
|
when 'Z' => write(rline, string'("z"));
|
203 |
|
|
when 'X' => write(rline, string'("x"));
|
204 |
|
|
when 'L' => write(rline, string'("L"));
|
205 |
|
|
when 'H' => write(rline, string'("H"));
|
206 |
|
|
when '1' => write(rline, string'("1"));
|
207 |
|
|
when '0' => write(rline, string'("0"));
|
208 |
|
|
when others => write(rline, string'("?"));
|
209 |
|
|
end case;
|
210 |
|
|
end loop; -- i
|
211 |
|
|
end wrstlv;
|
212 |
|
|
|
213 |
|
|
end sorter_pkg;
|
214 |
|
|
|