src/ieee754/div_rem_sqrt_rsqrt/test_core.py

   1 #!/usr/bin/env python3
   2 # SPDX-License-Identifier: LGPL-2.1-or-later
   3 # See Notices.txt for copyright information
   4
   5 from ieee754.div_rem_sqrt_rsqrt.core import (DivPipeCoreConfig,
   6                     DivPipeCoreSetupStage,
   7                     DivPipeCoreCalculateStage, DivPipeCoreFinalStage,
   8                     DivPipeCoreOperation, DivPipeCoreInputData,
   9                     DivPipeCoreInterstageData, DivPipeCoreOutputData)
  10 from ieee754.div_rem_sqrt_rsqrt.algorithm import (FixedUDivRemSqrtRSqrt,
  11                         Fixed, Operation, div_rem,
  12                         fixed_sqrt, fixed_rsqrt)
  13 import unittest
  14 from nmigen import Module, Elaboratable, Signal
  15 from nmigen.hdl.ir import Fragment
  16 from nmigen.back import rtlil
  17 from nmigen.back.pysim import Simulator, Delay, Tick
  18 from itertools import chain
  19
  20
  21 def show_fixed(bits, fract_width, bit_width):
  22     fixed = Fixed.from_bits(bits, fract_width, bit_width, False)
  23     return f"{str(fixed)}:{repr(fixed)}"
  24
  25
  26 def get_core_op(alg_op):
  27     if alg_op is Operation.UDivRem:
  28         return DivPipeCoreOperation.UDivRem
  29     if alg_op is Operation.SqrtRem:
  30         return DivPipeCoreOperation.SqrtRem
  31     assert alg_op is Operation.RSqrtRem
  32     return DivPipeCoreOperation.RSqrtRem
  33
  34
  35 class TestCaseData:
  36     __test__ = False  # make pytest ignore class
  37
  38     def __init__(self,
  39                  dividend,
  40                  divisor_radicand,
  41                  alg_op,
  42                  quotient_root,
  43                  remainder,
  44                  core_config):
  45         self.dividend = dividend
  46         self.divisor_radicand = divisor_radicand
  47         self.alg_op = alg_op
  48         self.quotient_root = quotient_root
  49         self.remainder = remainder
  50         self.core_config = core_config
  51
  52     @property
  53     def core_op(self):
  54         return get_core_op(self.alg_op)
  55
  56     def __str__(self):
  57         bit_width = self.core_config.bit_width
  58         fract_width = self.core_config.fract_width
  59         dividend_str = show_fixed(self.dividend,
  60                                   fract_width * 2,
  61                                   bit_width + fract_width)
  62         divisor_radicand_str = show_fixed(self.divisor_radicand,
  63                                           fract_width,
  64                                           bit_width)
  65         quotient_root_str = show_fixed(self.quotient_root,
  66                                        fract_width,
  67                                        bit_width)
  68         remainder_str = show_fixed(self.remainder,
  69                                    fract_width * 3,
  70                                    bit_width * 3)
  71         return f"{{dividend={dividend_str}, " \
  72             + f"divisor_radicand={divisor_radicand_str}, " \
  73             + f"op={self.alg_op.name}, " \
  74             + f"quotient_root={quotient_root_str}, " \
  75             + f"remainder={remainder_str}, " \
  76             + f"config={self.core_config}}}"
  77
  78
  79 def generate_test_case(core_config, dividend, divisor_radicand, alg_op):
  80     bit_width = core_config.bit_width
  81     fract_width = core_config.fract_width
  82     obj = FixedUDivRemSqrtRSqrt(dividend,
  83                                 divisor_radicand,
  84                                 alg_op,
  85                                 bit_width,
  86                                 fract_width,
  87                                 core_config.log2_radix)
  88     obj.calculate()
  89     yield TestCaseData(dividend,
  90                        divisor_radicand,
  91                        alg_op,
  92                        obj.quotient_root,
  93                        obj.remainder,
  94                        core_config)
  95
  96
  97 def shifted_ints(total_bits, int_bits):
  98     """ Generate a sequence like a generalized binary version of A037124.
  99
 100         See https://oeis.org/A037124
 101
 102         Generates the sequence of all non-negative integers ``n`` in ascending
 103         order with no repeats where ``n < (1 << total_bits) and n == (v << i)``
 104         where ``i`` is a non-negative integer and ``v`` is a non-negative
 105         integer less than ``1 << int_bits``.
 106     """
 107     n = 0
 108     while n < (1 << total_bits):
 109         yield n
 110         if n < (1 << int_bits):
 111             n += 1
 112         else:
 113             n += 1 << (n.bit_length() - int_bits)
 114
 115
 116 def partitioned_ints(bit_width):
 117     """ Get ints with all 1s on one side and 0s on the other. """
 118     for i in range(bit_width):
 119         yield (-1 << i) & ((1 << bit_width) - 1)
 120         yield (1 << (i + 1)) - 1
 121
 122
 123 class TestShiftedInts(unittest.TestCase):
 124     def test(self):
 125         expected = [0x000,
 126                     0x001,
 127                     0x002, 0x003,
 128                     0x004, 0x005, 0x006, 0x007,
 129                     0x008, 0x009, 0x00A, 0x00B, 0x00C, 0x00D, 0x00E, 0x00F,
 130                     0x010, 0x012, 0x014, 0x016, 0x018, 0x01A, 0x01C, 0x01E,
 131                     0x020, 0x024, 0x028, 0x02C, 0x030, 0x034, 0x038, 0x03C,
 132                     0x040, 0x048, 0x050, 0x058, 0x060, 0x068, 0x070, 0x078,
 133                     0x080, 0x090, 0x0A0, 0x0B0, 0x0C0, 0x0D0, 0x0E0, 0x0F0,
 134                     0x100, 0x120, 0x140, 0x160, 0x180, 0x1A0, 0x1C0, 0x1E0,
 135                     0x200, 0x240, 0x280, 0x2C0, 0x300, 0x340, 0x380, 0x3C0,
 136                     0x400, 0x480, 0x500, 0x580, 0x600, 0x680, 0x700, 0x780,
 137                     0x800, 0x900, 0xA00, 0xB00, 0xC00, 0xD00, 0xE00, 0xF00]
 138         self.assertEqual(list(shifted_ints(12, 4)), expected)
 139
 140
 141 def get_test_cases(core_config,
 142                    dividends=None,
 143                    divisors=None,
 144                    radicands=None):
 145     if dividends is None:
 146         dividend_width = core_config.bit_width + core_config.fract_width
 147         dividends = [*shifted_ints(dividend_width,
 148                                    max(3, core_config.log2_radix)),
 149                      *partitioned_ints(dividend_width)]
 150     else:
 151         assert isinstance(dividends, list)
 152     if divisors is None:
 153         divisors = [*shifted_ints(core_config.bit_width,
 154                                   max(3, core_config.log2_radix)),
 155                     *partitioned_ints(core_config.bit_width)]
 156     else:
 157         assert isinstance(divisors, list)
 158     if radicands is None:
 159         radicands = [*shifted_ints(core_config.bit_width, 5),
 160                      *partitioned_ints(core_config.bit_width)]
 161     else:
 162         assert isinstance(radicands, list)
 163
 164     for alg_op in reversed(Operation):  # put UDivRem at end
 165         if get_core_op(alg_op) not in core_config.supported:
 166             continue
 167         if alg_op is Operation.UDivRem:
 168             for dividend in dividends:
 169                 for divisor in divisors:
 170                     yield from generate_test_case(core_config,
 171                                                   dividend,
 172                                                   divisor,
 173                                                   alg_op)
 174         else:
 175             for radicand in radicands:
 176                 yield from generate_test_case(core_config,
 177                                               0,
 178                                               radicand,
 179                                               alg_op)
 180
 181
 182 class DivPipeCoreTestPipeline(Elaboratable):
 183     def __init__(self, core_config, sync):
 184         self.setup_stage = DivPipeCoreSetupStage(core_config)
 185         self.calculate_stages = [
 186             DivPipeCoreCalculateStage(core_config, stage_index)
 187             for stage_index in range(core_config.n_stages)]
 188         self.final_stage = DivPipeCoreFinalStage(core_config)
 189         self.interstage_signals = [
 190             DivPipeCoreInterstageData(core_config, reset_less=True)
 191             for i in range(core_config.n_stages + 1)]
 192         self.i = DivPipeCoreInputData(core_config, reset_less=True)
 193         self.o = DivPipeCoreOutputData(core_config, reset_less=True)
 194         self.sync = sync
 195
 196     def elaborate(self, platform):
 197         m = Module()
 198         stages = [self.setup_stage, *self.calculate_stages, self.final_stage]
 199         stage_inputs = [self.i, *self.interstage_signals]
 200         stage_outputs = [*self.interstage_signals, self.o]
 201         for stage, input, output in zip(stages, stage_inputs, stage_outputs):
 202             stage.setup(m, input)
 203             assignments = output.eq(stage.process(input))
 204             if self.sync:
 205                 m.d.sync += assignments
 206             else:
 207                 m.d.comb += assignments
 208         return m
 209
 210     def traces(self):
 211         yield from self.i
 212         # for interstage_signal in self.interstage_signals:
 213         #     yield from interstage_signal
 214         yield from self.o
 215
 216
 217 class TestDivPipeCore(unittest.TestCase):
 218     def handle_config(self,
 219                       core_config,
 220                       test_cases=None,
 221                       sync=True):
 222         if test_cases is None:
 223             test_cases = get_test_cases(core_config)
 224         test_cases = list(test_cases)
 225         base_name = f"test_div_pipe_core_bit_width_{core_config.bit_width}"
 226         base_name += f"_fract_width_{core_config.fract_width}"
 227         base_name += f"_radix_{1 << core_config.log2_radix}"
 228         if not sync:
 229             base_name += "_comb"
 230         if core_config.supported != frozenset(DivPipeCoreOperation):
 231             name_map = {
 232                 DivPipeCoreOperation.UDivRem: "div",
 233                 DivPipeCoreOperation.SqrtRem: "sqrt",
 234                 DivPipeCoreOperation.RSqrtRem: "rsqrt",
 235             }
 236             # loop using iter(DivPipeCoreOperation) to maintain order
 237             for op in DivPipeCoreOperation:
 238                 if op in core_config.supported:
 239                     base_name += f"_{name_map[op]}"
 240             base_name+="_only"
 241
 242         with self.subTest(part="synthesize"):
 243             dut = DivPipeCoreTestPipeline(core_config, sync)
 244             vl = rtlil.convert(dut, ports=[*dut.i, *dut.o])
 245             with open(f"{base_name}.il", "w") as f:
 246                 f.write(vl)
 247         dut = DivPipeCoreTestPipeline(core_config, sync)
 248         sim = Simulator(dut)
 249         with sim.write_vcd(vcd_file=open(f"{base_name}.vcd", "w"),
 250                            gtkw_file=open(f"{base_name}.gtkw", "w"),
 251                            traces=[*dut.traces()]):
 252             def generate_process():
 253                 for test_case in test_cases:
 254                     if sync:
 255                         yield Tick()
 256                     yield dut.i.dividend.eq(test_case.dividend)
 257                     yield dut.i.divisor_radicand.eq(test_case.divisor_radicand)
 258                     yield dut.i.operation.eq(int(test_case.core_op))
 259                     if sync:
 260                         yield Delay(0.9e-6)
 261                     else:
 262                         yield Delay(1e-6)
 263
 264             def check_process():
 265                 # sync with generator
 266                 if sync:
 267                     yield Tick()
 268                     for _ in range(core_config.n_stages):
 269                         yield Tick()
 270                     yield Tick()
 271                 else:
 272                     yield Delay(0.5e-6)
 273
 274                 # now synched with generator
 275                 for test_case in test_cases:
 276                     if sync:
 277                         yield Tick()
 278                         yield Delay(0.9e-6)
 279                     else:
 280                         yield Delay(1e-6)
 281                     quotient_root = (yield dut.o.quotient_root)
 282                     remainder = (yield dut.o.remainder)
 283                     with self.subTest(test_case=str(test_case)):
 284                         self.assertEqual(quotient_root,
 285                                          test_case.quotient_root,
 286                                          str(test_case))
 287                         self.assertEqual(remainder, test_case.remainder,
 288                                          str(test_case))
 289             if sync:
 290                 sim.add_clock(2e-6)
 291             sim.add_process(generate_process)
 292             sim.add_process(check_process)
 293             sim.run()
 294
 295     def test_bit_width_2_fract_width_1_radix_2_comb(self):
 296         self.handle_config(DivPipeCoreConfig(bit_width=2,
 297                                              fract_width=1,
 298                                              log2_radix=1),
 299                            sync=False)
 300
 301     def test_bit_width_2_fract_width_1_radix_2(self):
 302         self.handle_config(DivPipeCoreConfig(bit_width=2,
 303                                              fract_width=1,
 304                                              log2_radix=1))
 305
 306     def test_bit_width_8_fract_width_4_radix_2_comb(self):
 307         self.handle_config(DivPipeCoreConfig(bit_width=8,
 308                                              fract_width=4,
 309                                              log2_radix=1),
 310                            sync=False)
 311
 312     def test_bit_width_8_fract_width_4_radix_2(self):
 313         self.handle_config(DivPipeCoreConfig(bit_width=8,
 314                                              fract_width=4,
 315                                              log2_radix=1))
 316
 317     def test_bit_width_8_fract_width_4_radix_4_comb(self):
 318         self.handle_config(DivPipeCoreConfig(bit_width=8,
 319                                              fract_width=4,
 320                                              log2_radix=2),
 321                            sync=False)
 322
 323     def test_bit_width_8_fract_width_4_radix_4(self):
 324         self.handle_config(DivPipeCoreConfig(bit_width=8,
 325                                              fract_width=4,
 326                                              log2_radix=2))
 327
 328     def test_bit_width_8_fract_width_4_radix_4_div_only(self):
 329         supported = (DivPipeCoreOperation.UDivRem,)
 330         self.handle_config(DivPipeCoreConfig(bit_width=8,
 331                                              fract_width=4,
 332                                              log2_radix=2,
 333                                              supported=supported))
 334
 335     def test_bit_width_8_fract_width_4_radix_4_comb_div_only(self):
 336         supported = (DivPipeCoreOperation.UDivRem,)
 337         self.handle_config(DivPipeCoreConfig(bit_width=8,
 338                                              fract_width=4,
 339                                              log2_radix=2,
 340                                              supported=supported),
 341                            sync=False)
 342
 343     @unittest.skip("really slow")
 344     def test_bit_width_32_fract_width_24_radix_8_comb(self):
 345         self.handle_config(DivPipeCoreConfig(bit_width=32,
 346                                              fract_width=24,
 347                                              log2_radix=3),
 348                            sync=False)
 349
 350     @unittest.skip("really slow")
 351     def test_bit_width_32_fract_width_24_radix_8(self):
 352         self.handle_config(DivPipeCoreConfig(bit_width=32,
 353                                              fract_width=24,
 354                                              log2_radix=3))
 355
 356     @unittest.skip("really slow")
 357     def test_bit_width_32_fract_width_28_radix_8_comb(self):
 358         self.handle_config(DivPipeCoreConfig(bit_width=32,
 359                                              fract_width=28,
 360                                              log2_radix=3),
 361                            sync=False)
 362
 363     @unittest.skip("really slow")
 364     def test_bit_width_32_fract_width_28_radix_8(self):
 365         self.handle_config(DivPipeCoreConfig(bit_width=32,
 366                                              fract_width=28,
 367                                              log2_radix=3))
 368
 369     # FIXME: add more test_* functions
 370
 371
 372 if __name__ == '__main__':
 373     unittest.main()