From 2e52942b806617524a1880c2b5961a0d66a4f061 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Thu, 11 May 2023 01:05:04 -0700 Subject: [PATCH] SelectableMSB0Fraction is now basically complete and correct afaict --- src/openpower/decoder/fp_working_format.py | 113 +++++++--- .../decoder/test_fp_working_format.py | 201 ++++++++++++++++++ 2 files changed, 285 insertions(+), 29 deletions(-) create mode 100644 src/openpower/decoder/test_fp_working_format.py diff --git a/src/openpower/decoder/fp_working_format.py b/src/openpower/decoder/fp_working_format.py index 5defead7..e3176041 100644 --- a/src/openpower/decoder/fp_working_format.py +++ b/src/openpower/decoder/fp_working_format.py @@ -106,11 +106,17 @@ class BFPStateClass: class SelectableMSB0Fraction: - """a MSB0 infinite bit string that is really a real number between 0 and 1, - but we approximate it using a Fraction. + """a MSB0 infinite bit string that is a real number generally between 0 + and 2, but we approximate it using a Fraction. - this is not just SelectableInt because we need more than 256 bits and - because this isn't an integer. + bit 0 is the lsb of the integer part, + bit 1 is the msb of the fraction part, + bit 2 is the next-to-msb of the fraction part, etc. + + this is not SelectableInt because we need more bits and because this isn't + an integer -- it can represent unlimited values, both really small and + really large -- corresponding to having bits be able to be set in bit + indexes 0, -1, -2, -3, etc. """ def __init__(self, value=None): @@ -133,7 +139,9 @@ class SelectableMSB0Fraction: # use int() to convert from start = int(0 if index.start is None else index.start) stop = int(index.stop) - length = stop - start + 1 + # pseudo-code compiler converts from inclusive to + # standard Python slices + length = stop - start else: start = int(index) length = 1 @@ -142,16 +150,20 @@ class SelectableMSB0Fraction: def __slice_as_int(self, start, length): if start < 0 or length < 0: raise ValueError("slice out of range") - end = start + length + if length == 0: + return 0 + last = start + length - 1 # shift so bits we want are the lsb bits of the integer part - v = math.floor(self.value * (1 << end)) + v = math.floor(self.value * (1 << last)) return v & ~(~0 << length) # mask off unwanted bits def __set_slice(self, start, length, value): if start < 0 or length < 0: raise ValueError("slice out of range") - end = start + length - shift_factor = 1 << end + if length == 0: + return + last = start + length - 1 + shift_factor = 1 << last # shift so bits we want to replace are the lsb bits of the integer part v = self.value * shift_factor mask = ~(~0 << length) @@ -160,7 +172,7 @@ class SelectableMSB0Fraction: # compute how much we need to add offset = value - (math.floor(v) & mask) # shift offset back into position - offset /= shift_factor + offset = Fraction(offset, shift_factor) self.value += offset def __getitem__(self, index): @@ -179,7 +191,7 @@ class SelectableMSB0Fraction: ): """ convert to a string of the form: `0x3a.bc` or `0x...face.face_face_face_face... (0xa8ef0000 / 0x5555)`""" - if max_int_digits < 0 or max_fraction_digits < 0: + if max_int_digits <= 0 or max_fraction_digits <= 0: raise ValueError("invalid digit limit") approx = False int_part = math.floor(self.value) @@ -191,21 +203,22 @@ class SelectableMSB0Fraction: int_part %= int_part_limit int_str = f"0x...{int_part:0{max_int_digits}x}" - # is the denominator a power of 2? - if (self.value.denominator & (self.value.denominator - 1)) == 0: - fraction_bits = self.value.denominator.bit_length() - 1 - fraction_digits = -(-fraction_bits) // 4 # ceil division by 4 + factor = 0x10 ** max_fraction_digits + fraction_part_exact = (self.value - math.floor(self.value)) * factor + fraction_part = math.floor(fraction_part_exact) + + if fraction_part == fraction_part_exact: + # extract least-significant set bit of fraction_part + fraction_part_lsb = fraction_part & -fraction_part + log2_fraction_part_lsb = fraction_part_lsb.bit_length() - 1 + zero_fraction_digits = max(0, log2_fraction_part_lsb // 4) + fraction_part >>= 4 * zero_fraction_digits + fraction_digits = max_fraction_digits - zero_fraction_digits + suffix = "" else: - # something bigger than max_fraction_digits - fraction_digits = max_fraction_digits + 1 - if fraction_digits > max_fraction_digits: suffix = "..." approx = True fraction_digits = max_fraction_digits - else: - suffix = "" - factor = 0x10 ** fraction_digits - fraction_part = math.floor(self.value * factor) fraction_str = f"{fraction_part:0{fraction_digits}x}" fraction_parts = [] if fraction_sep_period is not None and fraction_sep_period > 0: @@ -216,10 +229,28 @@ class SelectableMSB0Fraction: retval = int_str if self.value.denominator != 1: retval += fraction_str + else: + retval += ".0" if approx: n = self.value.numerator d = self.value.denominator - retval += f" ({n:#x} / {d:#x})" + fraction = f" ({n:#x} / {d:#x})" + + # is the denominator a power of 2? + if (self.value.denominator & (self.value.denominator - 1)) == 0: + log2_d = self.value.denominator.bit_length() - 1 + + if self.value.denominator == 1: + fraction = f" ({n:#x})" + + # extract least-significant set bit of n + n_lsb = n & -n + n //= n_lsb + log2_n_lsb = n_lsb.bit_length() - 1 + exponent = log2_n_lsb - log2_d + if exponent < -8 or exponent > 8: + fraction = f" ({n:#x} * 2**{exponent})" + retval += fraction return retval def __repr__(self): @@ -242,6 +273,18 @@ class SelectableMSB0Fraction: def __pos__(self): return SelectableMSB0Fraction(self) + def __floor__(self): + return SelectableMSB0Fraction(math.floor(self.value)) + + def __ceil__(self): + return SelectableMSB0Fraction(math.ceil(self.value)) + + def __trunc__(self): + return SelectableMSB0Fraction(math.trunc(self.value)) + + def __round__(self): + return SelectableMSB0Fraction(round(self.value)) + @staticmethod def __arith_op(lhs, rhs, op): lhs = SelectableMSB0Fraction(lhs) @@ -270,6 +313,18 @@ class SelectableMSB0Fraction: def __rtruediv__(self, other): return self.__arith_op(other, self, operator.truediv) + def __floordiv__(self, other): + return self.__arith_op(self, other, operator.floordiv) + + def __rfloordiv__(self, other): + return self.__arith_op(other, self, operator.floordiv) + + def __mod__(self, other): + return self.__arith_op(self, other, operator.mod) + + def __rmod__(self, other): + return self.__arith_op(other, self, operator.mod) + def __lshift__(self, amount): if not isinstance(amount, int): raise TypeError("can't shift by non-int") @@ -298,22 +353,22 @@ class SelectableMSB0Fraction: return op(self.value, other) def __eq__(self, other): - return self.__cmp_op(self, other, operator.eq) + return self.__cmp_op(other, operator.eq) def __ne__(self, other): - return self.__cmp_op(self, other, operator.ne) + return self.__cmp_op(other, operator.ne) def __lt__(self, other): - return self.__cmp_op(self, other, operator.lt) + return self.__cmp_op(other, operator.lt) def __le__(self, other): - return self.__cmp_op(self, other, operator.le) + return self.__cmp_op(other, operator.le) def __gt__(self, other): - return self.__cmp_op(self, other, operator.gt) + return self.__cmp_op(other, operator.gt) def __ge__(self, other): - return self.__cmp_op(self, other, operator.ge) + return self.__cmp_op(other, operator.ge) class BFPState: diff --git a/src/openpower/decoder/test_fp_working_format.py b/src/openpower/decoder/test_fp_working_format.py new file mode 100644 index 00000000..56436102 --- /dev/null +++ b/src/openpower/decoder/test_fp_working_format.py @@ -0,0 +1,201 @@ +import unittest +from openpower.decoder.fp_working_format import ( + BFPState, SelectableMSB0Fraction) +from fractions import Fraction +import math + + +class TestSelectableMSB0Fraction(unittest.TestCase): + def test_repr(self): + def check(v, pos, neg): + v = Fraction(v) + with self.subTest(v=f"{v.numerator:#x} / {v.denominator:#x}", + pos=pos, neg=neg): + pos = f"SelectableMSB0Fraction({pos})" + neg = f"SelectableMSB0Fraction({neg})" + self.assertEqual(repr(SelectableMSB0Fraction(v)), pos) + self.assertEqual(repr(SelectableMSB0Fraction(-v)), neg) + check(0, "0x0.0", "0x0.0") + check(1, "0x1.0", "0x...ffff.0 (-0x1)") + check(0x2, "0x2.0", "0x...fffe.0 (-0x2)") + check(0x4, "0x4.0", "0x...fffc.0 (-0x4)") + check(0x8, "0x8.0", "0x...fff8.0 (-0x8)") + check(0x10, "0x10.0", "0x...fff0.0 (-0x10)") + check(0x100, "0x100.0", "0x...ff00.0 (-0x100)") + check(0x1000, "0x1000.0", "0x...f000.0 (-0x1 * 2**12)") + check(0x10000, + "0x...0000.0 (0x1 * 2**16)", "0x...0000.0 (-0x1 * 2**16)") + check(0x100000, + "0x...0000.0 (0x1 * 2**20)", "0x...0000.0 (-0x1 * 2**20)") + check(0x1000000, + "0x...0000.0 (0x1 * 2**24)", "0x...0000.0 (-0x1 * 2**24)") + check(Fraction(1, 1 << 1), "0x0.8", "0x...ffff.8 (-0x1 / 0x2)") + check(Fraction(1, 1 << 2), "0x0.4", "0x...ffff.c (-0x1 / 0x4)") + check(Fraction(1, 1 << 3), "0x0.2", "0x...ffff.e (-0x1 / 0x8)") + check(Fraction(1, 1 << 4), "0x0.1", "0x...ffff.f (-0x1 / 0x10)") + check(Fraction(1, 1 << 8), "0x0.01", "0x...ffff.ff (-0x1 / 0x100)") + check(Fraction(1, 1 << 12), "0x0.001", "0x...ffff.fff (-0x1 * 2**-12)") + check(Fraction(1, 1 << 16), + "0x0.0001", "0x...ffff.ffff (-0x1 * 2**-16)") + check(Fraction(1, 1 << 20), + "0x0.0000_1", "0x...ffff.ffff_f (-0x1 * 2**-20)") + check(Fraction(1, 1 << 24), + "0x0.0000_01", "0x...ffff.ffff_ff (-0x1 * 2**-24)") + check(Fraction(1, 1 << 28), + "0x0.0000_001", "0x...ffff.ffff_fff (-0x1 * 2**-28)") + check(Fraction(1, 1 << 32), + "0x0.0000_0001", "0x...ffff.ffff_ffff (-0x1 * 2**-32)") + check(Fraction(1, 1 << 36), + "0x0.0000_0000_1", "0x...ffff.ffff_ffff_f (-0x1 * 2**-36)") + check(Fraction(1, 1 << 40), + "0x0.0000_0000_01", "0x...ffff.ffff_ffff_ff (-0x1 * 2**-40)") + check(Fraction(1, 1 << 44), + "0x0.0000_0000_001", "0x...ffff.ffff_ffff_fff (-0x1 * 2**-44)") + check(Fraction(1, 1 << 48), + "0x0.0000_0000_0001", "0x...ffff.ffff_ffff_ffff (-0x1 * 2**-48)") + check(Fraction(1, 1 << 52), + "0x0.0000_0000_0000_1", + "0x...ffff.ffff_ffff_ffff_f (-0x1 * 2**-52)") + check(Fraction(1, 1 << 56), + "0x0.0000_0000_0000_01", + "0x...ffff.ffff_ffff_ffff_ff (-0x1 * 2**-56)") + check(Fraction(1, 1 << 60), + "0x0.0000_0000_0000_001", + "0x...ffff.ffff_ffff_ffff_fff (-0x1 * 2**-60)") + check(Fraction(1, 1 << 64), + "0x0.0000_0000_0000_0001", + "0x...ffff.ffff_ffff_ffff_ffff (-0x1 * 2**-64)") + check(Fraction(1, 1 << 68), + "0x0.0000_0000_0000_0000_1", + "0x...ffff.ffff_ffff_ffff_ffff_f (-0x1 * 2**-68)") + check(Fraction(1, 1 << 72), + "0x0.0000_0000_0000_0000_0... (0x1 * 2**-72)", + "0x...ffff.ffff_ffff_ffff_ffff_f... (-0x1 * 2**-72)") + check(Fraction(1, 1 << 76), + "0x0.0000_0000_0000_0000_0... (0x1 * 2**-76)", + "0x...ffff.ffff_ffff_ffff_ffff_f... (-0x1 * 2**-76)") + check(Fraction(1, 3), + "0x0.5555_5555_5555_5555_5... (0x1 / 0x3)", + "0x...ffff.aaaa_aaaa_aaaa_aaaa_a... (-0x1 / 0x3)") + check(Fraction(1, 5), + "0x0.3333_3333_3333_3333_3... (0x1 / 0x5)", + "0x...ffff.cccc_cccc_cccc_cccc_c... (-0x1 / 0x5)") + check(Fraction(1, 7), + "0x0.2492_4924_9249_2492_4... (0x1 / 0x7)", + "0x...ffff.db6d_b6db_6db6_db6d_b... (-0x1 / 0x7)") + check(Fraction(1234, 4567), + "0x0.452b_c745_e653_bec0_b... (0x4d2 / 0x11d7)", + "0x...ffff.bad4_38ba_19ac_413f_4... (-0x4d2 / 0x11d7)") + check(Fraction(0x123456789abcdef, 0x1234567), + "0x...0079.0000_3840_001a_9640_0... " + "(0x123456789abcdef / 0x1234567)", + "0x...ff86.ffff_c7bf_ffe5_69bf_f... " + "(-0x123456789abcdef / 0x1234567)") + # decent approximation to math.tau + check(Fraction(312689, 49766), + "0x6.487e_d511_4b5c_560c_d... (0x4c571 / 0xc266)", + "0x...fff9.b781_2aee_b4a3_a9f3_2... (-0x4c571 / 0xc266)") + check(Fraction(0xface0000, 0xffff), + "0xface.face_face_face_face_f... (0x539a0000 / 0x5555)", + "0x...0531.0531_0531_0531_0531_0... (-0x539a0000 / 0x5555)") + + def test_ops(self): + inputs = [1, 4, 6, Fraction(1, 2), Fraction(1, 3), Fraction(2, 3)] + inputs.extend([-i for i in inputs]) + inputs.append(0) + for a in inputs: + for b in inputs: + with self.subTest(a=a, b=b): + af = SelectableMSB0Fraction(a) + bf = SelectableMSB0Fraction(b) + self.assertEqual(af.value, a) + self.assertEqual((+af).value, a) + self.assertEqual((-af).value, -a) + self.assertEqual(math.floor(af).value, math.floor(a)) + self.assertEqual(math.ceil(af).value, math.ceil(a)) + self.assertEqual(math.trunc(af).value, math.trunc(a)) + self.assertEqual(round(af).value, round(a)) + self.assertEqual((af + bf).value, a + b) + self.assertEqual((af - bf).value, a - b) + self.assertEqual((af * bf).value, a * b) + self.assertEqual(af == bf, a == b) + self.assertEqual(af != bf, a != b) + self.assertEqual(af < bf, a < b) + self.assertEqual(af <= bf, a <= b) + self.assertEqual(af > bf, a > b) + self.assertEqual(af >= bf, a >= b) + if b != 0: + self.assertEqual((af / bf).value, a / Fraction(b)) + self.assertEqual((af // bf).value, a // b) + self.assertEqual((af % bf).value, a % b) + if isinstance(b, int): + if b >= 0: + pow2_b = Fraction(1 << b) + else: + pow2_b = Fraction(1, 1 << -b) + self.assertEqual((af << b).value, a * pow2_b) + self.assertEqual((af >> b).value, a / pow2_b) + + def slice_helper(self, v, start, length): + f = SelectableMSB0Fraction(v) + if length > 0: + expected = v + # expected is 0b...XX.XXXmybitsXXX... where mybits is what we want + expected *= 1 << start + # expected is 0b...XXm.ybitsXXX... + expected *= 1 << (length - 1) + # expected is 0b...XXmybits.XX... + expected = math.floor(expected) + # expected is 0b...XXmybits + expected %= 1 << length + # expected is 0bmybits + else: + expected = 0 + with self.subTest(expected=hex(expected), f=str(f)): + self.assertEqual(hex(expected), hex(int(f[start:start+length]))) + if length == 1: + self.assertEqual(hex(expected), hex(int(f[start]))) + for replace in (0x5555, 0xffff, 0xaaaa, 0): + expected = v + # expected is 0b...XX.XXXoldbitsYY... + # where oldbits is what we want to replace with newbits + if length > 0: + expected *= 1 << start + # expected is 0b...XXo.ldbitsYYY... + expected *= 1 << (length - 1) + # expected is 0b...XXoldbits.YY... + fraction = expected - math.floor(expected) + # fraction is 0b.YYY... + expected = math.floor(expected) + # expected is 0b...XXoldbits + expected -= expected % (1 << length) + # expected is 0b...XX0000000 + expected |= replace % (1 << length) + # expected is 0b...XXnewbits + expected += fraction + # expected is 0b...XXnewbits.YY... + expected /= 1 << (length - 1) + # expected is 0b...XXn.ewbitsYYY... + expected /= 1 << start + # expected is 0b...XX.XXXnewbitsYY... + expected = SelectableMSB0Fraction(expected) + with self.subTest(expected=str(expected), + replace=hex(replace)): + f = SelectableMSB0Fraction(v) + f[start:start+length] = replace + self.assertEqual(f, expected) + if length == 1: + f = SelectableMSB0Fraction(v) + f[start] = replace + self.assertEqual(f, expected) + + def test_slice(self): + for v in [Fraction(0xface0000, 0xffff), Fraction(0x1230000, 0xffff)]: + for start in range(0, 17): + for length in reversed(range(0, 17)): + with self.subTest(v=v, start=start, length=length): + self.slice_helper(v, start, length) + + +if __name__ == "__main__": + unittest.main() -- 2.30.2