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/CMakeLists.txt | 2 ++ src/common/uint128.cpp | 18 ++++++++++++++++++ src/common/uint128.h | 30 ++++++++++++++++++++++++++++++ 3 files changed, 50 insertions(+) create mode 100644 src/common/uint128.cpp create mode 100644 src/common/uint128.h (limited to 'src/common') diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt index bdd885273..b0174b445 100644 --- a/src/common/CMakeLists.txt +++ b/src/common/CMakeLists.txt @@ -113,6 +113,8 @@ add_library(common STATIC threadsafe_queue.h timer.cpp timer.h + uint128.cpp + uint128.h vector_math.h web_result.h ) 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 diff --git a/src/common/uint128.h b/src/common/uint128.h new file mode 100644 index 000000000..fda313bcc --- /dev/null +++ b/src/common/uint128.h @@ -0,0 +1,30 @@ +#include +#include +#include +#include +#include "common/common_types.h" + +namespace Common { + +#ifdef _MSC_VER +#include + +#pragma intrinsic(_umul128) +#endif + +inline u128 umul128(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); + +} // 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 +++++++++++++++++++++++- src/common/uint128.h | 23 +++-------------------- 2 files changed, 26 insertions(+), 21 deletions(-) (limited to 'src/common') 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}; } diff --git a/src/common/uint128.h b/src/common/uint128.h index fda313bcc..45e384c33 100644 --- a/src/common/uint128.h +++ b/src/common/uint128.h @@ -1,30 +1,13 @@ #include #include -#include #include +#include #include "common/common_types.h" namespace Common { -#ifdef _MSC_VER -#include - -#pragma intrinsic(_umul128) -#endif - -inline u128 umul128(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; -} +u128 Multiply64Into128(u64 a, u64 b); -std::pair udiv128(u128 dividend, u64 divisor); +std::pair Divide128On64(u128 dividend, u64 divisor); } // namespace Common -- 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 ++++++----- src/common/uint128.h | 9 +++++---- 2 files changed, 11 insertions(+), 9 deletions(-) (limited to 'src/common') 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) { diff --git a/src/common/uint128.h b/src/common/uint128.h index 45e384c33..52e6b46eb 100644 --- a/src/common/uint128.h +++ b/src/common/uint128.h @@ -1,13 +1,14 @@ -#include -#include -#include + #include #include "common/common_types.h" namespace Common { +// This function multiplies 2 u64 values and produces a u128 value; u128 Multiply64Into128(u64 a, u64 b); -std::pair Divide128On64(u128 dividend, u64 divisor); +// This function divides a u128 by a u32 value and produces two u64 values: +// the result of division and the remainder +std::pair Divide128On32(u128 dividend, u32 divisor); } // namespace Common -- cgit v1.2.3