-
Notifications
You must be signed in to change notification settings - Fork 0
/
bubble_sort_network.vhd
126 lines (126 loc) · 5.65 KB
/
bubble_sort_network.vhd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
-----------------------------------------------------------------------------------
--! @file bubble_sort_network.vhd
--! @brief Bubble Sort Network Package :
--! @version 1.4.1
--! @date 2022/11/1
--! @author Ichiro Kawazome <ichiro_k@ca2.so-net.ne.jp>
-----------------------------------------------------------------------------------
--
-- Copyright (C) 2020-2022 Ichiro Kawazome
-- All rights reserved.
--
-- Redistribution and use in source and binary forms, with or without
-- modification, are permitted provided that the following conditions
-- are met:
--
-- 1. Redistributions of source code must retain the above copyright
-- notice, this list of conditions and the following disclaimer.
--
-- 2. Redistributions in binary form must reproduce the above copyright
-- notice, this list of conditions and the following disclaimer in
-- the documentation and/or other materials provided with the
-- distribution.
--
-- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-- "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-- OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-- SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-- LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-- DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-- THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-- (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
--
-----------------------------------------------------------------------------------
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
library Merge_Sorter;
use Merge_Sorter.Sorting_Network;
package Bubble_Sort_Network is
-------------------------------------------------------------------------------
--
-------------------------------------------------------------------------------
function New_Network(
LO : integer;
HI : integer;
ORDER : integer
) return Sorting_Network.Param_Type;
-------------------------------------------------------------------------------
--
-------------------------------------------------------------------------------
function New_Network(
LO : integer;
HI : integer;
ORDER : integer;
QUEUE : Sorting_Network.Queue_Param_Type
) return Sorting_Network.Param_Type;
end Bubble_Sort_Network;
-----------------------------------------------------------------------------------
--
-----------------------------------------------------------------------------------
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
library Merge_Sorter;
use Merge_Sorter.Sorting_Network;
package body Bubble_Sort_Network is
-------------------------------------------------------------------------------
--
-------------------------------------------------------------------------------
procedure bubble_sort(
variable NETWORK : inout Sorting_Network.Param_Type;
START_STAGE : in integer;
LO : in integer;
HI : in integer
) is
variable comp_stage : integer;
variable last_stage : integer;
begin
if (HI - LO > 0) then
comp_stage := START_STAGE;
for net in HI-1 downto LO loop
Sorting_Network.Add_Comparator(NETWORK, comp_stage, net, net+1, TRUE);
if (NETWORK.Stage_Hi < comp_stage) then
NETWORK.Stage_Hi := comp_stage;
end if;
comp_stage := comp_stage + 1;
end loop;
NETWORK.Stage_Size := NETWORK.Stage_Hi - NETWORK.Stage_Lo + 1;
bubble_sort(NETWORK, START_STAGE + 2, LO + 1, HI);
end if;
end procedure;
-------------------------------------------------------------------------------
--
-------------------------------------------------------------------------------
function New_Network(
LO : integer;
HI : integer;
ORDER : integer
) return Sorting_Network.Param_Type
is
variable network : Sorting_Network.Param_Type;
begin
network := Sorting_Network.New_Network(LO,HI,ORDER);
bubble_sort(network, network.Stage_Lo, network.Lo, network.Hi);
return network;
end function;
-------------------------------------------------------------------------------
--
-------------------------------------------------------------------------------
function New_Network(
LO : integer;
HI : integer;
ORDER : integer;
QUEUE : Sorting_Network.Queue_Param_Type
) return Sorting_Network.Param_Type
is
variable network : Sorting_Network.Param_Type;
begin
network := New_Network(LO,HI,ORDER);
Sorting_Network.Set_Queue_Param(network, QUEUE);
return network;
end function;
end Bubble_Sort_Network;