[gem5-dev] Change in gem5/gem5[develop]: base: Create wide multiply functions in intmath.hh.
Gabe Black has submitted this change. (
https://gem5-review.googlesource.com/c/public/gem5/+/42358 )
Change subject: base: Create wide multiply functions in intmath.hh.
..
base: Create wide multiply functions in intmath.hh.
These implementations are from the x86 multiply microops. When
multipying two integers of a certain width together, these functions
will produce two values of the same size which hold the upper and lower
part of the multiplication result.
The version which works for 32 bit values and smaller just takes
advantage of 64 bit multiplication using standard types. The 64 bit
version needs to do more work since there isn't a built in standard
facility for doing those sorts of multiplications.
Change-Id: If7b3d3aa174dd13aae6f383772cbc5291181de5d
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/42358
Reviewed-by: Gabe Black
Maintainer: Gabe Black
Tested-by: kokoro
---
M src/base/intmath.hh
M src/base/intmath.test.cc
2 files changed, 211 insertions(+), 0 deletions(-)
Approvals:
Gabe Black: Looks good to me, approved; Looks good to me, approved
kokoro: Regressions pass
diff --git a/src/base/intmath.hh b/src/base/intmath.hh
index 0852913..308c33f 100644
--- a/src/base/intmath.hh
+++ b/src/base/intmath.hh
@@ -109,6 +109,91 @@
}
/**
+ * @ingroup api_base_utils
+ */
+template
+static constexpr std::enable_if_t
+mulUnsigned(std::make_unsigned_t , std::make_unsigned_t ,
+std::make_unsigned_t val_a, std::make_unsigned_t val_b)
+{
+uint64_t product = (uint64_t)val_a * (uint64_t)val_b;
+low = product;
+high = (product >> (sizeof(low) * 8));
+};
+
+/**
+ * @ingroup api_base_utils
+ */
+template
+static constexpr std::enable_if_t
+mulSigned(std::make_signed_t , std::make_signed_t ,
+ std::make_signed_t val_a, std::make_signed_t val_b)
+{
+uint64_t product = (int64_t)val_a * (int64_t)val_b;
+low = product;
+high = (product >> (sizeof(low) * 8));
+};
+
+/**
+ * @ingroup api_base_utils
+ * Multiply two values with place value p.
+ *
+ * (A * p + a) * (B * p + b) =
+ * (A * B) * p^2 + (a * B + A * b) * p + (a * b)
+ *
+ * low result = (a * B + A * b) * p + (a * b)
+ * high result = (A * B) + carry out from low result.
+ *
+ * As long as p is at most half the capacity of the underlying type, no
+ * individual multiplication will overflow. We just have to carefully
manage
+ * carries to avoid losing any during the addition steps.
+ */
+template
+static constexpr std::enable_if_t
+mulUnsigned(std::make_unsigned_t , std::make_unsigned_t ,
+std::make_unsigned_t val_a, std::make_unsigned_t val_b)
+{
+low = val_a * val_b;
+
+uint64_t A = (uint32_t)(val_a >> 32);
+uint64_t a = (uint32_t)val_a;
+uint64_t B = (uint32_t)(val_b >> 32);
+uint64_t b = (uint32_t)val_b;
+
+uint64_t c1 = 0, c2 = 0; // Carry between place values.
+uint64_t ab = a * b, Ab = A * b, aB = a * B, AB = A * B;
+
+c1 = (uint32_t)(ab >> 32);
+
+// Be careful to avoid overflow.
+c2 = (c1 >> 1) + (Ab >> 1) + (aB >> 1);
+c2 += ((c1 & 0x1) + (Ab & 0x1) + (aB & 0x1)) >> 1;
+c2 >>= 31;
+
+high = AB + c2;
+}
+
+/**
+ * @ingroup api_base_utils
+ */
+template
+static constexpr std::enable_if_t
+mulSigned(std::make_signed_t , std::make_signed_t ,
+ std::make_signed_t val_a, std::make_signed_t val_b)
+{
+uint64_t u_high = 0, u_low = 0;
+mulUnsigned(u_high, u_low, val_a, val_b);
+
+if (val_a < 0)
+u_high -= val_b;
+if (val_b < 0)
+u_high -= val_a;
+
+high = u_high;
+low = u_low;
+}
+
+/**
* This function is used to align addresses in memory.
*
* @param val is the address to be aligned.
diff --git a/src/base/intmath.test.cc b/src/base/intmath.test.cc
index 3baa502..4eb8aaf 100644
--- a/src/base/intmath.test.cc
+++ b/src/base/intmath.test.cc
@@ -112,6 +112,132 @@
EXPECT_EQ(46, divCeil(451, 10));
}
+TEST(IntmathTest, mulUnsignedNarrow)
+{
+uint8_t a = 0xff;
+uint8_t b = 0x02;
+uint8_t hi;
+uint8_t low;
+mulUnsigned(hi, low, a, b);
+EXPECT_EQ(hi, 0x1);
+EXPECT_EQ(low, 0xfe);
+
+a = 14;
+b = 9;
+mulUnsigned(hi, low, a, b);
+EXPECT_EQ(hi, 0);
+EXPECT_EQ(low, 0x7e);
+
+a = 0;
+b = 0x55;
+mulUnsigned(hi, low, a, b);
+EXPECT_EQ(hi, 0);
+EXPECT_EQ(low, 0);
+}
+
+TEST(IntmathTest, mulSignedNarrow)
+{
+int8_t a = -0x80;
+int8_t b = -0x7f;
+int8_t hi;
+int8_t low;
+mulSigned(hi, low, a, b);
+EXPECT_EQ(hi, 0x3f);
+EXPECT_EQ(low, -0x80);
+
+a = 14;
+b = -9;
+mulSigned(hi, low, a, b);
+EXPECT_EQ(hi, -0x01);
+EXPECT_EQ(low, -0x7e);
+
+a = 0;
+b = -0x55;
+mulSigned(hi, low, a, b);
+EXPECT_EQ(hi, 0);
+EXPECT_EQ(low, 0);
+}
+
+TEST(IntmathTest, mulUnsignedMid)
+{
+uint32_t a = 0xULL;
+uint32_t b = 0x0002ULL;
+uint32_t hi;
+uint32_t low;
+
[gem5-dev] Change in gem5/gem5[develop]: base: Create wide multiply functions in intmath.hh.
Gabe Black has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/42358 )
Change subject: base: Create wide multiply functions in intmath.hh.
..
base: Create wide multiply functions in intmath.hh.
These implementations are from the x86 multiply microops. When
multipying two integers of a certain width together, these functions
will produce two values of the same size which hold the upper and lower
part of the multiplication result.
The version which works for 32 bit values and smaller just takes
advantage of 64 bit multiplication using standard types. The 64 bit
version needs to do more work since there isn't a built in standard
facility for doing those sorts of multiplications.
Change-Id: If7b3d3aa174dd13aae6f383772cbc5291181de5d
---
M src/base/intmath.hh
M src/base/intmath.test.cc
2 files changed, 121 insertions(+), 0 deletions(-)
diff --git a/src/base/intmath.hh b/src/base/intmath.hh
index acf7681..8c88ae7 100644
--- a/src/base/intmath.hh
+++ b/src/base/intmath.hh
@@ -117,6 +117,83 @@
}
/**
+ * @ingroup api_base_utils
+ * Multiply two values Aa and Bb where Aa = A << p + a.
+ * Aa * Bb
+ * = (A << p + a) * (B << p + b)
+ * = (A * B) << 2p + (A * b + a * B) << p + a * b
+ */
+template
+static constexpr std::enable_if_t
+mulUnsigned(std::make_unsigned_t , std::make_unsigned_t ,
+std::make_unsigned_t val_a, std::make_unsigned_t val_b)
+{
+uint64_t product = (uint64_t)val_a * (uint64_t)val_b;
+low = product;
+hi = (product >> (sizeof(low) * 8));
+};
+
+template
+static constexpr std::enable_if_t
+mulSigned(std::make_signed_t , std::make_signed_t ,
+ std::make_signed_t val_a, std::make_signed_t val_b)
+{
+uint64_t product = (int64_t)val_a * (int64_t)val_b;
+low = product;
+hi = (product >> (sizeof(low) * 8));
+};
+
+template
+static constexpr std::enable_if_t
+mulUnsigned(std::make_unsigned_t , std::make_unsigned_t ,
+std::make_unsigned_t val_a, std::make_unsigned_t val_b)
+{
+low = val_a * val_b;
+
+uint64_t A = (uint32_t)(val_a >> 32);
+uint64_t a = (uint32_t)val_a;
+uint64_t B = (uint32_t)(val_b >> 32);
+uint64_t b = (uint32_t)val_b;
+
+uint64_t c1, c2; // Carry between place values.
+uint64_t ab = a * b, Ab = A * b, aB = a * B, AB = A * B;
+
+c1 = (uint32_t)(ab >> 32);
+
+// Be careful to avoid overflow.
+c2 = (c1 >> 1) + (Ab >> 1) + (aB >> 1);
+c2 += ((c1 & 0x1) + (Ab & 0x1) + (aB & 0x1)) >> 1;
+c2 >>= 31;
+
+hi = AB + c2;
+}
+
+template
+static constexpr std::enable_if_t
+mulSigned(std::make_signed_t , std::make_signed_t ,
+ std::make_signed_t val_a, std::make_signed_t val_b)
+{
+uint64_t u_hi, u_low;
+mulUnsigned(u_hi, u_low, val_a, val_b);
+
+if (val_a < 0)
+u_hi -= val_b;
+if (val_b < 0)
+u_hi -= val_a;
+
+hi = u_hi;
+low = u_low;
+}
+
+/**
+ * @ingroup api_base_utils
+ */
+static constexpr void
+mulSigned(uint64_t , uint64_t , uint64_t a, uint64_t b)
+{
+}
+
+/**
* This function is used to align addresses in memory.
*
* @param val is the address to be aligned.
diff --git a/src/base/intmath.test.cc b/src/base/intmath.test.cc
index e985a1b..55d3e71 100644
--- a/src/base/intmath.test.cc
+++ b/src/base/intmath.test.cc
@@ -108,6 +108,50 @@
EXPECT_EQ(46, divCeil(451, 10));
}
+TEST(IntmathTest, mulUnsignedNarrow)
+{
+uint8_t a = 0xff;
+uint8_t b = 0x02;
+uint8_t hi;
+uint8_t low;
+mulUnsigned(hi, low, a, b);
+EXPECT_EQ(hi, 0x1);
+EXPECT_EQ(low, 0xfe);
+}
+
+TEST(IntmathTest, mulSignedNarrow)
+{
+int8_t a = -0x80;
+int8_t b = -0x7f;
+int8_t hi;
+int8_t low;
+mulSigned(hi, low, a, b);
+EXPECT_EQ(hi, 0x3f);
+EXPECT_EQ(low, -0x80);
+}
+
+TEST(IntmathTest, mulUnsignedWide)
+{
+uint64_t a = 0xULL;
+uint64_t b = 0x0002ULL;
+uint64_t hi;
+uint64_t low;
+mulUnsigned(hi, low, a, b);
+EXPECT_EQ(hi, 0x1);
+EXPECT_EQ(low, 0xfffe);
+}
+
+TEST(IntMathTest, mulSignedWide)
+{
+int64_t a = -0x8000;
+int64_t b = -0x7fff;
+int64_t hi;
+int64_t low;
+mulSigned(hi, low, a, b);
+EXPECT_EQ(hi, 0x3fff);
+EXPECT_EQ(low, -0x8000);
+}
+
TEST(IntmathTest, roundUp)
{
EXPECT_EQ(4104, roundUp(4101, 4));
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/42358
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: If7b3d3aa174dd13aae6f383772cbc5291181de5d
Gerrit-Change-Number: 42358
Gerrit-PatchSet: 1
Gerrit-Owner: Gabe Black
Gerrit-MessageType: newchange
___
gem5-dev mailing list -- gem5-dev@gem5.org
To unsubscribe send an email to gem5-dev-le...@gem5.org
