From 3ea48e8ebe25686f2342cd79b32409fcd1bccb28 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Fri, 15 Feb 2019 19:26:41 -0400 Subject: Implement 128 bits Unsigned Integer Multiplication and Division. --- src/common/uint128.cpp | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) create mode 100644 src/common/uint128.cpp (limited to 'src/common/uint128.cpp') diff --git a/src/common/uint128.cpp b/src/common/uint128.cpp new file mode 100644 index 000000000..aea7f03e2 --- /dev/null +++ b/src/common/uint128.cpp @@ -0,0 +1,18 @@ + +namespace Common { + +std::pair udiv128(u128 dividend, u64 divisor) { + u64 remainder = dividend[0] % divisor; + u64 accum = dividend[0] / divisor; + if (dividend[1] == 0) + return {accum, remainder}; + // We ignore dividend[1] / divisor as that overflows + u64 first_segment = (dividend[1] % divisor) << 32; + accum += (first_segment / divisor) << 32; + u64 second_segment = (first_segment % divisor) << 32; + accum += (second_segment / divisor); + remainder += second_segment % divisor; + return {accum, remainder}; +} + +} // namespace Common -- cgit v1.2.3 From ecccfe033777d6ae7d29bcf0cfc30412f7d3be24 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Fri, 15 Feb 2019 20:04:11 -0400 Subject: Use u128 on Clock Cycles calculation. --- src/common/uint128.cpp | 24 +++++++++++++++++++++++- 1 file changed, 23 insertions(+), 1 deletion(-) (limited to 'src/common/uint128.cpp') diff --git a/src/common/uint128.cpp b/src/common/uint128.cpp index aea7f03e2..8548ba808 100644 --- a/src/common/uint128.cpp +++ b/src/common/uint128.cpp @@ -1,7 +1,25 @@ +#ifdef _MSC_VER +#include + +#pragma intrinsic(_umul128) +#endif +#include "common/uint128.h" namespace Common { +u128 Multiply64Into128(u64 a, u64 b) { +#ifdef _MSC_VER + u128 result; + result[0] = _umul128(a, b, &result[1]); +#else + unsigned __int128 tmp = a; + tmp *= b; + u128 result; + std::memcpy(&result, &tmp, sizeof(u128)); +#endif + return result; +} -std::pair udiv128(u128 dividend, u64 divisor) { +std::pair Divide128On64(u128 dividend, u64 divisor) { u64 remainder = dividend[0] % divisor; u64 accum = dividend[0] / divisor; if (dividend[1] == 0) @@ -12,6 +30,10 @@ std::pair udiv128(u128 dividend, u64 divisor) { u64 second_segment = (first_segment % divisor) << 32; accum += (second_segment / divisor); remainder += second_segment % divisor; + if (remainder >= divisor) { + accum++; + remainder -= divisor; + } return {accum, remainder}; } -- cgit v1.2.3 From a8d4927e29bb1acbf5f3267f368801847acd4222 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Sat, 16 Feb 2019 16:52:24 -0400 Subject: Corrections, documenting and fixes. --- src/common/uint128.cpp | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'src/common/uint128.cpp') diff --git a/src/common/uint128.cpp b/src/common/uint128.cpp index 8548ba808..2238a52c5 100644 --- a/src/common/uint128.cpp +++ b/src/common/uint128.cpp @@ -3,31 +3,32 @@ #pragma intrinsic(_umul128) #endif +#include #include "common/uint128.h" namespace Common { + u128 Multiply64Into128(u64 a, u64 b) { -#ifdef _MSC_VER u128 result; +#ifdef _MSC_VER result[0] = _umul128(a, b, &result[1]); #else unsigned __int128 tmp = a; tmp *= b; - u128 result; std::memcpy(&result, &tmp, sizeof(u128)); #endif return result; } -std::pair Divide128On64(u128 dividend, u64 divisor) { +std::pair Divide128On32(u128 dividend, u32 divisor) { u64 remainder = dividend[0] % divisor; u64 accum = dividend[0] / divisor; if (dividend[1] == 0) return {accum, remainder}; // We ignore dividend[1] / divisor as that overflows - u64 first_segment = (dividend[1] % divisor) << 32; + const u64 first_segment = (dividend[1] % divisor) << 32; accum += (first_segment / divisor) << 32; - u64 second_segment = (first_segment % divisor) << 32; + const u64 second_segment = (first_segment % divisor) << 32; accum += (second_segment / divisor); remainder += second_segment % divisor; if (remainder >= divisor) { -- cgit v1.2.3