git.seregonwar.com

common/uint128.h

1	// SPDX-FileCopyrightText: Copyright 2019 yuzu Emulator Project
2	// SPDX-License-Identifier: GPL-2.0-or-later
3
4	#pragma once
5
6	#include <utility>
7
8	#ifdef _MSC_VER
9	#ifndef __clang__
10	#define HAS_INTRINSICS
11	#include <intrin.h>
12	#pragma intrinsic(__umulh)
13	#pragma intrinsic(_umul128)
14	#pragma intrinsic(_udiv128)
15	#else
16	#endif
17	#else
18	#include <cstring>
19	#endif
20
21	#include "common/shadpkg_types.h"
22
23	namespace Common {
24
25	// This function multiplies 2 u64 values and divides it by a u64 value.
26	[[nodiscard]] static inline u64 MultiplyAndDivide64(u64 a, u64 b, u64 d) {
27	#ifdef HAS_INTRINSICS
28	u128 r{};
29	r[0] = _umul128(a, b, &r[1]);
30	u64 remainder;
31	return _udiv128(r[1], r[0], d, &remainder);
32	#else
33	const u64 diva = a / d;
34	const u64 moda = a % d;
35	const u64 divb = b / d;
36	const u64 modb = b % d;
37	return diva * b + moda * divb + moda * modb / d;
38	#endif
39	}
40
41	// This function multiplies 2 u64 values and produces a u128 value;
42	[[nodiscard]] static inline u128 Multiply64Into128(u64 a, u64 b) {
43	u128 result;
44	#ifdef HAS_INTRINSICS
45	result[0] = _umul128(a, b, &result[1]);
46	#else
47	unsigned __int128 tmp = a;
48	tmp *= b;
49	std::memcpy(&result, &tmp, sizeof(u128));
50	#endif
51	return result;
52	}
53
54	[[nodiscard]] static inline u64 GetFixedPoint64Factor(u64 numerator, u64 divisor) {
55	#ifdef __SIZEOF_INT128__
56	const auto base = static_cast<unsigned __int128>(numerator) << 64ULL;
57	return static_cast<u64>(base / divisor);
58	#elif defined(_M_X64) \|\| defined(_M_ARM64)
59	std::array<u64, 2> r = {0, numerator};
60	u64 remainder;
61	return _udiv128(r[1], r[0], divisor, &remainder);
62	#else
63	// This one is bit more inaccurate.
64	return MultiplyAndDivide64(std::numeric_limits<u64>::max(), numerator, divisor);
65	#endif
66	}
67
68	[[nodiscard]] static inline u64 MultiplyHigh(u64 a, u64 b) {
69	#ifdef __SIZEOF_INT128__
70	return (static_cast<unsigned __int128>(a) * static_cast<unsigned __int128>(b)) >> 64;
71	#elif defined(_M_X64) \|\| defined(_M_ARM64)
72	return __umulh(a, b); // MSVC
73	#else
74	// Generic fallback
75	const u64 a_lo = u32(a);
76	const u64 a_hi = a >> 32;
77	const u64 b_lo = u32(b);
78	const u64 b_hi = b >> 32;
79
80	const u64 a_x_b_hi = a_hi * b_hi;
81	const u64 a_x_b_mid = a_hi * b_lo;
82	const u64 b_x_a_mid = b_hi * a_lo;
83	const u64 a_x_b_lo = a_lo * b_lo;
84
85	const u64 carry_bit = (static_cast<u64>(static_cast<u32>(a_x_b_mid)) +
86	static_cast<u64>(static_cast<u32>(b_x_a_mid)) + (a_x_b_lo >> 32)) >>
87	32;
88
89	const u64 multhi = a_x_b_hi + (a_x_b_mid >> 32) + (b_x_a_mid >> 32) + carry_bit;
90
91	return multhi;
92	#endif
93	}
94
95	// This function divides a u128 by a u32 value and produces two u64 values:
96	// the result of division and the remainder
97	[[nodiscard]] static inline std::pair<u64, u64> Divide128On32(const u128& dividend, u32 divisor) {
98	u64 remainder = dividend[0] % divisor;
99	u64 accum = dividend[0] / divisor;
100	if (dividend[1] == 0)
101	return {accum, remainder};
102	// We ignore dividend[1] / divisor as that overflows
103	const u64 first_segment = (dividend[1] % divisor) << 32;
104	accum += (first_segment / divisor) << 32;
105	const u64 second_segment = (first_segment % divisor) << 32;
106	accum += (second_segment / divisor);
107	remainder += second_segment % divisor;
108	if (remainder >= divisor) {
109	accum++;
110	remainder -= divisor;
111	}
112	return {accum, remainder};
113	}
114
115	} // namespace Common
116

Seregon/ShadPKG