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