projects / ieee754fpu.git / blob
? search:


c81127c0f81d1febc2f20ccee699667bf8583cd8
[ieee754fpu.git] / src / ieee754 / div_rem_sqrt_rsqrt / test_algorithm.py
1 # SPDX-License-Identifier: LGPL-2.1-or-later
2 # See Notices.txt for copyright information
3
4 from nmigen.hdl.ast import Const
5 from .algorithm import (div_rem, UnsignedDivRem, DivRem,
6 Fixed, fixed_sqrt, FixedSqrt, fixed_rsqrt, FixedRSqrt)
7 import unittest
8
9
10 class TestDivRemFn(unittest.TestCase):
11 def test_signed(self):
12 test_cases = [
13 # numerator, denominator, quotient, remainder
14 (-8, -8, 1, 0),
15 (-7, -8, 0, -7),
16 (-6, -8, 0, -6),
17 (-5, -8, 0, -5),
18 (-4, -8, 0, -4),
19 (-3, -8, 0, -3),
20 (-2, -8, 0, -2),
21 (-1, -8, 0, -1),
22 (0, -8, 0, 0),
23 (1, -8, 0, 1),
24 (2, -8, 0, 2),
25 (3, -8, 0, 3),
26 (4, -8, 0, 4),
27 (5, -8, 0, 5),
28 (6, -8, 0, 6),
29 (7, -8, 0, 7),
30 (-8, -7, 1, -1),
31 (-7, -7, 1, 0),
32 (-6, -7, 0, -6),
33 (-5, -7, 0, -5),
34 (-4, -7, 0, -4),
35 (-3, -7, 0, -3),
36 (-2, -7, 0, -2),
37 (-1, -7, 0, -1),
38 (0, -7, 0, 0),
39 (1, -7, 0, 1),
40 (2, -7, 0, 2),
41 (3, -7, 0, 3),
42 (4, -7, 0, 4),
43 (5, -7, 0, 5),
44 (6, -7, 0, 6),
45 (7, -7, -1, 0),
46 (-8, -6, 1, -2),
47 (-7, -6, 1, -1),
48 (-6, -6, 1, 0),
49 (-5, -6, 0, -5),
50 (-4, -6, 0, -4),
51 (-3, -6, 0, -3),
52 (-2, -6, 0, -2),
53 (-1, -6, 0, -1),
54 (0, -6, 0, 0),
55 (1, -6, 0, 1),
56 (2, -6, 0, 2),
57 (3, -6, 0, 3),
58 (4, -6, 0, 4),
59 (5, -6, 0, 5),
60 (6, -6, -1, 0),
61 (7, -6, -1, 1),
62 (-8, -5, 1, -3),
63 (-7, -5, 1, -2),
64 (-6, -5, 1, -1),
65 (-5, -5, 1, 0),
66 (-4, -5, 0, -4),
67 (-3, -5, 0, -3),
68 (-2, -5, 0, -2),
69 (-1, -5, 0, -1),
70 (0, -5, 0, 0),
71 (1, -5, 0, 1),
72 (2, -5, 0, 2),
73 (3, -5, 0, 3),
74 (4, -5, 0, 4),
75 (5, -5, -1, 0),
76 (6, -5, -1, 1),
77 (7, -5, -1, 2),
78 (-8, -4, 2, 0),
79 (-7, -4, 1, -3),
80 (-6, -4, 1, -2),
81 (-5, -4, 1, -1),
82 (-4, -4, 1, 0),
83 (-3, -4, 0, -3),
84 (-2, -4, 0, -2),
85 (-1, -4, 0, -1),
86 (0, -4, 0, 0),
87 (1, -4, 0, 1),
88 (2, -4, 0, 2),
89 (3, -4, 0, 3),
90 (4, -4, -1, 0),
91 (5, -4, -1, 1),
92 (6, -4, -1, 2),
93 (7, -4, -1, 3),
94 (-8, -3, 2, -2),
95 (-7, -3, 2, -1),
96 (-6, -3, 2, 0),
97 (-5, -3, 1, -2),
98 (-4, -3, 1, -1),
99 (-3, -3, 1, 0),
100 (-2, -3, 0, -2),
101 (-1, -3, 0, -1),
102 (0, -3, 0, 0),
103 (1, -3, 0, 1),
104 (2, -3, 0, 2),
105 (3, -3, -1, 0),
106 (4, -3, -1, 1),
107 (5, -3, -1, 2),
108 (6, -3, -2, 0),
109 (7, -3, -2, 1),
110 (-8, -2, 4, 0),
111 (-7, -2, 3, -1),
112 (-6, -2, 3, 0),
113 (-5, -2, 2, -1),
114 (-4, -2, 2, 0),
115 (-3, -2, 1, -1),
116 (-2, -2, 1, 0),
117 (-1, -2, 0, -1),
118 (0, -2, 0, 0),
119 (1, -2, 0, 1),
120 (2, -2, -1, 0),
121 (3, -2, -1, 1),
122 (4, -2, -2, 0),
123 (5, -2, -2, 1),
124 (6, -2, -3, 0),
125 (7, -2, -3, 1),
126 (-8, -1, -8, 0), # overflows and wraps around
127 (-7, -1, 7, 0),
128 (-6, -1, 6, 0),
129 (-5, -1, 5, 0),
130 (-4, -1, 4, 0),
131 (-3, -1, 3, 0),
132 (-2, -1, 2, 0),
133 (-1, -1, 1, 0),
134 (0, -1, 0, 0),
135 (1, -1, -1, 0),
136 (2, -1, -2, 0),
137 (3, -1, -3, 0),
138 (4, -1, -4, 0),
139 (5, -1, -5, 0),
140 (6, -1, -6, 0),
141 (7, -1, -7, 0),
142 (-8, 0, -1, -8),
143 (-7, 0, -1, -7),
144 (-6, 0, -1, -6),
145 (-5, 0, -1, -5),
146 (-4, 0, -1, -4),
147 (-3, 0, -1, -3),
148 (-2, 0, -1, -2),
149 (-1, 0, -1, -1),
150 (0, 0, -1, 0),
151 (1, 0, -1, 1),
152 (2, 0, -1, 2),
153 (3, 0, -1, 3),
154 (4, 0, -1, 4),
155 (5, 0, -1, 5),
156 (6, 0, -1, 6),
157 (7, 0, -1, 7),
158 (-8, 1, -8, 0),
159 (-7, 1, -7, 0),
160 (-6, 1, -6, 0),
161 (-5, 1, -5, 0),
162 (-4, 1, -4, 0),
163 (-3, 1, -3, 0),
164 (-2, 1, -2, 0),
165 (-1, 1, -1, 0),
166 (0, 1, 0, 0),
167 (1, 1, 1, 0),
168 (2, 1, 2, 0),
169 (3, 1, 3, 0),
170 (4, 1, 4, 0),
171 (5, 1, 5, 0),
172 (6, 1, 6, 0),
173 (7, 1, 7, 0),
174 (-8, 2, -4, 0),
175 (-7, 2, -3, -1),
176 (-6, 2, -3, 0),
177 (-5, 2, -2, -1),
178 (-4, 2, -2, 0),
179 (-3, 2, -1, -1),
180 (-2, 2, -1, 0),
181 (-1, 2, 0, -1),
182 (0, 2, 0, 0),
183 (1, 2, 0, 1),
184 (2, 2, 1, 0),
185 (3, 2, 1, 1),
186 (4, 2, 2, 0),
187 (5, 2, 2, 1),
188 (6, 2, 3, 0),
189 (7, 2, 3, 1),
190 (-8, 3, -2, -2),
191 (-7, 3, -2, -1),
192 (-6, 3, -2, 0),
193 (-5, 3, -1, -2),
194 (-4, 3, -1, -1),
195 (-3, 3, -1, 0),
196 (-2, 3, 0, -2),
197 (-1, 3, 0, -1),
198 (0, 3, 0, 0),
199 (1, 3, 0, 1),
200 (2, 3, 0, 2),
201 (3, 3, 1, 0),
202 (4, 3, 1, 1),
203 (5, 3, 1, 2),
204 (6, 3, 2, 0),
205 (7, 3, 2, 1),
206 (-8, 4, -2, 0),
207 (-7, 4, -1, -3),
208 (-6, 4, -1, -2),
209 (-5, 4, -1, -1),
210 (-4, 4, -1, 0),
211 (-3, 4, 0, -3),
212 (-2, 4, 0, -2),
213 (-1, 4, 0, -1),
214 (0, 4, 0, 0),
215 (1, 4, 0, 1),
216 (2, 4, 0, 2),
217 (3, 4, 0, 3),
218 (4, 4, 1, 0),
219 (5, 4, 1, 1),
220 (6, 4, 1, 2),
221 (7, 4, 1, 3),
222 (-8, 5, -1, -3),
223 (-7, 5, -1, -2),
224 (-6, 5, -1, -1),
225 (-5, 5, -1, 0),
226 (-4, 5, 0, -4),
227 (-3, 5, 0, -3),
228 (-2, 5, 0, -2),
229 (-1, 5, 0, -1),
230 (0, 5, 0, 0),
231 (1, 5, 0, 1),
232 (2, 5, 0, 2),
233 (3, 5, 0, 3),
234 (4, 5, 0, 4),
235 (5, 5, 1, 0),
236 (6, 5, 1, 1),
237 (7, 5, 1, 2),
238 (-8, 6, -1, -2),
239 (-7, 6, -1, -1),
240 (-6, 6, -1, 0),
241 (-5, 6, 0, -5),
242 (-4, 6, 0, -4),
243 (-3, 6, 0, -3),
244 (-2, 6, 0, -2),
245 (-1, 6, 0, -1),
246 (0, 6, 0, 0),
247 (1, 6, 0, 1),
248 (2, 6, 0, 2),
249 (3, 6, 0, 3),
250 (4, 6, 0, 4),
251 (5, 6, 0, 5),
252 (6, 6, 1, 0),
253 (7, 6, 1, 1),
254 (-8, 7, -1, -1),
255 (-7, 7, -1, 0),
256 (-6, 7, 0, -6),
257 (-5, 7, 0, -5),
258 (-4, 7, 0, -4),
259 (-3, 7, 0, -3),
260 (-2, 7, 0, -2),
261 (-1, 7, 0, -1),
262 (0, 7, 0, 0),
263 (1, 7, 0, 1),
264 (2, 7, 0, 2),
265 (3, 7, 0, 3),
266 (4, 7, 0, 4),
267 (5, 7, 0, 5),
268 (6, 7, 0, 6),
269 (7, 7, 1, 0),
270 ]
271 for (n, d, q, r) in test_cases:
272 self.assertEqual(div_rem(n, d, 4, True), (q, r))
273
274 def test_unsigned(self):
275 for n in range(16):
276 for d in range(16):
277 if d == 0:
278 q = 16 - 1
279 r = n
280 else:
281 # div_rem matches // and % for unsigned integers
282 q = n // d
283 r = n % d
284 self.assertEqual(div_rem(n, d, 4, False), (q, r))
285
286
287 class TestUnsignedDivRem(unittest.TestCase):
288 def helper(self, log2_radix):
289 bit_width = 4
290 for n in range(1 << bit_width):
291 for d in range(1 << bit_width):
292 q, r = div_rem(n, d, bit_width, False)
293 with self.subTest(n=n, d=d, q=q, r=r):
294 udr = UnsignedDivRem(n, d, bit_width, log2_radix)
295 for _ in range(250 * bit_width):
296 self.assertEqual(n, udr.quotient * udr.divisor
297 + udr.remainder)
298 if udr.calculate_stage():
299 break
300 else:
301 self.fail("infinite loop")
302 self.assertEqual(n, udr.quotient * udr.divisor
303 + udr.remainder)
304 self.assertEqual(udr.quotient, q)
305 self.assertEqual(udr.remainder, r)
306
307 def test_radix_2(self):
308 self.helper(1)
309
310 def test_radix_4(self):
311 self.helper(2)
312
313 def test_radix_8(self):
314 self.helper(3)
315
316 def test_radix_16(self):
317 self.helper(4)
318
319
320 class TestDivRem(unittest.TestCase):
321 def helper(self, log2_radix):
322 bit_width = 4
323 for n in range(1 << bit_width):
324 for d in range(1 << bit_width):
325 for signed in False, True:
326 n = Const.normalize(n, (bit_width, signed))
327 d = Const.normalize(d, (bit_width, signed))
328 q, r = div_rem(n, d, bit_width, signed)
329 with self.subTest(n=n, d=d, q=q, r=r, signed=signed):
330 dr = DivRem(n, d, bit_width, signed, log2_radix)
331 for _ in range(250 * bit_width):
332 if dr.calculate_stage():
333 break
334 else:
335 self.fail("infinite loop")
336 self.assertEqual(dr.quotient, q)
337 self.assertEqual(dr.remainder, r)
338
339 def test_radix_2(self):
340 self.helper(1)
341
342 def test_radix_4(self):
343 self.helper(2)
344
345 def test_radix_8(self):
346 self.helper(3)
347
348 def test_radix_16(self):
349 self.helper(4)
350
351 # FIXME: add tests for Fract, fract_sqrt, FractSqrt, fract_rsqrt, and FractRSqrt