1 # SPDX-License-Identifier: LGPL-2.1-or-later
2 # See Notices.txt for copyright information
3 """ Core of the div/rem/sqrt/rsqrt pipeline.
5 Special case handling, input/output conversion, and muxid handling are handled
6 outside of these classes.
8 Algorithms based on ``algorithm.FixedUDivRemSqrtRSqrt``.
12 ``dividend == quotient_root * divisor_radicand``
14 ``divisor_radicand == quotient_root * quotient_root``
16 ``1 == quotient_root * quotient_root * divisor_radicand``
18 The remainder is the left-hand-side of the comparison minus the
19 right-hand-side of the comparison in the above formulas.
21 from nmigen
import (Elaboratable
, Module
, Signal
, Const
, Mux
)
25 class DivPipeCoreConfig
:
26 """ Configuration for core of the div/rem/sqrt/rsqrt pipeline.
28 :attribute bit_width: base bit-width.
29 :attribute fract_width: base fract-width. Specifies location of base-2
31 :attribute log2_radix: number of bits of ``quotient_root`` that should be
32 computed per pipeline stage.
35 def __init__(self
, bit_width
, fract_width
, log2_radix
):
36 """ Create a ``DivPipeCoreConfig`` instance. """
37 self
.bit_width
= bit_width
38 self
.fract_width
= fract_width
39 self
.log2_radix
= log2_radix
43 return f
"DivPipeCoreConfig({self.bit_width}, " \
44 + f
"{self.fract_width}, {self.log2_radix})"
47 def num_calculate_stages(self
):
48 """ Get the number of ``DivPipeCoreCalculateStage`` needed. """
49 return (self
.bit_width
+ self
.log2_radix
- 1) // self
.log2_radix
52 class DivPipeCoreOperation(enum
.IntEnum
):
53 """ Operation for ``DivPipeCore``.
55 :attribute UDivRem: unsigned divide/remainder.
56 :attribute SqrtRem: square-root/remainder.
57 :attribute RSqrtRem: reciprocal-square-root/remainder.
65 def create_signal(cls
, *, src_loc_at
=0, **kwargs
):
66 """ Create a signal that can contain a ``DivPipeCoreOperation``. """
67 return Signal(min=int(min(cls
)),
69 src_loc_at
=(src_loc_at
+ 1),
74 class DivPipeCoreInputData
:
75 """ input data type for ``DivPipeCore``.
77 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
78 configuration to be used.
79 :attribute dividend: dividend for div/rem. Signal with a bit-width of
80 ``core_config.bit_width + core_config.fract_width`` and a fract-width
81 of ``core_config.fract_width * 2`` bits.
82 :attribute divisor_radicand: divisor for div/rem and radicand for
83 sqrt/rsqrt. Signal with a bit-width of ``core_config.bit_width`` and a
84 fract-width of ``core_config.fract_width`` bits.
85 :attribute operation: the ``DivPipeCoreOperation`` to be computed.
88 def __init__(self
, core_config
, reset_less
=True):
89 """ Create a ``DivPipeCoreInputData`` instance. """
90 self
.core_config
= core_config
91 self
.dividend
= Signal(core_config
.bit_width
+ core_config
.fract_width
,
92 reset_less
=reset_less
)
93 self
.divisor_radicand
= Signal(core_config
.bit_width
,
94 reset_less
=reset_less
)
96 # FIXME: this goes into (is replaced by) self.ctx.op
98 DivPipeCoreOperation
.create_signal(reset_less
=reset_less
)
101 """ Get member signals. """
103 yield self
.divisor_radicand
104 yield self
.operation
# FIXME: delete. already covered by self.ctx
107 """ Assign member signals. """
108 return [self
.dividend
.eq(rhs
.dividend
),
109 self
.divisor_radicand
.eq(rhs
.divisor_radicand
),
110 self
.operation
.eq(rhs
.operation
), # FIXME: delete.
114 class DivPipeCoreInterstageData
:
115 """ interstage data type for ``DivPipeCore``.
117 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
118 configuration to be used.
119 :attribute divisor_radicand: divisor for div/rem and radicand for
120 sqrt/rsqrt. Signal with a bit-width of ``core_config.bit_width`` and a
121 fract-width of ``core_config.fract_width`` bits.
122 :attribute operation: the ``DivPipeCoreOperation`` to be computed.
123 :attribute quotient_root: the quotient or root part of the result of the
124 operation. Signal with a bit-width of ``core_config.bit_width`` and a
125 fract-width of ``core_config.fract_width`` bits.
126 :attribute root_times_radicand: ``quotient_root * divisor_radicand``.
127 Signal with a bit-width of ``core_config.bit_width * 2`` and a
128 fract-width of ``core_config.fract_width * 2`` bits.
129 :attribute compare_lhs: The left-hand-side of the comparison in the
130 equation to be solved. Signal with a bit-width of
131 ``core_config.bit_width * 3`` and a fract-width of
132 ``core_config.fract_width * 3`` bits.
133 :attribute compare_rhs: The right-hand-side of the comparison in the
134 equation to be solved. Signal with a bit-width of
135 ``core_config.bit_width * 3`` and a fract-width of
136 ``core_config.fract_width * 3`` bits.
139 def __init__(self
, core_config
, reset_less
=True):
140 """ Create a ``DivPipeCoreInterstageData`` instance. """
141 self
.core_config
= core_config
142 self
.divisor_radicand
= Signal(core_config
.bit_width
,
143 reset_less
=reset_less
)
144 # FIXME: delete self.operation. already covered by self.ctx.op
146 DivPipeCoreOperation
.create_signal(reset_less
=reset_less
)
147 self
.quotient_root
= Signal(core_config
.bit_width
,
148 reset_less
=reset_less
)
149 self
.root_times_radicand
= Signal(core_config
.bit_width
* 2,
150 reset_less
=reset_less
)
151 self
.compare_lhs
= Signal(core_config
.bit_width
* 3,
152 reset_less
=reset_less
)
153 self
.compare_rhs
= Signal(core_config
.bit_width
* 3,
154 reset_less
=reset_less
)
157 """ Get member signals. """
158 yield self
.divisor_radicand
159 yield self
.operation
# FIXME: delete. already in self.ctx.op
160 yield self
.quotient_root
161 yield self
.root_times_radicand
162 yield self
.compare_lhs
163 yield self
.compare_rhs
166 """ Assign member signals. """
167 return [self
.divisor_radicand
.eq(rhs
.divisor_radicand
),
168 self
.operation
.eq(rhs
.operation
), # FIXME: delete.
169 self
.quotient_root
.eq(rhs
.quotient_root
),
170 self
.root_times_radicand
.eq(rhs
.root_times_radicand
),
171 self
.compare_lhs
.eq(rhs
.compare_lhs
),
172 self
.compare_rhs
.eq(rhs
.compare_rhs
)]
175 class DivPipeCoreOutputData
:
176 """ output data type for ``DivPipeCore``.
178 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
179 configuration to be used.
180 :attribute quotient_root: the quotient or root part of the result of the
181 operation. Signal with a bit-width of ``core_config.bit_width`` and a
182 fract-width of ``core_config.fract_width`` bits.
183 :attribute remainder: the remainder part of the result of the operation.
184 Signal with a bit-width of ``core_config.bit_width * 3`` and a
185 fract-width of ``core_config.fract_width * 3`` bits.
188 def __init__(self
, core_config
, reset_less
=True):
189 """ Create a ``DivPipeCoreOutputData`` instance. """
190 self
.core_config
= core_config
191 self
.quotient_root
= Signal(core_config
.bit_width
,
192 reset_less
=reset_less
)
193 self
.remainder
= Signal(core_config
.bit_width
* 3,
194 reset_less
=reset_less
)
197 """ Get member signals. """
198 yield self
.quotient_root
203 """ Assign member signals. """
204 return [self
.quotient_root
.eq(rhs
.quotient_root
),
205 self
.remainder
.eq(rhs
.remainder
)]
208 class DivPipeCoreSetupStage(Elaboratable
):
209 """ Setup Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
211 def __init__(self
, core_config
):
212 """ Create a ``DivPipeCoreSetupStage`` instance."""
213 self
.core_config
= core_config
214 self
.i
= self
.ispec()
215 self
.o
= self
.ospec()
218 """ Get the input spec for this pipeline stage."""
219 return DivPipeCoreInputData(self
.core_config
)
222 """ Get the output spec for this pipeline stage."""
223 return DivPipeCoreInterstageData(self
.core_config
)
225 def setup(self
, m
, i
):
226 """ Pipeline stage setup. """
227 m
.submodules
.div_pipe_core_setup
= self
228 m
.d
.comb
+= self
.i
.eq(i
)
230 def process(self
, i
):
231 """ Pipeline stage process. """
232 return self
.o
# return processed data (ignore i)
234 def elaborate(self
, platform
):
235 """ Elaborate into ``Module``. """
238 m
.d
.comb
+= self
.o
.divisor_radicand
.eq(self
.i
.divisor_radicand
)
239 m
.d
.comb
+= self
.o
.quotient_root
.eq(0)
240 m
.d
.comb
+= self
.o
.root_times_radicand
.eq(0)
242 with m
.If(self
.i
.operation
== DivPipeCoreOperation
.UDivRem
):
243 m
.d
.comb
+= self
.o
.compare_lhs
.eq(self
.i
.dividend
244 << self
.core_config
.fract_width
)
245 with m
.Elif(self
.i
.operation
== DivPipeCoreOperation
.SqrtRem
):
246 m
.d
.comb
+= self
.o
.compare_lhs
.eq(
247 self
.i
.divisor_radicand
<< (self
.core_config
.fract_width
* 2))
248 with m
.Else(): # DivPipeCoreOperation.RSqrtRem
249 m
.d
.comb
+= self
.o
.compare_lhs
.eq(
250 1 << (self
.core_config
.fract_width
* 3))
252 m
.d
.comb
+= self
.o
.compare_rhs
.eq(0)
253 m
.d
.comb
+= self
.o
.operation
.eq(self
.i
.operation
)
258 class DivPipeCoreCalculateStage(Elaboratable
):
259 """ Calculate Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
261 def __init__(self
, core_config
, stage_index
):
262 """ Create a ``DivPipeCoreSetupStage`` instance. """
263 self
.core_config
= core_config
264 assert stage_index
in range(core_config
.num_calculate_stages
)
265 self
.stage_index
= stage_index
266 self
.i
= self
.ispec()
267 self
.o
= self
.ospec()
270 """ Get the input spec for this pipeline stage. """
271 return DivPipeCoreInterstageData(self
.core_config
)
274 """ Get the output spec for this pipeline stage. """
275 return DivPipeCoreInterstageData(self
.core_config
)
277 def setup(self
, m
, i
):
278 """ Pipeline stage setup. """
279 setattr(m
.submodules
,
280 f
"div_pipe_core_calculate_{self.stage_index}",
282 m
.d
.comb
+= self
.i
.eq(i
)
284 def process(self
, i
):
285 """ Pipeline stage process. """
288 def elaborate(self
, platform
):
289 """ Elaborate into ``Module``. """
291 m
.d
.comb
+= self
.o
.divisor_radicand
.eq(self
.i
.divisor_radicand
)
292 m
.d
.comb
+= self
.o
.operation
.eq(self
.i
.operation
)
293 m
.d
.comb
+= self
.o
.compare_lhs
.eq(self
.i
.compare_lhs
)
294 log2_radix
= self
.core_config
.log2_radix
295 current_shift
= self
.core_config
.bit_width
296 current_shift
-= self
.stage_index
* log2_radix
297 log2_radix
= min(log2_radix
, current_shift
)
298 assert log2_radix
> 0
299 current_shift
-= log2_radix
300 radix
= 1 << log2_radix
301 trial_compare_rhs_values
= []
303 for trial_bits
in range(radix
):
304 shifted_trial_bits
= Const(trial_bits
, log2_radix
) << current_shift
305 shifted_trial_bits_sqrd
= shifted_trial_bits
* shifted_trial_bits
308 div_rhs
= self
.i
.compare_rhs
309 div_factor1
= self
.i
.divisor_radicand
* shifted_trial_bits
310 div_rhs
+= div_factor1
<< self
.core_config
.fract_width
313 sqrt_rhs
= self
.i
.compare_rhs
314 sqrt_factor1
= self
.i
.quotient_root
* (shifted_trial_bits
<< 1)
315 sqrt_rhs
+= sqrt_factor1
<< self
.core_config
.fract_width
316 sqrt_factor2
= shifted_trial_bits_sqrd
317 sqrt_rhs
+= sqrt_factor2
<< self
.core_config
.fract_width
320 rsqrt_rhs
= self
.i
.compare_rhs
321 rsqrt_rhs
+= self
.i
.root_times_radicand
* (shifted_trial_bits
<< 1)
322 rsqrt_rhs
+= self
.i
.divisor_radicand
* shifted_trial_bits_sqrd
324 trial_compare_rhs
= Signal
.like(
325 self
.o
.compare_rhs
, name
=f
"trial_compare_rhs_{trial_bits}")
327 with m
.If(self
.i
.operation
== DivPipeCoreOperation
.UDivRem
):
328 m
.d
.comb
+= trial_compare_rhs
.eq(div_rhs
)
329 with m
.Elif(self
.i
.operation
== DivPipeCoreOperation
.SqrtRem
):
330 m
.d
.comb
+= trial_compare_rhs
.eq(sqrt_rhs
)
331 with m
.Else(): # DivPipeCoreOperation.RSqrtRem
332 m
.d
.comb
+= trial_compare_rhs
.eq(rsqrt_rhs
)
333 trial_compare_rhs_values
.append(trial_compare_rhs
)
335 pass_flag
= Signal(name
=f
"pass_flag_{trial_bits}")
336 m
.d
.comb
+= pass_flag
.eq(self
.i
.compare_lhs
>= trial_compare_rhs
)
337 pass_flags
.append(pass_flag
)
339 # convert pass_flags to next_bits.
341 # Assumes that for each set bit in pass_flag, all previous bits are
344 # Assumes that pass_flag[0] is always set (since
345 # compare_lhs >= compare_rhs is a pipeline invariant).
347 next_bits
= Signal(log2_radix
)
348 for i
in range(log2_radix
):
350 for j
in range(0, radix
, 1 << i
):
351 bit_value ^
= pass_flags
[j
]
352 m
.d
.comb
+= next_bits
.part(i
, 1).eq(bit_value
)
355 for i
in range(radix
):
356 next_flag
= pass_flags
[i
+ 1] if i
+ 1 < radix
else 0
357 next_compare_rhs |
= Mux(pass_flags
[i
] & ~next_flag
,
358 trial_compare_rhs_values
[i
],
361 m
.d
.comb
+= self
.o
.compare_rhs
.eq(next_compare_rhs
)
362 m
.d
.comb
+= self
.o
.root_times_radicand
.eq(self
.i
.root_times_radicand
363 + ((self
.i
.divisor_radicand
366 m
.d
.comb
+= self
.o
.quotient_root
.eq(self
.i
.quotient_root
367 |
(next_bits
<< current_shift
))
371 class DivPipeCoreFinalStage(Elaboratable
):
372 """ Final Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
374 def __init__(self
, core_config
):
375 """ Create a ``DivPipeCoreFinalStage`` instance."""
376 self
.core_config
= core_config
377 self
.i
= self
.ispec()
378 self
.o
= self
.ospec()
381 """ Get the input spec for this pipeline stage."""
382 return DivPipeCoreInterstageData(self
.core_config
)
385 """ Get the output spec for this pipeline stage."""
386 return DivPipeCoreOutputData(self
.core_config
)
388 def setup(self
, m
, i
):
389 """ Pipeline stage setup. """
390 m
.submodules
.div_pipe_core_final
= self
391 m
.d
.comb
+= self
.i
.eq(i
)
393 def process(self
, i
):
394 """ Pipeline stage process. """
395 return self
.o
# return processed data (ignore i)
397 def elaborate(self
, platform
):
398 """ Elaborate into ``Module``. """
401 m
.d
.comb
+= self
.o
.quotient_root
.eq(self
.i
.quotient_root
)
402 m
.d
.comb
+= self
.o
.remainder
.eq(self
.i
.compare_lhs
403 - self
.i
.compare_rhs
)