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
)
24 # TODO, move to new (suitable) location
25 #from ieee754.fpcommon.getop import FPPipeContext
28 class DivPipeCoreConfig
:
29 """ Configuration for core of the div/rem/sqrt/rsqrt pipeline.
31 :attribute bit_width: base bit-width.
32 :attribute fract_width: base fract-width. Specifies location of base-2
34 :attribute log2_radix: number of bits of ``quotient_root`` that should be
35 computed per pipeline stage.
38 def __init__(self
, bit_width
, fract_width
, log2_radix
):
39 """ Create a ``DivPipeCoreConfig`` instance. """
40 self
.bit_width
= bit_width
41 self
.fract_width
= fract_width
42 self
.log2_radix
= log2_radix
46 return f
"DivPipeCoreConfig({self.bit_width}, " \
47 + f
"{self.fract_width}, {self.log2_radix})"
50 def num_calculate_stages(self
):
51 """ Get the number of ``DivPipeCoreCalculateStage`` needed. """
52 return (self
.bit_width
+ self
.log2_radix
- 1) // self
.log2_radix
55 class DivPipeCoreOperation(enum
.IntEnum
):
56 """ Operation for ``DivPipeCore``.
58 :attribute UDivRem: unsigned divide/remainder.
59 :attribute SqrtRem: square-root/remainder.
60 :attribute RSqrtRem: reciprocal-square-root/remainder.
68 def create_signal(cls
, *, src_loc_at
=0, **kwargs
):
69 """ Create a signal that can contain a ``DivPipeCoreOperation``. """
70 return Signal(min=int(min(cls
)),
72 src_loc_at
=(src_loc_at
+ 1),
77 # TODO: move to suitable location
78 class DivPipeBaseData
:
79 """ input data base type for ``DivPipe``.
82 def __init__(self
, pspec
):
83 """ Create a ``DivPipeBaseData`` instance. """
84 width
= pspec
['width']
85 self
.out_do_z
= Signal(reset_less
=True)
86 self
.oz
= Signal(width
, reset_less
=True)
88 self
.ctx
= FPPipeContext(pspec
) # context: muxid, operator etc.
89 self
.muxid
= self
.ctx
.muxid
# annoying. complicated.
92 """ Get member signals. """
98 """ Assign member signals. """
99 return [self
.out_do_z
.eq(i
.out_do_z
), self
.oz
.eq(i
.oz
),
103 class DivPipeCoreInputData
:
104 """ input data type for ``DivPipeCore``.
106 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
107 configuration to be used.
108 :attribute dividend: dividend for div/rem. Signal with a bit-width of
109 ``core_config.bit_width + core_config.fract_width`` and a fract-width
110 of ``core_config.fract_width * 2`` bits.
111 :attribute divisor_radicand: divisor for div/rem and radicand for
112 sqrt/rsqrt. Signal with a bit-width of ``core_config.bit_width`` and a
113 fract-width of ``core_config.fract_width`` bits.
114 :attribute operation: the ``DivPipeCoreOperation`` to be computed.
117 def __init__(self
, core_config
):
118 """ Create a ``DivPipeCoreInputData`` instance. """
119 self
.core_config
= core_config
120 self
.dividend
= Signal(core_config
.bit_width
+ core_config
.fract_width
,
122 self
.divisor_radicand
= Signal(core_config
.bit_width
, reset_less
=True)
124 # FIXME: this goes into (is replaced by) self.ctx.op
125 self
.operation
= DivPipeCoreOperation
.create_signal(reset_less
=True)
128 """ Get member signals. """
130 yield self
.divisor_radicand
131 yield self
.operation
# FIXME: delete. already covered by self.ctx
139 """ Assign member signals. """
140 return [self
.dividend
.eq(rhs
.dividend
),
141 self
.divisor_radicand
.eq(rhs
.divisor_radicand
),
142 self
.operation
.eq(rhs
.operation
)] # FIXME: delete.
145 # TODO: move to suitable location
146 class DivPipeInputData(DivPipeCoreInputData
, DivPipeBaseData
):
147 """ input data type for ``DivPipe``.
150 def __init__(self
, core_config
):
151 """ Create a ``DivPipeInputData`` instance. """
152 DivPipeCoreInputData
.__init
__(self
, core_config
)
153 DivPipeBaseData
.__init
__(self
, pspec
) # XXX TODO args
154 self
.out_do_z
= Signal(reset_less
=True)
155 self
.oz
= Signal(width
, reset_less
=True)
157 self
.ctx
= FPPipeContext(pspec
) # context: muxid, operator etc.
158 self
.muxid
= self
.ctx
.muxid
# annoying. complicated.
161 """ Get member signals. """
162 yield from DivPipeCoreInputData
.__iter
__(self
)
163 yield from DivPipeBaseData
.__iter
__(self
)
166 """ Assign member signals. """
167 return DivPipeBaseData
.eq(self
, rhs
) + \
168 DivPipeCoreInputData
.eq(self
, rhs
)
172 class DivPipeCoreInterstageData
:
173 """ interstage data type for ``DivPipeCore``.
175 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
176 configuration to be used.
177 :attribute divisor_radicand: divisor for div/rem and radicand for
178 sqrt/rsqrt. Signal with a bit-width of ``core_config.bit_width`` and a
179 fract-width of ``core_config.fract_width`` bits.
180 :attribute operation: the ``DivPipeCoreOperation`` to be computed.
181 :attribute quotient_root: the quotient or root part of the result of the
182 operation. Signal with a bit-width of ``core_config.bit_width`` and a
183 fract-width of ``core_config.fract_width`` bits.
184 :attribute root_times_radicand: ``quotient_root * divisor_radicand``.
185 Signal with a bit-width of ``core_config.bit_width * 2`` and a
186 fract-width of ``core_config.fract_width * 2`` bits.
187 :attribute compare_lhs: The left-hand-side of the comparison in the
188 equation to be solved. Signal with a bit-width of
189 ``core_config.bit_width * 3`` and a fract-width of
190 ``core_config.fract_width * 3`` bits.
191 :attribute compare_rhs: The right-hand-side of the comparison in the
192 equation to be solved. Signal with a bit-width of
193 ``core_config.bit_width * 3`` and a fract-width of
194 ``core_config.fract_width * 3`` bits.
197 def __init__(self
, core_config
):
198 """ Create a ``DivPipeCoreInterstageData`` instance. """
199 self
.core_config
= core_config
200 self
.divisor_radicand
= Signal(core_config
.bit_width
, reset_less
=True)
201 # XXX FIXME: delete. already covered by self.ctx.op
202 self
.operation
= DivPipeCoreOperation
.create_signal(reset_less
=True)
203 self
.quotient_root
= Signal(core_config
.bit_width
, reset_less
=True)
204 self
.root_times_radicand
= Signal(core_config
.bit_width
* 2,
206 self
.compare_lhs
= Signal(core_config
.bit_width
* 3, reset_less
=True)
207 self
.compare_rhs
= Signal(core_config
.bit_width
* 3, reset_less
=True)
210 """ Get member signals. """
211 yield self
.divisor_radicand
212 yield self
.operation
# XXX FIXME: delete. already in self.ctx.op
213 yield self
.quotient_root
214 yield self
.root_times_radicand
215 yield self
.compare_lhs
216 yield self
.compare_rhs
219 """ Assign member signals. """
220 return [self
.divisor_radicand
.eq(rhs
.divisor_radicand
),
221 self
.operation
.eq(rhs
.operation
), # FIXME: delete.
222 self
.quotient_root
.eq(rhs
.quotient_root
),
223 self
.root_times_radicand
.eq(rhs
.root_times_radicand
),
224 self
.compare_lhs
.eq(rhs
.compare_lhs
),
225 self
.compare_rhs
.eq(rhs
.compare_rhs
)]
228 # TODO: move to suitable location
229 class DivPipeInterstageData(DivPipeCoreInterstageData
, DivPipeBaseData
):
230 """ interstage data type for ``DivPipe``.
232 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
233 configuration to be used.
236 def __init__(self
, core_config
):
237 """ Create a ``DivPipeCoreInterstageData`` instance. """
238 DivPipeCoreInterstageData
.__init
__(self
, core_config
)
239 DivPipeBaseData
.__init
__(self
, pspec
) # XXX TODO args
242 """ Get member signals. """
243 yield from DivPipeInterstageData
.__iter
__(self
)
244 yield from DivPipeBaseData
.__iter
__(self
)
247 """ Assign member signals. """
248 return DivPipeBaseData
.eq(self
, rhs
) + \
249 DivPipeCoreInterstageData
.eq(self
, rhs
)
252 class DivPipeCoreOutputData
:
253 """ output data type for ``DivPipeCore``.
255 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
256 configuration to be used.
257 :attribute quotient_root: the quotient or root part of the result of the
258 operation. Signal with a bit-width of ``core_config.bit_width`` and a
259 fract-width of ``core_config.fract_width`` bits.
260 :attribute remainder: the remainder part of the result of the operation.
261 Signal with a bit-width of ``core_config.bit_width * 3`` and a
262 fract-width of ``core_config.fract_width * 3`` bits.
265 def __init__(self
, core_config
):
266 """ Create a ``DivPipeCoreOutputData`` instance. """
267 self
.core_config
= core_config
268 self
.quotient_root
= Signal(core_config
.bit_width
, reset_less
=True)
269 self
.remainder
= Signal(core_config
.bit_width
* 3, reset_less
=True)
272 """ Get member signals. """
273 yield self
.quotient_root
278 """ Assign member signals. """
279 return [self
.quotient_root
.eq(rhs
.quotient_root
),
280 self
.remainder
.eq(rhs
.remainder
)]
283 # TODO: move to suitable location
284 class DivPipeOutputData(DivPipeCoreOutputData
, DivPipeBaseData
):
285 """ interstage data type for ``DivPipe``.
287 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
288 configuration to be used.
291 def __init__(self
, core_config
):
292 """ Create a ``DivPipeCoreOutputData`` instance. """
293 DivPipeCoreOutputData
.__init
__(self
, core_config
)
294 DivPipeBaseData
.__init
__(self
, pspec
) # XXX TODO args
297 """ Get member signals. """
298 yield from DivPipeOutputData
.__iter
__(self
)
299 yield from DivPipeBaseData
.__iter
__(self
)
302 """ Assign member signals. """
303 return DivPipeBaseData
.eq(self
, rhs
) + \
304 DivPipeCoreOutputData
.eq(self
, rhs
)
307 class DivPipeBaseStage
:
308 """ Base Mix-in for DivPipe*Stage """
310 def _elaborate(self
, m
, platform
):
311 m
.d
.comb
+= self
.o
.oz
.eq(self
.i
.oz
)
312 m
.d
.comb
+= self
.o
.out_do_z
.eq(self
.i
.out_do_z
)
313 m
.d
.comb
+= self
.o
.ctx
.eq(self
.i
.ctx
)
316 class DivPipeCoreSetupStage(Elaboratable
):
317 """ Setup Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
319 def __init__(self
, core_config
):
320 """ Create a ``DivPipeCoreSetupStage`` instance."""
321 self
.core_config
= core_config
322 self
.i
= self
.ispec()
323 self
.o
= self
.ospec()
326 """ Get the input spec for this pipeline stage."""
327 return DivPipeCoreInputData(self
.core_config
)
330 """ Get the output spec for this pipeline stage."""
331 return DivPipeCoreInterstageData(self
.core_config
)
333 def setup(self
, m
, i
):
334 """ Pipeline stage setup. """
335 m
.submodules
.div_pipe_core_setup
= self
336 m
.d
.comb
+= self
.i
.eq(i
)
338 def process(self
, i
):
339 """ Pipeline stage process. """
340 return self
.o
# return processed data (ignore i)
342 def elaborate(self
, platform
):
343 """ Elaborate into ``Module``. """
346 m
.d
.comb
+= self
.o
.divisor_radicand
.eq(self
.i
.divisor_radicand
)
347 m
.d
.comb
+= self
.o
.quotient_root
.eq(0)
348 m
.d
.comb
+= self
.o
.root_times_radicand
.eq(0)
350 with m
.If(self
.i
.operation
== DivPipeCoreOperation
.UDivRem
):
351 m
.d
.comb
+= self
.o
.compare_lhs
.eq(self
.i
.dividend
352 << self
.core_config
.fract_width
)
353 with m
.Elif(self
.i
.operation
== DivPipeCoreOperation
.SqrtRem
):
354 m
.d
.comb
+= self
.o
.compare_lhs
.eq(
355 self
.i
.divisor_radicand
<< (self
.core_config
.fract_width
* 2))
356 with m
.Else(): # DivPipeCoreOperation.RSqrtRem
357 m
.d
.comb
+= self
.o
.compare_lhs
.eq(
358 1 << (self
.core_config
.fract_width
* 3))
360 m
.d
.comb
+= self
.o
.compare_rhs
.eq(0)
361 m
.d
.comb
+= self
.o
.operation
.eq(self
.i
.operation
)
365 # XXX in DivPipeSetupStage
366 DivPipeBaseStage
._elaborate
(self
, m
, platform
)
369 class DivPipeCoreCalculateStage(Elaboratable
):
370 """ Calculate Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
372 def __init__(self
, core_config
, stage_index
):
373 """ Create a ``DivPipeCoreSetupStage`` instance. """
374 self
.core_config
= core_config
375 assert stage_index
in range(core_config
.num_calculate_stages
)
376 self
.stage_index
= stage_index
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 DivPipeCoreInterstageData(self
.core_config
)
388 def setup(self
, m
, i
):
389 """ Pipeline stage setup. """
390 setattr(m
.submodules
,
391 f
"div_pipe_core_calculate_{self.stage_index}",
393 m
.d
.comb
+= self
.i
.eq(i
)
395 def process(self
, i
):
396 """ Pipeline stage process. """
399 def elaborate(self
, platform
):
400 """ Elaborate into ``Module``. """
402 m
.d
.comb
+= self
.o
.divisor_radicand
.eq(self
.i
.divisor_radicand
)
403 m
.d
.comb
+= self
.o
.operation
.eq(self
.i
.operation
)
404 m
.d
.comb
+= self
.o
.compare_lhs
.eq(self
.i
.compare_lhs
)
405 log2_radix
= self
.core_config
.log2_radix
406 current_shift
= self
.core_config
.bit_width
407 current_shift
-= self
.stage_index
* log2_radix
408 log2_radix
= min(log2_radix
, current_shift
)
409 assert log2_radix
> 0
410 current_shift
-= log2_radix
411 radix
= 1 << log2_radix
412 trial_compare_rhs_values
= []
414 for trial_bits
in range(radix
):
415 shifted_trial_bits
= Const(trial_bits
, log2_radix
) << current_shift
416 shifted_trial_bits_sqrd
= shifted_trial_bits
* shifted_trial_bits
419 div_rhs
= self
.i
.compare_rhs
420 div_factor1
= self
.i
.divisor_radicand
* shifted_trial_bits
421 div_rhs
+= div_factor1
<< self
.core_config
.fract_width
424 sqrt_rhs
= self
.i
.compare_rhs
425 sqrt_factor1
= self
.i
.quotient_root
* (shifted_trial_bits
<< 1)
426 sqrt_rhs
+= sqrt_factor1
<< self
.core_config
.fract_width
427 sqrt_factor2
= shifted_trial_bits_sqrd
428 sqrt_rhs
+= sqrt_factor2
<< self
.core_config
.fract_width
431 rsqrt_rhs
= self
.i
.compare_rhs
432 rsqrt_rhs
+= self
.i
.root_times_radicand
* (shifted_trial_bits
<< 1)
433 rsqrt_rhs
+= self
.i
.divisor_radicand
* shifted_trial_bits_sqrd
435 trial_compare_rhs
= self
.o
.compare_rhs
.like(
436 name
=f
"trial_compare_rhs_{trial_bits}")
438 with m
.If(self
.i
.operation
== DivPipeCoreOperation
.UDivRem
):
439 m
.d
.comb
+= trial_compare_rhs
.eq(div_rhs
)
440 with m
.Elif(self
.i
.operation
== DivPipeCoreOperation
.SqrtRem
):
441 m
.d
.comb
+= trial_compare_rhs
.eq(sqrt_rhs
)
442 with m
.Else(): # DivPipeCoreOperation.RSqrtRem
443 m
.d
.comb
+= trial_compare_rhs
.eq(rsqrt_rhs
)
444 trial_compare_rhs_values
.append(trial_compare_rhs
)
446 pass_flag
= Signal(name
=f
"pass_flag_{trial_bits}")
447 m
.d
.comb
+= pass_flag
.eq(self
.i
.compare_lhs
>= trial_compare_rhs
)
448 pass_flags
.append(pass_flag
)
450 # convert pass_flags to next_bits.
452 # Assumes that for each set bit in pass_flag, all previous bits are
455 # Assumes that pass_flag[0] is always set (since
456 # compare_lhs >= compare_rhs is a pipeline invariant).
458 next_bits
= Signal(log2_radix
)
459 for i
in range(log2_radix
):
461 for j
in range(0, radix
, 1 << i
):
462 bit_value ^
= pass_flags
[j
]
463 m
.d
.comb
+= next_bits
.part(i
, 1).eq(bit_value
)
466 for i
in range(radix
):
467 next_flag
= pass_flags
[i
+ 1] if i
+ 1 < radix
else 0
468 next_compare_rhs |
= Mux(pass_flags
[i
] & ~next_flag
,
469 trial_compare_rhs_values
[i
],
472 m
.d
.comb
+= self
.o
.compare_rhs
.eq(next_compare_rhs
)
473 m
.d
.comb
+= self
.o
.root_times_radicand
.eq(self
.i
.root_times_radicand
474 + ((self
.i
.divisor_radicand
477 m
.d
.comb
+= self
.o
.quotient_root
.eq(self
.i
.quotient_root
478 |
(next_bits
<< current_shift
))
481 # XXX in DivPipeCalculateStage
482 DivPipeBaseStage
._elaborate
(self
, m
, platform
)
486 class DivPipeCoreFinalStage(Elaboratable
):
487 """ Final Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
489 def __init__(self
, core_config
):
490 """ Create a ``DivPipeCoreFinalStage`` instance."""
491 self
.core_config
= core_config
492 self
.i
= self
.ispec()
493 self
.o
= self
.ospec()
496 """ Get the input spec for this pipeline stage."""
497 return DivPipeCoreInterstageData(self
.core_config
)
500 """ Get the output spec for this pipeline stage."""
501 return DivPipeCoreOutputData(self
.core_config
)
503 def setup(self
, m
, i
):
504 """ Pipeline stage setup. """
505 m
.submodules
.div_pipe_core_setup
= self
506 m
.d
.comb
+= self
.i
.eq(i
)
508 def process(self
, i
):
509 """ Pipeline stage process. """
510 return self
.o
# return processed data (ignore i)
512 def elaborate(self
, platform
):
513 """ Elaborate into ``Module``. """
516 m
.d
.comb
+= self
.o
.quotient_root
.eq(self
.i
.quotient_root
)
517 m
.d
.comb
+= self
.o
.remainder
.eq(self
.i
.compare_lhs
518 - self
.i
.compare_rhs
)
522 # XXX in DivPipeFinalStage
523 DivPipeBaseStage
._elaborate
(self
, m
, platform
)