69de47db4f4c4cfcc11ff483e5dcfb5ebcc655d9
1 # SPDX-License-Identifier: LGPL-2.1-or-later
2 # See Notices.txt for copyright information
4 """ Algorithms for div/rem/sqrt/rsqrt.
6 code for simulating/testing the various algorithms
9 from nmigen
.hdl
.ast
import Const
12 def div_rem(dividend
, divisor
, bit_width
, signed
):
13 """ Compute the quotient/remainder following the RISC-V M extension.
15 NOT the same as the // or % operators
17 dividend
= Const
.normalize(dividend
, (bit_width
, signed
))
18 divisor
= Const
.normalize(divisor
, (bit_width
, signed
))
23 quotient
= abs(dividend
) // abs(divisor
)
24 remainder
= abs(dividend
) % abs(divisor
)
25 if (dividend
< 0) != (divisor
< 0):
28 remainder
= -remainder
29 quotient
= Const
.normalize(quotient
, (bit_width
, signed
))
30 remainder
= Const
.normalize(remainder
, (bit_width
, signed
))
31 return quotient
, remainder
35 """ Unsigned integer division/remainder following the RISC-V M extension.
37 NOT the same as the // or % operators
39 :attribute remainder: the remainder and/or dividend
40 :attribute divisor: the divisor
41 :attribute bit_width: the bit width of the inputs/outputs
42 :attribute log2_radix: the base-2 log of the division radix. The number of
43 bits of quotient that are calculated per pipeline stage.
44 :attribute quotient: the quotient
45 :attribute current_shift: the current bit index
48 def __init__(self
, dividend
, divisor
, bit_width
, log2_radix
=3):
49 """ Create an UnsignedDivRem.
51 :param dividend: the dividend/numerator
52 :param divisor: the divisor/denominator
53 :param bit_width: the bit width of the inputs/outputs
54 :param log2_radix: the base-2 log of the division radix. The number of
55 bits of quotient that are calculated per pipeline stage.
57 self
.remainder
= Const
.normalize(dividend
, (bit_width
, False))
58 self
.divisor
= Const
.normalize(divisor
, (bit_width
, False))
59 self
.bit_width
= bit_width
60 self
.log2_radix
= log2_radix
62 self
.current_shift
= bit_width
64 def calculate_stage(self
):
65 """ Calculate the next pipeline stage of the division.
67 :returns bool: True if this is the last pipeline stage.
69 if self
.current_shift
== 0:
71 log2_radix
= min(self
.log2_radix
, self
.current_shift
)
73 self
.current_shift
-= log2_radix
74 radix
= 1 << log2_radix
76 for i
in range(radix
):
77 v
= (self
.divisor
* i
) << self
.current_shift
78 remainders
.append(self
.remainder
- v
)
80 for i
in range(radix
):
81 if remainders
[i
] >= 0:
83 self
.remainder
= remainders
[quotient_bits
]
84 self
.quotient |
= quotient_bits
<< self
.current_shift
85 return self
.current_shift
== 0
88 """ Calculate the results of the division.
92 while not self
.calculate_stage():
98 """ integer division/remainder following the RISC-V M extension.
100 NOT the same as the // or % operators
102 :attribute dividend: the dividend
103 :attribute divisor: the divisor
104 :attribute signed: if the inputs/outputs are signed instead of unsigned
105 :attribute quotient: the quotient
106 :attribute remainder: the remainder
107 :attribute divider: the base UnsignedDivRem
110 def __init__(self
, dividend
, divisor
, bit_width
, signed
, log2_radix
=3):
113 :param dividend: the dividend/numerator
114 :param divisor: the divisor/denominator
115 :param bit_width: the bit width of the inputs/outputs
116 :param signed: if the inputs/outputs are signed instead of unsigned
117 :param log2_radix: the base-2 log of the division radix. The number of
118 bits of quotient that are calculated per pipeline stage.
120 self
.dividend
= Const
.normalize(dividend
, (bit_width
, signed
))
121 self
.divisor
= Const
.normalize(divisor
, (bit_width
, signed
))
125 self
.divider
= UnsignedDivRem(abs(dividend
), abs(divisor
),
126 bit_width
, log2_radix
)
128 def calculate_stage(self
):
129 """ Calculate the next pipeline stage of the division.
131 :returns bool: True if this is the last pipeline stage.
133 if not self
.divider
.calculate_stage():
135 divisor_sign
= self
.divisor
< 0
136 dividend_sign
= self
.dividend
< 0
137 if self
.divisor
!= 0 and divisor_sign
!= dividend_sign
:
138 quotient
= -self
.divider
.quotient
140 quotient
= self
.divider
.quotient
142 remainder
= -self
.divider
.remainder
144 remainder
= self
.divider
.remainder
145 bit_width
= self
.divider
.bit_width
146 self
.quotient
= Const
.normalize(quotient
, (bit_width
, self
.signed
))
147 self
.remainder
= Const
.normalize(remainder
, (bit_width
, self
.signed
))