-
Notifications
You must be signed in to change notification settings - Fork 43
/
Arithmetic_Predicates_Binary_Multiprecision.html
197 lines (164 loc) · 7.36 KB
/
Arithmetic_Predicates_Binary_Multiprecision.html
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Arithmetic_Predicates_Binary_Multiprecision.html">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="Given two integers, `A` and `B`, derives all the possible arithmetic predictates (equal, greater-than, less-than-equal, etc...) as both signed and unsigned comparisons. Uses multiprecision arithmetic to allow handling very wide integers.">
<title>Arithmetic Predicates Binary Multiprecision</title>
</head>
<body>
<p class="inline bordered"><b><a href="./Arithmetic_Predicates_Binary_Multiprecision.v">Source</a></b></p>
<p class="inline bordered"><b><a href="./legal.html">License</a></b></p>
<p class="inline bordered"><b><a href="./index.html">Index</a></b></p>
<h1>Arithmetic Predicates (Binary), using Multiprecision Arithmetic</h1>
<p>Given two integers, <code>A</code> and <code>B</code>, derives all the possible arithmetic
predictates (equal, greater-than, less-than-equal, etc...) as both signed
and unsigned comparisons. Uses multiprecision arithmetic to allow handling
very wide integers.</p>
<p>This code implements "<em>How the Computer Sets the Comparison Predicates</em>" in
Section 2-12 of Henry S. Warren, Jr.'s <a href="./reading.html#Warren2013">Hacker's
Delight</a>, which describes how to compute all the
integer comparisons, based on the condition flags generated after
a (2's-complement) subtraction <code>A-B</code>.</p>
<h2>Multiprecision Implementation</h2>
<p>This version uses a <a href="./Adder_Subtractor_Binary_Multiprecision.html">Multiprecision Binary
Adder/Subtractor</a> to
calculate predicates on very wide integers without reducing operating speed
or greatly increasing area, at the price of a few cycles of latency per
result (roughly <code>ceil(WORD_WIDTH / STEP_WORD_WIDTH</code>) cycles). If you need
results every cycle, use a conventional <a href="./Arithmetic_Predicates_Binary.html">Arithmetic
Predicates</a> and
<a href="./Register_Pipeline_Simple.html">pipeline</a> the inputs.</p>
<pre>
`default_nettype none
module <a href="./Arithmetic_Predicates_Binary_Multiprecision.html">Arithmetic_Predicates_Binary_Multiprecision</a>
#(
parameter WORD_WIDTH = 0,
parameter STEP_WORD_WIDTH = 0,
parameter PIPELINE_DEPTH = -1
)
(
input wire clock,
input wire clock_enable,
input wire clear,
input wire input_valid,
output wire input_ready,
input wire [WORD_WIDTH-1:0] A,
input wire [WORD_WIDTH-1:0] B,
output wire output_valid,
input wire output_ready,
output reg A_eq_B,
output reg A_lt_B_unsigned,
output reg A_lte_B_unsigned,
output reg A_gt_B_unsigned,
output reg A_gte_B_unsigned,
output reg A_lt_B_signed,
output reg A_lte_B_signed,
output reg A_gt_B_signed,
output reg A_gte_B_signed
);
localparam ZERO = {WORD_WIDTH{1'b0}};
initial begin
A_eq_B = 1'b0;
A_lt_B_unsigned = 1'b0;
A_lte_B_unsigned = 1'b0;
A_gt_B_unsigned = 1'b0;
A_gte_B_unsigned = 1'b0;
A_lt_B_signed = 1'b0;
A_lte_B_signed = 1'b0;
A_gt_B_signed = 1'b0;
A_gte_B_signed = 1'b0;
end
</pre>
<p>First, let's subtract B from A, and get the the carry-out and overflow
bits.</p>
<p>NOTE: we cannot pipeline here, as there is a loop inside the
Adder_Subtractor_Binary_Multiprecision. We pipeline the raw results later
below.</p>
<pre>
wire [WORD_WIDTH-1:0] difference_raw;
wire carry_out_raw;
wire overflow_signed_raw;
wire output_valid_raw;
wire output_ready_raw;
<a href="./Adder_Subtractor_Binary_Multiprecision.html">Adder_Subtractor_Binary_Multiprecision</a>
#(
.WORD_WIDTH (WORD_WIDTH),
.STEP_WORD_WIDTH (STEP_WORD_WIDTH)
)
subtraction
(
.clock (clock),
.clock_enable (clock_enable),
.clear (clear),
.input_valid (input_valid),
.input_ready (input_ready),
.add_sub (1'b1), // 0/1 -> A+B/A-B
.A (A),
.B (B),
.output_valid (output_valid_raw),
.output_ready (output_ready_raw),
.sum (difference_raw),
.carry_out (carry_out_raw),
// verilator lint_off PINCONNECTEMPTY
.carries (),
// verilator lint_on PINCONNECTEMPTY
.overflow (overflow_signed_raw)
);
</pre>
<p>Since this module is intended to handle very wide integers, let's add
optional pipelining here to both retime into the final predicate
calculation logic, and to allow flexible placement of logic.</p>
<pre>
wire [WORD_WIDTH-1:0] difference;
wire carry_out;
wire overflow_signed;
localparam PIPELINE_WIDTH = WORD_WIDTH + 1 + 1;
<a href="./Skid_Buffer_Pipeline.html">Skid_Buffer_Pipeline</a>
#(
.WORD_WIDTH (PIPELINE_WIDTH),
.PIPE_DEPTH (PIPELINE_DEPTH)
)
subtraction_results
(
// If PIPE_DEPTH is zero, these are unused
// verilator lint_off UNUSED
.clock (clock),
.clear (clear),
// verilator lint_on UNUSED
.input_valid (output_valid_raw),
.input_ready (output_ready_raw),
.input_data ({difference_raw, carry_out_raw, overflow_signed_raw}),
.output_valid (output_valid),
.output_ready (output_ready),
.output_data ({difference, carry_out, overflow_signed})
);
</pre>
<p>We now have enough information to compute all the arithmetic predicates.
Note that in 2's-complement subtraction, the meaning of the carry-out bit
is reversed, and that special care must be taken for signed comparisons to
distinguish the carry-out from an overflow. This code takes advantage of
the sequential evaluation of blocking assignments in a Verilog procedural
block to re-use and optimize the logic expressions.</p>
<pre>
reg negative = 1'b0;
always @(*) begin
negative = (difference[WORD_WIDTH-1] == 1'b1);
A_eq_B = (difference == ZERO);
A_lt_B_unsigned = (carry_out == 1'b0);
A_lte_B_unsigned = (A_lt_B_unsigned == 1'b1) || (A_eq_B == 1'b1);
A_gte_B_unsigned = (carry_out == 1'b1);
A_gt_B_unsigned = (A_gte_B_unsigned == 1'b1) && (A_eq_B == 1'b0);
A_lt_B_signed = (negative != overflow_signed);
A_lte_B_signed = (A_lt_B_signed == 1'b1) || (A_eq_B == 1'b1);
A_gte_B_signed = (negative == overflow_signed);
A_gt_B_signed = (A_gte_B_signed == 1'b1) && (A_eq_B == 1'b0);
end
endmodule
</pre>
<hr>
<p><a href="./index.html">Back to FPGA Design Elements</a>
<center><a href="https://fpgacpu.ca/">fpgacpu.ca</a></center>
</body>
</html>