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
, Cat
, Array
)
22 from nmigen
.lib
.coding
import PriorityEncoder
26 class DivPipeCoreConfig
:
27 """ Configuration for core of the div/rem/sqrt/rsqrt pipeline.
29 :attribute bit_width: base bit-width.
30 :attribute fract_width: base fract-width. Specifies location of base-2
32 :attribute log2_radix: number of bits of ``quotient_root`` that should be
33 computed per pipeline stage.
36 def __init__(self
, bit_width
, fract_width
, log2_radix
):
37 """ Create a ``DivPipeCoreConfig`` instance. """
38 self
.bit_width
= bit_width
39 self
.fract_width
= fract_width
40 self
.log2_radix
= log2_radix
44 return f
"DivPipeCoreConfig({self.bit_width}, " \
45 + f
"{self.fract_width}, {self.log2_radix})"
49 """ Get the number of ``DivPipeCoreCalculateStage`` needed. """
50 return (self
.bit_width
+ self
.log2_radix
- 1) // self
.log2_radix
53 class DivPipeCoreOperation(enum
.Enum
):
54 """ Operation for ``DivPipeCore``.
56 :attribute UDivRem: unsigned divide/remainder.
57 :attribute SqrtRem: square-root/remainder.
58 :attribute RSqrtRem: reciprocal-square-root/remainder.
66 """ Convert to int. """
70 def create_signal(cls
, *, src_loc_at
=0, **kwargs
):
71 """ Create a signal that can contain a ``DivPipeCoreOperation``. """
72 return Signal(min=min(map(int, cls
)),
73 max=max(map(int, cls
)) + 2,
74 src_loc_at
=(src_loc_at
+ 1),
75 decoder
=lambda v
: str(cls(v
)),
79 DP
= DivPipeCoreOperation
81 class DivPipeCoreInputData
:
82 """ input data type for ``DivPipeCore``.
84 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
85 configuration to be used.
86 :attribute dividend: dividend for div/rem. Signal with a bit-width of
87 ``core_config.bit_width + core_config.fract_width`` and a fract-width
88 of ``core_config.fract_width * 2`` bits.
89 :attribute divisor_radicand: divisor for div/rem and radicand for
90 sqrt/rsqrt. Signal with a bit-width of ``core_config.bit_width`` and a
91 fract-width of ``core_config.fract_width`` bits.
92 :attribute operation: the ``DivPipeCoreOperation`` to be computed.
95 def __init__(self
, core_config
, reset_less
=True):
96 """ Create a ``DivPipeCoreInputData`` instance. """
97 self
.core_config
= core_config
98 self
.dividend
= Signal(core_config
.bit_width
+ core_config
.fract_width
,
99 reset_less
=reset_less
)
100 self
.divisor_radicand
= Signal(core_config
.bit_width
,
101 reset_less
=reset_less
)
102 self
.operation
= DP
.create_signal(reset_less
=reset_less
)
105 """ Get member signals. """
107 yield self
.divisor_radicand
111 """ Assign member signals. """
112 return [self
.dividend
.eq(rhs
.dividend
),
113 self
.divisor_radicand
.eq(rhs
.divisor_radicand
),
114 self
.operation
.eq(rhs
.operation
),
118 class DivPipeCoreInterstageData
:
119 """ interstage data type for ``DivPipeCore``.
121 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
122 configuration to be used.
123 :attribute divisor_radicand: divisor for div/rem and radicand for
124 sqrt/rsqrt. Signal with a bit-width of ``core_config.bit_width`` and a
125 fract-width of ``core_config.fract_width`` bits.
126 :attribute operation: the ``DivPipeCoreOperation`` to be computed.
127 :attribute quotient_root: the quotient or root part of the result of the
128 operation. Signal with a bit-width of ``core_config.bit_width`` and a
129 fract-width of ``core_config.fract_width`` bits.
130 :attribute root_times_radicand: ``quotient_root * divisor_radicand``.
131 Signal with a bit-width of ``core_config.bit_width * 2`` and a
132 fract-width of ``core_config.fract_width * 2`` bits.
133 :attribute compare_lhs: The left-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.
137 :attribute compare_rhs: The right-hand-side of the comparison in the
138 equation to be solved. Signal with a bit-width of
139 ``core_config.bit_width * 3`` and a fract-width of
140 ``core_config.fract_width * 3`` bits.
143 def __init__(self
, core_config
, reset_less
=True):
144 """ Create a ``DivPipeCoreInterstageData`` instance. """
145 self
.core_config
= core_config
146 self
.divisor_radicand
= Signal(core_config
.bit_width
,
147 reset_less
=reset_less
)
148 self
.operation
= DP
.create_signal(reset_less
=reset_less
)
149 self
.quotient_root
= Signal(core_config
.bit_width
,
150 reset_less
=reset_less
)
151 self
.root_times_radicand
= Signal(core_config
.bit_width
* 2,
152 reset_less
=reset_less
)
153 self
.compare_lhs
= Signal(core_config
.bit_width
* 3,
154 reset_less
=reset_less
)
155 self
.compare_rhs
= Signal(core_config
.bit_width
* 3,
156 reset_less
=reset_less
)
159 """ Get member signals. """
160 yield self
.divisor_radicand
162 yield self
.quotient_root
163 yield self
.root_times_radicand
164 yield self
.compare_lhs
165 yield self
.compare_rhs
168 """ Assign member signals. """
169 return [self
.divisor_radicand
.eq(rhs
.divisor_radicand
),
170 self
.operation
.eq(rhs
.operation
),
171 self
.quotient_root
.eq(rhs
.quotient_root
),
172 self
.root_times_radicand
.eq(rhs
.root_times_radicand
),
173 self
.compare_lhs
.eq(rhs
.compare_lhs
),
174 self
.compare_rhs
.eq(rhs
.compare_rhs
)]
177 class DivPipeCoreOutputData
:
178 """ output data type for ``DivPipeCore``.
180 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
181 configuration to be used.
182 :attribute quotient_root: the quotient or root part of the result of the
183 operation. Signal with a bit-width of ``core_config.bit_width`` and a
184 fract-width of ``core_config.fract_width`` bits.
185 :attribute remainder: the remainder part of the result of the operation.
186 Signal with a bit-width of ``core_config.bit_width * 3`` and a
187 fract-width of ``core_config.fract_width * 3`` bits.
190 def __init__(self
, core_config
, reset_less
=True):
191 """ Create a ``DivPipeCoreOutputData`` instance. """
192 self
.core_config
= core_config
193 self
.quotient_root
= Signal(core_config
.bit_width
,
194 reset_less
=reset_less
)
195 self
.remainder
= Signal(core_config
.bit_width
* 3,
196 reset_less
=reset_less
)
199 """ Get member signals. """
200 yield self
.quotient_root
205 """ Assign member signals. """
206 return [self
.quotient_root
.eq(rhs
.quotient_root
),
207 self
.remainder
.eq(rhs
.remainder
)]
210 class DivPipeCoreSetupStage(Elaboratable
):
211 """ Setup Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
213 def __init__(self
, core_config
):
214 """ Create a ``DivPipeCoreSetupStage`` instance."""
215 self
.core_config
= core_config
216 self
.i
= self
.ispec()
217 self
.o
= self
.ospec()
220 """ Get the input spec for this pipeline stage."""
221 return DivPipeCoreInputData(self
.core_config
)
224 """ Get the output spec for this pipeline stage."""
225 return DivPipeCoreInterstageData(self
.core_config
)
227 def setup(self
, m
, i
):
228 """ Pipeline stage setup. """
229 m
.submodules
.div_pipe_core_setup
= self
230 m
.d
.comb
+= self
.i
.eq(i
)
232 def process(self
, i
):
233 """ Pipeline stage process. """
234 return self
.o
# return processed data (ignore i)
236 def elaborate(self
, platform
):
237 """ Elaborate into ``Module``. """
240 m
.d
.comb
+= self
.o
.divisor_radicand
.eq(self
.i
.divisor_radicand
)
241 m
.d
.comb
+= self
.o
.quotient_root
.eq(0)
242 m
.d
.comb
+= self
.o
.root_times_radicand
.eq(0)
244 with m
.If(self
.i
.operation
== int(DP
.UDivRem
)):
245 m
.d
.comb
+= self
.o
.compare_lhs
.eq(self
.i
.dividend
246 << self
.core_config
.fract_width
)
247 with m
.Elif(self
.i
.operation
== int(DP
.SqrtRem
)):
248 m
.d
.comb
+= self
.o
.compare_lhs
.eq(
249 self
.i
.divisor_radicand
<< (self
.core_config
.fract_width
* 2))
250 with m
.Else(): # DivPipeCoreOperation.RSqrtRem
251 m
.d
.comb
+= self
.o
.compare_lhs
.eq(
252 1 << (self
.core_config
.fract_width
* 2))
254 m
.d
.comb
+= self
.o
.compare_rhs
.eq(0)
255 m
.d
.comb
+= self
.o
.operation
.eq(self
.i
.operation
)
260 class Trial(Elaboratable
):
261 def __init__(self
, core_config
, trial_bits
, current_shift
, log2_radix
):
262 self
.core_config
= core_config
263 self
.trial_bits
= trial_bits
264 self
.current_shift
= current_shift
265 self
.log2_radix
= log2_radix
266 bw
= core_config
.bit_width
267 self
.divisor_radicand
= Signal(bw
, reset_less
=True)
268 self
.quotient_root
= Signal(bw
, reset_less
=True)
269 self
.root_times_radicand
= Signal(bw
* 2, reset_less
=True)
270 self
.compare_rhs
= Signal(bw
* 3, reset_less
=True)
271 self
.trial_compare_rhs
= Signal(bw
* 3, reset_less
=True)
272 self
.operation
= DP
.create_signal(reset_less
=True)
274 def elaborate(self
, platform
):
278 dr
= self
.divisor_radicand
279 qr
= self
.quotient_root
280 rr
= self
.root_times_radicand
282 trial_bits_sig
= Const(self
.trial_bits
, self
.log2_radix
)
283 trial_bits_sqrd_sig
= Const(self
.trial_bits
* self
.trial_bits
,
286 tblen
= self
.core_config
.bit_width
+self
.log2_radix
287 tblen2
= self
.core_config
.bit_width
+self
.log2_radix
*2
288 dr_times_trial_bits_sqrd
= Signal(tblen2
, reset_less
=True)
289 m
.d
.comb
+= dr_times_trial_bits_sqrd
.eq(dr
* trial_bits_sqrd_sig
)
292 with m
.If(self
.operation
== int(DP
.UDivRem
)):
293 dr_times_trial_bits
= Signal(tblen
, reset_less
=True)
294 m
.d
.comb
+= dr_times_trial_bits
.eq(dr
* trial_bits_sig
)
295 div_rhs
= self
.compare_rhs
297 div_term1
= dr_times_trial_bits
298 div_term1_shift
= self
.core_config
.fract_width
299 div_term1_shift
+= self
.current_shift
300 div_rhs
+= div_term1
<< div_term1_shift
302 m
.d
.comb
+= self
.trial_compare_rhs
.eq(div_rhs
)
305 with m
.Elif(self
.operation
== int(DP
.SqrtRem
)):
306 qr_times_trial_bits
= Signal((tblen
+1)*2, reset_less
=True)
307 m
.d
.comb
+= qr_times_trial_bits
.eq(qr
* trial_bits_sig
)
308 sqrt_rhs
= self
.compare_rhs
310 sqrt_term1
= qr_times_trial_bits
311 sqrt_term1_shift
= self
.core_config
.fract_width
312 sqrt_term1_shift
+= self
.current_shift
+ 1
313 sqrt_rhs
+= sqrt_term1
<< sqrt_term1_shift
314 sqrt_term2
= trial_bits_sqrd_sig
315 sqrt_term2_shift
= self
.core_config
.fract_width
316 sqrt_term2_shift
+= self
.current_shift
* 2
317 sqrt_rhs
+= sqrt_term2
<< sqrt_term2_shift
319 m
.d
.comb
+= self
.trial_compare_rhs
.eq(sqrt_rhs
)
323 rr_times_trial_bits
= Signal((tblen
+1)*3, reset_less
=True)
324 m
.d
.comb
+= rr_times_trial_bits
.eq(rr
* trial_bits_sig
)
325 rsqrt_rhs
= self
.compare_rhs
327 rsqrt_term1
= rr_times_trial_bits
328 rsqrt_term1_shift
= self
.current_shift
+ 1
329 rsqrt_rhs
+= rsqrt_term1
<< rsqrt_term1_shift
330 rsqrt_term2
= dr_times_trial_bits_sqrd
331 rsqrt_term2_shift
= self
.current_shift
* 2
332 rsqrt_rhs
+= rsqrt_term2
<< rsqrt_term2_shift
334 m
.d
.comb
+= self
.trial_compare_rhs
.eq(rsqrt_rhs
)
339 class DivPipeCoreCalculateStage(Elaboratable
):
340 """ Calculate Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
342 def __init__(self
, core_config
, stage_index
):
343 """ Create a ``DivPipeCoreSetupStage`` instance. """
344 self
.core_config
= core_config
345 assert stage_index
in range(core_config
.n_stages
)
346 self
.stage_index
= stage_index
347 self
.i
= self
.ispec()
348 self
.o
= self
.ospec()
351 """ Get the input spec for this pipeline stage. """
352 return DivPipeCoreInterstageData(self
.core_config
)
355 """ Get the output spec for this pipeline stage. """
356 return DivPipeCoreInterstageData(self
.core_config
)
358 def setup(self
, m
, i
):
359 """ Pipeline stage setup. """
360 setattr(m
.submodules
,
361 f
"div_pipe_core_calculate_{self.stage_index}",
363 m
.d
.comb
+= self
.i
.eq(i
)
365 def process(self
, i
):
366 """ Pipeline stage process. """
369 def elaborate(self
, platform
):
370 """ Elaborate into ``Module``. """
373 # copy invariant inputs to outputs (for next stage)
374 m
.d
.comb
+= self
.o
.divisor_radicand
.eq(self
.i
.divisor_radicand
)
375 m
.d
.comb
+= self
.o
.operation
.eq(self
.i
.operation
)
376 m
.d
.comb
+= self
.o
.compare_lhs
.eq(self
.i
.compare_lhs
)
379 log2_radix
= self
.core_config
.log2_radix
380 current_shift
= self
.core_config
.bit_width
381 current_shift
-= self
.stage_index
* log2_radix
382 log2_radix
= min(log2_radix
, current_shift
)
383 assert log2_radix
> 0
384 current_shift
-= log2_radix
385 radix
= 1 << log2_radix
387 # trials within this radix range. carried out by Trial module,
388 # results stored in pass_flags. pass_flags are unary priority.
389 trial_compare_rhs_values
= []
391 for trial_bits
in range(radix
):
392 t
= Trial(self
.core_config
, trial_bits
, current_shift
, log2_radix
)
393 setattr(m
.submodules
, "trial%d" % trial_bits
, t
)
395 m
.d
.comb
+= t
.divisor_radicand
.eq(self
.i
.divisor_radicand
)
396 m
.d
.comb
+= t
.quotient_root
.eq(self
.i
.quotient_root
)
397 m
.d
.comb
+= t
.root_times_radicand
.eq(self
.i
.root_times_radicand
)
398 m
.d
.comb
+= t
.compare_rhs
.eq(self
.i
.compare_rhs
)
399 m
.d
.comb
+= t
.operation
.eq(self
.i
.operation
)
401 # get the trial output
402 trial_compare_rhs_values
.append(t
.trial_compare_rhs
)
404 # make the trial comparison against the [invariant] lhs.
405 # trial_compare_rhs is always decreasing as trial_bits increases
406 pass_flag
= Signal(name
=f
"pass_flag_{trial_bits}", reset_less
=True)
407 m
.d
.comb
+= pass_flag
.eq(self
.i
.compare_lhs
>= t
.trial_compare_rhs
)
408 pfl
.append(pass_flag
)
410 # Cat all the pass flags list together (easier to handle, below)
411 pass_flags
= Signal(radix
, reset_less
=True)
412 m
.d
.comb
+= pass_flags
.eq(Cat(*pfl
))
414 # convert pass_flags (unary priority) to next_bits (binary index)
416 # Assumes that for each set bit in pass_flag, all previous bits are
419 # Assumes that pass_flag[0] is always set (since
420 # compare_lhs >= compare_rhs is a pipeline invariant).
422 m
.submodules
.pe
= pe
= PriorityEncoder(radix
)
423 next_bits
= Signal(log2_radix
, reset_less
=True)
424 m
.d
.comb
+= pe
.i
.eq(~pass_flags
)
426 m
.d
.comb
+= next_bits
.eq(pe
.o
-1)
428 m
.d
.comb
+= next_bits
.eq(radix
-1)
430 # get the highest passing rhs trial (indexed by next_bits)
431 ta
= Array(trial_compare_rhs_values
)
432 m
.d
.comb
+= self
.o
.compare_rhs
.eq(ta
[next_bits
])
434 # create outputs for next phase
435 m
.d
.comb
+= self
.o
.root_times_radicand
.eq(self
.i
.root_times_radicand
436 + ((self
.i
.divisor_radicand
439 m
.d
.comb
+= self
.o
.quotient_root
.eq(self
.i
.quotient_root
440 |
(next_bits
<< current_shift
))
444 class DivPipeCoreFinalStage(Elaboratable
):
445 """ Final Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
447 def __init__(self
, core_config
):
448 """ Create a ``DivPipeCoreFinalStage`` instance."""
449 self
.core_config
= core_config
450 self
.i
= self
.ispec()
451 self
.o
= self
.ospec()
454 """ Get the input spec for this pipeline stage."""
455 return DivPipeCoreInterstageData(self
.core_config
)
458 """ Get the output spec for this pipeline stage."""
459 return DivPipeCoreOutputData(self
.core_config
)
461 def setup(self
, m
, i
):
462 """ Pipeline stage setup. """
463 m
.submodules
.div_pipe_core_final
= self
464 m
.d
.comb
+= self
.i
.eq(i
)
466 def process(self
, i
):
467 """ Pipeline stage process. """
468 return self
.o
# return processed data (ignore i)
470 def elaborate(self
, platform
):
471 """ Elaborate into ``Module``. """
474 m
.d
.comb
+= self
.o
.quotient_root
.eq(self
.i
.quotient_root
)
475 m
.d
.comb
+= self
.o
.remainder
.eq(self
.i
.compare_lhs
476 - self
.i
.compare_rhs
)