src/ieee754/div_rem_sqrt_rsqrt/algorithm.py

   1 # SPDX-License-Identifier: LGPL-2.1-or-later
   2 # See Notices.txt for copyright information
   3
   4 """ Algorithms for div/rem/sqrt/rsqrt.
   5
   6 code for simulating/testing the various algorithms
   7 """
   8
   9 from nmigen.hdl.ast import Const
  10
  11
  12 def div_rem(dividend, divisor, bit_width, signed):
  13     """ Compute the quotient/remainder following the RISC-V M extension.
  14
  15     NOT the same as the // or % operators
  16     """
  17     dividend = Const.normalize(dividend, (bit_width, signed))
  18     divisor = Const.normalize(divisor, (bit_width, signed))
  19     if divisor == 0:
  20         quotient = -1
  21         remainder = dividend
  22     else:
  23         quotient = abs(dividend) // abs(divisor)
  24         remainder = abs(dividend) % abs(divisor)
  25         if (dividend < 0) != (divisor < 0):
  26             quotient = -quotient
  27         if dividend < 0:
  28             remainder = -remainder
  29     quotient = Const.normalize(quotient, (bit_width, signed))
  30     remainder = Const.normalize(remainder, (bit_width, signed))
  31     return quotient, remainder
  32
  33
  34 class UnsignedDivRem:
  35     """ Unsigned integer division/remainder following the RISC-V M extension.
  36
  37     NOT the same as the // or % operators
  38
  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
  46     """
  47
  48     def __init__(self, dividend, divisor, bit_width, log2_radix=3):
  49         """ Create an UnsignedDivRem.
  50
  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.
  56         """
  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
  61         self.quotient = 0
  62         self.current_shift = bit_width
  63
  64     def calculate_stage(self):
  65         """ Calculate the next pipeline stage of the division.
  66
  67         :returns bool: True if this is the last pipeline stage.
  68         """
  69         if self.current_shift == 0:
  70             return True
  71         log2_radix = min(self.log2_radix, self.current_shift)
  72         assert log2_radix > 0
  73         self.current_shift -= log2_radix
  74         radix = 1 << log2_radix
  75         remainders = []
  76         for i in range(radix):
  77             v = (self.divisor * i) << self.current_shift
  78             remainders.append(self.remainder - v)
  79         quotient_bits = 0
  80         for i in range(radix):
  81             if remainders[i] >= 0:
  82                 quotient_bits = i
  83         self.remainder = remainders[quotient_bits]
  84         self.quotient |= quotient_bits << self.current_shift
  85         return self.current_shift == 0
  86
  87     def calculate(self):
  88         """ Calculate the results of the division.
  89
  90         :returns: self
  91         """
  92         while not self.calculate_stage():
  93             pass
  94         return self
  95
  96
  97 class DivRem:
  98     """ integer division/remainder following the RISC-V M extension.
  99
 100     NOT the same as the // or % operators
 101
 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
 108     """
 109
 110     def __init__(self, dividend, divisor, bit_width, signed, log2_radix=3):
 111         """ Create a DivRem.
 112
 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.
 119         """
 120         self.dividend = Const.normalize(dividend, (bit_width, signed))
 121         self.divisor = Const.normalize(divisor, (bit_width, signed))
 122         self.signed = signed
 123         self.quotient = 0
 124         self.remainder = 0
 125         self.divider = UnsignedDivRem(abs(dividend), abs(divisor),
 126                                       bit_width, log2_radix)
 127
 128     def calculate_stage(self):
 129         """ Calculate the next pipeline stage of the division.
 130
 131         :returns bool: True if this is the last pipeline stage.
 132         """
 133         if not self.divider.calculate_stage():
 134             return False
 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
 139         else:
 140             quotient = self.divider.quotient
 141         if dividend_sign:
 142             remainder = -self.divider.remainder
 143         else:
 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))
 148         return True