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
)
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
.Enum
):
53 """ Operation for ``DivPipeCore``.
55 :attribute UDivRem: unsigned divide/remainder.
56 :attribute SqrtRem: square-root/remainder.
57 :attribute RSqrtRem: reciprocal-square-root/remainder.
65 """ Convert to int. """
69 def create_signal(cls
, *, src_loc_at
=0, **kwargs
):
70 """ Create a signal that can contain a ``DivPipeCoreOperation``. """
71 return Signal(min=min(map(int, cls
)),
72 max=max(map(int, cls
)) + 2,
73 src_loc_at
=(src_loc_at
+ 1),
74 decoder
=lambda v
: str(cls(v
)),
78 class DivPipeCoreInputData
:
79 """ input data type for ``DivPipeCore``.
81 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
82 configuration to be used.
83 :attribute dividend: dividend for div/rem. Signal with a bit-width of
84 ``core_config.bit_width + core_config.fract_width`` and a fract-width
85 of ``core_config.fract_width * 2`` bits.
86 :attribute divisor_radicand: divisor for div/rem and radicand for
87 sqrt/rsqrt. Signal with a bit-width of ``core_config.bit_width`` and a
88 fract-width of ``core_config.fract_width`` bits.
89 :attribute operation: the ``DivPipeCoreOperation`` to be computed.
92 def __init__(self
, core_config
, reset_less
=True):
93 """ Create a ``DivPipeCoreInputData`` instance. """
94 self
.core_config
= core_config
95 self
.dividend
= Signal(core_config
.bit_width
+ core_config
.fract_width
,
96 reset_less
=reset_less
)
97 self
.divisor_radicand
= Signal(core_config
.bit_width
,
98 reset_less
=reset_less
)
100 # FIXME: this goes into (is replaced by) self.ctx.op
102 DivPipeCoreOperation
.create_signal(reset_less
=reset_less
)
105 """ Get member signals. """
107 yield self
.divisor_radicand
108 yield self
.operation
# FIXME: delete. already covered by self.ctx
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
), # FIXME: delete.
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 # FIXME: delete self.operation. already covered by self.ctx.op
150 DivPipeCoreOperation
.create_signal(reset_less
=reset_less
)
151 self
.quotient_root
= Signal(core_config
.bit_width
,
152 reset_less
=reset_less
)
153 self
.root_times_radicand
= Signal(core_config
.bit_width
* 2,
154 reset_less
=reset_less
)
155 self
.compare_lhs
= Signal(core_config
.bit_width
* 3,
156 reset_less
=reset_less
)
157 self
.compare_rhs
= Signal(core_config
.bit_width
* 3,
158 reset_less
=reset_less
)
161 """ Get member signals. """
162 yield self
.divisor_radicand
163 yield self
.operation
# FIXME: delete. already in self.ctx.op
164 yield self
.quotient_root
165 yield self
.root_times_radicand
166 yield self
.compare_lhs
167 yield self
.compare_rhs
170 """ Assign member signals. """
171 return [self
.divisor_radicand
.eq(rhs
.divisor_radicand
),
172 self
.operation
.eq(rhs
.operation
), # FIXME: delete.
173 self
.quotient_root
.eq(rhs
.quotient_root
),
174 self
.root_times_radicand
.eq(rhs
.root_times_radicand
),
175 self
.compare_lhs
.eq(rhs
.compare_lhs
),
176 self
.compare_rhs
.eq(rhs
.compare_rhs
)]
179 class DivPipeCoreOutputData
:
180 """ output data type for ``DivPipeCore``.
182 :attribute core_config: ``DivPipeCoreConfig`` instance describing the
183 configuration to be used.
184 :attribute quotient_root: the quotient or root part of the result of the
185 operation. Signal with a bit-width of ``core_config.bit_width`` and a
186 fract-width of ``core_config.fract_width`` bits.
187 :attribute remainder: the remainder part of the result of the operation.
188 Signal with a bit-width of ``core_config.bit_width * 3`` and a
189 fract-width of ``core_config.fract_width * 3`` bits.
192 def __init__(self
, core_config
, reset_less
=True):
193 """ Create a ``DivPipeCoreOutputData`` instance. """
194 self
.core_config
= core_config
195 self
.quotient_root
= Signal(core_config
.bit_width
,
196 reset_less
=reset_less
)
197 self
.remainder
= Signal(core_config
.bit_width
* 3,
198 reset_less
=reset_less
)
201 """ Get member signals. """
202 yield self
.quotient_root
207 """ Assign member signals. """
208 return [self
.quotient_root
.eq(rhs
.quotient_root
),
209 self
.remainder
.eq(rhs
.remainder
)]
212 class DivPipeCoreSetupStage(Elaboratable
):
213 """ Setup Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
215 def __init__(self
, core_config
):
216 """ Create a ``DivPipeCoreSetupStage`` instance."""
217 self
.core_config
= core_config
218 self
.i
= self
.ispec()
219 self
.o
= self
.ospec()
222 """ Get the input spec for this pipeline stage."""
223 return DivPipeCoreInputData(self
.core_config
)
226 """ Get the output spec for this pipeline stage."""
227 return DivPipeCoreInterstageData(self
.core_config
)
229 def setup(self
, m
, i
):
230 """ Pipeline stage setup. """
231 m
.submodules
.div_pipe_core_setup
= self
232 m
.d
.comb
+= self
.i
.eq(i
)
234 def process(self
, i
):
235 """ Pipeline stage process. """
236 return self
.o
# return processed data (ignore i)
238 def elaborate(self
, platform
):
239 """ Elaborate into ``Module``. """
242 m
.d
.comb
+= self
.o
.divisor_radicand
.eq(self
.i
.divisor_radicand
)
243 m
.d
.comb
+= self
.o
.quotient_root
.eq(0)
244 m
.d
.comb
+= self
.o
.root_times_radicand
.eq(0)
246 with m
.If(self
.i
.operation
== int(DivPipeCoreOperation
.UDivRem
)):
247 m
.d
.comb
+= self
.o
.compare_lhs
.eq(self
.i
.dividend
248 << self
.core_config
.fract_width
)
249 with m
.Elif(self
.i
.operation
== int(DivPipeCoreOperation
.SqrtRem
)):
250 m
.d
.comb
+= self
.o
.compare_lhs
.eq(
251 self
.i
.divisor_radicand
<< (self
.core_config
.fract_width
* 2))
252 with m
.Else(): # DivPipeCoreOperation.RSqrtRem
253 m
.d
.comb
+= self
.o
.compare_lhs
.eq(
254 1 << (self
.core_config
.fract_width
* 3))
256 m
.d
.comb
+= self
.o
.compare_rhs
.eq(0)
257 m
.d
.comb
+= self
.o
.operation
.eq(self
.i
.operation
)
262 class DivPipeCoreCalculateStage(Elaboratable
):
263 """ Calculate Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
265 def __init__(self
, core_config
, stage_index
):
266 """ Create a ``DivPipeCoreSetupStage`` instance. """
267 self
.core_config
= core_config
268 assert stage_index
in range(core_config
.num_calculate_stages
)
269 self
.stage_index
= stage_index
270 self
.i
= self
.ispec()
271 self
.o
= self
.ospec()
274 """ Get the input spec for this pipeline stage. """
275 return DivPipeCoreInterstageData(self
.core_config
)
278 """ Get the output spec for this pipeline stage. """
279 return DivPipeCoreInterstageData(self
.core_config
)
281 def setup(self
, m
, i
):
282 """ Pipeline stage setup. """
283 setattr(m
.submodules
,
284 f
"div_pipe_core_calculate_{self.stage_index}",
286 m
.d
.comb
+= self
.i
.eq(i
)
288 def process(self
, i
):
289 """ Pipeline stage process. """
292 def elaborate(self
, platform
):
293 """ Elaborate into ``Module``. """
295 m
.d
.comb
+= self
.o
.divisor_radicand
.eq(self
.i
.divisor_radicand
)
296 m
.d
.comb
+= self
.o
.operation
.eq(self
.i
.operation
)
297 m
.d
.comb
+= self
.o
.compare_lhs
.eq(self
.i
.compare_lhs
)
298 log2_radix
= self
.core_config
.log2_radix
299 current_shift
= self
.core_config
.bit_width
300 current_shift
-= self
.stage_index
* log2_radix
301 log2_radix
= min(log2_radix
, current_shift
)
302 assert log2_radix
> 0
303 current_shift
-= log2_radix
304 radix
= 1 << log2_radix
305 trial_compare_rhs_values
= []
307 for trial_bits
in range(radix
):
308 trial_bits_sig
= Const(trial_bits
, log2_radix
)
309 trial_bits_sqrd_sig
= Const(trial_bits
* trial_bits
,
312 dr_times_trial_bits
= self
.i
.divisor_radicand
* trial_bits_sig
313 dr_times_trial_bits_sqrd
= self
.i
.divisor_radicand \
314 * trial_bits_sqrd_sig
315 qr_times_trial_bits
= self
.i
.quotient_root
* trial_bits_sig
316 rr_times_trial_bits
= self
.i
.root_times_radicand
* trial_bits_sig
319 div_rhs
= self
.i
.compare_rhs
320 if trial_bits
!= 0: # no point adding stuff that's multiplied by zero
321 div_term1
= dr_times_trial_bits
322 div_term1_shift
= self
.core_config
.fract_width
323 div_term1_shift
+= current_shift
324 div_rhs
+= div_term1
<< div_term1_shift
327 sqrt_rhs
= self
.i
.compare_rhs
328 if trial_bits
!= 0: # no point adding stuff that's multiplied by zero
329 sqrt_term1
= qr_times_trial_bits
330 sqrt_term1_shift
= self
.core_config
.fract_width
331 sqrt_term1_shift
+= current_shift
+ 1
332 sqrt_rhs
+= sqrt_term1
<< sqrt_term1_shift
333 sqrt_term2
= trial_bits_sqrd_sig
334 sqrt_term2_shift
= self
.core_config
.fract_width
335 sqrt_term2_shift
+= current_shift
* 2
336 sqrt_rhs
+= sqrt_term2
<< sqrt_term2_shift
339 rsqrt_rhs
= self
.i
.compare_rhs
340 if trial_bits
!= 0: # no point adding stuff that's multiplied by zero
341 rsqrt_term1
= rr_times_trial_bits
342 rsqrt_term1_shift
= current_shift
+ 1
343 rsqrt_rhs
+= rsqrt_term1
<< rsqrt_term1_shift
344 rsqrt_term2
= dr_times_trial_bits_sqrd
345 rsqrt_term2_shift
= current_shift
* 2
346 rsqrt_rhs
+= rsqrt_term2
<< rsqrt_term2_shift
348 trial_compare_rhs
= Signal
.like(
349 self
.o
.compare_rhs
, name
=f
"trial_compare_rhs_{trial_bits}",
352 with m
.If(self
.i
.operation
== int(DivPipeCoreOperation
.UDivRem
)):
353 m
.d
.comb
+= trial_compare_rhs
.eq(div_rhs
)
354 with m
.Elif(self
.i
.operation
== int(DivPipeCoreOperation
.SqrtRem
)):
355 m
.d
.comb
+= trial_compare_rhs
.eq(sqrt_rhs
)
356 with m
.Else(): # DivPipeCoreOperation.RSqrtRem
357 m
.d
.comb
+= trial_compare_rhs
.eq(rsqrt_rhs
)
358 trial_compare_rhs_values
.append(trial_compare_rhs
)
360 pass_flag
= Signal(name
=f
"pass_flag_{trial_bits}", reset_less
=True)
361 m
.d
.comb
+= pass_flag
.eq(self
.i
.compare_lhs
>= trial_compare_rhs
)
362 pass_flags
.append(pass_flag
)
364 # convert pass_flags to next_bits.
366 # Assumes that for each set bit in pass_flag, all previous bits are
369 # Assumes that pass_flag[0] is always set (since
370 # compare_lhs >= compare_rhs is a pipeline invariant).
372 next_bits
= Signal(log2_radix
, reset_less
=True)
373 for i
in range(log2_radix
):
375 for j
in range(0, radix
, 1 << i
):
376 bit_value ^
= pass_flags
[j
]
377 m
.d
.comb
+= next_bits
.part(i
, 1).eq(bit_value
)
380 for i
in range(radix
):
381 next_flag
= pass_flags
[i
+ 1] if i
+ 1 < radix
else 0
382 selected
= Signal(name
=f
"selected_{i}", reset_less
=True)
383 m
.d
.comb
+= selected
.eq(pass_flags
[i
] & ~next_flag
)
384 next_compare_rhs |
= Mux(selected
,
385 trial_compare_rhs_values
[i
],
388 m
.d
.comb
+= self
.o
.compare_rhs
.eq(next_compare_rhs
)
389 m
.d
.comb
+= self
.o
.root_times_radicand
.eq(self
.i
.root_times_radicand
390 + ((self
.i
.divisor_radicand
393 m
.d
.comb
+= self
.o
.quotient_root
.eq(self
.i
.quotient_root
394 |
(next_bits
<< current_shift
))
398 class DivPipeCoreFinalStage(Elaboratable
):
399 """ Final Stage of the core of the div/rem/sqrt/rsqrt pipeline. """
401 def __init__(self
, core_config
):
402 """ Create a ``DivPipeCoreFinalStage`` instance."""
403 self
.core_config
= core_config
404 self
.i
= self
.ispec()
405 self
.o
= self
.ospec()
408 """ Get the input spec for this pipeline stage."""
409 return DivPipeCoreInterstageData(self
.core_config
)
412 """ Get the output spec for this pipeline stage."""
413 return DivPipeCoreOutputData(self
.core_config
)
415 def setup(self
, m
, i
):
416 """ Pipeline stage setup. """
417 m
.submodules
.div_pipe_core_final
= self
418 m
.d
.comb
+= self
.i
.eq(i
)
420 def process(self
, i
):
421 """ Pipeline stage process. """
422 return self
.o
# return processed data (ignore i)
424 def elaborate(self
, platform
):
425 """ Elaborate into ``Module``. """
428 m
.d
.comb
+= self
.o
.quotient_root
.eq(self
.i
.quotient_root
)
429 m
.d
.comb
+= self
.o
.remainder
.eq(self
.i
.compare_lhs
430 - self
.i
.compare_rhs
)